StaleBench: Isolating Stale Retrieval in Agent Memory, and Pricing the Fix

S M Mahbub MurshedarXiv 2026 · arXiv

TL;DR

Standard RAG systems fail when facts update because similarity search can’t distinguish between current and stale versions of the same entity. StaleBench is a new benchmark that reveals how traditional retrieval metrics can rank memory policies backwards, proving that "contaminated" contexts—containing both old and new facts—drastically degrade LLM reader accuracy even when the correct answer is ranked first.

What Problem Does This Paper Address?

Imagine an AI agent that remembers "Peter Sagan plays for Bora-Hansgrohe." Later, it learns "Peter Sagan plays for TotalEnergies." When asked, "Which team does Sagan play for now?", a standard similarity retriever sees two perfect matches for "Peter Sagan." Without a way to prioritize currency, it essentially flips a coin, returning the stale fact roughly 53% of the time.

This is the stale-retrieval failure. Existing benchmarks often conflate this with general knowledge updates or long-term recall. The authors argue that we lack a "public instrument" to measure how agent memory systems handle supersession—the process of one fact replacing another. Furthermore, they show that common fixes (like timestamp reranking) might improve retrieval scores while actually making the final answer worse for the LLM reader.

Methods

The authors introduce StaleBench, a framework that streams facts chronologically and poses "value-agnostic" queries (e.g., "Who is the current coach of X?").

They evaluate several Policies:

  1. Store-all: The baseline RAG approach (BM25 or Cosine similarity).
  2. Time-aware: Reranking the top hits by timestamp or using recency-weighted scores.
  3. Retention: A more sophisticated approach that uses a Keyer (to decide if an incoming fact is a new version of an existing one) and a Mechanism (to overwrite or invalidate the old version).

A core contribution is the Keying Ladder, which tests different methods for "same-fact detection," ranging from simple embedding thresholds to LLM-based adjudication and "Symmetric Keying"—resolving entities at both the write (ingestion) and read (query) paths.

Datasets

  • TempLAMA-based facts: The primary dataset consists of 892 real updating facts derived from Wikidata (2010–2020) across nine relations (teams, employers, etc.).
  • Scale Track: An expanded set of 2,904 facts to test the system at a larger scale.
  • Distractor Corpus: A 7,078-statement stream used to populate the "neighborhood" of facts, making same-fact detection more challenging.
  • Production Systems: The authors also evaluate three deployed memory systems—Mem0, Graphiti, and LangMem—plus a reimplementation of ERASE.

Key Insights and Ideas

  • The Metric Trap: The most surprising finding is that current@1 (how often the current fact is at rank 1) can be a deceptive metric. A policy might put the right answer at the top but leave the stale answer at rank 2. This "contamination" confuses LLM readers, leading to a massive drop in accuracy (up to 65.6 points) despite a high retrieval score.
  • The "Anchor" Problem: Most benchmarks use full entity names ("Peter Sagan"). In real logs, entities are often referred to by short forms ("Sagan" or "he"). Withdrawing this "lexical anchor" causes standard vector stores to collapse, but entity resolution can recover most of that loss.
  • Symmetric Resolution is "Free": Resolving a query to a specific "key" (entity ID) before searching is highly effective and doesn't require expensive generative model calls. It fixes the "miss" rate that plagues systems that only resolve entities during ingestion.
  • Reader Conflict: LLMs are unreliable at resolving conflicting evidence in their context window. If the retriever provides both the old and new team for a player, the reader often defaults to the wrong one based on position or internal bias.

Key Results

  • Baseline Failure: Standard cosine similarity retrieval surfaces a stale version of a fact 53% of the time.
  • Reranking Paradox: Timestamp reranking lifts current@1 to 0.925, but for some readers (like Qwen2.5), it actually decreases accuracy by 22.9 points because it leaves the context contaminated with the stale fact.
  • Retention Wins: Policies that actively remove or invalidate stale facts (Retention) outperform those that merely rerank them.
  • Symmetric Keying: On "anchor-free" data (using aliases), symmetric keying achieved a current@1 of 0.831, compared to just 0.111 for standard cosine retrieval.

Limitations and Future Work

  • Scope of Data: The benchmark focuses primarily on single-valued facts that change over time. It does not yet handle complex multi-valued facts or "retractions" (where a statement is simply marked as wrong).
  • Language & Discourse: The current version is English-only and uses templated text. It doesn't yet account for naturalistic dialogue features like pronouns or nicknames that require deep discourse coreference.
  • Saturation: On "anchored" tasks (where full names are always used), the benchmark is nearly saturated, suggesting that the real frontier for agent memory lies in the "anchor-free" regime.

Summary updated

Abstract

An agent that stores facts over time eventually stores several versions of the same fact. Asked a value-agnostic question - "which team does X play for now?" - a similarity retriever cannot prefer the current version, because every version matches the entity the query names. StaleBench isolates this stale-retrieval failure on 892 real updating facts, with currency labels from the source (Wikidata validity years via TempLAMA), never from a retrieval score. Our central result is that retrieval metrics can rank memory policies backwards: a retention policy and its retain-everything control return the identical statement at rank 1 for every test query, yet differ by 29.5 and 65.6 points in reader accuracy on two readers when no date is shown. Contamination@5, the metric we add, ranks them correctly where current@1 and current@5 do not. Withdrawing the lexical anchor that statements carry costs deployed keying mechanisms tens of points of freshness; entity resolution on both the write path and the query recovers most of the loss. Three deployed systems (Mem0, Graphiti, LangMem) and a reimplemented ERASE each handle supersession differently, and no single scoring convention describes all four. We release the data, a frozen evaluator, and reference baselines.
BibTeX
@misc{murshed2026stalebench,
  author = {S M Mahbub Murshed},
  title = {{StaleBench: Isolating Stale Retrieval in Agent Memory, and Pricing the Fix}},
  year = {2026},
  eprint = {2611.19752},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.19752},
}
Figure