mlsanityData to 7 Oct 2026

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

arXiv 2509.12908 ↗First posted 16 Sep 2025cs.CL cs.AIcited by 3

On the map: LLM reasoning → Test-time compute and efficient thinking

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.

Key facts. Cited by 3 papers in the map (data through 7 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.

Builds on

18 of 39 references.

Closest ancestors · 2

Same direction, newest first

  1. 2025GrACE: A Generative Approach to Better Confidence Elicitation and Efficient Test-Time Scaling in Large Language Models11 Sep
  2. 2022Language Models (Mostly) Know What They Know11 Jul

Other references · 16

  1. 2021Training Verifiers to Solve Math Word Problemscited by 9,743
  2. 2024Gemma 2: Improving Open Language Models at a Practical Sizecited by 1,928
  3. 2023Math-Shepherd: Verify and Reinforce LLMs Step-by-step without Human Annotationscited by 895
  4. 2025The Lessons of Developing Process Reward Models in Mathematical Reasoningcited by 402
  5. 2023Generating with Confidence: Uncertainty Quantification for Black-box Large Language Modelscited by 286
  6. 2022FOLIO: Natural Language Reasoning with First-Order Logiccited by 233
  7. 2024Calibrating Large Language Models with Sample Consistencycited by 72
  8. 2023Are You Sure? Challenging LLMs Leads to Performance Drops in The FlipFlop Experimentcited by 71
  9. 2025Understanding the Uncertainty of LLM Explanations: A Perspective Based on Reasoning Topologycited by 24
  10. 2024Atomic Calibration of LLMs in Long-Form Generationscited by 23
  11. 2024LoGU: Long-form Generation with Uncertainty Expressionscited by 19
  12. 2025LoVeC: Reinforcement Learning for Better Verbalized Confidence in Long-Form Generationscited by 17
4 more
  1. 2024Graph-based Uncertainty Metrics for Long-form Language Model Outputscited by 11
  2. 2025UNCLE: Benchmarking Uncertainty Expressions in Long-Form Generationcited by 11
  3. 2024Graph-based Confidence Calibration for Large Language Modelscited by 10
  4. 2025VerifiAgent: a Unified Verification Agent in Language Model Reasoningcited by 10

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 3.

3 papers.

  1. 2026Confidence Estimation for LLMs in Multi-turn Interactionscited by 12
  2. 2026A Systematic Evaluation of Black-Box Uncertainty Estimation Methods for Large Language Modelscited by 2
  3. 2026GUT: Quantifying and Optimizing the Reasoning Uncertainty of LLMs via Graph Complexitycited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026Diagnosing Multi-step Reasoning Failures in Black-box LLMs via Stepwise Confidence Attribution
  2. 2026Confidence over Time: Confidence Calibration with Temporal Logic for Large Language Model Reasoning
  3. 2026How Reliable are Confidence Estimators for Large Reasoning Models? A Systematic Benchmark on High-Stakes Domains
  4. 2026Probability is Not Enough: Exploring and Counting Divergent Tokens for Reasoning Uncertainty Quantification in LLMs
  5. 2026ConfidenceBench: Evaluating Confidence Calibration in Large Language Models
  6. 2023Reasoning on Graphs: Faithful and Interpretable Large Language Model Reasoning
  7. 2026Evaluating LLMs on Large-Scale Graph Property Estimation via Random Walks
  8. 2026Debate-on-Graph: Reliable and Adaptive Reasoning of Large Language Model on Uncertain Knowledge Graph