cs.LGNov 16, 2026

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

Authors: Xiaoyu Li, Jiangxuan Long

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 κ/k\sqrt{κ/k}, where kk 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≪κ≪k\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-kk 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

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. Context-Adaptive Inference: A Unified Statistical and Foundation-Model View

    Jul 25, 2026Yue Yao, Caleb N. Ellington, Jingyun Jia +9Adaptive InferenceMeta-Learning