1 Introduction↩︎

LLM agents increasingly solve tasks by acting in external environments rather than by producing a single textual response [1], [2]. This changes what confidence estimation must deliver. In a web, mobile, or shell environment, an intermediate action can change the state on which all later decisions condition. A wrong click moves the browser to an irrelevant page, a wrong tap enters a dead end screen, and an unhelpful shell command alters the working context for every subsequent command. Some actions are costly or impossible to reverse, such as submitting a form, deleting a file, or modifying a database. Final task success is therefore an insufficient reliability signal: it reports whether the trajectory worked, not whether the next proposed action should be executed, deferred to a human, or sent back for replanning. What deployment needs is step-level confidence estimation—a calibrated probability that each proposed action is productive, produced before the environment is changed by executing it.

Existing LLM confidence estimation methods, such as token logits, consistency and verbalized confidence [3]–[5], can be adapted to this setting, but they inherit a response-level framing: the score is elicited for a single proposed step under the provided context, whereas agent deployment asks whether executing that step will productively change the state. [6] show that chain of thought (CoT) prompting improves verbalized confidence for embodied agents, yet the judgment still relies on the context supplied to the current query rather than a persistent record of how similar decisions behaved after execution. Trained process reward models and step-level verifiers [7]–[9] provide stronger supervision but require labeled process data and trainable models, neither of which is available when an agent is deployed with a fixed API model and no step annotations.

The structural gap is that agent confidence targets an execution event rather than only a generated response. A proposed action can look locally plausible under the provided context, yet its usefulness is determined by the state reached after execution: it may advance the task, leave the agent in a loop, or make later progress harder. Step-level confidence must therefore estimate action productivity before that environment transition is observed. This difficulty is visible even in a simple diagnostic. Figure 1 evaluates several off-the-shelf confidence signals on Mind2Web steps grouped by their position in the trajectory. These signals are not consistently calibrated as interaction unfolds, indicating that response-style confidence does not transfer cleanly to step-level agent confidence. In contrast, CEB maintains substantially better estimation, suggesting that retrieved execution experience provides a useful signal beyond the current trajectory context.

CEB starts from a simple premise: across a task stream, agents often face recurring decisions in related contexts. A fixed critic need not judge each recurrence only from the current query. Once a trajectory finishes, its execution feedback can be converted into compact records of what the critic believed before execution and whether the step was productive afterward. We instantiate this idea as the Critic Experience Bank(CEB), a self-evolving critic framework that retrieves such records as precedents when a similar future step is scored. Figure 2 summarizes the resulting online scoring and hindsight update pipeline. After each completed trajectory, a hindsight LLM that sees the full action–observation sequence votes multiple times on whether each step was productive. The majority vote becomes a pseudo-label stored in the bank together with the state, action, observed consequence, and the critic’s original score before execution. At each new step, the critic is shown the most similar past examples, retrieved by a composite key based on the task, state and action.

CEB occupies a deployment regime that existing tools serve poorly. Specifically, CEB addresses the calibration problem during the inference stage, where an agent needs reliable confidence before executing each action but has no ground truth step labels or trainable verifier available. It is step-level: it scores each proposed action before execution. Its evidence is built solely from execution feedback, the LLM critic’s weights are frozen, and the critic’s effective behavior changes over the task stream as it retrieves from an expanding bank of hindsight labeled experience. Across three agent benchmarks spanning web, mobile GUI, and shell modalities, and across three critic backbones, CEB attains the best ECE, Brier score and AUC in all nine dataset–critic combinations.

1.0.0.1 Contributions.

• We formulate step-level confidence estimation for LLM agents: estimating before execution whether a proposed action will be productive for the task under the current task information, state, and interaction history.

• We introduce CEB, a training-free critic framework that augments a fixed LLM critic with hindsight-labeled execution experience from prior trajectories and retrieves related productive and unproductive records as precedents when future steps are scored.

• Across three agent benchmarks and three critic backbones, CEB achieves the best ECE, Brier score, and AUC in all dataset–critic combinations, reduces ECE by up to \(54\%\) relative to the strongest training-free baseline, supports selective execution, and remains strongest under permissive LLM-as-judge step labels.

2 Related Work↩︎

Confidence estimation and calibration. LLM confidence estimation without training commonly uses token uncertainty, verbalized confidence, single token probing, or probability aggregation over multiple samples [3]–[5], [10], [11]. [6] adapt verbalized confidence to embodied agents with CoT prompting. These methods are compatible with closed APIs, so we evaluate the corresponding families as baselines. However, they estimate confidence for the current query without accumulating execution consequences from previous trajectories, whereas agent action reliability depends on how similar decisions behaved after the environment responded. Other calibrators such as MICE, CCPS, and DACA provide complementary signals but require access to hidden states or paired base and fine tuned checkpoints [12]–[14], which are unavailable in the fixed API regime. CEB keeps the critic fixed and instead uses execution feedback from prior trajectories as calibration evidence during inference.

Step-level supervision and agent verification. Process reward models and step-level verifiers train on annotated process data [7]–[9], [15]. Recent work studies verifier construction and statistically controlled decision rules for computer use agents [16]–[18]. These approaches are effective when labeled process data, trainable verifiers, or calibrated validation sets exist. We instead focus on the inference stage, where actor and critic are fixed models, ground truth step labels are unavailable at deployment, and the score must be produced before executing the action. [19] is closest in using LLM judge scores for step-level confidence, but their judge does not build a persistent record of the critic’s own interaction history.

Experience and memory in LLM agents. Reflexion [20], ExpeL [21], and ReasoningBank [22] accumulate agent experience to improve future action selection or reasoning, and further work studies how memory design affects agent behavior [23]. These systems improve the actor. CEB places memory on the critic side: it retrieves past state–action outcomes and the critic’s earlier scores to estimate whether the next proposed action is reliable. This also differs from self refinement and tool augmented critique [24]–[27], which critique each instance independently and target actor correction rather than calibrated step-level confidence.

3 Method↩︎

3.1 Problem Formulation↩︎

A trajectory is \(\tau = (s_1,a_1,o_1), \ldots, (s_T,a_T,o_T)\), where \(s_t\) is the environment state before the action, \(a_t\) is the proposed action, and \(o_t\) is the observation after the action execution. The task is \(q\), and \(h_{<t}=\{(s_i,a_i,o_i)\}_{i<t}\) is the prior interaction history. At step \(t\) we seek a confidence score \(\hat{z}_t \in [0,1]\) for the proposed action \(a_t\), computed before execution. The purpose of this score is to support online intervention: low confidence actions can be deferred to replanning, human review, or selective execution before they are executed. The score can be computed according to the task, current state, and prior history, but not the unobserved \(o_t\): \[\hat{z}_t = f\!\bigl(q,\, s_t,\, h_{<t},\, a_t\bigr), \label{eq:problem}\tag{1}\] The target event is step productivity: \(y_t{=}1\) iff the proposed action is correct or makes progress under the benchmark’s step-level criterion. Thus \(\hat{z}_t\) is intended to estimate \(P(y_t{=}1 \mid q,s_t,h_{<t},a_t)\), so calibration is measured against this held-out label, which is not observable during inference and is used only for evaluation.

3.2 Self-Evolving Critic via an Experience Bank↩︎

We instantiate the estimator \(f\) as a fixed LLM critic augmented with a Critic Experience Bank: \[\hat{z}_t = f_\theta\!\bigl(q,\, s_t,\, h_{<t},\, a_t;\, \mathcal{B}_t\bigr), \label{eq:ceb-estimator}\tag{2}\] where \(\theta\) is fixed and \(\mathcal{B}_t\) contains hindsight labeled records from earlier trajectories. Because the critic weights are fixed, any adaptation must come from the evidence placed in its context. We build this evidence after each trajectory, when the agent has observed the environment’s response \(o_{1:T}\) to every action and can judge consequences that were unavailable before execution. A hindsight LLM \(g_\phi\), conditioned on the full \((s_{1:T}, a_{1:T}, o_{1:T}, q)\), emits binary productivity labels for every step. We sample \(g_\phi\) \(V\) times at temperature \(\tau{>}0\) and apply majority vote because individual hindsight judgments can vary on ambiguous steps: \[\tilde{y}_t = \tfrac{1}{V}\sum_{v=1}^{V}\hat{y}^{(v)}_t, \qquad \hat{y}_t = \mathbf{1}[\tilde{y}_t \ge 1/2]. \label{eq:vote}\tag{3}\] The completed step is appended to the bank as a record containing the task, state summary, action, observation, hindsight pseudo label \(\hat{y}_t\), and the confidence score \(\hat{z}_t\) assigned before execution.

Each bank record has the form \[e = (q',\, s',\, a',\, \tilde{o}',\, \hat{y}',\, \hat{z}',\, \chi'),\] where \(q'\) is the parent task, \(s'\) a compact state summary before action execution, \(a'\) the executed action, and \(\tilde{o}'\) a summary of the observation after action execution. In web navigation, for example, \(s'\) is a truncated DOM snippet around the candidate action. In mobile GUI control it is the visible clickable element list. In shell interaction it is the recent terminal output. The pseudo label \(\hat{y}' \in \{0,1\}\) is produced by hindsight voting (Eq. 3 ), and \(\hat{z}' \in [0,1]\) is the online confidence score assigned before execution. We additionally store an agreement flag \[\chi' = \mathbf{1}\!\bigl[\mathbf{1}[\hat{z}' \ge 1/2] = \hat{y}'\bigr],\] recording whether the critic’s original binary judgment agreed with the hindsight outcome. Retrieved examples expose this flag so the critic can see where it has previously assigned too much or too little confidence.

We keep the bank as a class split union \(\mathcal{B}_t = \mathcal{B}_t^{+} \cup \mathcal{B}_t^{-}\) with \(\mathcal{B}_t^{+} = \{e : \hat{y}' = 1\}\) and \(\mathcal{B}_t^{-} = \{e : \hat{y}' = 0\}\). This split makes retrieval explicitly contrastive: the critic sees not only similar actions that worked, but also similar actions that failed. The critic is self-evolving in the sense that its scoring context changes as \(\mathcal{B}_t\) grows from the agent’s own interaction during inference with no human or ground truth labels in the loop.

3.3 Retrieval and Critic Prompting↩︎

For each new step we form a composite query \(\kappa_t = \texttt{task:}~q \mathbin{\Vert} \texttt{state:}~s_t \mathbin{\Vert} \texttt{action:}~a_t\). Bank items are keyed analogously by \(\kappa' = \texttt{task:}~q' \mathbin{\Vert} \texttt{state:}~s' \mathbin{\Vert} \texttt{action:}~a'\). We include all three fields because action strings are often short and reusable across states. The task and state fields make retrieval conditional on the user’s intent and the environment context, rather than on surface overlap in the action text alone. Retrieval is cosine similarity between \(\kappa_t\) and \(\{\kappa'\}\) under a TF-IDF embedding fit to the bank’s keys. The top-\(k\) items from each nonempty class bucket form \(\mathcal{R}_t^{+}, \mathcal{R}_t^{-}\), so the prompt is contrastive whenever both buckets contain records. The retrieval depth \(k\) controls how many examples are drawn from each class. The deployed value is specified in §4.1. If a class bucket has fewer than \(k\) records, we retrieve all available records from that bucket. If it is empty, that side of the contrast is omitted. Finally, we include a repetition flag \(\rho_t = \mathbf{1}[a_t \text{ matches the prefix of any action in } a_{t-3:t-1}]\), which alerts the critic to short loops that may not be captured by semantic similarity alone.

The critic prompt contains \(q\), \(s_t\), \(h_{<t}\), \(a_t\), the retrieved examples \(\mathcal{R}_t^{\pm}\), and \(\rho_t\). Prior steps and retrieved examples are shown with their execution feedback and past confidence scores. This gives the critic two sources of consequence informed evidence: evidence from the current episode and evidence across trajectories from similar past states. The critic returns a single JSON object with a numeric score field. Let \(r_t\) denote the value of this field. The online confidence is \[\hat{z}_t = \mathrm{clip}\!\bigl(r_t,\; 0,\; 1\bigr). \label{eq:online-score}\tag{4}\] Algorithm 3 summarizes the loop.

4 Experiments↩︎

4.1 Setup↩︎

Datasets. We evaluate on three datasets covering common agent interfaces that can have risky actions or change environment state: Mind2Web [1] (\(1{,}009\) web navigation trajectories), AMEX [28] (\(1{,}000\) mobile-GUI episodes randomly sampled from the benchmark), and InterCode-Bash [2] (\(200\) bash tasks).

Step labels and metrics. The evaluation target is a binary step label defined by the dataset. For Mind2Web and AMEX, labels follow the reference matching logic of offline GUI agent evaluation: a step is positive when the predicted action matches the reference action defined by the dataset. For InterCode-Bash, labels are derived from reward, i.e., the action that increases the reward is defined as the productive action. Reference matching labels can be conservative toward alternative valid paths. We therefore also report an LLM-as-judge evaluation for Mind2Web and AMEX in §4.2, with the corresponding label shift summarized in Appendix 6. Label construction details are in Appendix 7. We report Expected Calibration Error (ECE), Brier score, and AUC. ECE measures calibration across bins, Brier is a proper scoring rule, and AUC measures ranking quality.

Models and configuration. The actions are generated by a ReAct agent framework [29] with one of three backbones: GPT-4.1, GPT-5.4, and Qwen3-Next-80B-A3B-Instruct. For confidence estimation, we use the same backbone as the actor. Unless stated otherwise, CEB uses vote count \(V{=}5\) and retrieval depth \(k{=}2\) per class. Serving and decoding details are in Appendix 7.

Baselines. All baselines require no training and observe the same information \((q, s_t, h_{<t}, a_t)\) before execution. The post-hoc scorers (CoT, P(True), PPL, ME) and CEB score the same frozen actions against the same held-out labels, so differences reflect confidence estimation. CEB additionally processes trajectories in stream order and appends trajectories to its bank after all of its actions are scored, so no future feedback leaks into an online estimate. Verbalization and PRO instead emit their own action jointly with the confidence signal and are scored on the actions they generate. Perplexity (PPL) and Mean Entropy (ME) aggregate the agent’s token uncertainty over the action span (\(s = 1/\mathrm{PPL}\) and \(s = \exp(-H_{\text{mean}})\) respectively). PRO [11] samples \(N{=}5\) completions and derives confidence from the softmax over sequence log probabilities. Verbalization is the “ask the model how sure it is” signal [4], [5]: the agent itself emits action and confidence in a single forward pass, so confidence is a side effect of action generation rather than a separate critic call. P(True) [3] asks the critic whether the proposed action is correct and reads the probability mass assigned to the True token. CoT (Inductive) [6] performs CoT reasoning without examples followed by a verbalized confidence in \([0,100]\), rescaled to \([0,1]\).

4pt

4.2 Main Results↩︎

Table 1 reports the comparison across three critic backbones and three fixed substrates. CEB attains the best ECE, Brier, and AUC in every dataset–critic cell. This consistency is the main result: across web, mobile GUI, and shell tasks, consequence informed experience gives a fixed critic a more reliable estimate of whether the next action is productive before it is executed. Representative gaps range from a \(14\%\) relative ECE reduction over the strongest baseline that requires no training on Mind2Web with GPT-5.4 to a \(54\%\) reduction on InterCode-Bash with GPT-4.1.

The baselines clarify why agent confidence cannot be reduced to ordinary response confidence. Verbalized confidence and CoT confidence ask the model to introspect on the current step, but they remain weak calibration signals because they do not use what happened after similar actions in prior trajectories. Token uncertainty is poorly calibrated on every substrate—its ECE is the highest or near-highest in each cell—and on the web and shell substrates its ranking is even inverted (AUC\({<}0.5\)); it is competitive on ranking only on AMEX, where short tap actions make token probabilities more informative but the scores remain badly scaled. Probability aggregation over same-model samples is likewise brittle when the samples are nearly identical. In contrast, CEB retrieves concrete prior outcomes for similar state and action contexts, which improves calibration and ranking together rather than merely rescaling the scores. Its calibration advantage (ECE, Brier) is the robust one, since it does not depend on the orientation of a raw uncertainty signal that a label-free deployment cannot correct.

Reference matching labels can be conservative toward exploratory or alternative valid steps, so we also evaluate the same confidence scores under an independent LLM-as-judge labeling policy on Mind2Web and AMEX. The judge receives each step’s agent action, the dataset reference action, and the agent’s stated reasoning with trajectory context visible, then assigns a permissive binary productivity label. Table 2 reports the results under these judge labels. CEB remains the best method in every dataset–critic cell, showing that its advantage is not limited to exact reference matching. Appendix 6 and Table 7 link the ground truth matching evaluation in Table 1 to the LLM-as-judge evaluation here by reporting the label shift between the two targets.

4pt

4.3 Component Ablation↩︎

Table 3 ablates each component of CEB on the GPT-5.4 Mind2Web substrate, removing one piece at a time from the deployed configuration. All variants score identical \((\text{action}, y)\) pairs. The vote count and retrieval depth used here are the deployed settings; Appendix 8 reports the corresponding sensitivity sweeps. The ablation shows that the gain comes from giving the critic contrastive, relevant experience rather than from a generic longer prompt. Removing the bank entirely produces the largest degradation, confirming that the fixed critic needs past execution outcomes to recalibrate its step scores. Within the bank, the productive/unproductive contrast is the most important component: seeing similar actions that failed gives the critic evidence for lowering confidence on locally plausible but unproductive steps. Composite key retrieval is the next major factor, showing that the bank is useful when examples are matched by task, state, and action rather than sampled as unrelated demonstrations. Voting over multiple hindsight samples and the repetition signal provide smaller refinements by reducing noisy pseudo-labels and highlighting short loops. Together, these results support the intended mechanism of CEB: it turns the agent’s own past execution feedback into calibration evidence that is relevant to future states. The growing bank is best understood as a prior over the critic’s own systematic errors, indexed by task and state. Retrieval is what turns that prior into an evolving context for a critic whose weights remain fixed.

4.4 Self-Evolving Behavior over the Task Stream↩︎

CEB is self-evolving: its bank is empty at the start of the stream and grows as trajectories complete, so its scoring context strengthens over time even though the critic weights never change. Figure 4 tracks cumulative ECE as the bank fills on Mind2Web with GPT-5.4, against the bank-free Static critic on the identical step stream, averaged over \(5\) random stream orders (mean\(\pm\)std) to reduce noise in early prefixes. Near the start, when the bank is almost empty, CEB and Static are statistically indistinguishable. As experience accumulates the gap grows—\(+0.073\) after \(30\) tasks, \(+0.104\) after \(50\), and \(+0.136\) after \(150\)—while the Static critic stays flat because it has no memory to accumulate. On the full deployed stream the gap reaches \(+0.142\), suggesting that more hindsight-labeled experience continues to strengthen the critic context.

4.5 Downstream Utility: Selective Execution↩︎

Step-level confidence can be used to identify which actions to execute and which to defer. We therefore use a replay-based risk-coverage diagnostic on the Mind2Web: for each method, rank steps by ascending confidence, abstain (assume deferring to replanning or human review) on the lowest-confidence \(b\%\), and report the GT positive rate among the retained steps. The abstention budget fixes coverage and does not tune a threshold on labels. This does not claim a closed-loop replanning policy; it isolates whether the confidence signal concentrates wrong actions in the low-confidence region where an external controller could intervene.

CEB attains the highest retained accuracy at every nontrivial budget. Three failure modes appear. Mean Entropy and Perplexity are actively misaligned: retained accuracy drops as their lowest confidence steps are removed (\(0.198 \to 0.114\) for ME at \(b{=}50\%\)), meaning they place many correct actions below incorrect ones. Verbalization yields an essentially flat curve—its scores do not separate steps for which abstention helps. CoT lifts retained accuracy by only \(+0.036\) at \(b{=}50\%\), versus \(+0.090\) for CEB: verbalized CoT confidence is less aligned with which steps are actually wrong.

4.5.0.1 From step-level confidence to task success.

The proxy above is step-level. We next ask whether better step-level confidence translates into higher final task success. We simulate a bounded human-in-the-loop review: for each task the agent defers its \(m\) lowest-confidence steps to an oracle reviewer that corrects them, and a task counts as successful only if all of its steps are then correct—the official Mind2Web Task Success Rate criterion, which we also apply to AMEX. A method helps only if its confidence ranks a task’s genuinely wrong steps into the small reviewed set, so this measures within-task discrimination under a fixed per-task review budget—the operating point of a human reviewer who inspects the few least-confident steps of each task the agent runs. Table 5 reports task success at \(m\in\{1,2,3\}\) on Mind2Web and AMEX with the GPT-5.4 critic. \(m{=}0\) is the base rate.

CEB improves final task success over most baselines at every budget on both datasets, and stays closest to the per-task oracle. Because a task succeeds only when every one of its wrong steps is reviewed, this metric rewards ranking the wrong steps of a task below its correct ones—exactly the within-task ordering that CEB’s per-step calibration provides, whereas token-uncertainty scores (Mean Entropy, Perplexity), which vary little within a task, gain the least.

4.6 Closing the Gap to a Ground Truth Oracle↩︎

To bound how much of CEB’s residual calibration error is attributable to noise in the pseudo-labels, we replace the hindsight pseudo-labels with held out ground truth step labels in the bank. This oracle is unavailable in deployment and is never used in the main method. It isolates the contribution of the hindsight labeler from retrieval, prompting, and the critic backbone.

3.6pt

Table 6 reports this comparison in ECE. The Static\(-\)Oracle column is the gap between the bank-free Static critic and the ground-truth oracle—the total calibration headroom that a perfectly labeled bank could close—while the CEB\(-\)Oracle column is the residual gap between CEB(which uses only pseudo-labels) and that oracle, i.e.the portion of CEB’s error attributable to pseudo-label noise. This residual is small, so noise in the pseudo-labels is not the dominant source of residual error: the hindsight majority vote over execution feedback already extracts most of the calibration signal that ground truth labels would provide. The Closed column, \((\text{Static}-CEB)/(\text{Static}-\text{Oracle})\), is the fraction of that headroom CEB recovers. The key advantage is temporal rather than supervisory. The online critic must score an action before seeing its consequence, whereas the hindsight labeler constructs bank evidence from completed trajectories.

Appendix 6 provides the full LLM-as-judge label analysis, with Table 7 connecting the strict reference labels used in Table 1 with the permissive judge labels used in Table 2.

5 Conclusion↩︎

We presented CEB, a self-evolving critic framework that recasts step-level confidence estimation for LLM agents as retrieval augmented critic calibration over the agent’s own past state–action outcomes. CEB requires no training, uses no human or ground truth step labels, and bootstraps directly from execution feedback. Across three datasets and three critic backbones it attains the best ECE, Brier, and AUC in every dataset–critic cell, closes up to \(95\%\) of the calibration gap to a ground truth oracle, and supports selective execution and higher final task success under a fixed review budget, whereas token-uncertainty baselines are actively misaligned. Under permissive LLM-as-judge labels on Mind2Web and AMEX, CEB remains the strongest method across all reported metrics and dataset–critic cells. The component ablation identifies the productive/unproductive contrast and retrieval conditioned on state as the primary mechanisms, with vote denoising and the repetition signal as complementary refinements.

5.0.0.1 Limitations.

All experiments use the same model as critic and hindsight labeler, so we do not isolate the effect of an independent labeler. Step labels still depend on reference annotations or LLM-as-judge relabeling. On InterCode-Bash in particular the reward-derived labels may have some noise. We also do not add eviction or compression to the bank, which will matter for deployment streams much larger than those evaluated here. Future work should close the loop with live intervention, study independent hindsight labelers, and scale the bank.

6 LLM-as-Judge Label Analysis↩︎

Reference matching step labels mark any action that does not match the annotated reference as unproductive, which can penalize exploratory or harmless actions and alternative valid paths too strongly. To quantify how much this affects the evaluation target, we relabel Mind2Web and AMEX with an independent LLM judge (GPT-5.4) under a permissive policy. For each task, the judge receives every step’s agent action, the dataset reference action, and the agent’s stated reasoning, batched in a single call so trajectory context is visible, and outputs one binary label per step at temperature \(0\). A step is productive if it serves the same intent as the reference action, constitutes reasonable harmless exploration, or makes incremental progress in the right direction; it is unproductive if it picks a clearly wrong control, takes a destructive or irreversible step the reference did not, or repeats a recent step without progress.

Table 7 links the strict reference matching evaluation in Table 1 with the LLM-as-judge evaluation in Table 2. The judge agrees with the strict labels on \(74\)–\(82\%\) of steps across all three critics, and the disagreements are strongly asymmetric: the judge mainly relabels strict negative steps as productive. This indicates that strict reference matching is conservative rather than random noise.

7 Experimental Details↩︎

7.0.0.1 Step labels.

For Mind2Web [1], a step is positive when the agent’s element prediction matches pos_candidates and the operation type matches the gold action. For AMEX [28], we score TAP actions and mark a step positive when the predicted touch point falls inside the human touch bounding box. For InterCode-Bash [2], the label derives from the reward function: a reward increase larger than \(0.05\) is positive, and final steps with reward at least \(0.7\) are positive when the reward does not decrease. Positive rates are actor-dependent, because each backbone generates different actions: the strict-label positive rate spans \(0.16\)–\(0.20\) on Mind2Web and \(0.59\)–\(0.69\) on AMEX across the three actors (the strict pos.column of Table 7), and is \(0.409\) on InterCode-Bash. Labels are used only post hoc to compute calibration metrics.

7.0.0.2 Critic backbones and serving.

GPT-4.1 and GPT-5.4 are accessed through Azure OpenAI. Qwen3-Next-80B-A3B-Instruct is served locally with vLLM on \(2\times\)NVIDIA H200 GPUs (tensor parallelism \(2\), BF16, gpu-memory-utilization \(=\) \(0.65\)). GPT-5.4 is the primary closed model because it is the strongest model in our pool with log probability access, which PPL and ME require.

7.0.0.3 CEB configuration.

The deployed configuration uses vote count \(V{=}5\), retrieval depth \(k{=}2\) per class, and hindsight sampling temperature \(\tau{=}0.7\). The hindsight labeler \(g_\phi\) is the same model as the critic. The TF-IDF retriever uses 1–2 gram features fit to the running bank. All baselines score the same frozen actions under the same information available before action execution \((q, s_t, h_{<t}, a_t)\).

8 Hyperparameter Sensitivity↩︎

We sweep the hindsight vote count \(V\) and retrieval depth \(k\) on Mind2Web. Calibration is stable across hindsight vote counts: across all three critics, \(\Delta\)ECE between \(V{=}1\) and \(V{=}5\) is below \(0.003\) when \(k{=}1\) (Table 8). We retain \(V{=}5\) in the main setting as a conservative default, since the component ablation under deployed \(k{=}2\) attributes \(+0.028\) ECE to vote denoising. The vote matters more at \(k{=}2\) than at \(k{=}1\) because a larger retrieved set aggregates more pseudo-labels, so noise in the hindsight labels compounds across the retrieved evidence and denoising has more to correct; at \(k{=}1\) the single nearest record dominates the prompt regardless of vote count. Retrieval depth exhibits a cost–calibration tradeoff: \(k{=}5\) gives the best ECE, but \(k{=}2\) reaches the same ECE as \(k{=}3\) with lower prompt cost (Table 9). We therefore deploy \(k{=}2\) as the default when cost matters and treat \(k{=}5\) as the setting that prioritizes calibration. Appendix 9 reports the corresponding token overhead.

2.8pt

9 Token Cost of Retrieval Depth↩︎

Each retrieved bank example contributes roughly \(160\) input tokens (state summary, action, observation after action execution, past score, agreement flag), so the bank section of the prompt scales linearly in \(k\) while the remainder (system prompt, current page state, history) is fixed overhead. Table 10 reports measured token costs for each call on Mind2Web with GPT-5.4 (tokens measured with tiktoken cl100k_base). Moving from \(k{=}1\) to \(k{=}5\) adds \(+70\%\) total input tokens for a \(-7\%\) relative ECE gain. \(k{=}2\) obtains roughly half the calibration improvement at \(+18\%\) tokens, which motivates it as the deployed default.

10 Reliability Diagrams↩︎

Figure 5 shows per-bin reliability diagrams on the full Mind2Web stream for CEB and three representative baselines. CEB tracks the diagonal closely (ECE \(0.176\)), whereas CoT (\(0.459\)) and P(True) (\(0.396\)) are over-confident across most bins and Mean Entropy (\(0.710\)) is severely mis-scaled, concentrating mass at high confidence regardless of correctness. This is the bin-level view behind the aggregate ECE in Table 1.

11 Retrieval Mechanism↩︎

CEB retrieves bank examples with a sparse TF-IDF score over the composite key (task \(\Vert\) state \(\Vert\) action). A natural question is whether a learned dense retriever would do better. Table 11 compares the deployed TF-IDF retriever against (i) a dense retriever that embeds the same composite key with OpenAI text-embedding-3-small and ranks by cosine similarity, and (ii) random retrieval, all on Mind2Web with the GPT-5.4 critic and an otherwise identical frozen substrate (\(k{=}2\), \(V{=}5\)). The dense retriever improves over random but not much, while the sparse TF-IDF key gives the best overall result. We attribute this to the retrieval target being lexical and structural—near-duplicate actions on near-identical page states (e.g.the same CLICK on the same labeled control)—which sparse term overlap captures directly, whereas a general-purpose sentence embedder smooths over the exact tokens that distinguish a productive selection from an unproductive one. TF-IDF also adds no extra model or API dependency, consistent with CEB’s training-free design.

12 Offline Confidence-Gated Regeneration↩︎

The selective-execution analysis in §4.5 tests whether low-confidence steps are good intervention targets by deferring them. Here we use the same selection question but test a stronger frozen-state intervention: the agent regenerates its action on the flagged steps, and we re-measure step correctness on the same state. On a \(200\)-task Mind2Web subset (\(1{,}613\) steps, GPT-5.4, baseline per-step positive rate \(0.183\)), we re-predict each flagged step once with an identical generic critique (“a reviewer flagged this step; reconsider”), so the regeneration procedure is held fixed across methods and the only variable is which steps each confidence signal selects. We compare the five methods that score the frozen action (CEB, CoT, P(True), PPL, ME) at a matched regeneration budget (the lowest-confidence \(b\%\) of steps), against a Random-\(b\%\) lower bound and an Oracle that regenerates the truly-wrong steps first.

Table 12 and Figure 6 report the per-step positive rate after replacing the selected steps with regenerated actions. CEB is the best method at every budget and tracks the Oracle almost exactly at \(b{=}10\%\) (\(0.201\) vs.\(0.202\)) and \(b{=}25\%\) (\(0.234\) vs.\(0.236\)): the steps it flags as low-confidence are very nearly the steps that are actually wrong. PPL and ME fall below Random—they regenerate correct steps and break them—mirroring their sub-\(0.5\) AUC in Table 1.

13 CEB Prompts↩︎

CEB uses two LLM prompts, both reproduced verbatim below. Figure 7 is the bank-construction (hindsight labeling) prompt: after a trajectory completes, an LLM that can see the entire executed trajectory votes (\(V{=}5\)) on whether each step was productive, producing the pseudo-labels \(\hat{y}\) that populate the bank. Figure 8 is the critic (verifier) prompt used at inference time to score a proposed, not-yet-executed action, conditioned on the within-trajectory history and the retrieved contrastive bank examples. Both prompts are fixed throughout deployment; only the retrieved bank content in the critic prompt changes as experience accumulates.

References↩︎

---