PaperlayerView exact revision on arXiv

Source-linked AI summary

COUNTERMEM: World-Model Verified Counter-Factual Memory for Language Agents

Hongji Pu, Ruixiang Tang, Yongfeng Zhang

arXiv:2609.31874v1cs.AI

TL;DR

Existing agent memory mainly records factual trajectories, leaving unchecked whether a different action would have improved an outcome. COUNTERMEM checks local alternatives and stores verified corrections with conditions for reuse, then uses a learned policy to select a record or skip memory. It improves both ReAct and Reflexion across all 12 benchmarks with gpt-oss-120b, while reported task-run tokens decrease across two backbones.

  • Problem

    Existing agent memories mainly preserve factual actions and feedback, leaving untested whether a different action would have improved the outcome; evaluating alternatives in active environments can cost interactions or alter the comparison state.

    Source: §1 · p. 1

  • Method

    COUNTERMEM checks local edits to failed actions from a copied or reset state, stores verified corrections with outcomes and applicability conditions, and trains a policy to select a retrieved record or skip memory.

    Source: §1 · p. 2, §3.2 · p. 3

  • Results

    With gpt-oss-120b, COUNTERMEM improves both ReAct and Reflexion on all 12 benchmarks across six domains, averaging +12.6 points; across two backbones, task-run tokens decrease by 7.7–42.0%.

    Source: §1 · p. 2, §7 · p. 9

  • Takeaways & Limitations

    Further analyses indicate that useful counterfactual memory requires verified corrections and appropriate reuse, since mismatched records can erase gains or cause harm.

    Source: §7 · p. 9

    Benchmark task performance is not a deployment safety guarantee, and a checked correction may not be safe under different requirements or permissions.

    Source: §9 · p. 10

Abstract

from arXiv · show

Existing agent memory frameworks mainly create memory through an agent's interaction with the factual world, e.g., remembering feedback from actions taken to improve performance on future tasks. However, these frameworks seldom ask the "what if" question during memory construction: what if a different action had been taken, would the feedback have changed, and how could this feedback become useful memory? Obtaining such feedback directly in an active environment can be expensive and can alter the state needed for comparison. In this work, we introduce COUNTERMEM, a reinforcement-learning framework for constructing and using verified counterfactual memory across tasks. After a failed action, COUNTERMEM evaluates local alternatives from a copy or reset of the original state using executable world models, such as tests, proof checkers, and solvers. It stores improvements with the original and corrected actions, checked outcomes, and conditions for reuse. A learned memory-use policy selects a retrieved record or skips memory to balance task success and interaction cost, while the base LLM remains fixed. Both memory and policy are frozen during held-out evaluation. We evaluate COUNTERMEM on 12 benchmark settings across six domains. With gpt-oss-120b, COUNTERMEM improves both ReAct and Reflexion on all 12 benchmarks across six domains, averaging a gain of 12.6 percentage points over their unaugmented versions. In the four-domain comparison across two backbones, task-run tokens decrease by 7.7-42.0%, excluding offline selector-training costs. Further analyses show that removing verification or persistent storage weakens the gains, while applying verified corrections to unsuitable decisions can reverse them. Code will be released upon acceptance.

1 INTRODUCTION

Existing agent memories preserve factual trajectories, but do not establish whether an untried alternative would have improved an outcome. COUNTERMEM evaluates local alternatives, stores verified corrections with reuse conditions, and improves both base agents across the reported benchmarks.

1 INTRODUCTION

  • Existing memory methods mainly retain actions and feedback from factual trajectories, while alternative actions could offer useful experience that the original trajectory never reveals.A proposed alternative is not evidence of improvement unless it is checked.Source: §1 · p. 1
  • Testing alternatives in active environments can add interactions or change the comparison state, while evaluating every alternative can be costly.Copied or reset states and executable evaluators offer a controlled way to test bounded alternatives.Source: §1 · pp. 1–2
  • COUNTERMEM stores checked action contrasts and applicability conditions, then trains a policy to select a retrieved record or skip memory based on task success and interaction cost.The base LLM remains fixed, and memory and policy are frozen for held-out evaluation.Source: §1 · p. 2, Figure 1 · p. 2
  • With gpt-oss-120b, COUNTERMEM improves both ReAct and Reflexion on all 12 benchmarks across six domains, averaging +12.6 points.Across two backbones, task-run tokens decrease by 7.7–42.0%.Source: §1 · p. 2

2 RELATED WORK

Prior work addresses agent memory, counterfactual reasoning, and executable world models. COUNTERMEM connects these threads by retaining checked action alternatives, along with the conditions for future reuse.

2 RELATED WORK

  • Agent-memory systems retain reflections, experiences, workflows, or strategies, while counterfactual methods evaluate alternative outcomes or actions.The cited examples include Reflexion (Shinn et al., 2023), ExpeL (Zhao et al., 2024), and counterfactual methods (Vashishtha et al., 2026; Antoniades et al., 2025).Source: §2 · p. 3
  • COUNTERMEM combines these directions by checking local alternatives at the same decision state and retaining their outcome contrasts and applicability conditions for cross-task reuse.Unlike current-task planning, its retained evidence is bounded by the tested state and available checks.Source: §2 · p. 3
  • World models support planning by predicting or simulating consequences, and executable tests provide direct feedback for software agents.The cited work includes Hafner et al. (2019; 2020) and Jimenez et al. (2024).Source: §2 · p. 3

3 METHODOLOGY

COUNTERMEM builds records from checked edits to failed actions and uses a learned selector to decide whether a compatible record should guide a later action. The base LLM stays fixed while memory is constructed, the selector is trained, and held-out tasks are evaluated.

3.1 WHAT THE AGENT REMEMBERS

  • COUNTERMEM saves an improved action, its check results, and conditions for use as a record that a selector can later offer to the LLM or skip.The base LLM parameters remain unchanged throughout the construction, selector-training, and testing stages.Source: §3.1 · p. 3

3.2 MODULE I: PROPOSE ALTERNATIVES TO A FAILED ACTION

  • After a failed action, a generator proposes at most four local alternatives, each asking what would have happened if that edited action had been taken.The evaluator is a task-specific test suite, proof checker, SQL result checker, or solver, which the paper calls a world model.Source: §3.2 · p. 3

3.3 MODULE II: CHECK ALTERNATIVES AND STORE CORRECTIONS

  • Alternatives are checked from a copy or reset of the original state, and a completed check must show improvement above a minimum threshold for a correction to qualify.Records retain the original and improved actions, check results, applicability conditions, and reuse statistics; the specified store holds at most 200 records.Source: §3.3 · p. 4

3.4 MODULE III: RETRIEVE A RECORD AND DECIDE WHETHER TO USE IT

  • On later tasks, retrieval filters records by applicability conditions and ranks candidates, while a DQN selector chooses one record or skips memory.The selector is trained with rewards for task completion and penalties for evaluator calls, failed attempts, and token use; it predicts expected reward for each choice.Source: §3.4 · p. 4

4 EXPERIMENTAL SETUP

The experiments compare memory mechanisms across benchmark domains and examine how accumulated records transfer and should be retained. Source-task memory construction, selector training, and held-out evaluation use separated stages, with success and cost as evaluation measures.

4 EXPERIMENTAL SETUP

  • The experimental setup measures whether earlier corrections help solve new tasks using success and cost.The benchmark suite spans mathematics, coding, formal verification, text-to-SQL, SMT, and SAT, with task-appropriate executable checks.Source: §4 · p. 4, §4.1 · p. 5

4.1 TASKS, AGENTS, AND MEMORY BASELINES

  • The main comparison tests six memory conditions across ReAct and Reflexion with two LLM backbones, alongside a separate Best-of-N compute control.Table 1 summarizes four domains; the full 12-benchmark, six-domain evaluation is reported in Appendix D.7.Source: §4.1 · p. 5, Table 1 · p. 6

4.2 BUILD MEMORY, TRAIN SELECTION, THEN TEST

  • Source tasks build records, training tasks update only the selector, and held-out tasks test reuse with the store and selector fixed.Held-out tasks appear in neither construction nor selector training.Source: §4.2 · p. 5

4.3 WHAT THE ADDITIONAL EXPERIMENTS CHANGE

  • Additional experiments vary source-task accumulation, record-retention rules, and transfer conditions, including look-alike tasks where an old correction becomes wrong.Retention strategies are compared at equal capacity; ablations remove checks or storage, or change which records reach the selector.Source: §4.3 · pp. 5–6

4.4 EVALUATION METRICS

  • Scores use a 0–100 success scale, while token totals include reasoning, retrieval, and augmentation but exclude offline selector-training costs.Figure 2 also tracks retrieval and context tokens per task, score loss on earlier tasks, and retention-rule scores; its accumulation checkpoints count source tasks, not records.Source: §4.4 · p. 6, Figure 2 · p. 7

5 RESULTS

COUNTERMEM’s stored corrections improve benchmark performance and reduce task-run tokens, while transfer depends on task conditions and interaction-cost changes vary by benchmark. Results also favor utility-aware retention and show that more source tasks do not guarantee more useful guidance.

5.2 WHAT CHANGES AS THE AGENT ENCOUNTERS MORE SOURCE TASKS?

  • As more source tasks accumulate, COUNTERMEM’s held-out score rises, while ReasoningBank’s first rises and then falls; retrieval and context costs rise for both.COUNTERMEM loses less performance on earlier tasks at each nonzero checkpoint, though neither fully preserves it.Source: §5.2 · p. 7
  • With the same record limit, utility-based retention scores 65.3, versus 59.8 for similarity, 54.2 for recency, and 51.7 for random retention.Its 5.5-point advantage over similarity supports utility-aware retention when storage is limited.Source: §5.2 · p. 7

5.3 WHEN DOES A STORED CORRECTION APPLY TO A NEW TASK?

  • COUNTERMEM scores higher than ReasoningBank in all four task-change conditions, but its score falls from 67.4 in the original environment to 52.6 in a new one.Earlier corrections remain useful, but do not remove transfer difficulty.Source: §5.3 · p. 7, Figure 3 · p. 8
  • In the original environment, COUNTERMEM has higher success with lower coverage (76.9% versus 82.4%), so finding guidance more often does not explain which method succeeds more often.Figure 3 distinguishes task success, retrieved-guidance frequency, and harmful-use percentages.Source: §5.3 · p. 8, Figure 3 · p. 8
  • On look-alike tasks, COUNTERMEM reaches 49.8% success versus 36.4% for ReasoningBank, with harmful use at 11.8% versus 27.6%.Removing applicability condition c raises COUNTERMEM harmful use from 11.8% to 34.2%.Source: §5.3 · p. 8

5.1 DOES EARLIER EXPERIENCE HELP SOLVE NEW TASKS?; 5.4 DOES BETTER PERFORMANCE REQUIRE FEWER EVALUATIONS?

  • Across 12 benchmarks, COUNTERMEM improves both agents in all 24 comparisons, averaging +12.6 pp; task-run tokens fall by 7.7–42.0% relative to “None”.Interaction-cost changes are benchmark dependent.Source: §5.1 · p. 7, §5.4 · p. 8

6 FURTHER ANALYSIS

The analyses test whether checking and retaining corrections contribute to gains, and whether records are useful when matched to the current decision. Unverified advice and unsaved alternatives recover less than the full method, while mismatched records can weaken gains or cause harm.

6.1 WHAT DO VERIFICATION AND PERSISTENT STORAGE CONTRIBUTE?

  • Unverified advice gives +5.2/+2.1pp and checked alternatives without saved records give +7.1/+3.4pp, versus +18.5/+8.2pp for the full method.Unverified advice also uses 10.4/9.9 calls per solved task versus 9.6/9.1 for base agents; the full method uses 7.0/8.4.Source: §6.1 · p. 8

6.2 WHAT HAPPENS WHEN A VALID RECORD REACHES THE WRONG DECISION?

  • Matched retrieval gives +18.5/+8.2pp, versus +0.6/+0.4pp for random retrieval and -1.1/-0.9pp for shuffled retrieval.Shuffling yields 0.21 action changes and 0.17 harmful changes per retrieved record, compared with 0.29 and 0.03 for matched retrieval.Source: §6.2 · p. 9, Figure 4 · p. 9

7 CONCLUSION

COUNTERMEM turns tested corrections from earlier tasks into later-task guidance, with a selector that can offer a record or let the agent act without memory. The paper reports improved performance and lower task-run tokens, while further analyses emphasize verified corrections and appropriate reuse.

7 CONCLUSION

  • COUNTERMEM turns tested corrections from earlier tasks into guidance for later ones, improving both base agents across 12 benchmarks and reducing task-run tokens across two backbones.With gpt-oss-120b, gains average +12.6 points; task-run tokens decrease by 7.7–42.0%.Source: §7 · p. 9

8 AI USE STATEMENT(DOES NOT COUNT TOWARDS THE PAGE LIMIT)

The authors disclose using ChatGPT for manuscript language revision and clarification, while retaining responsibility for the final content and checking reported results against run artifacts and checkpoints.

8 AI USE STATEMENT(DOES NOT COUNT TOWARDS THE PAGE LIMIT)

  • ChatGPT was used for language polishing and clarification, not as a substitute for experimental validation or scientific judgment.Authors reviewed outputs and checked reported configurations and results against run artifacts and checkpoints.Source: §8 · p. 10

9 ETHICS STATEMENT(DOES NOT COUNT TOWARDS THE PAGE LIMIT)

Persistent memory raises reuse and information-protection concerns, and benchmark task performance does not establish deployment safety.

9 ETHICS STATEMENT(DOES NOT COUNT TOWARDS THE PAGE LIMIT)

  • Stored trajectories may expose sensitive information; records should preserve source and scope, and benchmark task performance is not a deployment safety guarantee.Source-task verification does not establish that a correction is safe under different requirements or permissions.Source: §9 · p. 10

10 REPRODUCIBILITY STATEMENT(DOES NOT COUNT TOWARDS THE PAGE LIMIT)

The reproducibility statement documents COUNTERMEM’s verified-memory and frozen held-out evaluation procedures, alongside definitions of reuse, comparisons, and interaction metrics. It also clarifies the limits of what verification and reported measures establish, cautioning that different denominators and task-run token budgets are not equivalent measures of total cost.

A LIMITATIONS AND FUTURE WORK

  • Checked improvements do not guarantee correctness on future tasks, and stale or unsuitable records can harm transfer; the reported comparisons do not isolate DQN’s benefit or establish lower total cost or safe deployment.The authors propose combining records, detecting or retiring stale ones, and reporting end-to-end training and runtime costs as future work.Source: A LIMITATIONS AND FUTURE WORK · p. 15

B.1 VERIFICATION AND ADMISSION

  • A record is admitted only after candidate evaluation completes and its raw utility gain exceeds 0.05; checked gains support corrections in that setting, not universal future correctness.Records preserve the situation, original and improved actions, check results, reuse conditions, and source-task metadata; an illustrative SQL record is not a measured test case.Source: §B.1 · p. 15, §B.2 · p. 15

B.3 CAPACITY AND REUSE

  • The store is capped at 200 correction records, retrieval returns up to three eligible records, and the selector can use only one; retention considers checked improvement, reuse utility, frequency, and redundancy.The 200-task construction checkpoint is not necessarily 200 stored records, and the accumulation analysis reuses one trained selector across snapshots.Source: §B.3 · p. 16, §B.4 · p. 17, §D.3 · p. 20

C.1 DECISION PROCESS AND OBSERVATIONS

  • At each decision, the selector presents at most one retrieved record or skips memory; its reward favors task completion while penalizing evaluator calls, failed actions, and tokens.The Q-network is trained while the base LLM, generator, evaluator, and admission rules remain fixed; held-out selection is greedy, and the compressed observation omits full agent history.Source: §C.1 · p. 17, §C.2 · p. 18

C.3 CONSTRUCTION, TRAINING, AND EVALUATION PROCEDURE

  • Held-out evaluation freezes both the memory snapshot and policy, while independent reruns require task manifests, the runner, benchmark environments, evaluator traces, and trained checkpoints.The reported task-run token totals exclude offline selector-training costs.Source: §10 · p. 10, §C.3 · p. 19

D.1 BENCHMARKS AND EVALUATORS

  • The twelve benchmark settings use executable checks, but successful SQL execution alone does not establish that a query answers the question; held-out SQL construction and evaluation use 60 and 40 tasks, respectively.The SQL configuration also uses 35 construction databases and 34 nonoverlapping evaluation databases.Source: §D.1 · p. 19, §D.2 · pp. 19–20

D.3 ACCUMULATION CHECKPOINTS AND RECORD RETENTION

  • Accumulation checkpoints count processed source tasks, not stored memories, and the fixed-capacity comparison controls record count but not record length, retrieval tokens, or all computational costs.The figure uses five source-task orderings; its earlier-task regression measure is distinct from held-out performance.Source: §D.3 · p. 20

D.4 TRANSFER CONDITIONS AND REUSE MEASUREMENTS

  • The transfer study uses 60 source–target pairs per condition and distinguishes task success, retrieval coverage, and harmful use; retrieval coverage is neither a selection rate nor a correctness rate.A retrieved record may be skipped, and a failed task alone does not show that memory caused the failure.Source: §D.4 · pp. 20–21
  • Retrieval coverage, harmful use, and intervention rates use different denominators and should not be interchanged.Coverage is per retrieval attempt; harmful use is per selected memory use, excluding retrieved-but-skipped records and failures without selected harmful actions. Figure 4(d) reports change rates per retrieved memory, while Appendix E.3 uses 120 paired tasks per domain.Source: §D.4 · p. 21

D.5 BASELINES AND INTERVENTIONS

  • The comparison controls add distinct mechanisms, while component and retrieval ablations vary verification, persistence, or record matching.Best-of-N adds current-task candidates without persistent memory or verifier-guided selection; the ablations are not comparisons between trained and fixed selection rules. Complete baseline prompts and per-method construction budgets are not supplied with the manuscript package.Source: §D.5 · pp. 21–22

D.6 METRIC CONVENTIONS

  • Normalized interaction counts divide world-model calls and failed attempts by solved instances, whereas the main table reports total task-run tokens.Reductions in normalized counts can reflect changes in both numerator and denominator; offline selector-training tokens and compute are not separately itemized, so task-run tokens do not establish equal total training cost or wall-clock time.Source: §D.6 · p. 22

D.7 VALUES UNDERLYING THE BENCHMARK BREAKDOWN

The appendix reports benchmark and backbone summaries, describes the prompt interfaces used in the runs, and compares methods under a common 6M-token budget. COUNTERMEM averages 63.5 in that comparison, ahead of both ReasoningBank controls.

D.7 VALUES UNDERLYING THE BENCHMARK BREAKDOWN

  • Figure 5 compares each augmented agent with its own unaugmented version; positive entries indicate higher scores or fewer evaluator calls and failed attempts per solved task.Negative reductions indicate additional interaction.Source: Figure 5 · p. 22
  • The mean across 24 score changes is 12.5625 pp; equal-weighted four-domain means are 18.5 pp for ReAct and 8.175 pp for Reflexion.The domain-weighted summary differs from the 12-benchmark mean because domains contain different numbers of benchmarks.Source: §D.7 · p. 22

D.8 PROMPT AND PARSER INTERFACES

  • The reported runs use fixed prompts with parser-checked output contracts, and prompt fields are truncated to specified character limits before rendering.The condition instruction asks for a checkable requirement that can be false on a similar-looking task; “none” is parsed as an empty condition treated as universally applicable.Source: §D.8 · pp. 22–23

E.1 BACKBONE SUMMARY

  • All four backbone configurations move toward higher scores and fewer total tokens, but four configurations are insufficient to establish how gains depend on base-model ability.The plotted band shows variation across the four agent–backbone combinations, not a confidence interval over runs.Source: §E.1 · p. 24, Figure 6 · p. 24

E.2 COMPARISON AT A COMMON 6M-TOKEN BUDGET

  • 63.5 average, exceeding ReasoningBank with MaTTS by 7.8 pp and ReasoningBank with verified feedback by 10.4 pp in the common-budget comparison.All methods use a 6M-token task-run budget across five domains.Source: §E.2 · p. 24

E.3 RESCUED TASKS, BROKEN TASKS, AND APPLICABILITY CONDITIONS

Paired runs count tasks rescued or broken by memory, while a separate ablation tests removing applicability conditions. COUNTERMEM has positive net counts across the five domains, but memory can still break individual tasks and removing applicability conditions increases harmful use.

E.3 RESCUED TASKS, BROKEN TASKS, AND APPLICABILITY CONDITIONS

  • A rescued task fails without memory and succeeds with it; a broken task succeeds without memory and fails with it.Tasks whose success status is unchanged contribute to neither count, and the difference measures net successful-task change in paired runs.Source: §E.3 · p. 24
  • Across 600 paired runs per method, COUNTERMEM yields 94 net additional successes versus 13 for ReasoningBank, while still breaking some tasks.COUNTERMEM’s domain net counts are +25, +15, +31, +6, and +17; in Formal Verification it rescues 17 tasks and breaks 11.Source: §E.3 · p. 25, Figure 8 · p. 25
  • Removing applicability field c raises harmful use from 4.2% to 6.1% on ordinary tasks and from 11.8% to 34.2% on look-alike tasks.The intervention removes c from both the retrieval filter and rendered record; percentages are per selected record use.Source: §E.3 · p. 25

Related papers

Loading 2609.31874v1…