Conformal Language Model Reasoning with Coherent Factuality

Weakness 3

The responses in our experiments are generated from GPT-4, with the proxy graphs being generated from GPT-4o. We have now made explicit mention of this in Section 5, and have produced results with Llama-3.1-70B-Instruct, given the reviewer’s helpful feedback on reproducibility with open-source models. These results are included in Appendix E of our revision.

Our silver-calibrated, validated results were similar to those for GPT. Both conformal bounds were satisfied in the calibration experiment (see Figure 6a). We retain a competitive percentage of claims relative to independent factuality (see below), despite a stricter definition, while attaining an empirical factuality coverage close to the target rate.

We are currently working on validating these results with respect to gold-annotations, which requires more annotations. We will add these to the camera-ready version.

To further aid with the reproducibility of our approach, we have also included the following cost estimates for generating proxy graphs and producing responses, and included them in Appendix J of our revised paper. For each example in the calibration and test set, the algorithm requires 8 queries comprising at most 16k tokens; for our calibration set of 50 examples, this cost in total less than $\\$5.00$using GPT and less than$\$0.70$ using Llama; the same queries are made for the test set, so each test example cost less than $\\$0.10$for GPT and$\$0.01$ for Llama. These estimates are conservative, assuming full utilization of 2000-token total context and output to accommodate longer response lengths (although our responses were much shorter).

Question 1:

Why do you use “median” in LINE 361? And how do you select the hyper-parameter?

We explored several similar graph-sensitive scoring mechanisms, each motivated by weighting the risk score of a node according to the risk scores of its ancestors and/or descendants. This median version seemed most robust in performance to small changes in beta (we speculate this is because the median is not sensitive to outlier scores). We swept beta values in [0, 1] and chose 0.5 for its good performance. This information is now included in the scoring section as a footnote.

Question 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”)?

As our algorithm does not depend on a complete practical instantiation of the ground truth $C_{true}$, this is addressed during annotation on the basis of human understanding of the annotator’s understanding of the priors necessary to solve a given problem (e.g. the math axioms) and interpretation of the given context. This serves as a reasonable proxy, following from prior works such as Mohri and Hashimoto, 2024.

We hope that our response and revised paper addresses your concerns and questions. Please let us know if you have any further questions, and we would be happy to answer them!

We thank Reviewer D79W for taking the time to review our paper, and for their helpful suggestions. We address the points raised in the review below:

Weakness 1

Thank you for the suggestions on writing-related revisions! We have incorporated this feedback into our revised version, which we hope clarifies some terminology that was unclear before and addresses the concerns raised.

One key property of the ideal graph is it uses the “minimal set of the claims”. However, this is only mentioned in the appendix.

We have updated the main text to include a note on the minimal set of claims.

What is the “graph G” at LINE 350? Is it the corresponding subgraph to each node?

Graph G refers to the approximate deducibility graph as defined in Definition 4, whose subgraphs we examine.

LINE 402 points to Appendix F, but appendix F does not contain the prompts.

Thank you for pointing this out -- this has been corrected to point to Appendix K, which does contain the prompts.

Figure 4(b) and 4(c) use the same title. This is confusing and seems to be typos.

Thank you for bringing this to our attention -- we’ve corrected this in the revised version.

What is “Descendants weight boosting” in LINE 501?

“Descendants weight boosting” refers to the “Descendant Weighting” scoring function introduced in Section 4. We have reworded this accordingly in line 503 of our revised paper.

What is “independently filtered outputs” in LINE 509?

“Independently filtered outputs” refers to the application of Mohri and Hashimoto, 2024’s method of treating claims as independent of one another, which we termed “independent factuality”.

What is “self-consistency scoring” in LINE 970?

Self-consistency scoring is a frequency score measure introduced in Mohri and Hashimoto, 2024, wherein several (e.g. 5) additional responses are sampled from the model for a given prompt. For each generation, the model determines whether the claim supports, contradicts, or is independent of the target claim, assigning +1, -1, or 0 to that output, and yielding a score for the target claim in [-5, 5]. We include a similar description of this approach in Section 4, in the discussion about the scoring functions used in our algorithm.

I don't understand the sentence from LINE 316-318.

This sentence refers to the notion that GPT-4o-generated approximate deducibility graphs may not be minimal, and since we simply require them to have sufficient substantiation sets, they are constructed in such a manner that they may contain more edges than would be needed in the ideal deducibility graph.

Weakness 2

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.

We examine 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). These results are in Table 1 of our work, which shows that these outputs can be made iteratively more useful by reducing the factuality error. That us, this bootstrapping method of filtering with our protocol and re-prompting is more effective for coherent factuality than it is for independently factual outputs; for example, with $\\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.

We thank Reviewer DfTB for taking the time to review our paper, and for their positive review. Please see below for our responses to the reviewer’s feedback:

​​It is not clear how to create and use $C_{true}$ in the experiments on MATH and FELM datasets.

Notably, our algorithm does not directly require knowledge of $C_{true}$ or a complete fixed instantiation of the ground truth in practice, although our guarantees depend on the quality of annotations in the calibration set, which are with respect to $C_{true}$. 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 [1]; for math problems, however, we can reasonably believe that the annotators’ conceptions will be uniform, with similar levels of mathematical knowledge and depth.

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

We examined the quality of these graphs against ideal human-annotated graphs; the following is repeated from the general response: We compare human-annotated ideal graphs for the first ten examples against the GPT-4o-generated graphs for the same samples. The edit distance to the ideal deducibility graph was on average 1.8; the edit distance to an 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$)

The plots of the results which include the realized coherent factuality for each of these settings are in Appendix F.

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?

Our results in Table 1 by re-prompting to condition on the previous coherently factual output and fill in the remainder of the reasoning chain addresses the practical viability of our method in yielding useful responses. The motivation for this is that a coherent response is easier to complete than a non-coherent response. Notably, this approach results in decreased factuality error, showing that our empirically achieved factuality does improve via re-prompting and reinforcing our hypothesis; 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.

References

[1] Christopher Mohri and Tatsunori Hashimoto, “Language Models with Conformal Factuality Guarantees.” arXiv preprint, arXiv:2402.10978 (2024).

We hope that these responses address your concerns. Please let us know if you have any further questions!

Thank you for your feedback! You raise a good point: in addition to the factuality of outputs, their downstream utility is important. It is first important to note that the primary aim of this work is to detect and filter hallucinations at a calibrated rate while preserving reasoning integrity. We do not consider augmented prompting of the original output (in line with Mohri and Hashimoto, 2024 [1]), so this method does not allow a model to solve a problem it previously couldn’t solve. However, this framework considers outputs from an arbitrary model, so it can be appended to any existing augmented prompting strategy in order to guarantee factual and coherent outputs.

It is still important that we compete with the utility of filtering baselines. We compare the downstream utility of our method with the baseline according to two metrics: legibility of outputs (how transparently true/false they appear) and the rate at which outputs contain a correct answer.

For fixed levels of factuality, our method’s outputs are more legible than baseline filtered outputs. Legibility (Kirchner et al. 2024 [2]) is the ability of observers to understand and spot errors in an output, so legible outputs are either plainly correct or plainly incorrect, and downstream users can confidently decide when to use them.

We defer human legibility studies to future work, but as a proxy, we asked GPT-4o and Llama-3.1-70B-Instruct to “grade” filtered outputs (original, not re-prompted) as either correct or erroneous (more details in footnote). For each combination of output generation method (GPT, Llama) and output grading method (GPT, Llama), our method was more legible than the baseline (lower false positive and false negative rates for fixed levels of factuality). The task was error detection, so, e.g., “false positive” means GPT graded an output as containing an error when it didn’t.

1) GPT-4 outputs, GPT-4o as judge:

a) Ours

b) Baseline

2) GPT-4 outputs, Llama-3.1-70B-Instruct as judge:

a) Ours

b) Baseline

3) Llama-3.1-70B-Instruct outputs, GPT-4o as judge:

a) Ours

b) Baseline

4) Llama-3.1-70B-Instruct outputs, Llama-3.1-70B-Instruct as judge:

a) Ours

b) Baseline

Of course, it is still important that filtered outputs contain the correct answer. We manually checked all GPT outputs filtered by our method and the baseline at $\\alpha = 0.1$. Of hallucination-free outputs, 64% contained the correct final answer, the same rate as the (coherence-free, less legible) baseline. Note that some were examples on which GPT’s hallucinated solution had been filtered out, and so filtering had no chance of outputting a correct solution.

For several outputs which technically did not contain the final answer, computing the answer based on the output’s last step was trivial (e.g., completing a sum or choosing between a positive and negative solution). Our filtered outputs preserve coherence to scaffold users toward correct conclusions while controlling for hallucinations. Our approach improves upon the coherence and legibility of the baseline while retaining its output completeness as measured by percent of claims retained and proportion of outputs with correct final answers.

Footnote (Legibility Details): All queries at temp. = 0. We considered all outputs across $\\alpha = 0.1, 0.15, 0.2$ for which (1) our method and the baseline produced different, non-empty outputs and (2) both outputs had the same independent factuality (both contained a hallucination or both didn't).

[1] Christopher Mohri and Tatsunori Hashimoto, “Language Models with Conformal Factuality Guarantees.” arXiv preprint, arXiv:2402.10978 (2024).

[2] Jan Kirchner et al. “Prover-Verifier Games improve legibility of LLM outputs”. arXiv preprint, arXiv: 2407:13692 (2024).

Qualitative Examples

Are there extra qualitative results for other datasets (e.g., FELM)? Yes, we include a qualitative example from FELM below, as well as a few more in Appendix L.2 of the revised version of our paper.

Question: Jessica makes $\\$2,000.00$a month. She sets 25\% of her paycheck aside to put towards fancy shoes. Each pair of shoes she buys costs$\$1,000.00$. How many shoes can she buy in a year?

Independent Factuality: Jessica sets aside 25% of her paycheck, which is: $\\$2,000.00$x 0.25 =$\$500.00$ So Jessica can buy 6 pairs of shoes in a year with the money she sets aside from her paycheck.

Coherent Factuality: Jessica sets aside 25% of her paycheck, which is: $\\$2,000.00$x 0.25 =$\$500.00$ To figure out how many pairs of shoes she can buy in a year, we need to multiply the number of pairs she can buy in a month by 12 (the number of months in a year):$\\$500.00$x 12 =$\$6,000.00$.

We hope that this addresses the points raised in the review, and we would be happy to address any concerns that remain!

We thank Reviewer wbML for taking the time to review our paper and for their feedback. We address each of the stated weaknesses below and in our revised draft.

Handling Bad Claims

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?... 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?

In our calibration algorithm, we consider the lowest score we can filter possible outputs on while still having coherently factual outputs a large proportion of the time. Thus, if bad claims are often consistent, with a high self-consistency score, the calibration algorithm will produce a high threshold with more stringent conditions for including a claim in the final output. Because there is no guarantee on percentage of claims kept, if self-consistency scores have no correlation with the correctness of subclaims, it will remove most claims to retain high correctness.

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.

The premise for our work is that given a language model that can potentially produce false claims, we want to remove such claims without any reliance or access to the gold labels from the MATH dataset. This is implemented through our filtering protocol, which makes use of a frequency-based scoring function, as a robust, grounding-free source of determining correctness for new examples; as such, our method is agnostic of the gold labels (true claims) in the dataset.

Graph Proxies

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.

The lower bound of Theorem 1 holds regardless of the quality of the graphs, although low quality graphs may harm claim retention. The only caveat is that coherent factuality is obtained relative to the knowledge source on which annotator’s rely on to perform annotation (which, in the context of our work, is solely limited to the annotator’s background knowledge). The upper bound is satisfied by graphs that satisfy Definition 4, and relative to human-annotated “ideal” deducibility graphs, the GPT-4o graphs satisfied this definition (see analysis of this below). Furthermore, as noted in our work, such a graph with additional edges still serves as an approximate deducibility graph per our definition, since we do not require minimality; the presence of bad claims and edges between this is therefore not a concern, as the calibration algorithm produces an appropriate threshold to filter out bad claims.

As mentioned above, are there any results from experiments using a human annotated ideal graph other than GPT-4o? Yes, we also have the following results comparing GPT-4o-generated graphs to human-annotated ideal graphs, and analyzing our method’s performance with these gold graphs (repeated from general response). For GPT-4o, we manually constructed ideal graphs for the first ten examples. The edit distance to the ideal deducibility graph was on average 1.8; the edit distance to an 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$).

The plots of the results which include the realized coherent factuality for each of these settings are in Appendix F.