GUT: Quantifying and Optimizing the Reasoning Uncer... | AI Research

GUT: Quantifying and Optimizing the Reasoning Uncertainty of LLMs via Graph Complexity
Large Language Models (LLMs) often struggle with "reasoning uncertainty," where the same prompt can lead to wildly different, and sometimes nonsensical, reasoning paths. This happens because LLMs use stochastic sampling to generate text, creating a branching tree of possibilities. This paper introduces the Graph-complexity-based UncerTainty (GUT) method, which models these potential reasoning branches as a directed acyclic graph (DAG). By analyzing the structure and complexity of these graphs, the authors provide a way to measure how uncertain a model is and a framework to actively reduce that uncertainty. The same ai evaluation question is explored in Instruction Duplication as an Inference-Time Control..., which adds a research perspective.

Mapping the Reasoning Space

The core of the GUT method is the construction of a graph that captures all potential reasoning paths for a given problem. Instead of looking at a single chain of thought, the researchers sample multiple reasoning sequences and merge semantically equivalent steps using a Natural Language Inference (NLI) model. This creates a clear map of the "reasoning space." By identifying where the model branches out into many different directions, the researchers can visualize and quantify the model's confusion.

Measuring Uncertainty

The authors propose two modules to handle this uncertainty. The first, GUT-Q (Quantification), measures uncertainty by calculating "graph complexity." It looks at the topology of the reasoning graph—such as its width (the number of branches at a single step) and its height (the length of the reasoning chain)—combined with the statistical uncertainty of the tokens themselves. By assigning uncertainty scores to nodes in the graph, the researchers can estimate how reliable a model’s reasoning process is. They offer three ways to estimate this complexity: Width, Height, and Uncertainty Propagation, with the latter often performing best for tasks like selective generation. The same large language models question is explored in Spurious Advantage Hidden in GRPO, which adds a research perspective.

Optimizing for Better Reasoning

The second module, GUT-O (Optimization), focuses on reducing uncertainty. Because the graph-based uncertainty measure is not directly differentiable (meaning it cannot be easily used in standard training), the authors use an indirect approach. They use a differentiable proxy—Mean Token Log Probability—as a reward function within a reinforcement learning framework. By treating "negative uncertainty" as a reward, the model is encouraged to follow reasoning paths that are more stable and less prone to the divergent, nonsensical branches that characterize high-uncertainty outputs.

Key Findings

The researchers validated GUT across four different LLMs and five datasets. Their experiments showed that the GUT-Q module outperformed 45 other uncertainty quantification methods in selective generation tasks. Furthermore, the GUT-O module successfully reduced reasoning uncertainty while simultaneously improving the overall accuracy of the models' answers. These results suggest that by explicitly modeling the branching nature of LLM reasoning, developers can gain better control over the reliability and consistency of AI outputs. The same ai evaluation question is explored in Calibrated Enough to Know, Not Calibrated..., which adds a research perspective. as detailed in the full paper on Arxiv