Argument Graph Uncertainty: Quantifying Uncertainty from the Logical Structure of Reasoning Chains

Simon Baur; Sumire Honda; Wojciech Samek; Jackie Ma

cs.AIOct 14, 2026

Argument Graph Uncertainty: Quantifying Uncertainty from the Logical Structure of Reasoning Chains

Authors: Simon Baur, Sumire Honda, Wojciech Samek, Jackie Ma

Organizations: Fraunhofer Heinrich-Hertz-Institut 10587 Berlin, Germany

Abstract

Reliable uncertainty estimation is essential for deploying large language models in high-stakes reasoning tasks, yet most existing approaches rely on expensive sampling strategies or shallow token-level signals that ignore the internal logical structure of model outputs. We introduce Argument Graph Uncertainty, a post-hoc framework for multiple choice question tasks, that estimates model confidence directly from the logical structure of a single chain-of-thought reasoning trace. Our method uses either a lightweight instruction-tuned model or a simple deterministic rule to segment the reasoning chain into propositional units, then applies a NLI model to infer relational edges and construct two complementary argument graphs over these segments. The resulting edge scores are aggregated into a Dirichlet posterior over answer options, whose concentration yields calibrated uncertainty estimates reflecting both local step-to-step coherence and global logical consistency across the reasoning trace. Evaluated on GPQA, MMLU-Pro and TruthfulQA, our method consistently surpasses token-based and consistency-based uncertainty baselines across multiple reasoning models. We further demonstrate through extensive combination analyses that argument graph uncertainty captures an orthogonal signal to existing approaches, making it a complementary component in uncertainty ensembles. Crucially, our framework requires no additional calls to the evaluated model and relies entirely on small, efficient auxiliary models, producing fully interpretable, per-node uncertainty attributions at low computational cost.

Figures & tables

Figure 1: Argument Graph Uncertainty. A reasoning trace is segmented into propositional nodes

\{v_{1},\dots,v_{4}\}

and passed through an NLI model to construct two complementary graphs: a Segment–Segment Graph capturing pairwise entailment, conflict, and asymmetry across all nodes, and a Segment–Option Commitment Graph mapping each node to answer options. Graph-derived evidence signals are aggregated into Dirichlet concentration parameters

\{\alpha_{o}\}

, from which a normalized predictive entropy

H_{\mathrm{norm}}

serves as the final uncertainty score.

Figure 2: Token-level entropy across reasoning trace of a single GPQA example. Normalized per-token entropy (rolling mean, q10–q90 band) and backtracking cue tokens (

\times

) across a single reasoning trace. The vast majority of tokens are generated with high confidence, with intermittent spikes, causing the rolling mean to settle roughly between

{\approx}0.1-{\approx}0.2

. Backtracking cues exhibit strongly varying entropy, and do not align with spikes or plateaus. Reasoning traces of correct and incorrect predictions yield similar token entropy trajectories, making it unclear which tokens to select or how to aggregate them into a meaningful uncertainty signal.

Figure 3: PRR across all models for

U_{\mathrm{AGU}}

U_{\mathrm{Cons}}

, and their equal-weight combination. The combined score consistently dominates both individual methods.

	Argument Graph Uncertainty $\boldsymbol{U_{\mathrm{AGU}}(R)}$		$\boldsymbol{U_{\mathrm{Cons}}}$		$\boldsymbol{U_{\mathrm{Token}}}$
Model	PRR $\uparrow$	$\rho$ $\downarrow$	PRR $\uparrow$	$\rho$ $\downarrow$	PRR $\uparrow$	$\rho$ $\downarrow$
Nemotron-3 Nano 30B	0.65 $\pm$ 0.07	-0.37 $\pm$ 0.06	0.24 $\pm$ 0.14	-0.24 $\pm$ 0.08	0.41 $\pm$ 0.15	-0.32 $\pm$ 0.08
GPT-OSS 120B	0.56 $\pm$ 0.09	-0.28 $\pm$ 0.06	0.36 $\pm$ 0.15	-0.37 $\pm$ 0.08	-0.27 $\pm$ 0.19	0.02 $\pm$ 0.08
GPT-OSS 20B	0.55 $\pm$ 0.10	-0.37 $\pm$ 0.07	0.35 $\pm$ 0.14	-0.36 $\pm$ 0.09	0.14 $\pm$ 0.18	-0.20 $\pm$ 0.09
Qwen3 4B Thinking	0.51 $\pm$ 0.07	-0.39 $\pm$ 0.06	0.20 $\pm$ 0.09	-0.21 $\pm$ 0.07	0.27 $\pm$ 0.08	-0.21 $\pm$ 0.07
Qwen3 30B Thinking	0.43 $\pm$ 0.09	-0.27 $\pm$ 0.06	0.31 $\pm$ 0.11	-0.32 $\pm$ 0.07	0.10 $\pm$ 0.02	-0.10 $\pm$ 0.02

Table 1: Calibration performance across nine reasoning models on GPQA Diamond. We compare Argument Graph Uncertainty

U_{\mathrm{AGU}}(R)

against consistency-based uncertainty

U_{\mathrm{Cons}}

and token probability uncertainty

U_{\mathrm{Token}}

using Prediction Rejection Rate (PRR

\uparrow

) and Spearman correlation (

\rho

\downarrow

). Bold indicates the best method per model.

U_{\mathrm{AGU}}(R)

achieves the highest PRR in eight out of nine models.

Figure 4: Uncertainty score distribution examples. Token entropy ( top ) collapses to near-zero across all models, rendering it uninformative.

U_{\mathrm{Cons}}

( bottom ) is strongly bimodal (models either agree unanimously or disagree maximally) with little resolution in between.

U_{\mathrm{AGU}}

( middle ) spreads broadly across

[0,1]

, capturing diverse uncertainty signals and filling precisely the range that consistency cannot resolve.

Segmenter	Nemotron 30B	GPT-OSS 120B	GPT-OSS 20B	Qwen3 4B-T	Qwen3 30B-T	Phi-4 mini-R	R1-Qwen 14B	R1-Llama 70B	R1-Llama 8B	Mean
Qwen3-8B	0.65 $\pm$ .07	0.56 $\pm$ .09	0.55 $\pm$ .10	0.51 $\pm$ .07	0.43 $\pm$ .09	0.43 $\pm$ .07	0.41 $\pm$ .08	0.34 $\pm$ .04	0.29 $\pm$ .08	0.46
GPT-OSS-120B	0.67 $\pm$ .07	0.68 $\pm$ .03 ∗	0.76 $\pm$ .03 ∗	0.39 $\pm$ .06 ∗	0.47 $\pm$ .02	0.32 $\pm$ .03 ∗	0.42 $\pm$ .01	0.46 $\pm$ .02 ∗	0.31 $\pm$ .02	0.50
Paragraph split	0.71 $\pm$ .05	0.62 $\pm$ .03	0.76 $\pm$ .01 ∗	0.35 $\pm$ .01 ∗	0.46 $\pm$ .01	0.29 $\pm$ .03 ∗	0.37 $\pm$ .04	0.36 $\pm$ .04	0.29 $\pm$ .03	0.47

Table 2: Segmentation ablation on GPQA Diamond. PRR of

U_{\mathrm{AGU}}

across different segmenters, mean

\pm

std over seeds. ∗ marks cells that differ significantly from the Qwen3-8B row (Welch’s

t

-test,

p<0.05

Figure 5: Robustness of

U_{\mathrm{AGU}}

to NLI errors. PRR retained on GPQA Diamond when (a) a fraction

\varepsilon

of edge classes is flipped at random and (b) Gaussian noise

\sigma

is added to the class log-probabilities. Grey: individual models; bold: mean; band:

\pm

1 std.

Figure 6: Compute cost comparison. (a) Analytical cost against trace length for the consistency and AGU configurations. (b) Measured wall-clock time per model on GPQA Diamond.

Appendix figures & tables10 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 7: Example visualization of PRR.

Model	$U_{\mathrm{AGU}}$	$U_{\mathrm{Token}}$	$U_{\mathrm{Cons}}$	$U_{\mathrm{AGU}}{+}U_{\mathrm{Cons}}$
GPT-OSS-120B	0.54 $\pm$ .01	0.05 $\pm$ .00	0.48 $\pm$ .01	0.66 $\pm$ .01
Nemotron-30B	0.52 $\pm$ .01	0.11 $\pm$ .01	0.51 $\pm$ .00	0.67 $\pm$ .00
Qwen3-30B-T	0.43 $\pm$ .01	0.05 $\pm$ .02	0.49 $\pm$ .00	0.63 $\pm$ .01
Phi-4-mini-R	0.41 $\pm$ .01	0.07 $\pm$ .00	0.60 $\pm$ .01	0.64 $\pm$ .00
R1-Llama-70B	0.40 $\pm$ .01	0.04 $\pm$ .01	0.51 $\pm$ .00	0.63 $\pm$ .01
Mean	0.46	0.06	0.52	0.64

Appendix

Table 3: PRR on MMLU-Pro. Mean

\pm

std over seeds. Bold marks the best signal per model.

Model	$U_{\mathrm{AGU}}$	$U_{\mathrm{Token}}$	$U_{\mathrm{Cons}}$	$U_{\mathrm{AGU}}{+}U_{\mathrm{Cons}}$
Qwen3-30B-T	0.48 $\pm$ .05	0.13 $\pm$ .02	0.37 $\pm$ .03	0.60 $\pm$ .03
R1-Llama-70B	0.42 $\pm$ .04	0.33 $\pm$ .01	0.44 $\pm$ .02	0.59 $\pm$ .02
Qwen3-4B-T	0.39 $\pm$ .04	0.18 $\pm$ .04	0.36 $\pm$ .03	0.51 $\pm$ .04
Phi-4-mini-R	0.38 $\pm$ .03	0.11 $\pm$ .05	0.46 $\pm$ .02	0.55 $\pm$ .02
GPT-OSS-120B	0.35 $\pm$ .03	0.11 $\pm$ .02	0.37 $\pm$ .03	0.48 $\pm$ .03
Nemotron-30B	0.34 $\pm$ .04	0.17 $\pm$ .03	0.46 $\pm$ .01	0.51 $\pm$ .01

Appendix

Table 4: PRR on TruthfulQA MC4. Mean

\pm

std over seeds. Bold marks the best signal per model.

Figure 8: NLI edge statistics. (a, b) Share of edges by predicted class per model for segment–segment edges within the window (

w{=}10

) and segment–option edges; conf. and entr. are the mean probability of the predicted class and the mean three-class entropy normalised by

\log 3

. (c) A complete five-segment trace of GPT-OSS-20B with the scorer’s actual outputs; segment text is abbreviated. Adjacent segment–segment edges are shown along the chain. For visibility, only segment–option edges with

p\geq 0.75

are drawn as arrows;

v_{1}

and

v_{2}

are neutral towards all options and

v_{5}

towards

o_{A}

. (d) All ordered segment–segment edges of the same trace; row is premise, column is hypothesis, shading is the scorer’s confidence.

		PRR		Pairs
Model	Mean segs	Window	All-to-all	Window	All-to-all
GPT-OSS-20B	69.4	0.67	0.67	94.9k	1.64M
GPT-OSS-120B	61.8	0.59	0.60	102.3k	1.43M
Nemotron-30B	64.4	0.54	0.53	85.3k	1.02M
Qwen3-30B-T	99.2	0.48	0.47	190.4k	3.51M
R1-Qwen-14B	92.8	0.34	0.33	168.8k	2.86M

Appendix

Table 5: Windowed (

w{=}10

) vs. all-to-all segment graph on GPQA Diamond. PRR and number of scored segment–segment pairs, one seed per model.

Model	Segment count	$U_{\mathrm{AGU}}$	$U_{\mathrm{AGU}}\,\|\,$ length	$\rho$
GPT-OSS-20B	0.52 $\pm$ .06	0.67 $\pm$ .06	0.49 $\pm$ .08	0.45 $\pm$ .07
Nemotron-30B	0.46 $\pm$ .14	0.60 $\pm$ .08	0.45 $\pm$ .11	0.52 $\pm$ .07
GPT-OSS-120B	0.65 $\pm$ .03	0.58 $\pm$ .02	0.28 $\pm$ .02	0.59 $\pm$ .01
Qwen3-30B-T	0.41 $\pm$ .07	0.50 $\pm$ .05	0.38 $\pm$ .05	0.54 $\pm$ .04
R1-Qwen-14B	0.23 $\pm$ .09	0.37 $\pm$ .04	0.31 $\pm$ .06	0.29 $\pm$ .06
Qwen3-4B-T	0.15 $\pm$ .04	0.35 $\pm$ .02	0.29 $\pm$ .05	0.36 $\pm$ .07

Appendix

Table 6: Trace length versus graph signal on GPQA Diamond. PRR of the segment count used as an uncertainty score, of

U_{\mathrm{AGU}}

, and of

U_{\mathrm{AGU}}

after rank-regressing out the segment count;

\rho

is the Spearman correlation between

U_{\mathrm{AGU}}

and segment count. Mean

\pm

std over seeds; bold marks the better of the two single scores.

Figure 9: Different uncertainty score combination techniques aggregated over models.

Figure 10: Histograms of uncertainty distributions per model and method.

Figure 11: Influence of hyperparameters evaluated for every model.

Model	PRR $\uparrow$	$\rho$ $\downarrow$	$(\kappa,\alpha_{0})$	$(\gamma_{c},\gamma_{a})$
GPT-OSS-20B	0.66	-0.39	(27.68, 0.10)	(1.20, 1.00)
Nemotron-30B	0.65	-0.37	(12.00, 1.00)	(1.20, 1.00)
GPT-OSS-120B	0.68	0.26	(12.00, 1.00)	(1.20, 1.00)
Qwen3-30B-T	0.51	-0.35	(37.95, 0.10)	(1.20, 1.00)
Qwen3-4B-T	0.51	-0.39	(12.00, 1.00)	(1.20, 1.00)
Phi-4-mini-R	0.43	-0.35	(12.00, 1.00)	(1.20, 1.00)

Appendix

Table 7: Results of sweep over

\kappa,\alpha_{0}

and fixed

(\gamma_{c},\gamma_{a})

. Improved models are bold .

LLM Uncertainty Estimation

Large language model uncertainty estimation measures when outputs may be wrong, ambiguous, or unreliable to guide safer decisions.

See all 399 papers

Jul 18, 2026

Beyond Semantic Equivalence: Logical Graphs for LLM Uncertainty Quantification

Large Language Models often produce confidently stated yet unreliable outputs, posing critical challenges for deployment in safety-sensitive applications. Existing uncertainty metrics such as semantic entropy capture agreement at the level of semantic equivalence, but largely ignore the logical relationships between distinct answers. As a result, they tend to overestimate uncertainty and falsely flag hallucinations in settings where generated responses are diverse in form yet logically compatible (e.g., differing only in granularity or specificity). We propose Logical Graph Uncertainty (LGU), a framework that explicitly models implication and incompatibility among answers. LGU aggregates probability mass along entailment chains onto the most specific hypotheses the answers support, measures the entropy of the resulting distribution, and penalizes mutual incompatibility among those hypotheses. Across multiple question-answering benchmarks and model families, LGU ranks first on average among existing uncertainty measures, with its largest gains---up to +7.1% AUROC and +3.5% AUARC over semantic entropy---on questions whose sampled answers are logically structured.

Yanni Dong, Minghua Liu, Meilin Zhu +2

Institute of Intelligent Software, Guangzhou, China · Institute of Software, Chinese Academy of Sciences, Beijing, China · University of Liverpool, Liverpool, UK

Reasoning Consistency in Language Models LLM Reliability LLM Uncertainty Estimation

Ask PDF

Sep 4, 2026

GUT: Quantifying and Optimizing the Reasoning Uncertainty of LLMs via Graph Complexity

Recent years have witnessed great advances in the reasoning ability of Large Language Models (LLMs). However, the reasoning processes of LLMs often exhibit uncertainty, where LLMs often produce a proliferation of divergent branches at each reasoning step even when fed the same prompting inputs, and certain branches exhibit evidently incredible, even nonsensical, reasoning chains and results. In this paper, we propose the Graph-complexity-based UncerTainty (GUT) method for investigating the reasoning uncertainty of LLMs. The key idea of GUT is to characterize the potential branches of each reasoning chain with a directed acyclic graph, thereby ensuring that all potential branches are comprehensively covered within the graph space. Building upon this recognition, we further build two modules of GUT, that is, a Quantification (GUT-Q) module and an Optimization (GUT-O) module, for quantifying and reducing the reasoning uncertainty of LLMs, respectively. GUT-Q measures LLM reasoning uncertainty by approximating the reasoning space complexity with graph complexity. GUT-O implements uncertainty optimization by treating negative uncertainty as the reward function in reinforcement learning. Experimental results conducted on four LLMs and five datasets validate the effectiveness of GUT.

Shuang Liang, Xin-Yu Hu, Xiang-Jun Ou +1

National Key Laboratory for Novel Software Technology, Nanjing University, China. · School of Intelligent Science and Technology, Nanjing University, China.

LLM Uncertainty Estimation LLM Reasoning with Graphs

Ask PDF

Oct 19, 2026

Diagnostic Analysis for Large Language Model Reasoning

Reasoning structures (e.g., chains and graphs) are increasingly used for probabilistic inference, factuality verification, and uncertainty estimation, but their structural reliability is rarely evaluated directly. We test whether this reliability holds through a proposed two-stage diagnostic evaluation in open-ended multi-hop QA. Stage 1 tests different capabilities required to construct reasoning graphs, showing that graph reliability varies with topology, prompt design, and model family. Stage 2 uses uncertainty estimation as a downstream test case. Generated-edge experiments show that graph-based computation is sensitive to upstream graph errors, with performance dropping relative to the gold-graph setting. Gold-graph experiments further show that graph structure provides little benefit when used only as prompt context, but improves the separation of correct from incorrect answers by confidence score and enables node-level diagnostics.

Xinyu Liu, Dongqi Fu, Jun Wu

Michigan State University · Meta AI

Language Model Reasoning Evaluation LLM Reasoning with Graphs Multi-Hop QA

Ask PDF

Abstract

LLM Uncertainty Estimation

Explore similar work

Beyond Semantic Equivalence: Logical Graphs for LLM Uncertainty Quantification

GUT: Quantifying and Optimizing the Reasoning Uncertainty of LLMs via Graph Complexity

Diagnostic Analysis for Large Language Model Reasoning