# All Roads Lead to Rome: Graph-Based Confidence Estimation for Large Language Model Reasoning

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Placed in Test-time compute and efficient thinking, one of 17 directions in LLM reasoning.
- Builds on 18 of its 39 references that are in the map.
- First posted on arXiv 16 Sep 2025.

## 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, 18 of 18)

- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [Gemma 2: Improving Open Language Models at a Practical Size](https://mlsanity.com/paper/2408.00118/) (2024)
- [Language Models (Mostly) Know What They Know](https://mlsanity.com/paper/2207.05221/) (2022)
- [Math-Shepherd: Verify and Reinforce LLMs Step-by-step without Human Annotations](https://mlsanity.com/paper/2312.08935/) (2023)
- [The Lessons of Developing Process Reward Models in Mathematical Reasoning](https://mlsanity.com/paper/2501.07301/) (2025)
- [Generating with Confidence: Uncertainty Quantification for Black-box Large Language Models](https://mlsanity.com/paper/2305.19187/) (2023)
- [FOLIO: Natural Language Reasoning with First-Order Logic](https://mlsanity.com/paper/2209.00840/) (2022)
- [Are You Sure? Challenging LLMs Leads to Performance Drops in The FlipFlop Experiment](https://mlsanity.com/paper/2311.08596/) (2023)
- [Calibrating Large Language Models with Sample Consistency](https://mlsanity.com/paper/2402.13904/) (2024)
- [Understanding the Uncertainty of LLM Explanations: A Perspective Based on Reasoning Topology](https://mlsanity.com/paper/2502.17026/) (2025)
- [Atomic Calibration of LLMs in Long-Form Generations](https://mlsanity.com/paper/2410.13246/) (2024)
- [LoGU: Long-form Generation with Uncertainty Expressions](https://mlsanity.com/paper/2410.14309/) (2024)
- [LoVeC: Reinforcement Learning for Better Verbalized Confidence in Long-Form Generations](https://mlsanity.com/paper/2505.23912/) (2025)
- [Graph-based Uncertainty Metrics for Long-form Language Model Outputs](https://mlsanity.com/paper/2410.20783/) (2024)
- [UNCLE: Benchmarking Uncertainty Expressions in Long-Form Generation](https://mlsanity.com/paper/2505.16922/) (2025)
- [Graph-based Confidence Calibration for Large Language Models](https://mlsanity.com/paper/2411.02454/) (2024)
- [VerifiAgent: a Unified Verification Agent in Language Model Reasoning](https://mlsanity.com/paper/2504.00406/) (2025)
- [GrACE: A Generative Approach to Better Confidence Elicitation and Efficient Test-Time Scaling in Large Language Models](https://mlsanity.com/paper/2509.09438/) (2025)

## Built on by (most cited first, 3 of 3)

- [Confidence Estimation for LLMs in Multi-turn Interactions](https://mlsanity.com/paper/2601.02179/) (2026)
- [A Systematic Evaluation of Black-Box Uncertainty Estimation Methods for Large Language Models](https://mlsanity.com/paper/2606.19868/) (2026)
- [GUT: Quantifying and Optimizing the Reasoning Uncertainty of LLMs via Graph Complexity](https://mlsanity.com/paper/2609.05284/) (2026)

## Abstract (arXiv)

Confidence estimation is essential for the reliable deployment of large language models (LLMs). Existing methods are primarily designed for factual QA tasks and often fail to generalize to reasoning tasks. To address this gap, we propose a set of training-free, graph-based confidence estimation methods tailored to reasoning tasks. Our approach models reasoning paths as directed graphs and estimates confidence by exploiting graph properties such as centrality, path convergence, and path weighting. Experiments with two LLMs on three reasoning datasets demonstrate improved confidence estimation and enhanced performance on two downstream tasks.