Technical Summary: Critic Experience Bank (CEB)

Problem Formulation

Large Language Model (LLM) agents increasingly operate in external environments (web, mobile GUIs, shells) where actions alter the state upon which all subsequent decisions depend. In these settings, a single erroneous step can waste interaction budgets or trigger irreversible side effects long before a final task failure is observed. Consequently, final task success is an insufficient reliability signal for deployment.

The core challenge addressed is step-level confidence estimation: the need to produce a calibrated probability that a proposed action will be productive before it is executed. Existing confidence estimation methods (e.g., token logits, verbalized confidence, consistency checks) are primarily designed for response-level scoring. They evaluate a single proposed step based on the immediate context but fail to account for execution consequences—specifically, whether similar actions in similar situations actually advanced the task after the environment responded. This structural gap leads to unstable calibration as interaction unfolds, as standard signals do not transfer cleanly from static response generation to dynamic agent execution.

Methodology: Critic Experience Bank (CEB)

The authors propose the Critic Experience Bank (CEB), a training-free, self-evolving critic framework designed to operate during the inference stage without ground truth step labels or trainable verifiers.

Core Mechanism

CEB augments a fixed LLM critic with a memory bank of hindsight-labeled execution experiences. The framework operates on the premise that agents often face recurring decisions in related contexts. Instead of judging each recurrence solely from the current query, the critic retrieves precedents from its own past judgments and their observed consequences.

The pipeline consists of two phases:

1. Online Scoring: At each step $t$, the agent proposes an action $a_t$ based on the task $q$, current state $s_t$, and history $h_{<t}$. Before execution, the frozen LLM critic estimates the confidence score $\hat{z}_t$. To do this, the critic is prompted with the current context and contrastive examples retrieved from the Experience Bank. These examples are retrieved using a composite key (task, state, action) and include both productive ($B^+$) and unproductive ($B^-$) past records. The prompt also includes a repetition flag to detect short loops.
2. Hindsight Update: After a trajectory $\tau$ completes, a "hindsight LLM" ($g_\phi$) observes the full sequence of states, actions, and observations. It votes (via majority vote over $V$ samples) on whether each step was productive, generating pseudo-labels $\hat{y}_t$. These records, containing the state summary, action, observation, pseudo-label, and the critic's original pre-execution score, are appended to the bank.

Key Design Features

• Self-Evolving: The critic's weights remain frozen; its behavior evolves solely through the expanding context of retrieved experiences.
• Contrastive Retrieval: The bank is split into productive and unproductive sets. The critic is explicitly shown examples of similar actions that succeeded and similar actions that failed, allowing it to calibrate based on consequences.
• No Training Required: The method requires no fine-tuning of the actor or critic and no access to ground truth step labels during deployment.

Key Contributions

1. Problem Formulation: The paper formally defines step-level confidence estimation for LLM agents as the task of estimating action productivity before execution, distinguishing it from standard response-level confidence.
2. CEB Framework: Introduction of a training-free critic framework that utilizes hindsight-labeled execution experience from prior trajectories to augment a fixed LLM critic.
3. Empirical Superiority: Demonstration that CEB achieves state-of-the-art calibration (Expected Calibration Error - ECE, Brier score) and ranking (AUC) across three diverse agent benchmarks (Mind2Web, AMEX, InterCode-Bash) and three critic backbones (GPT-4.1, GPT-5.4, Qwen3-Next).

Experimental Results

The evaluation covers web navigation, mobile GUI control, and shell interaction tasks.

• Calibration Performance: CEB consistently outperformed all training-free baselines (including Perplexity, Mean Entropy, Verbalized Confidence, P(True), and CoT).
  • On the InterCode-Bash dataset with GPT-4.1, CEB reduced ECE by 54% relative to the strongest baseline.
  • On Mind2Web with GPT-5.4, CEB achieved an ECE of 0.176, significantly lower than the next best baseline (0.396 for P(True)).
  • CEB maintained the best performance across all dataset–critic combinations in terms of ECE, Brier score, and AUC.
• Robustness to Label Definitions: The advantage of CEB persisted even when using permissive "LLM-as-judge" labels that credit alternative valid paths, indicating the method is not an artifact of strict reference matching.
• Component Ablation: Removing the experience bank entirely caused the largest performance degradation, confirming that past execution outcomes are critical for recalibration. The contrastive nature of the bank (seeing both successes and failures) was identified as the most important component.
• Self-Evolving Behavior: As the task stream progressed and the bank filled with hindsight-labeled data, CEB's calibration error decreased significantly compared to a static critic, demonstrating that the system improves over time without weight updates.
• Downstream Utility: In selective execution tasks (deferring low-confidence steps for human review), CEB identified wrong steps more effectively than baselines, leading to higher final task success rates when a fixed budget of reviews was applied.

Significance and Claims

The paper claims that CEB addresses a critical gap in the deployment of LLM agents: the need for reliable, step-level confidence before an action changes the environment. By leveraging the agent's own interaction history as calibration evidence, CEB enables a fixed critic to adapt its scoring behavior dynamically.

The authors emphasize that this approach is particularly valuable in deployment regimes where:

• The actor and critic are fixed API models.
• Ground truth step labels are unavailable.
• Training new verifiers is infeasible.

The results suggest that retrieved execution experience provides a signal that is superior to current response-style confidence methods, offering a practical path toward safer and more reliable autonomous agents in complex, state-changing environments. The paper concludes that the primary advantage of CEB is temporal (accumulating evidence over time) rather than supervisory (relying on better labels), effectively turning the agent's own past mistakes and successes into a prior for future decision-making.