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

Data Efficient Sample Selection for In-Context Learning
Sep 6, 2026V Venktesh, Cem Levi, Avishek AnandIn-Context Example Selection In-Context Learning
Stockholm University · SKIM Group B.V. · TU Delft
Easier to Judge than to Find: Predicting In-Context Learning Success for Demonstration Selection
May 18, 2026Haochun Wang, Chaofen Yang, Jiatong Liu +5LLM Inference Efficiency In-Context Example Selection
Research Center for Social Computing and Interactive Robotics, Harbin Institute of Technology, China.
A Theoretical Interpretation of In-Context Learning via Probabilistic Modeling
Jun 27, 2026Zhenyu Liu, Huaze Tang, Shao-Lun HuangIn-Context Learning
Tsinghua Shenzhen International Graduate School, Tsinghua University, Shenzhen, China

Sep 6, 2026J/K move · Enter open · S save

Data Efficient Sample Selection for In-Context Learning

V Venktesh, Cem Levi, Avishek Anand

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

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

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

Data Efficient Sample Selection for In-Context Learning

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

A Theoretical Interpretation of In-Context Learning via Probabilistic Modeling