When deploying large language model (LLM) agents in consequential domains, a calibrated confidence estimate is essential for deciding whether to trust the output or intervene. Traditional confidence estimation is hard because evidence of success is spread across heterogeneous, interdependent steps of the agent’s trajectory, and practical deployments often lack internal model signals, incur costly roll‑outs, and may not have up‑to‑date training data. To tackle these issues we introduce Confidence Reasoning Graphs (CRGs), an inference‑time framework that estimates the probability of task completion from a single trajectory without privileged model access or extra training data.
The key idea of a CRG is to start from the claim "the agent accomplished the task" and recursively decompose it into contextualized sub‑claims that are directly grounded in observable evidence from the trajectory. Each terminal sub‑claim receives an independent confidence estimate, and these estimates are aggregated to produce an overall confidence score. This preserves fine‑grained evidence while avoiding the coarse‑grained compression of the entire execution into a single judgment.
Across three agentic benchmarks, three backbone LLMs, and three agent frameworks, CRGs consistently outperform verbalized, sampling‑based, and white‑box surrogate baselines in terms of calibration quality and risk‑aware decision making. Importantly, calibration error alone can be misleading: some white‑box surrogates appear well‑calibrated yet exhibit near‑chance discrimination. Ablation studies attribute CRG’s gains mainly to claim‑level confidence estimation and aggregation, rather than to the graph construction itself.
Moreover, a CRG exposes the claims and the corresponding trajectory evidence underlying each confidence estimate, enabling real‑time auditability of the agent’s decisions.
Review: CRGs offer an interpretable, data‑efficient confidence estimation approach for LLM agents that balances calibration accuracy with risk control, making it a promising candidate for real‑world deployments.