COUNTERMEM Uses Verified Counterfactual Memory to Improve Language Agents

Summary

Existing language-agent memory systems mainly record feedback from actions that actually occurred, leaving alternative actions and their possible outcomes unexplored. The paper introduces COUNTERMEM, a reinforcement-learning framework that constructs and uses verified counterfactual memory across tasks. After an action fails, the framework evaluates local alternatives from a copy or reset of the original state with executable world models, including tests, proof checkers, and solvers. It stores the original and corrected actions, checked outcomes, and the conditions under which the correction should be reused. A learned memory-use policy decides whether to retrieve a record or skip memory, balancing task success against interaction cost. The base large language model remains fixed, and both the memory and policy are frozen during held-out evaluation. Across 12 benchmark settings in six domains, COUNTERMEM with gpt-oss-120b improves both ReAct and Reflexion over their unaugmented versions, with an average gain of 12.6 percentage points. In a four-domain comparison using two backbones, task-run tokens fall by 7.7% to 42.0%, excluding offline selector-training costs. Ablation analyses show that removing verification or persistent storage reduces the gains, while applying verified corrections to unsuitable decisions can reverse the improvement. The authors state that code will be released upon acceptance.