Data Efficient Sample Selection for In-Context Learning¶
Conference: EMNLP 2026
Paper: ACL Anthology
Code: https://github.com/VenkteshV/DearICL
Area: LLM Reasoning
Keywords: in-context learning, exemplar selection, multi-armed bandits, learning to rank, sample complexity
TL;DR¶
Addressing the generalization limits of static selection and the latency of online search, DEARICL recasts demonstration subset selection as an instance-level ranking problem, utilizing a multi-armed bandit top-\(m\) auxiliary objective to sample informative borderline arms and train a non-linear differentiable sorting surrogate with 63%–75% fewer LLM queries and up to 15.99% accuracy improvement.
Background & Motivation¶
In-context learning (ICL) has fundamentally altered how large language models (LLMs) solve complex tasks, allowing models to adapt on the fly without gradient updates merely by conditioning on a sequence of demonstration input-output pairs \((v, w)\) followed by a target test input. However, in realistic scenarios with large exemplar pools, choosing demonstrations arbitrarily or through rudimentary heuristics often yields poor or unstable downstream performance. To address this, prior literature commonly formulates exemplar selection as a subset selection problem, with a prominent line of research focusing on task-level static selection: choosing a single, near-optimal subset offline that maximizes average validation performance across a target domain. Recent frameworks (such as EXPLORA and CASE) cast this task as top-\(m\) arm identification within stochastic multi-armed bandits (MABs), viewing each candidate subset as an arm and utilizing LLM validation rewards to discard sub-optimal arms with reduced sample complexity.
Despite these advancements, existing selection formulations face two fundamental bottlenecks. First, state-of-the-art bandit approaches overwhelmingly rely on linear surrogates to map arm features to expected performance. In practice, LLM in-context reasoning depends heavily on complex, combinatorial multi-sample interactions across attention layers; the downstream reward landscape is non-convex, non-linear, and poorly approximated by linear assumptions. Second, task-level static selection enforces a single fixed exemplar subset for all incoming queries, which inevitably fails to generalize whenever unseen test queries require reasoning patterns or domain concepts absent from that static set. Conversely, fully dynamic (instance-level) selection constructs prompts tailored to each individual query, but running bandit exploration to convergence per query incurs prohibitive inference latency, while unsupervised retrieval heuristics (such as KNN or MMR) select samples independently based on embedding distance without accounting for collective joint synergy or downstream reward feedback.
To reconcile the expressive flexibility of instance-level subset selection with the sample efficiency of multi-armed bandits, demonstration selection must unite active exploration with differentiable ranking. The system requires an adaptive sampling engine capable of distinguishing subtle, near-optimal subset configurations from deceiving borderline contenders without wasting queries on clearly inferior combinations. The core idea is to employ top-\(m\) arm identification in a gap-index bandit framework as an auxiliary exploration objective in the outer loop, explicitly sampling ambiguous borderline arms to fit a lightweight non-linear surrogate via a differentiable sorting objective in the inner loop, thereby enabling instantaneous, instance-level subset ranking at inference time.
Method¶
Overall Architecture¶
DEARICL implements a dual-loop optimization framework connecting active multi-armed bandit exploration in the outer loop with differentiable learning-to-rank (LTR) in the inner loop. The pipeline takes as input a pool of candidate exemplars \(\mathcal{Q}\), prompt exemplar size \(k\), a validation query set \(\mathcal{V}\), target top-\(m\) size, and challenger set size \(m'\); it outputs a trained non-linear ranking surrogate \(F_\theta\).
During the offline selection phase, the algorithm iteratively tracks an estimated set of optimal arms \(\mathcal{U}_t\) and a challenger pool \(\mathcal{C}_t\). The outer loop calculates empirical mean estimates using sentence embeddings across prompt exemplars and queries, determines the most ambiguous arm pair \((b_t, ch_t)\) based on a derived gap-index bound that incorporates Monte Carlo Dropout variance and algorithmic stability, and queries the downstream LLM on the most informative borderline arm. The resulting instance-level reward is stored in dataset \(\mathcal{D}\). The inner loop then updates the multi-layer non-linear surrogate \(F_\theta\) via one epoch of SGD minimizing a relaxed differentiable NDCG loss. Once the gap-index of the ambiguity frontier drops below a predefined threshold \(\epsilon\), the algorithm terminates; the learned surrogate \(F_\theta\) is deployed directly at test time to dynamically score and rank candidate demonstration subsets per test query with negligible latency.
%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
A["Input Candidate Pool Q, Validation Set V, and Initial Sets (U0, C0)"] --> B["Border Arm Detection & Confidence Swap<br/>Identify weakest in Ut and strongest in Ct and swap"]
B --> C["Ambiguity Frontier & Gap-Index Evaluation<br/>Compute pairwise gap bound using MC-Dropout variance and SGD stability"]
C --> D["Greedy Feedback Acquisition & Dataset Expansion<br/>Evaluate downstream LLM on borderline arm and append to D"]
D --> E["Non-linear Differentiable Sorting Inner Loop<br/>Perform one-epoch SGD on relaxed NDCG loss to optimize F_theta"]
E -->|Gap Bt(cht, bt) > epsilon| B
E -->|Gap converges to <= epsilon| F["Frozen Lightweight Surrogate F_theta<br/>Deploy for instant per-query instance-level subset ranking"]
Key Designs¶
1. Border Arm Detection & Confidence Swap: Adaptive Tracking of the Near-Optimal Frontier
To avoid uniform sampling over the exponentially large subset space, DEARICL actively maintains an estimated top-\(m\) shortlist \(\mathcal{U}_{t-1}\) and a challenger shortlist \(\mathcal{C}_{t-1}\) (\(m' < m\)). At iteration \(t\), the algorithm computes the empirical mean \(\hat{\rho}_t(a)\) of each candidate arm \(a\) across validation queries \(v_{\text{val}}^{(i)} \in \mathcal{V}\): $\(\hat{\rho}_t(a) = \frac{1}{n'} \sum_{i=1}^{n'} F_\theta\left(x_a(v_{\text{val}}^{(i)})\right)\)$ where \(x_a(v_{\text{val}}^{(i)})\) is the concatenated vector of the validation query embedding and the average sentence embedding of the \(k\) demonstrations in subset \(a\). The algorithm identifies the weakest arm in the current top-\(m\) pool \(m_t = \arg\min_{a \in \mathcal{U}_{t-1}} \hat{\rho}_t(a)\) and the strongest challenger \(c_t = \arg\max_{a \in \mathcal{C}_{t-1}} \hat{\rho}_t(a)\). If \(\hat{\rho}_t(c_t) \ge \hat{\rho}_t(m_t)\), the two arms are swapped. The challenger pool is then expanded by drawing \(m'\) random arms from the unvisited candidate complement \((\mathcal{U}_t \cup \mathcal{C}_{t-1})^c\) and taking the top-\(m'\) candidates based on updated empirical means, dynamically preventing exploration from stagnating in local optima.
2. Ambiguity Frontier & Gap-Index Evaluation: Multi-Source Error Decomposition for Non-linear Surrogates
In standard linear bandits, confidence bounds rely on regularized least-squares ellipsoids; however, deep neural networks lack such analytical forms. To provide rigorous theoretical guarantees, the paper derives a high-probability (\(1-\delta\)) pairwise gap-index bound \(B_t(i, j) = \hat{\rho}_t(i) - \hat{\rho}_t(j) + W_t(i, j)\) for non-linear networks. The error between the empirical gap and the true performance gap is formally bounded by decomposing it into three distinct components: Monte Carlo Dropout variance (capturing epistemic uncertainty over \(N\) stochastic forward passes), single-epoch SGD algorithmic stability drift \(\epsilon_{\text{stab}}^{(t)}\) (via Hardt et al.'s uniform stability bounds), and network approximation biases \(b_i, b_j\): $\(W_t(i, j) = c_t \left(\sqrt{\frac{2 \hat{V}_{ij, t} \log(2K^2/\delta)}{N}} + \frac{4M \log(2K^2/\delta)}{3N}\right) + \epsilon_{\text{stab}}^{(t)} + b_i + b_j\)$ where \(\hat{V}_{ij, t}\) is the empirical variance of MC-Dropout difference predictions across \(N\) passes and \(c_t\) is an annealed multiplier. Leveraging this bound, the algorithm calculates the most ambiguous arm pair along the decision boundary: \(b_{t+1} = \arg\max_{b \in \mathcal{U}_t} \max_{ch \in \mathcal{C}_t} B_t(ch, b)\) and \(ch_{t+1} = \arg\max_{ch \in \mathcal{C}_t} B_t(ch, b_{t+1})\), focusing exploration strictly on arms where misclassification risk is highest.
3. Greedy Feedback Acquisition & Non-linear Differentiable Sorting: Stability-Controlled LTR Optimization
Once the critical pair \((b_{t+1}, ch_{t+1})\) is identified, the algorithm executes a greedy selection rule that selects the arm minimizing prediction variance between \(b_{t+1}\) and \(ch_{t+1}\). Only this selected arm \(a_{t+1}\) is queried against the downstream LLM (e.g., Llama-3.2-3B) across validation instances. The evaluation generates reward vector \(\vec{r}_{t+1}(a_{t+1}) = \mathcal{R}(\psi(a_{t+1}), \mathcal{V})\), where rewards are measured via BERTScore against ground truth rationales and answers. The resulting pair \((a_{t+1}, \vec{r}_{t+1})\) is appended to dataset \(\mathcal{D}\). In the inner loop, surrogate \(F_\theta\) is retrained for one epoch on \(\mathcal{D}\) using a relaxed differentiable ranking objective based on a temperature-softened permutation matrix \(P_\tau(\hat{\vec{\rho}})\): $\(\mathcal{L}(\hat{\vec{\rho}}, \vec{r}) = - \widehat{\text{NDCG}}_\tau(\hat{\vec{\rho}}, \vec{r}) = - \frac{1}{Z(\vec{r})} \sum_{i, j} P_\tau(i, j; \hat{\vec{\rho}}) \, r_j \, D(i)\)$ Lemma I.1 proves that this relaxed loss is \(L\)-Lipschitz with \(L = \mathcal{O}(1/\tau)\), establishing the requisite uniform stability for one-epoch SGD updates. Consequently, the surrogate stably refines its ranking landscape without suffering catastrophic forgetting or variance collapse from adaptively sampled borderline points.
Loss & Training¶
The inner surrogate network is configured as a compact multi-layer feed-forward network with ReLU activations (e.g., layers \((256, 256, 128, 64)\) for PiRank-based configurations). Training runs with Adam optimizer at learning rate \(1\times 10^{-4}\) and batch size 16. In the outer bandit loop, parameters are set to error tolerance \(\delta = 0.05\), stopping threshold \(\epsilon = 0.1\), target top-\(m = 10\), and challenger size \(m' = 5\). Demonstration candidate prompts are initialized by sampling one exemplar from each of 5 semantic clusters pre-computed via \(k\)-means on the training pool, forming 5-shot prompt combinations (\(k=5\)).
Key Experimental Results¶
Main Results¶
Evaluations were conducted on mathematical reasoning benchmarks GSM8K and AquaRAT using Exact Match (EM, %), and on machine translation benchmark WMT19 (English-Chinese) using BERTScore, with Llama-3.2-3B as the primary downstream language model. DEARICL was evaluated in both static configuration (DEARICLstatic, using the converged top-\(m\) arm) and dynamic configuration (DEARICLdynamic, using the trained surrogate for per-query ranking).
| Dataset | Metric | Dynamic SOTA (CASEdynamic) | Static Surrogate (DEARICLstatic) | Full Dynamic Model (DEARICLdynamic) | Gain over CASEdynamic |
|---|---|---|---|---|---|
| GSM8K | EM (%) | 70.00 | 69.90 | 75.66 | ▲8.08% (p < 0.05) |
| AquaRAT | EM (%) | 47.51 | 50.00 | 55.11 | ▲15.99% (p < 0.05) |
| WMT19 (en-zh) | BERTScore | 71.70 | 68.83 | 78.89 | ▲10.03% (p < 0.05) |
Compared to traditional learning-to-rank baselines on GSM8K and AquaRAT, DEARICLdynamic substantially outperforms NeuralNDCG (72.23% and 44.09%), PiRank (69.30% and 37.00%), and ListNet (70.30% and 43.30%). Furthermore, it surpasses standard similarity/diversity retrieval baselines such as KNN (61.07% and 41.31%) and MMR (66.48% and 45.84%) by significant margins.
Ablation Study¶
Ablation experiments were performed to examine the contribution of the gap-index active exploration mechanism and to test alternative LTR objectives trained on data collected by DEARICL.
| Configuration / Variant | GSM8K (EM) | AquaRAT (EM) | WMT19 (BERTScore) | Core Note & Finding |
|---|---|---|---|---|
| DEARICLdynamic (Full Model) | 75.66 | 55.11 | 78.89 | Full gap-index MAB + relaxed NDCG surrogate |
| w/o Gap Exploration (Random Sampling) | 69.06 | 49.21 | 70.38 | Replacing gap-index with random exploration drops EM by 5.9–6.6% |
| w/o Exploration (Static Surrogate) | 70.30 | 37.00 | 71.30 | Removing adaptive sampling causes severe 18.11% drop on difficult AquaRAT |
| NDCGLoss 2++ (Trained on DEARICL data) | 72.11 | 49.00 | 74.06 | Offline LTR benefits from DEARICL data but lacks active outer loop adaptation |
| NeuralNDCG (Trained on DEARICL data) | 69.83 | 48.30 | 72.75 | Passive LTR objectives remain 5.8–6.8% below online closed-loop DEARICL |
Sample Complexity & Runtime Efficiency¶
The authors evaluated offline sample complexity by recording the total number of LLM evaluation calls required to achieve convergence, as well as the average online test latency per query (in seconds).
| Method | GSM8K Total LLM Calls | AquaRAT Total LLM Calls | WMT19 Total LLM Calls | GSM8K Latency / Query (s) | AquaRAT Latency / Query (s) | WMT19 Latency / Query (s) |
|---|---|---|---|---|---|---|
| CASEdynamic (Online Bandit) | 10200 | 4360 | 87 | 1554.19 | 2378.04 | 106.54 |
| NeuralNDCG (Neural Ranker) | - | - | - | 10.59 | 18.51 | 5.20 |
| PiRank (Lightweight LTR) | - | - | - | 6.10 | 11.59 | 1.80 |
| DEARICLdynamic (Ours) | 2600 | 1580 | 48 | 6.04 | 11.59 | 1.68 |
Key Findings¶
- Sample Complexity Reduction of 63%–75%: DEARICL converges in significantly fewer rounds than CASE (e.g., 79 rounds vs. 238 rounds on AquaRAT, and 130 vs. 510 rounds on GSM8K). Linear bandit baselines suffer from plateauing gap indices around round 70 due to linear separability failure on complex subsets, whereas DEARICL reduces LLM evaluation calls from 10,200 to 2,600 on GSM8K.
- Negligible Inference Overhead: Running dynamic multi-armed bandits at test time (CASEdynamic) is practically intractable, incurring 1,554–2,378 seconds per query. In contrast, DEARICLdynamic evaluates candidate scores via a lightweight MLP forward pass, executing in 1.68–11.59 seconds per query—matching the latency of purely static exemplar selection.
- Robust Transferability to Frontier LLMs: Exemplar subsets and surrogate selections obtained with Llama-3.2-3B transfer effectively to stronger models without retraining. On AquaRAT, DEARICLdynamic achieves 81.88% on GPT-4o-mini (vs. 76.77% for CASEdynamic) and 74.41% on DeepSeek-R1-Distill-Qwen-7B (vs. 69.68% for CASEdynamic), both statistically significant at \(p < 0.05\).
Highlights & Insights¶
- Repurposing Top-\(m\) Identification as an Active Learning Engine: Rather than treating multi-armed bandit arm identification merely as a static end-state decision, DEARICL recognizes that gap-index bounds provide the optimal criterion for negative hard-mining, actively funneling ambiguous borderline subsets to train a ranking surrogate where data is most needed.
- Theoretical Cohesion via Algorithmic Stability and MC-Dropout: The framework establishes a rigorous theoretical foundation that bridges stochastic bandits with deep ranking models, utilizing uniform stability of one-epoch SGD and empirical Bernstein bounds over Monte Carlo Dropout differences to provide PAC sample complexity guarantees.
- Decoupled Architecture for Real-World Scalability: Heavy combinatorial search and LLM evaluation costs are confined strictly to an offline, sample-efficient exploration phase, leaving a simple, fast neural scoring model for runtime deployment that delivers instance-level customization at static-selection inference speeds.
Limitations & Future Work¶
- Dependence on Ground-Truth Target Labels for Reward Computation: The acquisition loop currently relies on supervised pairs to calculate BERTScore rewards against ground truth rationales and answers. Extending this methodology to unsupervised or open-ended generation tasks requires developing self-supervised reward proxies.
- Search Space Constraints via Semantic Clustering: In order to constrain the discrete combination space, candidate subsets are generated by sampling from \(k\)-means clusters. This heuristic may potentially exclude high-performing exemplar combinations that reside within the same cluster.
- Absence of Theoretical Regret Bounds: While the paper establishes rigorous PAC sample complexity upper bounds, deriving formal cumulative or simple regret bounds for gap-index frameworks with non-linear neural surrogates remains an open theoretical challenge left for future research.
Related Work & Insights¶
- vs. CASE / EXPLORA (Purohit et al., 2024, 2025): While CASE relies on a linear surrogate within a static top-\(m\) bandit setup, it fails to capture non-linear subset interactions and cannot adapt dynamically per query; DEARICL uses non-linear differentiable sorting and deploys the surrogate for instant per-query ranking, yielding up to 15.99% accuracy gains while cutting LLM calls by over 60%.
- vs. KNN / MMR (Rubin et al., 2022; Ye et al., 2023b): Unsupervised retrieval baselines score exemplars independently based on embedding similarity or diversity heuristics, ignoring inter-demonstration synergy and downstream performance feedback; DEARICL treats demonstration subsets holistically, learning joint combination utility directly from LLM rewards.
- vs. Classical Learning to Rank (NeuralNDCG / PiRank): Standard LTR methods lack a principled exploration mechanism to sample ambiguous demonstration combinations, relying instead on static or random negative sampling; DEARICL leverages the bandit gap index as an active sampling objective, ensuring the surrogate receives targeted supervision along the decision boundary.
Rating¶
- Novelty: ⭐⭐⭐⭐⭐ [Pioneering integration of gap-index stochastic bandits with differentiable learning-to-rank for sample-efficient in-context demonstration selection]
- Experimental Thoroughness: ⭐⭐⭐⭐⭐ [Extensive comparisons across mathematical reasoning and translation, encompassing open-source, reasoning-distilled, and closed-source LLMs alongside runtime and sample complexity audits]
- Writing Quality: ⭐⭐⭐⭐⭐ [Exemplary mathematical exposition, rigorous theoretical proofs in appendix, and transparent empirical presentation]
- Value: ⭐⭐⭐⭐⭐ [Directly resolves the speed-generalization trade-off in prompt demonstration selection, offering a practical blueprint for high-performance ICL pipelines]