TL;DR
MemCredit is a decision-centric memory framework for LLM agents that shifts memory selection from "what looks similar" (semantic relevance) to "what actually helps" (decision utility). By using counterfactual interventions to train a lightweight utility estimator, it allows agents to achieve higher task success rates while using up to 75% fewer memory tokens than traditional retrieval methods.
What Problem Does This Paper Address?
As Large Language Model (LLM) agents tackle increasingly complex, long-horizon tasks—like navigating the web or managing household chores—their interaction histories grow massive. Standard memory management relies on semantic relevance (e.g., RAG using BM25 or vector embeddings) to decide what to keep in the limited context window.
However, the authors argue that "relatedness" does not equal "usefulness." A memory might be highly relevant to the current state but redundant, while a seemingly unrelated memory (like a specific user constraint mentioned ten steps ago or a record of a failed attempt) might be critical for the next action. This "Memory-Action Gap" leads to agents that are either inefficient (wasting tokens on noise) or prone to failure (forgetting critical constraints).
Methods
The core innovation of MemCredit is treating memory selection as a credit assignment problem. The framework consists of four main stages:
- Atomic Memory Construction: Interaction histories are broken down into discrete units (goals, states, constraints, etc.).
- Counterfactual Credit Collection: To find the "true" value of a memory, the authors perform offline experiments. They run the agent twice from the exact same state: once with a specific memory included and once without. The difference in the resulting reward is the marginal decision utility.
- Utility Estimation: Since running counterfactuals at inference time is impossible (too slow and requires environment snapshots), they distill these findings into a lightweight Utility Estimator (an ExtraTrees regressor). This model learns to predict utility based on features like memory age, functional type, and overlap with already-selected context.
- Budget-Aware Arbitration: At inference time, the agent first uses a fast relevance-based search to get a broad pool of candidates. Then, the Utility Estimator iteratively selects the most useful memories until the token budget is reached.
Datasets
The authors evaluated MemCredit on two diverse benchmarks:
- ALFWorld: A text-based environment for embodied agents to perform household tasks (e.g., "put a clean sponge in the cabinet").
- WebShop: A simulated e-commerce website where agents must find and purchase products that meet specific, multi-attribute user constraints.
Key Insights and Ideas
- Relevance is a poor proxy for utility: The authors found that semantic relevance has almost zero correlation ($\rho = -0.011$) with the actual counterfactual utility of a memory.
- Utility is sparse: In 86.9% of cases, adding or removing a specific memory had no measurable effect on the agent's behavior. Most memories are "noise" for any single decision step.
- State-Dependent Value: Utility is highly concentrated in "failure contexts." When an agent makes a mistake, memories that help it recover or avoid repeating the error become incredibly valuable.
- Separation of Concerns: The paper demonstrates that relevance is best used for recall (finding candidates), while utility should be used for arbitration (final selection).
Key Results
MemCredit consistently outperforms traditional retrieval and structured memory baselines, especially under tight token constraints:
- Efficiency Gains: On WebShop, MemCredit achieved the highest task score (0.612) while using only 152.1 tokens per decision—a 64.4% reduction in memory usage compared to the strongest baseline, MemArbiter, and a 74.5% reduction compared to BM25.
- Success Rate: On ALFWorld, with a strict 500-token budget, MemCredit reached an 86.57% success rate, significantly higher than BM25 (65.67%) and State-Aware Retrieval (76.12%).
- Robustness: The benefits held true across different LLM backbones, including Qwen, DeepSeek-V3, and GPT models, proving the framework isn't tied to a specific policy.
Limitations and Future Work
- Marginal vs. Joint Utility: The current estimator calculates the utility of memories one by one. It might miss "complementary" memories that are only useful when presented together.
- Environment Snapshots: The offline credit collection requires the ability to "rewind" the environment to the exact same state for counterfactual testing, which is difficult in non-deterministic or live real-world web environments.
- Frozen Policy: MemCredit assumes the underlying agent policy is fixed. Future work could explore co-training the memory selector and the agent policy together.
Summary updated