This paper addresses the challenge of quantifying uncertainty in automatically generated text, particularly in natural language generation (NLG) tasks such as machine translation (MT) and language modeling (LM). Conformal prediction, a framework that provides statistical guarantees on prediction sets, is adapted to handle non-i.i.d. data in NLG, which is a significant limitation for its application in these tasks. The authors introduce non-exchangeable conformal nucleus sampling, a novel extension of conformal prediction that leverages nearest neighbor search to dynamically generate calibration sets during inference. This method ensures statistical coverage guarantees while producing tighter and more relevant prediction sets compared to existing sampling techniques. The contributions of the paper include: 1. Presenting a novel technique based on non-exchangeable conformal prediction for NLG, which is the first of its kind. 2. Validating the effectiveness of the method in MT and LM tasks, showing competitive or superior performance in terms of generation quality while maintaining tighter prediction sets and better coverage. 3. Demonstrating that the method maintains coverage under distributional shift, where the model's latent representations are corrupted. 4. Publishing the code for the project in an open-source repository. The paper also discusses related work, background on conformal prediction and non-exchangeable conformal prediction, and experimental results that demonstrate the method's performance and robustness. The authors conclude by highlighting the potential of their approach to provide a more principled way to perform sampling with conformal guarantees in NLG tasks.This paper addresses the challenge of quantifying uncertainty in automatically generated text, particularly in natural language generation (NLG) tasks such as machine translation (MT) and language modeling (LM). Conformal prediction, a framework that provides statistical guarantees on prediction sets, is adapted to handle non-i.i.d. data in NLG, which is a significant limitation for its application in these tasks. The authors introduce non-exchangeable conformal nucleus sampling, a novel extension of conformal prediction that leverages nearest neighbor search to dynamically generate calibration sets during inference. This method ensures statistical coverage guarantees while producing tighter and more relevant prediction sets compared to existing sampling techniques. The contributions of the paper include: 1. Presenting a novel technique based on non-exchangeable conformal prediction for NLG, which is the first of its kind. 2. Validating the effectiveness of the method in MT and LM tasks, showing competitive or superior performance in terms of generation quality while maintaining tighter prediction sets and better coverage. 3. Demonstrating that the method maintains coverage under distributional shift, where the model's latent representations are corrupted. 4. Publishing the code for the project in an open-source repository. The paper also discusses related work, background on conformal prediction and non-exchangeable conformal prediction, and experimental results that demonstrate the method's performance and robustness. The authors conclude by highlighting the potential of their approach to provide a more principled way to perform sampling with conformal guarantees in NLG tasks.