acceptodds
Under review as a conference paper at ICLR 2027

Agent Trace Theory: Information Coverage for Evaluating Stateful Tool-Using LLM Agents

Abstract

Tool-using large language model (LLM) agents complete tasks through extended interactions that modify persistent environments and shape later decisions. Evaluations often reduce these executions to call validity, step-level correctness, or terminal success, obscuring evidence carried across the trajectory. We propose Agent Trace Theory (ATT), an information-theoretic framework that distinguishes agent performance from evaluation coverage by relating full stateful traces to their observable projections. ATT characterizes the verdict-relevant information retained by a trace representation and identifies evidence omitted by call-only, step-local, and outcome-only views. It also formalizes how observations, state changes, backend conditions, ordering, and recovery jointly contribute to an auditable execution record. We operationalize ATT with a TraceState-centered framework that records persistent state, tool-induced transitions, backend conditions, and trajectory-level oracle evidence. Across multiple LLM backbones and prompting strategies, execution studies of state persistence, cross-tool dependency, interaction noise, and backend migration reveal dependency violations, stale-state errors, failed recovery, and backend-specific fragility. A same-trace projection audit shows that retaining state and transition evidence makes these failures more observable than reduced trajectory views, thereby separating diagnostic coverage from agent performance.

Primary area:
interpretability and explainable AI
Keywords:
Agent Trace Theory

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_eNTYOpenReview ↗
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
  1. 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?
  2. 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?
  3. Does any result in Section 3 go beyond data processing, the chain rule and Blackwell-type sufficiency applied to evaluation records?
  4. 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.
  5. 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?
  6. 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
AuthorsOpenReview ↗

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.

Evaluator on the original audit tracesFalse acceptanceFalse rejectionOverall disagreement
Outcome-only17.9%0.0%17.9%
State-aware14.4%6.4%20.8%

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.

Evaluator and sampleTrajectoriesCall-only disagreementAO disagreementOutcome-only disagreementState-aware disagreementFull disagreement
Original rules on primary test set50053.6%46.8%14.8%15.2%0.0% by construction
Qwen judge on primary test set50048.6%39.0%43.2%41.6%42.2%
Qwen judge on review subset10046.0%35.0%38.0%40.0%45.0%
Gemma judge on the same review subset10034.0%33.0%27.0%33.0%31.0%

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)>0H(Y\mid K)>0, Equation 19 gives the coverage gain from restoring a field ZZ as I(Y;Z∣K,Ξ)/H(Y∣K)I(Y;Z\mid K,\Xi)/H(Y\mid 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.

Evidence available on the order-constrained taskConditional verdict entropyBest attainable error
Complete terminal state1 bit50%
Ordered target file IDs0 bits0%

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

  • AgentBoard, Ma et al. measures progress toward subgoals. ATT asks whether the retained observations preserve the evidence needed to reconstruct a trajectory verdict.
  • ToolSandbox, Lu et al. defines and scores milestones over a trajectory. ATT takes such a target as given and evaluates what happens when the record retains or drops a field needed to decide it.
AuthorsOpenReview ↗

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 tasksRecovered / fault-triggered
Continue after state satisfaction, original strategy budgets, issue corrective query60/80
Same conditions, omit corrective query0/80
Continue after state satisfaction, sufficient diagnostic budget, issue corrective query20/20
Same diagnostic budget, omit corrective query0/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 conditionAll runsTerminal state correctState and observation both correctReplay triggeredRecovered / triggered
Oracle early stopping enabled160105/16015/160130/13
Oracle early stopping disabled160106/16050/1607237/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 viewMacro trajectory-failure recallSize relative to Full
Outcome-only80.0%0.114
State-aware87.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 distributionConditional verdict entropyCoverageMean bytes
Outcome-only1/3 bit66.7%269.50
AO0 bits100%410.83
State-aware0 bits100%1,499.17
Full0 bits100%2,657.50
Selected record, payload content and ordered file IDs0 bits100%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.

AuthorsOpenReview ↗

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.

ProtocolL1 correctL2 correctL3 correctL1 minus L3 (pp)Mock terminal correctLocal MCP terminal correctMock minus local MCP (pp)
Original protocol rerun62/6463/8830/88+62.8174/240154/240+8.3
Common 16-step cap, original stopping settings64/6466/8848/88+45.5186/240185/240+0.4
Common 16-step cap, policy-controlled termination64/6464/8847/88+46.6183/240185/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 protocolDirectCoTReActSelf-refine
Original protocol rerun2/227/229/2212/22
Common cap, original stopping settings12/2211/2211/2214/22
Common cap, policy-controlled termination12/2212/2212/2211/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 terminationCount
Terminal goal passed78/88 runs
Terminal goal and dependency checks both passed47/88 runs
Terminal goal passed, dependency check failed31/88 runs
Distinct tasks with such violations5

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?

BackboneStateful 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.

Reviewer_KPJkOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes Agent Trace Theory, which is the framework to quantify information retained by its evaluation record. It defines the evaluation coverage as normalized conditional mutual information between a trace representation and a trajectory-level verdict. They derive properties concerning projection loss, sequential information, sufficiency, and verdict ambiguity and also implement a TraceState execution framework that records actions, observations, state transitions, and backend conditions. Experiments conducts on four models.

Critical strengths
  1. It focuses on a very important question that a successful-looking tool call or correct terminal state may conceal dependency violations or unsuccessful recovery. ATT provides a new perspective to evaluate the execution.

  2. The paper conditions information quantities on shared context, distinguishes structured verdict components, and restricts projection comparisons to the same target and distribution. The general flow of this table is easy to read.

  3. The experiments cover several relevant failure settings rather than relying exclusively on final task success.

Critical weaknesses
  1. The theoretical contribution is largely a reformulation of established ones. The paper needs a clearer account of what new technical insight ATT adds beyond applying familiar information-theoretic concepts to execution logs.

  2. The implementation explicitly does not estimate the proposed mutual information or coverage quantities and the cost-aware parsimony objective is also not solved or evaluated. Would be good to outline the component in the implementation / algorithm.

  3. The main text describes matched execution constraints, but Table 18 gives mismatched decision budgets.

Questions for authors

N/A

5 comments
AuthorsOpenReview ↗

This is part 1 of our reply (Responses to W1 and W2). 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 Technical contribution beyond established information identities

ATT contributes a new perspective on agent evaluation and a method for evaluating the record itself. Alongside asking whether an agent completed a task correctly, we ask whether the benchmark retained enough evidence to decide that question. Our method fixes the trajectory verdict YY, shared context KK, and execution distribution, then compares alternative records Ξ\Xi by how much verdict uncertainty each leaves. This lets a benchmark designer identify which distinctions disappear when a field is removed and choose the lowest-cost record that meets a specified uncertainty tolerance.

Why stepwise success can miss trajectory correctness. Consider two executions that write the same approval and publication files. Every write succeeds and the final files are identical. Only one execution obtains approval before publication. Counting successful calls or inspecting the final files gives the same answer in both cases. If the task instead specifies only the final payload, both orders are valid. The value of logging write order therefore depends on the verdict the benchmark intends to score.

From sufficiency to a logging decision. Coverage quantifies the fraction of verdict uncertainty resolved by the record given the task context. The sequential decomposition measures what a step adds given the preceding history. In our revised paper, Proposition 6 asks the corresponding question about a field: given what the benchmark already logs, how much additional verdict information does this field supply? Equation 20 turns the answer into a design decision by selecting the lowest-cost candidate record that meets a specified uncertainty tolerance.

We applied this criterion on the enumerated task distribution. For each candidate, we grouped executions with the same context and record, computed verdict uncertainty within those groups, and compared storage costs among candidates meeting the constraint.

Candidate record across the pooled tasksRemaining verdict entropyCoverageMean serialized bytes
Final payload content alone1/3 bit66.7%28.5
Ordered target file IDs alone2/3 bit33.3%32.0
Final payload content and ordered target file IDs0 bits100%59.5
Full Audit0 bits100%2,657.5

The selected fields have distinct jobs. Payload content establishes what was written, and ordered target IDs establish whether approval preceded publication. Dropping either field leaves ambiguity on part of the pooled distribution. Keeping both yields the least expensive candidate that preserves the full verdict. In the revised paper, Section 3.5 explains this connection, and Section 4 works through the logging decision.

Relation to existing evaluations

  • τ-bench compares the final database with an annotated goal state. For a verdict defined by that state, the database suffices. ATT identifies what else must be logged when a task adds a process requirement such as prior approval. τ-bench, Yao et al.
  • ToolSandbox scores intermediate and final milestones and supports temporal dependencies between them. Given such a milestone, ATT asks which fields must remain available after execution for an evaluator to verify that dependency. ToolSandbox, Lu et al.

W2 The original same-trace audit reports evaluator disagreement, failure recall, and record size. In the controlled experiment, we implemented Equation 20 on a distribution with known branch probabilities and verdicts. For each logging scheme, the algorithm groups executions by context and projected record, calculates the verdict distribution within each group, and uses those distributions to compute conditional entropy, coverage, and minimum binary decision error. It then selects the feasible scheme with the smallest weighted average serialized size.

Controlled experiment designValue
Task contexts3
Enumerated execution branches8
Candidate schemes133
Allowed additional conditional entropy relative to Full0 bits
Candidate on the pooled distributionConditional entropyCoverageMean bytesSatisfies constraint
Final payload content alone1/3 bit66.7%28.5No
Ordered file IDs alone2/3 bit33.3%32.0No
Final payload content and ordered file IDs0 bits100%59.5Yes, lowest cost among candidates
Full Audit0 bits100%2,657.5Yes

Payload content resolves the terminal-content verdict, and ordered file IDs resolve the approval-order verdict. Together they meet the uncertainty constraint at the lowest cost among the enumerated candidates. The coverage values in this table are exact for that distribution.

AuthorsOpenReview ↗

This is part 2 of our reply (Responses to W3).

W3 The matched elements in the original dependency study were the tool schemas and offline scoring oracle within each task. The decision cap was strategy-specific, as listed in Table 19 of our revision. Self-refine also received feedback when it attempted to finish before satisfying the goal.

We reran the dependency and backend studies with a common decision cap and a condition that disables both oracle-triggered stopping and oracle-driven rejection of a finish request. The offline scoring oracle stays fixed.

StrategyOriginal dependency capControlled capL3 correct under original protocol rerunL3 correct under equal cap and policy-controlled termination
Direct2162/2212/22
CoT4167/2212/22
ReAct8169/2212/22
Self-refine101612/2211/22
Dependency correctness under equal cap and policy-controlled terminationL1L2L3
Correct runs / total64/6464/8847/88
Correctness100.0%72.7%53.4%

Under the common cap and policy-controlled termination, every model–strategy combination scored lower on L3 than on L1. Direct and Self-refine achieved similar correctness within L3.

Changes in the revised manuscript. Section 4 applies Equation 20 to the approval-before-publication task and reports how dependency correctness changes under a common decision cap. Appendix E.2 gives the field ablations and costs in Table 21. Appendix E.4 reports the controlled dependency and backend runs in Tables 24–25.

We sincerely appreciate the reviewer for your great efforts and valuable comments for our paper.

AuthorsOpenReview ↗

Gentle Follow-up on Our Rebuttal

We sincerely appreciate your insightful comments. We have carefully addressed your concerns and submitted our rebuttal. We would be grateful if you could take a moment to review our responses and share any further comments. Thank you so much again for your valuable time and consideration.

Reviewer_gXLmOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

ATT separates agent performance from the verdict information retained by an evaluation record. It formalizes trace coverage and sufficiency, implements a stateful audit framework, and compares five evaluation views of the same 4,640 trajectories alongside execution studies.

Critical strengths

Separating evaluation coverage from agent success is useful, and the formal framework carefully distinguishes population information, observable diagnostics, and policy performance.

Critical weaknesses
  1. The main concern is the interpretation of the projection audit. Table 7 changes both retained fields and verdict rules: Action–Observation rejects any visible error, including an otherwise successful recovery. Full audit is also the reference oracle, making its perfect agreement automatic. Despite explicitly disclaiming information estimation, the conclusion attributes reduced-view errors to omitted evidence. The results establish differences between these evaluators but do not separate information loss from rule choice.
  2. The theory largely applies standard information identities. Its additional practical value needs a clearer demonstration, such as a worked logging decision informed by ATT; serialized byte ratios do not validate Equation 20's uncertainty constraint.
  3. Algorithm 1 conditions the policy on the full trace prefix, although backend fields are described as audit-only. Specify the actual visible-history projection; this notation issue does not establish leakage.
Questions for authors

Using the existing traces, how much disagreement can be attributed to the rules in Table 7 versus unavailable evidence?

6 comments
AuthorsOpenReview ↗

We sincerely appreciate the reviewer.

We have revised the manuscript in response to the reviewer's insightful comments and uploaded the updated version.

W1 /& Q1 The original audit compares operational verdicts on the same executions. Table 8 of our revision specifies each record–rule pair: AO rejects any visible error, even after successful recovery, while Full Audit defines the reference verdict. Table 15 reports their disagreement. Our paired comparisons separately examine rule choice and evidence availability.

The AO rule can collapse outcomes distinguishable from its record. A failed call followed by successful recovery and one followed by another failure are both rejected, although their observations differ.

On the same held-out trajectories, we first fixed the AO record and replaced its rule with a recovery-aware Qwen judge. We then fixed the judge, prompt, and task context while adding tool observations to the call-only record. The judge received no oracle verdict.

Change on the same test trajectoriesTrajectoriesDisagreement beforeDisagreement afterNet reduction in errors
Fixed AO record, original rule → Qwen judge50046.8%39.0%39
Fixed Qwen judge, Call-only → AO50048.6%39.0%48
Fixed AO recordTrajectoriesOriginal errors correctedNew errors introducedNet reduction in errors
All held-out trajectories50015411539
Subset flagged as successful recoveries4715141

On the successful-recovery subset, the paired counts show exactly which way decisions moved when we changed the rule. With Qwen held fixed, providing tool observations reduced disagreement on the same trajectories. This supports missing observations as a contributor to error for the Call-only input. The two net changes answer separate questions and share the same AO endpoint.

Controlled test of missing evidence. In the approval-before-publication task, both writes succeed in either order and produce byte-identical terminal records. The two orders are equally likely. The oracle accepts approval followed by publication and rejects publication followed by approval.

Evidence retained for this taskRemaining verdict entropyLowest attainable error
Complete terminal state1 bit50%
Target file IDs in write order0 bits0%

Any judge reading only the terminal state receives identical input for opposite verdicts. The ordered file IDs distinguish the two executions exactly. In our revised paper, Section 4 presents this case; Appendix E.2 gives the calculation for the order-constrained task following Table 21.

W2 Consider a designer deciding whether to retain payload contents, write order, or both. In a task requiring approval before publication, reversing the writes produces byte-identical terminal states with opposite verdicts. In a task requiring only the correct final payload, reversing their order preserves the verdict. We enumerated the declared execution distribution, calculated conditional verdict entropy for each candidate record, applied the uncertainty constraint, and only then compared storage costs.

Design parameterValue
Task contexts3
Enumerated branches8
Candidate logging schemes133
Allowed additional uncertainty relative to Full0 bits
Task and logging choiceConditional verdict entropyMinimum decision errorMean serialized bytes
Order-constrained task, complete terminal state1 bit50%318.0
Order-constrained task, ordered file IDs0 bits0%35.0
Terminal-content task, final payload content0 bits0%28.5
Pooled tasks, final payload content and ordered file IDs0 bits0%59.5
Pooled tasks, Full Audit0 bits0%2,657.5

Under a common logging scheme for the pooled tasks, payload content plus write order is the least expensive feasible candidate. The entropy calculation establishes feasibility, while bytes determine the selection among feasible schemes. These exact quantities apply to the declared finite distribution.

W3 The policy samples At∼π(⋅∣Vtpol)A_t \sim \pi(\cdot \mid V_t^{\mathrm{pol}}), where VtpolV_t^{\mathrm{pol}} is the message the runner sends at decision tt. It contains the task identifier and description, the configured tool schemas and current state summary, and the history of tool names, arguments, success or error indicators, and observations returned to the agent. If the runner rejects a finish request, it appends the rejection to that history before the next decision. The evaluator stores the paired before/after snapshots and backend audit metadata separately.

In our revised paper, Section 4 reports paired decoder errors in Table 3 and uses the approval-order task to select logging fields under Equation 20. Section 3.9 defines the policy-visible input, and Algorithm 1 in Appendix B.4 uses that input when sampling an action.

We sincerely appreciate the reviewer.

AuthorsOpenReview ↗

Gentle Follow-up on Our Rebuttal

We sincerely appreciate your insightful comments. We have carefully addressed your concerns and submitted our rebuttal. We would be grateful if you could take a moment to review our responses and share any further comments. Thank you so much again for your valuable time and consideration.

AuthorsOpenReview ↗

Second Follow-up on Our Rebuttal

I am following up once more on the rebuttal we submitted. We greatly appreciate the reviewer. Please let us know if any further information would be helpful. Thank you very much for your kind attention.

Comments on the paper

3 comments
AuthorsOpenReview ↗

Thank you so much for your time and efforts in handling our submission.

Thank you all for your time and consideration. We have carefully addressed all the reviewers' concerns in our rebuttal and sincerely appreciate the positive feedback from the reviewer who has engaged in the discussion.

We would greatly appreciate any further feedback from the other reviewers, particularly regarding whether our responses have adequately addressed their concerns. As the discussion period is approaching its end, we hope there will still be an opportunity for further discussion and clarification.

Thank you again for your time and consideration.

Area_Chair_FmArOpenReview ↗

Reminder: Please respond to the author rebuttal

Dear Reviewers gXLm and eNTY, the authors have responded to your reviews with a revised paper and additional experiments, and the author-reviewer discussion ends soon. Please read their response, post a brief reply on whether your concerns are addressed, and update your scores if your assessment has changed. Thank you! AC.

AuthorsOpenReview ↗

Summary. Thank you very much AC.

We sincerely thank the AC and all reviewers for their patience in reviewing our paper and for their great efforts throughout the process.

Among the three reviewers, reviewer KPJk has recognized our work after carefully reading our responses and maintained a positive score. For eviewer gXLm, despite receiving no further reply, we believe our responses have fully addressed their concerns. We have also carefully revised the manuscript in accordance with all reviewers' comments. Reviewer eNTY posted a very brief comment at the final time, still raising an audit-related concern. However, we genuinely believe we have clarified this issue thoroughly in our rebuttal, and we are confident it has been resolved.

Once again, we thank the AC and the reviewers for their patience in reviewing and for their great efforts on our paper.

In particular, we are deeply grateful to the AC for the kind help regarding our paper.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.