- 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
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 be the pool of confidence values assigned to any leaf by CRGs for a given model and benchmark, and let be the pool of final (root) confidences that CRG assigns for a given model and benchmark. We compare:
- CRG (ours): our method without modification: each leaf gets its original assigned confidence.
- Random leaf confidences: given a graph produced by CRGs, replace each leaf confidence with an independent sample from 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.
- Random final confidence: ignore the graph and sample a random final confidence value from the distribution of observed final confidences for that model & benchmark (). 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.
| Model | Method | SWE-Bench Verified | EnterpriseOps-Gym | SkillsBench | |||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| ECE (↓) | Brier (↓) | AUROC (↑) | BAS (↑) | ECE (↓) | Brier (↓) | AUROC (↑) | BAS (↑) | ECE (↓) | Brier (↓) | AUROC (↑) | BAS (↑) | ||
| Qwen3.8-27B | Random final | 0.11 | 0.22 | 0.50 | 0.35 | 0.20 | 0.29 | 0.50 | 0.04 | 0.23 | 0.32 | 0.48 | 0.08 |
| Qwen3.8-27B | Random leaf | 0.10 | 0.22 | 0.51 | 0.35 | 0.24 | 0.31 | 0.50 | 0.03 | 0.24 | 0.32 | 0.54 | 0.09 |
| Qwen3.8-27B | CRG | 0.09 | 0.20 | 0.57 | 0.37 | 0.13 | 0.24 | 0.62 | 0.08 | 0.11 | 0.24 | 0.65 | 0.14 |
| GPT-5.6 Sol | Random final | 0.21 | 0.28 | 0.49 | 0.30 | 0.29 | 0.34 | 0.50 | 0.02 | 0.35 | 0.39 | 0.47 | −0.02 |
| GPT-5.6 Sol | Random leaf | 0.23 | 0.30 | 0.50 | 0.29 | 0.34 | 0.36 | 0.50 | 0.01 | 0.36 | 0.40 | 0.53 | 0.04 |
| GPT-5.6 Sol | CRG | 0.16 | 0.23 | 0.62 | 0.36 | 0.24 | 0.29 | 0.67 | 0.06 | 0.22 | 0.29 | 0.65 | 0.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.
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 Verified | EnterpriseOps-Gym | SkillsBench | |||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Estimator | LLM | ECE↓ | Brier↓ | AUROC↑ | BAS↑ | ECE↓ | Brier↓ | AUROC↑ | BAS↑ | ECE↓ | Brier↓ | AUROC↑ | BAS↑ |
| CRG (ours) | GPT-5.6 Sol | 0.16 | 0.23 | 0.62 | 0.36 | 0.24 | 0.29 | 0.67 | 0.06 | 0.22 | 0.29 | 0.65 | 0.09 |
| CRG (ours) | Qwen-3.8 27B | 0.09 | 0.20 | 0.57 | 0.37 | 0.13 | 0.24 | 0.62 | 0.08 | 0.11 | 0.24 | 0.65 | 0.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):
| Estimator | LLM | ECE↓ | Brier↓ | AUROC↑ | BAS↑ |
|---|---|---|---|---|---|
| Verbal Consistency | GPT-5.6 Sol | 0.26 | 0.29 | 0.73 | −6.90 |
| Verbal Consistency | Qwen-3.8 27B | 0.32 | 0.33 | 0.66 | −9.97 |
| CRG (ours) | Qwen-3.8 27B | 0.08 | 0.22 | 0.70 | 0.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.
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:
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):
These results indicate that:
We have added this claim-level analysis to the revised paper (Appendix M).