PaperlayerView exact revision on arXiv

Source-linked AI summary

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

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

arXiv:2609.05284v1cs.AI

TL;DR

LLM reasoning uncertainty is difficult to quantify because stochastic generation creates divergent branches that sequence-based modeling can miss. GUT represents potential reasoning branches with graphs, using GUT-Q to quantify uncertainty and GUT-O to optimize it through reinforcement learning. Across 4 LLMs and 5 datasets, GUT-Q outperformed 45 UQ contenders, while GUT-O reduced uncertainty and improved accuracy.

  • Problem

    Sequence-based modeling fails to accurately capture LLM reasoning uncertainty because it overlooks potential branches emerging at individual reasoning steps.

  • Method

    GUT models reasoning branches with graph complexity, using GUT-Q for uncertainty quantification and GUT-O with negative uncertainty as an RL reward for optimization.

  • Results

    Across 4 LLMs and 5 datasets, GUT-Q outperformed 45 UQ contenders on selective generation, while GUT-O reduced reasoning uncertainty and improved accuracy.

  • Takeaways & Limitations

    GUT provides a graph-complexity-based approach for quantifying and reducing LLM reasoning uncertainty.

  • Takeaways & Limitations

    Existing sequence-based approaches remain limited because they omit potential branches in reasoning chains.

Abstract

from arXiv · show

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.

1. Introduction

LLM reasoning uncertainty arises from stochastic generation and branching that sequence-based or self-prompting approaches do not fully capture. GUT models potential reasoning branches as a graph, estimates uncertainty through graph complexity, and optimizes it with reinforcement learning.

  • LLM reasoning uncertainty reflects stochastic token distributions and sampling, which can produce divergent reasoning branches from identical prompts.
  • Sequence-based uncertainty measures overlook potential branches emerging at individual reasoning steps, limiting their coverage of inherent reasoning uncertainty.
  • GUT constructs a graph by repeatedly sampling reasoning steps and merging equivalent steps with a Natural Language Inference model.
  • GUT-Q approximates reasoning-space complexity with graph complexity that integrates token-level distribution statistics and graph topology.
  • GUT-O uses negative uncertainty as an RL reward, with experiments showing reduced reasoning uncertainty and improved accuracy across LLM scales and datasets.
  • Across 4 LLMs and 5 datasets, GUT-Q outperforms 45 UQ contenders on selective generation measured by AUROC, AUPRC, and PRR.

2. Related Work

Prior approaches quantify reasoning uncertainty through self-prompting, sequence-level statistics, or graph structure, but they do not fully capture stochastic branching or directly optimize uncertainty.

  • Self-prompting approaches are fundamentally limited by stochastic prompt-based generation, which recursively amplifies reasoning uncertainty.
  • Sequence-based methods use single-sequence statistics or diversity across sampled sequences to quantify uncertainty.
  • Modeling reasoning chains as sequences misses potential branches emerging at each reasoning step.
  • Graph-based methods represent reasoning branches with graph topology, including graph distance and path counts, but still rely heavily on self-prompting.
  • Existing optimization studies use uncertainty signals to explore or terminate reasoning, whereas direct reasoning-uncertainty reduction remains largely unexplored.

3. Uncertainty Quantification

GUT-Q models sampled reasoning chains as a DAG whose branches represent potential reasoning paths, then combines token-level uncertainty with graph complexity to estimate reasoning uncertainty.

  • GUT-Q constructs a DAG from sampled Chain-of-Thought reasoning chains to reveal potential branches at each reasoning step.
  • The DAG starts at the problem root, connects successive reasoning-step nodes, and terminates paths at nodes representing final answers.
  • Semantically equivalent nodes can be merged using bidirectional entailment from an NLI model, while traversal preserves the DAG property.
  • Step-level uncertainty aggregates token-level uncertainty measures, including local group aggregation intended to capture uncertainty within reasoning steps.
  • GUT-Q estimates graph complexity through width, height, and uncertainty propagation, combining reasoning-space topology with node uncertainty.
  • Width measures the maximum branching at one step, whereas height measures the longest reasoning-chain depth.

Appendix A.2 lists a variant that initializes this FNN’s weights with U(v).

GUT-Q-W and GUT-Q-H provide interpretable views of reasoning-space topology, while GUT-Q-UP typically performs better for selective generation; GUT-O optimizes uncertainty indirectly with reinforcement learning.

  • GUT-Q-W and GUT-Q-H are more explainable because they characterize intrinsic reasoning-space topology.
  • GUT-Q-UP typically outperforms GUT-Q-W and GUT-Q-H in the downstream selective-generation task.
  • GUT-Q-W and GUT-Q-H suit topology explainability, whereas GUT-Q-UP suits selective generation.
  • GUT-O replaces the nondifferentiable graph-based uncertainty target with a differentiable sample-level proxy for indirect optimization.
  • Mean Token Log Probability is used as the differentiable proxy, and its negative is supplied as the reward for gradient-based GRPO optimization.
  • PCCs between MTLP and complexity-based uncertainty metrics are consistently positive across the investigated datasets, validating the optimization target.

5. Experiments

Experiments evaluate GUT-Q and GUT-O across four Qwen3 models and five datasets spanning mathematical reasoning, first-order logic reasoning, and long-form question answering. GUT-Q consistently outperforms competing uncertainty-quantification methods, while GUT-O reduces reasoning uncertainty and improves accuracy.

  • GUT-Q Evaluation: GUT-Q evaluates whether graph-complexity-based uncertainty discriminates correct from incorrect generations against 45 white-box and black-box contenders.The evaluation uses AUROC, AUPRC, and PRR, with higher values indicating better uncertainty quantification.
  • Experimental Setup: Experiments span four Qwen3 model scales and five datasets covering mathematical, first-order logic, and long-form QA tasks.The datasets include GSM8K, MATH-500, AMC2022-2024, FOLIO, and MMLU-Pro.
  • GUT-Q Results: GUT-Q-UP consistently outperforms all contenders across three metrics and datasets, with similar results across all four investigated LLMs.The comparison covers partial datasets in the main text and five datasets in the appendix.
  • GUT-Q Results: 11.79% in PRR, 13.33% in AUROC, and 9.66% in AUPRC are GUT-Q’s average improvements over the best contenders across four LLMs and five datasets.GUT-Q also has runtime complexity comparable to methods such as SE and Eig-C.
  • Ablation and Sensitivity Analyses: Node merging is more important than node uncertainty for UP methods, while both components are essential for GUT-Q-W and GUT-Q-H.The ablation comparisons evaluate UQ performance on mathematical reasoning datasets.
  • Ablation and Sensitivity Analyses: K = 9, T = 1.0, and F = 5 are recommended settings balancing UQ performance with computational efficiency.Larger K increases computational costs, while the sensitivity analyses vary samples, temperature, and shots.

B.1. Details on Datasets

The evaluation spans mathematical reasoning, first-order logic, and long-form question-answering datasets, with accuracy used to characterize difficulty. The appendix also specifies sampling, uncertainty-calculation, and generation-length configurations, including a completeness trade-off.

  • Dataset formats: The mathematical datasets use fill-in-the-blank answers, while FOLIO and MMLU-Pro use multiple-choice answers with distinct answer sets.FOLIO answers are True, False, or Uncertain; MMLU-Pro answers are A, B, C, or D.
  • Evaluated datasets: GSM8K, MATH-500, and AMC2022-2024 are ordered from easy to hard, with accuracy decreasing sequentially across the three datasets.GSM8K contains 8500 grade-school problems, MATH-500 contains 500 high-school problems, and AMC2022-2024 contains 128 competition problems.
  • Evaluation considerations: The reported accuracy can differ from prior work because the study uses a different reasoning-extraction prompt and a smaller token-generation budget.The smaller budget is attributed to computational-resource constraints, while the study primarily focuses on quantifying and optimizing reasoning uncertainty rather than improving accuracy.

B.4. Runtime Complexity Analysis of GUT-Q and Its Contenders

GUT-Q has runtime complexity comparable to representative diversity-based and graph-based uncertainty methods. Wall-clock measurements on MATH-500 support this analysis, while batch-parallel prompting reduces the practical cost of sampling.

  • Complexity comparison: GUT-Q uses the same number of LLM prompts as representative diversity-based methods, with only a slightly larger number of auxiliary-model executions.The comparison is made against methods such as SE and Eig-E.
  • Complexity comparison: GUT-Q has comparable LLM-prompt and auxiliary-execution counts to classical graph-based methods such as Topo-UQ.The runtime analysis therefore places GUT-Q alongside both diversity-based and graph-based UQ methods in complexity.
  • Wall-clock evaluation: GUT-Q's wall-clock time is comparable to SE, Eig-E, and Topo-UQ on MATH-500 using Qwen3-4B with K = 10 and L = 5.These settings make LLM inference costs comparable across methods.
  • Practical runtime: GUT-Q's sampling time is only around 2.5 times Ppl's sampling time rather than K = 10 times, because LLM prompting can be batch-parallel.Batch parallelism through packages such as Transformers or vllm makes GUT-Q more efficient in practice.

B.5. UQ Performance Evaluations

Across four Qwen3 model scales and five datasets spanning three difficulty levels, GUT-Q with the UP algorithm generally outperforms the evaluated uncertainty-quantification contenders.

  • Evaluation scope: GUT-Q performance is evaluated for Qwen3-8B, Qwen3-4B, Qwen3-1.7B, and Qwen3-0.6B across five datasets.The comparisons use three evaluation metrics and datasets spanning three difficulty levels.
  • Experimental setup: The evaluation includes results tables for all four model scales, with separate tables for Qwen3-8B, Qwen3-4B, Qwen3-1.7B, and Qwen3-0.6B.The appendix also lists the configurations used for GUT-O and describes fine-tuning across the evaluated reasoning datasets.
  • Performance comparison: GUT-Q implemented with the UP algorithm generally outperforms all contenders across the three evaluation metrics and datasets spanning three difficulty levels.The reported pattern is presented as validation of the proposed GUT-Q module.

C.2. UO Performance Evaluation

GUT-O is evaluated through changes in uncertainty, accuracy, and the relationship between its optimization target and GUT-Q uncertainty. The reported results support both uncertainty reduction and the use of MTLP as an optimization target.

  • UO performance: GUT-O effectively reduces uncertainty and improves accuracy across LLM scales, datasets, and UQ evaluation metrics.Table 14 reports percentage changes in mean uncertainty and absolute changes in accuracy for Qwen3-1.7B and Qwen3-0.6B.
  • Optimization target: GUT-Q-derived uncertainty generally has significant positive PCCs with the MTLP optimization target across five datasets and all four Qwen3 scales.The evaluated scales are 0.6B, 1.7B, 4B, and 8B.
  • Optimization target: The reported correlations support treating MTLP as a valid optimization target for GUT-Q-derived uncertainty.This conclusion is stated for the investigated Qwen3 family and five datasets.

D.1. Additional Ablation Analyses

Ablations show that node merging is especially important for UP, while both node uncertainty and node merging are essential to GUT-Q width and height calculations.

  • Node merging is more important than node uncertainty in the UP algorithm.
  • Both node uncertainty and node merging are essential for GUT-Q-W and GUT-Q-H.

D.2. Additional Sensitivity Analyses

Sensitivity analyses examine samples, temperature, shots, and node-merging criteria, yielding recommended configurations and robustness findings across Qwen3 model scales.

  • Number of Samples K: K = 9 for Qwen3-4B, K = 12 for Qwen3-1.7B, and K = 11 for Qwen3-8B and Qwen3-0.6B balance efficiency and performance.Larger K leads to higher computational costs.
  • Temperature T: T = 1.0 for Qwen3-4B and T = 0.7 for Qwen3-1.7B and Qwen3-0.6B are recommended based on UQ performance.
  • Number of Shots F: F = 5 for Qwen3-8B and Qwen3-4B, F = 3 for Qwen3-1.7B, and F = 7 for Qwen3-0.6B are recommended based on UQ performance.
  • Node Merging Criterion: Bi-entailment, uni-entailment, and non-contradiction produce comparable UQ performance across model scales, datasets, and evaluation metrics.GUT-Q is robust against the choice of node-merging criterion.

E. Case study of the GUT

The case study applies GUT to MATH-500 instances with Qwen3-4B and compares reasoning graphs for correct and incorrect answers. Graph complexity is typically larger for incorrect instances, while GUT-O tends to produce fewer reasoning steps.

  • The MATH-500 case study applies GUT to two Qwen3-4B test instances, one incorrectly answered and one correctly answered.
  • Graph complexity metrics are typically larger for incorrectly answered instances than for correctly answered ones.The observation supports using GUT-Q to discriminate between correct and incorrect instances.
  • GUT-O tends to produce fewer reasoning steps for the same question.
  • For one binomial-expansion instance, the correct expansion yields a = 11, b = 9, c = 3, and a + b + c = 23.
  • For another instance, the reasoning identifies 17, 53, and 71 as the qualifying two-digit primes, giving an answer of 3.
Loading 2609.05284v1…