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

Shuang Liang; Xin-Yu Hu; Xiang-Jun Ou; Shao-Qun Zhang

cs.AISep 4, 2026

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

Authors: Shuang Liang, Xin-Yu Hu, Xiang-Jun Ou, Shao-Qun Zhang

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

Abstract

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.

Figures & tables

Figure 1: Illustration of our proposed GUT. A real-world case study of GUT is provided in Appendix E .

UQ	GSM8K	MATH-500	AMC2022-2024
GUT-Q-W	0.1909 $\pm$ 0.0207	0.2364 $\pm$ 0.0315	0.3603 $\pm$ 0.0592
GUT-Q-H	0.1365 $\pm$ 0.0229	0.1945 $\pm$ 0.0318	0.3197 $\pm$ 0.0602
GUT-Q-UP	0.2110 $\pm$ 0.0213	0.2069 $\pm$ 0.0334	0.2586 $\pm$ 0.0600

Table 1: PCCs between MTLP and complexity-based uncertainty metrics across investigated mathematical reasoning datasets, averaged across 4 Qwen3 LLMs.

UQ	GSM8K			MATH-500			AMC2022-2024
UQ	PRR	AUROC	AUPRC	PRR	AUROC	AUPRC	PRR	AUROC	AUPRC
MSP	-33.66 $\pm$ 1.22	58.89 $\pm$ 0.97	86.84 $\pm$ 0.80	-8.09 $\pm$ 2.46	58.76 $\pm$ 1.67	60.85 $\pm$ 2.04	-37.65 $\pm$ 4.97	67.35 $\pm$ 3.70	52.35 $\pm$ 4.27
Ppl	-33.66 $\pm$ 1.22	58.89 $\pm$ 0.98	86.84 $\pm$ 0.79	-8.09 $\pm$ 2.46	58.76 $\pm$ 1.65	60.85 $\pm$ 2.01	-37.65 $\pm$ 4.97	67.35 $\pm$ 3.77	52.35 $\pm$ 4.41
MTE	47.45 $\pm$ 0.86	28.89 $\pm$ 1.73	74.56 $\pm$ 1.26	31.08 $\pm$ 2.36	36.22 $\pm$ 1.99	44.79 $\pm$ 2.13	37.77 $\pm$ 4.71	26.06 $\pm$ 3.79	28.18 $\pm$ 3.57
MTLP	-27.77 $\pm$ 1.13	57.30 $\pm$ 1.52	84.56 $\pm$ 0.91	2.10 $\pm$ 2.40	55.29 $\pm$ 1.95	62.99 $\pm$ 2.53	27.33 $\pm$ 5.00	28.86 $\pm$ 3.86	26.17 $\pm$ 3.20
MPMI	-28.86 $\pm$ 1.13	59.13 $\pm$ 1.58	87.55 $\pm$ 0.86	4.67 $\pm$ 2.37	57.56 $\pm$ 2.01	63.94 $\pm$ 2.56	-12.39 $\pm$ 4.79	48.12 $\pm$ 4.37	43.94 $\pm$ 5.05

Table 2: Comparisons of UQ performance for Qwen3-4B across partial contenders and datasets, where bold and underline denote the group best and second-best results, respectively.

Panel of Figure 2 — Figure 2: Ablation and sensitivity analyses of the GUT-Q for Qwen3-4B.

Models	Accuracy	MTLP	Mean Uncertainty
Models	Accuracy	MTLP	GUT-Q-W	GUT-Q-H	GUT-Q-UP
Qwen3-0.6B	$18.00\pm 1.31$	$-7.55\pm 0.04$	$0.77\pm 0.01$	$1.86\pm 0.03$	$1.14\pm 0.01$
+ GRPO	$23.40\pm 1.51$	$-7.67\pm 0.04$	$0.74\pm 0.01$ (-3.9%)	$1.88\pm 0.03$ (+1.1%)	$1.17\pm 0.02$ (+2.6%)
+ GUT-O	$21.40\pm 1.43$	$-8.94\pm 0.04$	$0.64\pm 0.01$ (-16.9%)	$1.51\pm 0.03$ (-18.8%)	$0.88\pm 0.01$ (-22.8%)
Qwen3-1.7B	$42.20\pm 1.79$	$-13.45\pm 0.06$	$0.43\pm 0.01$	$2.03\pm 0.05$	$0.47\pm 0.01$
+ GRPO	$46.40\pm 1.81$	$-13.56\pm 0.07$	$0.42\pm 0.01$ (-2.3%)	$1.89\pm 0.05$ (-6.9%)	$0.46\pm 0.01$ (-2.1%)

Table 3: Comparisons of UO performance for 4 Qwen3 LLMs on the MATH-500 dataset, where ‘+’ in column “Models” indicates the applied fine-tuning method, and values in parentheses denote the percentage change in mean uncertainty.

Appendix figures & tables15 assets

Supplementary material from the paper’s appendix.

Appendix

Scale	UQ	GSM8K			MATH-500			AMC2022-2024
Scale	UQ	PRR	AUROC	AUPRC	PRR	AUROC	AUPRC	PRR	AUROC	AUPRC
8B	GUT-Q-UP	72.01 $\pm$ 4.34	83.72 $\pm$ 1.55	97.01 $\pm$ 0.50	53.28 $\pm$ 4.34	75.93 $\pm$ 1.90	81.59 $\pm$ 1.87	72.85 $\pm$ 4.89	81.83 $\pm$ 3.02	84.53 $\pm$ 2.88
8B	GUT-Q-UP-W	73.91 $\pm$ 4.19	84.42 $\pm$ 1.60	97.39 $\pm$ 0.46	52.77 $\pm$ 4.57	76.64 $\pm$ 1.76	79.34 $\pm$ 2.11	74.68 $\pm$ 6.32	87.35 $\pm$ 2.54	82.27 $\pm$ 4.55
4B	GUT-Q-UP	81.68 $\pm$ 1.83	86.61 $\pm$ 1.02	96.93 $\pm$ 0.36	61.93 $\pm$ 3.59	80.13 $\pm$ 1.57	79.45 $\pm$ 2.07	80.82 $\pm$ 4.24	89.48 $\pm$ 2.19	84.60 $\pm$ 3.39
4B	GUT-Q-UP-W	81.76 $\pm$ 1.79	86.63 $\pm$ 1.00	96.94 $\pm$ 0.35	62.13 $\pm$ 3.60	80.23 $\pm$ 1.58	79.56 $\pm$ 2.15	79.07 $\pm$ 4.50	88.72 $\pm$ 2.19	83.24 $\pm$ 3.72
1.7B	GUT-Q-UP	77.50 $\pm$ 1.83	85.48 $\pm$ 0.86	92.83 $\pm$ 0.67	63.39 $\pm$ 3.36	80.68 $\pm$ 1.50	74.08 $\pm$ 2.45	68.00 $\pm$ 6.93	82.90 $\pm$ 3.72	68.00 $\pm$ 6.30

Appendix

Table 4: Comparisons of UQ performance between the GUT-Q implemented with Algorithms 2 (GUT-Q-UP) or 4 (GUT-Q-UP-W).

Scale	Mathematical Reasoning			First-Order Logic Reasoning	Reasoning QA
Scale	GSM8K	MATH-500	AMC2022-2024	FOLIO	MMLU-Pro
8B	89.61	64.20	49.59	72.41	69.58
4B	84.08	53.80	38.02	68.47	60.83
1.7B	71.11	42.20	22.31	43.84	43.33
0.6B	28.89	18.00	0 9.09	44.83	29.17

Appendix

Table 5: Accuracy of the evaluated LLMs on the concerned datasets.

Hyperparameter	Setting
Token-level UQ	Avg Log Prob
Selection Strategy	Top-3%
Window Size $w$	6
Weight $\omega$ in Algorithm 2	0.2

Appendix

Table 6: Configuration of hyperparameters in step-level uncertainty calculation.

Category	UQ	Number of LLM Inferences	Auxiliary Model Execution			Other Computation
Category	UQ	Number of LLM Inferences	Model	Scale	Number of Execution	Other Computation
Information- based	Ppl	1	-	-	-	Token-level statistics computation
Information- based	MCSE	$K$	-	-	-	Token-level statistics computation
Reflexive- based	P(True)	2	-	-	-	-
Reasoning- enhanced	CoT-UQ-ME	2	-	-	-	Token-level statistics computation
Reasoning- enhanced	CoT-UQ-SP	3	-	-	-	-

Appendix

Table 8: Runtime complexity comparison of GUT-Q and its contenders.

Figure 4: Average wall-clock time comparison of GUT-Q and its contenders on the MATH-500 dataset using Qwen3-4B.

Hyperparameter	Value	Hyperparameter	Value
Batch Size	128	Max New Tokens	3072
Group Size $M$	7	Learning Rate	$3\times 10^{-6}$
KL Penalty $\beta$	0.0005	Learning Rate Scheduler	Cosine
Temperature $T$	1.0	Warmup Ratio	0.1
Clip Ratio $\epsilon$	0.2	Optimizer	AdamW
Training Steps	60

Appendix

Table 13: Configuration of hyperparameters for GUT-O.

Dataset	Models	Accuracy	MTLP	Mean Uncertainty
Dataset	Models	Accuracy	MTLP	GUT-Q-W	GUT-Q-H	GUT-Q-UP
GSM8K	Qwen3-0.6B	$28.89\pm 0.97$	$-7.11\pm 0.02$	$3.10\pm 0.02$	$5.93\pm 0.04$	$4.14\pm 0.04$
	+GRPO	$38.97\pm 1.05$	$-7.38\pm 0.02$	$3.03\pm 0.02$ (-2.3%)	$5.77\pm 0.04$ (-2.7%)	$3.99\pm 0.04$ (-3.6%)
	+GUT-O	$38.06\pm 1.07$	$-8.54\pm 0.02$	$2.78\pm 0.02$ (-10.3%)	$5.27\pm 0.04$ (-11.1%)	$3.32\pm 0.03$ (-19.8%)
	Qwen3-1.7B	$71.11\pm 1.00$	$-14.54\pm 0.03$	$1.68\pm 0.02$	$5.51\pm 0.06$	$1.58\pm 0.03$
	+GRPO	$72.93\pm 0.95$	$-14.28\pm 0.04$	$1.69\pm 0.02$ (+0.6%)	$5.41\pm 0.06$ (-1.8%)	$1.62\pm 0.03$ (+2.5%)

Appendix

Table 14: Comparisons of UO performance for Qwen3 families across 5 reasoning datasets, where ‘+’ indicates the applied fine-tuning method, and values in parentheses indicate the percentage change in mean uncertainty.

Model	UQ	GSM8K	MATH-500	AMC2022-2024	FOLIO	MMLU-Pro
Qwen3-0.6B	GUT-Q-W	0.2755 $\pm$ 0.0203	0.1611 $\pm$ 0.0314	0.3310 $\pm$ 0.0646	0.2397 $\pm$ 0.0548	0.2566 $\pm$ 0.0432
	GUT-Q-H	0.2033 $\pm$ 0.0220	0.1718 $\pm$ 0.0345	0.0724 $\pm$ 0.0690	0.1917 $\pm$ 0.0484	0.2542 $\pm$ 0.0449
	GUT-Q-UP	0.2980 $\pm$ 0.0207	0.0734 $\pm$ 0.0337	0.1034 $\pm$ 0.0695	0.2450 $\pm$ 0.0495	0.2243 $\pm$ 0.0470
Qwen3-1.7B	GUT-Q-W	0.2961 $\pm$ 0.0206	0.3874 $\pm$ 0.0308	0.3462 $\pm$ 0.0601	0.3145 $\pm$ 0.0539	0.3521 $\pm$ 0.0406
	GUT-Q-H	0.2199 $\pm$ 0.0227	0.3213 $\pm$ 0.0291	0.3297 $\pm$ 0.0604	0.2773 $\pm$ 0.0594	0.3191 $\pm$ 0.0382
	GUT-Q-UP	0.3302 $\pm$ 0.0238	0.3260 $\pm$ 0.0366	0.1531 $\pm$ 0.0637	0.3952 $\pm$ 0.0512	0.2042 $\pm$ 0.0544

Appendix

Table 15: PCCs between the MTLP optimization target and GUT-Q-derived uncertainties across 4 LLMs and 5 datasets.

Panel of Figure 5 — Figure 5: Ablation comparisons of UQ performance.

Panel of Figure 6 — Figure 6: Impact of the number of samples $K$ on UQ performance.

Panel of Figure 7 — Figure 7: Impact of the temperature $T$ on UQ performance.

Panel of Figure 8 — Figure 8: Impact of the number of shots $F$ on UQ performance.

Panel of Figure 9 — Figure 9: Impact of the criterion for determining equivalence with the NLI model.

Figure 10: Application of our proposed GUT to two test instances from the MATH-500 dataset using Qwen3-4B. For illustrative purposes, the width and height are obtained by removing the node uncertainty in GUT-Q-W and GUT-Q-H, respectively.

Explore similar work

Can We Trust LLM's Logic? Quantifying Uncertainty, Coherence, and Robustness via a Graph-Based Framework
Jul 9, 2026Riccardo Revalor, Jalees Rehman, Debjit PalCoT Faithfulness LLM Reasoning with Graphs
¶Department of Electrical and Computer Engineering · ‡Department of Biochemistry and Molecular Genetics
GRUET: Quantifying Uncertainty of Agentic Reasoning-and-Acting Processes
Sep 21, 2026Shuang Liang, Xin-Yu Hu, Shao-Qun ZhangUncertainty Quantification Agentic Reasoning
National Key Laboratory for Novel Software Technology, Nanjing University, China. · School of Intelligent Science and Technology, Nanjing University, China.
Uncertainty Localization in LLM Reasoning via Embedding Perturbations
Feb 2, 2026Qihao Wen, Jiahao Wang, Yang Nan +3LLM Reliability LLM Uncertainty Estimation
University of Arizona · Michigan State University

Jul 9, 2026J/K move · Enter open · S save

Can We Trust LLM's Logic? Quantifying Uncertainty, Coherence, and Robustness via a Graph-Based Framework

Riccardo Revalor, Jalees Rehman, Debjit Pal

¶Department of Electrical and Computer Engineering · ‡Department of Biochemistry and Molecular Genetics

CoT Faithfulness LLM Reasoning with Graphs Reasoning Evaluation Reasoning Consistency in Language Models Adversarial Robustness of Language Models LLM Uncertainty Estimation+1

Open paper AskPDF arXiv

Large-Language Models (LLMs) can be prone to flawed and unfaithful reasoning that decoding strategies like Self-Consistency (SC) fail to detect as they evaluate only final-answer agreement while ignoring the logical validity of intermediate steps. This raises three fundamental questions: How can we reliably quantify uncertainty in LLM reasoning? Can semantic, structural, and causal awareness select more faithful reasoning compared to naïve majority voting? and How robust is reasoning topology under adversarial conditions? To address these questions, we introduce GRAPHEVAL, a graph-based reasoning framework that re-frames uncertainty quantification (UQ) as a holistic reasoning fidelity problem. We propose a novel UQ metric, Graph Reasoning Coherence Score (GRCS), that quantifies semantic-structural consensus of the reasoning space and captures pathological mode collapse and confident hallucinations. We find that GRCS is the only metric that is consistently negatively correlated with reasoning faithfulness across both more capable and smaller models. Additionally, we introduce Graph Self-Consistency (GSC), a medoid-based decoding strategy that trades nominal accuracy for reasoning fidelity, exposing the degree to which SC is inflated by unfaithful lucky guesses in smaller models, while preserving or improving accuracy in more capable ones. Finally, through adversarial medoid ablation, we demonstrate that the GSC-selected path acts as a "load-bearing path" and forcing models away from it degrades reasoning faithfulness and, in targeted cases, causes drops in accuracy.

Abstract

Explore similar work

Can We Trust LLM's Logic? Quantifying Uncertainty, Coherence, and Robustness via a Graph-Based Framework

GRUET: Quantifying Uncertainty of Agentic Reasoning-and-Acting Processes

Uncertainty Localization in LLM Reasoning via Embedding Perturbations