# Non-Exchangeable Conformal Language Generation with Nearest Neighbors

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

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 55 of its 98 references that are in the map.
- First posted on arXiv 1 Feb 2024.

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

- [LLaMA: Open and Efficient Foundation Language Models](https://mlsanity.com/paper/2302.13971/) (2023)
- [BERTScore: Evaluating Text Generation with BERT](https://mlsanity.com/paper/1904.09675/) (2019)
- [On Calibration of Modern Neural Networks](https://mlsanity.com/paper/1706.04599/) (2017)
- [Dropout as a Bayesian Approximation: Representing Model Uncertainty in Deep Learning](https://mlsanity.com/paper/1506.02142/) (2015)
- [OPT: Open Pre-trained Transformer Language Models](https://mlsanity.com/paper/2205.01068/) (2022)
- [The Curious Case of Neural Text Degeneration](https://mlsanity.com/paper/1904.09751/) (2019)
- [Benchmarking Neural Network Robustness to Common Corruptions and Perturbations](https://mlsanity.com/paper/1903.12261/) (2019)
- [Billion-scale similarity search with GPUs](https://mlsanity.com/paper/1702.08734/) (2017)
- [BLOOM: A 176B-Parameter Open-Access Multilingual Language Model](https://mlsanity.com/paper/2211.05100/) (2022)
- [Language Models (Mostly) Know What They Know](https://mlsanity.com/paper/2207.05221/) (2022)
- [Can You Trust Your Model's Uncertainty? Evaluating Predictive Uncertainty Under Dataset Shift](https://mlsanity.com/paper/1906.02530/) (2019)
- [Hierarchical Neural Story Generation](https://mlsanity.com/paper/1805.04833/) (2018)
- [COMET: A Neural Framework for MT Evaluation](https://mlsanity.com/paper/2009.09025/) (2020)
- [Generalization through Memorization: Nearest Neighbor Language Models](https://mlsanity.com/paper/1911.00172/) (2019)
- [A Gentle Introduction to Conformal Prediction and Distribution-Free Uncertainty Quantification](https://mlsanity.com/paper/2107.07511/) (2021)
- [Teaching Models to Express Their Uncertainty in Words](https://mlsanity.com/paper/2205.14334/) (2022)
- [Beyond English-Centric Multilingual Machine Translation](https://mlsanity.com/paper/2010.11125/) (2020)
- [Datasets: A Community Library for Natural Language Processing](https://mlsanity.com/paper/2109.02846/) (2021)
- [Quantifying the Carbon Emissions of Machine Learning](https://mlsanity.com/paper/1910.09700/) (2019)
- [Conformal Prediction Under Covariate Shift](https://mlsanity.com/paper/1904.06019/) (2019)
- [MAUVE: Measuring the Gap Between Neural Text and Human Text using Divergence Frontiers](https://mlsanity.com/paper/2102.01454/) (2021)
- [Classification with Valid and Adaptive Coverage](https://mlsanity.com/paper/2006.02544/) (2020)
- [Uncertainty Sets for Image Classifiers using Conformal Prediction](https://mlsanity.com/paper/2009.14193/) (2020)
- [Robots That Ask For Help: Uncertainty Alignment for Large Language Model Planners](https://mlsanity.com/paper/2307.01928/) (2023)
- [Nearest Neighbor Machine Translation](https://mlsanity.com/paper/2010.00710/) (2020)
- [Conformal Prediction with Large Language Models for Multi-Choice Question Answering](https://mlsanity.com/paper/2305.18404/) (2023)
- [Is MAP Decoding All You Need? The Inadequacy of the Mode in Neural Machine Translation](https://mlsanity.com/paper/2005.10283/) (2020)
- [Learning to Write with Cooperative Discriminators](https://mlsanity.com/paper/1805.06087/) (2018)
- [Localized Conformal Prediction: A Generalized Inference Framework for Conformal Prediction](https://mlsanity.com/paper/2106.08460/) (2021)
- [Efficient Nearest Neighbor Language Models](https://mlsanity.com/paper/2109.04212/) (2021)

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

- [Language Models with Conformal Factuality Guarantees](https://mlsanity.com/paper/2402.10978/) (2024)
- [Conformal Alignment: Knowing When to Trust Foundation Models with Guarantees](https://mlsanity.com/paper/2405.10301/) (2024)
- [Conformal Prediction for Natural Language Processing: A Survey](https://mlsanity.com/paper/2405.01976/) (2024)
- [Conformal Prediction: A Data Perspective](https://mlsanity.com/paper/2410.06494/) (2024)
- [Prune 'n Predict: Optimizing LLM Decision-making with Conformal Prediction](https://mlsanity.com/paper/2501.00555/) (2024)
- [Conformal Generative Modeling with Improved Sample Efficiency through Sequential Greedy Filtering](https://mlsanity.com/paper/2410.01660/) (2024)
- [Entropy Alone is Insufficient for Safe Selective Prediction in LLMs](https://mlsanity.com/paper/2603.21172/) (2026)
- [Conformal Prediction Beyond the Seen: A Missing Mass Perspective for Uncertainty Quantification in Generative Models](https://mlsanity.com/paper/2506.05497/) (2025)
- [Domain-Shift-Aware Conformal Prediction for Large Language Models](https://mlsanity.com/paper/2510.05566/) (2025)
- [Uncertainty Quantification on Graph Learning: A Survey](https://mlsanity.com/paper/2404.14642/) (2024)
- [Comparing Uncertainty Measurement and Mitigation Methods for Large Language Models: A Systematic Review](https://mlsanity.com/paper/2504.18346/) (2025)
- [Statistical Methods in Generative AI](https://mlsanity.com/paper/2509.07054/) (2025)
- [Calibrated Large Language Models for Binary Question Answering](https://mlsanity.com/paper/2407.01122/) (2024)
- [A Collaborative Content Moderation Framework for Toxicity Detection based on Conformalized Estimates of Annotation Disagreement](https://mlsanity.com/paper/2411.04090/) (2024)
- [Conformal Certification of Reasoning Trace Prefixes](https://mlsanity.com/paper/2605.30085/) (2026)
- [Does Compression Preserve Uncertainty? A Unified Benchmark for Quantized and Sparse LLMs via Conformal Prediction](https://mlsanity.com/paper/2606.01850/) (2026)
- [ConfHit: Conformal Generative Design with Oracle Free Guarantees](https://mlsanity.com/paper/2603.07371/) (2026)
- [Strategic Decision Support for AI Agents](https://mlsanity.com/paper/2606.12587/) (2026)
- [Conformalized Large Language Models under Configuration Shift](https://mlsanity.com/paper/2608.01460/) (2026)
- [Directional Concentration Uncertainty: A representational approach to uncertainty quantification for generative models](https://mlsanity.com/paper/2602.13264/) (2026)
- [Uncertainty quantification for trustworthy deep learning: Methods and measures](https://mlsanity.com/paper/2607.28248/) (2026)

## Abstract (arXiv)

Quantifying uncertainty in automatically generated text is important for letting humans check potential hallucinations and making systems more reliable. Conformal prediction is an attractive framework to provide predictions imbued with statistical guarantees, however, its application to text generation is challenging since any i.i.d. assumptions are not realistic. In this paper, we bridge this gap by leveraging recent results on non-exchangeable conformal prediction, which still ensures bounds on coverage. The result, non-exchangeable conformal nucleus sampling, is a novel extension of the conformal prediction framework to generation based on nearest neighbors. Our method can be used post-hoc for an arbitrary model without extra training and supplies token-level, calibrated prediction sets equipped with statistical guarantees. Experiments in machine translation and language modeling show encouraging results in generation quality. By also producing tighter prediction sets with good coverage, we thus give a more theoretically principled way to perform sampling with conformal guarantees.