UCS: Estimating Unseen Coverage for Improved In-Context Learning

Jiayi Xin; Xiang Li; Evan Qiang; Weiqing He; Tianqi Shang; Weijie J. Su; Qi Long

cs.LGApr 13, 2026

UCS: Estimating Unseen Coverage for Improved In-Context Learning

Authors: Jiayi Xin, Xiang Li, Evan Qiang, Weiqing He, Tianqi Shang, Weijie J. Su, Qi Long

Organizations: University of Pennsylvania

Abstract

In-context learning (ICL) performance depends critically on which demonstrations are placed in the prompt, yet most existing selectors prioritize heuristic notions of relevance or diversity and provide limited insight into the coverage of a demonstration set. We propose Unseen Coverage Selection (UKS), a training-free, subset-level coverage prior motivated by the principle that a good demonstration set should expose the model to latent cluster unrevealed by the currently selected subset. UCS operationalizes this idea by (1) inducing discrete latent clusters from model-consistent embeddings and (2) estimating the number of unrevealed clusters within a candidate subset via a Smoothed Good--Turing estimator from its empirical frequency spectrum. Unlike previous selection methods, UCS is coverage-based and training-free, and can be seamlessly combined with both query-dependent and query-independent selection baselines via a simple regularized objective. Experiments on multiple intent-classification and reasoning benchmarks with frontier Large Language Models show that augmenting strong baselines with UCS consistently improves ICL accuracy by up to 2-6% under the same selection budget, while also yielding insights into task- and model-level latent cluster distributions. Code is available at https://github.com/Raina-Xin/UCS.

Figures & tables

Figure 1: Contrast to prior methods ( left ), our approach reasons at the subset level by clustering demonstrations into latent clusters and using their frequency to measure coverage ( right ).

Figure 2: Schematics of UCS . (1) Demonstrations are embedded in a model-consistent space. (2) Embeddings are discretized into latent clusters via dictionary learning and clustering. (3) Candidate subsets are scored using an SGT estimation-regularized objective with a base selection utility. (4) The selected subset is used for ICL.

Methods	UCS-augmented scoring rule
DPP+UCS	$\arg\max_{i\notin S}\ \Delta_{\text{DPP}}(i\mid S)+\lambda(\Phi(S\cup\{i\})-\Phi(S))$
MDL+UCS	$\arg\max_{S\in\mathcal{C}(x)}\ \text{MDL}(S;x)+\lambda\Phi(S)$
VoteK+UCS	$\text{score}(i)=v(i)+\lambda\log w_{c(i)},\ \ w_{c}\propto(\widehat{g}_{n_{c}}+\epsilon)^{-1}$

Table 1: Instantiations of UCS for three baselines.

Backbone Model	Dataset	MDL	UCS+MDL	DPP	UCS+DPP	VoteK	UCS+VoteK
Qwen2.5-7B-it	Banking77	0.764 $\pm 0.019$	0.771 $\pm 0.011$	0.831 $\pm 0.005$	0.831 $\pm 0.007$	0.518 $\pm 0.008$	0.543 $\pm 0.020$
	CLINC150	0.748 $\pm 0.004$	0.752 $\pm 0.012$	0.755 $\pm 0.011$	0.775 $\pm 0.010$	0.703 $\pm 0.001$	0.744 $\pm 0.010$
	HWU64	0.785 $\pm 0.002$	0.801 $\pm 0.011$	0.791 $\pm 0.003$	0.794 $\pm 0.004$	0.609 $\pm 0.003$	0.671 $\pm 0.021$
Llama-3.2-3B-it	Banking77	0.718 $\pm 0.003$	0.732 $\pm 0.012$	0.743 $\pm 0.008$	0.746 $\pm 0.006$	0.421 $\pm 0.009$	0.426 $\pm 0.002$
	CLINC150	0.747 $\pm 0.005$	0.755 $\pm 0.006$	0.698 $\pm 0.008$	0.714 $\pm 0.009$	0.597 $\pm 0.003$	0.599 $\pm 0.008$
	HWU64	0.537 $\pm 0.008$	0.539 $\pm 0.010$	0.565 $\pm 0.003$	0.571 $\pm 0.008$	0.457 $\pm 0.004$	0.498 $\pm 0.020$

Table 2: UCS consistently improves base selection across different datasets and models. ICL accuracy (higher is better) across three intent classification datasets. Each method selects a demonstration set of size budget=10 using dict_dbscan clustering. We evaluate on test_size=500 examples and report mean

\pm

std over n_runs=3 .

Backbone Model	Dataset	MDL	UCS+MDL	DPP	UCS+DPP	VoteK	UCS+VoteK
Qwen2.5-7B-it	Causal	0.608 $\pm 0.012$	0.692 $\pm 0.042$	0.517 $\pm 0.012$	0.542 $\pm 0.012$	0.492 $\pm 0.012$	0.525 $\pm 0.00$
	Properties	0.083 $\pm 0.029$	0.092 $\pm 0.031$	0.050 $\pm 0.020$	0.067 $\pm 0.024$	0.050 $\pm 0.020$	0.067 $\pm 0.012$
	Shuffled	0.200 $\pm 0.043$	0.225 $\pm 0.000$	0.133 $\pm 0.012$	0.258 $\pm 0.012$	0.242 $\pm 0.063$	0.242 $\pm 0.043$

Table 3: UCS consistently improves base selection on reasoning tasks (Qwen2.5-7B). ICL accuracy (higher is better) across three Big-Bench Extra Hard (BBEH) reasoning datasets ( Kazemi et al., 2025 ) : Causal Understanding, Object Properties, and Shuffled Objects. Each method selects a demonstration set of size budget=10 using dict_dbscan clustering. We evaluate on test_size=40 examples and report mean

\pm

std over n_runs=3 .

Figure 3: Cluster-size distributions across datasets and LLMs. Left: number of demonstrations in clusters of size

k\in[1,8]

(heavy-tailed, many singletons). Right: sizes of the top-

8

clusters (a few dominant clusters).

Method	# Uniq Clusters	Cluster Size	1/Size
MDL	9.53 $\pm 0.006$	6.28 $\pm 0.550$	0.689 $\pm 0.007$
UCS+MDL	9.49 $\pm 0.031$	6.57 $\pm 0.734$	0.688 $\pm 0.005$
DPP	9.62 $\pm 0.014$	6.29 $\pm 0.323$	0.701 $\pm 0.003$
UCS+DPP	9.93 $\pm 0.016$	5.39 $\pm 0.178$	0.719 $\pm 0.004$
VoteK	9.67 $\pm 0.471$	8.50 $\pm 1.390$	0.604 $\pm 0.020$
UCS+VoteK	10.0 $\pm 0.000$	1.00 $\pm 0.000$	1.00 $\pm 0.000$

Table 4: UCS Prioritizes Cluster Coverage. Metrics for Qwen on CLINC150. # Uniq Clusters : number of distinct clusters in the selected prompt. Cluster Size : average size of the clusters that the selected demos belong to (over the entire pool). 1/Size : per-demo inverse cluster size averaged over the prompt; a value of 1.0 indicates all demos come from singleton clusters.

Backbone	Dataset	Single-Source	Joint-Source	$\Delta$
Qwen	Banking77	83.1 $\pm 0.7$	78.3 $\pm 1.3$	$-4.8$
	CLINC150	77.5 $\pm 0.1$	82.3 $\pm 2.0$	$+4.8$
	HWU64	79.4 $\pm 0.4$	67.5 $\pm 1.3$	$-11.9$
Llama	Banking77	74.6 $\pm 0.6$	74.6 $\pm 1.1$	$0.0$
	CLINC150	71.4 $\pm 0.9$	70.5 $\pm 1.3$	$-0.9$
	HWU64	57.1 $\pm 0.8$	57.7 $\pm 4.7$	$+0.6$

Table 5: Single-Source vs. Joint-Source UCS. Comparison of UCS+DPP accuracy (

B{=}10

) when using a dictionary derived from the inference model itself (Single-Source) versus a Joint Dictionary aligned across multiple LLMs. The joint representation maintains performance for the 3B model but shows trade-offs for the larger 7B model.

$t$	bin size	$\textsc{UCS}{+}\textsc{MDL}$	$\Delta$
2	10	73.1 $\pm 1.1$	$+$ 1.3
4	10	73.0 $\pm 0.7$	$+$ 1.2
8	10	72.9 $\pm 1.6$	$+$ 1.1
4	5	72.8 $\pm 1.7$	$+$ 1.0
4	20	72.9 $\pm 1.2$	$+$ 1.1

Table 6: Sensitivity to SGT hyperparameters. Accuracy and improvement for MDL and UCS+MDL for Llama model on Banking77 dataset.

Budget	MDL	$\textsc{UCS}{+}\textsc{MDL}$	$\Delta$
0	34.7 $\pm 0.7$	34.9 $\pm 0.2$	$+$ 0.2
1	56.4 $\pm 1.1$	56.5 $\pm 1.6$	$+$ 0.1
5	70.9 $\pm 1.9$	72.4 $\pm 1.1$	$+$ 1.5
10	71.8 $\pm 0.3$	73.2 $\pm 1.2$	$+$ 1.4
20	63.6 $\pm 0.3$	65.9 $\pm 2.1$	$+$ 2.3

Table 7: Sensitivity to selection budget. Accuracy (%) as a function of the number of demonstrations for MDL and UCS+MDL with Llama on Banking77 dataset.

Embedding construction
UCS +DPP	Banking77	CLINC150	HWU64
Mid+Mean	73.9 $\pm$ 0.1	70.7 $\pm$ 0.8	57.3 $\pm$ 1.2
Last+LastToken	73.7 $\pm$ 1.4	71.7 $\pm$ 0.5	56.7 $\pm$ 1.5
Last+Mean+ $\ell_{2}$ Norm	74.8 $\pm$ 1.3	71.7 $\pm$ 0.9	57.5 $\pm$ 0.8
Clustering method
dbscan	73.6 $\pm$ 1.1	70.4 $\pm$ 0.2	54.2 $\pm$ 0.6

Table 8: Ablation results : Accuracy in %, mean

\pm

std over 3 runs on three datasets. “Mid” and “Last” refer to the layer used for embedding extraction. Two alternative clustering methods are described in Section 3.4 .

Method	Banking77	CLINC150	HWU64
VoteK	42.1 $\pm$ 0.9	59.7 $\pm$ 0.3	45.7 $\pm$ 0.4
UCS+VoteK	42.6 $\pm$ 0.2	59.9 $\pm$ 0.8	49.8 $\pm$ 2.0
B1	40.8 $\pm$ 2.3	60.0 $\pm$ 1.4	44.2 $\pm$ 1.1
B2	43.6 $\pm$ 1.7	59.1 $\pm$ 1.1	44.2 $\pm$ 1.1

Table 9: Rarity-only VoteK controls (Llama-3.2-3B-it). Mean

\pm

std accuracy (%) over 3 runs. B1: inverse-size rarity. B2: spectrum rarity without GT.

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Dataset (size)	Pool embed	Dict fit	Dict transform	DBSCAN	Total
CLINC150 ( ${\sim}$ 15k)	35.88	19.65	0.17	0.37	57.03
HWU64 ( ${\sim}$ 10k)	19.87	16.57	0.24	0.24	37.83
BANKING77 ( ${\sim}$ 11k)	27.70	14.25	0.19	0.26	43.31

Appendix

Table 10: Offline preprocessing (one-time per dataset+model, in seconds).

Dataset	MDL+UCS	VoteK+UCS	DPP+UCS
CLINC150	+1.96	$-$ 13.37	+605.84
HWU64	$-$ 0.09	+2.75	+680.70
BANKING77	+2.28	+1.19	+625.38

Appendix

Table 11: Online selection overhead (

\Delta

end-to-end time in seconds, selection + ICL evaluation).

Component	Hyperparameter	Value
Data / Evaluation	--dataset_type	banking77 / clinc150 / hwu64
	--budget	10
	--test_size	500
	--n_runs	3
	--seed	42
	--icl_batch_size	16

Appendix

Table 12: Common Hyperparameters used for Experiments.

Backbone	Retriever	Banking77	CLINC150	HWU64
Qwen2.5 7B-it	UCS+MDL	0.15	0.01	0.15
	UCS+DPP	0.01	0.01	0.01
	UCS+VoteK	0.01	0.01	0.01
Llama-3.2 3B-it	UCS+MDL	0.01	0.01	0.01
	UCS+DPP	0.01	0.01	0.01
	UCS+VoteK	0.01	0.01	0.01

Appendix

Table 13: Tuned dbscan_q values. This parameter controls the density quantile for clustering. It is tuned separately for each backbone and retriever combination to ensure the granularity of clusters matches the retriever’s selection logic.

Backbone	Retriever	Banking77	CLINC150	HWU64
Qwen2.5 7B-it	UCS+MDL	0.01	0.005	0.001
	UCS+DPP	0.001	0.01	0.01
	UCS+VoteK	5.0	5.0	5.0
Llama-3.2 3B-it	UCS+MDL	0.05	0.05	0.05
	UCS+DPP	0.50	0.05	0.05
	UCS+VoteK	0.05	0.05	0.50

Appendix

Table 14: Tuned sgt_lambda values. This parameter controls the strength of the UCS term (

\lambda

) added to the Retriever score. It balances the exploitation of the base method (MDL/DPP/VoteK) with the exploration of unseen clusters.

Explore similar work

Sep 6, 2026

Data Efficient Sample Selection for In-Context Learning

The In-context learning (ICL) paradigm aids large language models (LLMs) to adapt to new tasks without need for fine-tuning. However, selecting an optimal combination of demonstration examples from a large pool of example subsets is a challenging problem. Existing approaches for selection do not model the complex relationship between ICL samples and downstream LLM performance. They typically perform static task-level selection, choosing subsets once offline, which can fail to generalize to unseen queries. We introduce DearICL (Data Efficient Algorithm for Ranking) ICL samples, a new framework that models demonstration example selection as a subset ranking problem. DearICL employs a non-linear surrogate employing a differentiable sorting objective within a gap-index bandit algorithm. The gap-index based approach enables fine-grained separation of good arms and borderline arms, which is used as an auxiliary objective to train the non-linear surrogate through sufficient sampling of borderline arms, supporting instance-level subset ranking. On exemplar selection benchmarks with open-source LLMs, DearICL achieves 8.08-15.9% accuracy gains over strong linear bandit baselines, with low sample complexity. Code and data: https://github.com/VenkteshV/DearICL.

V Venktesh, Cem Levi, Avishek Anand

Stockholm University · SKIM Group B.V. · TU Delft

In-Context Example Selection In-Context Learning Learning to Rank

Ask PDF

May 18, 2026

Easier to Judge than to Find: Predicting In-Context Learning Success for Demonstration Selection

In-context learning (ICL) is highly sensitive to which demonstrations appear in the prompt, but selecting them is expensive because the space of possible demonstration contexts and combinations is enormous. We argue that demonstration selection is easier to judge than to find: predicting whether a specific query--context pair

(q,D)

will succeed is cheaper and more general than searching for an optimal

D^\star

. Based on this insight, we propose DiSP, a sample-and-judge framework that stratifies queries by difficulty. DiSP runs random demonstration trials to estimate success rate of each training query, trains a lightweight router to predict difficulty from the query, and trains level-specific judges for sampled demonstrations. At inference, DiSP performs stop-on-acceptance judging under an explicit budget, emitting diagnostic risk tags when no suitable context is found. Across five classification datasets with Llama~~3--8B and Qwen~~2.5--7B, DiSP achieves the best average accuracy, improving over strong learned selection baselines by up to 3.4%, while achieving up to

23\times

end-to-end wall-clock speedup.

Haochun Wang, Chaofen Yang, Jiatong Liu +5

Research Center for Social Computing and Interactive Robotics, Harbin Institute of Technology, China.

LLM Inference Efficiency In-Context Example Selection Few-Shot Learning In-Context Learning

Ask PDF

Jun 27, 2026

A Theoretical Interpretation of In-Context Learning via Probabilistic Modeling

In-context learning (ICL) is an emerging paradigm that employs the semantic information inherent in large language models (LLMs) for generating answers to user queries. While the remarkable performance of ICL has been widely known, a general modeling and a rigorous theoretical analysis of this paradigm are still lacking. This work presents a probabilistic model for ICL and derives the performance of ICL for both general parametric distributions and exponential families. Based on the derived results, the work explains the impact of multiple factors such as the number of demonstrations, the sensitivity of the probabilistic model to the variation of its parameters, as well as the similarity between the demonstrations and the query on the performance of ICL.

Zhenyu Liu, Huaze Tang, Shao-Lun Huang

Tsinghua Shenzhen International Graduate School, Tsinghua University, Shenzhen, China

In-Context Learning

Ask PDF