acceptodds
Under review as a conference paper at ICLR 2027

Confidence Reasoning Graphs: Structured Confidence Estimation for LLM Agents

Abstract

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.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
confidence estimation, uncertainty quantification, agents, black-box estimation

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_tm49OpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper proposes Confidence Reasoning Graphs (CRGs) for estimating the success probability of LLM agents. It recursively decomposes the claim "the task was accomplished" into contextualized sub-claims and attaches trajectory evidence labeled Supported, Undermined, or Unverified. Each leaf is scored by verbalized confidence, and the scores are multiplied under a conditional-independence approximation.

Critical strengths

The paper clearly motivates confidence estimation without labeled calibration data, addressing the practical challenges of collecting and maintaining labeled agent’s execution.

The evaluation goes beyond calibration error by reporting AUROC and BAS. It also usefully demonstrates that low ECE alone does not imply reliable instance-level discrimination, as illustrated by the near-chance AUROC of Surrogate LNSP despite its relatively low ECE.

Critical weaknesses

W1. While the experimental results are encouraging, the paper does not sufficiently explain or directly validate whether the leaf-level verbalized probabilities are reliable enough to support confidence estimation without labeled calibration data. It also remains unclear how errors in these probabilities propagate through multiplication and affect calibration gains and overall performance.

W2. The experimental comparison is informative, but several additions or clarifications could further strengthen it. (i) Table 2 reports CRG results only with Qwen-3.8 27B, while direct verbalization and Reason-as-Graph are evaluated with both Qwen-3.8 27B and GPT-5.6 Sol. Including the CRG + GPT-5.6 Sol results, if available, would help assess whether the gains are robust across estimator models. (ii) Verbal Consistency is evaluated only with Qwen-3.8 27B. Results with GPT-5.6 Sol, even on a representative subset, would provide a more complete comparison.

W3. The results are promising, particularly in calibration and decision utility. However, the margins relative to the strongest baseline, Surrogate LNSP, are relatively modest in some settings—for example, ECE of 0.09 versus 0.10 and BAS of 0.37 versus 0.36 on SWE-Bench, and BAS of 0.08 versus 0.06 on EnterpriseOps-Gym. Presenting confidence intervals and paired significance tests for the main comparison against Surrogate LNSP directly in the main text would make it easier to assess the robustness of these differences.

Questions for authors

Q1. Does the number of leaf nodes affect CRG’s overall performance?

Q2. With only a small labeled calibration set, would BTProp or a calibrated verbalizer outperform CRG?

Q3. Could the reported calibration gains be partly explained by the confidence reduction induced by multiplication?

Q4. Does CRG exploit meaningful evidence signals at the leaf level, or would most of its gains persist through multiplicative confidence shrinkage alone even if those signals were disrupted?

10 comments
AuthorsOpenReview ↗

Response to W1 (Part 1/2): Reliability of leaf estimates

W1 (Part 1/2): Reliability of leaf estimates

A. On Reliability of Leaf Estimates: This is a good point: to address this, we evaluate the truth of each claim produced by our CRG decomposition and then compute the reliability of our leaf-level estimates for these claims in Appendix M. We consider a claim to be true if its proposition about the task and agent's trajectory holds with respect to the itemized verifier output logs used for evaluating that task. For example, a claim that a coding agent's solution "introduced no regressions" would be labeled true if all pass-to-pass regression tests in the verifier pass, even if the overall verifier indicates the agent failed. We found our leaf-level estimates to be reliable and discriminative:

Claim-Labeling Method:

Following Hilkenmeier et al. (2026), we label the ground-truth of each claim using three independent LLM evaluators (GPT-5.6 Sol, Qwen3.8-27B, and Gemini 3.6 Flash), and have a human adjudicate any claims in which the three verdicts are not unanimous (Heseltine & Clemm von Hohenberg, 2024). When labeling claims, we provide the task, trajectory, claim and verifier logs, allowing the LLM annotator to evaluate a claim with all available signals about the truth of that claim with respect to the final state of the agent’s environment. We observe substantial agreement between panel LLMs (average Cohen’s kappa of 0.74), with 90.4% of judgments being unanimous. For 50 graphs from each estimator LLM in our development set (25 per benchmark), this resulted in the following set of labeled claims:

GraphsTrueFalseTotal
Qwen3.8-27B26526291
GPT-5.6 Sol45968527
Claim-Level Results:

Using the confidence estimates CRGs assigned to leaf-level claims at runtime, we find our estimates are both well-calibrated (Adaptive ECE, Brier) and discriminative (AUROC):

CRG Model# ClaimsECE (↓)Brier (↓)AUROC (↑)
Qwen3.8-27B2910.0350.0510.878
GPT-5.6 Sol5270.0480.0600.894

These results indicate that:

  1. Our leaf-level estimates are reliable: our confidence estimates are well calibrated and can reliably distinguish true and false claims.
  2. Our motivating premise holds: a simple verbalized-confidence estimator is more discriminative and better calibrated on concrete, low-level claims than on a high-level claim such as ‘the agent succeeded’ as evaluated by our baselines in Table 2 of the paper. This is further supported by CRGs' well-calibrated full-trajectory confidence estimates.

We have added this claim-level analysis to the revised paper (Appendix M).

AuthorsOpenReview ↗

Response to W1 (Part 2/2), as well as Q3, Q4: role of multiplicative confidence shrinkage and leaf-level signals

W1 (Part 2/2), Q3, Q4: role of multiplicative confidence shrinkage and leaf-level signals

W1 raises additional concerns about propagation’s influence vs. the quality of our leaf estimates. While the analysis in part 1 of our response evaluates leaf quality directly, here we compare CRGs to ablations which control for the influence of leaf count and multiplicative confidence shrinkage. We believe this analysis also addresses your Questions 3 & 4, but please correct us if we are mistaken.

We compare CRGs to two ablations that use randomized variants: let PleafP_{leaf} be the pool of confidence values assigned to any leaf by CRGs for a given model and benchmark, and let PfinalP_{final} be the pool of final (root) confidences that CRG assigns for a given model and benchmark. We compare:

  1. CRG (ours): our method without modification: each leaf gets its original assigned confidence.
  2. Random leaf confidences: given a graph produced by CRGs, replace each leaf confidence with an independent sample from PleafP_{leaf} with replacement. Then propagate as normal (product of leaves). This assesses whether our calibration/discrimination results are explained by leaf count and multiplicative confidence shrinkage alone.
  3. Random final confidence: ignore the graph and sample a random final confidence value from the distribution of observed final confidences for that model & benchmark (PfinalP_{final}). This assesses whether our results are explained by the overall distribution of CRG confidences alone (e.g., a mean confidence close to the success rate), rather than by assigning the right confidence to the right trajectory.

We report each randomized variant as the mean over 5 random seeds.

ModelMethodSWE-Bench VerifiedEnterpriseOps-GymSkillsBench
ECE (↓)Brier (↓)AUROC (↑)BAS (↑)ECE (↓)Brier (↓)AUROC (↑)BAS (↑)ECE (↓)Brier (↓)AUROC (↑)BAS (↑)
Qwen3.8-27BRandom final0.110.220.500.350.200.290.500.040.230.320.480.08
Qwen3.8-27BRandom leaf0.100.220.510.350.240.310.500.030.240.320.540.09
Qwen3.8-27BCRG0.090.200.570.370.130.240.620.080.110.240.650.14
GPT-5.6 SolRandom final0.210.280.490.300.290.340.500.020.350.390.47−0.02
GPT-5.6 SolRandom leaf0.230.300.500.290.340.360.500.010.360.400.530.04
GPT-5.6 SolCRG0.160.230.620.360.240.290.670.060.220.290.650.09

We observe that CRGs outperform both these ablations, often substantially, suggesting that the confidence value we assign to each leaf carries valuable information for estimating task success that is not explained by the structure of the decomposition or number of leaves in a given graph.

AuthorsOpenReview ↗

Response to W2: Clarification of Results

W2: Clarification of Results

(i) Table 2 reports CRG results only with Qwen-3.8 27B, while direct verbalization and Reason-as-Graph are evaluated with both Qwen-3.8 27B and GPT-5.6 Sol. Including the CRG + GPT-5.6 Sol results, if available, would help assess whether the gains are robust across estimator models. (ii) Verbal Consistency is evaluated only with Qwen-3.8 27B. Results with GPT-5.6 Sol, even on a representative subset, would provide a more complete comparison.

(i) To clarify, we do report CRG results with both Qwen-3.8 27B and GPT-5.6 Sol in Table 2:

SWE-Bench VerifiedEnterpriseOps-GymSkillsBench
EstimatorLLMECE↓Brier↓AUROC↑BAS↑ECE↓Brier↓AUROC↑BAS↑ECE↓Brier↓AUROC↑BAS↑
CRG (ours)GPT-5.6 Sol0.160.230.620.360.240.290.670.060.220.290.650.09
CRG (ours)Qwen-3.8 27B0.090.200.570.370.130.240.620.080.110.240.650.14

We find the Qwen CRG setting to be better calibrated and achieve higher utility, though the GPT-5.6 Sol setting is the better discriminator. Both exhibit strong performance across benchmarks.

(ii) A complete test-set run of Verbal Consistency with GPT-5.6 Sol would be cost-prohibitive, because it samples many generations per trajectory rather than only 1. We believe this approach's extreme cost and poor performance in the Qwen-3.8 27B setting justify its exclusion from the main results. To address this weakness, we run this GPT 5.6 Sol Verbal Consistency baseline on the development set using 8 true/false sampled judgments per trajectory (8 is the most GPT-5.6 Sol allows in one request):

EstimatorLLMECE↓Brier↓AUROC↑BAS↑
Verbal ConsistencyGPT-5.6 Sol0.260.290.73−6.90
Verbal ConsistencyQwen-3.8 27B0.320.330.66−9.97
CRG (ours)Qwen-3.8 27B0.080.220.700.19

We find that while GPT-5.6 Sol improves on Qwen-3.8 27B, Verbal Consistency remains poorly calibrated with both LLMs (ECE 0.26 and 0.32, against 0.08 for CRGs) and has a strongly negative BAS. The highly negative BAS is due to extreme over-confidence, as verbal consistency frequently predicts a confidence of 1.0 (all judgments being true), even for incorrect solutions.

Reviewer_BuUgOpenReview ↗
Rating
3(+1)
Confidence
4
Informativeness
2
Presentation
3
Soundness
2(+1)
Read review
Paper summary

The authors propose a new confidence estimation method by building a graph-structured representation of the agent's inference trajectory and estimating confidence over the structured trajectory. The method was evaluated for both open-source and proprietary black-box models on three realistic agentic benchmarks, showing somewhat promising confidence estimation quality in terms of some metrics.

Critical strengths
  • I believe the confidence estimation and uncertainty modeling of LLM agents are nowadays among the most important topics. The authors work on a timely and impactful topic.
  • The proposed method makes sense and can be applied to both black-box / white-box LLMs.
  • The authors conduct evaluation on realistic agent benchmarks beyond simple multi-step QA-style toy benchmarks.
Critical weaknesses

Weaknesses

  1. Questionable computational efficiency. The authors argue that multi-rollout sampling methods are computationally expensive because they require multiple forward passes. However, their own method also involves multiple expensive LLM inference steps, including recursive claim decomposition, evidence gathering, and separate estimator LLM calls for each leaf claim. Although the authors report inference costs in Appendix A.4, it is unclear whether their method actually offers a favorable cost-performance tradeoff compared to multi-rollout approaches. A direct comparison under matched inference budgets is missing in the main body of paper.
  2. Methodological complexity and reliability of LLM-based confidence estimation. Compared to simple verbalized confidence, the proposed method involves a very complex, complicated multi-stage pipeline. More importantly, the final confidence estimates still fundamentally rely on verbalized confidence generated by an estimator LLM for individual claims. There is no guarantee that these leaf-level estimates are accurate or better calibrated than direct verbalized confidence. The authors do not sufficiently validate the reliability of these individual estimates, despite their central role in the proposed framework.
  3. Weak and incomplete baselines. The baseline methods considered in this work are surprisingly limited (for example, compare to the extensive comparison of Bouchard et al. 2026, which the authors already cited in their paper). The authors omit several recently proposed agent-specific UQ and confidence estimation methods (Oh et al., 2026a; Zhang et al., 2026a; Zhang et al., 2026b; Zhang et al., 2026c). Even basic UQ baselines, such as aggregated action-token negative log-likelihood and mean token entropy (Oh et al., 2026b), are missing. While these white-box baselines do not satisfy the authors' strict black-box constraint, their inclusion would provide important context, especially since the paper already evaluates a surrogate probability-based baseline applied to Qwen backbone. Furthermore, the verbalized confidence baselines use manually designed prompts rather than established prompting strategies from prior work (Tian et al., 2023; Oh et al., 2026b). Since verbalized confidence is highly sensitive to prompting, the absence of prompt sensitivity analysis raises serious concerns about the fairness of the comparisons.
  4. Poor task-success discrimination despite improved calibration. Despite the authors' claim of improvements in calibration, the AUROC results are still very poor. CRG frequently underperforms simple verbalized confidence baselines, particularly on SWE-Bench Verified and Claude Code trajectories (See Tables 2 and 3). Moreover, none of the main or transfer results achieve AUROC above 0.7, with several barely exceeding random discrimination. This suggests the proposed method remains ineffective at distinguishing successful from failed agent executions. Although the authors acknowledge the distinction between calibration and discrimination, they provide insufficient justification for such weak discrimination performance.
  5. (minor) The authors missed some directly relevant recent work on agent uncertainty quantification (Oh et al., 2026a,b; Zhang et al., 2026a,b).

References

  • Bouchard et al. 2026, Beyond Single-Turn Confidence: Trajectory-Adapted Uncertainty Quantification for LLM Agents
  • Oh et al. 2026a, Neglected Free Lunch from Post-training: Progress Advantage for LLM Agents
  • Oh et al. 2026b, Uncertainty Quantification in LLM Agents: Foundations, Emerging Challenges, and Opportunities
  • Zhang et al. 2026a, Confidence Estimation for LLMs in Multi-turn Interactions
  • Zhang et al. 2026b, Agentic Uncertainty Quantification
  • Zhang et al. 2026c, Agentic Confidence Calibration
  • Tian et al. 2023, Just Ask for Calibration: Strategies for Eliciting Calibrated Confidence Scores from Language Models Fine-Tuned with Human Feedback
Questions for authors

See the above sections.

12 comments
AuthorsOpenReview ↗

Response to W1: Questionable computational efficiency

W1: Questionable computational efficiency.

We’ve addressed this feedback by clarifying our computational efficiency analysis (Appendix A) and adding estimated cost-comparisons to multi-rollout sampling methods. We believe our computational efficiency findings are clear:
1) CRGs are cost-effective, and are the best-calibrated method on the calibration-cost Pareto frontier for EnterpriseOps-Gym and SkillsBench (Appendix A). On SWE-Bench, the small difference in performance conceded to one of the added surrogate baselines is not significant (Appendix Q), and the relative cost can be justified by CRG's production of a human-auditable structured argument supporting its estimate, which can inform decision making. 2) Relative to the concern you raise: CRGs are substantially more efficient than any method requiring multi-rollout sampling (consistency based methods), by a factor of 3x to >50x, as shown below and included in our updated Appendix A.

In our introduction, we argue that multi-rollout confidence estimators are cost-prohibitive in general because they require multiple full agentic rollouts, each of which includes many forward passes (we observe 12–78 agent steps on average, per rollout). This motivates our practical evaluation setting: confidence estimation for a single agentic rollout.

While our method uses more than one forward pass, it uses fewer passes and costs less than even a single agent rollout (9-13 total). We find CRGs are 3x to >50x cheaper than the expected cost of multi-rollout sampling methods:

  • Existing multi-rollout sampling methods typically use between 4 and 10 rollouts (Bouchard & Chauhan, 2026; Chen et al., 2026). Using the average cost of a single rollout cτˉ\bar{c_{\tau}} (0.15, 1.06, and 0.95 for EnterpriseOps-Gym, SWE-Bench, and SkillsBench respectively), we estimate the cost of multi-rollout sampling methods as the expected cost of the remaining n−1n-1 rollouts that must be sampled in addition to the one being evaluated: cτˉ∗(n−1)\bar{c_{\tau}}*(n-1).
Enterprise Ops GymSWE-Bench VerifiedSkillsBench
CRG (ours)$0.13$0.18$0.23
cost of one rollout$0.15$1.06$0.95
NCP, ASC, TER (n=4) (Bouchard & Chauhan, 2026)$0.45$3.18$2.85
MATU (n=10) (Chen et al., 2026)$1.35$9.54$8.55
AuthorsOpenReview ↗

Response to W2: Methodological complexity and reliability of LLM-based confidence estimation.

A. Concerning Complexity:

While our method introduces modest complexity compared to simple verbalized confidence, we believe it is well-motivated and empirically justified. Our key motivation is that a high-level, multifaceted claim (such as ‘the agent was successful’) is assessed more reliably when decomposed into concrete, evidence-grounded sub-claims. This builds on insights from assurance cases (Rushby, 2015) and claim decomposition (Hou et al., 2025), and, as we show below under Concerning Reliability, verbalized confidence is better calibrated and more discriminative when elicited for these concrete sub-claims than for the trajectory as a whole. Finally, our core results show better calibration and better decision-making than verbal baselines (Table 2), justifying the modest complexity we introduce with better performance.

B. Concerning Reliability:

This is a good point: to address this, we evaluate the truth of each claim produced by our CRG decomposition and then compute the reliability of our leaf-level estimates for these claims in Appendix M. We consider a claim to be true if its proposition about the task and agent's trajectory holds with respect to the itemized verifier output logs used for evaluating that task. For example, a claim that a coding agent's solution "introduced no regressions" would be labeled true if all pass-to-pass regression tests in the verifier pass, even if the overall verifier indicates the agent failed. We found our leaf-level estimates to be reliable and discriminative:

Claim-Labeling Method:

Following Hilkenmeier et al. (2026), we label the ground-truth of each claim using three independent LLM evaluators (GPT-5.6 Sol, Qwen3.8-27B, and Gemini 3.6 Flash), and have a human adjudicate any claims in which the three verdicts are not unanimous (Heseltine & Clemm von Hohenberg, 2024). When labeling claims, we provide the task, trajectory, claim and verifier logs, allowing the LLM annotator to evaluate a claim with all available signals about the truth of that claim with respect to the final state of the agent’s environment. We observe substantial agreement between panel LLMs (average Cohen’s kappa of 0.74), with 90.4% of judgments being unanimous. For 50 graphs from each estimator LLM in our development set (25 per benchmark), this resulted in the following set of labeled claims:

GraphsTrueFalseTotal
Qwen3.8-27B26526291
GPT-5.6 Sol45968527
Claim-Level Results:

Using the confidence estimates CRGs assigned to leaf-level claims at runtime, we find our estimates are both well-calibrated (Adaptive ECE, Brier) and discriminative (AUROC):

CRG Model# ClaimsECE (↓)Brier (↓)AUROC (↑)
Qwen3.8-27B2910.0350.0510.878
GPT-5.6 Sol5270.0480.0600.894

These results indicate that:

  1. Our leaf-level estimates are reliable: our confidence estimates are well calibrated and can reliably distinguish true and false claims.
  2. Our motivating premise holds: a simple verbalized-confidence estimator is more discriminative and better calibrated on concrete, low-level claims than on a high-level claim such as ‘the agent succeeded’ as evaluated by our baselines in Table 2 of the paper. This is further supported by CRGs' well-calibrated full-trajectory confidence estimates.

We have added this claim-level analysis to the revised paper (Appendix M).

AuthorsOpenReview ↗

Response to W3: Weak and incomplete baselines (Part 1/3: Agent UQ methods)

W3: Weak and incomplete baselines

We include all the suggested baselines which are applicable to our setting in Table 2 of our main results and include any which cannot be applied in Related Work. We address each in detail by type in three comments:

Recent agent-specific UQ and confidence estimation methods:

  1. Oh et al., 2026a is a concurrent work which quantifies uncertainty in an agent’s trajectory using progress advantage: the average difference in log-probability between an action token according to an RL-trained policy and a reference base model. This approach has key shortcomings: (1) it requires any open-weight model used to also have a published base model (not true of Qwen 3.8) and (2) it cannot produce a probabilistic confidence estimate, meaning its calibration error, brier, and BAS cannot be measured. For these reasons, we do not implement it. Further, as a concurrent work it is not in scope as consideration for a baseline according to the ICLR reviewing guidelines. We have included this paper in our related work.
  2. Zhang et al. 2026a study confidence evolution in multi-turn conversations rather than post-hoc confidence estimation for completed agent trajectories. We adapt their P(Sufficient) verbal probe to estimate confidence at the final turn, including it in an updated Table 2. CRGs consistently achieve better calibration, reducing ECE by 25–50% (0.09 vs. 0.12 on SWE-Bench Verified; 0.13 vs. 0.22 on EnterpriseOps-Gym; 0.11 vs. 0.22 on SkillsBench), while matching or improving BAS (0.37 vs. 0.37; 0.08 vs. −0.01; 0.14 vs. 0.01).
  3. Zhang et al. 2026b address a different setting, where agents verbalize confidence at each step and use it to guide subsequent actions through uncertainty-aware memory and reflection (AUQ), rather than estimating confidence post hoc. While potentially beneficial, this approach requires control over the agent's execution and harness. We instead estimate confidence post hoc, supporting any Agent Client Protocol (ACP)-compatible agent, including OpenHands, Codex, and Claude Code. Because AUQ uses confidence estimates to guide subsequent agent actions through memory and reflection, it is not directly applicable to our post-hoc setting. Instead, we compare with a related mean per-turn verbalized confidence baseline following Oh et al. (2026b) in Table 2. Due to its extreme inference cost (78 LLM calls per estimate on average for SWE-Bench Verified), we evaluate this baseline only on Qwen 3.8 27B. We find that CRGs substantially outperform per-turn verbalized confidence on all benchmarks, reducing ECE by 68–73% (0.13 vs. 0.41 on EnterpriseOps-Gym; 0.11 vs. 0.40 on SkillsBench) and Brier scores by 40–41% (0.24 vs. 0.41; 0.24 vs. 0.40), while turning negative BAS scores positive (0.08 vs. −0.32; 0.14 vs. −0.24) and improving AUROC on two benchmarks (0.62 vs. 0.58; 0.65 vs. 0.64).

The results for this baseline are in Table 2 but are still running for SWE-Bench Verified, as this method is highly computationally intensive, making many more LLM calls per task than CRGs. These are the current results on the 625 of 900 trajectories it has completed, with CRGs scored on the same 625 trajectories:

Estimator (Qwen-3.8 27B)ECE ↓Brier ↓AUROC ↑BAS ↑
Mean turn verb.0.160.220.610.31
CRG (ours)0.090.200.580.38

We will update the paper with these results as soon as they finish, but believe the trend will hold: CRGs are likely better calibrated and better decision makers than this approach on all 3 benchmarks.

  1. Zhang et al. 2026c: estimates confidence using features learned from action-token log-probabilities. Since their method is neither black-box compatible nor training-free, it is not directly applicable to our setting. While their pre-trained weights could be applied to our surrogate model, their weights, code, and data are not publicly available, and thus we are unable to reproduce and include it. Prior to submitting, we reached out to the authors but did not receive a response.
Reviewer_K23XOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposes Confidence Reasoning Graphs for estimating task-success probability from a single agent trajectory without training or model-internal signals. An LLM decomposes task success into contextualized claims, attaches supporting, undermining, or unverified trajectory evidence, estimates confidence in individual leaf claims, and multiplies those confidences to obtain a root score.

Critical strengths

The method can inspect a completed black-box trajectory without rerunning a state-changing task, accessing token probabilities, or collecting training labels. The claims with evidence also provide a concrete way to inspect why a confidence estimate is low, which is more actionable than a single unsupported score.

The paper has good experiment design. It reports ECE, Brier score, AUROC, and decision utility, and includes task-level paired bootstrap analysis.

Critical weaknesses

The required conjunction and independence assumptions are approximations.

Questions for authors

na

1 comment

Thank you for the thoughtful review!

We agree our method makes assumptions about independence and the conjunction structure of claims in our decomposition. We find these work well in practice, and evaluate these assumptions in a couple parts of the paper.

  • In Appendix L, we follow prior work on claim decomposition and evaluate the quality of our decompositions using textual entailment, evaluating the refinement invariant and independence assumptions that support our method. We find CRGs often but not always exhibit the expected entailments, remaining effective despite imperfect adherence to these assumptions.
  • In Appendix J, we ablate different methods of propagating leaf-confidence estimates to the root, including two variants which evaluate the Fréchet bounds on the probability of the conjunction, which hold under any dependence between leaf claims and make no independence assumption. On development data with Qwen-3.8 27B, the product is better calibrated than both bounds. The product also outperforms the arithmetic mean, geometric mean, and maximum, which do not treat the leaves as a conjunction.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response to all reviewers

We are grateful for the valuable feedback provided by all reviewers on our paper. The thoughtful suggestions and constructive comments not only helped us improve the overall quality of the work but also strengthened the clarity and validity of our findings and claims. In response, we have incorporated the following changes in the revised version of the paper:

  1. We've greatly expanded our evaluated baselines, now covering 17 total baseline settings across prompting methods, verbal probes, surrogate uncertainty quantifiers, and existing methods for confidence estimation for agents, with updates to the paper in Sections 5 and 6 and our main results in Table 2. We find that CRGs are the best general-purpose estimator in terms of calibration and decision-utility: they maintain a clear advantage over nearly all baselines on EnterpriseOps-Gym and SkillsBench, and every baseline that is competitive on one benchmark falls significantly behind CRGs on another, meaning practitioners would need labeled data in order to select the appropriate baseline method. No baseline has a statistically significant advantage over CRGs on any benchmark. Figures 2 and 3 have been updated to show that CRGs have reliability and decision utility advantages over the strongest baselines. We argue that the performance, generality, and auditability of CRGs give them a clear advantage over existing methods for real-world decision-making about agent produced work. More details in our response to reviewer buUg.
  2. We've added a reliability analysis of CRGs' leaf-claim confidence estimates (Appendix M, Table 12), labeling the truth of 818 leaf claims from development data. We find the leaf estimates are well calibrated and discriminative for both CRG LLMs (ECE 0.035–0.048, AUROC 0.878–0.894), supporting our motivating hypothesis that concrete, low-level claims are assessed more reliably than the high-level claim of task success. More details in our responses to reviewer buUg, W2, and reviewer tm49, W1.
  3. We've conducted a prompt sensitivity analysis evaluating seven confidence elicitation methods in Appendix H using development data, and included the best performing verbalized methods in our main results. More details in our response to reviewer buUg, W3, Part 3.
  4. We update our cost analysis (Appendix A, Figure 4) to reflect new baselines and compare to costs of multi-rollout sampling methods, finding that CRG's are substantially cheaper than multi-rollout sampling methods and remain on the cost-calibration pareto frontier in 2/3 cases, with the advantage of the baseline for the lone exception (SWE-Bench) not being statistically significant (Appendix Q). More details in our response to reviewer buUg, W1.
  5. We extend our paired bootstrap test to every comparison in Table 2 and report 95% confidence intervals (Appendix Q, Table 13). More details in our response to reviewer tm49, W3.
  6. We conduct our post-hoc calibration comparison to the strongest new baselines (Appendix K, Table 10); CRGs remain best calibrated on EnterpriseOps-Gym and SkillsBench. We also note this setting assumes supervised data for tuning the temperature parameter, which our main results setting assumes is unavailable. We more carefully motivate this setting in responses and in the paper. More details in our response to reviewer tm49, Q2.
  7. We also conduct ablations that support the reliability of our method:
    1. In response to reviewer tm49 we compare CRGs to randomly sampled leaf confidences (Appendix S, Table 14), finding CRGs substantially out-perform the ablation, indicating the strength of our method is not simply in decomposing the task to an appropriate number of claims. This complements our finding that individual leaf estimates are reliable (Appendix M). More details in our response to reviewer tm49, W1 (Part 2).
    2. We also look at performance by number of leaves, and learned belief propagation with our labeled claims. We find the relationship between leaf count and performance to be inconsistent, and note possible confounders such as task evaluation difficulty. We also find learned belief propagation to not outperform our simple training-free product based propagation. More details in our responses to reviewer tm49, W1 (Part 2), Q1, and Q2.

We extend our sincere thanks to all reviewers and the chairs for their valuable time and effort in reviewing our paper. Their insightful feedback has been instrumental in enhancing the quality of our work. We remain available for any remaining questions and would be happy to clarify any aspect of our responses.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.