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

arXiv: https://arxiv.org/abs/2609.05284 · HTML: https://mlsanity.com/paper/2609.05284/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 41 of its 56 references that are in the map.
- First posted on arXiv 4 Sep 2026.

## Placed in

- LLM reasoning / [Test-time compute and efficient thinking](https://mlsanity.com/lr/test-time-compute-and-efficient-thinking/)

## Builds on (most cited first, 30 of 41)

- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [DeepSeekMath: Pushing the Limits of Mathematical Reasoning in Open Language Models](https://mlsanity.com/paper/2402.03300/) (2024)
- [Qwen3 Technical Report](https://mlsanity.com/paper/2505.09388/) (2025)
- [Measuring Mathematical Problem Solving With the MATH Dataset](https://mlsanity.com/paper/2103.03874/) (2021)
- [Let's Verify Step by Step](https://mlsanity.com/paper/2305.20050/) (2023)
- [Tree of Thoughts: Deliberate Problem Solving with Large Language Models](https://mlsanity.com/paper/2305.10601/) (2023)
- [A Broad-Coverage Challenge Corpus for Sentence Understanding through Inference](https://mlsanity.com/paper/1704.05426/) (2017)
- [DeBERTa: Decoding-enhanced BERT with Disentangled Attention](https://mlsanity.com/paper/2006.03654/) (2020)
- [Language Models (Mostly) Know What They Know](https://mlsanity.com/paper/2207.05221/) (2022)
- [MMLU-Pro: A More Robust and Challenging Multi-Task Language Understanding Benchmark](https://mlsanity.com/paper/2406.01574/) (2024)
- [Can LLMs Express Their Uncertainty? An Empirical Evaluation of Confidence Elicitation in LLMs](https://mlsanity.com/paper/2306.13063/) (2023)
- [SelfCheckGPT: Zero-Resource Black-Box Hallucination Detection for Generative Large Language Models](https://mlsanity.com/paper/2303.08896/) (2023)
- [Towards Reasoning Era: A Survey of Long Chain-of-Thought for Reasoning Large Language Models](https://mlsanity.com/paper/2503.09567/) (2025)
- [INSIDE: LLMs' Internal States Retain the Power of Hallucination Detection](https://mlsanity.com/paper/2402.03744/) (2024)
- [How Language Model Hallucinations Can Snowball](https://mlsanity.com/paper/2305.13534/) (2023)
- [Generating with Confidence: Uncertainty Quantification for Black-box Large Language Models](https://mlsanity.com/paper/2305.19187/) (2023)
- [Unsupervised Quality Estimation for Neural Machine Translation](https://mlsanity.com/paper/2005.10608/) (2020)
- [Chain-of-Thought Reasoning Without Prompting](https://mlsanity.com/paper/2402.10200/) (2024)
- [Learning to Reason without External Rewards](https://mlsanity.com/paper/2505.19590/) (2025)
- [Deep Think with Confidence](https://mlsanity.com/paper/2508.15260/) (2025)
- [Out-of-Distribution Detection and Selective Generation for Conditional Language Models](https://mlsanity.com/paper/2209.15558/) (2022)
- [Kernel Language Entropy: Fine-grained Uncertainty Quantification for LLMs from Semantic Similarities](https://mlsanity.com/paper/2405.20003/) (2024)
- [LM-Polygraph: Uncertainty Estimation for Language Models](https://mlsanity.com/paper/2311.07383/) (2023)
- [Benchmarking LLMs via Uncertainty Quantification](https://mlsanity.com/paper/2401.12794/) (2024)
- [Forest-of-Thought: Scaling Test-Time Compute for Enhancing LLM Reasoning](https://mlsanity.com/paper/2412.09078/) (2024)
- [Benchmarking Uncertainty Quantification Methods for Large Language Models with LM-Polygraph](https://mlsanity.com/paper/2406.15627/) (2024)
- [Maximizing Confidence Alone Improves Reasoning](https://mlsanity.com/paper/2505.22660/) (2025)
- [Uncertainty Quantification and Confidence Calibration in Large Language Models: A Survey](https://mlsanity.com/paper/2503.15850/) (2025)
- [A Survey of Large Language Models for Financial Applications: Progress, Prospects and Challenges](https://mlsanity.com/paper/2406.11903/) (2024)
- [LUQ: Long-text Uncertainty Quantification for LLMs](https://mlsanity.com/paper/2403.20279/) (2024)

## Abstract (arXiv)

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.