Confidence Reasoning Graphs: Structured Confidence Estimation for LLM Agents

In consequential domains, aggregate agent success rates do not establish whether an individual execution can be trusted. Estimating confidence requires integrating heterogeneous evidence across interdependent trajectory steps, often without token-level probabilities, repeated roll-outs, or gold trajectories. 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 one holistic judgment, a CRG recursively decomposes the claim that the task was accomplished into contextualized sub-claims, and grounds each in evidence from specific trajectory steps as supporting it, undermining it, or leaving it unverified. Confidence is then estimated for each leaf claim and aggregated into the root. Across three agentic benchmarks, three backbone models, and three frameworks, we find that CRGs produce better-calibrated confidence than verbalized, sampling-based, and white-box surrogate baselines, and supports better risk-aware decisions. Our results also illustrate why calibration should not be evaluated in isolation: a surrogate baseline can achieve low calibration error while providing near-chance discrimination. Ablations attribute the gains to leaf-level confidence estimation and aggregation rather than graph construction alone. Finally, the resulting graph exposes the claims and trajectory evidence behind each estimate, allowing a confidence score to be audited rather than taken on trust.