# Conformal Language Model Reasoning with Coherent Factuality

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

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 31 of its 46 references that are in the map.
- First posted on arXiv 21 May 2025.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)

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

- [Self-Consistency Improves Chain of Thought Reasoning in Language Models](https://mlsanity.com/paper/2203.11171/) (2022)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [A Survey on Hallucination in Large Language Models: Principles, Taxonomy, Challenges, and Open Questions](https://mlsanity.com/paper/2311.05232/) (2023)
- [Can LLMs Express Their Uncertainty? An Empirical Evaluation of Confidence Elicitation in LLMs](https://mlsanity.com/paper/2306.13063/) (2023)
- [Show Your Work: Scratchpads for Intermediate Computation with Language Models](https://mlsanity.com/paper/2112.00114/) (2021)
- [Semantic Uncertainty: Linguistic Invariances for Uncertainty Estimation in Natural Language Generation](https://mlsanity.com/paper/2302.09664/) (2023)
- [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)
- [Conformalized Quantile Regression](https://mlsanity.com/paper/1905.03222/) (2019)
- [How Can We Know When Language Models Know? On the Calibration of Language Models for Question Answering](https://mlsanity.com/paper/2012.00955/) (2020)
- [Chain-of-Verification Reduces Hallucination in Large Language Models](https://mlsanity.com/paper/2309.11495/) (2023)
- [How Language Model Hallucinations Can Snowball](https://mlsanity.com/paper/2305.13534/) (2023)
- [Conformal Risk Control](https://mlsanity.com/paper/2208.02814/) (2022)
- [Survey on Factuality in Large Language Models: Knowledge, Retrieval and Domain-Specificity](https://mlsanity.com/paper/2310.07521/) (2023)
- [Universal Self-Consistency for Large Language Model Generation](https://mlsanity.com/paper/2311.17311/) (2023)
- [Conformal Language Modeling](https://mlsanity.com/paper/2306.10193/) (2023)
- [Conformal Prediction with Large Language Models for Multi-Choice Question Answering](https://mlsanity.com/paper/2305.18404/) (2023)
- [Language Models with Conformal Factuality Guarantees](https://mlsanity.com/paper/2402.10978/) (2024)
- [Quantifying Uncertainty in Answers from any Language Model and Enhancing their Trustworthiness](https://mlsanity.com/paper/2308.16175/) (2023)
- [Question Decomposition Improves the Faithfulness of Model-Generated Reasoning](https://mlsanity.com/paper/2307.11768/) (2023)
- [Let's reward step by step: Step-Level reward model as the Navigators for Reasoning](https://mlsanity.com/paper/2310.10080/) (2023)
- [Large language model validity via enhanced conformal prediction methods](https://mlsanity.com/paper/2406.09714/) (2024)
- [Prover-Verifier Games improve legibility of LLM outputs](https://mlsanity.com/paper/2407.13692/) (2024)
- [FELM: Benchmarking Factuality Evaluation of Large Language Models](https://mlsanity.com/paper/2310.00741/) (2023)
- [Linguistic Calibration of Long-Form Generations](https://mlsanity.com/paper/2404.00474/) (2024)
- [Distinguishing the Knowable from the Unknowable with Language Models](https://mlsanity.com/paper/2402.03563/) (2024)
- [Multicalibration for Confidence Scoring in LLMs](https://mlsanity.com/paper/2404.04689/) (2024)
- [Llamas Know What GPTs Don't Show: Surrogate Models for Confidence Estimation](https://mlsanity.com/paper/2311.08877/) (2023)
- [Multi-group Uncertainty Quantification for Long-form Text Generation](https://mlsanity.com/paper/2407.21057/) (2024)

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

- [Adaptive Stopping for Multi-Turn LLM Reasoning](https://mlsanity.com/paper/2604.01413/) (2026)
- [Conformal Prediction Beyond the Seen: A Missing Mass Perspective for Uncertainty Quantification in Generative Models](https://mlsanity.com/paper/2506.05497/) (2025)
- [Document Summarization with Conformal Importance Guarantees](https://mlsanity.com/paper/2509.20461/) (2025)
- [Online Reasoning Calibration: Test-Time Training Enables Generalizable Conformal LLM Reasoning](https://mlsanity.com/paper/2604.01170/) (2026)
- [Robust Uncertainty Quantification for Self-Evolving Large Language Models via Continual Domain Pretraining](https://mlsanity.com/paper/2510.22931/) (2025)
- [E-Scores for (In)Correctness Assessment of Generative Model Outputs](https://mlsanity.com/paper/2510.25770/) (2025)
- [Inference-time Unlearning Using Conformal Prediction](https://mlsanity.com/paper/2602.03787/) (2026)
- [PseudoAct: Leveraging Pseudocode Synthesis for Flexible Planning and Action Control in Large Language Model Agents](https://mlsanity.com/paper/2602.23668/) (2026)
- [Conformal Certification of Reasoning Trace Prefixes](https://mlsanity.com/paper/2605.30085/) (2026)
- [Pause and Reflect: Conformal Aggregation for Chain-of-Thought Reasoning](https://mlsanity.com/paper/2605.14098/) (2026)
- [Conformal Language Modeling via Posterior Sampling](https://mlsanity.com/paper/2606.03731/) (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)
- [Though Language Models Err While They Strive: Conformal Prediction for Self-Correcting Scientific Generation](https://mlsanity.com/paper/2607.16704/) (2026)

## Abstract (arXiv)

Language models are increasingly being used in important decision pipelines, so ensuring the correctness of their outputs is crucial. Recent work has proposed evaluating the "factuality" of claims decomposed from a language model generation and applying conformal prediction techniques to filter out those claims that are not factual. This can be effective for tasks such as information retrieval, where constituent claims may be evaluated in isolation for factuality, but is not appropriate for reasoning tasks, as steps of a logical argument can be evaluated for correctness only within the context of the claims that precede them. To capture this, we define "coherent factuality" and develop a conformal-prediction-based method to guarantee coherent factuality for language model outputs. Our approach applies split conformal prediction to subgraphs within a "deducibility" graph" that represents the steps of a reasoning problem. We evaluate our method on mathematical reasoning problems from the MATH and FELM datasets and find that our algorithm consistently produces correct and substantiated orderings of claims, achieving coherent factuality across target coverage levels. Moreover, we achieve 90% factuality on our stricter definition while retaining 80% or more of the original claims, highlighting the utility of our deducibility-graph-guided approach.