# Sample Efficient Demonstration Selection for In-Context Learning

arXiv: https://arxiv.org/abs/2506.08607 · HTML: https://mlsanity.com/paper/2506.08607/

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- Builds on 37 of its 50 references that are in the map.
- First posted on arXiv 10 Jun 2025.

## Builds on (most cited first, 30 of 37)

- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [HotpotQA: A Dataset for Diverse, Explainable Multi-hop Question Answering](https://mlsanity.com/paper/1809.09600/) (2018)
- [Calibrate Before Use: Improving Few-Shot Performance of Language Models](https://mlsanity.com/paper/2102.09690/) (2021)
- [Fantastically Ordered Prompts and Where to Find Them: Overcoming Few-Shot Prompt Order Sensitivity](https://mlsanity.com/paper/2104.08786/) (2021)
- [Program of Thoughts Prompting: Disentangling Computation from Reasoning for Numerical Reasoning Tasks](https://mlsanity.com/paper/2211.12588/) (2022)
- [Measuring and Narrowing the Compositionality Gap in Language Models](https://mlsanity.com/paper/2210.03350/) (2022)
- [Did Aristotle Use a Laptop? A Question Answering Benchmark with Implicit Reasoning Strategies](https://mlsanity.com/paper/2101.02235/) (2021)
- [Program Induction by Rationale Generation : Learning to Solve and Explain Algebraic Word Problems](https://mlsanity.com/paper/1705.04146/) (2017)
- [Learning To Retrieve Prompts for In-Context Learning](https://mlsanity.com/paper/2112.08633/) (2021)
- [Plan-and-Solve Prompting: Improving Zero-Shot Chain-of-Thought Reasoning by Large Language Models](https://mlsanity.com/paper/2305.04091/) (2023)
- [Complexity-Based Prompting for Multi-Step Reasoning](https://mlsanity.com/paper/2210.00720/) (2022)
- [Dynamic Prompt Learning via Policy Gradient for Semi-structured Mathematical Reasoning](https://mlsanity.com/paper/2209.14610/) (2022)
- [Prompt Cache: Modular Attention Reuse for Low-Latency Inference](https://mlsanity.com/paper/2311.04934/) (2023)
- [Active Example Selection for In-Context Learning](https://mlsanity.com/paper/2211.04486/) (2022)
- [Active Prompting with Chain-of-Thought for Large Language Models](https://mlsanity.com/paper/2302.12246/) (2023)
- [Finding Support Examples for In-Context Learning](https://mlsanity.com/paper/2302.13539/) (2023)
- [Sequential Experimental Design for Transductive Linear Bandits](https://mlsanity.com/paper/1906.08399/) (2019)
- [Optimal Best-arm Identification in Linear Bandits](https://mlsanity.com/paper/2006.16073/) (2020)
- [Complementary Explanations for Effective In-Context Learning](https://mlsanity.com/paper/2211.13892/) (2022)
- [Gamification of Pure Exploration for Linear Bandits](https://mlsanity.com/paper/2007.00953/) (2020)
- [Knowledge-Aware Language Model Pretraining](https://mlsanity.com/paper/2007.00655/) (2020)
- [Fully adaptive algorithm for pure exploration in linear bandits](https://mlsanity.com/paper/1710.05552/) (2017)
- [Submodular Optimization with Submodular Cover and Submodular Knapsack Constraints](https://mlsanity.com/paper/1311.2106/) (2013)
- [Nearly Instance Optimal Sample Complexity Bounds for Top-k Arm Selection](https://mlsanity.com/paper/1702.03605/) (2017)
- [Online Learning to Rank in Stochastic Click Models](https://mlsanity.com/paper/1703.02527/) (2017)
- [QuanTemp: A real-world open-domain benchmark for fact-checking numerical claims](https://mlsanity.com/paper/2403.17169/) (2024)
- [Online Learning to Rank with Features](https://mlsanity.com/paper/1810.02567/) (2018)
- [Guiding Retrieval using LLM-based Listwise Rankers](https://mlsanity.com/paper/2501.09186/) (2025)
- [Top-m identification for linear bandits](https://mlsanity.com/paper/2103.10070/) (2021)

## Built on by (most cited first, 13 of 13)

- [Bridging Streaming Continual Learning via In-Context Large Tabular Models](https://mlsanity.com/paper/2512.11668/) (2025)
- [Context Learning for Multi-Agent Discussion](https://mlsanity.com/paper/2602.02350/) (2026)
- [Learning to Select Visual In-Context Demonstrations](https://mlsanity.com/paper/2603.26775/) (2026)
- [Efficient Text Classification with Conformal In-Context Learning](https://mlsanity.com/paper/2512.05732/) (2025)
- [Shaping Schema via Language Representation as the Next Frontier for LLM Intelligence Expanding](https://mlsanity.com/paper/2605.09271/) (2026)
- [Towards Reliable, Generalizable, and Specific In-Context Knowledge Editing via Multi-Objective Reinforcement Learning](https://mlsanity.com/paper/2608.25100/) (2026)
- [Large Language Models Can Perform Automatic Modulation Classification via Discretized Self-supervised Candidate Retrieval](https://mlsanity.com/paper/2510.00316/) (2025)
- [Challenger-Based Combinatorial Bandits for Subcarrier Selection in OFDM Systems](https://mlsanity.com/paper/2510.04559/) (2025)
- [Data Efficient Sample Selection for In-Context Learning](https://mlsanity.com/paper/2609.06670/) (2026)
- [Downstream-Aware Context Selection for Online In-Context Reinforcement Learning](https://mlsanity.com/paper/2609.33166/) (2026)
- [You Only Edit Once: Incentivizing In-Context Capability of LLMs via Local Demonstration Refinement](https://mlsanity.com/paper/2609.33609/) (2026)
- [Efficient Task Adaptation in Large Language Models: A Survey of Weight-Based, Prompt-Based, and Embedding-Based Adaptations](https://mlsanity.com/paper/2610.00928/) (2026)
- [Accelerating Linear Bandits with Persistent Candidate Sets](https://mlsanity.com/paper/2610.13407/) (2026)

## Abstract (arXiv)

The in-context learning paradigm with LLMs has been instrumental in advancing a wide range of natural language processing tasks. The selection of few-shot examples (exemplars / demonstration samples) is essential for constructing effective prompts under context-length budget constraints. In this paper, we formulate the exemplar selection task as a top-m best arms identification problem. A key challenge in this setup is the exponentially large number of arms that need to be evaluated to identify the m-best arms. We propose CASE (Challenger Arm Sampling for Exemplar selection), a novel sample-efficient selective exploration strategy that maintains a shortlist of "challenger" arms, which are current candidates for the top-m arms. In each iteration, only one of the arms from this shortlist or the current topm set is pulled, thereby reducing sample complexity and, consequently, the number of LLM evaluations. Furthermore, we model the scores of exemplar subsets (arms) using a parameterized linear scoring function, leading to stochastic linear bandits setting. CASE achieves remarkable efficiency gains of up to 7x speedup in runtime while requiring 7x fewer LLM calls (87% reduction) without sacrificing performance compared to state-of-the-art exemplar selection methods. We release our code and data at https://github.com/kiranpurohit/CASE