Inference-Time Conformal Reasoning with Valid Factuality Control for Large Language Models

Large language models (LLMs) increasingly perform multi-step reasoning, where intermediate claims form implicit directed acyclic graphs whose node correctness is structurally conditioned on their ancestors. This makes factuality uncertainty structural, rather than a trivial accumulation of node-wise errors, and necessitates inference-time uncertainty quantification over the reasoning structure. While conformal prediction (CP) offers flexible user-specified factuality control, existing work remains post-hoc and cannot intervene during generation. To fill the gap between CP’s flexibility and its post-hoc limitation, we propose an Inference-Time Conformal Reasoning (ITCR) framework that integrates CP directly into reasoning graph generation. ITCR learns a structure-level factuality uncertainty function that aggregates claim-level factuality signals over reasoning graphs without complex modeling assumptions. We then design the non-conformity score based on graph-level factuality uncertainty and calibrate the conformal threshold to decide when to stop generation. We theoretically show such generation is nested, yielding valid coverage guarantees for factuality control. Experiments over multiple datasets and coverage objectives demonstrate empirically valid coverage. In downstream reasoning tasks, inference-time calibrated graphs yield more accurate generation than post-hoc pruned graphs.

Large language models often generate reasoning as a chain of intermediate steps, but they lack a reliable way to decide whether an earlier step should be trusted before continuing. This is problematic because a single unreliable intermediate conclusion can propagate through the rest of the reasoning process and lead to an incorrect final answer. Our research asks how to estimate and control the uncertainty of LLM during the reasoning step generation, rather than only judging the final output. We introduce a conformal prediction-based framework that provides the trustworthiness of each intermediate reasoning step, enabling LLMs to decide when to continue generating and when to stop and rethink. Our method evaluates both the local correctness of a step and its logical coherence with prior steps, and it provides a principled trade-off between factual accuracy and uncertainty. This work offers a practical mechanism for monitoring and intervening in LLM reasoning processes. Instead of treating reasoning as an opaque generated sequence, our method provides a way to test, calibrate, and control uncertainty during generation, making LLM reasoning more reliable and transparent.