MemCredit: From Relevance to Utility for Decision-Time Memory in Long-Horizon Web Agents

Quanjiang Guo, Sijie Wang, Qianyang Zhu, Ben Zhang, Jinchuan Zhang, Ke Yan, Zhao KangarXiv 2026 · arXiv

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).

Figure 1: Motivation of MemCredit. Semantic relevance does not necessarily imply decision utility.

Methods

The core innovation of MemCredit is treating memory selection as a credit assignment problem. The framework consists of four main stages:

  1. Atomic Memory Construction: Interaction histories are broken down into discrete units (goals, states, constraints, etc.).
  2. 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.
  3. 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.
  4. 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.
Figure 3: Overview of MemCredit framework, showing the transition from offline counterfactual testing to online utility-aware arbitration.

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).
Figure 5: Counterfactual analysis showing that utility is sparse and varies significantly by decision state.

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.
Figure 2: Performance–memory Pareto comparison on WebShop, showing MemCredit in the "desirable region" (top-left).

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

Abstract

Large language model (LLM) agents increasingly operate over long Web interaction histories, making memory management critical for reliable and efficient decision making. Existing methods primarily optimize storage, retrieval, or compression, but the memories most semantically relevant to the current state are not necessarily those that most improve the agent's action. We introduce MemCredit, a decision-centric memory framework that shifts memory selection from semantic relevance to decision utility. MemCredit estimates the state-, reference-context-, and policy-conditional marginal contribution of individual memories through controlled counterfactual interventions, and distills these intervention-derived credits into a lightweight utility estimator. At inference time, semantic relevance is used only for high-recall candidate generation, while predicted utility arbitrates which memories are retained under a fixed token budget, without modifying the underlying agent policy or requiring additional environment interaction. We evaluate MemCredit on ALFWorld and WebShop against representative memory baselines. On ALFWorld, MemCredit achieves 86.57 SR@50 under a 500-token historical-memory budget, compared with 65.67% for BM25 retrieval. Counterfactual analysis further shows that memory utility is sparse, strongly state dependent, and poorly captured by semantic relevance. These results suggest that decision utility provides a more effective principle than relevance alone for long-horizon agent memory management.
BibTeX
@misc{guo2026memcredit,
  author = {Quanjiang Guo and Sijie Wang and Qianyang Zhu and Ben Zhang and Jinchuan Zhang and Ke Yan and Zhao Kang},
  title = {{MemCredit: From Relevance to Utility for Decision-Time Memory in Long-Horizon Web Agents}},
  year = {2026},
  eprint = {2611.15600},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.15600},
}
Figure