- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 2
- Soundness
- 1
Read review
Paper summary
For stateful tool-using agents, the paper's information-theoretic framework models call-only, action-observation, outcome-only, and state-aware evaluation records as deterministic projections of the full stateful trace, and defines each record's coverage as the conditional mutual information between the record and the trajectory verdict given common non-execution context, normalized by the conditional verdict entropy. It also proves conditional data-processing, chain-rule, sufficiency, and Bayes-risk results about coverage, kept separate from trajectory-level policy performance. The framework is implemented in TraceState, the authors' audit representation with persistent state, append-only interaction recording, backend metadata, and trajectory-level oracle evidence. The authors evaluate the framework through four execution studies on stateful and stateless execution, cross-tool dependency, interaction perturbations, and mock/sandbox/live MCP backends, with four open-weight LLM backbones and four prompting strategies, plus an offline same-trace audit re-scoring 4,640 recorded traces under each record type. The experiments don't estimate the coverage itself.
Critical strengths
- Separating how informative an evaluation record is from how well an agent performs is a helpful framing. Conditioning on shared context so task identity is not credited to each record is spelled out carefully. As far as I can tell, the propositions are all correct. A benchmark builder could reuse this part of the paper as a vocabulary for reporting evaluation results.
- Each trace record stores the agent-visible observation separately from the raw observation and fault metadata, plus paired before/after state snapshots, so recorded runs can be re-scored offline without rerunning the policy. Fixing each trace while varying the view is the right experiment for the question being asked, although the decoders used are weak.
Critical weaknesses
- The same-trace audit doesn't measure the trace-projection coverage of Definition 1. Its ordering of views is due to how the verdict rules are nested. In Table 7, each projected verdict is a deterministic verdict rule: call-only accepts any call that parses, so its false acceptance of 56.9% equals the oracle failure rate; state-aware is a conjunction containing the outcome-only rule, so it cannot accept more failures than outcome-only; full audit is simply the trajectory-level oracle, so its zero false acceptance and full recall hold by construction.
- As far as I can tell, the only information-level statistic reported, the exact collision rate in Table 14, is zero for all views, including call-only, so these traces show no view losing any verdict information. Given a learned decoder for the call-only projection, both audit metrics would change whereas the projection's coverage stays fixed. Appendix B.7 states that these metrics don't estimate I(Y; Xi | K).
- ATT makes no prediction the experiments test, and the central claim made by the paper, that retaining state and transition evidence carries more verdict information than reduced views, rests on rule design, not on measured information. Repeating the same audit would not resolve this, so the central claim doesn't hold as presented; this is the main reason for my rating.
- The execution-side evidence that reduced views hide failures does not hold, either. Stale-state Recovery is exactly 0% for each model and strategy, although State Accuracy remains high, a pattern that fits an unattainable recovery predicate under stale-state feedback just as well as it fits "no recovery"; the paper's main example of terminal-state accuracy hiding invalid execution therefore cannot be told apart from a defect in the metric.
- The other execution comparisons are confounded: strategies are given unequal maximum decision-step budgets, oracle-triggered termination is applied even though Appendix B.4 requires such episodes to be reported as a separate condition, and stateless execution, which gives each call a fresh copy of the initial state, has higher Final-State Accuracy for three of the four models. So these studies do not give independent support for the claim that the audit cannot establish.
Questions for authors
- Can stale-state Recovery be attained with the stale replay mechanism? If an oracle agent taking the corrective action also gets 0% Recovery, is the metric at fault rather than the models?
- Could the audit be rerun with a decoder predicting Y from each projection, reporting held-out accuracy or conditional entropy per view? What about a classifier trained on held-out contexts, or a trace judge?
- Does any result in Section 3 go beyond data processing, the chain rule and Blackwell-type sufficiency applied to evaluation records?
- In Table 14, outcome-only reaches 80.0% recall with about one eighth of the state-aware record size. By the paper's own parsimony criterion, when should a benchmark builder prefer the state-aware view? As far as I can tell, terminal-state checking is already what ToolSandbox milestones do, and what tau-bench does with database checks.
- Do the dependency-depth declines remain strategy-dependent under equal step budgets? And the mock-to-live drops? What about with policy-issued termination only?
- How do the state-aware and full-audit views compare against existing trajectory scorers on the same traces? What about ToolSandbox milestone similarity, the progress rate of AgentBoard or an LLM trace judge? Related work on log sufficiency for agent evaluation (Kirgis et al.) and on proxy-state evaluation from full traces (Chuang et al., "Proxy State-Based Evaluation") is not discussed. How does ATT's claim differ from these two?
10 comments
This is part 2 of our reply (Responses to W4 & Q1, Q3, Q4).
W4 & Q1 Yes. On every original stale-state task, a scripted policy can satisfy the original Recovery predicate when it has a decision available for the corrective query. The predicate requires a post-fault retry, a correct terminal state, and a correct final observation. In wifi_off, the agent turns Wi-Fi off, receives the cached observation true, and obtains the fresh value false on retry. Omitting only that retry leaves Wi-Fi in the same correct state but fails the recovery check.
| Scripted condition on the original stale-state tasks | Recovered / fault-triggered |
|---|---|
| Continue after state satisfaction, original strategy budgets, issue corrective query | 60/80 |
| Same conditions, omit corrective query | 0/80 |
| Continue after state satisfaction, sufficient diagnostic budget, issue corrective query | 20/20 |
| Same diagnostic budget, omit corrective query | 0/20 |
We then tested whether model policies could recover under the same predicate. The stale conditions below use the same per-task decision cap. Recovery is conditional on replay actually occurring. Joint correctness uses all runs and permits a comparison even when early stopping changes which runs reach replay.
| Model condition | All runs | Terminal state correct | State and observation both correct | Replay triggered | Recovered / triggered |
|---|---|---|---|---|---|
| Oracle early stopping enabled | 160 | 105/160 | 15/160 | 13 | 0/13 |
| Oracle early stopping disabled | 160 | 106/160 | 50/160 | 72 | 37/72 |
The models recovered after stale replay when continuation was allowed. The increase in joint correctness, alongside nearly unchanged terminal correctness, identifies what the state-only check misses in these runs. The additional criterion asks whether the agent obtained a correct observation after changing the state.
Q3 In the revised paper, Section 3 identifies which evidence a benchmark must retain to support a specified trajectory verdict. With the verdict, shared context, and execution distribution fixed, the chain rule quantifies what each added field contributes given the existing log. In the approval task, the contribution of write order depends on the requirement being scored. It resolves the approval-before-publication verdict, while final contents alone resolve the terminal-content verdict. Equation 20 translates that distinction into a choice of fields at a specified uncertainty tolerance and storage cost.
Q4 A builder should prefer State-aware over Outcome-only when Outcome-only leaves more verdict uncertainty than the application permits, State-aware meets the tolerance, and its extra cost is justified relative to other feasible records. Table 15 of the revised paper gives the observed cost and recall tradeoff for the original rules.
| Original audit view | Macro trajectory-failure recall | Size relative to Full |
|---|---|---|
| Outcome-only | 80.0% | 0.114 |
| State-aware | 87.6% | 0.886 |
We evaluated the Equation 20 decision directly on the controlled distribution. For each candidate, we grouped executions by task context and retained evidence, computed the remaining conditional verdict entropy, and compared the costs of the feasible candidates.
| Candidate on the pooled controlled distribution | Conditional verdict entropy | Coverage | Mean bytes |
|---|---|---|---|
| Outcome-only | 1/3 bit | 66.7% | 269.50 |
| AO | 0 bits | 100% | 410.83 |
| State-aware | 0 bits | 100% | 1,499.17 |
| Full | 0 bits | 100% | 2,657.50 |
| Selected record, payload content and ordered file IDs | 0 bits | 100% | 59.50 |
For these tasks, the decision is to log final payload content and ordered file IDs. They capture exactly the distinctions needed across the tasks at the lowest cost among the candidates considered. AO also suffices. The example gives a benchmark builder a reason to collect process evidence and a criterion for deciding how much of it to retain.
This is part 3 of our reply (Responses to W5 & Q5, W6).
W5 & Q5 Under a common decision budget and policy-controlled termination, every model–strategy combination scored lower on L3 than on L1. Terminal checks also accepted executions that violated predefined dependencies. With the common budget, the strategies achieved similar L3 correctness, and mock and local MCP achieved similar terminal accuracy under both stopping settings.
Under policy-controlled termination, reaching the goal leaves the agent free to verify or repair its work. A finish request ends the run even if the goal is unmet, so the agent receives no oracle signal to continue. The same offline oracle scores the trajectory after the policy finishes or exhausts its budget.
| Protocol | L1 correct | L2 correct | L3 correct | L1 minus L3 (pp) | Mock terminal correct | Local MCP terminal correct | Mock minus local MCP (pp) |
|---|---|---|---|---|---|---|---|
| Original protocol rerun | 62/64 | 63/88 | 30/88 | +62.8 | 174/240 | 154/240 | +8.3 |
| Common 16-step cap, original stopping settings | 64/64 | 66/88 | 48/88 | +45.5 | 186/240 | 185/240 | +0.4 |
| Common 16-step cap, policy-controlled termination | 64/64 | 64/88 | 47/88 | +46.6 | 183/240 | 185/240 | −0.8 |
Our MCP runs used a local server. In a deployment evaluation, the agent connects to the MCP server under test over the network used in practice. If a service times out or becomes temporarily unavailable, a retry can consume a decision step that the mock run could use to complete the task. Under a fixed budget, such conditions could widen a terminal-accuracy gap in favor of mock. They also make the execution record valuable even when both runs succeed: call outcomes and retries show whether the agent recovered from an interruption, a distinction the final state alone can miss. The rates above describe the local MCP setting.
The difficulty gap persisted across strategies. The levels contain different tasks, so the gap describes performance across difficulty groups. Within L3, the strategies achieved similar correctness once they had the same budget. In the dependency runner, goal-triggered stopping was already disabled, and only Self-refine’s finish-rejection setting changed between the two common-budget conditions.
| L3 correct runs by protocol | Direct | CoT | ReAct | Self-refine |
|---|---|---|---|---|
| Original protocol rerun | 2/22 | 7/22 | 9/22 | 12/22 |
| Common cap, original stopping settings | 12/22 | 11/22 | 11/22 | 14/22 |
| Common cap, policy-controlled termination | 12/22 | 12/22 | 12/22 | 11/22 |
The same executions directly test whether terminal success captures process compliance. We scored the terminal goal and the predefined dependencies on each controlled L3 run, independently of the stale-state recovery metric.
| L3 outcome under the common cap and policy-controlled termination | Count |
|---|---|
| Terminal goal passed | 78/88 runs |
| Terminal goal and dependency checks both passed | 47/88 runs |
| Terminal goal passed, dependency check failed | 31/88 runs |
| Distinct tasks with such violations | 5 |
In a Qwen Direct contact-removal run, the first tool call deleted the contact and the last searched for it. The terminal check correctly confirmed deletion. The call sequence showed that the agent had violated the requirement to search before removal. The two checks answer different questions about the very same run: whether the contact was gone and whether the agent followed the required order.
W6 The stateful/stateless experiment measures policy performance under two execution protocols. Its final-state accuracy records how often the policy reached the configured goal in each mode. ATT’s coverage comparison asks a separate question on a fixed execution distribution: which fields retain the evidence needed to score a given verdict?
| Backbone | Stateful minus stateless final-state accuracy, percentage points |
|---|---|
| DeepSeek | −8 |
| GPT-OSS | −3 |
| Gemma | +1 |
| Qwen | −10 |
In the revised paper, Appendix B.7 specifies the baseline used for these results. The runner uses mode-specific goals and tool configurations, and the stateless path retains shared storage across calls. This identifies the protocols whose final-state accuracies are compared above. The L3 analysis evaluates terminal success and process compliance on the very same runs.
This is part 1 of our reply (Responses to W1, W2 & Q2, W3). Thank you very much for your valuable comments.
We have revised the manuscript in response to the reviewer's insightful comments and uploaded the updated version.
W1 Adding a conjunctive check can only narrow the set of accepted runs. The empirical question is which runs change verdict. On the same trajectories, we counted failures caught by the additional State-aware checks and successful executions they rejected. The table reports both contributions to overall disagreement.
All rates use the full set of trajectories as their denominator. Rule nesting determines the direction of the change in false acceptance. The paired audit supplies its magnitude and the corresponding change in false rejection. Full Audit defines the target here. The next table reports independent judges’ predictions from the Full record.
W2 & Q2 Changing the decoder changes the ordering of views on the same trajectories. We held out task groups during judge development, fixed the task context and prompt across views, and withheld the oracle verdict from both judges. Each row below reports disagreement with the same trajectory-level target. The final two rows compare judges on identical examples.
Qwen achieved its lowest disagreement with AO, and Gemma achieved its lowest disagreement with Outcome-only on the shared review subset. These rankings describe how each judge used the available fields. ATT’s guarantee for nested records concerns the best attainable error. A decoder given the richer record can always reproduce the reduced-view decision by ignoring the added fields.
Table 15 counts pairs with the same context and projected record but opposing verdicts. A record observed only once provides no pair to test. The controlled approval task supplies that comparison directly by giving both write orders positive probability within the same context.
W3 ATT makes a testable prediction once the verdict, record, and distribution are specified. For H(Y∣K)>0, Equation 19 gives the coverage gain from restoring a field Z as I(Y;Z∣K,Ξ)/H(Y∣K). Thus the gain is proportional to the conditional mutual information of the restored field, with the task distribution and verdict held fixed. The same-trace audit’s disagreement and recall measure the decisions of particular evaluators. We use mutual information to give ATT a statistical characterization in information-theoretic terms, without attempting to estimate it from the observed agent trajectories.
We tested the prediction where that distribution is known. From the same initial state, the executor completes both writes successfully in either order. The task requires approval before publication. Its two equally probable branches therefore have identical step-success flags and byte-identical terminal records, but opposite verdicts. Any terminal decoder sees the same input in both branches. Restoring the ordered target IDs separates them. Enumerating the branches gives the following quantities exactly.
A designer scoring approval before publication must retain evidence of order. A designer scoring only final contents can omit order. The controlled experiment gives exact information values for those choices, and the historical audit measures the effect of changing evaluators on recorded agent runs. Section 3.5 states the design principle, and Section 4 reports both tests.
Comparison with existing evaluations