acceptodds
Under review as a conference paper at ICLR 2027

CounterGraft: Counterfactual Execution for Agent Self-Improvement

Abstract

A higher-scoring agent can still make worse behavioral choices: stronger downstream execution can conceal unnecessary or harmful changes. We introduce **CounterGraft**, a method for improving executable agent policies and prompts through counterfactual feedback. Its core operation runs the successor from the incumbent's selected choice and execution state, then compares the outcome with execution from the successor's own handoff. Holding the successor policy fixed reveals whether the replacement improves declared utility, supplying revision feedback unavailable from paired endpoints alone. CounterGraft uses this feedback to repair programs, then independently audits the selected program before release. On AgentDojo, it improves held-out task success by up to 32.9 percentage points over incumbent agents and by 1.3–1.9 points over the strongest adapted baseline across three executors; it also achieves the highest success among the compared methods on ALFWorld. In a matched AgentDojo experiment, exposing counterfactual feedback reduces harmful replacements by 70% while increasing task success, with the proposer, executor, and proposal budget fixed. Repairs recover required actions and improve replacement quality at an unchanged departure count. The release audit controls false certification on the bound workload under adaptive stopping, reduces replay beyond deterministic checks, and enables certified successors to become subsequent incumbents in prospective runs.

Primary area:
foundation or frontier models, including LLMs
Keywords:
agent self-improvement, counterfactual execution, language model agents, sequential testing, risk-limiting certification

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_1i57OpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

The paper introduced CounterGraft, a method to capture richer feedback signals during agent self-improvement.

Given an incumbent agent A0 and a candidate agent A1, both perform a task x, producing trajectories T0 and T1. A handoff, including an action and its associated execution state, is determined in T0, and A1 resumes from it to finish the task (hence “grafting”). Comparing this execution with A1’s own execution may provide richer feedback on whether the A0->A1 modifications are meaningful.

The method is empirically tested on ALFWorld and AgentDojo, with 1.3-1.9 pp gains on AgentDojo and 0.7 pp on ALFWorld over the strongest adapted baseline.

Critical strengths
  • Grafting a partial trajectory to a new policy could provide richer signals and enable better credit assignment. The motivation is sound.
Critical weaknesses
  • The manuscript is very hard to follow. In particular, (1) many terms are introduced without sufficiently clear explanations, e.g., incumbent, handoff, departure, and release; (2) it does not clearly establish the problem setting for “agent self-improvement,” which could refer to different problems.
  • Too many details are missing from the experimental settings. (1) How are the 64 development tasks and 159 confirmation tasks selected for AgentDojo? The original benchmark has 97 user tasks and 629 security test cases, so the numbers do not match directly. For ALFWorld, the source and role of the separate 200-task set are unclear, although the 134-task confirmation workload matches the standard unseen split. (2) The paper mentions “3 targets” in the AgentDojo experiments, but provides little information on what these are. (3) Details on the initial incumbent agents are also lacking. Did you use any open-source agent framework? What tools does this agent have?
Questions for authors
  • I find it hard to understand Figure 1. What extra information is obtained from grafting the child agent onto the parent agent’s trajectory? By reflecting on the child agent’s trajectory alone, the meta-agent could also plausibly find the bug in the stopping rule. The problem in this example seems identifiable from ordinary trajectory feedback.
  • How did you implement the Self-Refine baseline (Madaan et al., 2023)? It was originally designed for non-agent tasks. Adapting this method from output refinement to agent-program self-improvement would be non-trivial.
2 comments
AuthorsOpenReview ↗

To Reviewer 1i57: Counterfactual information, experimental construction, and Self-Refine adaptation

Thank you for your questions! We explain the additional execution evidence, test its value against complete trace feedback, and specify the experimental construction and baseline adaptation.

1. What information does Figure 1 add beyond a trace?

The additional observation is the successor's outcome from the incumbent-selected handoff. Comparing it with the successor's own execution holds the continuation policy fixed and measures the value of the changed choice. Paired endpoints alone do not determine this comparison, as formalized by the non-identification result.

In Figure 1, the same successor succeeds from the incumbent's post-refund state but fails from its own terminal handoff. A trace can suggest a stopping-rule repair; grafting executes the alternative and measures the replacement's disadvantage. The controlled experiment below tests whether providing that evidence improves the repairs found.

We test its practical value against a baseline that receives complete traces, tool returns, failures, and costs. Across five paired searches for each of F1/F2/F4, with proposer, executor, 16 opportunities, and selector matched, counterfactual feedback reduces harmful replacements 122 → 78 (36.1%), lowers them in 12/15 pairs, and increases passed units by 1.53/159 per search. Beneficial replacements rise 623 → 708 while departures rise 889 → 912. These results directly address the ordinary-reflection alternative: adding executed counterfactual evidence improves the revisions found with the same proposal budget and selector.

2. Agent setting and starting programs.

GPT-5.4 revises executable policy.py and prompts.py; the executor model stays fixed. Programs interact with AgentDojo's Banking, Slack, Travel, and Workspace environments or ALFWorld's embodied actions. The incumbent is the reference program, a successor is its revision, a handoff combines an action and restorable state, a departure is a changed selected behavior, and release admits a frozen candidate under the contract.

F1–F4 come from an upstream development-feedback proposal stage and are selected before confirmation for different failure profiles: action suppression, excessive verification, state-dependent control flow, and premature termination. F3 develops the procedure; F1/F2/F4 are the evaluated repair targets. All methods receive the same target-specific starting files. The execution supplement will identify the runner/framework and version, exposed tool schemas, initial program files, and artifact genealogy.

3. Workload construction.

AgentDojo counts executable units: (suite, user_task_id) for utility and (suite, user_task_id, injection_task_id) for security. Development contains 26 utility and 38 security units: 21 unearned units from F3 evidence plus 43 selected by SHA-256 ordering, frozen and shared across methods. Confirmation contains 49 utility and 110 security units, excluding all exact development and previously opened source-edge units. Utility pass means legitimate-task completion; security pass means attack prevention; execution errors receive zero. Broader template overlap is reported separately.

ALFWorld development uses valid_seen (140 games); complete-method confirmation uses valid_unseen (134). The separate audit uses all 200 games in json_2.1.1/valid_train in our data distribution, frozen before candidate evaluation. These are a separate collection, not a sample from the 140 games. The 140-versus-200 comparison has zero path, game-hash, and trial-identity overlap; task families can overlap.

4. Self-Refine adaptation.

Each Self-Refine opportunity critiques the current executable program using ordinary development feedback, then produces replacement policy/prompt files. A valid revision becomes the next iteration's current program; an invalid revision consumes its opportunity and retains the latest valid program. Final selection is applied separately to evaluated candidates using the common evaluator and qualification rule. Counterfactual records inform that selector for all methods but are withheld from the Self-Refine proposer. This preserves iterative critique–revision while controlling the editable interface, development workload, and confirmation protocol.

We will put these definitions and construction details alongside the main experimental setup and enlarge Figure 1 so that the three executions and their distinct roles are immediately legible.

Thank you again for your thoughtful feedback and for considering these additional results and clarifications!

Thanks for your response. The clarifications were helpful, but I still think they do not fully address my concerns. In particular, the data construction and experimental settings still appear somewhat arbitrary, and needs further justification.

RE 1. I am still confused by the example in Figure 1. You mentioned the “incumbent’s post-refund state” but neither of the two execution branches in panel (a) involves a refund. Did I miss anything?

RE 2. It is still unclear how F1-F4 were selected. By “an upstream development-feedback proposal stage” do you mean that you ran an initial agent, generated revisions, and grouped their failure modes? Was this grouping and selection performed by an agent or by humans? Do F1-F4 correspond, respectively, to “action suppression, excessive verification, state-dependent control flow, and premature termination”?

RE 3. Thanks for explaining the data splits. This explains what they contain, but not why the experiments were designed this way. In particular, for AgentDojo, why combine 21 unearned units from F3 with 43 units selected by SHA-256 ordering?

RE 4. Your implementation appears to be a substantial adaptation of Self-Refine (Madaan et al., 2023). I would expect such adaptations to be clearly documented in the paper.

The paper would also require significant work to improve its readability. Given these considerations, I'll maintain my score.

Reviewer_anoSOpenReview ↗
Rating
2
Confidence
2
Informativeness
1
Presentation
2
Soundness
1
Read review
Paper summary

This paper proposes an agent self-improvement framework that uses counterfactual execution to evaluate behavioral changes between incumbent and successor agents. By comparing the successor's performance under its own handoff with the incumbent's, the method generates feedback to guide revisions to agent prompts and policies. Experiments on AgentDojo and ALFWorld report improvements in task success and behavioral quality over adapted self-improvement baselines.

Critical strengths
  • The paper explores counterfactual execution as a source of fine-grained feedback for agent self-improvement, which is a valid design choice to me.
  • CounterGraft integrates counterfactual feedback, executable program revision, and independent release certification into a unified workflow.
  • The paper includes matched-feedback experiments that attempt to isolate the contribution of counterfactual information, alongside comparisons with existing self-improvement methods.
Critical weaknesses
  • The paper uses numerous concepts and terms, such as proposer, incumbent, successor, and handoff, without sufficiently establishing the overall self-improvement setting or clearly directing readers to their formal definitions. This makes the introduction and method sections unnecessarily difficult to follow, especially given the complexity of the proposed framework.
  • CounterGraft introduces additional counterfactual executions, iterative program revisions, and a separate release audit, making the overall procedure potentially more expensive than conventional self-improvement methods. A more comprehensive comparison of performance gains against computational cost would strengthen the evaluation.
  • Several presentation issues make the results difficult to interpret. For example, Figure 1 appears somewhat blurry. The colored shading in some tables is inconsistent. The notation and evaluation metrics are also introduced without sufficient explanation. Table 2 uses unexplained bold formatting, including inconsistent highlighting of the beneficial replacement metric (P). Additionally, task success is reported as percentages in Table 1 but as raw counts in Table 2, without clearly emphasizing the change in representation. Together, these issues reduce the clarity and accessibility of the empirical results.
  • The choice of evaluation benchmarks is insufficiently motivated. In particular, AgentDojo was originally developed primarily for evaluating prompt-injection attacks and defenses, rather than general agent self-improvement.
  • The construction of the evaluation workloads is insufficiently documented. The original AgentDojo benchmark contains 97 legitimate user tasks, whereas this paper uses 64 development tasks and 159 confirmation tasks per revision target (Section 4.1). The manuscript does not clearly explain how these workloads were constructed, whether additional tasks were introduced, or how they relate to the original benchmark.
  • The four revision targets (F1–F4) play a central role in the empirical evaluation, yet I find it hard to locate their construction, selection criteria, and differences.
  • The empirical evidence for consistent improvements over existing self-improvement methods is limited.
Questions for authors

See weaknesses.

3 comments
AuthorsOpenReview ↗

To Reviewer anoS: Evaluation clarity, workload provenance, and cost-controlled results

Thank you for your detailed questions! The new comparisons show improvements in both utility and security, an advantage over adapted HSI in all five replication blocks, and 40% fewer harmful replacements at closely matched development-token consumption. We clarify the experimental setting and provide the evidence below.

1. Setting and revision targets.

CounterGraft improves policy.py and prompts.py with the executor model fixed. The proposer edits these files; the incumbent is the reference program; the successor is a revision. A handoff comprises a selected action and restorable execution state. Running the successor from both handoffs measures replacement value under the same continuation policy. An independent audit then checks the frozen revision against the release contract.

F1–F4 originate from upstream GPT-5.4 proposals using development feedback, selected before confirmation for distinct failure profiles: action suppression (F1), excessive verification (F2), state-dependent control flow (F3), and premature termination (F4). F3 develops the procedure; F1/F2/F4 form the evaluation panel. Methods share each target's starting artifact, and all targets remain in the results.

2. Why AgentDojo, and what do 64 and 159 mean?

AgentDojo provides stateful tool-use environments in which a program revision can affect legitimate-task execution and resistance to injected objectives. ALFWorld complements it with embodied task completion.

Our AgentDojo counts refer to executable evaluation units: (suite, user_task_id) for utility and (suite, user_task_id, injection_task_id) for security. They are not counts of distinct canonical user tasks. Development contains 26 utility + 38 security units; confirmation contains 49 + 110. The shared development set retains 21 unearned units from F3 procedure-development evidence and adds 43 by deterministic SHA-256 ordering. It is frozen before candidate selection. Confirmation excludes every exact development unit and previously opened source-edge audit unit: exact-unit overlap is zero. Broader overlap is quantified as 26 user-task identities and 23 injection-task identities. The three targets share the same 159 units; 477 denotes target–unit evaluations.

Adequacy means legitimate-task completion on utility units and attack prevention on security units; execution errors receive zero. Aggregate Success counts passed evaluation units. The new five-search-per-target breakdown is:

TargetFeedbackUtility /49Security /110Combined /159
F1Endpoint + traces41.8107.2149.0
F1CounterGraft42.6107.4150.0
F2Endpoint + traces46.4109.0155.4
F2CounterGraft47.6109.4157.0
F4Endpoint + traces46.2108.2154.4
F4CounterGraft47.2109.2156.4

Both utility completion and attack prevention improve on every target in the five-search means. Legitimate-task completion accounts for 15 of the 23 additional passed units across the 15 pairs. Security pass denotes attack prevention; joint task completion under attack is a separate metric.

3. Repeated gains and computational cost.

Five repeated three-target comparisons favor CounterGraft over adapted HSI in every block: 455.6 versus 450.2/477 mean passed evaluations, with 11/15 versus 5/15 contract-compatible selections.

To test whether additional ordinary reflection substitutes for counterfactual execution, we also run five F2 searches per method under a common 30M-token development cap. The endpoint-only baseline computes no development counterfactuals and spends the saved budget on more proposals:

Mean per searchEndpoint-onlyCounterGraft
Development tokens24.90M24.91M
Proposal opportunities22.816.0
Passed units /159155.8157.0
Harmful replacements7.04.2
Contract-compatible selections1/54/5

Independent confirmation adds 3.58M and 3.73M tokens, respectively, giving totals of 28.48M versus 28.64M. At virtually equal development-token consumption, CounterGraft achieves 40% fewer harmful replacements and higher mean adequacy, even with 42.5% more proposal opportunities allocated to the baseline. Accounting separates proposer/executor input and output tokens and post-selection confirmation.

4. Presentation.

We will introduce the setting and metrics before the method, redraw Figure 1 with larger labels and vector graphics, standardize shading, define boldface in each caption, and label counts and percentages explicitly.

Thank you again for your thoughtful feedback and for considering these additional results and clarifications!

Thank you for addressing my concerns and providing additional experiments. While the new breakdown shows consistent directional improvements, the absolute gains remain modest, particularly given the limited number of revision targets. In addition, I remain unconvinced that the evaluation on AgentDojo and ALFWorld sufficiently supports the broader claims about agent self-improvement. Therefore, I will maintain my overall rating.

Thank you for considering the additional results! We would like to emphasize that the contribution concerns the quality of behavioral changes alongside endpoint performance.

Across 15 paired searches, harmful replacements decrease by 36.1%, while beneficial replacements and total departures both increase. In the separate token-controlled comparison, harmful replacements decrease by 40% at nearly identical development-token consumption, even though the baseline receives more proposal opportunities. These results demonstrate practical value beyond the modest endpoint gains.

Regarding scope, the repeated searches assess search variability, while F1/F2/F4 cover distinct starting-program failure profiles. AgentDojo and ALFWorld test the mechanism in stateful tool-use and embodied-action settings. The claim being evaluated is that successor-relative counterfactual feedback improves executable policy and prompt revision.

We would appreciate your reconsideration in light of these behavioral-quality and resource-controlled results, and clarification of which additional evidence would most directly address your remaining concern about scope. Thank you again!

Reviewer_MNCuOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes CounterGraft, a framework for improving agent policies and prompts using counterfactual execution feedback. In addition to evaluating the incumbent and candidate endpoints, it executes the candidate policy from the incumbent-selected handoff. Comparing the two candidate-policy continuations labels behavioral replacements as beneficial, harmful, or tied under a declared utility. These labels guide program revision, followed by an independently bound release audit combining deterministic completion checks with sequential statistical evidence. Experiments cover AgentDojo and ALFWorld, with additional frozen-update analyses across other systems.

Critical strengths
  1. The candidate-on-incumbent execution provides a useful diagnostic beyond endpoint performance. It distinguishes improvements in continuation from the value of replacing the selected handoff. The matched F2 experiment is particularly helpful: both conditions use the same evaluation and selection rule, while differing in whether the proposer receives counterfactual feedback. This directly tests the usefulness of that feedback for revision.

  2. The release procedure has a clearly stated statistical scope. The paper separates development from frozen-candidate confirmation and explicitly limits false-certification control to the bound workload under its sampling assumptions. Comparing sequential acquisition with deterministic completion checks on the same artifacts and acquisition orders also helps isolate the statistical procedure’s contribution.

Critical weaknesses
  1. The experimental evidence is insufficient to establish the robustness of the improvement over strong repair baselines. Each method–target pair receives one search, with three targets per AgentDojo executor and one selected artifact per method in the ALFWorld comparison. The gains over adapted HSI are 1.3–1.9 percentage points on AgentDojo and one task on ALFWorld. The headline 70% reduction in harmful replacements comes from a single matched F2 comparison, rather than repeated independent repair runs. The results are encouraging, but do not establish how consistently the feedback helps across search variation and initial artifacts. This limits my confidence in the general empirical claim.

  2. Faithful counterfactual execution is central to the method, but its reproducibility and sensitivity to execution variability remain insufficiently supported. The reproducibility statement indicates that the supplementary counts and statistical reference implementation do not replace the original execution harness or raw run logs. Appendix F.2 also reports that fresh replay reproduces 40 of 43 labels. This does not invalidate the conditional finite-table theorem, but leaves an important gap between that theorem and its operational use: how the table is constructed and how stochastic execution affects replacement labels and release decisions. More complete execution materials and broader replay-stability analysis are needed to assess this component reliably.

Questions for authors
  1. Can you provide independent repeated repair runs for the matched F2 experiment and the principal method comparisons, reporting variability across searches and initial artifacts? In particular, how consistently does counterfactual feedback reduce harmful replacements relative to endpoint-and-trace feedback?

  2. How are execution randomness and repeat-draw rules bound before an audit, and how sensitive are labels and release decisions to these choices? Please clarify the coverage of the reported replay-stability checks and whether the complete execution harness, selected policy artifacts, and branch-level logs can be made available.

  3. Appendix F.3 shows that the listed release-decision differences disappear when the budget counts only harmful replacements rather than harmful plus tied replacements. What motivates the strict-improvement contract for the intended deployment setting, and which conclusions remain under a harmful-only contract or alternative cost orderings?

3 comments
AuthorsOpenReview ↗

To Reviewer MNCu: Repeated searches, execution stability, and contract sensitivity

Thank you for your careful assessment! We address search robustness, execution stability, and contract sensitivity below.

1. The feedback advantage persists across repeated repair searches.

We extend the matched comparison to 15 paired searches: five each for F1, F2, and F4, retaining all outcomes. Both arms use GPT-5.4 as proposer, GPT-4.1 as executor, the same starting program, 64-unit development workload, and 16 proposal opportunities. Both selectors compute counterfactual labels; only CounterGraft exposes them to the proposer. The baseline receives complete execution traces, tool returns, failures, and costs. Each selected program is frozen before confirmation.

TargetMean passed units /159: baseline → CounterGraftMean harmful replacements: baseline → CounterGraft
F1149.0 → 150.08.4 → 6.4
F2155.4 → 157.08.2 → 4.2
F4154.4 → 156.47.8 → 5.0

Harmful replacements decrease 122 → 78 (36.1%), with reductions in 12/15 pairs. Beneficial replacements increase 623 → 708, while departures increase 889 → 912: CounterGraft makes more changes and improves their quality. Mean harmful reduction is 2.93 per search (target-stratified paired-bootstrap 95% CI: 1.73–4.00). Passed units increase by 1.53/159 on average; legitimate-task completion accounts for 15 of the 23 additional passes, and attack prevention for eight.

Replications independently regenerate and evaluate candidates under preassigned feedback-order seeds, paired across arms, with proposer temperature fixed at zero. Statistical resampling uses search pairs within each fixed target. A separate complete-method comparison against adapted HSI also favors CounterGraft in all five three-target replication blocks: 455.6 versus 450.2 passed evaluations/477 on average (+1.13 percentage points), with 11/15 versus 5/15 contract-compatible selections.

2. Expanded replay checks preserve the evaluated release decisions.

Before audit acquisition, the binding fixes the program, workload, execution configuration, handoffs, and repeat-draw rule; acquisition uses a fresh uniform order. We replay all 363 departures from six frozen artifacts, covering both feedback arms and all three targets. Each departure receives three fresh label evaluations, comparing both successor continuations in isolated environments. Restoration convention, utility, and majority aggregation are fixed; missing/restoration-failed branches and three-way disagreements remain unresolved.

Original and fresh-majority labels agree on 344/363 (94.8%); only two directly reverse beneficial versus harmful. Holding endpoint-loss records fixed to isolate replacement-label variability, all six census compatibility decisions and all six sequential verdicts remain unchanged under the same acquisition order, contract, and risk level. Two stopping positions change. The formal guarantee remains conditional on the bound execution table; this replay experiment separately tests its execution stability.

The anonymous reproducibility supplement will include the execution harness, selected policy/prompt artifacts, workload and run configurations, and branch-level records linking restored states to outcomes and replacement labels.

3. Harmful-replacement reductions survive alternative utilities.

On the same frozen artifacts, harmful counts remain lower when tool calls precede model turns in the cost ordering (125 → 81) and when utility uses adequacy alone (91 → 60).

The strict contract implements a deployment preference for justified behavioral change: a replacement earns its admission by improving declared utility. Accordingly, H + T counts harmful and unearned changes, while H alone implements a non-degradation preference. Under the harmful-only budget, both original matched-F2 candidates pass, with harmful counts of 10 versus 3. The release distinction depends on the chosen contract; the reduction in harmful replacements holds under either contract.

Thank you again for your thoughtful feedback and for considering these additional results and clarifications!

Thank you for the experiments. The paired searches address my concern. I suggest highlighting the 36.1% reduction across repeated searches and including the replay and cost-controlled results in the main text.

Just one last question: how many of the 19 replay disagreements reflect actual label changes?

Thank you for the helpful suggestions! We will highlight the repeated-search reduction and include the replay and cost-controlled results in the main text. Of the 19 disagreements, only two were actual changes between resolved labels, both beneficial↔harmful reversals. The remaining 17 were unresolved fresh evaluations under the predeclared three-draw rule. With endpoint-loss records held fixed, all six census compatibility decisions and all six sequential verdicts remained unchanged; only two stopping positions changed.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.