Choosing which worked examples to put in a language model's prompt ("in-context demonstrations") is a search over subsets of a large pool. Every candidate subset costs real model calls to score, because its quality is only visible by running the model on a validation batch. Current sample-efficient methods treat each candidate as an arm in a bandit with a linear reward. That assumption lets them share information across subsets, but it ignores the strong interactions between examples that other work documents. We propose a different search primitive, taken from property testing of Boolean functions. It rests on the view that the value of a prompt is a function on the corners of a hypercube: each corner is one subset of the pool. The procedure has three steps. First, take a random walk of many swaps away from the current subset. Second, if the far end of the walk scores clearly differently from the start, binary-search along the walk to find the single swap responsible. Third, keep that swap if it helps, and mark the swapped items as harmful or helpful if it hurts.
This matters because of how the cost scales. One walk tests ℓ swaps at once, and finding the responsible swap costs only about $\log \ell$ further evaluations. If only a few items in the pool actually move accuracy, the number of model calls should then grow with the number of items that matter, not with the pool size. The same argument lets adaptive monotonicity testers run in time proportional to a function's total influence rather than its dimension. Whether prompt utility really has this "few items matter" structure has never been measured. Our method gives a direct way to measure it.
Core Claim
Our claim has three parts, and each can be checked. The first part is a measurement. For demonstration selection on reasoning benchmarks, the utility over fixed-size subsets has low total influence. Here a swap's influence is the expected accuracy change when one exemplar is exchanged for another, and total influence is the sum of those effects summed over positions. Most of that influence is carried by a small set of items.
The second part is a method claim. Under that structure, walk-plus-binary-search finds improving swaps with far fewer model calls than two alternatives: single-swap local search, and linear-bandit shortlist exploration.
The third part is an explanation. The size of the advantage should track the measured concentration of influence. Where influence is spread evenly across the pool, the method should lose its edge, and we will report where that happens.
The method comes from Adaptive Boolean Monotonicity Testing in Total Influence Time. That paper takes random walks on the hypercube and, when the endpoints disagree, binary-searches the walk to find an influential edge in $O(\log \ell)$ queries. This yields $O(I(f)\cdot\mathrm{poly}(\epsilon^{-1}\log n))$ testers that beat every non-adaptive tester when influence is small. We carry the mechanism over with three changes. The target is optimization rather than testing. The function is real-valued and noisy rather than Boolean and exact. The domain is the "slice" of $k$-subsets, where one step is a swap, rather than the full cube.
Research Program
The search primitive. Let $u(S)$ be the validation accuracy of the model prompted with subset $S$ of size $k$, drawn from a pool of $N$ candidates. Each evaluation of $u$ on a fresh mini-batch is a noisy observation. From the current incumbent $S_0$, we sample a walk $S_0, S_1, \dots, S_\ell$ of random swaps. If a confidence test says $|u(S_\ell)-u(S_0)|$ exceeds a threshold, we bisect. We evaluate the midpoint of the walk and recurse into the half whose endpoint gap is larger. This ends at a single swap $(a \to b)$ together with an estimated effect.
The noisy comparisons use Kullback–Leibler (KL) confidence intervals on Bernoulli accuracies, following Information Complexity in Bandit Subset Selection. That paper showed KL intervals, whose rate is set by Chernoff information, need substantially fewer samples than Hoeffding intervals, especially when means sit near 0 or 1. Near-extreme accuracies are exactly the regime of strong models on GSM8K.
Found swaps feed a simple bookkeeping step. Items whose insertion repeatedly hurts are dropped from the pool. Items whose removal repeatedly hurts are pinned. This adaptive shrinking of the pool plays the role that domain reduction plays in Domain Reduction for Monotonicity Testing: A $o(d)$ Tester for Boolean Functions on Hypergrids. Unlike the fixed semantic clusters of Mixture of Demonstrations for In-Context Learning, it is driven by observed effects.
Analysis. A caveat comes first. For a real-valued function, bisection that always follows the larger gap only guarantees a final swap with effect at least $\Delta/\ell$, where $\Delta$ is the endpoint gap. A strong guarantee therefore needs concentration. We will prove a bound of the form
$$\mathbb{E}[\text{calls per accepted improvement}] = O\!\left(\frac{\log \ell}{p_\ell}\cdot \frac{\log(1/\delta)}{d^*(\Delta)}\right),$$
where $p_\ell$ is the probability that a length-$\ell$ walk contains a swap with effect at least $\Delta$, and $d^*(\Delta)$ is the Chernoff information separating accuracies that differ by $\Delta$. The $d^*$ term comes from the KL comparison rate.
We will then show that $p_\ell$ grows roughly like $\ell$ times the single-swap probability, as long as effects do not cancel along the walk. This is the analogue of the "sticky vertex" argument in the monotonicity paper. Together these give an $\ell/\log \ell$ saving over random single-swap search.
Interactions between examples can break the no-cancellation condition, and the bound will say so explicitly. Our empirical cancellation rate is the quantity that tells us whether the theory applies. We do not claim matching lower bounds. Bandits, Query Learning, and the Haystack Dimension already shows that exact black-box maximization is governed by a worst-case elimination measure. Our contribution is structure-dependent upper bounds and their empirical test.
Measuring influence. As a first-class output, we estimate the distribution of per-item and per-swap influence on each benchmark from the walks themselves. Every bisection yields an effect estimate at no extra cost. We report what fraction of total influence the top 1%, 5%, and 20% of items carry. Finding Support Examples for In-Context Learning found large swings from example choice and ordering, which motivates the hypothesis. It does not tell us whether those swings are concentrated in a few items or diffuse.
Baselines
Random subsets. The naive reference is evaluating uniformly random $k$-subsets and keeping the best, given the same budget of model calls. Li and Qiu report that random selection averages 44.2% accuracy against 69.8% for their LENS method across eight classification datasets (Finding Support Examples for In-Context Learning). We run random selection on our benchmarks to anchor the scale.
CASE, the strongest existing method. CASE (Sample Efficient Demonstration Selection for In-Context Learning) casts selection as top-$m$ identification in a linear bandit over sentence embeddings. It keeps a shortlist of challenger arms and chooses which to query with a gap index. It reports 7x fewer LLM calls (an 87% reduction) and up to a 7x runtime speedup compared with LENS and EXPLORA on GSM8K. It also reports accuracy gains of up to 15.19% relative to LENS across GSM8K, AquaRat, TabMWP, FinQA, and StrategyQA with GPT-3.5-turbo.
CASE is the strongest competitor because it targets the same currency we do, model calls. It also already shares statistical strength across subsets. We run the released code (kiranpurohit/CASE) with the same pool, model, validation split, and total call budget as our method. Each method's hyperparameters get the same number of tuning runs. To beat CASE, we must reach equal or better held-out test accuracy with a smaller call budget, or higher accuracy at matched budget, across seeds on at least three of the five datasets.
Single-swap local search. This baseline evaluates random single swaps and accepts improvements under the same KL test. It is our method with $\ell=1$, so it isolates the contribution of long walks plus bisection.
Non-adaptive walks. This baseline evaluates the walk endpoints and a fixed set of evenly spaced intermediate subsets, then keeps the best one without bisecting. It separates the benefit of adaptivity from the benefit of simply moving further per step. It mirrors the adaptive-versus-non-adaptive gap studied in An o(n) Monotonicity Tester for Boolean Functions over the Hypercube.
Hoeffding comparisons. A final ablation replaces the KL tests with Hoeffding tests, isolating the Chernoff-information component.
Why not just…?
Why not just use CASE's linear bandit, which already cuts calls sevenfold? CASE's savings come from assuming reward is linear in embedding features. When one exemplar's value depends on which others are present, that model assigns a single fixed score to an item and can steer the shortlist wrong. Our method assumes no functional form, only that few swaps carry most of the effect. This alternative is a genuine threat. If prompt utility turns out close to additive, CASE may match us at lower overhead. The influence and cancellation measurements will tell us which regime each dataset is in. We will also report whether CASE's residual error on held-out subsets predicts where we win.
Why not just do greedy or single-swap hill climbing? That is exactly the $\ell=1$ ablation. If improving swaps are rare, a single-swap search spends most of its calls confirming that nothing changed. A walk of length ℓ checks roughly ℓ swaps per endpoint comparison. If the $\ell=1$ variant matches ours at equal budget, the core idea fails, and we will say so.
Why not just pick the nearest neighbours of the query by embedding similarity? Similarity retrieval costs no model calls, but others report it is beaten by search-based selection. Qin et al. report about 4% lower accuracy on math reasoning than their iterative method (In-Context Learning with Iterative Demonstration Selection). Wang et al. find redundancy in similar top-$k$ sets (Mixture of Demonstrations for In-Context Learning). We include it as a zero-budget point and also as a starting incumbent $S_0$ for our search. That tests whether walks improve on a sensible start rather than only on a random one.
Why not just use group testing or delta-debugging-style bisection over item sets? These are close relatives and we acknowledge the lineage. They bisect over a known set of suspects under a monotone failure condition. We instead sample the chain randomly, work on the fixed-size slice with noisy real-valued outcomes, and tie cost to measured influence. We will implement a set-bisection variant that halves the set of items differing between $S_0$ and a random far subset. We report it as an additional baseline.
Proposed Experiments
The main benchmarks are the five CASE datasets: GSM8K, AquaRat, TabMWP, FinQA, and StrategyQA. We use the CASE pools and splits, with an open-weight instruction model for reproducibility, and GPT-3.5-class results where access allows. For classification, we also run the eight-dataset LENS setting so we can compare against the reported 69.8% and 44.2% points. The primary metric is held-out test accuracy as a function of cumulative model calls, reported as full budget curves over five seeds, not single endpoints.
The decisive checks are three. First, at matched call budgets, the method must beat the $\ell=1$ ablation and the non-adaptive-walk ablation. If it does not, bisection adds nothing. Second, across datasets and pool sizes (we subsample pools of 100, 500, and 2000), the calls needed to reach a fixed accuracy should grow with the measured number of high-influence items rather than with $N$. We test this by regressing cost on both quantities. Third, the win over CASE should increase with measured non-additivity. We quantify non-additivity as the cancellation rate along walks and as CASE's held-out residual.
If influence turns out diffuse on some datasets, we report that as a negative finding about prompt utility. It would be a useful measurement in its own right, since neither line of work has one.
References
- Adaptive Boolean Monotonicity Testing in Total Influence Time
- Information Complexity in Bandit Subset Selection
- Domain Reduction for Monotonicity Testing: A $o(d)$ Tester for Boolean Functions on Hypergrids
- Mixture of Demonstrations for In-Context Learning
- Bandits, Query Learning, and the Haystack Dimension
- Finding Support Examples for In-Context Learning
- Sample Efficient Demonstration Selection for In-Context Learning
- An o(n) Monotonicity Tester for Boolean Functions over the Hypercube
- In-Context Learning with Iterative Demonstration Selection