The Price of Choosing Examples: Context Overfitting in Adaptive In-Context Learning
Organizations: University of New South Wales · The University of Hong Kong
Abstract
In-context learning is usually analyzed as if the examples in the prompt were sampled before the learner is chosen. In deployed systems they are not: examples are retrieved, filtered, re-ranked, edited, and repeatedly tested after seeing the query and the data store. We formalize this gap by treating prompt construction as adaptive data analysis through a conditional stochastic-kernel calculus. Our main quantity is the context capacity, the mutual information or approximate max-information between the data store and the final prompt transcript. For any frozen in-context learner and any adaptive context pipeline with capacity , we prove a finite-sample context generalization bound of order , where is the number of selected examples whose losses form the reported score. We prove a matching lower bound, whose constant is exact when , and derive two PAC-Bayesian retrieval rules: a first-order Gibbs rule that charges data-dependent candidate gates their prior mass, and a self-normalized second-order rule. On Banking77 with 64 retrieval recipes and two model families, the certificates hold in all 24,000 resampled selection events, and from 64 (Qwen2.5-7B) or 128 (GPT-4.1-mini) reused validation queries the Gibbs rule certifies a risk below the zero-shot error in over 99% of validation draws. Finally, we instantiate the theory for Bayesian linear in-context regression, including an order-statistics analysis of query-aligned top- Gaussian retrieval. The results separate context quality from context certification: longer or more relevant contexts improve risk only when the procedure used to choose them is stable enough for selected-context evidence to transfer.
Figures & tables
| Analysis lens | Random object | Complexity term | What is missing |
|---|---|---|---|
| Uniform convergence [ 40 , 39 ] | fixed hypothesis class | or VC dimension | no query-dependent prompt transcript |
| PAC-Bayes [ 32 , 10 ] | posterior over hypotheses | no explicit selected-context sample size | |
| Adaptive data analysis [ 14 , 36 ] | adaptive statistical queries | information per query | no prompt examples or frozen ICL map |
| Fixed-retrieval ICL theory [ 19 , 20 ] | retrieved context distribution | retrieval noise / task mismatch | no reuse of validation data to choose retrieval |
| This paper | prompt-construction kernel | or profiled KL | separates context quality from context certification |
| Prompt-construction step | Capacity charge | Required log |
|---|---|---|
| Choose one of prompt templates | ; for Theorem 4.2 (Lemma D.7 ) | template id and candidate set size |
| Try context recipes, keep best validation score | ( for Theorem 4.2 ) plus score-release cost | recipe ids and validation reuse count |
| Gibbs/SCAR sampling from prior | , including candidate-gate mass; bounds only | posterior weights, sampling temperature, and |
| Gaussian-noisy score vector | by Proposition D.24 ; bounds only | noise precision and an almost-sure bound on |
| interactive prompt edits | by Proposition 4.5 | per-round transcript and candidate pool |
| Fresh held-out evaluation after prompt selection | for selection certificate | split identifier and no reuse guarantee |
Appendix figures & tables8 assets
Supplementary material from the paper’s appendix.
Appendix
| Symbol | Meaning |
|---|---|
| , | query, task descriptor, or user request |
| ; | data store given ; fresh deployment item |
| , ; | complete transcript (Definition 3.1 ); pipeline kernel (Definition 3.3 ) |
| , | coupled law and decoupled (ghost) law of store and transcript |
| ; | distinct selected indices; context length |
| , , | loss of the frozen predictor, its risk, and its selected-context score |
| Assumption | Why it is used | When it holds in deployment | How to weaken or check it |
|---|---|---|---|
| Conditional i.i.d. store | gives a ghost store with clean selected-example concentration | exchangeable items within a task; the strongest idealization for scraped corpora | use Proposition D.21 , blocking, clustered bootstrap, or an effective |
| Frozen in-context learner after transcript | separates prompt adaptivity from model training | a version-pinned model during the search window | include any model-in-the-loop edits in |
| Logged transcript contains all data-dependent choices | makes capacity auditable | retrieval stacks that log candidates, scores, filters, and seeds | store candidate ids, validation scores, filters, and random seeds |
| Bounded or sub-Gaussian losses | yields finite cumulant envelope | accuracy, exact match, task success ( ) | use robust losses, clipping, or sub-gamma Theorem D.19 |
| Prior retriever dominates generated candidates | PAC-Bayes KL charges data-dependent gates | a base retriever or recipe library fixed before any score is read | condition the prior only on public metadata or a separate split; log |
| Qwen2.5-7B-Instruct (zero-shot ) | GPT-4.1-mini (zero-shot ) | ||||||||||
| 16 | 32 | 64 | 128 | 256 | 16 | 32 | 64 | 128 | 256 | ||
| mean gap, best-of-64 | 0.057 | 0.039 | 0.023 | 0.016 | 0.010 | 0.052 | 0.042 | 0.028 | 0.017 | 0.008 | |
| 95th percentile gap | 0.142 | 0.107 | 0.071 | 0.045 | 0.014 | 0.148 | 0.109 | 0.074 | 0.045 | 0.010 | |
| bound on mean gap, Thm. 4.1 | 0.361 | 0.255 | 0.180 | 0.127 | 0.090 | 0.361 | 0.255 | 0.180 | 0.127 | 0.090 | |
| certificate, Thm. 4.2 | 0.600 | 0.425 | 0.300 | 0.212 | 0.150 | 0.600 | 0.425 | 0.300 | 0.212 | 0.150 | |
| certified risk, SCAR | 0.455 | 0.363 | 0.292 | 0.232 | 0.198 | 0.455 | 0.351 | 0.296 | 0.239 | 0.204 | |
In-Context Example Selection
In-context example selection chooses demonstrations that help language and multimodal models perform a query-specific task without changing model weights.
See all 32 papers