Research map / Large language models / Language, safety and interpretability

Sample Efficient Demonstration Selection for In-Context Learning

ICML 2025 · Large language models › Language, safety and interpretability · approach: In-context learning analysis · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes CASE, a challenger-arm sampling top-m best-arm identification method in a stochastic linear bandit that selects few-shot exemplar subsets for in-context learning with far fewer LLM calls than LENS and EXPLORA.

Problem

Selecting few-shot exemplar subsets for in-context learning is exponentially large combinatorially and each evaluation requires costly LLM calls, so sample-efficient exemplar selection is needed.

Approach

Formulate multi-exemplar-subset selection as top-m arm identification in a stochastic linear bandit with a similarity-based linear reward, and maintain a shortlist of sampled challenger arms (selective exploration) so gap-index computations and LLM calls scale with the shortlist rather than all exponentially many subsets.

Key results

• CASE with GPT-3.5-turbo reaches 79.91 on GSM8K vs 77.86 for EXPLORA and 69.37 for LENS, with about 7x fewer LLM calls than EXPLORA (480 vs 3619 on GSM8K).
• On synthetic K=10, m=3 bandit experiments, CASE needs about 20,367 comparisons vs 948,206 for LinGapE and 2,180,252 for LinGIFA.
• CASE with GPT-4o-mini improves over LENS, e.g. 91.13 vs 76.19 on GSM8K.

Measured effects reported in the paper

Surprising findings

• Exemplars selected with small open LLMs (Mistral-7B, Llama2-7B) transfer to larger GPT-3.5-turbo, suggesting exemplar reuse across models.
• On AquaRAT, CASE uses more total LLM calls than EXPLORA, because EXPLORA stops after 10 iterations while CASE runs to convergence.

Limitations

• The regret bound for CASE is not rigorously derived; the paper relies on an assumed average regret bound justified via SETC.
• On AquaRAT the total number of LLM calls is slightly higher than EXPLORA.
• Main experiments use only 5-shot prompts and small sets of tasks; smaller open models perform noticeably worse than GPT models.

Experimental setup

Datasets: GSM8K AquaRAT TabMWP FinQA StrategyQA

Benchmarks: GSM8K AquaRAT TabMWP FinQA StrategyQA

Metrics: exact match cover-EM simple regret number of LLM calls runtime gap index comparisons

Baselines: KNN MMR KNN+SC MMR+SC PromptPG Manual Few-Shot CoT Random GraphCut FacilityLocation Active-prompt EXPLORA LENS

Builds on: GIFA LinGapE LENS EXPLORA chain-of-thought prompting

Closest papers by meaning

• Prompt Optimization with EASE? Efficient Ordering-aware Automated Selection of Exemplars (NeurIPS 2024 · similarity 0.89)
• Efficient Prompt Optimization Through the Lens of Best Arm Identification (NeurIPS 2024 · similarity 0.89)
• Comparative Analysis of Demonstration Selection Algorithms for In-Context Learning in Large Language Models (Student Abstract) (AAAI 2025 · similarity 0.88)
• Large Language Models are Demonstration Pre-Selectors for Themselves (ICML 2025 · similarity 0.88)
• Provoking Multi-modal Few-Shot LVLM via Exploration-Exploitation In-Context Learning (CVPR 2025 · similarity 0.85)
• Demonstration Selection for In-Context Learning via Reinforcement Learning (ICML 2025 · similarity 0.85)