PaperlayerView exact revision on arXiv

Source-linked AI summary

Confidence Reasoning Graphs: Structured Confidence Estimation for LLM Agents

Brendan King, Farima Fatahi Bayat, Jean-Flavien Bussotti, Pouya Pezeshkpour, Estevam Hruschka

arXiv:2610.07948v1cs.AIcs.CL

TL;DR

Agent confidence is difficult to estimate from heterogeneous, interdependent trajectories, especially when models are black-box, roll-outs are costly, and labeled data are unavailable. CRGs build confidence from evidence-grounded claims in a single trajectory. Across benchmarks, they improve calibration and decision utility over evaluated baselines while retaining strong discrimination.

  • Problem

    Agent confidence estimation must reason over heterogeneous, interdependent trajectories, while practical settings can restrict access to internal signals, repeated roll-outs, and labeled training data.

    Source: §1 · pp. 1–2

  • Method

    CRGs decompose task success into contextualized claims grounded in one trajectory, estimate confidence for leaf claims, and aggregate those estimates into root confidence.

    Source: §1 · p. 2, §4 · p. 4

  • Results

    CRGs improve calibration and decision utility across benchmarks over evaluated baselines while retaining strong discrimination.

    Source: §1 · p. 2, §7 · p. 10

  • Takeaways & Limitations

    CRGs provide practical, auditable confidence estimates for black-box agents without training.

    Source: §7 · p. 10

    Graph construction and evaluation inherit LLM limitations: decompositions may be incomplete, claim dependencies may be missed, and evidence may be misinterpreted.

    Source: ETHICS STATEMENT · p. 10

Abstract

from arXiv · show

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.

1 INTRODUCTION

Confidence estimation for agents must account for heterogeneous, interdependent trajectories and deployment constraints such as black-box models, costly roll-outs, and unavailable training data. The paper introduces single-trajectory Confidence Reasoning Graphs (CRGs) and reports stronger calibration and decision utility than evaluated baselines.

1 INTRODUCTION

  • The need for agent confidence arises because average success rates do not establish whether a particular output is correct, while checking an execution can be difficult across its chain of decisions and observations.An error early in that chain can affect what follows.Source: §1 · p. 1
  • Existing agent confidence estimators face practical barriers when they require privileged signals, repeated roll-outs, or labeled trajectories that can become stale.Verbalized estimates avoid those requirements but are often substantially overconfident.Source: §1 · p. 2
  • CRGs decompose task success into contextualized sub-claims, ground leaf claims in trajectory evidence, estimate their confidence, and aggregate those estimates into an overall confidence.The method evaluates one trajectory without privileged model access, repeated roll-outs, or labeled training data.Source: §1 · p. 2
  • CRGs achieve the lowest adaptive ECE and Brier score and the highest decision utility on every benchmark, outperforming verbalized and surrogate-probability baselines.Ablations attribute the gains to leaf-level confidence estimation and aggregation rather than graph construction alone.Source: §1 · p. 2
  • The evaluated CRGs span three agent LLMs and three challenging benchmarks: SWE-Bench Verified, EnterpriseOps-Gym, and SkillsBench.The benchmark names are accompanied by their original references in the paper: SWE-Bench Verified, EnterpriseOps-Gym (Malay et al., 2026), and SkillsBench (Li et al., 2026).Source: §1 · p. 2

2 RELATED WORK

Prior confidence estimation for LLMs uses internal signals, repeated outputs, or verbalized confidence, but extending these approaches to agents must address heterogeneous multi-step trajectories. Related structured-argument approaches do not quantify truth in the root claim in this setting, while a cited Bayesian approach requires labeled calibration data.

2 RELATED WORK

  • LLM confidence methods use white-box signals, agreement across sampled outputs, or verbalized confidence, while agent trajectories add heterogeneous, multi-step evidence.The cited approaches include white-box signals, sampled-output agreement, and verbalized confidence.Source: §2 · p. 2
  • Agent confidence work has used white-box signals, repeated or branching executions, or labeled trajectories, limiting direct use with costly black-box agents.Prior work on verbalized agent confidence has reported high overconfidence.Source: §2 · p. 2
  • Assurance cases structure claims and evidence, but the cited LLM assurance-case work differs from agent confidence estimation and does not quantify truth in the root claim.Hou et al. (2025) infer target truth with a Bayesian hidden Markov tree whose emission probabilities require held-out truth-labeled statements; this paper targets inference without fitted parameters or labeled calibration data.Source: §2 · pp. 2–3

3 PRELIMINARIES

The preliminaries define an agent execution as a trajectory of actions and observations, then frame confidence estimation as predicting task success from that trajectory. The evaluation uses complementary measures of calibration, ranking, probabilistic error, and accept-or-abstain utility.

3 PRELIMINARIES

  • An LLM agent is governed by an LLM policy and interacts with an environment through a sequence of actions and observations, summarized as trajectory τ.The agent’s solution may be an explicit final response or a change made to the environment.Source: §3 · p. 3
  • Confidence estimation maps an observable trajectory to a score estimating the probability that the agent’s solution successfully completes the task.The stated deployment constraints are black-box access to textual trajectory content, one completed execution, and no labeled trajectories or supervised fitting.Source: §3 · p. 3
  • Adaptive ECE measures calibration, AUROC measures ranking of successful versus unsuccessful trajectories, and Brier score measures squared probabilistic error.Behavioral Alignment Score averages accept-or-abstain utility across risk thresholds and penalizes confident failures.Source: §3 · p. 3

4 METHODOLOGY

CRGs assess task success by building an evidence-grounded claim structure from a trajectory, estimating confidence at its leaves, and aggregating those estimates to the root. The method uses contextualized claim refinements, cited evidence, and a product aggregation based on a conditional-independence approximation.

4 METHODOLOGY

  • CRGs turn the task-success claim into a structured argument by decomposing it, grounding leaf claims in trajectory evidence, estimating leaf confidence, and aggregating to the root.The overview also presents the graph as inspectable: low-confidence paths can be traced to uncertain leaf claims and their associated evidence.Source: §4 · pp. 3–4, Figure 1 · p. 4

4.1 CLAIM DECOMPOSITION

  • Decomposition splits a claim into jointly sufficient sub-claims, while particularization restates it for the specific task; both preserve parent equivalence to the conjunction of children.Refinement is capped at depth k = 5, with sensitivity examined separately.Source: §4.1 · pp. 4–5

4.2 EVIDENCE GATHERING

  • An LLM attaches trajectory evidence to leaf claims, citing steps and labeling each attachment Supported, Undermined, or Unverified.Unverified evidence can capture an agent stopping without confirming that an action succeeded.Source: §4.2 · p. 5

4.3 ESTIMATING LEAF CONFIDENCE

  • A verbalized-confidence LLM estimates each leaf claim separately from its attached evidence and a reduced trajectory.The reduction retains the prefix through the last cited step, but cannot recover evidence omitted during graph construction.Source: §4.3 · p. 5

4.4 AGGREGATING CONFIDENCE TO THE ROOT

  • CRG approximates root confidence as the product of leaf confidences, assuming children introduced at each decomposition are conditionally independent given the trajectory.The root claim holds exactly when all leaf claims hold, but its joint probability generally requires modeling dependencies among leaves.Source: §4.4 · pp. 5–6

5 EXPERIMENTAL SETUP

The experiments test confidence estimators on diverse agent trajectories and compare CRG with black-box verbalized and surrogate-probability baselines. They report calibration, discrimination, and decision utility using complementary metrics.

Benchmarks and Trajectories

  • Three benchmarks cover software engineering, enterprise workflows, and long-horizon skill use, with one OpenHands trajectory per problem and verifier-provided success labels.The study focuses on harder problems where success is less saturated; transfer beyond OpenHands is evaluated separately.Source: §5 · p. 6

CRG Settings

  • CRG uses Qwen-3.8 27B or GPT-5.6 Sol as its estimator LLM, with medium reasoning effort and a maximum refinement depth of five.The depth is used without per-benchmark tuning.Source: §5 · p. 6

Baselines

  • Baselines include direct verbalized confidence, graph-guided verbalization, ten-sample verbal consistency, and surrogate-LM sequence probability.Verbal Consistency is run only with Qwen-3.8 27B because of inference cost.Source: §5 · p. 6

Metrics

  • Adaptive ECE, Brier score, AUROC, and BAS measure calibration, probabilistic error, ranking, and decision utility, respectively.The reported OpenHands results average over agent LLMs; adaptive ECE uses ten bins.Source: §5 · p. 6, Table 2 · p. 7

6 RESULTS AND ANALYSES

Across the main benchmarks and framework-transfer tests, CRG improves calibration and decision utility, while calibration and discrimination can diverge. Ablations attribute the main gains to leaf-level confidence scoring and aggregation; further analyses test robustness and cost.

6.1 MAIN RESULTS

  • CRGs achieve the lowest adaptive ECE and Brier score and highest BAS on all three benchmarks, with best or second-best AUROC; Figure 2 shows strong calibration across benchmarks.Qwen-3.8 27B CRG adaptive ECE is 0.09, 0.13, and 0.11 on SWE-Bench Verified, EnterpriseOps-Gym, and SkillsBench, respectively.Source: §6.1 · p. 7, Figure 2 · p. 8

6.2 GENERALIZATION TO OTHER AGENT FRAMEWORKS

  • Adaptive ECE falls from 0.19 to 0.05 on Codex and 0.11 on Claude Code; CRG has the lowest Brier score and highest BAS on both, but weaker AUROC on Claude Code.The transfer evaluation uses SWE-Bench Verified trajectories from the two frameworks.Source: Table 3 · p. 9, §6.2 · p. 9

6.4 ADDITIONAL FINDINGS

  • CRG gains persist with temperature scaling and varying reasoning effort, and CRG remains effective despite imperfect refinement-invariant and independence-approximation adherence.The additional analyses also report cost efficiency and case studies in which claim graphs can be audited and overruled at inference time.Source: §6.4 · p. 9

7 CONCLUSION

The conclusion presents CRGs as a way to estimate task-success confidence from a single black-box trajectory by decomposing success into evidence-grounded claims and aggregating their confidence. It reports improved calibration and decision utility across benchmarks, while cautioning that estimates require verification and human oversight.

7 CONCLUSION

  • CRGs estimate task-success confidence from a single black-box trajectory by decomposing success into evidence-grounded claims and aggregating their confidences.The resulting estimates are intended as decision support, not guarantees of correctness.Source: §7 · pp. 9–10
  • CRGs improve calibration and decision utility across benchmarks while retaining strong discrimination, enabling auditable confidence estimates without training.The graph exposes the claims and evidence underlying each estimate.Source: §7 · p. 10
  • Incomplete decompositions, missed claim dependencies, or misinterpreted evidence can undermine estimates, so CRG confidence should be paired with verification and human oversight.The authors warn that inaccurate or overconfident estimates could create false reassurance, especially in high-stakes applications.Source: ETHICS STATEMENT · p. 10

A.1 BENCHMARKS AND TRAJECTORY COLLECTION

The evaluation set uses challenging tasks from SWE-Bench Verified, SkillsBench, and EnterpriseOps-Gym, with trajectories collected mainly through OpenHands. The appendix also describes separate development-set problems and binary success labeling.

A.1 BENCHMARKS AND TRAJECTORY COLLECTION

  • The test set focuses on more challenging benchmark tasks because confidence estimation is most informative when agent success is not saturated.Source: TEST SET: MAIN EXPERIMENTS · p. 14
  • The test set retains 306 harder SWE-Bench Verified problems, 81 Extended or Extreme SkillsBench problems with supplied skills, and 325 EnterpriseOps-Gym problems across eight domains.EnterpriseOps-Gym samples half the problems in each domain to preserve domain composition.Source: TEST SET: MAIN EXPERIMENTS · pp. 14–15
  • The main evaluation contains 900 SWE-Bench, 219 SkillsBench, and 975 EnterpriseOps-Gym OpenHands trajectories, after excluding runs that crash or exceed the representable context length.SWE-Bench runs use a 500-iteration cap; SkillsBench and EnterpriseOps-Gym use a 100-iteration cap.Source: TEST SET: MAIN EXPERIMENTS · p. 15
  • Each scored trajectory receives a binary success label from its benchmark’s native verifier, with SkillsBench partial reward counted as failure.For SWE-Bench Verified and EnterpriseOps-Gym, the label is resolved status in the benchmark evaluation report.Source: TEST SET: MAIN EXPERIMENTS · p. 15
  • The authors also use 64 sampled SWE-Smith problems and 64 non-overlapping EnterpriseOps Gym problems for development, without tuning hyperparameters on that set.The development set informed initial prompt development; the test set evaluates transfer to harder SWE-Bench Verified problems and a new SkillsBench domain.Source: DEVELOPMENT SET · p. 15

A.2 CALIBRATION AND BRIER SCORE

This section defines Brier score and adaptive ECE for evaluating confidence estimates against observed task outcomes. Adaptive ECE uses approximately equal-count bins to compare confidence with success frequency.

A.2 CALIBRATION AND BRIER SCORE

  • Brier score is the average squared difference between each trajectory’s estimated success probability and its binary outcome.The passage defines c_i as estimated success probability and y_i as observed outcome; lower values indicate better probabilistic predictions.Source: §A.2 · pp. 15–16
  • Adaptive ECE sorts trajectories by confidence and divides them into 10 approximately equal-count bins.Bin sizes differ by at most one, and tied confidences retain their original order under a stable sort.Source: §A.2 · p. 15
  • Equal-count binning avoids sparsely populated bins, reducing the variance of per-bin accuracy estimates, especially on smaller datasets.The cited passage also reports that equal-count binning has been reported to have lower bias.Source: §A.2 · p. 16
  • ECE measures the gap between confidence and observed success frequency within bins, while Brier score summarizes squared prediction error.Lower values indicate better probabilistic predictions for both metrics.Source: §A.2 · p. 16

A.3 CASE STUDIES

The case studies show how CRGs connect task-specific claims and trajectory evidence to confidence estimates, including both a cautious estimate after high-confidence subclaims and an incorrect estimate caused by missing evidence. The section also situates CRGs on a cost–calibration tradeoff.

A.3 CASE STUDIES

  • Leaf confidences of 0.93–0.96 for an HR-enrollment task aggregate to 0.71 for the primary objective and 0.58 at the root.The root is more cautious after integrity and policy-compliance claims are also accounted for.Source: §A.3 · p. 16

A.4 COST

CRG lies on the cost–calibration Pareto frontier across the three benchmarks, trading additional inference cost for lower adaptive ECE than the cheaper surrogate. On SWE-Bench Verified, greater reasoning effort makes verbalized baselines more expensive than CRG without matching its calibration.

A.4 COST

  • Inference usage is converted to estimated cost per trajectory in USD because methods differ in model size and prompt and completion length.Figure 5 compares each estimator’s inference cost and calibration.Source: §A.4 · p. 17
  • Across all three benchmarks, CRG lies on the cost–calibration Pareto frontier with the cheaper but less calibrated Surrogate LNSP, costing approximately $0.04–$0.07 per trajectory.CRG achieves lower adaptive ECE on every benchmark; the largest gap is on EnterpriseOps-Gym (0.13 vs. 0.22).Source: §A.4 · p. 17
  • On SWE-Bench Verified, increased reasoning effort can make verbalized baselines more expensive than CRG while leaving them substantially less calibrated.The passage suggests the improvement comes from how CRG structures and aggregates confidence estimation, rather than simply from additional test-time compute.Source: §A.4 · p. 17

A.5 ECE ROBUSTNESS TO BINNING

This appendix examines CRG robustness and design choices, including construction and scoring, prompted baselines, a graph-informed ablation, binning, and task resampling. It also evaluates aggregation assumptions and graph quality, and documents the prompts and claim-tree construction used by CRGs.

A.8 SURROGATE LOG-PROBABILITY AGGREGATIONS

  • CRGs achieve the best ECE, Brier score, AUROC, and BAS overall among surrogate methods, while all surrogate methods discriminate poorly.SP aggregation yields estimates consistently near zero; LNSP rankings vary by benchmark, with Action LNSP (min) at ECE 0.34 versus 0.10 for Action LNSP (last) on SWE-Bench Verified.Source: Table 7 · p. 19, §A.8 · p. 20

A.9 AGGREGATION RULES

  • The goal-leaf product has the lowest ECE and Brier score, best BAS, and strong discrimination on EnterpriseOps-Gym, supporting conjunctive aggregation.The product approximates the conjunction probability under conditional independence, which cannot be assumed in practice; Hou et al. (2025) use held-out labeled data and are included only diagnostically.Source: §A.9 · p. 20, Table 8 · p. 21

A.10 TEMPERATURE-SCALED BASELINES

  • After temperature scaling, CRG remains the best-calibrated method and achieves the highest BAS.Temperatures are chosen per method by minimizing development-set NLL, with a maximum temperature of 15 when no finite minimum exists.Source: §A.10 · p. 21, Table 9 · p. 21

A.11 GRAPH QUALITY ANALYSIS

  • CRGs satisfy sufficiency and non-redundancy more consistently than necessity and particularization, and neither setting achieves near-perfect decomposition.Judges unanimously find GPT-5.6 Sol graphs better maintain the refinement invariant but contain more overlapping sibling claims; imperfect graphs nevertheless yield calibration and decision-utility gains.Source: §A.11 · p. 22, Table 10 · p. 22

A.12.2 CRG CONSTRUCTION

  • CRG prompts define success for each domain and construct a claim tree whose atomic leaves can be evaluated using trajectory evidence.The tree decomposes success into necessary and sufficient conditions, with goal nodes for claims and evidence nodes for observations; domain-specific success definitions are included in CRG and verbalized-baseline prompts, and prompt text uses runtime placeholders.Source: §A.12.1 · p. 22, §A.12 · p. 22, §A.12.2 · p. 23
  • CRG construction separates claim decomposition from evidence gathering, linking atomic success conditions to supporting, undermining, or missing trajectory evidence.Decomposition uses necessary-and-sufficient child claims and task-aware particularization; evidence is attached to atomic leaves with precise trajectory step numbers when available.Source: §A.12.2 · pp. 24–26

A.12.3 CRG LEAF-CONFIDENCE ESTIMATION

  • Leaf claims receive independent confidence estimates, with evaluators judging each target claim rather than overall task success.Estimators weigh evidence and predecessor confidences, and use priors to represent uncertainty when claims are unverified rather than treating missing verification as falsehood.Source: §A.12.3 · pp. 26–27

A.12.4 PROMPTED BASELINES

  • Prompted baselines include verbal confidence, graph-scaffolded reasoning, repeated success judgments, and surrogate sequence probability.Verbal Consistency samples ten responses and uses the fraction ending in “Successful: True”; Surrogate LNSP uses length-normalized probability of the final action, while Reason-as-Graph uses a graph scaffold without returning a persistent graph.Source: §A.12.4 · p. 28

A.12.5 REASON-WITH-GRAPH ABLATION

  • Reason-with-Graph receives the constructed CRG but directly verbalizes root confidence instead of scoring and aggregating leaf claims.Source: §A.12.5 · p. 28
  • The Reason-with-Graph ablation prompts judges to assess the root claim from graph decomposition and evidence, accounting for missing support and conflicts without assuming claims or evidence are correct.The graph contains auditable goal claims, subgoals, concrete evidence, and links indicating decomposition or evidential support, opposition, or uncertainty.Source: §A.12.5 · p. 29

A.14 THEORETICAL FOUNDATIONS OF CRG CONFIDENCE AGGREGATION

  • The aggregation analysis derives root confidence from contextualized claims, first establishing leaf equivalence, then characterizing dependence-aware joint probability, and finally deriving product aggregation under conditional independence.Probabilities are epistemic and conditioned on the observed trajectory; the trajectory need not determine claim truth.Source: §A.14 · p. 29

A.14.1 LEAF EQUIVALENCE

  • When each internal claim is intended to equal the conjunction of its children, the root claim is equivalent to the conjunction of all leaves, though LLM-generated refinements may not always satisfy that intended semantics.Leaf claims need not be logically independent for this equivalence to hold.Source: §A.14.1 · p. 30

A.14.2 DEPENDENCE-AWARE AGGREGATION

  • Under the refinement invariant, root probability is the joint probability that all leaf claims hold; marginal leaf probabilities alone generally identify only an interval when dependence is unknown.The dependence-aware proposition requires no independence assumption.Source: §A.14.2 · p. 31

A.14.3 PRODUCT AGGREGATION

  • Product aggregation approximates the joint probability under conditional independence; overlapping or positively associated leaves may cause double-counting and underestimation, while other dependence can cause overestimation.Non-redundancy is only a diagnostic for obvious independence violations, and the product is not necessarily a lower bound when independence fails.Source: §A.14.3 · pp. 32–33

Related papers

Loading 2610.07948v1…