Conformal Language Model Reasoning with Coherent Factuality

Authors: Maxon Rubin-Toles, Maya Gambhir, Keshav Ramji, Aaron Roth, Surbhi Goel
Primary area: foundation or frontier models, including LLMs
Keywords: language models, reasoning, conformal prediction, factuality, graph representation, coherence

Abstract:
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.

Decision: accept (poster)
Reviewer scores: 6, 6, 6

Reviews and discussion:
<thread>
creation date:
1730247010611

thread_type:
official_review

<thread_object>
creator: reviewer_d79w

<content>
summary:
This work presents a conformal prediction framework for LLMs on reasoning tasks. The key difference between this work and previous work is the consideration of dependencies between claims. Unlike previous framework that scores and removes each claim independently, the proposed framework generates graph with each node representing a claim in the response, and then score and remove the claims while considering the graph structure. On MATH and FELM, the proposed method shows better calibration and stronger guarantee compared to previous methods and a few simpler baselines.

strengths:
1. Extending the conformal prediction framework to reasoning problems is an important direction. The idea of considering the dependency structure among the claims is straightforward and effective.
2. The proposed framework is simple to implement and shows stronger performance than baselines in the experiments.

weaknesses:
1. This writing of this paper can be substantially improved and in general should be more rigorous. There are a number of writing issue in this paper making this paper a bit hard to understand. To list a few:
    * One key property of the ideal graph is it uses the "minimal set of the claims". However, this is only mentioned in the appendix.
	* What is the "graph G" at LINE 350? Is it the corresponding subgraph to each node?
	* LINE 402 points to appendix F, but appendix F does not contain the prompts.
	* Figure 4(b) and 4(c) use the same title. This is confusing and seems to be typos.
	* What is "Descendants weight boosting" in LINE 501?
	* What is "independently filtered outputs" in LINE 509?
	* What is "self-consistency scoring" in LINE 970?
	* I don't understand the sentence from LINE 316-318.
	* The graph generation step is a critical part of the proposed method, but all the details are in the appendix. I can understand the specific prompt to be in the appendix, but there need to be some high-level descriptions in the main paper.
2. Reasoning problems are different from general fact-related questions as they often-times require a single correct conclusion. While it's still useful to provide partially correct responses, it is important in this case to also report (e.g., through human studies) how many of the responses actually contain the correct answer, or how useful these responses are after filtering.
3. The proposed method is only tested on one model (which I believe is GPT-4o, but the paper does not explicitly mention where the model responses on MATH come from). It would be great to test at least one more model to see how generalizable the proposed framework is. If the authors can use open-source models, it will also greatly improve the reproducibility of this paper.

questions:
1. Why do you use "median" in LINE 361? And how do you select the hyper-parameter $\beta$?
2. Do you make any special design to deal with the cases in LINE 153 (i.e., "it is not reasonable to do so in a proof of that fact")?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730444280525

thread_type:
official_review

<thread_object>
creator: reviewer_dftb

<content>
summary:
The paper defines “coherent factuality” and develops a conformal-predictionbased method to guarantee coherent factuality of language model outputs for reasoning tasks, where claims need to be substantiated and outputted in a comprehensible order to ensure correctness as well as coherence. In addition, they evaluate the method on MATH and FELM datasets, and verify the effectiveness of the method.

strengths:
Several recent works used conformal prediction to verify the correctness of the generation of LLMs with a strong assumption that the factuality of a claim can be independently evaluated. In order to generalize the method to reasoning domains, where claims need to be substantiated and outputted in a comprehensible order, the paper defines a new notion of factuality ”coherent factuality” and develops a conformal-predictionbased method to guarantee coherent factuality of language model outputs. The paper verified the proposed method on MATH and FELM datasets by comparing the results of the baseline proposed in (Mohri & Hashimoto, 2024).

weaknesses:
It is not clear how to create and use $C_{true}$ in the experiments on MATH and FELM datasets. The paper said in Line 150 “In practice, we might choose some reference like Wikipedia or a math textbook as our ground truth”, however, there is no statements about $C_{true}$ in the experiments.

The paper uses GPT4o to generate the graphs, but the quality of the graphs is unknown.

In addition, the proposed method can obtain both coherent factuality and independent factuality of the LLM output, however, there is no experiment to demonstrate whether there is an impact on the performance of downstream tasks. Or can the proposed method improve the performance of the downstream tasks?

questions:
see the weaknesses.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730696460515

thread_type:
official_review

<thread_object>
creator: reviewer_wbml

<content>
summary:
The paper defines “coherent factuality” of language model for reasoning tasks and applies a conformal prediction to guarantee coherent factuality. In addition to the split conformal prediction proposed by (Mohri & Hashimoto, 2024), this work proposes a deducibility graph by employing the “deducibility” property instead of “partial entailment” to take in claims by the ground truth. This criticizes that the previous work focuses solely on independent factuality, which makes the strong assumption that sub-claims are independent. Coherence factuality is applied to mathematical reasoning problems such as MATH or FELM, filtering the sub-graphs with the desired coherence factuality.

strengths:
This paper clearly points out that existing conformal factuality is not appropriate for reasoning tasks, and suggests deducibility graph and conformal prediction with coherence factuality. In addition, this experimentally achieved the desired correction and substantiation by applying conformal prediction to the newly defined coherence factuality.
This also proposes a claim-scoring function that considers the graph and reflects the confidence along descendants well.

weaknesses:
It seems to be sufficiently appealed that coherence factuality is more necessary for reasoning tasks than independent factuality. However, if bad claims, as mentioned in the sentence below, are accepted because they are consistent, wouldn't that be of no help in resolving hallucination? I think additional explanations about coherence factuality or deducibility more than as defined in the paper.
"Our definition of deducibility graphs permits the arbitrary treatment of claims that do not follow from the
ground truth".
Similarly, all qualitative results were drawn from the MATH dataset, which has only true claims as far as I know. It appears that additional qualitative results that include bad claims with coherence factuality are needed.

Additionally, an approximate deducibility graph is obtained by creating graph proxies using GPT-4o, but this does not provide theoretical guarantee, which is also mentioned in the paper. This paper said that these graph proxies provide a benefit in imposing the property called dependency, but as mentioned above, it does not come as a big advantage if bad claims are considered, so it appears that the theoretical guarantee of conformal prediction is not fully utilized.

questions:
As mentioned above, are there any results from experiments using a human annotated ideal graph other than GPT-4o?

Although it seems sufficiently argued that coherence factuality is more necessary than independent factuality for reasoning tasks, if bad claims are accepted because they are consistent how would this help in addressing hallucination issues?

Are there extra qualitative results for other datasets (e.g., FELM)?
</content>
</thread_object>

</thread>
<thread>
creation date:
1732239489554

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Response (Part 1/2)

comment:
We sincerely thank the reviewers for their valuable feedback, comments, suggestions, and questions. The concerns raised primarily surround the points of the practical utility of coherently factual outputs, the quality of the graph proxies generated by GPT-4o, how bad claims are handled, and how the ground truth is instantiated. We address each of these points below:

1. *Practical utility of coherently factual outputs*: Reviewers DfTB and D79W raise the question of whether the responses generated after filtering are useful, and can improve performance / correctness. In our work, we examined the utility of coherently factual outputs by re-prompting the model conditional on the outputs of our algorithm. This involves generating a coherently factual output through our subgraph filtering protocol (which constitutes a partial reasoning chain), and re-prompting the model to complete the reasoning chain (i.e. filling in any missing steps). The intuition driving this procedure is that a coherent response consisting of subclaims that are directly related to one another in the approximate deducibility graph is easier to complete than a non-coherent response consisting of disjoint claims. These are the results included in Table 1 of our work. Our findings reinforce the notion that while coherent factuality is stricter than independent factuality, our protocol does not result in correctness being sacrificed at the cost of coherence. In fact, it attains both a lower factuality error as well as higher claim retention relative to independent factuality; for $\\alpha = 0.05$, the factuality error was reduced to 0.10 with bootstrapping on coherently factual responses, as opposed to 0.26 when bootstrapping independently factual responses. This appears to validate our hypothesis on coherently factual responses being more amenable to completion by re-prompting. We have included the methodology behind this bootstrapping method in Appendix I. 

2. *Quality of the graph proxies*: As reviewers wbML and DfTB note, our work relies on GPT-4o to produce proxy graphs for reasoning problems, though they may be of seemingly unknown quality. First, we note that the conformal lower bound is independent of graph quality and only requires data exchangeability. However, low quality graphs might harm claim retention. To measure the quality of our GPT graph proxies, we manually construct “ideal” graphs for the first ten problems in MATH, such that we have gold (human-annotated) and silver (model-generated) graphs for those samples. To determine proxy-ideal similarity, we compute edit distance. The edit distance from GPT proxies to the ideal deducibility graph was on average 1.8; the edit distance to any approximate deducibility graph was 0 (meaning each graph considered satisfied Definition 4, which is all that is necessary for both bounds to hold). Both methods were calibrated, so coherent factuality was approximately the target $1 - \\alpha$ in either case. Thus, we only include retention results in this table. Note that 1.0 because the baseline accuracy here was 70% (no filtering needed at $\\alpha = 0.3$)


| $\\alpha$ | Claim Retention (Human-Generated Graphs) | Claim Retention (GPT-Generated Graphs) |
| --------- | ---------------------------------------- | -------------------------------------- |
| 0.1       | 0.33                                     | 0.33                                   |
| 0.2       | 0.74                                     | 0.86                                   |
| 0.3       | 1.0                                      | 1.0                                    |


The plots of the results which include the realized coherent factuality for each of these settings are in Appendix F. As noted above, the graph quality is not necessary to obtain the lower bound in Theorem 1, and this is supported by our calibration plots. Nonetheless, we have empirical evidence that the graphs are high-quality -- in fact, as observed through the table above and the plots in Appendix F, they outperform human-annotated ideal graphs (albeit for a small number of samples). This is likely due to the model-generated graphs capturing dependency, which in practice refers to how prior claims are considered in producing subsequent ones, and the non-minimal nature of approximate deducibility graphs. Further evidence of our graphs’ quality is the fact that silver calibration (which assumes validity of the deducibility graph) yields effective gold validation (which does not depend on graph validity).
</content>
</thread_object>

</thread>
<thread>
creation date:
1732239867959

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
General Response (Part 2/2)

comment:
3. *Handling of bad claims*: The inclusion of bad claims in the approximate deducibility graph or such claims receiving a high self-consistency score is not a concern because our calibration algorithm ensures that only claims that meet calibrated thresholds over self-consistency score as well as the graphical definition of coherence are included in the final output. Our algorithm dynamically adjusts the threshold to filter out claims with lower scores, such that only those with a high probability of being factual remain. If bad claims are highly self-consistent, the threshold would rise accordingly, imposing stricter conditions for any one claim to be included in the output. Additionally, subgraphs containing bad claims are effectively excluded because their scores, influenced by the bad claims, are likely to fall below the threshold with high probability. This combination of score-based filtering and the representation of dependencies guarantees that the final output maintains correctness and coherence, regardless of the initial presence or consistency of bad claims.

4. *Instantiation of ground truth*: With regards to the use of the ground truth (subset of claims we assume to be valid, denoted $C_{true}$) -- notably, our algorithm does not directly require knowledge of $C_{true}$ or a complete fixed instantiation of the ground truth in practice. Our guarantees do depend on the quality of annotations in the calibration set, which are with respect to $C_{true}$. To this effect, in the annotation phase, we relied on the annotators’ understanding of the required prior knowledge and the given context of the problem to serve as a reasonable proxy, as in Mohri and Hashimoto, 2024; for math problems, however, we reasonably assume that the annotators’ conceptions will be uniform, with similar levels of mathematical knowledge and similar conceptions of mathematical substantiation. 


### Update to Paper
We have made the following updates to our paper in the revised draft based on the valuable feedback of the reviewers; our paper has been uploaded above (changes are visible in teal):
* A clarification of the minimal set of claims, in Section 3.1. 
* An explanation of the self-consistency scoring function used in practice, in Section 4.
* Added experiments with Llama-3.1-70-Instruct, an open-source model, in Appendix E, and clarified that responses were generated from GPT-4 in the experiments included in the main text.
* Updated Table 1 and R5 in Section 5 to address the iterative application of our algorithm and its implications in boosting correctness and the utility of outputs. 
* An analysis of claim retention using ten human-annotated “ideal” deducibility graphs, as opposed to using ten GPT-4o-generated “approximate” deducibility graphs, in Appendix F.
* Added our cost estimates to Appendix J, for reproducibility.
* Added example outputs from FELM to Appendix L.2, comparing the behavior of independent factuality and coherent factuality.
</content>
</thread_object>

</thread>


Metareview:
metareview:
The paper introduces a conformal prediction framework tailored for reasoning tasks in LMs. It addresses limitations of prior methods by proposing "coherent factuality," capturing correctness across interconnected claims rather than independently evaluating them. The methodology employs deducibility graphs, combining graph-based claim scoring with a split conformal prediction approach. Experiments on the MATH and FELM datasets demonstrate the method's ability to improve factuality retention while maintaining high correctness.

*Strengths*:  
-The paper proposes an innovative "coherent factuality" approach, extending conformal prediction frameworks to reasoning tasks, which have unique dependencies.  
-The method achieves substantial improvements in correctness without sacrificing coherence.  
-The framework is adaptable to multiple language models, including open-source options like Llama.  
-It examines the quality of deducibility graphs, compares proxy and human-annotated graphs, and validates its calibration guarantees.  

*Weaknesses*:  
-Reviewers raised concerns about inconsistent terminology and unclear descriptions, although these were addressed in the revised version.  
-Several reviewers noted issues regarding how the "ground truth" was instantiated in the experiments.  
-There were limited direct evaluations of how filtering outputs impacts the utility in solving full reasoning problems.  
-Potential for accepting bad (incorrect) claims just because they are consistent with the rest of the claims.  
-Reliance on GPT-generated graphs without a formal guarantee was noted as a limitation, albeit mitigated by empirical validation.

While reviewers all indicated marginally above acceptance rate, none expressed strong enthusiasm for the work. This may have been driven more by the paper's solid technical contributions and execution than by its ability to excite or inspire transformative potential. While the authors added experiments with Llama, reviewers might still find the limited dataset scope (MATH and FELM) and absence of additional task types a concern.