When a large language model is shown a few worked examples before a question, a method called in-context learning, the choice of examples matters a great deal. On text classification, randomly drawn examples averaged 44.2% accuracy, while carefully chosen ones reached 69.8% (Finding Support Examples for In-Context Learning). Because there are astronomically many possible example sets, recent methods borrow guarantees from combinatorial optimization. The most common borrowed idea is submodularity, a "diminishing returns" property: each added example helps less when the set already holds more examples. When a utility has this property, the simple greedy procedure of adding the best example one at a time is provably within a factor $(1-1/e)$ of the best possible set. These guarantees are cited as justification, but nobody has measured whether the true utility, meaning the accuracy of a real LLM given a set of examples, actually has diminishing returns. That gap matters most on multi-step reasoning, where one worked example may be useless unless a complementary one is also present.
This proposal makes that measurement. On small but exhaustively enumerable candidate pools for real reasoning benchmarks and real open models, we estimate the submodularity ratio, a number between 0 and 1 that says how far a utility departs from diminishing returns. We use it to test whether the published approximation bounds predict how far greedy selection actually falls short of the best set. We then test one targeted fix: when the measurement shows that examples help each other more together than apart, we let greedy add pairs of examples instead of single ones. The main contribution is empirical, a calibrated account of when the theory used in this area holds. The method is a falsifiable consequence of that account rather than the headline.
Core Claim
We claim that the utility of an in-context example set has a submodularity ratio that varies systematically across tasks. It should be near 1 for single-step tasks such as sentiment classification. On multi-hop and multi-step reasoning tasks such as StrategyQA and GSM8K, it should be low enough that the weak-submodularity bound becomes vacuous. Where the ratio is low, the realized gap between greedy and the exhaustive best set should be large. Where it is high, greedy should be essentially optimal, and the extra machinery of surrogate-based searches buys little beyond cost reduction.
To make the quantity concrete, let $F(S)$ be validation accuracy of a fixed model prompted with example set $S$, averaged over random orderings of $S$ so that $F$ is a genuine set function. The submodularity ratio of Scalable Greedy Feature Selection via Weak Submodularity is
$$ \gamma = \min_{L,\,S:\ |L|\le k,\ |S|\le k,\ L\cap S=\emptyset} \frac{\sum_{e\in S}\big(F(L\cup\{e\})-F(L)\big)}{F(L\cup S)-F(L)}, $$
which equals 1 or more under diminishing returns and approaches 0 when items are only useful jointly. That paper proves that greedy achieves at least $(1-e^{-\gamma})$ of the optimum. We will compute empirical lower and upper estimates of $\gamma$ and check this inequality directly against exhaustive optima.
Positioning Against Prior Work
Three groups of prior work shape this proposal, and they play different roles.
The first group motivates it. SMILE learns a deep submodular surrogate built from diversity, relevance, and instruction-alignment networks, and runs greedy selection on it. It reports an average of 63.0 against 59.8 for the strongest joint baseline on Qwen3-4B. SMILE's own limitations section concedes that the guarantee fails on super-additive multi-step reasoning, the case where examples help more together than apart. Its submodularity is imposed by the surrogate's architecture, so the surrogate cannot reveal whether the LLM's real utility has the property. We measure the real utility instead. LENS supplies the contrary evidence: specific pairs of examples cause large, non-monotonic accuracy swings. We turn this anecdote into a measured quantity.
The second group supplies the method. The $\gamma$ machinery and the stochastic and distributed greedy analyses come from Khanna et al. They validated it on regression and logistic regression, with ElectricityLoadDiagrams and Gisette, where $F$ is $R^2$ or log-likelihood. We carry the same diagnostic over to a black-box, non-convex utility that their analysis never touched.
The third group constrains us and sets the strongest bar. EXPLORA and CASE treat example-set selection as a bandit problem that identifies the best subsets, using a linear reward model over BERT embeddings. CASE reports up to 15.19% gains over LENS with 7x fewer LLM calls than EXPLORA. A linear reward over aggregate similarity features is additive by construction, so it cannot represent complementarity. If our measurements show strong super-additivity, that predicts where CASE should fail. If they do not, CASE's linear assumption is vindicated, which is equally worth knowing.
The broader concern that proofs built on idealized assumptions mislead practice is documented elsewhere. Examples include the Nibble local clustering algorithm, whose provably safe parameters underperform heuristics (A Local Clustering Algorithm for Massive Graphs), and Multinomial Logit Contextual Bandits, whose theoretical exploration schedules were impractically slow. We apply that critique to subset selection for prompts.
Research Program
The core is an exhaustive measurement study. For each task we fix a candidate pool of $N=20$ training examples, chosen once at random, and a validation set of 100 questions. We evaluate every subset of size up to 3 and a large random sample of size-4 and size-5 subsets. Each subset is scored under several random orderings. For $N=20$ there are 1,350 subsets of size at most 3, so this costs on the order of a few hundred thousand forward passes per task on a 4B–7B model, which is feasible.
From this table we compute four things. The first is the exact optimum for $k\le3$. The second is greedy's realized ratio to that optimum. The third is bracketing estimates of $\gamma$: a lower bound from the worst observed $(L,S)$ pairs with $|L|,|S|\le 2$, and an extrapolated estimate from sampled chains at $k=4,5$. The fourth is a pairwise interaction score, $F(\{a,b\})-F(\{a\})-F(\{b\})+F(\emptyset)$, for every pair. Its distribution shows directly whether complementarity is rare or widespread.
Ordering is a confound, since it is known to swing accuracy, and we keep it separate rather than ignore it. Because $F$ averages over orderings, we also record the spread of accuracy across orderings of the same subset. This lets us state how much of the apparent "interaction" between examples is really order sensitivity. Reporting that split is itself a validation result that no prior paper in the file provides.
The second component is a diagnostic-triggered variant of greedy, which we call pair-greedy. At each step it considers adding either the best single example or the best pair. It estimates which pairs are worth considering from pairwise interaction scores computed on a small probe subsample of the pool. Pair-greedy is meant to be used only when the estimated $\gamma$ falls below a threshold. Using the same probe evaluations, we also derive a cheap estimate of $\gamma$ that does not need the exhaustive table, and we test whether this cheap estimate tracks the exhaustive one. The program then checks a scaled-up setting with $N=100$ and $k$ up to 8, where enumeration is impossible. There, the cheap diagnostic must decide on its own whether pair-greedy is worth its cost.
Baselines
The naive reference points are random sampling of $k$ examples and nearest-neighbour retrieval by Sentence-BERT similarity. Random sampling is the "do nothing" option. On classification it averaged 44.2% against 69.8% for LENS (Finding Support Examples for In-Context Learning). Nearest-neighbour retrieval is what practitioners actually deploy. Both draw from the same 20- or 100-example pool and use the same orderings, so the comparison isolates selection.
Plain greedy on the true LLM utility is the most important comparison. It uses exactly the same evaluation table as pair-greedy, so it is the ablation that isolates the one ingredient we add, joint consideration of pairs. Pair-greedy beats it only if it closes a statistically significant part of the gap to the exhaustive optimum on tasks with low $\gamma$, measured by bootstrap over validation questions. Pair-greedy must also do no worse on tasks with high $\gamma$. Compute is matched by giving plain greedy the same number of LLM evaluations, which it can spend on stochastic restarts.
The strongest existing method is CASE, run from its released code (github.com/kiranpurohit/CASE), with EXPLORA as its predecessor. Its strength is a reported improvement of up to 15.19% over LENS and 7x fewer LLM calls than EXPLORA (CASE). EXPLORA reports a 12.24% improvement over LENS on GSM8K (EXPLORA). The file gives no absolute per-dataset accuracies for AquaRat, TabMWP, FinQA, or StrategyQA; no reported result found on Lacuna for those breakdowns. We will rerun CASE ourselves on identical pools, models, and LLM-call budgets rather than compare against reported numbers. SMILE is included where its code can be reproduced. Its reported 63.0 average on Qwen3-4B covers a different six-dataset suite, so we treat that figure only as context. Beating CASE means higher accuracy at equal LLM-call budget, on the tasks the diagnostic flags as super-additive. We do not claim to beat it everywhere.
Why not just…?
Why not just run greedy and ignore the theory, since it works in practice? This is the most serious alternative, and it may be correct. If greedy reaches within one or two points of the exhaustive optimum on every task, including those with low $\gamma$, the method component fails. The paper then reports a different finding: the weak-submodularity bound is loose by a measured margin for LLM utilities, and greedy needs no additional justification. The plain-greedy ablation settles this directly, and we commit to reporting either outcome.
Why not just use CASE or EXPLORA, which already cut LLM calls sharply? Their linear reward model over embedding similarities adds up per-example contributions, so it cannot represent a pair that helps only jointly. Our pairwise interaction scores show how much accuracy lies in such pairs on each task. CASE's shortfall against the exhaustive optimum on those tasks, relative to its shortfall on additive tasks, is the test. If CASE matches the optimum on StrategyQA anyway, then complementarity is rare or captured by similarity, and we say so.
Why not just brute-force small subsets? For $k\le3$ on a 20-example pool, we do exactly that, because it is our ground truth. It does not scale: CASE notes that choosing 5 of 100 already gives over 75 million subsets. The question that matters at scale is whether a cheap diagnostic can tell when greedy is enough, and the $N=100$ experiment tests that.
Why not just learn a non-submodular surrogate? A learned surrogate inherits whatever inductive bias it is given, and SMILE shows that the bias then determines which guarantees hold. Measuring the true utility first tells any future surrogate designer which interactions it must represent. That measurement is what this work provides.
Proposed Experiments
The tasks are GSM8K, AquaRat, TabMWP, FinQA, and StrategyQA, the CASE and EXPLORA suite, plus Date from SMILE's suite. We add two classification controls from the LENS suite, including MR, where we expect $\gamma$ to be near 1. The models are Mistral-7B, used by EXPLORA, and Qwen3-4B, used by SMILE. This gives us two model families and lets us check whether $\gamma$ is a property of the task or of the model. We also add a planted positive control: a synthetic two-hop task in which each answer requires facts carried by two specific examples. There $\gamma$ should be near 0 and pair-greedy should clearly win. If it does not, our estimation pipeline is broken.
Four checks decide the outcome. The first tests whether the bound holds: on every task, greedy's realized ratio to the exhaustive optimum should be at least $1-e^{-\hat\gamma}$, and we report how loose the bound is. The second tests whether $\hat\gamma$ ranks tasks consistently with the greedy shortfall, using rank correlation across the 8 tasks and 2 models. The third tests whether order sensitivity accounts for more or less of the variance than set interactions. The fourth tests whether, at $N=100$, the cheap diagnostic correctly predicts the tasks where pair-greedy beats plain greedy and CASE at equal LLM-call budget. Metrics are exact-match accuracy, number of LLM calls, and wall-clock time, the last because the Multinomial Logit Contextual Bandits results show that theoretical efficiency and runtime can diverge by an order of magnitude. If check two fails, the central claim fails: the submodularity ratio is not a useful guide in this domain, and that negative result would be published as such.
References
- Finding Support Examples for In-Context Learning
- Scalable Greedy Feature Selection via Weak Submodularity
- SMILE: Extended Deep Submodular Function-Based Instruction and In-context Learning Demonstration Selection
- EXPLORA: Efficient Exemplar Subset Selection for Complex Reasoning
- Sample Efficient Demonstration Selection for In-Context Learning
- A Local Clustering Algorithm for Massive Graphs and Its Application to Nearly Linear Time Graph Partitioning
- Multinomial Logit Contextual Bandits: Provable Optimality and Practicality