Recent advances have dramatically improved the reasoning ability of large language models (LLMs), yet their reasoning often exhibits uncertainty: given identical prompts, each step can spawn multiple divergent branches, some of which are implausible or nonsensical. To study this phenomenon systematically, we introduce Graph‑complexity‑based Uncertainty (GUT). The key idea is to encode all potential reasoning branches into a directed acyclic graph (DAG), guaranteeing that the graph space exhaustively covers possible paths. Built on this representation, GUT consists of two modules: a Quantification module (GUT‑Q) and an Optimization module (GUT‑O). GUT‑Q approximates the complexity of the reasoning space by measuring the structural complexity of the graph, yielding an uncertainty score; GUT‑O treats negative uncertainty as a reinforcement‑learning reward, encouraging the model to favor more certain trajectories during generation. Experiments on four mainstream LLMs and five benchmark datasets demonstrate that GUT markedly reduces branch dispersion and improves answer quality.
Review: GUT offers an interpretable graph‑based perspective for measuring and mitigating LLM reasoning uncertainty, combining solid theoretical grounding with practical impact, and merits further investigation on larger models and multimodal tasks.