Conformal Language Model Reasoning with Coherent Factuality
Authors: Maxon Rubin-Toles
Maya Gambhir
Keshav Ramji
Aaron Roth
Surbhi Goel
Venue: ICLR 2025 Poster (2025)
Keywords: language models
reasoning
conformal prediction
factuality
graph representation
coherence
Primary area: foundation or frontier models, including LLMs
TL;DR: We apply conformal prediction on dependency graphs towards ensuring coherence and factuality in language model reasoning.

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.

Published as a conference paper at ICLR 2025
CONFORMAL LANGUAGE MODEL REASONING WITH COHERENT FACTUALITY
Maxon Rubin-Toles Maya Gambhir**, Keshav Ramji²., Aaron Roth Surbhi Goel
1 University of Pennsylvania, 2IBM Research Al Denotes equal contribution
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 gener- ation 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 appropri- ate for reasoning tasks, as steps of a logical argument can be evaluated for correct- ness only within the context of the claims that precede them. To capture this, we define "coherent factuality" and develop conformal-predictionn prediction- -bbded method to guarantee coherent factuality for language model outputs. Our approach applies split conformal prediction to subgraphs within a "deducibility" graph that repre- sents the steps of reasoning problem. We evaluate our method on mathematical reasoning problems from the MATH and FELM datasets and find that our algo- rithm consistently produces correct and substantiated orderings of claims, achiev- ing 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-graan -rr--g-gaappheeeeee approach.
INTRODUCTION
As foundation models become ubiquitous, it is important to verify the correctness of their genera- tions. Consequently, ensuring the factuality and reliability of the outputs of these models is an area of active and growing research. One line of research (Guo et al., 2017; Jiang et al., 2021; Lin et al., 2022; Mielke et al., 2022; Detommaso et al., 2024; Ahdritz al., 2024) attempts to catch errors by quantifying model uncertainty; however, these methods are often difficult to apply in practical settings where output spaces are intractably large and uncertainty signals, like logit weights, are not accessible for many proprictary models.
Recently, conformal prediction has been explored as an uncertainty quantification technique to ad- dress correctness in language model (LM) outputs. In particular, (Mohri & Hashimoto, 2024) apply split conformal prediction to filter generations by removing weak claims according to some thresh- old calibrated desired error rate a. Subsequent work (Cherian et al., 2024) issues weaker but adaptive guarantees to ensure output completeness. However, both works implicitly assume the fac- reasoning tuality of claim can be independently evaluated, which limits their generalizability domains, where claims require substantiation. For example, in solving math problems, a given step often deduced result of preceding steps: generally, logical arguments require substantiation.
To tackle this challenge, we propose new notion of factuality to account for the structure of rea- soning problems, provide an algorithm which applies split conformal prediction to filter claims over a graph representation, and give correctness guarantees over the filtered output:
well-defined notion of coherent factuality. We present a notion of factuality which accounts for inter-claim dependence to evaluate correctness in more faithful manner. This definition requires
Code available https: //g1 thub.
http://tthu.....maamoaaaaa/ wttp://ww///aambiiiooo. ntoolenttteless weatttols//oooooooeooo __M_____________________ ________________ Reason ing

---

Published as a conference paper at ICLR 2025
Prompt: points (x. represented in this on a straight line. The point (13, q) lies on same What is value of p u?
-5
-14
p+2 2 -17
Original output:
Filtered output 1:
Filtered output 2:
-17 (-1)
-3
The sispa -17-
-3 2
The slope -17 (-1-(-14)
-3
p+2-p 2
p+2
p+2-y
-14
(-5- -9
14 - (-5) -9
slops also
The slope
2
2
p-2
p-?
Setting hees equa gives
-9
Seting these equai gives
-3
Setting these equal give
p
p
p
Sorving the equation gives p
5)
5
(-(-5) 13-2
2=5
The slope 1- (-5)
9+5 11
elope 13
The slope
2
11
11
Setting this equal gives
-3
3
1-5
Setting equal gives
-3
5
Setting equal givo
-3 g 11
2
2
11
2
2
11
33
Sahing gives
16.5
Independent Factuality
Independent Factuality
Coherent Factuality
X
Coherent Factuality
Therotor,, p (- (- 8.5
Here, the previous method (Output 1) removes the erroneous claims outlined in red, but leaves the response incoherent by removing Step 2, which is referenced Step 3. We (Output 2) consider reasoning structure to filter out erroneous claims while maintaining coherence; even though we remove a true claim, it is not essential for understanding the claims that remain (a = 0.1).
Figure 1:
that language model generations are both factual and coherent by evaluating entire orderings of claims as correct rather than evaluating individual claims.
An algorithm for coherent claim filtration. To apply this coherent definition of factuality, we propose graph representation for inter-claim dependence and an empirical method for obtaining such a graph. Rather than filtering claims individually, we filter between "well-supported" subgraphs via split conformal prediction to ensure coherence and factuality at any user-specified rate.
Empirical realization of conformal guarantees. We validate our algorithm on a variety of compe- tition math problems from the MATH dataset (Hendrycks et al., 2021) and from FELM (Chen al., 2023a), and experiment with different heuristic risk functions. We find that our graphical represen- tation often both sufficient (graph-based calibration satisfies conformal guarantees) and necessury (calibration that ignores graph structure does not satisfy conformal guarantees) to ensure coherent factuality. We achieve outputs as complete as the baseline with improved "legibility," or third-party verifiability, and we bootstrap filtered responses by reprompting to further improve factuality.
1.1 RELATED WORK
Conformal prediction is a statistical uncertainty quantification technique which yields marginal coverage guarantees over a confidence set in a distribution-free manner, traditionally only assum- ing exchangeability of the data (Gammerman et al., 1998; Shafer & Vovk, 2008; Angelopoulos & Bates, 2022). Split conformal prediction (Papadopoulos et al., 2002; Lei et al., 2018; Romano al., 2019) is a batched algorithm which relies on held out calibration set to yield tight guarantees in expectation over the draw of the calibration set. While conformal prediction has been explored un- der graph settings, this has largely been in the context of hierarchical labels (Tyagi & Guo, 2024; Angelopoulos et al., 2023) or graph neural networks, rather than induced graphs for reasoning.
Recent work has sought apply conformal prediction to language modeling, including multiple choice question answering (Kumar et al., 2023), as well as open domain and domain ques- tion answering and long-form generations (Quach et al., 2024; Mohri & Hashimoto, 2024; Cherian et al., 2024; Liu & Wu, 2024).
Mohri & Hashimoto 2024 applies nested conformal prediction (Gupta et al., 2022) with entailment sets, splitting generations into disjoint claims, and obtaining confidence estimates for each such that removing claims below corresponding calibrated threshold score yields a-conformal factual
2

---

Published as a conference paper at ICLR 2025
response. Cherian et al. 2024 extends this framework by introducing level adaptivity by conditional calibration (see also Detommaso et al. (2024) for a conditional calibration approach to scoring factu- ality), lowering the correctness level while simultaneously ensuring completeness of the output. Liu & Wu 2024 extend Mohri & Hashimoto 2024 to give context-conditiona coverage guarantees using the group conditional conformal prediction techniques developed by Jung al. 2023. However, while these works are effective in their application domains, where claims may be treated as inde- pendent, they do not generalize reasoning problems, where the correctness of each step cannot be evaluated without the context of the steps that precede it.
LLM Reasoning, Chain-of- Thought (CoT) reasoning induces LLMs to produce step-by-step ratio- nales to support their generations, similar to the human System 2 reasoning process (Wei et al., 2024; Nye et al., 2021; Kojima et al., 2022). Several approaches have been proposed to explore thought di- versity to this effect by sampling more and marginalizing over reasoning chains (Wang et al., 2023b; Chen et al., 2023b), incorporating different types of feedback (e.g. self-critique, external verifiers) and revision (Yao et al., 2023; Besta et al., 2024).
(Radhakrishnan et al., 2023) introduced CoT decomposition and factored decomposition as proce- dures that iteratively solve subquestions that make up the final generation, and showed that while accuracy drops slightly. factored decomposition greatly improves faithfulness to the true reasoning process of the model. Lastly, works process supervision and intermediate verification (Lightman et al., 2023; Ma et al., 2023; Dhuliawala et al., 2023) help with mitigating hallucination, but are costly at test-time and rely on the correctness of the feedback. We show how our filtered output can be used as chain-of-thought to get more factual completions.
2 PRELIMINARIES
Setup and notation. As is standard the language model (LM) generation setting, we assume that the LM takes in input X E X' and generates output Y E Y. We further assume that output Y can be written as set of "claims," and our goal is to filter the output to keep a set of "factual" and "coherent" claims. Note that we do attempt formal definitions for each of these difficult terms, and we ultimately evaluate our method's performance with human annotations.
Definition (Claim). A claim is an atomic proposition. From this, we define C, the set of all claims.
For example, claims might assert things like "The sky is blue" or, more abstractly, provide the definition of addition. The set of claims C can also contain assertions that are incorrect-for example that "Barack Obama was president in 2020." Note that we will not formalize where the boundaries are for what makes a particular string an atomic "claim" or not; we assume access to a claim splitter function, which takes LM outputs in Y and maps them
set of discrete claims. We write this as S:: + _ In practice, we will use a language model to implement claim splitting (Figure 1).
Definition (Ground truth). The ground truth Cuue S is the subset of all claims we assume to be valid without any additional information or context. In particular, this set is some known body of knowledge from which we base our evaluations of factuality.
Remark 1. In practice, might choose some reference like Wikipedia math textbook our ground truth. It is important to note that the ground truth is not necessarily fixed over examples and can be context-sensitive-fur instance, while it is generally reasonable to assume that v2 is irrational, it is not reasonable to do so in a proof of that fact.
Background: Conformal prediction guarantees for LM generations. Mohri & Hashimoto 2024 improve the factuality of LM generations by splitting them into subclaims and filtering low- confidence subclaims via conformal prediction. They obtain factuality calibrated to a user-specified parameter while maintaining significant proportion of the original output. Each subclaim is scored according to some heuristic confidence function" a : C + [O, 1] computed by comparing par- ticular subclaims to alternate generations for the same prompt. For each output, the non-conformity score r r(X, T) is simply the minimum threshold in set 'I such that all subclaims with confidence scores above the threshold are "factual" (or entailed by the ground truth Ciue. as verified by a human annotator). Further mathematical details are in Appendix H.
TTo frame our filtering method incurring risk by adding subclaims, we instead consider to be a heuristic risk dunction-details follow.
3

---

Published as a conference paper at ICLR 2025
Then, for calibration set of (1), (Xn: Yn), ordering r(X1, Y1, 7)....(((,,, Yn. 7) and taking da as the (n+1)(1-o)) quantile of the scores we obtain the split conformal guarantee:
n a - M T) S qal - -1--0 a 1/(n 1).
This result assumes data exchangeability and no ties scores (which can be enforced by inserting continuous noise). Mohri and Hashimoto further assume that (Vy E S(Y), Cirue = y) (Y is factual), i.e., the factuality of Y simply the simultaneous factuality of each its claims y-- Then, by omitting claims in S(Y*+1) with confidence scores below d. and recombining the remain- ing claims in filtered 1 which we denote Y n++ the above guarantee transfers factuality.
3 A NEW NOTION OF FACTUALITY: COHERENT FACTUALITY
While the approach of Mohri & Hashimoto 2024 calibrates to useful notion of factuality, this notion implicitly makes the strong assumption that subclaims are independent, so we call it independent factuality. Specifically, the assertion that (V'y S(Y), Ciue = y) each claim's 's correctness independently of the other claims in the generation. While this may be appropriate for pure recall tasks, like biography generation, we find that it is not sufficient to preserve
(Y is factual) treats
output quality for reasoning tasks. Our notion of coherent factuality further imposes coherence by requiring both correctness and substantiation.
Definition (Coherent factuality). Given an example X and ground truth Cones an outpul Yoddere (1/1, ...y Yn) E C of distinct claims is coherently factual if it satisfies
Vi E [n], ys is deducible from (y/,.... 1)-1), X, Cuue-
We omit a formal definition for "deducible" because deducibility is both subjective and context- sensitive (a claim may follow immediately for professional mathematicians but not for grade- schoolers, unless they are very precocious). Note that we require a claim in the ordering to be deducible from its prefix, the ground truth, and the example X, since information like variable def- initions will be sensitive to the context. As noted before, the ground truth is determined in part by the question (it not appropriate to assume a fact the proof of that fact).
Remark 2. According to this definition, coherence cannot come at the cost factuality. Deducibil- ity only stricter than implication: in particular, any fact which deducible from the ground truth must be implied by the ground truth. At worst, we might expect that by calibrating for this more stringent notion, we would simply output subsets of the claims output by the previous method. How- ever, by making use of graphical structure in our scoring and filtering, our method produces outputs of similar completeness to those of Mohri & Hashimoto (2024) and which, in some cases, contain important reasoning steps the previous method had omitted (see Appendix L).
Like independent factuality, coherent factuality does not stipulate that the response is relevant or responsive to query X (although it cannot contradict X), and would therefore consider logically consistent non-sequiturs to be correct. the setting we consider, we find that requiring relevance is not necessary, since the LMs we study consistently attempt a relevant response.
Intuitively, coherent factuality ensures outputs contain sufficient reasoning between previous claims and subsequent ones and considers orderings of claims rather simply sets. Steps must appear in logical sequence. For instance, a variable must be defined before is used. Given a set of claims S(Y). we write ((S())) E CN to denote particular ordering of those claims. Observation If an ordering (y1...., Un) is coherently factual, any prefix (y1...., for < n is also coherently factual. factual..
3.1 GRAPHICAL REPRESENTATIONS OF COHERENT FACTUALITY
will be helpful for us to capture coherence graphically. To do so, we will make the following benign assumption: if claim is deducible from some information, the claim remains deducible after adding more "good" information.
Assumption (Superstring deducibility). Fix some input X, ground truth Cune and claim Yn- Say that yn is deducible from some ordering of {y1.... .... Vn-1) }. and call the ordering Yuu. Then, if Yauper is coherently factual ordering on superset of {y1, ..., In- 1) yn is also deducible from Y Yuueer-
4

---

Published as a conference paper at ICLR 2025
coteenhent:: Clarn Claim
Coherent: Mainlain
etrccuue foral
Kdeal Graph
Graphh Proxy Edgea
Figure 2: The nodes above correspond to the subclaims enumerated in Figure 1. In blue is the ideal deducibility graph for this output which gives perfect information and allows us to keep all true claims. Even though our approximate deducibility graph lacks ground truth node and has additional edges (e.g.. (6, 7)), helps us preserve the integrity an output while filtering. In contrast, the baseline method leaves Claim 3 unsubstantiated by omitting Claim 2.
Ideal deducibility graphs. For particular Y), Ciue. oracle with perfect understanding of the ground truth could construct an ideal deducibility graph G = (V, E). Define vertex set := {S(Y), Puuee ), with Vuee stand in for all claims in Ciue and question X (as claims may be deducible from either/both of these). Then, edges indicate that a claim deducible from its ancestors. In particular, the oracle could construct the edge set E by iteratively considering topological layers beginning at the ground truth, asking, "Which claims are deducible from previous layers?" and drawing corresponding edges (a more detailed algorithm for construction
Appendix A).
Remark 3. There may be multiple ideal deducibility graphs. For example, if a claim is deducible from a or b, both deducible from Vrra, there is no way represent this relationship uniquely without a hypergraph; a graph with edge (a, c) or (b, c) could be obtained by the algorithm Appendix A).
This idealized construction yields a directed acyclic graph (DAG) where substantiated claims de- scend from Ubues and erroneous or unsubstantiated claims do not. we had such graph, conformal filtering would be unnecessary; we would simply output the descendants of Unue in topological order. However, this ideal unattainable, as ground truth and deducibility are not easily defined. Instead, we develop approximations of these graphs that suffice to achieve coherent factuality.
Approximate deducibility graphs. We define weaker notion of an approximate deducibility graph and find this notion is satisfied by ger--geneated proxies. This weaker notion is sufficient to maintain coherence during filtering while ensuring calibrated guarantees on factuality. Unlike ideal graphs, these proxies do not trace claims to ground truth represent the minimal set needed to substantiate a claim; instead. they capture sufficient sets for substantiation (see Observation for a formal definition of minimality). While they don't tell us which nodes erroncous, they indicate which claims are "required" for another and give a natural (topological) ordering on the claims.²
Definition 4 (Approximate deducibility graph). Let G = (V, E) be DAG for (X,Y), Crree Each node E V represents a claim y E Y. The edge set E must satisfy the following: (1) Ancestor- connected subgraphs: for any subgraph G (V.ub, Emai) that includes all ancestors of its nodes, if a coherently factual ordering exists for Vinnn then every topological ordering of G mb must also be coherent, and (2) Consistency: if an ancestor-connected subgraph Gub does not allow coherently factual ordering, then any larger subgraph Guuper 2 Guub must not admit a coherent ordering.
In other words, we require that a particular claim is sufficiently substantiated by its ancestors (so topological sort on those nodes will be coherently factual if and only the set does not contain erroneous claims). Since we assume we can access one such graph for each example, we would like be assured that graph satisfying this definition can always constructed.
In practice, these will almost al always correspond to the original numeric orderings of the claims originally generated.
5

---

Published as a conference paper at ICLR 2025
these conditios: [x] + and 2 + 1I 7
Prompt:
Find the sum of inigara that satisty
Independent Malinn
Bubgraph Altrring
equivalent to
2
66
Ix+ I| s 7 equivalent to 1
-7 e s 7 can be rererriitan as - a 6
3
"Exirs" dependency helps us filer ambiguous claims
-7 and 7 satisty both Inequaiitios
the -7 and
Figure 3: Even though Claim 6 is technically true, it detracts from the coherent solution it is de- rived from a false claim (which suggests the solution is 0). Although we do not require dependency, the edge (5, 6) prevents consideration of Claim 6 in the absence of Claim 5. This property improves the quality of the subgraphs we consider.
Forany Observation 2 (Approximate deducibility graph realizability). For any (X, Y), Crees there exists graph with vertex set S(Y) satisfying Definition 4.
The subgraph of the ideal deducibility graph G (V, induced on V \ Urmee (omitting the ground truth node) is an approximate deducibility graph (proof deferred to Appendix A).
Remark 4. An ideal deducibility graph is minimal. Among all approximate graphs for a particular (X,Y, ). there exists an ideal graph (minus Viue) with the minimum number of edges.* Ap- proximate graphs result from removing the ground truth node of an ideal graph and adding edges without introducing cycles (following Assumption 1). Approximate graphs enforce sufficient but not necessary substantiation; even so, they show great empirical utility in Section 5, with quantitative results in Appendix F and a qualitative example in Appendix
While an approximate deducibility graph must exist, we further assume that we can construct one for each (X, Y). In practice, we use GPT-4o to generate these graphs after splitting an output into claims, so we cannot enforce graph validity rigorously. However, our GPT-proxies satisfy Definition 4 in practice, which is sufficient for both calibration bounds to hold. We introduce another property of GPT-generated graphs which we call "dependency." Dependency helps us discard "unreasonable" subgraphs early in our filtering procedure. See Section 5 (end of paragraph "Approximate deducibil- ity graph generation") for more details and Figure (Appendix L) for an example.
4 A PROTOCOL FOR COHERENT FACTUALITY
If we had ideal deducibility graphs for each (X, Y), optimal filtering would be easy. Then, we could simply output topological sort of descendants from the ground truth node and omit the rest. Of course, approximate deducibility graphs don't allow this. They have two essential shortcomings: (1) they may contain extraneous edges (which is preferred over failing capture dependencies), and (2) they do not identify which claims follow from the ground truth.
post-hoc filtering. We would like apply conformal prediction filter the original output while maintaining calibration guarantees. As first approach, which we call "post- hoc filtering," " we take outputs filtered by the independent conformal baseline and apply our graphs to further filter claims lacking their ancestors. This alternate method will achieve coherent factuality by design if our graph proxies are good but may exceed the conformal upper bound as we remove additional erroneous claims.
First approach:
subgraph filtering. To achieve calibrated coherent factuality, we compute risk thresholds over a set of subgraphs of the approximate deducibility graph G to consider which sub- graph (and corresponding topological ordering of claims) to output. We subsequently show that thresholding based on this set suffices to obtain conformal coherent factuality.
Second approach:
To select subgraphs, we use a heuristic risk-scoring function o C + [o, 1]. which differs from Mohri & Hashimoto (2024) by measuring risk rather than confidence and using the graph G as input (clided for simplicity) rather than a singular subclaim. Subgraphs are generated by thresholding
"Since ideal graphs for the same (X, Y), Crue may have different numbers of edges, it is not the case that every idcal graph is minimal in this way.

---

Published as a conference paper at ICLR 2025
Algorithm 1: Subgraph Generator
Input: Graph G = E), claim-wise risk function o : V +
Output: Uf set of subgraph, threshold pairs (U;,
UT 0, T < sorted (-x) U (a(w) v VJ) // Sort risk scores
foreach 7; E T do
s Select nodes below threshold foreach E Vi in lopological order do
Vi + {u E V [())
if ancestor of v not in V2 then
Vi < V, {o} // Remove claim with missing ancestors U1 G[V]] // Induced subgraph
UT t UT U ((U,,))) returnlly U7
nodes independently and filtering out vertices lacking ancestors, producing at most |S(Y) + induced subgraphs. The heuristic risk of each subgraph corresponds to its threshold, with at most n + relevant thresholds, one for each each node and one for the empty set (Algorithm 1).
Scoring functions. Claim retention depends on our choice of claim-scoring function a. We apply a context-independen claim-scoring function and to score nodes individually. We refer to and as self-connistency scoring. In practice, we compute dndd as Mohri & Hashimoto (2024) by querying GPT-4 to generate 5 alternate responses and counting the frequency with which each subclaim ap- pears (prompt in K.1). We flip these confidence scores to obtain risk scores and use node risk scores to compute in the following two ways (with the use of the graph G)):
(1) Graph independent: (v) = (v),, which does not consider the graph to score each node,
(2) Descendant weighting: For each E V. define a(v) = (1 (n) + 8median (v') is descendant of v}. where 3 is a hyperparameter". The motivation for the descendant weight- ing function is to boost (reduce) confidence if the claims derived from particular claim are very confident (uncertain).
Once we have of subgraphs U corresponding to output Y, the non-conformity score of Y is simply the risk threshold below which all subgraphs make "good" filtered outputs.
Definition confoooofyrm scoring functioon. Given some (X, Y) pair, deducibility graph G EV. candidate subgraphs and thresholds Ut C U x T, we compute non-conformity score as follows:
XK,Y suupfr E R (U, E Uy with 7 S Tr, U coherently factual)
In other words, r(-) is the maximum tolerable risk: the risk of the first subgraph violating coher- ent factuality if one exists, otherwise co. Also, "U is coherently factual" is shorthand for "each topological sort of U is coherently factual according to X, Cirue."
Conformal correctness guarantees. Now, to apply split conformal prediction to control this risk, we take da : [(-aa)++]]] quantile of {1 - r(X,, Y, (T))) We then filter new outputs (Xn+1, 1n+1) with G441 by generating UT computing
Uniaered: Tiitered
=
arg max
T,
(U,r) UT 7<1-4.
and defining our final filtered output rd == Vi Viheerdd topological sort on Viltered. With the minimal assumption exchangeability of the underlying distribution D = X' x V, we have the following theorem (see Appendix C for full proof).
'Note that there several other ways ones below). We leave further exploration to future work.
graph structure for scoring (including modifications of the
'We explored several similar graph-sens sensitive scoring mechanisms. each motivated by weighting the risk score of node according the risk scores of its ancestors and/or descendants. The median version most robust in performance to small changes
beta (we speculate this is because the median not sensitive to outlier scores). swept heta values in [0, 1] and chose 0.5 its good performance.
'I there hack edges (yj ys when j i) in the "original" ordering of claims, removing the filtered claims without altering ordering yields valid V Vileeed

---

Published as a conference paper at ICLR 2025
Theorem 1 (Calibrated Factuality). Fix some calibration set {(x,, Y)) test point (Xx+1, Yn+1) ~ D, ground truth Cuve. and desired error rate a. Then the following holds:
1- PPLY44 is coherently factual].
If. additionally, each G3 is an approximate deducibility graph (see Definition 4) and r(X,Y,)) <
0o v(X,Y) we have:
P coherently factual] S 11- - a
n1
5 EMPIRICAL FINDINGS
Datasets. Our experiments make use of the MATH dataset (Hendrycks et al., 2021), which spans various branches of mathematics. This dataset is among the standard benchmarks reported in recent model releases, on which even frontier models hallucinate. We also use the FELM dataset Chen al., 2023a which consists of variety of verbal reasoning problems with results in Appendix D. We replicate our main experiments with an open-source model 1.lama-3.1-70BB -----B--nnttrutt for output and graph generation) and discuss the costs associated with GPT prompts in J.
Approximate deducibility graph generation. For proprietary models, we used examples and out- puts from Mohri & Hashimoto (2024), where subclaims were generated by GPT-4. We then queried GPT-40 via few-shot prompting (Appendix K) to produce adjacency lists, as graph generation proved more challenging than claim-splitting. Open-source experiments followed a similar setup (Appendix K. Dependency is an empirically useful heuristic suggesting the consideration use of one claim in producing the other, whether or not the use was correct. In this way, claim might depend on another even if it results from logical misstep. Dependency structure is quite common among the subgraphs we generate: in fact, 50% of graphs that contain any erroneous nodes have edges between erroneous nodes. For evidence of dependency's empirical utility, see Appendix F for quantitative data and L for qualitative data.
Individual claim (silver standard) and subset-level (gold standard) annotations were used to evaluate output factuality. For individual claims, annotators assessed whether a claim c would be true if all its graph ancestors were true, or, for a priori claims, whether it was supported by the ground truth. Subset factuality was measured by checking (1) ancestor connectedness and (2) whether any claim in the subset had an individual annotation of "No," assuming the graph proxies are reliable-at an assumption that may falter with sparse representations. Gold standard annotations directly assessed subsets for human notions of coherent factuality, independent of the graph. Silver annotations demonstrate the utility and accuracy of deducibility graphs through relative calibration. The MATH dataset includes both annotation types, while FELM includes only silver annotations.
Annotation.
Results. We directly compare the results of our coherent calibration algorithm with the conformal factuality algorithm of (Mohri & Hashimoto, 2024), which we call the baseline, on both independent and coherent definitions of factuality, considering the samples from the MATH dataset as well the FELM dataset. We validate all of our methods on manual (gold standard) annotations on each output. We also test our methods on the FELM Dataset with results in D and demonstrate utility for vary- ing types of reasoning problems. We attempted to generate deducibility graphs for the FActScore biography-generatin dataset; however, we found these graphs to be nonsensical and to contain ey- cles as responses to such prompts do not carry any inherent, directed structure. Our prompts can be found in Appendix K.I, and results of these experiments with Llama-3. 1---------ssttue can be found in Appendix J.
[R1] Graph proxies are sufficient to obtain coherent factuuliiy. The quality of the graph proxies is affirmed by the empirical satisfaction of theoretical guarantees in Figure 4a. Both bounds hold across factuality levels when we calibrate on silver annotations that assume proxies are good and validate on gold annotations. Empirical measurements of graph quality are in F.. We note some miscalibration
'This means each output contains a ballucination. This assumption is implicit in Mohri & Hashimoto (2024) and deseribes the setting in which this technique most useful. The lower bound holds without this assumption, and the upper hound approximately holds the underlying hallucination rate > a (we are working on a generalization of this upper bound).
2 This dataset contains reasoning word problems.
8

---

Published as a conference paper at ICLR 2025
Cal bratiinin ot
Catra Retained Caharent Tactuaiity
clamm: Tagel Facuusity
0.5
045
075
343
155
Callwrr
bectalllyy by Appa sangcogy uteein ieparieccy
Carlo Counce Dependargy Coep
Podh ag
Desceedd Yo Blssiing
Desentores (oadiec Schpraga fiberng ti stercy Griph)
(c)
(a)
(b)
Figure 4: We evaluate our post-hoe (green) and subgraph filtering algorithms (using descendant weighting with B 1/2 (red) and graph-independent scoring (bluc)) on MATH dataset. Post-hoc filtering is applied using the graph after initial filtering without a graph. We consider the baseline to be the method of Mohri & Hashimoto (2024) (yellow). In (a), we show calibration to desired factuality levels for Subgraph Filtering within theoretical bounds (shown in grey). In (b), we assess claim retention rates by varying a values, plotting both realized factuality and the fraction of retained claims across calibration methods and graph generation techniques. In (c) we plot claim retention with respect to user-desired calibration level.
for the FELM dataset (see Appendix 5a), which could be due to the lack of gold standard annotations for validation or incorrect graphs. The more efficient annotation method contingent on good LM- generated graphs gives practical empirical instantiation of our algorithm.
[R2] Graphical proxies are necessary to obtain coherent factuality. The baseline method fails to achieve both calibration (Figure 4a) and competitive claim retention likely because independent factuality does not often imply factual coherence. However, we must still validate against a simple N following the (linear) order in which claims occur in the
deducibility graph 1 - + generation, which also fails to achieve competitive levels of claim retention for the majority of a values when compared subgraph filtering. The linear method performs better on the FELM dataset (Figure 5b), which suggests the underlying graphs are closer to linear than they are in MATH.
[R3] Post-hoc filtering is not calibrated. While post-hoc filtering achieves similar claim retention as subgraph filtering for realized factuality level, it is not calibrated to user input. For a fixed user- specified factuality rate (which post-hoc filtering will often overshoot), subgraph filtering achieves better claim retention than post-hoc filtering although post-hoc filtering shows potential to correct independently-calinnn callbrated outputs. We note similar lack of calibration in post-hoc filtering for the FELM dataset (Figure 5a).
[R4] Conformally-filte
results achieve high levels of factuality while retaining most claims. We empirically achieve high coverage levels while retaining a majority of claims, thus preserving the utility of the generation (Figure 4b). This is important as conformal guarantees can trivially achieved by removing all claims with some calibrated probability. For example, the subgraph filter- ing algorithm obtains 90% factuality while retaining close to 80% of the claims, and obtains 85% factuality while retaining nearly 90% of the claims. The descendant weighting scoring function shows superior performance at low a, achieving arbitrarily high factuality while retaining at least 40% of claims.
[RS] Coherent outputs are more "legible" than the baseline while equally complete. (Kirchner et al., 2024) define legible reasoning as "reasoning that is clear and easy to check." " We defer human studies of output legibility to future works, but as a proxy, we asked GPT-4o and Llama-3.1-2 1---0B- Instruct to grade filtered outputs as either correct or erroneous (more details in Appendix N). For each combination of output generation model (GPT-4, Llama-3, -nsst-ttttt and output grading model (aforementioned judges), our method was more legible than the baseline (lower false positive and false negative rates for fixed levels of factuality). This improved output utility does not come at the cost of completeness: at a = 0.1, 64% of error-free outputs contain a correct final answer, the same rafe as the baseline outputs, which have diminished legibility and coherence.

---

Published as a conference paper at ICLR 2025
Table I: Change in error rate on questions with reprompting using claims retained via coherent and independent methods. We record the error rate of GPT oulputs on the prompt before conformal prediction is applied (zero-shot) and the error rate of GPT outputs when prompted to complete an incomplete (filtered) output. We compare error reduction between coherent incomplete outputs and incoherent incomplete outputs.
Coherent Factuality Error
Independent Factuality Error
Zero-shot
Post-filter
Reduction
Zero-shot
Post-filter
Reduction
0.05
28%
10%
418%
28%
26%
1.2%
0.10
28%
10.88%
417.12%
28%
16.56%
411.44%
0.15
28%
14%
414%
28%
18.84%
49.16%
[R6] Bootstrapping coherently factual inputs improves factuality of regenerations. We boot- strap coherent factuality by running the filtered output back through the model with the original prompt and requesting the model to fill in the blanks of our filtered output. See for more details. For a = 0.05, 0.10, 0.15, reprompting on coherent outputs provides consistently better reductions in error rate, compared to independently filtered outputs (Table 1). We posit this methodology is more effective for coherent outputs because they are easier to parse and build upon, demonstrating the utility of our method.
DISCUSSION
We show how achieve coherent factuality using the underlying graph structure of deducibility in reasoning problems. We show both theoretical bounds on the calibration guarantees of our method, and practical utility of our approach improve factuality of language models. Here we discuss limitations and potential future directions.
Graph proxies. While our graph proxies satisfy the definition of deducibility graphs empirically, relying on a proprictary model like GPT-4o for accurate graph generation is not ideal. We note that GPT-4o struggled with longer reasoning outputs containing many claims, raising concerns about practicality for multi-step problems.
Subjective ground truth and deduction. Whether claim is valid depends on the annotator's perspective and context. In a complex theorem, arithmetic may be implicit, while for simple algebra, could be central. Assumptions and axioms also vary by context. is important to note that correctness of outputs is only consistent with the annotator's subjective notion of truth.
Improved scoring functions. Our method works with any subgraph scoring function and increases claim retention by working to converge on the "true" underlying risk function with scoring function. Improvements may include scoring subsets beyond those considered by our algorithm based and accounting for additional graph structure in node heuristic measures.
Expanding evaluation to further domains. This work is primed to extend to any reasoning con- text, where graphical representation is not insignificantly sparse. For example, code generation a natural domain, as compilation both an easy and well defined notion coherent substanti- ation, and correct final outputs clearly indicate correctness. Furthermore, dependency graphs are common notion in software systems at large, which pairs well with our framework.
ACKNOWLEDGMENTS
SG acknowledges funding from OpenAl Sugenmli Fast Grant as well as Microsoft Research grant which generously supported the compute resources required in this work.
MG acknowledges funding from Penn Engineering's Rachleff Scholars Program.
REFERENCES
Gustaf Ahdritz, Tian Qin, Nikhil Vyas, Boaz Barak, and Benjamin L. Edelman. Distinguishing the knowable from the unknowable with language models, 2024. URL https: /apps://aree http///avvvvva///// .org/
10

---

Published as a conference paper at ICLR 2025
hos/2402.0350)
Anastasios N. Angelopoulos and Stephen Bates. A gentle introduction to conformal prediction and distribution-free uncertainty quantification, 2022. URL httt::///a/ http:///awxwww....aa/ooo wwtpa/wwwwww..//////////// 2207
07511.
Anastasios N. Angelopoulos, Stephen Bates, Adam Fisch, Lihua Lei, and Tal Schuster. Conformal risk control, 2023, URL htt.t:ttt///aiiiiie wrg/bbs///aaaa.. 2208 02814.
Neil Band, Xuechen Li, Tengyu Ma, and Tatsunori Hashimoto. Linguistic calibration of long-form generations, 2024. URL htattps://axxi..ogg/.ooo
00474.
Maciej Besta, Nils Blach, Ales Kubicek, Robert Gerstenberger, Michal Podstawski, Lukas Gi- aninazzi, Joanna Gajda, Tomasz Lehmann, Hubert Niewiadomski, Piotr Nyczyk, and Torsten Hoefler. Graph of thoughts: Solving elaborate problems with large language models. Pro- ceedings of the AAAI Conference on Artificial Intelligence, 38(16) March 2024. ISSN 5399,, doi: 1..1609/aaii.v38i6..2000 aaai
URL http: http//xddccccccoooooooooo.do...o doi
v38 voai.v38110
6 29720.
Jiuhai Chen and Jonas Mueller. Quantifying uncertainty in answers from any language model and enhancing their trustworthiness, 2023. URL https:// http://axxvvvoo hat//ab///// abs.///8.... 16175.
Shiqi Chen, Yiran Zhao, Jinghan Zhang, I-Chun Chern, Siyang Gao, Pengfei Liu, and Junxian He. Felm: Benchmarking factuality evaluation of large language models. In Thirty-seventh Conference on Neural Information Processing Systems Datasets and Benchmarks Track, 2023a.
URL http: arxivv. org/ abss/3111 00741.
Xinyun Chen, Renat Aksitov, Uri Alon, Jie Ren, Kefan Xiao, Pengcheng Yin. Sushant Prakash, Charles Sutton, Xuezhi Wang, and Denny Zhou. Universal self-consistency for large language model generation, 2023b. URL https: /wtxivivvvv///////// wogg/bs///... 2211..131111111.1..1111111111111 17311.
John J. Cherian, Isaac Gibbs, and Emmanuel J. Candès. Large language model validity via enhanced conformal prediction methods, 2024. URL
org/ abs 220//440000000 09714.
Gianluca Detommaso, Martin Bertran, Riccardo Fogliato, and Aaron Roth. Multicalibration for
confidence scoring in Ilms, 2024. URL https: http://:/axxxiv...aa.oa
/2404. 1..00.04660 04689.
Shehzaad Dhuliawala, Mojtaba Komeili, Jing Xu, Roberta Raileanu, Xian Li, Asli Celikyilmaz, and Jason Weston. Chain-of--erriiiaation reduces hallucination in large language models, 2023. URL
https: //tp:///////v////aa org/ alss 2309. 11495.
A. Gammerman, V. Vovk, and V. Vapnik. Learning by transduction. In Proceedings the Fourteenth Conference on Uncertainty in Artificial Intelligence, UAI'98, pp. 148-155, San Francisco, CA, USA, 1998. Morgan Kaufmann Publishers Inc. ISBN 155860555X.
Chuan Guo, Geoff Pleiss, Yu Sun, and Kilian Q. Weinberger. On calibration of modern neural networks. In Proceedings of the 34th International Conference on Machine Learning Volume 70, ICML' 17, pp. 1321-1330. JMLR.org, 2017.
Chirag Gupta, Arun K. Kuchibhotla, and Aaditya Ramdas. Nested conformal prediction and quantile out-of-bag ensemble methods. Pattern Recognition, 127:108496, July 2022. ISSN 0031-3203. doi: 10.101 patcopp.tto..2...1.. 2021. 108496.
URL http:/ /etp::/dxx.. doi www./oo./........o 1ww.:1111..pp.. pateoo..
Dan Hendrycks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. Measuring mathematical problem solving with the math dataset, 2021.
URL httph:tt///// /ttp//xxvvvoo// wtr.vi.orr///ooo abs/ /w1../113..00 03874.
Lei Huang, Weijiang Yu, Weitao Ma, Weihong Zhong, Zhangyin Feng, Haotian Wang, Qianglong Chen. Weihua Peng, Xiaocheng Feng, Bing Qin, and Ting Liu. A survey on hallucination in large language models: Principles, taxonomy, challenges, and open questions, 2023. URL https:
// //arxiv. //arxiv.org/abb///2..... 05232.
11

---

Published as a conference paper at ICLR 2025
Zhengbao Jiang, Jun Araki, Haibo Ding, and Graham Neubig. How we know when language models know? on the calibration of language models for question answering, 2021. URL https: //arxiv.org org. abs 00955.
Christopher Jung, Georgy Noarov, Ramya Ramalingam, and Aaron Roth. Batch multivalid confor- mal prediction, 2023. Proceedings of the International Conference Learning Representations (ICLR).
Adam Tauman Kalai and Santosh S. Vempala. Calibrated language models must hallucinate. In Pro- ceedings the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, pp. 160-171, New York, NY, USA, 2024. Association for Computing Machinery. ISBN 9798400703836. doi: 10.1145/3618260.36644
URL https: /doi. org/ 11 45/ 361 01115//61166600333
Jan Hendrik Kirchner, Yining Chen, Harri Edwards, Jan Leike, Nat McAleese, and Yuri Burda. Prover-verifier games improve legibility of Ilm outputs, 2024. URL httttt://aaaaaa /arxiv..///xv////////
abs /tt//2407..166
Takeshi Kojima, Shixiang (Shane) Gu, Machel Reid, Yutaka Matsuo, and Yusuke Iwa- sawa. Large language models are zero-shot reasoners. In S. Koyejo, S. Mo- hamed, A. Agarwal, D. Belgrave. K. Cho, and A. Oh (eds.), Advances in Neural In- formation Processing Systems, volume 35, pp. 22199-22213, Curran Associates, Inc., 2022. URL pettps::/proceeeeeee hewpeeedddnnnnnnnnnnneeeeeeeeeee neurips ceeee.c./ee http:/ppprreeeeeeeeeeeeaaaapeeee files/ pttes//pppe//22222 file/ t
pdf.
Lorenz Kuhn, Yarin Gal, and Sebastian Farquhar. Semantic uncertainty: Linguistic invariances for uncertainty estimation in natural language generation, 2023. URL httpp:s//axxxv.rrpp/p abs/2302. 09664.
Bhawesh Kumar, Charlie Lu, Gauri Gupta, Anil Palepu, David Bellamy, Ramesh Raskar, and An- drew Beam. Conformal prediction with large language models for multi-choice question answer- ing, 2023. URL https: /ttp///avvvvvvvvv///i//eee/..wva org/ abs wtbs//3000 320 18404.
Jing Lei, Max G' G'Slll, Alessandro Rinaldo, Ryan J. Tibshirani, and Larry Wasserman. Distribution- free predictive inference for regression. Journal of the American Statistical Association, 113 (523):1094-1111, 2018.
doi: 10.1080001221455.2007..11117
Hunter Lightman, Vineet Kosaraju, Yura Burda, Harri Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe. Let's verify step by step, 2023. URL
https:/ / /arxivv.. www//ogg/s.....oooooo.. 2/.///35..200
Stephanie Lin, Jacob Hilton, and Owain Evans. Teaching models to express their uncertainty in words, 2022. URL https: /att://axxxe arxiv. wttpabsssrg////..o////a.o http//abs//2/5// 2205 14334.
Terrance Liu and Zhiwei Steven Wu. Multi-group uncertainty quantification for long-form text generation, 2024. URL https:t.. / ht/pirxvvv.//// ort. /200 220.//2777........ 21057.
Qianli Ma, Haotian Zhou, Tingkai Liu, Jianbo Yuan, Pengfei Liu, Yang You, and Hongxia Yang- Let's reward step by step: Step-level reward model as the navigators for reasoning. 2023. URL
https: //tp:///aiivii//ii orgooo////o.o. wtggabs/////ea 2210 10080.
Sabrina Mielke, Arthur Szlam, Emily Dinan, and Y-Lan Boureau. Reducing conversational agents' overconfidence through linguistic calibration. Transactions the Association for Computational Linguistics, 10:857-872, 2022. doi: 16.1162/ URL https:
//aclantholog ogy wwwp////...2... 20..222tacl111.
Christopher Mohri and Tatsunori Hashimoto. Language models with conformal factuality guaran- tees, 2024. URL
10978.
Maxwell Nye, Anders Johan Andreassen, Guy Gur-Ari, Henryk Michalewski. Jacob Austin, David Bieber, David Dohan, Aitor Lewkowycz, Maarten Bosma, David Luan, Charles Sutton, and Au- gustus Odena. Show your work: Scratchpads for intermediate computation with language models, 2021. URL https:/
00114.
12

---

Published as a conference paper at ICLR 2025
Harris Papadopoulos, Kostas Proedrou, Volodya Vovk, and Alex Gammerman. Inductive confidence machines for regression. In Proceedings of the 13th European Conference on Machine Learning, ECML'02, pp. 345-356, Berlin, Heidelberg, 2002. Springer- Verlag. ISBN 3540440364. doi: 10.1007/3--40-36655-- 29, URL https: /oi iooi... org/ 0 100 3 540- 1_9.
Victor Quach, Adam Fisch, Tal Schuster, Adam Yala, Jae Ho Sohn, Tommi S. Jaakkola, and Regina Barzilay. Conformal language modeling, 2024. URL https: /ttp///aavvvvv/.a///a//eaaaaiwva org/ abs//306.. 10193.
Ansh Radhakrishnan, Karina Nguyen, Anna Chen, Carol Chen, Carson Denison, Danny Hernande,, Esin Durmus, Evan Hubinger, Jackson Kernion, Kamile Lukošiūté, Newton Cheng, Nicholas Joseph, Nicholas Schiefer, Oliver Rausch, Sam McCandlish, Sheer El Showk, Tamera Lan- ham, Tim Maxwell, Venkatesa Chandrasekaran, Zac Hatfield-Dodds, Jared Kaplan, Jan Brauner, Samuel R. Bowman, and Ethan Perez. Question decomposition improves the faithfulness of monel-generated reasoning, 2023. URL https:t/tttttttttee org/ abs 2207 11768.
Yaniv Romano, Evan Patterson, and Emmanuel J. Candès. Conformalized quantile regression, 2019. URL
abs// /190//99555.. 1905. 03222.
Glenn Shafer and Vladimir Vovk. A tutorial on conformal prediction. J. Mach. Learn. Res., 9: 371-421, 2008. ISSN 1532-4435.
Vaishnavi Shrivastava, Percy Liang, and Ananya Kumar. Llamas know what gpts don't it show: Sur- rogate models for confidence estimation, 2023. URL bittps://arxiin org/ 08877.
Katherine Tian, Eric Mitchell, Allan Zhou, Archit Sharma, Rafael Rafailov, Huaxiu Yao, Chelsea Finn, and Christopher Manning. Just ask for calibration: Strategies for eliciting calibrated con- fidence scores from language models fine-tuned with human feedback. In Houda Bouamor, Juan Pino, and Kalika Bali (eds.), Proceedings of the 2023 Conference on Empirical Meth- ods in Natural Language Processing, pp. 1433-5442, Singapore, December 2023. Associa- tion for Computational Linguistics. doi: 10. 10.18653/w1/2223.emm / //aclanthology org/ 2rg//023.rr emnlp momnlp-maing main. 330.
URL https:
Chhavi Tyagi and Wenge Guo. Multi-label classification under uncertainty: A tree-based conformal prediction approach, 2024. URL https: /tti:///axxii www.aaawv........o..aaaoa.. abs / 2404... 194722.
Cunxiang Wang, Xiaoze Liu, Yuanhao Yue, Xiangru Tang, Tianhang Zhang, Cheng Jiayang, Yunzhi Yao. Wenyang Gao, Xuming Hu, Zehan Qi, Yidong Wang. Linyi Yang, Jindong Wang, Xing Xie, Zheng Zhang, and Yue Zhang. Survey on factuality in large language models: Knowledge, retrieval and domain-specificcty, 2023a. URL https:://// /tt////aavvvv//// wrw.ooggaaaao. wbt./211.00.. 07521.
Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoe Le, Ed Chi, Sharan Narang, Aakanksha Chowdh- ery, and Denny Zhou, Sonfssoony improves chain of thought reasoning in language models, 2023b. URL https: / /aapiaixivvvooo...a/aaaa org. abs 22022.2...1111
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed H. Chi, Quoe V. Le, and Denny Zhou. Chain-of-thought prompting elicits reasoning in large language models. In Proceedings of the 36th International Conference on Neural Information Processing Systems, NIPS '22, Red Hook, NY, USA, 2024. Curran Associates Inc. ISBN 978171387 1088.
Miao Xiong, Zhiyuan Hu, Xinyang Lu, Yifei Li. Jie Fu, Junxian He, and Bryan Hooi. Can Ilms express their uncertainty? an empirical evaluation of confidence elicitation 1lms, 2024. URL https: //tpii/aaiivvvv/iaa/eaaeeearaaia org/abs 2306. 13063.
Shunyu Yao, Dian Yu, Jeffrey Zhao, Izhak Shafran, Tom Griffiths, Yuan Cao, and Karthik Narasimhan. Tree of thoughts: Deliberate problem solving with large language models. In A. Oh, T. Naumann, A. Globerson, K. Saenko, M. Hardt, and S. Levine (eds.), Advances in Neural Information Processing Systems, volume 36, pp. 11809- 11822. Curran Associates, Inc., 2023. URL https: /ttttp:://poooe http::////oooooooooeeeeeee neuriiss....uuussss heppp hacpapeeeeee_____aaaaaaaaaaaeeee /alles/aper/2000 file/ htle://2fal222222caaaaaaaaaa4aa3
.ddf.
13

---

Published as a conference paper at ICLR 2025
Muru Zhang. Ofir Press, William Merrill, Alisa Liu, and Noah A. Smith. How language model hallucinations can snowball, 2023. URL httph:://////c...t. aattps://axxii https////wwwvvv.raaaaaaao httpa//..rgga//////aaaaaae httpr///bb/330.1111/ 23534.334....
Kaidlyn Zhou, Dan Jurafsky, and Tatsunori Hashimoto. Navigating the grey area: How expressions of uncertainty and overconfidence affect language models. In Houda Bouamor, Juan Pino, and Ka- lika Bali (eds.), Proceedings of the 2023 Conference on Empirical Methods in Natural Language Processing, pp. 3506-5524, Singapore, December 2023. Association for Computational Linguis- URL ht https: / / ac ant holgyyyooo...oooooooooooooooooym org/2023.
tics. doi: 10. 10t0233/11/222mlppppp main.335
emn omnlp-ma ma 335.
14

---

Published as a conference paper at ICLR 2025
A GRAPH DETAILS
Algorithm 2: Ideal Graph Assembly
Input: example (X, Y), ground truth Cuue. claim splitter S y + 2
Vitart S(Y)
V, F 0
Lo = {tirue) }
V = V U
t =
while 3 Viaan that is deducible from some ordering of nodes in V do
t 1+1
Lt =
for each such do
ancestors = {A C 3 with x (A), is coherently factual) A arg A'anceeesssooooo |A' Lt-1
= =
VALI -isun \ {r} for each o' An L4-1 do EU {(r,,))}
V return G EV.
Proof of approximate deducibility graph existence. To prove this, we first make note of an important property of the ideal graph construction.
Lemma 1. In an amcestor-connected subgraph of the ideal graph, a claim v is a descendant of Orme iff. it is an element coherently factual ordering.
Assume a node u is in the vertex set Vsub of ancestor-connected subgraph Gsub Gideal-
(Vsubr Esub) of
To prove the forward direction, assume is descendant of Unme in G Then, by construction, there some ordering (a(v)) (Vower U/,, ..., Uk) such that (Virue 21,,.., Uk v) is coherently factual.
For the backward direction, assume that o is part of a coherently factual ordering (U1,... Uk v)- Then, by the definition of coherent factuality, 01 is deducible from Umue and so on inductively, so each node preceding v will have path from Unue in the ideal graph. Thus, will also be descendant of Virue in Giteat: since Gsub is ancestor connected, this holds in G.ub-
Now, we proceed with the proof of approximate deducibility graph existence. Fix some (X,Y) Cinee S: 2
Generate the ideal graph Gideal = (Vidcat, Esdea) with With Algorithm 2. Then, consider its subgraph on V Videal Lo L1 U... Inn Call this G = (V, E).
G' is DAG by construction, so to prove the approximate deducibility property, we fix some Gsub satisfying ancestor connectedness.
To show (1), assume that coherently factual ordering exists for Viub By Lemma 1, this implies that each v Voub descendant of Grme Giaea- Then, by construction, each v Vauh is deducible from a(v). In topological sort, is preceded by each v' a(v), and so any topological sort gives a coherently factual ordering.
To show (2), consider the case that Gsub does not allow coherently factual ordering. Since Urme is in a coherently factual ordering and G U ( is an ancestor-connected subgraph in Gideal. Lemma says that least element Ubad is not contained in any coherently factual ordering (otherwise, each u would descendant of Unue; by the previous argument, a topological sort of V.n is then coherently factual ordering). In particular, superset of Vub contains Und and therefore has coherently factual ordering.
Both properties hold, so the proof is concluded.
15

---

Published as a conference paper at ICLR 2025
B CONFORMAL FILTERING ALGORITHM
In the algorithm below, we refer to Algorithm "Subgraph Generator," simply as "subG."
Algorithm 3: Coherent Calibration
Input: Confidence a, calibration data {(X,, Y)) output graphs {G, = b,)
T O
for i in [n] do
Ur Sub
r = r fr(X,, Y(,U1,))
[(++1)(-o)) th quantile of {1 T/TT ET]
da
return 9o
C PROOF THEOREM
Proof. To show the following, we refer to notion of ancestor connectedness introduced Defi- nition 4. Recall that to obtain the upper bound, assume that (X,Y.) < V).
Note that, if we apply Algorithm to G each subgraph in output UTT,11 satisfics ancestor con- nectedness.
As we proceed, for ease notation, we simply write Now, since (1 - r(Xn+1) S 4n) (r(Xn+1) 2 - (n), we have
for r(X+1, 1n
1- < ((r((x+11) 2 dnl <
n
standard split conformal result (where the probability is taken over the draw of the calibration set and (Xn+1, )).
To prove the claim, it suffices to show r ((Xa+1) 2 Gn =
ydu, is coherently factual.
For both directions, will consider Utiltered in Section 4.
For the forward direction, assume r(Xn+1) 2 qc. Then, by definition, conformally filtered Y: coherently factual (since r r(Xn+1) is defined such that each subgraph with less risk is coherently factual, and Untereed satisfies this since Tittered assumptions on the quality of deducibility graphs to obtain this result.
Qa S r(Xn+1)). Note that make no
For the reverse direction, r(X,,, Y..) < co, there exists subgraph, threshold (Unad, Thad) with Ubad = (Vhad, Evat) E Un+ Thad 1 q.: otherwise, the first bad graph would have risk at least Go. so the supremum of safe scores r(Xn+1) would be at least 1 - da-
will show the contrapositive. Assume r(Xn+1) 11 qa- Since
Say n+1 is the vertex set from Unitered. Note that Tiltered Thad (since Trittrrd is the maximum of risks below d.).
Vittered Unad the desired result (1 is not coherently factual) follows.
Otherwise, Unad is subgraph of Unitered, and both ancestor-connected, properties obtained by Algorithm 1. particular, this means Viitered is a superset of Vhnd-
Note that G is approximate deducibility graph and Unat is an ancestor-connecte subgraph with no coherently factual ordering (if it had one, Via in particular would be coherently factual by Definition 4). Additionally, any superset of Voad has no coherently factual ordering. also by Defini- tion 4. However, y is one such ordering superset Vnitered. which concludes the contrapositive of the backward direction.
We have thus shown that (r(Xn+1)= 2 1- 5
(Y441 is factual), which proves the claim. n
16

---

Published as a conference paper at ICLR 2025
D RESULTS FOR FELM DATASET
We present the results of our algorithms on the FELM Dataset, as discussed in the results section. The lines graphed correspond to the same evaluation settings as with the MATH dataset. We note that the Post-Hoc Filtering algorithm remains un-calibrated (even more so) in these results compared to subgraph filtering which (almost perfectly) calibrated (see 5a). The slight discrepancy may be due to erroneous graphs in this case, but still fails to meet the lower bound for any value a. The validation results (see 5b also appear be similar that of the MATH dataset. However, of linear graphs, implying that reasoning paths may be closer to perfectly linear in this dataset. Post-Hop and subgraph filtering remain relatively the same, and still competitive relative one another in claim retention.
lack manual annotations. The dependency baseline performs better
note better performance
Claims Retained vs. Coherent Factuality
Callbration P
0.9
0.950
Pkalizedd CJ FaISi Pickaaly
0.7
0.900
0.000
0.825
02
0.800
0.825
0.300
0,875
0,900
0.925
0,500
0375
1.00
Taiget Ractuality [1 alpha)
Factuality
Conformal Bounds
Subgraph fibaring [CPT Dependency Graph)
hitering (GPT Dependency
Post Hoc Fittenng
Filwwing
(Baseline)
Empry Depenienncy Graph (Baseline)
Subgraph rikaring Depardency Graph)
(b) Percent of claims kept factuality (FELM) Figure 5: Results on the FELM dataset using GPT-4 for responses and GPT-4o for graphs.
(a) Calibration plot (FFLM)
E RESULTS WITH
(OPEN-SOURCH)
We ran the same experiment on the MATH dataset for outputs, subclaim splits, and graphs produced by Llama. While Llama Lamm--genrrate graphs were further from ideal and less often satisfied Definition (discussion of our altered approach in Appendix K.I), our empirical results suggest they are still useful. The plots below are for silver-annotated calibration and validation.
Calloration Pott
Cleims Retaised vs. erent Pactuality
1.00
Nodbbel Cihoren sochaatt
0.55
0.00
maa
a.55
0:50
Clver
0.75
0.70
0.85
0.75
3:80
0.55
Target hectuelity alphal
Subgueh Filrring
Ceheren: Factuell
Descendarts Weggh Beosling
--_ Contoreall So.ads
Subggughh Fillsiin
seccesccoosss Booudrng
(a) Calibration plot (Llama) Figure 6: Results on the MATH dataset solely using Llama-3. 1--70--Inntruun
(b) Percent claims kept vs. factuality (Llama)
17

---

Published as a conference paper at ICLR 2025
F MODEL-GENERATED VS. IDEAL GRAPHS
Surprisingly, graphs generated by GPT-4o seemed to have more empirical utility than ideal, human- generated graphs. As discussed in Section 5, this additional structure, although not strictly necessary to obtain theoretical guarantees, tends to improve the set of subgraphs we search over by deferring admittance of faulty claims that rely on faulty claims. GPT includes edges between such claims while the ideal construction does not require this.
In Figure 7, we compare the claim retention of GPT-graph vs, ideal-graph calibration on 10 examples from the MATH dataset.
To validate our graphs, for the first 10 GPT proxies, we measure their edit-distance to (manually- constructed) ideal graphs (1.8 on average) and check whether they are approximate deducibility graphs (100% are). The second result means each graph we checked satisfied Definition 4, which is sufficient to obtain both conformal bounds. For the first 10 LLaMa-generated graphs, the edit distance is 10.7, and 40% are approximate deducibility graphs.
vs Factuality
2.
2.-
Procert
8600
OFT Draplo HLmann udeal umapts
Figure 7: Performance of GPT-generated vs. human-constructed graphs for a = 0.1,,.2,0.3
G FURTHER RELATED WORK
Factuality and Hallucination in Language Models.
Ensuring the factuality of language model outputs is an important objective towards their reliable real-world deployment across diverse settings. Hallucinations can arise in several ways, including lack of knowledge or recall problems from pre-training data, fine-tuning data, or a vector datastore with RAG, well as issues with decoding strategy (Huang al., 2023), (Wang et al., 2023a)). Works such as (Kalai & Vempala, 2024) suggest that LMs will always hallucinate while there exists unknown knowledge, while others such as (Ahdritz al., 2024) seek identify uncertainty due to lack of knowledge via linear probes. At the same time. (Zhang et al., 2023) demonstrate LLMs can independently identify hallucinations, but often continue with incorrect lines of reasoning even when a mistake is made early on. Our work directly addresses such a setting through dependence- based factuality within reasoning chain, avoiding cascading hallucinations by design with high probability.
Uncertainty Estimation. The problem of insufficient (or incorrect) knowledge can be treated as epistemic uncertainty, while inference-time decoding randomness in sampling can be addressed as aleatoric (Ahdritz et al., 2024). Thus, the study of uncertainty estimation language models complementary to goal of mitigating hallucinations. Prior works have explored expressions of uncertainty including logit weights (Guo et al., 2017; Jiang et al., 2021), surrogate estimates (Shrivastava al., 2023), sampling variance (Kuhn al., 2023; Xiong et al., 2024), and natural language generations indicating uncertainty (Lin et al., 2022; Zhou et al., 2023).
There is also line of work which leverages confidence scores which, when calibrated, should be proportional to the correctness the generation (Mielke et al., 2022)). Chen & Mueller 2023 use self-reflection and consistency over generations sampled with fixed temperature, and select the
18

---

Published as a conference paper at ICLR 2025
generation with the highest confidence score (which is also output to the user). Tian al. 2023 demonstrates that verbalized confidence scores, akin to (Lin et al., 2022), are better calibrated than using the log probabilities, which generally overconfident relative to the true level of correct- ness. Band et al. 2024 introduces a pipeline for linguistic calibration with supervised fine-tuning to enable elicitation of faithful confidence scores, and decision-basee -aaeed reinforcement learning through a forecasting formulation. Detommaso et al. 2024 uses multicalibration to several groups of promp- Vcompletion pairs means to elicit reliable confidence scores. Our work makes use of risk function based on our coherent approach on factuality, calibrating with respect to annotated claim and subset labels.
H MORE DETAILS ON CONFORMAL FACTUALITY
We expand on the details of Mohri & Hashimoto (2024) application of conformal prediction to language model outputs.
More formally, Mohri Hashimoto (2024) frame factuality in terms of entailment by the ground truth.
Definition 6 (Entailment operator). The function E C - {Cruppon S 2c} takes in a claim E C and outputs each set Ssppport C 2 of claims whose conjunction implies
C E E(c), we abuse notation and simply write C = c. Mohri and Hashimoto seek retain claims such that Cirue = for each and consider this sufficient for realizing factuality of an output.
There some difference in notation between this definition and the original since Mohri and Hashimoto frame the ground truth Cive as simply an element of y, while we frame it as a set of claims.
Definition (Independent non-conformity scoring function). For a particular output Y with claims C' = S(Y) and some set T of candidate thresholds, the non-conformity score r is defined as follows:
r(X,Y,T) = inf(r E T Vj 2 T, Vy C, (o(y) 2 j) = (Cine = y)}
Then, since increasing the threshold can only remove claims, the traditional conformal guarantee
1 - a P|r(XXtt, T) s da) S a n+
can be written
1 m +
1 a < Plyy E S(Y Crre = v) 5 a
Then, they assume that (Vy E S(Y), Ciree
= v) - (Y factual), so we obtain
1 < Py +1 is factual]
n n+1
MORE DETAILS ON BOOTSTRAPPING CONFORMAL FACTUALITY
We may use the outputs both the baseline independent factuality conformal prediction algorithm and our new coherent factuality conformal prediction algorithm to reprompt the model, see K.3 for the exact prompt. We give the model both the original question and the remaining filtered output and ask it to complete the solution using the context given.
For a = 0.05, 0.1, 0.15 we observe the change in factuality from prompting with no context to prompting with the added context of the filtered set of claims. After reprompting, we observe the correctness of the new output and record the new error rate. The new output is considered correct only if all the new claims and reasoning used are correct. The table 1 demonstrates how the error rate has a greater reduction when reprompting with a coherent subset of the original claims rather than incoherent subset.
19

---

Published as a conference paper at ICLR 2025
J COSTS ASSOCIATED WITH GPT QUERIES AND RUNNING ON -LAMA-3.1-70B-INSTTI
Cost and reproducibility. We replicated our main experiments with 1--ma- Instruct (for output and graph generation) with slight changes to the prompting required to elicit useful graphs (see Appendix K. We find that the utility of the approach holds for less powerful open-source models: we present our results in Appendix.
The algorithm is also inexpensive implement. For each example in the calibration and test the algorithm requires 8 queries comprising at most 16k tokens; for our calibration set of 50 examples, this cost less than $5.00 using GPT and less than $0.70 using Llama. The same queries the test set, so each test example cost less than $0.10 for GPT and $0.01 for Llama. These estimates are conservative, assuning full utilization of 2000-token total context and output to accommodate longer form responses (although our responses were much shorter). Perhaps more prohibitive than monetary cost is the number of annotations necessary (at worst exponential in n, the number of subclaims for an example). However, this is a one-time cost for calibration, and our results suggest that silver annotations, of which there are n, suffice.
made for
K API USAGE FOR MODEL QUERIES
We report few important notes the API calls made to OpenAl models for empirical evaluation of our algorithm:
1. A temperature of 1.0 was used to generate alternate responses for frequency scoring; temperature 0.0 was used for all other API calls.
2. GPT-4 was used for the generation of outputs for the MATH questions.
3. GPT-4 was used for self-consistency scoring, described in Section 4.
4. GPT-4o was used for graph generation.
K.1 DEPENDENCY GRAPH GENERATION PROMPT (MATH/FELM)
GPT-4o Our prompt for graph generation includes in-context exemplars annotated with rationales ("commentary") for guided decomposition of the model-generater output into claims and their rela- tion one another.
I'm going to give you a question and a series of claims in response to the question. I want you to create dependency graph to represent the relationships between claims. The set of vertices should be the set of claims. Then, if a claim "a" relies on another claim "b" to be considered true, include edge (b, a) in the graph (so node's ancestors should contain all its necessary assumptions). Vertices that are "a priori" (e.g.. assumptions given in the question, definitions, etc.), should not have ancestors. Your final output will be an adjacency list.
Next, I'll give you some examples to make this clear.
Question: How many vertical asymptotes does the graph of y . have?
claim 1: A function has vertical asymptotes exactly where its denominator equals zero. claim
2: To solve for the vertical asymptotes of the function y प. we therefore must solve
2 + 1 0. claim 3: For all real values of x, x² + 1 > 0 claim 4: Thus, conclude that the function y = . has no vertical asymptotes.
Desired Output: [[0, 0, 0, 0 [1, 0, 0), 00 1,
0) 0 1,10
Commentary:
You should output an object like the one above without any other reasoning or formatting. In particular, you should output array of arrays, each of length n, where is the number of claims. If claim relies on the information from claim i, the jth array should have the ith entry I; otherwise this entry should be zero. In this case, note that claim does not have ancestors,
20

---

Published as a conference paper at ICLR 2025
because it does not require other steps to be justified (we assume common mathematical the- orems, like the presence of vertical asymptotes when the denominator is zero, to be a priori). However, claim 2 relies on the conclusion of claim since it sets the denominator equal to zero. claim 3 implicitly relies on claim 2, since we derive this check from claim 2. Also, the final answer, claim 4, relies combining information from both claims 2 and (which describe the significance of the equation x²² +1+ = 0 and its answer, respectively). Also note that in generat- ing this graph, we represent implicit relationships between claims: claim 4, for instance, does not cite claims 2 and 3 explicitly, but it certainly relies on their contents. For this reason, we put those edges in its adjacency list. way. In general, it is unlikely that claim should be completely "floating" (not relied upon by or reliant upon another claim); in this case, would not be contributing to the complete output.
very important to represent all relationships in this
By convention, we never include claim in its own adjacency list (we do not consider claim to rely on itself).
Here, we're interested in the dependency between claims, not just the correctness. For this reason, it's also important to represent these dependencies even in case that an answer is wrong.
I'll give you another example below.
Question: Consider the function y = x.2 + 2r 15. What is the sum of the zeroes of this function?
claim 1: The zeroes of function are the x-values of its x-intercepts. claim 2: To find the zeroes
of y = _² + 2x + 15, we set the right hand side equal to writing x² + 2x + 15. claim 3: To solve
2² + 2r + 15, we factor it as 0 (æ 3) 5). claim 4: This means that the zeroes of y = _² + 2x 15 are x = 3, claim 5: We conclude that the sum the zeroes of this function is -3 +++0
Desired Output: [[0. 0, 0, 0, 0). 1.0 0. 0. 1.0.
0j. 0, 0, 0,
Commentary:
Here, each claim simply relies on the previous claim. Importantly, claim makes an algebraic eπror, incorrectly factoring as 0 (z + 3) 5) instead of 0 = (x - 3) +5, which means the final answer is wrong. Even so, this claim relies on information from claim 2, and claim 4 represent these edges in final output. We are agnostic to correctness, and focus solely on the reliance between claims. If claim makes use of claim j. even incorrectly, claim j should be ancestor of claim our adjacency list.
relies the conclusion from claim 3,
Now, I'm going to give you another question and list of claims, as before. With all of this explanation in mind, want you to output an adjacency list with no other reasoning.
1aama-3.1-70B-Isttruu Llama had difficulty with this task, especially replicating the di- mensions of the adjacency list, so we reworked the few-shot prompt and gave more explicit in- struction. Despite our best efforts, it occasionally output cyclic graphs, in which case we simply considered the trivial "linear" graph (1 ~o 2 ~o ne n); our empirical results suggest that, while imperfect, its graphs were still useful.
You are system designed to create dependency graphs for subclaims in response given question. Your output must strictly adhere to the following instructions:
1. Graph Description:
Represent the dependency relationships between subclaims as a directed graph.
Each subclaim is a vertex in the graph.
An edge (b + a) exists if subclaim "a" depends on subclaim "b."
Subclaims that are "a priori" (e.g., assumptions definitions) should not have any ancestors.
2. Output Format:
Provide your graph as an adjacency list of size NUM x NUM, where NUM is the number of subclaims (this will be given at the beginning of the prompt).
21

---

Published as a conference paper at ICLR 2025
Each entry in the adjacency list is list of integers:
A value of at position in row j indicates that subclaim j depends on subelaim i. A value of 0 indicates no dependency. Ensure claim depends on itself (diagonal entries must be 0),
3. Rules: The adjacency list must be square, with n rows and n columns, where n is the exact number of subclaims provided. Each row and column must be exactly integers. Do not include extra rows, columns, or misaligned entries. The output must consist solely of the adjacency list (e.g., [[O, 0J, O0 0, 1], [0, 0, OJ)); do not include explanations, commentary, any other formatting.
4. Dependencies:
Consider explicit and implicit dependencies between subclaims. For example, if subclaim implicitly relies on subclaim (even if not stated directly), include the edge j) in the graph.
Always represent dependencies, even the subclaims are incorrect or contain logical errors.
Examples:
Input:
Question:
How many vertical asymptotes does the graph of = =x/(2²² + have?
NUM = Subclaims:
1. A function has vertical asymptotes exactly where its denominator equals zero.
2. To solve for the vertical asymptotes of the function = x/(x² +1), we therefore must solve
x² + 1 = 0.3. For all real values of x² + 0.
4. Thus, we conclude that the function y = x/(x²² + 1) has no vertical asymptotes.
Desired Output: [[0.0.0,00 00000011100000011110000001011110
Input:
Question: Consider the function y x² 22 15. What is the sum of the zeroes of this
function?
NUM 5
Subclaims:
1. The zeroes of function are the x-values of its z-intercepts.
2. To find the zeroes
= x² + 2r + 15, we set the right-hand side equal to 0, writing
. + 2r 15.
3. To solve 0 = x² + 2x + 15, we factor it as 0- = (r + (x 5).
4. This means that the zeroes of x² + 2r 15arer -3
5. We conclude that the sum of the zeroes of this function is -3 5
Desired Output: [0000000110000000000000000000000
Now provide your adjacency list for the following question and subclaims:
K.2 SELF-CONSISTENCY (FREQUENCY) SCORING PROMPT
You will get a list of claims and piece of text. For each claim, score whether the text sup- ports, contradicts, or is unrelated the claim. Directly return a jsonl, where each line is "Td''ICLAIM_DD ID] "score":[SCORE]] Directly return the jsonl with no explanation or other formatting. For the (SCORE), return 1 for supports, for contradicts, and for unrelated. The claims are: (CLAIMS)
K.3 RE-PROMPTING WITH FILTERED OUTPUT PROMPT
am going to give you question some starter work. Please fill in the starter work to provide complete answer to the question. Question: [QUESTION], Starter Work: [STARTER_WOS _ORK]
22

---

Published as a conference paper at ICLR 2025
L COMPARING OUTPUTS GENERATED FROM INDEPENDENT FACTUALITY AND COHERENT FACTUALITY
L.1 MATH DATASET OUTPUTS
Example
Question: Solve for w and express as a common fraction: 1
42
Independent Factuality:
Coherent Factuality:
1. Multiplying both sides by gives 1
Multiplying both sides by w gives 1
42
w
2. Simplifying the right side gives 1 14w.
2. Converting 1 to an improper fraction gives 14w.
3. Converting 1 to improper fraction gives 1 14w.
23

---

Published as a conference paper at ICLR 2025
Example
Question: Mr. Madoff invests 1000 dollars in a fund that compounds annually a constant interest rate. After three years, his investment has grown to 1225 dollars. What is the annual interest rate, as percentage? (Round your answer to the nearest integer.)
Independent Factuality:
Coherent Factuality:
the formula, A is the amount of money accumulated after years, in- cluding interest.
1. The formula for compound interest is
A
2. In the formula, A is the amount of money accumulated after n years, in- cluding interest.
2. In the formula, Pis the principal amount (the initial amount of money).
3. In the formula, P is the principal amount (the initial amount of money).
3. the formula, r is the annual interest rate (in decimal).
In the formula, rate (in decimal).
the annual interest
4. In this case,
1225, P 1000.
n 1. and = 3 years.
5. In the formula, is the number of times that interest compounded per year.
5. Substituting the given values into the formula, we get: 1225 = 1000(1 r/1)2=3
6. In this case, A 1225, P 1000,
= 1, and / = years.
7. Substituting the given values into the formula, get: 1225 1000(1 r/1)
6. Simplifying the equation, we get:
1225 1000(1 + r)
7. Dividing both sides by 1000, get:
8. Simplifying the equation, we get: 1225 1000(1+
1.225 = (1+
9. Dividing both sides by 1000, we get: 1.225 (1 +r)
8. Taking the cube root of both sides, we
get: 1.07 = + T.
10. Taking the cube root of both sides, we get: 1.07 = +.
9. Subtracting 1 from both sides, we get:
r 0.07.
11. Subtracting from both sides, we get: 0.07.
10. The annual interest rate 0.07, or 7% when expressed percentage.
12. The annual interest rate is 0.07, 7% when expressed as a percentage.
11. Rounded to the nearest integer, the nual interest rate is 7%.
13. Rounded the nearest integer, the an- nual interest rate is 7%.
Example
Question: What is the smallest real number r in the domain of the function
g(x) = / (xx 3) (x - 8)2
Independent Factuality:
Coherent Factuality:
The expression under the square root must be nonnegative.
1. The expression under the square root must be nonnegative.
2. We must have (x - 3) - (x 8)2 2
2. We must have (s 3)2 (sr 8)2 > 0.
3. This simplifies (x - 3 8x
3. This simplifies to (x 3 + x - 8)
3 (x 8)) 2 0.
(a 8)) 2 0.
11
4. This further simplifies to (2x 11 11)(5) 2
4. The smallest such x
0.
24

---

-9 p-2' Published as a conference paper at ICLR 2025
Example
Question: If (2x + (2 3) = 14, find the sum the possible values of x.
Independent Factuality:
Coherent Factuality:
1. The expanded equation simplifies to
1. The left side of the equation is expanded
2x
to 2x + 5x 15 = 14
2. The expanded equation simplifies to 2r - 29 0
2. Vieta's 's formulas are used find the sum of the roots of the equation
3. Vieta's 's formulas are used to find the sum of the roots of the equation
3. The sum of the roots of the equation is
4. The sum of the roots of the equation is
Example
The points (x,, y) represented in this table lie on straight line. The point (13, g) lies on the same line. What is the value of p + g? Express your answer as decimal the nearest tenth.
Question:
I
5
P
- 14
p + 2
- 17
Independent Factuality:
Coherent Factuality:
1. The slope of the line is calculated
1. The slope of the line is calculated as (1 -3 p+2-p p
-17- =3
p+2-p
The slope of line is also calculated
(-(-5)
9+5
2. Setting these two slope equations equal gives
13-2
II
3. The slope of the line is also calculated as -14-(-5)
3. The slope of the line also calculated as q (-5) 9+5 11
4. Setting this slope equation equal -3
13-2
gives ワ
9+5 II.
5. Setting these two slope equations equal gives
Setting this slope equation equal to = gives マ
2+5 IT
L.2 FELM DATASET OUTPUTS
Example
Question:
Jessica makes $2,000.00 month. She sets 25% of her paycheck aside to put towards fancy shoes. Each pair shoes she buys costs $1, 51,000.00. How many shoes can she buy in year?
Independent Factuality:
Coherent Factuality:
1. Jessica sets aside 25% of her paycheck, which is: $2,000.00 x 0.25 = $500.00
1. Jessica sets aside 25% her paycheck, which is: $2,000.00 0.25 $500.00
2. To figure out how many pairs of shoes she can buy in a year, need multi- ply the number of pairs she can buy in month by (the number months in year):5500.00 x 12 $6,000.00.
2. So Jessica can buy pairs shoes in a year with the money she sets aside from her paycheck.
25

---

Published as a conference paper at ICLR 2025
Example
The ratio of men to women on a bus is 5:9. If the total number of passengers on the bus is 84, and 20 women alight from the bus the next stop, how many women have remained on the bus?
Question:
Independent Factuality:
Coherent Factuality:
1. If the total number of passengers on the bus 84, then each ratio unit represents
1. The total ratio of men and women on the bus is
14.
84 passengers.
2. If the total number of passengers the bus is 84, then each ratio unit represents
14
2. The number of women on the bus
6 passengers.
is 9 units x passengers/unit
3. The number of women on the bus is 9 units x 6 passengers/unit
54 passengers.
54 passengers.
3. If 20 women alight from the bus, then the number of women remaining the bus is 54 20 = 34 women. Answer: 34
4. If 20 women alight from the bus, then the number of women remaining on the bus is 54 20 34 women. Answer:
34
Example
Question: John injured his back and needs go physical therapy. He went physical therapy for 6 weeks. Each week he went twice for 2 hours at time. If the sessions cost $125 per hour how much did the physical therapy cost?
Independent Factuality:
Coherent Factuality:
1. He went to therapy 2 < 6 2
1. He went to therapy 6 x 2 =<< x 2
12 >> 12 times.
12 > 12 times.
2. Each session cost 2 125
$ <<
2. So he paid 250 x 12 = $ < 250 12
x 125 = 250 >> 250.
3000 > 3000.
3. So he paid 250 12 <
250 x
3000 > 3000.
3. Answer: 3000
4. Answer: 3000
26

---

Published as a conference paper at ICLR 2025
M INDEPENDENT FACTUALITY BASELINES
We also report the baseline results of independent factuality as (Mohri & Hashimoto, 2024) for the problems analyze; these plots analogous those report in Section 6.
Independent Factuality Percent of Claims Kept
independent Error Rate vs.
1.0
Indege Calibration
Percent of Cleins Reteined
0.9
Nanusi Calérstton (Gold)
Draph calibradion (siver)
0.75
Conformal Rounds
0.7
independent Factuality
0.20
0.6
0.5
010
0.3
0.2
0.5
0.75
0.60
0.85
0.90
0.95
Independent Factuality
365
0.10
0.15
0.20
0.25
0.30
Independent Factuality calibration
(b) Percent of claims kept vs. independent factuality Figure 8: These figures depict the performance of independent factuality calibration validated against independent factuality. We can see that the calibration guarantees still hold and useful pro- portions of claim retention, however, as claims may still be retained despite claims that preceding it being deemed as incorrect, this does not reflect our coherent definition of factuality.
(a) Calibration plot
N LEGIBILITY RESULTS
To measure legibility, we asked GPT-4o and Llama-3.11700 1-70B-Instruct to grade outputs as erroncous or factual.
All queries were at temperature = O. We considered all outputs across a = 0.1, 0.1, 0.15, 0.2 for which (1) 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 't. The task was error detection, "false positive" means GPT graded output containing
when it didn't. t.
1. GPT-4 outputs, GPT-4o as judge
Table 2: Results of legibility experiment with LLM-as-a-jude with method.
Outcome
Proportion
True Positive
0.22
True Negative
0.59
False Positive
0.17
False Negative
0.02
Table 3: Results of legibility experiment with LLM-as-a-judge with the baseline, independent fac- tuality method.
Outcome
Proportion
True Positive
0.17
True Negative
0.46
False Positive
0.32
False Negative
0.05
27

---

Published as a conference paper at ICLR 2025
2. GPT-4 outputs, Llama-3.1-00B-Istttee judge
Table 4: Results of legibility experiment with LLM-as-a-judee with our method.
Outcome
Proportion
True Positive
0.15
True Negative
0.61
False Positive
0.15
False Negative
0.10
Table 5: Results of legibility experiment with LLM-as-a-jucd with the baseline, independent fac- tuality method.
Outcome
Proportion
True Positive
0.10
True Negative
0.54
False Positive
0.24
False Negative
0.12
3. Llama-3.1-70B-Instrrutt outputs, GPT-4o judge
Table 6: Results of legibility experiment with a--jugee with our method.
Outcome
Proportion
True Positive
0.08
True Negative
0.64
False Positive
0.26
False Negative
0.03
Table 7: Results of legibility experiment with LLM-as-aajudge with the baseline, independent fac- tuality method.
Outcome
Proportion
True Positive
0.06
True Negative
0.53
False Positive
0.36
False Negative
0.05
4. Llama-3.1-70B-Instuue outputs, Llamm-3.1-70B-Insttee judge
Table 8: Results of legibility experiment with LLM-as-a-judgee with our method.
Outcome
Proportion
True Positive
0.03
True Negative
0.83
False Positive
0.08
False Negative
0.08
28

---

Published as a conference paper at ICLR 2025
Table 9: Results of legibility experiment with LLM-as-a-judge with the baseline, independent fac-
tuality method.
Outcome
Proportion
True Positive
0.03
True Negative
0.78
False Positive
0.11
False Negative
0.09
Grading Prompt:
Given the prompt: [prompt]
Do the following subclaims contain any errors?
[Subclaims separated by newlines]
Respond with exactly one character: either 'Y' for 'there's an error' or 'N' for 'no error.'
29


Reviews:
[{"review_id": "1NczQvhTJH", "reviewer": "Reviewer_wbML", "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.", "questions": "As mentioned above, are there any results from experiments using a human annotated ideal graph other than GPT-4o?\n\nAlthough 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?\n\nAre there extra qualitative results for other datasets (e.g., FELM)?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "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.\nThis 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.\n\"Our definition of deducibility graphs permits the arbitrary treatment of claims that do not follow from the\nground truth\".\nSimilarly, 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.\n\nAdditionally, 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GAbX40UKoU", "reviewer": "Reviewer_DfTB", "summary": "The paper defines “coherent factuality” and develops a conformal-prediction\u0002based 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.", "questions": "see the weaknesses.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 2, "presentation": 3, "contribution": 3, "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-prediction\u0002based 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.\n\nThe paper uses GPT4o to generate the graphs, but the quality of the graphs is unknown.\n\nIn 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?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "UdAcZNf9XV", "reviewer": "Reviewer_D79W", "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.", "questions": "1. Why do you use \"median\" in LINE 361? And how do you select the hyper-parameter $\\beta$?\n2. 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\")?", "limitations": "", "rating": 6, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "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.\n2. 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:\n    * One key property of the ideal graph is it uses the \"minimal set of the claims\". However, this is only mentioned in the appendix.\n\t* What is the \"graph G\" at LINE 350? Is it the corresponding subgraph to each node?\n\t* LINE 402 points to appendix F, but appendix F does not contain the prompts.\n\t* Figure 4(b) and 4(c) use the same title. This is confusing and seems to be typos.\n\t* What is \"Descendants weight boosting\" in LINE 501?\n\t* What is \"independently filtered outputs\" in LINE 509?\n\t* What is \"self-consistency scoring\" in LINE 970?\n\t* I don't understand the sentence from LINE 316-318.\n\t* 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.\n2. 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.\n3. 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.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)