The Memory Most Similar to the Current State Is Often Useless to Agents

When agents perform long-horizon tasks, memory systems usually retrieve by semantic similarity: whichever piece of history the current state resembles is stuffed back into context. The MemCredit paper focuses on an awkward problem: the most similar memory may not help you choose the right next action. In his summary on X, Elvis said that most retrieved memories have no effect on decisions, and semantic relevance correlates poorly with usefulness.

The paper's approach is straightforward: for each memory, perform a controlled counterfactual intervention, run once with it kept and once with it removed, observe how the agent's actions change, and record the change as credit. These credits are then used to train a lightweight estimator. At inference time, semantic relevance is only responsible for high-recall candidates, and the estimator decides who stays within a fixed token budget. The underlying agent policy is not changed, and no additional environment runs are needed at inference time.

Numbers on ALFWorld: with a 500-token historical memory budget, MemCredit reaches an 86.57% success rate, while BM25 reaches 65.67%. On average, each decision uses 152.1 memory tokens, 74.5% fewer than BM25. The DAIR.AI Academy paper page adds that at 750 tokens it reaches 90.30%, using 64.4% fewer memory tokens than MemArbiter. The paper evaluates on ALFWorld and WebShop, though the public abstract mainly provides ALFWorld comparisons.

The data side is even more counterintuitive. The paper's analysis says memory utility is sparse and strongly state-dependent, and semantic relevance cannot capture it. X user Saeid Sisakhti pulled a set of numbers from the paper: average memory utility is 0.176 in failure states and 0.029 in other states, based on 1,041 ALFWorld interventions. A cheap strategy thus emerges: spend more memory budget after failures, and stay lean the rest of the time. But he also cautions that when using GPT-5.4 as the policy, BM25 actually slightly wins on SR@50.

The most frequently asked question in the comments is cost. Adam Wang points out that credit comes from rerunning with and without each memory, and the compute bill is hidden there. ellipsis asks about compositional effects: if a memory is useful only in combination with another, will ablating them one by one mark it as waste? Blum and Giacomo Masseroni also ask about intervention data and the number of rollouts. The paper says inference does not change the policy and does not run extra environments, but counterfactual data during training still costs money.

Another analogy from practice is even more painful. MJ says that when building coding agents, the most similar memory is often the last time it hit the same error, so the agent repeats the same failed fix. Ranking by whether a memory led to a good next step works better than ranking by how similar it is. This observation aligns with the paper's direction and also explains why some memories look highly relevant but actually just push the agent back to where it was.

Paper link: https://arxiv.org/abs/2611.15600
Chat with Paper: https://academy.dair.ai/papers/memcredit-from-relevance-to-utility-for-decision-time-memory-in-long-horizon-web-2611.15600

The claim should be scaled back a bit: memory management is shifting from finding relevance to computing usefulness. The direction is clear, but utility depends on state, policy, and memory composition. Training intervention cost, cross-environment transfer, and algorithms for compositional credit will all determine whether it can move from ALFWorld to real web tasks and coding tasks. At least for now, semantic similarity should not alone decide how the memory budget is spent.