The Price of Choosing Examples: Context Overfitting in Adaptive In-Context Learning
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.
The following analysis is generated by AI and may contain errors. It is separate from the authors’ abstract and is not peer review.
Research summary
The paper formalizes the statistical cost of adaptive prompt selection in in-context learning, proving sharp generalization bounds and introducing a stability-constrained retrieval algorithm that ensures valid risk certification.
Methodology
The paper introduces a rigorous theoretical framework for "context overfitting" in adaptive in-context learning (ICL). By modeling prompt construction as adaptive data analysis, the authors define "context capacity" as the mutual information between the data store and the final prompt transcript. They derive finite-sample generalization bounds of order $\sqrt{\kappa/k}$, where $\kappa$ is the capacity and $k$ is the number of selected examples. The methodology is mathematically sound, utilizing stochastic kernel calculus and PAC-Bayesian tools to handle the dependency between the selection process and the evaluation data. The introduction of the SCAR (Stability-constrained adaptive retrieval) algorithm provides a practical, regularized alternative to hard empirical prompt search, offering a concrete application of the theory.
Results & evaluation
The experimental section validates the theory on the Banking77 dataset using Qwen2.5-7B and GPT-4.1-mini. The authors demonstrate that the derived certificates hold across 24,000 resampled selection events. They show that the SCAR rule certifies risk below zero-shot error in over 99% of validation draws. While the experiments are limited to a single task (intent classification) and a specific retrieval recipe library, they effectively illustrate the theoretical predictions, particularly the trade-off between aggressive prompt search (high capacity) and statistical validity.
Reproducibility
The paper provides detailed protocols for the Banking77 experiments, including specific model versions, embedding models (bge-small-en-v1.5), and hyperparameters. The authors mention releasing scripts and cached model outputs, which enhances reproducibility. The theoretical proofs are included in the appendices, allowing for verification of the mathematical claims.
Limitations
The primary limitation is the gap between the theoretical worst-case bounds and the empirical results; the certificates are noted to be conservative by roughly an order of magnitude on the benign Banking77 library. The theory assumes a frozen in-context learner and does not account for the internal dynamics of how the transformer processes the prompt, which may limit its applicability to dynamic or fine-tuned models. Additionally, the experiments are confined to a single domain, leaving the generalizability of the SCAR rule to other tasks unverified.
Broader impact
This work addresses a critical flaw in current RAG and few-shot prompting practices: the reuse of validation data for prompt selection. By providing a statistical framework to quantify the "price" of this adaptivity, the paper offers a path toward more honest evaluation and deployment of LLMs. The proposed SCAR algorithm could be adopted as a standard practice for stable prompt retrieval, potentially reducing overfitting in production systems. The paper formalizes the statistical cost of adaptive prompt selection in in-context learning, proving sharp generalization bounds and introducing a stability-constrained retrieval algorithm that ensures valid risk certification.
Author of this paper? Send a correction.