- Rating
- 3(+1)
- Confidence
- 2
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 2
Read review
Paper summary
This paper formulates trajectory-level uncertainty quantification for LLM agents as Bayesian belief tracking over final task success. For each evidence channel, such as pass or fail outcomes from tools and critics and generation-level uncertainty like perplexity and verbalized confidence, the method estimates class-conditional likelihoods on successful and failed trajectories and adds the resulting log-likelihood ratios to the prior log-odds to compute the probability of success. An extension called Structured Bayesian Fusion models trajectory length, evidence from earlier steps, and evidence from the final step separately, and recalibrates the history contributions. The method is applied post hoc to recorded rollouts and requires no additional agent executions. Across 15 coding, retrieval, and interactive environments and five LLMs, the paper evaluates how well the scores identify failed trajectories using [email protected], and reports that the basic fusion achieves the highest average on retrieval and coding while Structured Bayesian Fusion leads on interactive tasks.
Critical strengths
S1. The paper addresses a practical and well-motivated problem. The premise that judging whether an agent's final outcome is correct requires combining generation uncertainty with external feedback such as tool results and tests is sound. The method is applied to recorded trajectories without changing the agent or the harness, and its training and inference costs are negligible. The tool-only variant, which works without token probabilities, is also practical.
S2. The evaluation is broad. The method is compared with baselines that include recent trajectory-level methods such as SAUP, UProp, and HTC across 15 environments, five LLMs, and multiple harnesses. Covering within-domain and cross-domain transfer as well as performance with little training data also reflects attention to practical use.
S3. The analysis of the roles of different evidence is useful. The observation that tool feedback matters more in retrieval and generation uncertainty matters more in coding, together with the analysis showing that adding uninformative critics on CRAG hurts the strongest signal, verbalized confidence, provides insight into when each type of evidence is useful.
Critical weaknesses
W1. The methodological novelty is limited, and the Bayesian belief tracking framing is overstated. The basic fusion is textbook naive Bayes that treats the evidence as independent and sums log-likelihood ratios. Although the update is written step by step, the method is evaluated only on completed trajectories, so its ability to track success over time is never tested. Furthermore, the authors show in Proposition 1 that naively summing correlated evidence overstates it, and the resulting expression itself indicates how to correct for trajectory length, yet this correction is not incorporated into the method.
W2. Evaluations matching the probabilistic framing are missing, and the comparison favors the proposed method. The method outputs success probabilities intended for decision making, but calibration is not evaluated, nor is failure prediction at intermediate points, which the tracking framing would require. In addition, the best variant differs by domain, so the best of several variants is compared against each baseline. The best variant on retrieval relies on verbalized confidence and therefore requires an extra LLM call at every step. Without verbalized confidence, the basic fusion variants fall below HTC and logistic regression, and only Structured Bayesian Fusion, which itself contains learned logistic-regression components, exceeds them slightly. On interactive tasks, all basic fusion variants fall below logistic regression, so it is unclear whether Bayesian fusion itself is the source of the gains.
W3. Performance depends heavily on critics designed for each benchmark, which limits generality to new environments. The core evidence, tool feedback, consists of boolean critics designed by hand for each benchmark, and when the critics are uninformative, as on CRAG, fusion can even hurt, as it does for the strongest signal, verbalized confidence. Much of the result therefore comes from critic design, and the need for such design in every new environment should be discussed alongside the claim that the method requires no changes to the harness. Indeed, performance approaches random when the domain changes. It is also unclear which accumulation rule for critic outcomes, such as summing per step or summarizing once per episode, is used in each experiment, and LLM-as-judge verifiers are not compared as an independent baseline.
Questions for authors
Q1. How well calibrated are the predicted success probabilities, for example in terms of ECE or Brier score? Does correcting the history contribution for trajectory length, as suggested by Proposition 1, improve ranking and calibration?
Q2. Does a single prespecified variant used across all domains still outperform the best baseline? Do the conclusions hold when terminated trajectories are included as failures?
Q3. How costly is it to design critics for a new environment, and how much does performance vary with critic quality? How well does the method predict failure at intermediate points of a trajectory?
5 comments
Response to Reviewer MB2N (2/4)
Q4. Performance depends heavily on critics designed for each benchmark, which limits generality to new environments…How costly is it to design critics for a new environment, and how much does performance vary with critic quality?
Critics are cheap to define: they are boolean checks on information the harness already provides, with no tuning on outcomes, and SBF stays the best learned method even when they carry almost no information (e.g., on CRAG).
The critics are lightweight boolean checks based on information that the harness already provides: whether an action is well-formed, whether a tool call executes successfully, and whether it changes the environment state (Tables 2, 4, and 6 list all of them). They follow directly from the information available in each task, and defining them requires no tuning on outcomes and no changes to the agent or the harness.
The method also remains effective when the critics carry little information. For example, on CRAG, tool feedback is nearly uninformative (Tool-only: −.020), yet SBF still achieves the best result among learned methods (.391 vs. .358 for logistic regression), because it weighs critic and generation evidence according to their estimated informativeness. As we note in lines 321–323, the CRAG critics do not check whether the search retrieved new documents, which explains the drop for Bayes Fused (Verb.). Additionally, Tables 7-9 already show how performance varies with critic quality (Tool-only row): the gain from fusion is largest where the critics are informative on their own (Tool-only reaches .353 on MuSiQue and .445 on BrowseComp-Plus) and smaller where they are not (−.020 on CRAG).
Under domain shift, we use only the critics shared by both domains, so the drop is not caused by missing critics. The same check can still predict success differently across environments, so critic likelihoods may also shift. However, the most visible shift is in the distributions of uncertainty scores, caused by differences in answer length, trajectory length, and response informativeness. A few labeled target examples are enough to re-estimate the likelihoods, after which the method outperforms the baselines even when tool feedback is nearly uninformative.
We will expand this discussion in the camera-ready version of the paper.
Q5. Although the update is written step by step, the method is evaluated only on completed trajectories, so its ability to track success over time is never tested…How well does the method predict failure at intermediate points of a trajectory?
On trajectory prefixes, SBF has the best average [email protected] for predicting both the final outcome and the current task state.
Thank you for this suggestion! We have added this evaluation. Each estimator sees only the trajectory up to step , and we test two setups: (1) whether it predicts the final outcome of the episode, and (2) whether it predicts the state of the task at step .
(1) Predicting the final outcome from the first steps ([email protected]).
| Method | WebArena, 8 steps | BrowseComp-Plus, 10 steps | DeepSWE, mid-trajectory step | Avg |
|---|---|---|---|---|
| SP | .171 ± .000 | .471 ± .000 | −.135 ± .000 | .169 ± .000 |
| Logistic regression | .307 ± .016 | .431 ± .009 | .035 ± .027 | .258 ± .011 |
| Bayes Fused (SP) | .196 ± .022 | .446 ± .001 | .025 ± .091 | .222 ± .031 |
| SBF | .294 ± .014 | .453 ± .006 | .095 ± .061 | .281 ± .021 |
(2) Predicting the state of the task at step ([email protected]).
| Method | BrowseComp-Plus, 10 steps | DeepSWE, mid-trajectory step | Avg |
|---|---|---|---|
| SP | .902 ± .000 | −.040 ± .000 | .431 ± .000 |
| Logistic regression | .934 ± .003 | .095 ± .091 | .515 ± .046 |
| Bayes Fused (SP) | .908 ± .001 | .210 ± .034 | .559 ± .017 |
| SBF | .939 ± .002 | .310 ± .016 | .625 ± .008 |
To obtain state labels on BrowseComp-Plus, we stop the agent after 10 steps and force it to give a final answer. On DeepSWE, we restore the repository after a random sample of the commands that modified the code (up to 8 per episode) and re-run the hidden tests.
SBF has the best average in both setups, with the largest margin for the intermediate state (.625 vs. .559 for the next-best estimator), and the highest PRR on DeepSWE in both. Prediction is harder very early in a trajectory: on WebArena, all methods stay below .15 after 2 to 4 steps.
We will add these experiments to the camera-ready version of the paper.
Response to Reviewer MB2N (3/4)
Q6. In addition, the best variant differs by domain, so the best of several variants is compared against each baseline. Does a single prespecified variant used across all domains still outperform the best baseline?
Yes, SBF is the best-performing method overall, outperforming the strongest baseline on average across all three domains.
It uses a single specification in every domain: no variant is selected per benchmark, and the same evidence model and hyperparameters are used throughout. Aggregated over all 15 benchmarks, SBF outperforms the best baseline overall and in each domain:
| Method | Retrieval | Coding | Interactive | Overall (15 datasets) |
|---|---|---|---|---|
| HTC | .502 ± .009 | .173 ± .025 | .443 ± .011 | .369 ± .010 |
| LR | .498 ± .009 | .277 ± .010 | .496 ± .009 | .424 ± .005 |
| Bayes Fused (SP) | .355 ± .006 | .338 ± .007 | .405 ± .005 | .369 ± .004 |
| Bayes Fused (Verb.) | .555 ± .004 | .231 ± .010 | .382 ± .008 | .378 ± .005 |
| SBF | .515 ± .005 | .306 ± .011 | .526 ± .006 | .450 ± .004 |
Bayes Fused (SP) remains stronger on coding, while Bayes Fused (Verb.) performs best on retrieval tasks. As expected, a single specification involves some trade-offs compared with the best variant in each domain. However, no baseline outperforms SBF in any domain: SBF is either the best- or second-best-performing method, with only other Bayes Fused variants outperforming it. Overall, SBF leads the best baseline by .026. Thus, a prespecified configuration, used unchanged across all domains, still outperforms the best baseline, and the reported gains do not depend on selecting a variant.
Q7. The method outputs success probabilities intended for decision making, but calibration is not evaluated...How well calibrated are the predicted success probabilities, for example in terms of ECE or Brier score?
We have added a calibration evaluation of the held-out predictions, where SBF + Platt scaling achieves the lowest average ECE.
Our conclusions concern outcome ranking rather than calibrated probabilities: the paper states that SBF's probabilities are not guaranteed to be calibrated (lines 263–264) and that PRR measures ranking quality, not calibration (lines 298–300), and the conclusion claims only the strongest average outcome rankings (line 480). Following your suggestion, we added the calibration evaluation below as a complementary analysis.
We report the expected calibration error (ECE, 10 bins) of the held-out predictions, averaged across seeds and configurations. Raw SP scores are min-max normalized to [0, 1]. SBF + Platt applies Platt scaling fitted on out-of-fold SBF predictions within the training folds only. For DeepSWE, ECE is computed against the cohort-median binary labels.
| Method | WebArena | OSWorld | ALFWorld | BrowseComp+ | DeepSWE | Average |
|---|---|---|---|---|---|---|
| SP | .467 ± .000 | .059 ± .000 | .262 ± .000 | .507 ± .000 | .219 ± .000 | .303 ± .000 |
| LR | .054 ± .006 | .058 ± .009 | .094 ± .016 | .065 ± .002 | .075 ± .017 | .069 ± .005 |
| Bayes Fused (SP) | .099 ± .002 | .064 ± .013 | .080 ± .009 | .077 ± .005 | .237 ± .012 | .111 ± .004 |
| SBF | .062 ± .005 | .112 ± .006 | .097 ± .005 | .060 ± .002 | .129 ± .020 | .092 ± .004 |
| SBF + Platt | .042 ± .005 | .072 ± .020 | .064 ± .004 | .022 ± .003 | .079 ± .016 | .056 ± .005 |
SBF is close to logistic regression on 3 of the 5 benchmarks (WebArena, ALFWorld, and BrowseComp+), and both learned estimators are far better calibrated than raw SP. If absolute probabilities are needed, a monotone recalibration fitted on the training folds (e.g., Platt scaling) can be applied while preserving the ranking within each fold, so PRR is essentially unaffected. SBF + Platt achieves the lowest average ECE and outperforms LR on 3 benchmarks, with ranking unchanged within each fold.
We will include these results in the camera-ready version of the paper.
Q8. Evaluations matching the probabilistic framing are missing, and the comparison favors the proposed method.
Our evaluation covers a broad range of tasks, models, and harnesses, without any tuning in our favor. We clearly report all results, including the cases where our method is not the best (e.g., cases where tools do not provide much signal).
All methods, including the baselines, are evaluated on the same trajectories with the same five folds and three split seeds, and no variant or hyperparameter is selected per benchmark. The evaluation covers 15 environments and 80 model-harness configurations, which leaves no room to fit the method to a particular setting. Tables 7-9 report all Bayes Fused variants and SBF for every dataset. For example, on CRAG, tool feedback is nearly uninformative and does not help to improve the performance. Finally, a single prespecified variant used unchanged across all domains, SBF, still outperforms the best baseline overall (see the table in Q6).
Response to Reviewer MB2N (1/4)
Thank you very much for your time in reviewing our paper and your insightful comments.
Q1. The methodological novelty is limited, and the Bayesian belief tracking framing is overstated…
Our contribution is not Bayes' rule but its formulation for LLM agents: Bayesian belief tracking over final task correctness, where tool outcomes and generation-level uncertainty both act as evidence.
The basic fusion rule is simple and standard, and the paper presents it as such (Eq. 1; lines 154–156), while lines 171–174 state the independence assumption. This simplicity is an advantage: the basic fusion improves every raw uncertainty signal in all three task families (Tables 7–9), it is already strong with 30–50 training episodes, where logistic regression is close to random (Figure 3), and it keeps its ranking quality under model and harness shifts, where logistic regression loses 0.191 PRR on average (Figure 4).
Additionally, prior trajectory-level methods (SAUP, UProp, HTC) rely on generation-level signals only, while we convert both generation signals and tool outcomes into log-likelihood ratios and add them on a common log-odds scale. SBF also goes beyond naive Bayes: it models trajectory length, history, and the final step separately, uses a joint final-step model (Eq. 16), and recalibrates the history evidence (Eq. 17).
The belief update is sequential, so the score exists for every trajectory prefix. We additionally evaluate it on prefixes, where SBF has the best average [email protected] (see our answer to Q5).
Q2. The correction from Proposition 1 is not incorporated into the method…Does correcting the history contribution for trajectory length, as suggested by Proposition 1, improve ranking and calibration?
The length correction suggested by Proposition 1 improves both ranking and calibration, and SBF performs on par with it.
SBF rescales the accumulated history evidence by a fitted β (Eq. 17; lines 256–258). For comparison, we also tested the length correction directly: we estimate ρ on the training folds and divide each accumulated history term by 1+(K−1)ρ.
The length correction improves both ranking and calibration, as Proposition 1 suggests. SBF's recalibration reaches the same quality without estimating ρ, so it already provides a similar correction.
We will add this analysis to the camera-ready version.
Q3. The best variant on retrieval relies on verbalized confidence and therefore requires an extra LLM call at every step...On interactive tasks, all basic fusion variants fall below logistic regression, so it is unclear whether Bayesian fusion itself is the source of the gains.
The gains come from combining tool feedback and generation uncertainty as evidence on a common log-odds scale: SBF outperforms both HTC and logistic regression on average in every domain, without verbalized confidence.
First, SBF does not require verbalized confidence, so the gains do not depend on the extra LLM call.
Second, fusion alone already helps: without any logistic-regression components, fitting only per-signal class-conditional likelihoods, Bayes Fused improves every raw signal in all three task families (15 of 15 cases in Tables 7–9; solid blue bars in Figure 2). Its simplicity is especially beneficial out of domain (Figures 4 and 5).
Third, SBF outperforms logistic regression given the same evidence (Appendix B.1: aggregates of every generation signal, tool outcomes, and per-step pass rates), so the gain does not come from additional inputs. SBF uses logistic regression only to project several uncertainty signals onto one scalar for the history and one for the final step. The evidence itself comes from class-conditional Gaussian and Bernoulli models.