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

1. Problem Statement

Large Language Models (LLMs) increasingly employ multi-step reasoning, generating sequences of intermediate claims that form implicit directed acyclic graphs (DAGs). In these structures, the correctness of a node (claim) is structurally conditioned on its ancestors; an error in an upstream claim can invalidate all downstream claims. This creates a scenario where factuality uncertainty is structural rather than a simple accumulation of independent node-wise errors.

Existing approaches to factuality control, such as Conformal Prediction (CP), are typically post-hoc. They generate a complete reasoning graph first and then prune or select subsets of claims to satisfy coverage guarantees. This approach has two critical limitations:

1. Structural Misalignment: Post-hoc pruning cannot influence the generation process itself, potentially leading to the generation of large amounts of invalid content before correction.
2. Inefficiency and Instability: Pruning fully generated graphs often results in overly conservative outputs (complete abstention) or unstable thresholds due to hallucination-induced noise.

The central question addressed by this paper is: Can we design inference-time conformal control for factuality that intervenes during generation, rather than post-hoc, while preserving rigorous coverage guarantees?

2. Methodology: Inference-Time Conformal Reasoning (ITCR)

The authors propose Inference-Time Conformal Reasoning (ITCR), a framework that integrates conformal prediction directly into the generation of reasoning graphs.

Core Components

1. Structure-Level Factuality Uncertainty Function:

   • Instead of relying solely on node-level scores, ITCR learns a function $F_{U_\theta}$ that maps an ancestor-closed reasoning subgraph and its constituent node-level uncertainty signals to a scalar graph-level factuality uncertainty score.
   • This function is trained via binary supervision (consistent vs. inconsistent with ground truth) on subgraphs. The learning of this function does not affect the theoretical validity of the coverage guarantees, which rely on conformal calibration.

2. Nested Non-Conformity Score:

   • To enable valid stopping during sequential generation, the non-conformity score $S(U)$ must satisfy a nested property: it must be monotone under subgraph expansion ($S(U_1) \le S(U_2) \le \dots$).
   • The authors define the score as:
     $$S(U) = 1 - \sigma(F_{U_\theta}(U, \{f_u(v)\}_{v \in V_U})) + \lambda |V_U|$$
     where $\sigma$ is the sigmoid function, $|V_U|$ is the number of nodes, and $\lambda$ is a penalty term.
   • The size penalty $\lambda |V_U|$ enforces monotonicity, ensuring that as the graph expands, the score increases (or stays the same), making the crossing of a calibrated threshold an irreversible stopping condition.

3. Inference Algorithm:

   • The generator incrementally expands the reasoning graph.
   • At each step, the non-conformity score of the current subgraph is computed.
   • If $S(U_t) \le \tau_\alpha$ (the calibrated threshold), generation continues.
   • If $S(U_t) > \tau_\alpha$, generation stops immediately, and the current ancestor-closed subgraph is returned as the final output.

Coverage Objectives

ITCR supports two distinct coverage targets, both guaranteed at level $1-\alpha$:

• No-False Coverage: Ensures the predicted subgraph contains no factually incorrect nodes (precision-oriented). This controls the false-positive rate.
• No-Miss Coverage: Ensures the predicted subgraph contains all factually correct nodes (recall-oriented). This allows for a limited number of uncertain nodes to avoid over-truncation of valid reasoning chains.

3. Key Contributions

1. Inference-Time Integration: The proposal of ITCR, which moves factuality control from a post-hoc selection problem to an inference-time generation mechanism.
2. Theoretical Guarantees: Proof that the proposed nested generation procedure induces valid conformal coverage guarantees for structured reasoning outputs under both No-False and No-Miss objectives.
3. Empirical Validation: Demonstration that ITCR achieves empirically valid coverage across multiple datasets (MATH, GSM8K, QA) and LLM backbones, while significantly improving reasoning accuracy compared to post-hoc methods.

4. Experimental Results

The paper evaluates ITCR on MATH, GSM8K, and a World Knowledge QA dataset using models including LLaMA-3.1-8B, Qwen3-4B, and DeepSeek-R1-Distill-Qwen-1.5B.

• Coverage Validity: ITCR consistently achieves empirical coverage rates that satisfy the target levels ($1-\alpha$) for both No-False and No-Miss objectives. In contrast, baseline methods (e.g., CPL, simple aggregation heuristics) often fail to meet coverage guarantees.
• Efficiency: ITCR achieves the highest efficiency (retaining more correct nodes or removing fewer correct nodes) among all methods that satisfy the coverage constraints.
• Downstream Performance: In downstream reasoning tasks, ITCR yields more accurate generations than post-hoc pruned graphs. Specifically, it improves the "correction gain" (Positive Correction Ratio minus Negative Correction Ratio) by an average of 18.77% across benchmarks.
• Computational Cost: ITCR reduces token consumption and runtime compared to post-hoc methods (PostCal) because it stops generation early rather than generating full trajectories and pruning them.
• Robustness: The method is robust to the choice of the underlying uncertainty function class (MLP, Random Forest, SVM) and prompt variations.

5. Significance and Claims

The paper claims that ITCR provides a statistically rigorous framework for controlling factuality in structured LLM reasoning. Its significance lies in:

• Bridging the Gap: It successfully integrates the flexibility of user-specified coverage guarantees (via CP) with the dynamic nature of autoregressive generation.
• Structural Awareness: By operating at the graph level rather than the node level, it respects the dependency structure of reasoning, acknowledging that upstream errors propagate.
• Practical Utility: The method not only guarantees validity but also improves the quality of reasoning by preventing the model from wasting compute on invalid paths and by enabling more effective self-correction.

The authors note limitations, specifically the reliance on the exchangeability assumption (calibration and test distributions must be similar) and the dependency on the accuracy of the initial graph construction and factuality verification. They suggest future work in localized calibration and adaptive penalties for non-exchangeable settings.