Elamur Research⌕
☰
home / papers / 2026 / UCS: Estimating Unseen Coverage for Improved In-Context Learning

UCS: Estimating Unseen Coverage for Improved In-Context Learning

Paper · 2026 · Jiayi Xin, Xiang Li, Evan Qiang et al.

Summary

Few-shot prompting is highly sensitive to which examples go into the prompt. Existing selectors rank candidates by relevance, diversity or information-based criteria, but none measures how much of a task's hidden structure a chosen set actually exposes. The authors propose Unseen Coverage Selection (UCS), a training-free add-on that scores whole subsets by their coverage.

The pipeline has three stages:

  • Each demonstration input is embedded with the same LLM used at inference, without its label.
  • These vectors are discretized into latent clusters through dictionary learning followed by density-based clustering.
  • A Smoothed Good–Turing estimator reads a subset's cluster-frequency spectrum and predicts how many clusters remain unrevealed.

This estimate enters existing selectors (DPP, MDL, VoteK) as a regularization term. Experiments spanned three intent-classification datasets plus three reasoning tasks drawn from BBEH, and were run on three frontier-class LLMs. Under equal budgets, UCS improved or matched the baselines, with gains of roughly 2–6%. The largest gains came for query-independent selection. The method is cheap, needs no training and gives interpretable views of long-tailed cluster distributions.

Key points

  • Intent benchmarks are Banking77, CLINC150 and HWU64. UCS is layered on VoteK (query-independent) and on DPP and MDL (query-dependent).
  • The maximum reported gain is 6.2% for query-independent selection. With Llama-3.2-3B-it on HWU64, VoteK rises from 45.7% to 49.8%.
  • On Banking77, UCS+MDL beats MDL at every budget, for example 73.2% vs 71.8% at 10 demos and 65.9% vs 63.6% at 20.
  • Ablations show the value of each component:
    • Dropping dictionary learning (plain dbscan) costs 2.9 points on HWU64.
    • Using a coverage-only score instead of the SGT-based objective costs 2.8 points.
    • Rarity-weighting controls without Good–Turing extrapolation fail to reproduce the gains.
  • Limitations: clusters may not match human-interpretable concepts, and evaluation focuses mostly on short-input tasks. Embedding the pool with each model adds offline cost.

Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.

 Institutions

🎓University of PennsylvaniaPhiladelphia · United States233 works · 65,583 citations

 Fields, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 18,614 worksArtificial Intelligence · 17,965 worksArts and Humanities · 17,450 worksLanguage and Linguistics · 17,296 works

🧭 Topics 1Research subjects and languages the work is about.Language models & pretraining · 3,894 works

Cite

Cite as Jiayi Xin, Xiang Li, Evan Qiang, Weiqing He, Tianqi Shang, Weijie J Su and Qi Long. 2026. UCS: Estimating Unseen Coverage for Improved In-Context Learning. Findings of the Association for Computational Linguistics: ACL 2026.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.18653/v1/2026.findings-acl.533

@inproceedings{xin2026ucs,
  title = {{UCS: Estimating Unseen Coverage for Improved In-Context Learning}},
  author = {Jiayi Xin, Xiang Li, Evan Qiang, Weiqing He, Tianqi Shang, Weijie J Su and Qi Long},
  booktitle = {Findings of the Association for Computational Linguistics: ACL 2026},
  year = {2026},
  doi = {10.18653/v1/2026.findings-acl.533},
  url = {https://doi.org/10.18653/v1/2026.findings-acl.533}
}

References

40 references, 17 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

  1. Intent Detection with Dual Sentence Encoders. In Proceedings of the 2nd Workshop on Natural Language Processing for Conversational AI, pages 38– 45, Online. Association for Computational Linguistics. Abhimanyu Dubey, Abhinav Jauhri, Abhinav Pandey, Abhishek Kadian, Ahmad Al-Dahle, Aiesha Letman, Akh… — The Llama 3 Herd of Models
  2. Martin Ester, Hans-Peter Kriegel, Jörg Sander, Xiaowei Xu, and 1 others. 1996. A density-based algorithm for discovering clusters in large spatial databases with noise. In kdd, volume 96, pages 226–231. find
  3. Irving J Good. 1953. The population frequencies of species and the estimation of population parameters. Biometrika, 40(3-4):237–264. find
  4. Shivanshu Gupta, Matt Gardner, and Sameer Singh. 2023. Coverage-based example selection for in-context learning. arXiv preprint arXiv:2305.14907. find
  5. Mehran Kazemi, Bahare Fatemi, Hritik Bansal, John Palowitch, Chrysovalantis Anastasiou, Sanket Vaibhav Mehta, Lalit K Jain, Virginia Aglietti, Disha Jindal, Yuanzhu Peter Chen, and 1 others. 2025. Big-bench extra hard. In Proceedings of the 63rd Annual Meeting of the Association for Computational Li…
  6. Takeshi Kojima, Shixiang Shane Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwasawa. 2022. Large language models are zero-shot reasoners. Advances in neural information processing systems, 35:22199– 22213.
  7. Alex Kulesza, Ben Taskar, and 1 others. 2012. Determinantal point processes for machine learning. Foundations and Trends® in Machine Learning, 5(2–3):123– 286. find
  8. Shengnan An, Bo Zhou, Zeqi Lin, Qiang Fu, Bei Chen, Nanning Zheng, Weizhu Chen, and Jian-Guang Lou. 2023. Skill-based few-shot selection for in-context learning. arXiv preprint arXiv:2305.14210. find
  9. Stefan Larson, Anish Mahendran, Joseph J. Peper, Christopher Clarke, Andrew Lee, Parker Hill, Jonathan K. Kummerfeld, Kevin Leach, Michael A. Laurenzano, Lingjia Tang, and Jason Mars. 2019. An Evaluation Dataset for Intent Classification and Out-of-Scope Prediction. In Proceedings of the 2019 Confer… find
  10. Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, and 1 others. 2020. Language models are few-shot learners. Advances in neural information processing systems, 33:1877–1901.
  11. Itay Levy, Ben Bogin, and Jonathan Berant. 2023. Diverse demonstrations improve in-context compositional generalization. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1401– 1422.
  12. Iñigo Casanueva, Tadas Temčinas, Daniela Gerz, Matthew Henderson, and Ivan Vulić. 2020. find
  13. Efficient Xiang Li, Jiayi Xin, Qi Long, and Weijie J Su. 2025. Evaluating the unseen capabilities: How Sweta Agrawal, Chunting Zhou, Mike Lewis, Luke Zettlemoyer, and Marjan Ghazvininejad. 2023. In-context examples selection for machine translation. In Findings of the Association for Computational L…
  14. Haoyu Liu, Jianfeng Liu, Shaohan Huang, Yuefeng Zhan, Hao Sun, Weiwei Deng, Furu Wei, and Qi Zhang. 2024. Se^2: Sequential example selection for in-context learning. arXiv preprint arXiv:2402.13874. find
  15. Jiachang Liu, Dinghan Shen, Yizhe Zhang, William B Dolan, Lawrence Carin, and Weizhu Chen. 2022. What makes good in-context examples for gpt-3? In Proceedings of Deep Learning Inside Out (DeeLIO 2022): The 3rd workshop on knowledge extraction and integration for deep learning architectures, pages 10…
  16. Xingkun Liu, Arash Eshghi, Pawel Swietojanski, and Verena Rieser. 2019. Benchmarking natural language understanding services for building conversational agents. In Increasing Naturalness and Flexibility in Spoken Dialogue Interaction - 10th International Workshop on Spoken Dialogue Systems, IWSDS 20… find
  17. Yao Lu, Max Bartolo, Alastair Moore, Sebastian Riedel, and Pontus Stenetorp. 2022. Fantastically ordered prompts and where to find them: Overcoming few-shot prompt order sensitivity. In Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), p…
  18. Keqin Peng, Liang Ding, Yancheng Yuan, Xuebo Liu, Min Zhang, Yuanxin Ouyang, and Dacheng Tao. 2024. Revisiting demonstration selection strategies in in-context learning. In Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 9090– 91… find
  19. Chengwei Qin, Aston Zhang, Chen Chen, Anirudh Dagar, and Wenming Ye. 2024. In-context learning with iterative demonstration selection. In Findings of the Association for Computational Linguistics: EMNLP 2024, pages 7441–7455, Miami, Florida, USA. Association for Computational Linguistics. find
  20. Alexander Scarlatos and Andrew Lan. 2023. RetICL: Sequential retrieval of in-context examples with reinforcement learning. Preprint, arXiv:2305.14502. — [arXiv:2305.14502](https://arxiv.org/abs/2305.14502) find
  21. Hongjin Su, Jungo Kasai, Chen Henry Wu, Weijia Shi, Tianlu Wang, Jiayi Xin, Rui Zhang, Mari Ostendorf, Luke Zettlemoyer, Noah A Smith, and 1 others. 2022. Selective annotation makes language models better few-shot learners. arXiv preprint arXiv:2209.01975. find
  22. Gemma Team, Morgane Riviere, Shreya Pathak, Pier Giuseppe Sessa, Cassidy Hardin, Surya Bhupatiraju, Léonard Hussenot, Thomas Mesnard, Bobak Shahriari, Alexandre Ramé, and 1 others. 2024. Gemma 2: Improving open language models at a practical size. arXiv preprint arXiv:2408.00118. find
  23. Minh-Hao Van, Xintao Wu, and 1 others. 2024. In-context learning demonstration selection via influence analysis. arXiv preprint arXiv:2402.11750. — [arXiv:2402.11750](https://arxiv.org/abs/2402.11750) find
  24. Liang Wang, Nan Yang, and Furu Wei. 2024. Learning to retrieve in-context examples for large language models. In Proceedings of the 18th Conference of the European Chapter of the Association for Computational Linguistics (Volume 1: Long Papers), pages 1752–1767.
  25. Man Luo, Xin Xu, Zhuyun Dai, Panupong Pasupat, Mehran Kazemi, Chitta Baral, Vaiva Imbrasaite, and Vincent Y Zhao. 2023. Dr. icl: Demonstration-retrieved in-context learning. arXiv preprint arXiv:2305.14128. — [arXiv:2305.14128](https://arxiv.org/abs/2305.14128) find
  26. Xubin Wang, Jianfei Wu, Yichen Yuan, Deyu Cai, Mingzhe Li, and Weijia Jia. 2025. Demonstration selection for in-context learning via reinforcement learning. In Proceedings of the 42nd International Conference on Machine Learning. ICML. find
  27. Sewon Min, Mike Lewis, Luke Zettlemoyer, and Hannaneh Hajishirzi. 2022a. Metaicl: Learning to learn in context. In Proceedings of the 2022 conference of the North American chapter of the Association for Computational Linguistics: Human Language Technologies, pages 2791–2809. find
  28. Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc Le, Ed Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. 2022. Self-consistency improves chain of thought reasoning in language models. arXiv preprint arXiv:2203.11171.
  29. Sewon Min, Xinxi Lyu, Ari Holtzman, Mikel Artetxe, Mike Lewis, Hannaneh Hajishirzi, and Luke Zettlemoyer. 2022b. Rethinking the role of demonstrations: What makes in-context learning work? arXiv preprint arXiv:2202.12837.
  30. Alon Orlitsky, Ananda Theertha Suresh, and Yihong Wu. 2016. Optimal prediction of the number of unseen species. Proceedings of the National Academy of Sciences, 113(47):13283–13288. find
  31. Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yogatama, Maarten Bosma, Denny Zhou, Donald Metzler, and 1 others. 2022a. Emergent abilities of large language models. arXiv preprint arXiv:2206.07682.
  32. Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, and 1 others. 2022b. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824– 24837.
  33. Zhenyu Wu, Yaoxiang Wang, Jiacheng Ye, Zhiyong Wu, Jiangtao Feng, Jingjing Xu, and Yu Qiao. 2023a. Openicl: An open-source framework for in-context learning. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 3: System Demonstrations), pages 489–498. find
  34. Zhiyong Wu, Yaoxiang Wang, Jiacheng Ye, and Lingpeng Kong. 2023b. Self-adaptive in-context learning: An information compression perspective for in-context example selection and ordering. In Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers…
  35. Qwen An Yang, Baosong Yang, Beichen Zhang, Binyuan Hui, Bo Zheng, Bowen Yu, Chengyuan Li, Dayiheng Liu, Fei Huang, Guanting Dong, Haoran Wei, Huan Lin, Jian Yang, Jianhong Tu, Jianwei Zhang, Jianxin Yang, Jiaxin Yang, Jingren Zhou, Junyang Lin, and 25 others. 2024. Qwen2.5 technical report. ArXiv, a… find
  36. Zhao Yang, Yuanzhe Zhang, Dianbo Sui, Cao Liu, Jun Zhao, and Kang Liu. 2023. Representative demonstration selection for in-context learning with two-stage determinantal point process. In Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pages 5443–5456, Singapor… find
  37. Jiacheng Ye, Zhiyong Wu, Jiangtao Feng, Tao Yu, and Lingpeng Kong. 2023a. Compositional exemplars for in-context learning. In International Conference on Machine Learning, pages 39818–39833. PMLR.
  38. Xi Ye, Srinivasan Iyer, Asli Celikyilmaz, Veselin Stoyanov, Greg Durrett, and Ramakanth Pasunuru. 2023b. Complementary explanations for effective in-context learning. In Findings of the Association for Computational Linguistics: ACL 2023, pages 4469–4484.
  39. Changshuo Zhang, Ang Gao, Xiao Zhang, Yong Liu, and Deyang Li2 Fangchao Liu2 Xinyu Zhang. 2025. Reward mixology: Crafting hybrid signals for reinforcement learning driven in-context learning. In Findings of the Association for Computational Linguistics: EMNLP 2025, pages 4373–4383. find
  40. Zhuosheng Zhang, Aston Zhang, Mu Li, and Alex Smola. 2022. Automatic chain of thought prompting in large language models. In The eleventh international conference on learning representations.

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/xin-2026-ucs-estimating-unseen-coverage-improved/