The Price of Choosing Examples: Context Overfitting in Adaptive In-Context Learning

Xiaoyu Li, Jiangxuan LongarXiv 2026 · arXiv

This paper, presented at NeurIPS 2024, tackles a critical but often overlooked issue in modern AI systems: context overfitting. As we move from static prompts to dynamic Retrieval-Augmented Generation (RAG) and agentic workflows, the way we choose examples for a model's context becomes a source of statistical bias.

TL;DR

The authors formalize "context overfitting"—the phenomenon where prompt examples selected specifically for a query look deceptively good but fail to generalize. They introduce context capacity to quantify this bias and provide rigorous generalization bounds alongside a new, stable retrieval algorithm called SCAR.

What Problem Does This Paper Address?

In-context learning (ICL) is typically analyzed as if prompt examples are sampled randomly. However, in production, we use complex pipelines to retrieve, filter, and re-rank demonstrations based on the specific query.

This adaptivity creates a "winner's curse": if you try enough different prompt templates or retrieval recipes, you will eventually find one that performs perfectly on your validation examples just by chance. This leads to context overfitting, where the reported performance on the selected context is significantly better than the model's actual deployment risk. The paper asks: What is the statistical price of choosing examples, and how can we trust that a "good" prompt will actually work on new data?

Methods

The authors treat prompt construction as a form of adaptive data analysis.

  • Context Capacity ($\kappa$): They define a new metric based on mutual information (or max-information) between the data store and the final prompt transcript. This measures how much "information" about the specific data store was used to pick the prompt.
  • Generalization Bounds: They prove that the gap between the observed performance on the selected context and the true deployment risk is at most $O(\sqrt{\kappa/k})$, where $k$ is the number of examples in the prompt. Crucially, the denominator is the context length $k$, not the total size of the data store $n$.
  • The "Ghost Law": To prove these bounds, they introduce a "ghost law" framework (Figure 1), comparing the real performance (coupled law) to performance on a fresh, independent "ghost" store.
Figure 1: Coupled (real) and decoupled (ghost) laws of store and transcript. The ghost law scores the same transcript on a fresh store, so its selected-context score averages k fresh losses; one change of measure back to the real law costs the context capacity κ.
  • SCAR (Stability-Constrained Adaptive Retrieval): Instead of "hard" selection (picking the single best-performing recipe), SCAR uses a regularized, randomized rule (a Gibbs distribution). This stabilizes the selection process, making the resulting performance estimates statistically certifiable.

Datasets

  • Banking77: A standard intent classification dataset with 77 categories. The authors used it to test 64 different retrieval recipes (varying templates, retrieval rules, and example counts).
  • Synthetic Benchmarks: Used to verify the "winner's curse" scaling laws and multi-round search dynamics.
  • API-Backed LLM Tests: Real-world stress tests using OpenAI's embeddings and models (GPT-4o-mini) to simulate prompt-engineering workflows.

Key Insights and Ideas

  • $k$ is the Effective Sample Size: A common misconception is that having a massive data store ($n$) makes selection safer. This paper shows that generalization depends on the number of selected examples ($k$). If you search over exponentially many prompts, you can "erase" the benefit of a long context.
  • Capacity Composes: Prompt engineering is often multi-round (retrieve, test, edit, repeat). The authors show that capacity adds up across rounds. This provides a formal "budgeting" rule for prompt engineers: every time you tweak a prompt based on validation results, you spend some of your "generalization budget."
  • Stability vs. Quality: High-quality retrieval (finding relevant examples) is good for prediction, but only stable retrieval (not being overly sensitive to small data changes) allows for statistical certification.

Key Results

  • Certification in Practice: On the Banking77 dataset, the theoretical certificates held in 100% of the 24,000 resampled selection events.
  • Beating Zero-Shot: Using the SCAR algorithm, the authors were able to certify that their adaptive ICL risk was lower than the zero-shot error in over 99% of validation draws (Figure 2).
  • Sharpness: They proved a matching lower bound, showing that their $O(\sqrt{\kappa/k})$ rate is essentially the best possible—you cannot avoid this "price of choice" in the worst case.
Figure 2: Banking77 recipe selection. (a) Mean gap of the best-of-M recipe in 30 (M, k) cells, with 95% intervals. (b) M = 64: mean and 95th-percentile gap (blue; amber: GPT-4.1-mini mean) against Theorems 4.1 (dashed) and 4.2 (solid). (c) Zero-shot error minus certified risk for SCAR and for the best-of-64 winner certified by Theorem 6.1; solid: Qwen, dashed: GPT-4.1-mini.

Limitations and Future Work

  • Model Agnosticism: The theory treats the LLM as a "frozen" map. It doesn't explain why a transformer is a good in-context learner, only how to validate the context selection process.
  • I.I.D. Assumption: The current bounds assume the data store contains independent items. Future work is needed to handle highly correlated data (e.g., near-duplicate documents in a RAG system).
  • Practical Accounting: While mutual information is hard to compute for arbitrary pipelines, the authors suggest a "reporting norm": practitioners should log the number of attempted prompts, re-ranking candidates, and validation passes to provide an auditable "capacity budget."

Summary updated

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 $\sqrt{κ/k}$, where $k$ is the number of selected examples whose losses form the reported score. We prove a matching lower bound, whose constant is exact when $\log k\llκ\ll k$, 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-$k$ 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.
BibTeX
@misc{li2026price,
  author = {Xiaoyu Li and Jiangxuan Long},
  title = {{The Price of Choosing Examples: Context Overfitting in Adaptive In-Context Learning}},
  year = {2026},
  eprint = {2611.21251},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.21251},
}
Figure