Understanding the Uncertainty of LLM Explanations: A Perspective Based on Reasoning Topology
Authors: Longchao Da
Xiaoou Liu
Jiaxin Dai
Lu Cheng
Yaqing Wang
Hua Wei
Venue: COLM 2025 (2025)
Keywords: Uncertainty Quantification
LLM Explanations
Graph Mining
TL;DR: A framework quantifies uncertainty in LLM explanations through a formal reasoning topology perspective.

Abstract: Understanding the uncertainty in large language model (LLM) explanations is important for evaluating their faithfulness and reasoning consistency, thus providing insights into the reliability of LLM's output. In this work, we propose a novel framework that quantifies uncertainty in LLM explanations through a formal reasoning topology perspective. By designing a structural elicitation strategy, we can decompose the explanation into the knowledge and reasoning dimensions, which allows us to not only quantify reasoning uncertainty but also assess knowledge redundancy and provide interpretable insights into the model’s reasoning structure. Our method offers a systematic way to interpret the LLM reasoning process, analyze limitations, and provide guidance for enhancing robustness and faithfulness. This work pioneers the use of graph-structured uncertainty measurement in LLM explanations, offering a new perspective on evaluating and improving reasoning capabilities.

Published as a conference paper at COLM 2025
Understanding the Uncertainty of LLM Explanations: A Perspective Based on Reasoning Topology
Longchao Da", Xiaoou Liu', Jiaxin Dai*, Lu Chengt, Yaqing WangS, Hua Weit* t "Arizona State University, #University of Illinois Chicago, SPurdue University {longchao, xiaoouli, jdai33, hwa.weii www. @@su.. edu [lucheng /@uic.eduu (wang5075]@purduee
Abstract
It is important to understand the uncertainty in large language models (LLMs) explanations because they reveal more information about the rea- soning process and thus provide insights into the reliability of LLMs' an- swers regarding a question. In this work, we propose novel framework that quantifies uncertainty in LLM explanations through reasoning topolo- gies. By designing a structural elicitation strategy, we guide the LLM to frame the explanations on how it derives the answers into graph topologies. This strategy first queries knowledge-relater sub-question and sub-answer pairs, and then guides the LLM to connect the pairs through topologi- cal reasoning process. Based on the reasoning topologies, we revisit the Graph Edit Distance and provide variant that can better quantify the LLM uncertainty from both semantic and reasoning structure dimensions. The topology structure further brings convenience to assess red redundancy by extracting and comparing the valid reasoning path to the raw explanation. Extensive experiments show the effectiveness of the proposed framework, and interesting findings on reasoning patterns and efficiency are discussed.
1 Introduction
Deep learning models have long been criticized for their lack of trustworthiness due to the complex network structures and opaque decision-making processes (Li et al., 2022; Deshi-Velez & Kim, 2017; Samek et al., 2021). This has motivated researchers to investi- gate methods for understanding and quantifying the uncertainty associated with these models (Abdar et al., 2021; Loquercio et al., 2020; Maddox et al., 2019). Recently, Large Language Models (LLMs) have demonstrated ted significant advancements over traditional deep learning approaches across a variety of tasks (Zhao et al., 2023; Naveed et al., 2023). However, concerns about their reliability persist. LLMs often produce outputs that are difficult to verify, particularly in scenarios requiring complex reasoning (Shi et al., 2024). This introduces risks in critical applications, such as healthcare or legal contexts (Cascella et al., 2023; Jayakumar et al., 2023), where incorrect or unreliable reasoning can have severe consequences. Properly quantifying uncertainty in reasoning is crucial for ensuring safe and trustworthy reference.
Existing research on Uncertainty Quantification (UQ) for LLMs primarily focuses on analyz- ing semantic uncertainty (Kuhn et al., 2023; Lin et al., 2023; Qiu & Miikkulainen, 2024; Da et al., 2024), which involves examining patterns from the meaning of multiple responses generated for given question. Although this can provide insights into output-level variabil- ity, overlooks the structural characteristics the reasoning process that give rise to such uncertainty. In other words, existing UQ methods do not model how uncertainty emerges and propagates through intermediate reasoning steps, which hinders practitioners' analyses, understanding, and potential reaed improvement. For instance, in Figure. (right), when asked the same question, In part & answer-based UQ can not reveal the vulnerable parts in the reasoning path, which are contained in the reasoning steps as in part @
* *Corresponding Author

---

Published as a conference paper at COLM 2025
Proxy Based (Explain)
Question
Direct Measure
Reasoning Explonations
DIBI
Answort Anzwor2
Black Box
Explor
Figure 1: The comparison of Answer-based-UQ measures and Proxy (Explanations)-basee UQ measures. The Explanations-basee approach reveals more reasoning information.
By quantifying uncertainty at the reasoning dimension, we can effectively detect inconsisten- cies in intermediate steps, support human-in-the-loop validation in sensitive applications, and uncover vulnerabilities within the reasoning process itself. This underscores the impor- tance of reasoning-awar uncertainty quantification. this paper, we address this challenge by explicitly modeling reasoning processes as logical topologies. While prior work treats (CoT) sequence as monolithic response (Wei et al., 2022; Wang et al., 2023) and measures semantic consistency at the output level, such approaches fail to capture the structural complexity of real-world reasoning, which frequently involves hierar- chical dependencies and parallel sub-tasks. To overcome these limitations, introduce formal topology that represents reasoning as a logical graph, where nodes correspond to individual reasoning steps and edges encode their logical dependencies. This graph-based structure enables finer-grained, more interpretable uncertainty analysis.
single
Based the structural representation, introduce a graph-based measure for assessing uncertainty, by first encoding the node and edge descriptions into the semantic embeddings, and then performing graph-edit-distance comparison, our framework captures the uncer- tainty from both semantic and topology aspects. Besides, we also propose redundancy measure for the valid reasoning path, which helps understand the LLM's reasoning effec- tiveness. Extensive experiments on diverse datasets and LLMs demonstrate the utility of the proposed quantification methods. In summary, the contributions of this paper are:
We identify limitations in existing answer-based UQ approaches for LLMs and propose a novel topology-elicitation framework that explicitly models the reasoning process from explanations logical topology.
We introduce Topo-UQ, topology-bases uncertainty measure from both semantic meaning and reasoning structure to show granular thinking variance. We also propose redundancy metric based valid reasoning paths and raw explanations.
We demonstrate the effectiveness of our framework through extensive experiments across multiple datasets and LLMs. Our results highlight its ability identify inconsistencies in reasoning paths, improving trustworthiness and interpretability. Additionally, we discover three widely adopted reasoning patterns in LLMs and show the chance of improvement under the redundancy measure.
2
Related Work
In this section, review the related work in the research domains of uncertainty quan- tification (UQ) for large language models (LLMs) and methods for explanation-base UQ, with focus on reasoning processes.
2.1 UQ for LLM
White-box Approaches A significant body of research has focused on performing UQ for LLMs by inducing the models to output their uncertainty along with their responses Ka- davath et al. (2022); Lin et al. (2022); Mielke et al. (2020); Tian et al. (2023). These methods often rely on token-level probabilities to train or fine-tune models for predicting uncertainty. While effective, these approaches require full access to the model's structure and weights,
2

---

Published as a conference paper at COLM 2025
which is impractical for black-box commercial LLMs. For example, supervised methods such as those in Kadavath et al. (2022) estimate uncertainty using logits and ground truth labels but are computationally expensive and resource-ineessive.
Black-box Approaches Another line of work estimates uncertainty directly at the response level using semantic entropy Kuhn et al. (2023). While this method avoids token-level dependencies, still relies on access to token probabilities, limiting its applicability in black-box settings, To address these limitations, researchers have proposed lightweight black-box methods that analyze response inconsistencies. For instance, Lin al. (2023)
uses graph Laplacian eigenvalues as an uncertainty indicator, while Chen & Mueller (2023)
computes confidence scores from generated outputs to identify speculative or unreliable answers. However, these approaches primarily focus on semantic-level analysis and neglect the logical structure underlying reasoning processes. Moreover, methods like Lin al. (2023)
average entailment probabilities without considering directional information in reasoning paths.
Our work is agnostic to the white box or black box since it leverages the generated explana- tions as a proxy to measure the reasoning uncertainty as in Figure. 1. This enables a more nuanced and interpretable assessment of uncertainty in reasoning processes.
2.2 UQ for LLM Explanation
Explanation-based UQ focuses on assessing the reliability of natural language explanations (NLEs) generated by LLMs by either prompting models to express confidence in their expla- nations or analyzing consistency across multiple outputs under varying conditions Tanneru et al. (2024); Yadkori et al. (2024). While these methods provide insights into explanation robustness, they treat explanations
question as unstructured text representation, which lacks structural information and fails to capture inconsistencies or leaps in logic. In con- trast, our work explicitly leverages well-structured reasoning topologies to enhance the UQ process for explanations. This structured representation enables to assess explanation uncertainties at a finer granularity within complex reasoning paths.
3 Preliminaries
This section provides the foundations for our study, including the definition of uncertainty in LLMs and its quantification in natural language explanations (NLE) fashion.
3.1 Uncertainty Quantification of LLMs
Uncertainty, as inherent attribute of LLMs, can arise from various aspects: training corpus coverage (Huang et al., 2023), prompt ambiguity (Abbasi Yadkori et al., 2024), the probabilistic nature of language generation (Lin et al., 2023), and many more. Effectively modeling and interpreting uncertainty are essential for reliable and trustworthy references; thus, researchers quantify the uncertainty for better decision-making.
Different from UQ methods in classical machine learning (Lakshminarayanan et al., 2017; Gal & Ghahramani, 2016; Hernández-Lobate
Adams, 2015; Abdar et al., 2021), UQ in LLM faces unique challenges such as discrete token-based generation, the large combinatorial output space, and expression diversities of the same concept, thus, most LLM-UQ methods responses as shown in @ in Figure. 1.
focus on analyzing uncertainty from The problem could be defined as follows:
Problem 1 (Uncertainty Quantification for LLMs). The LLM 'M' is provided with input query x9, the goal of the uncertainty function Uş is to map the generated outputs to a scalar score
that determines the uncertainty of the M, i.e. Ux = U ===--n(( ((M(x)))
3

---

Published as a conference paper at COLM 2025
Here, {M(x)) denotes set of n responses' generated by the model M, and U aggregates uncertainty across multiple responses. Uy is calculated only on x and is a property of the predicted distribution, which is estimated by U. For black-box methods that analyze response variability or semantic consistency (Lin et al., 2023), multiple outputs (n > 1) are typically required. In contrast, white-box methods that rely internal model parameters, such as logits (Kadavath et al., 2022), may only require a single output (n = 1). However, both current answer-based black-box Lin et al. (2023); Chen et al. (2025); Su et al. (2024) and white-box methods Margatina et al. (2023); Duan et al. (2024); Kadavath et al. (2022) share limitations in the quantification of reasoning procedures in that they focus on semantic variability without capturing deeper uncertainties in reasoning steps.
3.2 Uncertainty of LLM Explanations
To address these issues, researchers try to understand uncertainties in reasoning processes through the natural language explanations (NLEs) as a proxy, introduced by Camburu al. (2018); Tanneru et al. (2024). As shown in the green part (2) of Figure. 1, an NLE is a textual reasoning sequence generated by a language model M, to justify or explain the derivation of answer a for given input question 19. Following the existing work, it is defined as:
Definition (Natural Language Explanation). Given a model M and an input query x9, an
NLE can be represented as:
(1) where x" is an explanation-specife prompt, a is the model's answer to the query x9, and al the generated explanation accompanying the answer. The explanation af contains sequence of reasoning
M(x² + =
steps, represented as a" = $2,,,,. which capture the reasoning process or justification for a.
To quantify uncertainty through explanations, we extend Problem to consider n explana- tions generated for the same query x Each explanation of (i E {1,2,... n1) corresponds to a set of reasoning steps, assuming steps, then we denote them as of = / Sim The overall uncertainty across all explanations is captured by aggregating reasoning-level uncertainties for each explanation. This can be formally defined as:
Problem 2 (Uncertainty Quantification for LLM Explanations). Given an input query x9 and an explanation-specife prompt x², the model M generates set of answers aj the query x9, along with accompanying explanations af. The uncertainty for the query x9 is then defined as:
11 U, =4 (44) (Uaa) =u
(U simm)
(2)
i=1
where Uga represents the overall uncertainty for the query 24, and U aggregates uncertainties across all reasoning steps from all n explanations.
Unlike prior methods that focus on answer-based output variability (Tanneru al., 2024), in this paper, we aim to capture nuanced uncertainties from the reasoning process, which brings advantages in analyzing the reasoning patterns and logical errors. In the next section, we will introduce Topo-UQ, including how to model reasoning structures within explanations, and how this graph-based UQ method works with the extracted structures.
4 Method
In this section, we propose a reasoning Topology-based method for Uncertainty Quantification of LLMs, named Topo-UQ. To capture the complexity of reasoning paths, the proposed framework consists of two modules: (1) Reasoning Topology Elicitation, which constructs structured reasoning graph from LLM-generated explanations, and (2) Topology- based UQ, which leverages the constructed graphs for uncertainty quantification using variant of graph edit distance. We also present a byproduct- a metric of reasoning path re- dundancy inspired by the analysis of reasonable reasoning paths and original explanations.
Answers and responses used interchangeably in this paper.
4

---

Published as a conference paper at COLM 2025
Ti Reflection
Topelogy Const.
Question
Ogg 0100 (2,
g
Encoder
p
g
Uncertainty
LLM
Tg Answering
GED
E,
Topology Elicitation
Uncertainty Quantification
(podltion::
Re looieell: Mere u destralla lecate Eartk?
E
nodefow
nodlbow
b (ndge: J- Whor ir Casoda lncand on Fant?"
Mrodattens enfoe hode frodettons sdge, note,l (noda, edpe, nodley. (nade, edge, nodayl (nodls, edpe, nodea). (node, edpe, notehesut]]
odges
b (ndged) What a the geogrphecal reisnorriy boteoue Assonalia and Covadis? A (edged Hore daer the til the Earth affect reaross!
Sedgo, nodba. (nter, rode, lodpe, nodeai. jedge, nodea)l
hodtl
edpe:
Southere
Topa.
cage,
Casaad
Norbhre Hestighhre.
|nadee]: It
sppostte homigehory
[rodee] Oppontee kemupphres esparience opponti
sil
nodeResult
Bookiltont or Staer
Figure 2: An overview of Topo-UQ. It depends on two modules, ! Topology Elicitation and @ Uncertainty Quantification Start from D, given an input question x9, the LLM not only generates the answer a but is also elicited to provide reasoning explanations. It first reflects the necessary knowledge points (k,,) as sub-questions and then answers them as (ax), T1 and T2 are the prompt templates. These sub-question and answer sets form the edge and node sets E, V, creating matched pairs. By inserting node into an (edge-node) pair, the LLM constructs the reasoning topology G. When we have L explanations, their topologies are used to estimate Uncertainty through module @ we encode the content from each node and edge into embedding space to capture semantic meanings, and apply variant of Graph Edit Distance to measure structural variance, then the final uncertainty combines both semantic and structural differences. An example is shown at the bottom.
4.1 Reasoning Topology Elicitation
The objective of this step is to derive structured reasoning topology that captures the complexity of reasoning paths generated by large language models (LLMs). Existing approaches by Tanneru et al. (2024) represent reasoning explanation as linear sequences of steps from Chain-of-Thought (CoT) (Wei et al., 2023). While linear text sequences provide basic interpretability. they fail to capture complex logical transitions tasks like comparan comparative reasoning multi-faceted conclusive answering. This lack of structural richness limits their ability to analyze and quantify uncertainty in LLM-generated reasoning processes.
To address these limitations, we propose to elicit reasoning topologies from question X₂ to directed graph G (V,E), where V is the set of nodes corresponding to knowledge points or intermediate steps, and the set of edges capturing logical dependen- cies between them. The & includes two advantages: First, it can represent diverse structures, not limited to the linear sequence COT. Second, the construction is done by the LLM itself, thus it can flexibly reflect the thinking process for each answer. For example in Figure. 2, given the query x²: " If it is currently Summer in Australia, what season is it in Canada? ", the knowledge points might include sub-questions such as kg: 'Where is Australia located on Earth?', K₁: 'Where is Canada located on Earth?', k2: 'What is the geographical relationship between Australia and Canada?' and k3: 'How does the tilt of the Earth affect seasons?'. The corresponding answers A = {eg, #1, 22, 4z} demonstrate thoughts of LLM for sub-questions. These knowledge-answer pairs are then connected based on their logical dependencies to form the reasoning topology graph G. The connection becomes step from a; to aj: S = a;;; a; E V ki E E}
answer
Specifically, the construction of G consists of three steps: (1) Knowledge Point Reflection, where the LLM identifies sub-questions of knowledge points kn required to address the query as elicited by the template ;ú; (2) Self-Answering Module, based on the sub-questions among k,, the LLM generates answers for them, denoted as an in this process, template T2 carries the question variable which can be changed according to different sub-questions; up to
5

---

Published as a conference paper at COLM 2025
this point, there is intermediate set containing pairs (kn, (n), which will be used for (3) Reasoning Topology Construction. In this part, the knowledge-answerr pairs are connected into directed graph that reflects the overall reasoning process. It mainly requires insertion from the current node-edge pair to a prior node, which is identified by LLM itself. The detailed explanations of every module and prompt templates are introduced in the Appendix. B.
4.2 Topelogy-based Uncertainty Quantification
With the Topology Elicitation module built, we intend to understand the uncertainty from the elicited structural explanations. Given query x", the model M will be asked I. times, from which reasoning topologies 1 will be extracted. We propose UQ method: Reasoning Graph Edit Distance, namely Reason-GED, to evaluate the consistencies of [2 from the semantics embeddings of node, edge sentences, and structural topologies.
If we apply the traditional graph distances (Bai et al., 2020; Huang et al., 2024; Guzman- Pando et al., 2024) that solely quantify the differences in structures, we will lose the node and edge meaning implied in the structure. To understand the structural variance without loss of semantic meaning, we first encode the node and edge content into semantic embeddings.
Step1: Semantic Embedding. To measure semantic meanings of reasoning steps, for each graph (V, E {9 we employ an embedding function L to encode the content of nodes and edges in graph. Since the content of each node u E V and edge E & is textual description, we can derive embeddings:
(3) This paper adopts BERT as the embedding function L, but other embeddings could be preferred for different domain contexts, e.g, (Rasmy et al., 2021) for medical text. The encoded graph G' is shown in the gradient color of @ in Figure. 2. This obtains the semantics of nodes and edges while preserving the logical structure of the reasoning process.
h = [(v), L()) V
Step2: Reasoning Distance from Topology and Semantic. In our setting, we have L reasoning structures ( generated. To measure the pairwise distance of two reasoning processes 9, and G2, inspired by the concept of graph edit distance (Gao et al., 2010), we use the minimum transformations (substitution, deletion, insertion) required align the two graphs as their pairwise distance.
A. Substitution Costs: For two corresponding (edge, node) pairs in different topologies 91 E1,,E) and G2 = E2),E2) we define the semantic substitution cost based on (2, ei) V1, and (z),e;) E V22 E2:
( cos(L(e)),
cos cos(h,, h(), edge substitute
cf (e),)))
(4)
cos(C(t)), = ch h3),
node substitute
where cosine similarity measures the semantic alignment of two reasoning edges and nodes. c(.. is high, this indicates: either given a similar edge (sub-question) the nodes (sub- response) are different there might exist an incorrect sub-answer, or difference starts with edges, which follow up with different responses there is a different reasoning path or jumping step. The examples for these cases are shown in Appendix C.1.
B. Deletion/Insertion Costs: In order to decide which node / edge to delete or insert to align two reasoning topologies. We define the deletion and insertion costs. For node dj E V in graph G1 (V, relative to target graph G2 (22,E2)
Cdet. (v;) = max cos (C(v)), + 2 1,Eo2
Σ cos ((b)) (5) NEV
V1
Cross-graph Matching Term
Internal Uniqueness Term
2(n,, an) (edge, node)

---

Published as a conference paper at COLM 2025
The Eq. 5 jointly considers the cross-graph matching cost and the internal uniqueness cost when deleting node Vi. In the cross-graph matching part, if v; has a very similar counterpart 0; in 92, then deleting 8 would lose important alignment information; thus, high similarity here leads to higher deletion cost. In the uniqueness part, if v; is very similar (i.e., redundant) to many other nodes, the average similarity will be high, making this term low. In other words, deleting a redundant node is less costly, Otherwise, if oj is unique, deletion is costly. Since the insert. is a reverse action of delete., they share the same equation. The above defines the cost function for node, the same applies to edge er complete Eq. 19 is in Appendix C.2.
Graph Distance for Reasoning Uncertainty. Based on the above two steps, we can derive the overall graph edit cost in joint consideration of semantic meaning and topology variance as: GED(G,, 92) Ssub. (P) Cael the P represents the optimal matchings for sub-questions (edges Pe) and sub-responses (nodes Pt), using the Hungarian algorithm (Mills-Tettey et al., 2007), details are explained in the Appendix. H.1. We can calculate the minimal total cost of transformations by finding:
Step3:
GED GEDm(991 92) min GED(G1,
(6)
Given this, a higher GED implies a higher difference in the reasoning phase by considering both embedding and structures. We use this computed reasoning distance and construct matrix across L reasoning structures 19,,92.... , G,), we compute pairwise distances using:
d;j ,ED, m (9,, Gy), which then forms the overall distance matrix between L reasoning
topologies as shown on the right of Figure. 2: D = [dp] = (GED Gj)laxt. Now, we
can calculate the Topo-UQ by the variance of the distances in D&=, which reflects instability of the model's reasoning behavior. Combining Eq. 2, we have the uncertainty score over query x as: Usuraa (x9) Var (ar(D))) A higher variance indicates greater inconsistency in the model's reasoning, suggesting that the LLM generates more different structures across multiple responses to the same query.
4.3
LLM Reasoning Redundancy Measure
is known that the LLM's reasoning efficiency varies based on the problem type and model weights (Plaat et al., 2024), and the reasoning topology provides a good reference to understand the efficiency by analyzing the valid reasoning path. We find that LLMs do not necessarily rely on all of the nodes from their reasoning topology for the final conclusion, which means some the sub-steps do not contribute to solving a problem, and this causes the decreased efficiency. Here, we propose measurement named 'Reasoning Redundancy'. Reflect the reasoning steps: S - {[d;, by, cijl d E V,ei E E}, we aim to measure the redundancy based on the valid path constructed by the steps.
Definition (Redundant Node). node U2 E V is redundant if does not contribute to the reasoning path from nodeRaw to RedeResult. Formally, redundant node satisfies:
Uk &
U [OLRHAA] Priidd
where P Poulia represents the set of all valid paths contributing the final conclusion, nodeRaw and nodeResult are the initial reasoning question and result, respectively, as in Figure. 2.
Given the definition, it is feasible to detect the redundancy following the criteria in Ap- pendix H.2, we perform the searching for P Poslid valid paths and 'Redundancy Rate' using traversal algorithm (DFS), then we have the redundancy rate of the reasoning process for af:
| [eedundant
Fredun. (nf)
(8)
[V]
where the | is the total number of nodes in the reasoning topology, and |V /redundant| is the number of redundant nodes (isolated from valid reasoning path).
7

---

Published as a conference paper at COLM 2025
5 Experimental Study
In this section, we conducted extensive experiments covering LLMs: GPT4o-mini,
DeepSeek-RI (distilled on Ilama3-70b), Phi4, Llama3-8b, Llama3-70b (v3.3), 3 classic datasets, and UQ methods. We intend to answer the following research questions:
RQ1: Can Topo-UQ reveal the actual uncertainty in LLM's reasoning?
RQ2: How do LLMs perform in the proposed redundancy measure?
RQ3: From the proposed topology reasoning elicitation, do LLMs share certain patterns commonly?
5.1 Experiment Settings
Dataset: In this study, align with the research community (Mirzadeh al., 2024; Tosh- niwal et al., 2024; Zhang et al., 2024), we utilized widely adopted datasets, including GSM8k (Cobbe et al., 2021) and BoolQ (Clark al., 2019), which require complex reasoning rather than simple question-answering, These benchmarks assess LLM's ability to perform multi-step inference and logical reasoning. Besides, we also develop new dataset, GeoQA, especially for condition-based reasoning tasks. We will explain the details of the GeoQA dataset in Appendix E and provide a brief introduction of all datasets in Appendix 1.1
Baselines: To the best of our knowledge, few works focus on the uncertainty quantification of natural language explanations (NLE), thus, we included all possible baselines: (1) Chain- of-Thought Agreement (CoTA) (Tanneru et al., 2024), (2) Embedding distance-based UQ for NLE (Embed-UQ), (3) Entailment probability-based (Entail-UQ), and (4) NLI-logit based UQ, our extra baselines to understand their interpretability of LLM explanations. We provide a brief introduction here, and for the detailed explanation of baselines, please refer to Appendix. G.
To evaluate the performance of uncertainty quantification methods in LLM explanation tasks, follow the standard practice that compares uncertainty results with actual faithfulness (Tanneru et al., 2024). The ground truth faithfulness score reveals how much the model relies on its complete reasoning process, which is calculated through strategy named 'Early Answering' as proposed by (Lanham et al., 2023), We provide details on how the faithfulness score is derived in Appendix I. Ideally, UQ method is good in NLE if, for a higher faithful set, it generates lower uncertainty, and vice versa (Tanneru et al., 2024). Hence, we employ three robust statistical metrics to quantify the correlation between the derived uncertainty and faithfulness. Including Pearson Correlation Coefficient (PCC), which is used to measure the linear correlation between two variables. Given the relatively small amount of each bootstrap sample, employ two extra metrics, Spearman Rank Correlation (SRC) and Kendall Rank Correlation (KR); the calculation of metrics is also in the Appendix]. J.
Evaluation and Metrics:
For fair evaluation and to avoid bias, we conduct a bootstrap for a given dataset Djest and measure the correlation between uncertainty and faithfulness score each sub-set D' level. The sub-set is cut as 20 questions with 10 responses for each question = 200 a and bootstrapping conducted 1000 times on each dataset.
5.2 Quantitative Evaluation (RQ1)
In order to understand if Topo-UQ can reveal the uncertainty LLMs' reasoning, we perform experiments on GSM8K, BoolQ, and GeoQA datasets. Due to the page limit, GSM8K and BoolQ are shown in the Table. 1, GeoQA shown in Appendix, Figure. 4. Our method reveals a stronger negative correlation between the derived UQ results and the groundtruth faithfulness across different statistic metrics, the results on GPT4o-mini, Llama3-70b, and DeepSeek-R1 are more convincing because they have a more stable performance on the Topology elicitation task as in Figure. 6, which, is a key step for the proposed UQ method, the performance Phi4 and Llama3-8b not promising as ranked in the last two positions
8

---

Published as a conference paper at COLM 2025
Methods
GPT
DeepSeokeRi
Liuna3-80
POC())
SRC(J)
KR(()
PCC()) SRC(L) KR(.)
PCC())
SXC(1)
KR(L]
PCC(4)
SRC1))
KR(()
PCC(.)
S8C(()
KR(()
Datasel: BoolQ
Colik
0.55
0.08
0.00
.0.22
.0.0
-0:33
-0.00
0.05
0.5
-2.07
-8336
-0.0
0.88
0.07
0.15
Umbod-UQ
0.36
0.18
0.12
[156
1036
0.09
0.12
0.8
0.91
0.06
0.01
0.00
0.02
0.01
EnteilUUO
0:46
-005
-0.08
-0.0
NLIlogit
0.39
0.38
0.7
.3.1
2001
GSM8K
CoEA
.0.12
-0.10
00.0
-043
-.14
-0.3
Embee-UO
.0.12
-0.10
-0.07
0.09
0.30
0.07
0.15
0.14
0.30
0.23
0.23
0.15
0.28
0.28
0.19
Enteil-UQ
0.34
0.34
0.09
0.68
0.66
0.47
0.15
0.13
0.99
-0.05
-0127
-0.05
0.00
0.17
0.15
NLH-lgit
0.00
0.01
0.01
0.10
0.11
0.07
0.13
0.12
0.08
0.21
0.19
0.13
0.29
0.29
0.20
Ours
40.35
-0.34
-0.23
-022
+0.00
4.14
-0.85
+041
40.28
-0314
-0.33
40.08
0.12
0.10
0.06
Table 1: Comparison of our methods with different baselines various datasets and large language models. The results show that our results consistently outperform the baseline methods. The value reflects the correlation between the uncertainty and the ground truth faithfulness; the more faithful an LLM performs, the less uncertainty it should have, so by the UQ methods, we would expect negative correlation for well-performed UQ method.
in Appendix Figure. 6. This RQ result shows our method is effective in revealing the LLM's real faithfulness, yet it is more suitable for LLMs with good instruction-folloving abilities.
5.3
Redundancy Measure of LLMs (RQ2)
(%)
Average Node Redundancy
Topology Clustering
80
Dimension
40
0-
DeepSock Llama3 70b
Phi4
Laama3-8b
Dimension
Figure 3: The left side shows the quantification of the LLM's reasoning redundancy three datasets: GeoQA (Blue), GSMSK (Yellow), BoolQ (Purple); The right side shows the clustering result of the reasoning topologies.
Benefitting from the topology structure, we are able to extract the reasoning path Pvalid that successfully connects from nodeRaw to nodeResult. Then, effectively search the node that does not contribute to the final answer, which serves as sign of redundancy in the reasoning process. Following the Eq. 8, we analyze the redundancy rate for each of the five LLMs on both the node and edge redundancy. Since the node and edge always show up together in our setting, their redundancy results are very similar, we just present redundancy on the 'node' level for conciseness in the left part of Figure. 3. We find that, surprisingly, the GPT-4o-mint shows a significantly high redundancy rate both the nodes and edges, which might reveal that the high accuracy of the model comes from broader searching space (or generating length) when conducting reasoning and proposing solutions. However, this also reflects that there would be great potential to optimize the reasoning process for the GPT-wise models. Comparatively, the DeepSeek (distilled llama version) is relatively low, which might indicate the model's training was conducted with special design to encourage the 'valid' reasoning, which eventually contributes to the final result. We show more results in the appendix for reference.
5.4 Findings on the Reasoning Patterns from LLMs (RQ3)
Based on the topology representations, we conducted further analysis in structural patterns, we use Graph2Vec (Narayanan et al., 2017) to embed the graph structure information, such as node connectivity, and perform K-means clustering on 4 classes and obtained silhouette score of 0.38, as shown in right part of Figure. 3, we found three major reasoning patterns of the L.LSs (in color- red, green, purple on the right side of Figure. 3), they correspond with:

---

Published as a conference paper at COLM 2025
① Completion-based the model has seen the data in the training phase, and completes it as a 'cloze question'. For example, given the question that provides a feature of climate type, and asks for the answer as shown in Figure. 4, then in the sub-question step, the LLM directly asks 'Does object A have such a feature?', it shows a one-step, direct answer which possibly comes from the training memorization. @ Forward reasoning (actual reasoning): The model is actually performing reasoning based on the analysis procedure, like human beings, given a question, it first recalls relevant concepts and knowledge that contain the necessary information. Then, through a step-by-step narrowing-down process, it refines its understanding, gradually converging on the most precise answer. @ Combination of Memory-based answering, forward reasoning (o + @ + verify: The model uses two methods and double-checks verify the answer. Three modes are shown Figure. 4. We hope this could serve as an inspiration for the potential further study in answer topology.
Three Types Reasaning Patterns LLMs:
Q: "If place receives less than 250 of precipitation annually, what climate does it likely have?" (nodeRaw)
Ac "Arid"
Pattern:: Completion based Reasoning
Pattern2: Forword Reasoning
Pattern3: Combination i Veeilly
RodeRaw
Givnn (baaaadd) wnkh
nodeRaw
-Gleen [eaturs] mak for
nodeRaw
eminer?
node
node;
node,
Peoject how, (he
rolivint kowlecgo concest, namov down, confinn.
(11) lses Bii Bislodon cart emower?
nodey
nodeResult
modey
nodielesult
Cordiaiin
nodey
nodieflesult
dy Whatis the Breshnul of and precipaa fot
t. delindins
byeen?
lees 200 and 2290
rode:
ditied evss wich knoue
mustrogl cal 1.000 000 remo, and topiical war Jover 2,000 mer)
What
node,
phatton th 200 and cackened boutus))
by
eu Muru deeeeataaaiti of uxiff taaaacllcaareeees shens
nods.
wdaayy the cunsiion? (oadiese
Whalls fraal arower? node And
by www. answer??
node-eesut: And
Hhe modll SESNNS beiceion mewoonationnnoo cossnee
Brower EAN500 In ettuedl rel Insweesk
Figure 4: The examples of three types of reasoning patterns. As shown in the image, the first type directly reflects the correct answer in its first reasoning step, and not actually performing the reasoning, the second type is like humans, try to recall the knowledge points, and narrow down the range, and find the possible answer in a thought chain, while the third one is combination of two, it has the steps to ask for characteristics, but it also try to reflect if it has seen this question before at the edge 1, which is direct attempt to use answer to match the question, the last step is to confirm if the memory of answer matches the requirement in the question.
Conclusion
In this paper, we introduce a novel framework Topo-UQ to quantify the uncertainty of LLMs' reasoning through the explanations. By designing a reasoning topology elicitation module, we tackle the challenge of shaping the structural reasoning process of LLMs. Then, based on the constructed topologies, the paper provides a 'graph edit distance' based un- certainty measure named Reason-GED. It considers both the semantic meanings of the reasoning steps and the structural topology variance, by a set of well-designed operation costs: substitution and deletion (insertion), we can effectively quantify the reasoning un- certainty. The empirical studies show that this method provides better performance in revealing the true faithfulness of the natural language models. Besides, this paper also introduces a aeduuddncy-basee method to quantify the conciseness of the L.MMs' reasoning process, which could potentially serve as guide for improving reasoning efficiency.
Limitations: Although the Topo-UQ shows an interesting direction (topology structure) to quantify the LLM reasoning uncertainty, it requires the LLMs to come with good instruction- following ability. Thus, this method is more applicable to larger models with long-context reasoning capabilities. Besides, the current method is validated by the faithfulness, but it does not concern the answer's 's correctness from the reasoning path; analyzing the uncertainty relevant to the correctness would also be beneficial for woal-world use-cases.
10

---

Published as a conference paper at COLM 2025
Ethics Statement
This paper focuses on the uncertainty quantification of the LLM explanations. The data adopted are the widely acknowledged public datasets, and contain no ethics sensitive information, which has no ethics concerns.
Reproducibility Statement
This project will release the codes for the topology elicitation that is used for uncertainty quantification, and we conducted pre-processing for the three datasets, which will also be updated to the repository: http:s////t.t...o////o/oooo///// wowp/oongghhaoD///LMooooooooo.
References
Yasin Abbasi Yadkori, Ilja Kuzborskij, András György, and Csaba Szepesvari. To believe or not to believe your Ilm: Iterative prompting for estimating epistemic uncertainty. Advances in Neural Information Processing Systems, 37:58077-58111 2024.
Moloud Abdar, Farhad Pourpanah, Sadiq Hussain, Dana Rezazadegan, Liu, Mohammad Ghavamzadeh, Paul Fieguth, Xiaochun Cao, Abbas Khosravi, U Rajendra Acharya, et al A review of uncertainty quantification in deep learning: Techniques, applications and challenges. Information fusion, 76:243-299 297, 2021.
Yunsheng Bai, Hao Ding, Ken Gu, Yizhou Sun, and Wei Wang. Learning-based efficient graph similarity computation via multi-scale convolutional set matching. In Proceedings of the AAAI conference on artificial intelligence, volume 34, pp. 3219-3226, 2020.
Oana-Maria Camburu, Tim Rocktäschel, Thomas Lukasiewicz, and Phil Blunsom. e-snli: Natural language inference with natural language explanations. Advances in Neural Information Processing Systems, 31, 2018.
Marco Cascella, Jonathan Montomoli, Valentina Bellini, and Elena Bignami. Evaluating the feasibility of chatgpt in healthcare: analysis of multiple clinical and research scenarios. Journal of medical systems, 47(1)333, 2023.
Jiuhai Chen and Jonas Mueller. Quantifying uncertainty in answers from any language
model and enhancing their trustworthiness. 2023.
Tiejin Chen, Xiaoou Liu, Longchao Da, Vagelis Papalexakis, and Hua Wei. Uncertainty quantification of large language models through multi-dimensional responses. arXiv preprint #xXi::2502.16200 2025.
Christopher Clark, Kenton Lee, Ming-Wel Chang, Tom Kwiatkowski, Michael Collins, and Kristina Toutanova. Boolq: Exploring the surprising difficulty of natural yes/no questions, 2019. URL https://arxiis wwwpxxivv.org//eee org/abs/ /atss//995 195., 10044.
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworek, Jacob Hilton, Reiichiro Nakano, Christopher Hesse, and John Schulman. Training verifiers to solve math word problems, 2021. URL 14168.
https://arxxv.oor/altt
Longchao Da, Tiejin Chen, Lu Cheng, and Hua Wei. Lim uncertainty quantification through directional entailment graph and claim level response augmentation. arXiv preprint arXiv:2407.00999, 2024.
Finale Doshi-Veles and Been Kim. Towards a rigorous science of interpretable machine learning. arviv preprint ar Xic::1702.08608 2017.
Jinhao Duan, Hao Cheng, Shigi Wang, Alex Zavalny, Chenan Wang, Renjing Xu, Bhavya Kailkhura, and Kaidi Xu. Shifting attention to relevance: Towards the predictive un- certainty quantification of free-form large language models. In Proceedings of the 62nd
11

---

Published as a conference paper at COLM 2025
Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 5050-5063, 2024.
Yarin Gal and Zoubin Ghahramani. Dropout bayesian approximation: Representing model uncertainty in deep learning. In international conference on machine learning, PP- 1050-1059. PMLR, 2016.
Xinbo Gao, Bing Xiao, Dacheng Tao, and Xuelong Li. A survey of graph edit distance.
Pattern Analysis and applications, 13:113-122 2010.
Abimael Sluzman-Pandee Graciela Ramirez-Alonso, Carlos Quinata- and Javier Camarillo-Cisseros. Deep learning algorithms applied to computational chemistry. Molec- ular Diversity, 28(4) 2410, 2024.
Esmael Hamuda, Brian Mc Ginley, Martin Glavin, and Edward Jones. Improved image processing-based crop detection using kalman filtering and the hungarian algorithm. Computers and electronics in agricullure, 148:37-44, 2018.
Pengcheng He, Xiaodong Liu, Jianfeng Gao, and Weizhu Chen. Deberta: Decoding- enhanced bert with disentangled attention. Xrv preprint arXiv:2006.03654, 2020.
José Miguel Hernándezz-Lobato and Ryan Adams. Probabilistic backpropagation for scalable learning of bayesian neural networks. In International conference on machine learning, PP. 1861-1869. PMLR, 2015.
Di Huang, Jinbao Song, and Yu He. Community detection algorithm for social network based on node intimacy and graph embedding model. Engineering Applications of Artificial Intelligence, 132:107947, 2024.
Yuheng Huang, Jiayang Song, Zhijie Wang, Shengming Zhao, Huaming Chen, Felix Juefei- Xu, and Lei Ma. Look before you leap: An exploratory study of uncertainty measurement for large language models. Xiv preprint arXiv:2307.102366 2023.
Thanmay Jayakumar, Fauzan Farooqui, and Luqman Farooqui. Large language models are legal but they are not: Making the case for powerful legaillm. arXiv preprint :xii:2311.08890, 2023.
Saurav Kadavath, Tom Conerly, Amanda Askell, Tom Henighan, Dawn Drain, Ethan Perez, Nicholas Schiefer, Zac Hatfield-Dodds, Nova DasSarma, Eli Tran-Johnson, al. Language models (mostly) know what they know. arXiv preprint arXio:2207.05222 2022.
Lorenz Kuhn, Yarin Gal, and Sebastian Farquhar. Semantic uncertainty: Linguistic in- variances for uncertainty estimation in natural language generation. arXio preprint arXit:2302.09964, 2023.
Balaji Lakshminarayanan, Alexander Pritzel, and Charles Blundell. Simple and scalable predictive uncertainty estimation using deep ensembles. Advances in neural information processing systems, 30, 2017.
Tamera Lanham, Anna Chen, Ansh Radhakrishnan, Benoit Steiner, Carson Denison, Danny Hernandez, Dustin Li, Esin Durmus, Evan Hubinger, Jackson Kernion, et al. Measuring faithfulness in tfain-of-thought reasoning. ar arviv preprint arXiv:2307.13702 2023.
Xuhong Li, Haoyi Xiong, Xingjian Li, Xuanyu Wu, Xiao Zhang, Liu, Jiang Bian, and Dejing Dou. Interpretable deep learning: Interpretation, interpretability, trustworthiness, and beyond. Knowlledge and Information Systems, 64(12):3197-3234 2022.
Stephanie Lin, Jacob Hilton, and Owain Evans. Teaching models to express their uncertainty in words. arXiv preprint ar Xii::2205.1433. 2022.
Zhen Lin, Shubhendu Trivedi, and Jimeng Sun. Generating with confidence: Uncertainty quantification for black-box large language models. ar Xiv preprint arXim:2305.19188 2023.
12

---

Published as a conference paper at COLM 2025
Antonio Loquercio, Mattia Segu, and Davide Scaramuzza. A general framework for uncer- tainty estimation in deep learning. IEEE Robotics and Automation Letters, 322:3113--1100 2020.
Wesley J Maddox, Pavel Izmailov, Timur Garipov, Dmitry Vetrov, and Andrew Gordon Wilson. A simple baseline for bayesian uncertainty in deep learning. Advances in neural information processing systems, 32, 2019.
Katerina Margatina, Timo Schick, Nikolaos Aletras, and Jane Dwivedi-Yu. Active learning principles for in-context learning with large language models. In Findings of the Association for Computational I Linguistics: EMNLP 2023, pp. 5011 1-0044,,, 2023.
Sabrina J Mielke, Arthur Szlam, Y-Lan Boureau, and Emily Dinan. Linguistic calibration through metacognition: aligning dialogue agent responses with expected correctness. ar Xiv preprint ar arXiv:2012. 14983, 11, 2020.
G Ayorkor Mills-Tettey, Anthony Stentz, and M Bernardine Dias. The dynamic hungarian algorithm for the assignment problem with changing costs. Robotics Institute, Pittsburgh, PA, Tech. Rep. CMU-Ri- 2007.
Iman Mirzadeh, Keivan Alizadeh, Hooman Shahrokhi, Oncel Tuzel, Samy Bengio, and Mehrdad Farajtabar. Gsm-symbolic: Understanding the limitations of mathematical reasoning in large language models. arXiv preprint ar arXiv:2410.05229 2024.
Annamalai Narayanan, Mahinthan Chandramohan, Rajasekar Venkatesan, Lihui Chen, Yang Liu, and Shantanu Jaiswal. graph2vec: Learning distributed representations of graphs. Xix preprint arXiv:1 0tff::1707.000000 2017.
Humza Naveed, Asad Ullah Khan, Shi Qiu, Muhammad Saqib, Saeed Anwar, Muhammad Usman, Naveed Akhtar, Nick Barnes, and Ajmal Mian. A comprehensive overview of large language models. arXiv preprint vrXiv:2307.66433 2023.
Aske Plaat, Annie Wong, Suzan Verberne, Joost Brockens, Niki van Stein, and Thomas Back. Reasoning with large language models, a survey, 2024. URL //atps://axxiv... org/abs/ 2407. 11511.
Xin Qiu and Risto Miikkulainen. Semantic density: Uncertainty quantification semantic space for large language models. arv preprint ar 25Xiv:2405.13845, 2024.
Laila Rasmy, Yang Xiang, Ziqian Xie, Cui Tao, and Degui Zhi. Med-bert: pretrained contextualized embeddings on large-scale structured electronic health records for disease prediction. NPJ digital medicine, 4(1):86, 2021.
Wojciech Samek, Grégoire Montavon, Sebastian Lapuschkin, Christopher J Anders, and Klaus-Robert Müller. Explaining deep neural networks and beyond: review of methods and applications. Proceedings of the IEEE, 109(3):247-278, 2021.
Quan Shi, Michael Tang, Karthik Narasimhan, and Shunyu Yao. Can language models solve olympiad programming? aixiv preprint ar Xii:22404.1092,, 2024.
Jiayuan Su, Jing Luo, Hongwei Wang, and Lu Cheng. Api is enough: Conformal predic- tion for large language models without logit-access. In Findings of the Association for Computational Linguistics: EMNLP 2024, pp. 979-995, 2024.
Sree Harsha Tanneru, Chirag Agarwal, and Himabindu Lakkaraju. Quantifying uncertainty in natural language explanations of large language models. In International Conference on Artificial Intelligence and Statistics, pp. 1072-1080. PMLR, 2024.
Katherine Tian, Eric Mitchell, Allan Zhou, Archit Sharma, Rafael Rafailov, Huaxiu Yao, Chelsea Finn, and Christopher D Manning. Just ask for calibration: Strategies for eliciting calibrated confidence scores from language models fine-tuned with human feedback. Xiv preprint ar XrXit:2305.14971 14975, 2023.
13

---

Published as a conference paper at COLM 2025
Shubham Toshniwal, Ivan Moshkov, Sean Narenthiran, Daria Gitman, Fei Jia, and Igor Gitman. Openmathinstruct-ll A 1.8 million math instruction tuning dataset. arviv preprint (#Xiiv2402210176, 2024.
Hongru Wang, Rui Wang, Fei Mi, Yang Deng, Zezhong Wang, Bin Liang, Ruifeng Xu, and Kam-Fai Wong. Cue-cot: Chain-of-thoure prompting for responding to in-depth dialogue questions with llms. arXiv preprint arXivv2305.11792, 2023.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc Le, Denny Zhou, et al. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824-248871 2022.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Brian Ichter, Fei Xia, Ed Chi, Quoc Le, and Denny Zhou. Chain-of-thought prompopp elicits reasoning in large lan- guage models, 2023. URL https///araivvorr/aab///22 119933
Yasin Abbasi Yadkori, Ilja Kuzborskij, András György, and Csaba Szepesvári. To believe or not believe your 11m. ar preprint ar (tte:24000025443 2024.
Hugh Zhang, Jeff Da, Dean Lee, Vaughn Robinson, Catherine Wu, Will Song, Tiffany Zhao, Pranav Raja, Dylan Slack, Qin Lyu, et al. A careful examination of large language model performance on grade school arithmetic. arxiv preprint ar fae:2405.0032,, 2024.
Wayne Xin Zhao, Kun Zhou, Junyi Li, Tianyi Tang, Xiaolei Wang, Yupeng Hou, Yingqian Min, Beichen Zhang, Junjie Zhang, Zican Dong, al. A survey of large language models. ar Xie preprint ar arXiv:2303.16223, 2023.
14

---

Published as a conference paper at COLM 2025
A
Notation Table
In this section, we provide a comprehensive notation table as shown the Table.
Notation
Explanation
U,
Uncertainty function
M x
Large language model
Input(query or prompt)
U
Aggregation
19 x
Input prompt
Explanation-specifie prompt
LLMs answer
a²
Generated explanation accompanying the answer
Reasoning step
g (V,E)
Directed reasoning graph
V
Set of nodes
Number of nodes
g
Set of edges
[3]
Number of edges
Cjj
Edge from node to node j
K T Dm
Knowledge points
Prompt template
Set of knowled pairs for reasoning topology
(i)
Knowledge-answer pairs
ef
Sampling amount of edges
F C(-) h (-s(.)
Demonstration set Embedding function Contextual embedding
Cosine similarity
P
Optimal matching for sub-questions Graph edit distance between G, and Gi Redundancy rate
djj rredun.
Table 2: The notations and explanations in this paper.
B Reasoning Topology Costruction Process in Detail
B.1 Knowledge Point Reflection Module
The first module, the knowledge point reflection module, involves eliciting sufficient infor- mation that can be used to support the conclusion drawing toward the input x9, The input to this module the input query along with the prompt template T₁ to encourage the LLM to reflect 'What knowledge basis (or sub-questions) it should know to draw a final conclusion?'. And the output of this module is the set of knowledge points K9 extracted as series of sub-questions, i.e., K? T, to guide the model in reflecting on the sub-questions or knowledge points required for solving x
Specifically, we design a prompt template
Template Tj: Given question {x*)), reflect and generate the knowledge points sub-questions necessary solve this query. Ensure that the output both sufficient and concise.
The model generates set of knowledge points K M(x9, Ti) (ki,,,,... k kn), where each k; corresponds to a specific sub-question or piece of information identified as necessary to address the query x4 under the guidance of prompt Ty. To ensure traceability, we assign unique identifiers to each knowledge point using a tagging function f(-):
Kiag
iid; k, id2 k2...., id, kz)-
(9)
In the later sections of this paper, we assume the kl always carries its identifier while performing computing (K? + K)
15

---

Published as a conference paper at COLM 2025
B.2 Self-answering Module
To provide answers for the knowledge points K = (k1, kn) elicited in the previous module, we design a self-answering module to generate precise answers. For each sub- question k; E K9, the model M generates an answer d using the following prompt T2, ensuring coherence and sufficiency in addressing each of the knowledge points:
Template T2: Given sub-question (ki), provide precise answer that directly addresses the query without further discussion.
The model generates answers (41,42...., where each answer a; M(k, T2). So have:
A = (2,,0)....,, an} = (2) T2) M M(kn, T2)}
(10)
This formulation explicitly links each sub-question k; to its corresponding answer ensur- ing clarity in the relationship between the elicited knowledge points and their responses. The resulting set of knowledge-answer pairs forms the basis for constructing the reasoning topology:
Dm = { a1), (k2, (5,.a))..... (kn)a))
(11)
B.3 Reasoning Topology Construction Module
To construct the reasoning topology graph gV = E), a critical step would be to connect the (k, a) pairs in a structured format based on their logical dependencies. Since we are quantifying the uncertainty of LLM explanations, this connection should be determined by the model itself explain. Therefore, ability of LLMs and guide them in connecting the basis (k, a) pairs following their reasoning procedure. By sampling F amount of e as few-shot examples from demonstration set J and feeding them the model, the LLM learns to depict the reasoning path in a structured way for this task3: D'm = MMDm,, e the transformation from Dm to Dm follows:
this module, we leverage the few-shot learning
Dm M(D ef) {(aP) (aP),,s a1), (a?2, k2) (a"h kn, an))
(12)
where each aPi an answer node that connects to the corresponding knowledge-answer pair ak),
To ensure that the reasoning path forms a structured yet flexible topology that adapts to the complexity of real-world cases, the specific ordering of p; is not predetermined and depends on the actual reasoning structure generated by the model. Then for better illustration, we switch the order in the tuple below, by applying graph concepts, have the first two as the 'node' positions and the last as the 'edge' position:
(a"), 01,
(13)
nodes
edge
where the order of two nodes is defined by the reasoning LLM. Now, we can write basic reasoning step as:
Step,; [node; edge,; node]]
(14)
where node; is the starting node representing either a question, sub-question, or an intermediate response, node; is the resulting node from node; and connected by edge, which serves as the reasoning operation or sub-question.
Specifically, for the initial input query Xg, we denote the node as nodeRaw; for the final answer a, we denote nodeResult. All other steps in the middle are the reasoning process, with clearly defined structure. The final graph structure includes all reasoning steps from query
Pllease find details of few-shot learning in Appendix.
16

---

Published as a conference paper at COLM 2025
x to the final answer nodes (0;) and their dependencies edges (eij): The reasoning
process from query of to the final answer can be finalized as directed graph structure
9 (V,E),
(15)
where
V {nodeRaw, node,, nodeResult) = {vo, U1.-..}
(16)
and the edges expressed as:
& ((())))(((())
(17)
where stands for edge and {eij edge; node; + nodej), eij represents reasoning operations or dependencies between nodes. (start with index '1' since we assume '0' is the nodeRaw). The graph-based structure captures the full reasoning topology, including branching, dependencies, and multi-step interactions, which allows for better reflection of the relationships between intermediate steps.
Now, from a graph concept, the reasoning steps combined with Eq. 14 are formalized as below:
(18) where each triplet represents a logical transition between reasoning steps. Note that for complex reasoning, the final answer does not necessarily rely on all of the reasoning steps. For example, when being asked about "If it is currently summer in Australia, what season in Canada?" in the reasoning chain, some of the LLM might delve into 'what causes the season differences, wwhich is redundant step in concise reasoning.
S = {Step Step;j = [1t, eij, oyl0,, E V,ej E
C
More Studies for Reasoning Graph Edit Distance
C.1 The case behind high Csub.
Example1:
diel Where Australl located barth??
Whereis Canada louted oe tatt??
0i- when Auttmila oo Eurs?
G Where is Canada lncated oe Cart?
bastail Souther
Heriipheen
sppocte ferricstones esperience
rpportte sestoed?
one courtry Equane Yerent seaumu seme
and other thr i. cortey howe tecessary seastaryy thiy could come season
You because of darividd. ressornn??
Whut wwwsonsiiiiiioo...
wivter Canada Topiingy!
aley v.l. (yy vall 0, clei ez) the cost comes from the divergence of the answers from same sub aub-question:
Civy vy)
Figure 5: The example of the cause of substitution cost: same sub-question, divergence answers.
C.2 The complete equation of deletion/insertion cost
Similarly to Eq. equation for nodes, we define the deletion cost for an edge e; E & in
graph &1 EV) relative to the target graph G2 (V2, Eg) as:
(ei)
max cos (C(ei), + 1
Σ cos ((e))) (19)
2 G
6//
Cross-graph Matching Term
Internal Uniqueness Term
The Eq. equation 19 jointly considers the cross-graph matching cost and the internal unique- cost when deleting edge e,-
17

---

Published as a conference paper at COLM 2025
Cross-graph Matching Term:
max cos (C(e)), eyEt2
measures the highest semantic similarity between the edge in 91 and any edge ej in the target graph G2. If e; has very similar counterpart in E2, deleting it would remove important alignment information, leading higher deletion cost.
Internal Uniqueness Term:
1
cos (L(e)),((ez))
calculates how unique edge e; is within its own graph 91. If is very similar (i.e., redundant) to many other edges, the average similarity will high, making this term low; in other words, deleting redundant edge is less costly.
Thus, the overall deletion cost for edge ej is the average of these two terms.
D Related Work
In this section, we review the related work in the research domains of uncertainty quan- tification (UQ) for large language models (LLMs) and methods for explanation-based UQ, with focus on reasoning processes.
D.1 UQ for LLM
White-box Approaches A significant body of research has focused on performing UQ for LLMs by inducing the models to output their uncertainty along with their responses Ka- davath al. (2022); Lin et al. (2022); Mielke et al. (2020); Tian et al. (2023). These methods often rely on token-level probabilities to train or fine-tune models for predicting uncertainty. While effective, these approaches require full access to the model's structure and weights, which is impractical for black-box or commercial LLMs. For example, supervised methods such as those Kadavath et al. (2022) estimate uncertainty using logits and ground truth labels but are computationally expensive and resource-intensive
Black-box Approaches Another line of work estimates uncertainty directly at the response level using semantic entropy Kuhn al. (2023). While this method avoids token-level dependencies, it still relies on access to token probabilities, limiting its applicability in black-box settings. To address these limitations, researchers have proposed lightweight black-box methods that analyze response inconsistencies. For instance, Lin et al. (2023)
uses graph Laplacian eigenvalues as an uncertainty indicator, while Chen Mueller (2023) computes confidence scores from generated outputs to identify speculative unreliable answers. However, these approaches primarily focus on semantic-level analysis and neglect the logical structure underlying reasoning processes. Moreover, methods like Lin et al. (2023)
average entailment probabilities without considering directional information in reasoning paths.
Our work is agnostic to the white box or black box since it leverages the generated explana- tions proxy to measure the reasoning uncertainty in Figure. 1. This enables more nuanced and interpretable assessment of uncertainty in reasoning processes.
D.2 UQ for LLM Explanation
Explanation-based UQ focuses on assessing the reliability of natural language explanations (NLEs) generated by LLMs by either prompting models to express confidence in their expla- nations or analyzing consistency across multiple outputs under varying conditions Tanneru et al. (2024); Yadkori et al. (2024). While these methods provide insights into explanation
18

---

Published as a conference paper at COLM 2025
robustness, they treat explanations to question unstructured text representation, which lacks structural information and fails to capture inconsistencies or leaps in logic. In con- trast, our work explicitly leverages well-structured reasoning topologie to enhance the UQ process for explanations. This structured representation enables us to assess explanation uncertainties at finer granularity within complex reasoning paths.
E Details of the GeoQA Dataset
The GeoQA dataset is designed to evaluate the reasoning capabilities of large language mod- els (LLMs) on conditional geographical questions, emphasizing the comparative reasoning topology of their responses. By anchoring specific knowledge within conditional constraints and requiring models to infer results or solutions, GeoQA enables an in-depth analysis of the reasoning paths taken by LLMs. The dataset spans 20 categories, covering diverse geo- graphical topics such as climate, biome, tectonic plates, continental drift, altitude, sea level, desertification, urbanization, demography, population density, ocean currents, river basin, watershed, mountain range, volcano, earthquake, glacier, permafrost, and monsoon. Each question is crafted to test multi-step reasoning, integration of domain-specific knowledge, and the ability to navigate complex cause-effect relationships, making GeoQA unique and challenging benchmark for geographical reasoning.
F Empirical Study on the Choice of Number for Generations
It is basis setup that need to query LLM M with query x9 for k times and collect set of explanations to perform the NLE uncertainty measure. We have conducted a survey related literature and found there a preliminary study on the number of responses and tried to find the most suitable one (since the larger the response is, the more computationally expensive it will be for later evaluation).
standard definition setting, so conducted
G Details of Baseline methods
G.1 CoTA.
Chain-of-Thought Agreement (CoTA) evaluates the agreement between two Chain-of- Thought (CoT) explanations generated for the same query. Each CoT explanation consists of a sequence of reasoning steps, denoted as:
CoT, = (sat $22 San,,, COT, = (i2,,
The CoTA metric quantifies agreement between the two CoT explanations by calculating the maximum semantic alignment for each step in CoT, with steps in CoT, and vice versa. Formally, CoTA is defined as:
No
CoTA(COT,, CoTb) No + N₂ L....N
1
Σ
max E(SairSb)
(20)
Na
E(Sbj, (ai)))))))
max La.,,Na
where N, and N, are the number of steps in CoT, and CoT, respectively. The entailment function E(s;,s) measures the semantic agreement between two reasoning steps using a Natural Language Inference (NLI) model. It is defined as:
f1, if entails Sj. (0, otherwise.
E(sus;)
19

---

Published as a conference paper at COLM 2025
Table Examples of GeoQA dataset.
Type
Iype Ixplain
Example
glaciers
glacial movementt explore impact climate change dynamics.
what these seratches indicate past
Gladeer
while requitng demands undershading
2: Iia glaierr leses due to melting and sublimation exceeding accumalation, what process occurrng?
imbalance between accurnalation and ablation.
3: If soisanic waves are rocorded by actwork of sestnngraphs which method io used to pingoint the origin the distutbunce?
These questions focus en setemmo wave hehavion, fault activilty and earthquake detectionn.
Trangulation requires rensoning, through
Farthquake
wave arrival times, while P-wwae debection refies comparing wave speeds impast to explain carly warning systems.
earthsuukk early seamning syelems delecting the Powaves, which chanscteratiic waves makes fundblle?
permafrost
rising temperatures, releasing trapped exscobatte?? what
queeiiame permaalesst thawing. climate feedback loeps and varistions
Thawing permufros
permaimost
fooclback snalyzing enviroemental factors like temperature and insolation.
variations
3: If the active laver above permafrost
thicknes seasonally, what faclurs influence depth??
@) If the East Asian mensoon affects countries like China and Japan.
These quaeshoons cover seasonal wind shifts, monsoon pattests, and storm formation.
what two seasons does il primarily indluence?
The East A Asian monseon's impact on scneons involves reasoning about wind shitts, while monsoon depressions require linking low cow-pressure systems to storm lormation.
Monsoon
moneson depressions
Rey Bempel,
what weather womtss might they trigger upon landfall??
The entailment model employs pre-trained NLI models, such DeBERTa (He et al., 2020), fine-ture tuned for evaluating entailment relationships between statements. This binary scoring avoids dependency confidence calibration, and we take the threshold 0.7 to provide the binary cut.
G.2 Embed-UQ.
Embed-UQ measures uncertainty by embedding natural language explanations into semantic space and computing the variance of pairwise distances. Given query x9, let (a.,4,,..., represent explanations generated by the model. Using an embedding function C(-), each explanation of mapped high-dimensional embedding:
h [af)).
The pairwise distances between embeddings are computed as:
d h h,ll,
where dij represents the distance between explanations af and af. The uncertainty is then quantified as the variance of the distance matrix D:
U(x*) = Var(D),
where D [dij 1 i k).
G.3 Entail-UQ.
Entail-UQ modifies the distance computation in Embed-UQ by using an entailment-based similarity measure instead of embedding distances. Given the same set of explanations {at .t,...,af an entailment model computes the similarity between two explanations af and of as:
Sij = E(af, a9),
where E(.,)) is the entailment function that outputs similarity score between 0 and 1. The dissimilarity is then defined as 1 - Sij, and the uncertainty is computed as the variance of
the dissimilarity matrix S:
u (x*)) Var(1 (1+ -S),
20

---

Published as a conference paper at COLM 2025
1.0
Detasets
GAMBK
0.8
GeoQA
0.4
0.2
DeepSock R1(70) Llama3-83
Phi4
Figure 6: The model's success rate to generate legitimate reasoning topology. It is calculated by the percentage LLMs successfully generating the reasoning path from the nodeRaw to nodeResult following the few-shot prompt. It can be witnessed that, generally the GeoQA a harder one to generate due to the conditional question types, which are rarely seen in the LLM training tasks.
where (s1 1 < < k). Similarly to CoTA, in implementation, adopt DeBERTa (He et al., 2020) as the model to generate entailment logit and pass through layer of softmax to transform it into probabilities.
G.4 NLI-logit-UQ.
NT.-logit-UQ is a variant of Entail-UQ that directly utilizes the raw logits from Natural Language Inference (NLI) model to measure uncertainty, without applying the softmax operation. Given the set explanations af,,,,,,,,,44 ) the NLI model computes a raw logit score for each pair of explanations:
lij NL),
where NLI(,.) outputs logit value representing the degree of entailment between of and of
In contrast to Entail-UQ, where these logits are passed through softmax layer to obtain probabilities, the NLI-logit-UQ method uses the raw logits directly. The dissimilarity between explanations can be defined as:
duj 1y-1-14
11-1, lij.
or more generally, the uncertainty computed as the variance of the raw logit values: U(x*) Var((4;) 1 i,j k)).
H Research Methods
H.1 Part One
The final full version of the graph edit distance is below:
GED 92) Csub. (P) + Caei, (1,,,, P)
(21)
where P represents the optimal matchings for nodes (Pa) and edges (Pe), computed using algorithm such the Hungarian algorithm (Hamuda et al., 2018). The term Csub.(?) accounts for substitution costs, defined as:
Csub.(P)
Σ (prP
((,,) + Σ c(evee),
(22)
(MA))P.
21

---

Published as a conference paper at COLM 2025
where c(v,, 17) and cjei, represent the node and edge substitution costs, respectively. The term Cdel. &,,&, P) captures the deletion costs for nodes and edges in 91 that are not matched, given by:
Cael. (P) = Cdel. -Cdel (1, = Σ
Cael. +
Σ QEEEIP.
Cdel. (e:).
(23)
PLEMIPP
Here, (D;) and (e)) denote the deletion costs of unmatched nodes and edges, re- spectively. This formulation quantifies the total cost required to align the two reasoning structures by summing the substitution costs of matched components and the deletion costs of unmatched ones.
H.2 Algorithm for Detection of Redundant Nodes and Dead Branches
To identify redundant nodes and branches of dead nodes in the reasoning topology (y, U4 D4 E Vie } we first define the outgoing edges of a node 2 as: Out(D;) = {oj [8k, ex] E S} Then A node is considered redundant if it has no outgoing edges and is not the final node:
Out(px) Ø and a # NodeResult.
(24)
Then, compute the set of valid paths, Pvalid, connecting NodeRaw to NodeResult using DFS. A node dn E V is redundant it does not appear in any valid path:
Uk E
U
(0g
(25)
[ EPalld
In order more efficiently detect branches of dead nodes (not contributing to the whole reasoning path), let Ug and its parent Up satisfy:
Out(pp) = {ux}. and Up, u &
U
In this case, Dp and Di form a dead branch, as neither contributes to any reasoning path leading to NodeResult. And finally, the redundancy rate is computed as:
redun.(af [eedundantt
[V]
It allows to systematically identify nodes and branches that do not contribute to the reason- ing process, providing insights into the inefficiencies in the model's reasoning topology and we can analyze to understand where we can improve in the model training or fine-tuning process.
Experimental Details
L1 Details of the dataset
GSM8K (Cobbe et al., 2021): This dataset contains 8,000 high-quality math word problems, designed to evaluate LLMs' ability to perform arithmetic reasoning, It is standard benchmark for testing the numerical and reasoning capabilities of LLMs.
BoolQ (Clark et al., 2019): BoolQ is a yes/no guestion-answering dataset derived from naturalistic information-sseeking questions. The dataset is used to evaluate the ability of LLMs to reason logically over textual evidence and produce accurate binary answers.
GeoQA: GeoQA is a self-constructed dataset designed to evaluate the reasoning capabilities of LLMs conditional questions. With 20 categories, including climate and tectonic processes, its tasks require inference of specific results from given con- ditions. GeoQA emphasizes multi-step reasoning and domain-specific integration, making it challenging benchmark (details in the Appendix E).
22

---

Published as a conference paper at COLM 2025
1.2 The calculation of the faithfulness core
In our experiments, we utilize strategy called Early Answering to measure the faithful- ness of the reasoning paths a' = $2,,,2....,, which are generated by the LLM for given query x". This strategy involves truncating the reasoning steps a progressively and prompting the model to answer the query x combined with the partial reasoning path {s1, Sk),, where k E (1,2....,. ].. For example, instead of providing the entire reason- ing x9 + 51 + $2 +..... Sn, the model is prompted to answer using only x s1, X + S1 + 82, and so on, until the full reasoning path reached.
The Early Answering process evaluates how often the LLM's responses, derived from the partial reasoning path $2, Sk, match the final answer a generated using the complete reasoning x + $1 + + ................................ Sn. This evaluation reflects the faithfulness of the reasoning path: if the model consistently reaches the correct answer with partial reasoning, may indicate that the reasoning steps are unnecessary (post-hoc). Conversely, a lower match rate suggests that the intermediate reasoning steps are essential for arriving at the correct final answer, thereby indicating greater faithfulness.
We quantify the faithfulness
Vyath using the following equation:
1
n (f(x + 52 s2.,,2.....)))) a)
ratth 1
(26)
un-faithfullnes
where represents the total number reasoning steps in a², f(x9 + {si, sk, is the LLM's output when prompted with the query x9 and the partial reasoning path {8,, Sk, a denotes the final answer generated using the complete reasoning path, and I[-) is an indicator function that equals if the condition is true (i.e., the partial reasoning output matches the final answer), and 0 otherwise. The Viaith is calculated by
1 un-faithfulness, and the unfaithfulness means: how much the model's final answer (Not) depends on the intermediate reasoning steps, since by removing sub-steps, it still reaches same answer.
A high faithfulness score indicates that the model's final answer is more dependent on inter- mediate reasoning steps, suggesting that the reasoning is not post-hoc, and this faithfully reflects that the logical steps are required to derive the answer, by this high faithfulness, the UQ measure should align with it, in other words, a UQ method is good if it derives lower uncertainty when the faithfulness is high, and vise versa.
J Evaluation Metrics Calculation
Let (xx; } be a set of paired samples, where x; refers to the uncertainty value and yi refers to the ground-truth faithfulness. All three correlation metrics produce values in the range -1,11 1]:
= means a perfect positive correlation,
0 means perfect negative correlation,
= 0 means no correlation at all.
Note: In our setting, a more negative correlation is preferred because we expect higher uncertainty to correspond lower faithfulness (and vice versa).
Pearson Correlation Coefficient (PCC)
E (xi
8) 1)
PXY
V E
(xi -x)2 v
Σ" (y: -
23

---

Published as a conference paper at COLM 2025
8 x; and = E yi are the sample means of X and Y, respectively, This
where I
Σ
i=1 measures the linear correlation between x and y,
Spearman Rank Correlation (SRC)
First, convert each x; and y; into their respective ranks, denoted rank(x;) and rank(y;). Then define
d rank(x;) rank(y:).
The Spearman rank correlation coefficient r3 is given by
6 6-"-1 43 n(n² - 1)
rs
Spearman's method captures the monotonic relationship between the two variables, based on their ranks rather than their absolute values.
Kendall Rank Correlation (KRC)
For each pair (i,f) with < j, define
if > X₁, X
yf Jy>3 yr,
sgn(x; x;) =
xf < otherwise,
sgn vi) =
y otherwise.
0
Then the Kendall rank correlation I can be computed
== n(n - 1) K<j
Σ
Eggn(x x;) sgn(yj yi).
Equivalently, one may count the number of concordant pairs n. and discordant pairs nd yielding
21
n(n - 1)
Kendall's also measures the degree of ordinal association between two variables, similar to Spearman's rank correlation but with a different counting approach.
Methods
CPTio-mini
DeepSook-RR
Liama 3.--0B
PCC[] SRC(I)
KR(()
POC())
SRCIU)
KR[UT
PCCUL
SRC(I)
KR(T)
PCC
SRC(J)
KR[J]
PCE(])
SRC(L] KR[[]
Dataset: GeoQA
CoTA
.0.18
.0.09
-0.12
-0.14
-3.15
0.30
-0.08
-0.04
-0.03
0.01
0.01
0.01
-0.12
-0.04
-0.02
Dmbed-UQ
4.11
.0.0
2010
377
0.6
0.30
-0.0
0.01
0.88
0.89
0.06
-0.01
+000
-001
Betal-UUQ
<0.12
-005
0.6
0.4
0.46
+.25
40.3
-015
.005
.000
-0.04
-0.65
+000
-0.01
Table 4: Comparison of our methods with different baselines on various datasets and large language models. Cont. for GeoQA dataset.
K Time Complexity Analysis
Below we provide an explanation of the time complexity analysis using our Reason-GED: Let: G1, Gn, be the reasoning graphs generated for query Xq- For each pair of graphs Gj and 9j the graph edit distance is computed dij GED(G,
Assume the cost to compute the graph edit distance between two reasoning graphs is TeED- In our approach, we compute this distance for every pair, the amount of such pairs are:
n1
n 1)
(27)
2
2
24

---

Published as a conference paper at COLM 2025
Thus, the overall time complexity for computing all pairwise distances is:
o
n 1).
TCED 0 (n² TCED).
(28)
If each reasoning graph has nodes and the matching step (e.g., using the Hungarian algorithm) requires (m²) time, then: TGED O(m²), so, the total time complexity for estimating the uncertainty for one query is: O (n² m²). If is bounded considered constant, the complexity simplifies to: (n²²
This concludes the mathematical analysis of the time complexity for uncertainty estimation per question when we have n responses.
L Prompt Template & Few Shot Examples
Here we introduce details of the prompt template used in this paper as well as some few-shot examples to guide the LLMs to follow the elicitation process.
25

---

Published as a conference paper at COLM 2025
The Prompt Template to Elicit Knowledge Points.
System Description: You are helpful assistant to do the following: Given question, you should reflect and come up with the sufficient knowledge that you need to solve this question. Two standards: sufficient and concise. And you should respond with numbered points.
Task Description: Given a question: { question i J. Please provide a response following system requirements and learning the format from the example: { few shot example
Example1:
Question: If it is currently summer in Australia, what season is it in Canada?
Expected Response (For required knowledge):
1. Where is Australia located on Earth?
Where is Canada located on Earth?
3. What is the geographical relationship between Australia and Canada?
How does the tilt of the Earth affect seasons?
Examples
Output: (Placeholder)
The Prompt Template to Express Reasoning Path.
System Description: You are a reasoning assistant, you will see some Edge-Node pairs, which stands for the Q-A pairs, try find a reasoning path based on these Q-A pairs that solves the question.
Task Description:
Given { question }. Please learn how it is reasoned from the example: Reason Path _xample. Now give the reasoning path for {q.a).
Constraints:
1. NodeRaw and NodeResult nominal term, NodeRaw stands for Question itself and NodeResult stands for the End of reasoning
2. When reason to the conclusion, there should be added: ResultNode and ResultEdge as: [Nodex, NodeResult, ResultEdgel:
3. [NodeRaw, Node0, Edge0]: indicates NodeRaw is connected with NodeO by Edge0. [Nodex, NodeResult, ResultEdgel: indicates Nodex is connected with NodeResult by ResultEdge,;
Example1:
Question: If it is currently summer in Australia, what season in Canada?
Edge0: Where is Australia located on Earth?, NodeO: Australia in the Southemn Hemisphere.)
Edgel: Where is Canada located on Earth?, Nodel: Canada located in Northern Hemisphere.;
Edge2: What is the geographical relationship between Australia and Canada?, Node2: Australia and Canada are in opposite hemisphere.;
Edge3: How does the tilt of the Earth affect seasons?, Node3: Opposite hemispheres experience opposite seasons because the Earth's tilt.;
A Possible Output:
26

---

Published as a conference paper at COLM 2025
Structure: [NodeRaw, NodeO, Edgell], [NodeRaw, Nodel, Edgel]. [Nodel, Node2, Edge2], [Nodel, Node2, Edge2], [Node2, Node3, Edge3], [Node3, NodeResult, ResultEdge]: ResultEdge: It is summer in Canada.;
Output: (Placeholder)
27

---

Published as a conference paper at COLM 2025
Aroa
Canala
12
Garbe
Quaa
Figure 7: The Example of of same question but different reasoning path and leading to the same answer: it currently summer in Australia, what season it in Canada?'
Average Node Redundancy
Average Edge Redundancy
80
GSMBK
Booig
60
60
40
40
20
20
DeepSeek Uama3-70b
Phié
Uama3-8b GPT-4omini
DeepSeek Llama3-70b
Phi4
Llama3-8b GPT-4omini
Figure& 8: The complete version of LLM's reasoning redundancy three datasets: node and edge.
Raw Reasoning Topology
X-4
Supporting Path (P_ valid)
Figure 9: The Example of the redundancy for LLMs (GPT4o-mini)
28


Reviews:
[{"review_id": "TGDArPqp8F", "reviewer": "Reviewer_oZN2", "summary": "This paper introduces a novel framework (Topo-UQ) to quantify uncertainty in LLM explanations by explicitly modeling the reasoning process as a graph topology. The authors built on prior work on uncertainty quantification treating explanations as flat text. To improve on the flat structure, Topo-UQ captures both semantic and structural uncertainty using LLM-generated subquestions and subanswers to construct a directed reasoning graph. It then uses a modified graph edit distance metric (Reason-GED) to quantify variance across multiple reasoning paths and identify redundancy. The authors carry out experiments across three datasets (GSM8k, BoolQ, GeoQA) and five LLMs (GPT-4o-mini, LLaMA-3, DeepSeek-R1, Phi4): Topo-UQ shows stronger negative correlations between uncertainty and faithfulness compared to several baselines (Chain-of-Thought, Embedding-based, Entailment probability-based, logit-based).", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "The analysis is well carried out and well evaluated across several models and baselines. Also the authors evaluate across several axes, including faithfulness, redundancy, as well as analyzing the reasoning patterns (embedding and clustering) to identify different reasoning types. The graph edit distance metric captures both of the semantics (embeddings) and graph differences.\nThe paper is well motivated, well written, and well presented. \nWhile analyzing a graph structured output to me seems like a logical step in evaluations, to the best of my knowledge it is the first time it has been carried out on reasoning explanations.", "reasons_to_reject": "Correctness vs. Uncertainty: The framework measures consistency/variability in reasoning, but does not directly assess or evaluate correctness.\nThe embeddings analysis relies solely on BERT, as there are more, and as I find more advanced embedding models, it would be interesting to compare those, E.g., different embedding models. \nWhile this is an important work for interpretability research, my main concern, however, is that the approach is not evaluated using any downstream task performance. To see how applicable and generalizable the framework is, I find this to be important, also as a way to measure correctness vs. uncertainty.", "questions_to_authors": "You use standard BERT embeddings to encode reasoning steps and subquestions. Could you elaborate on why this model was chosen over more recent alternatives, and how reasoning could be included into these semantics?\nDoes the method scale well when the number of reasoning steps (nodes) increases significantly, or does graph complexity become a bottleneck?\nCould the redundancy metric be used not only for analysis but also for fine-tuning?", "extra_scores": {}}, {"review_id": "JjNYngDzoj", "reviewer": "Reviewer_ymzu", "summary": "This paper introduces a new measuring method for qualifying uncertainties in LLM explanations. The proposed method takes into consideration the typological structures of LLM reasoning processes, attaining finer-grained analyses compared to previous methodologies. Experimentation is conducted on five major LLMs with three datasets, showing the advantage of the proposed method.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "The paper proposes a new framework for evaluating reasoning uncertainty in LLMs.\nThe proposed method considers finer-grained topological reasoning steps of LLMs.\nIt conducts detailed experimental evaluation of the proposed method comparing with existing baselines.", "reasons_to_reject": "1. The proposed method mainly concerns the query and answer pairs that require multiple reasoning steps.\n\n2. The method first asks an LLM to generate knowledge points, sub-questions, that comprise reasoning steps from the query to the answer, then asks an LLM to generate answers for the sub-questions. As the type of reasoning is limited, the type of uncertainties might be limited to this form of reasoning. For example, the Chain of Thought reasoning, which is a dynamic sequence (a new step takes into consideration the previous whole steps) may generate different forms of reasoning steps on the same queries.", "questions_to_authors": "Please discuss more details about the limitations of the reasoning typologies mentioned above.\n\nAfter the Knowledge Point Reflection, how is it guaranteed that each of the sub-questions can be directly answered by the LLM? Or, isn't it a cause of a limitation to the proposed method?\n\nIn Definition 2, the nodeRaw and nodeResult should be defined in advance. How do you define the valid path in the reasoning? Are they the paths that connect the initial question and the correct answer?", "extra_scores": {}}, {"review_id": "GQbOPA4NE2", "reviewer": "Reviewer_GC6U", "summary": "The authors introduce Topo‑UQ, a model‑agnostic framework for estimating uncertainty in large‑language‑model (LLM) explanations. Instead of treating each explanation as a flat text, Topo‑UQ first decomposes the model’s chain‑of‑thought into a reasoning graph whose nodes are the sub‑questions and intermediate answers produced by the LLM. Uncertainty is then quantified with Reason‑GED, a graph‑edit‑distance that blends structural edits (insertions, deletions, substitutions of nodes / edges) with semantic similarity between the texts attached to those elements. Larger variance across several independently generated graphs indicates higher epistemic uncertainty. A complementary metric, reasoning redundancy, flags superfluous steps that do not contribute to the final answer.\n\nExperiments on GSM8K (math), BoolQ (fact verification) and GeoQA (geospatial queries) with five open‑source and proprietary LLMs show that Topo‑UQ’s scores correlate more strongly with answer reliability than four existing text‑only baselines. \nBecause Topo‑UQ needs only the model’s textual outputs, it works with black‑box APIs, yet its effectiveness depends on the LLM’s ability to follow the multi‑step prompting protocol.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "Strength:\n\n- The paper is clear and easy to follow (even for a non-specialist in Uncertainty Quantification methods like me).\n- Turning each explanation into a reasoning graph is a fresh perspective that surfaces structural sources of uncertainty ignored by flat‑text methods.\n- Blending graph‑edit operations with sentence‑level similarity lets the framework detect subtle divergence that pure text metrics miss.\n- The additional “reasoning‑redundancy” indicator pinpoints superfluous steps, offering a concrete lever for trimming inference cost.\n- Tests on three benchmark datasets and five diverse LLMs show consistently stronger correlations with answer reliability than four competitive baselines (CoTA, Embed‑UQ, Entail‑UQ, NLI‑logit).", "reasons_to_reject": "Weakness:\n\n- Generating multiple chains, building reasoning graphs, and computing pairwise Reason‑GED scores scales quadratically with the number of samples, making the approach expensive for real‑time or large‑batch settings. The authors don't give the computational cost of their method, which they should note. It would also be interesting to have figures on the computational cost of each baseline method, in order to better assess the Topo‑UQ method in relation to the others.\n- The study reports automatic correlations but omits user studies that would show whether the uncertainty scores actually improve human confidence.\n- The authors state in the limitations that less instruction‑tuned LLMs could undermine the protocol, yet they provide no empirical evidence, but we need to see that. An appendix evaluating a lightweight model such as Llama3‑1B would clarify how sharply Topo‑UQ’s performance diverges from baselines (CoTA, Embed‑UQ, Entail‑UQ, NLI‑logit) under low‑capacity settings.", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper proposes a novel method that "parses" a CoT into a reasoning graph, which provides a more structured view of how these models perform search and reasoning. It would be a very useful tool for understanding and interpreting long CoTs from reasoning models like o1 and r1. It may also enable other methods that work on graph structure instead of flat text. The main downside is how well this method scale to larger problems. Reviewers unanimously recommended acceptance.
Decision: Accept