# Confidence Reasoning Graphs: Structured Confidence Estimation for LLM Agents

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in Reasoning for agents, planning and code, one of 17 directions in LLM reasoning.
- Builds on 16 of its 44 references that are in the map.
- First posted on arXiv 6 Oct 2026.

## Placed in

- LLM reasoning / [Reasoning for agents, planning and code](https://mlsanity.com/lr/reasoning-for-agents-planning-and-code/)
- LLM agents and tool use / [General LLM agent frameworks and benchmarks](https://mlsanity.com/agents/general-llm-agent-frameworks-and-benchmarks/)

## Builds on (most cited first, 16 of 16)

- [Language Models (Mostly) Know What They Know](https://mlsanity.com/paper/2207.05221/) (2022)
- [SkillsBench: Benchmarking How Well Agent Skills Work Across Diverse Tasks](https://mlsanity.com/paper/2602.12670/) (2026)
- [SWE-smith: Scaling Data for Software Engineering Agents](https://mlsanity.com/paper/2504.21798/) (2025)
- [The OpenHands Software Agent SDK: A Composable and Extensible Foundation for Production Agents](https://mlsanity.com/paper/2511.03690/) (2025)
- [MiniMax Sparse Attention](https://mlsanity.com/paper/2606.13392/) (2026)
- [UProp: Investigating the Uncertainty Propagation of LLMs in Multi-Step Agentic Decision-Making](https://mlsanity.com/paper/2506.17419/) (2025)
- [Llamas Know What GPTs Don't Show: Surrogate Models for Confidence Estimation](https://mlsanity.com/paper/2311.08877/) (2023)
- [EnterpriseOps-Gym: Environments and Evaluations for Stateful Agentic Planning and Tool Use in Enterprise Settings](https://mlsanity.com/paper/2603.13594/) (2026)
- [Agentic Uncertainty Reveals Agentic Overconfidence](https://mlsanity.com/paper/2602.06948/) (2026)
- [BAS: A Decision-Theoretic Approach to Evaluating Large Language Model Confidence](https://mlsanity.com/paper/2604.03216/) (2026)
- [Explainable Compliance Detection with Multi-Hop Natural Language Inference on Assurance Case Structure](https://mlsanity.com/paper/2506.08713/) (2025)
- [DecMetrics: Structured Claim Decomposition Scoring for Factually Consistent LLM Outputs](https://mlsanity.com/paper/2509.04483/) (2025)
- [When Agents Disagree With Themselves: Behavioral Consistency as an Uncertainty Signal for LLM Agents](https://mlsanity.com/paper/2602.11619/) (2026)
- [Evaluating Assurance Cases as Text-Attributed Graphs for Structure and Provenance Analysis](https://mlsanity.com/paper/2604.20577/) (2026)
- [Beyond Single-Turn Confidence: Trajectory-Adapted Uncertainty Quantification for LLM Agents](https://mlsanity.com/paper/2608.11552/) (2026)
- [From Sequence to Structure: Relational Uncertainty Propagation for LLM Agents](https://mlsanity.com/paper/2608.16002/) (2026)

## Abstract (arXiv)

When using an LLM agent in a consequential domain, making an informed decision about whether to trust its output or intervene requires calibrated confidence in the agent's success. Confidence estimation for agents is difficult because evidence about success is distributed across heterogeneous, interdependent steps of an agent's trajectory. Practical agentic deployments introduce further challenges: frontier LLMs often provide limited access to internal signals, agent roll-outs are costly, and training data may be unavailable or quickly become outdated. To address these challenges, we introduce Confidence Reasoning Graphs (CRGs), an inference-time framework that estimates the probability an agent accomplished its task from a single trajectory, without privileged model access or training data. Rather than compressing an execution into a single holistic judgment, a CRG begins with the claim that the agent accomplished its task, decomposes it into contextualized sub-claims grounded in trajectory evidence, estimates confidence for each terminal claim, and finally aggregates these into an overall confidence estimate. Across three agentic benchmarks, three backbone models, and three agent frameworks, CRGs yield better-calibrated confidence and stronger risk-aware decision making than verbalized, sampling-based, and white-box surrogate baselines. We further find that calibration error alone can be misleading: a white-box surrogate baseline appears well calibrated while providing near-chance discrimination. Ablations attribute CRG's improvements to claim-level confidence estimation and aggregation rather than graph construction alone. Finally, a CRG exposes the claims and trajectory evidence underlying each confidence estimate, enabling it to be audited at decision time.