Temporal Validity in Retrieval Memory: Eliminating Stale-Fact Errors for AI Agents over Evolving Knowledge

🕒 Published (v1): 2026-06-25 01:31 UTC · Source: Arxiv · link

Why this paper was selected

Temporal validity for RAG memory; stale-fact elimination critical for deployed agent correctness

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

RAG-based agent memory has no model of time: when a fact changes, both stale and current versions sit at near-identical embedding distances and RAG cannot choose between them. MemStrata replaces the similarity-based write path with a deterministic (subject, relation, object) supersession rule over a bi-temporal ledger, retiring contradicted facts before retrieval. On four evolving benchmarks it reaches 0.95–1.00 accuracy vs. RAG's 0.20–0.47, and drives stale-fact-error rate to ∼0% at the same ∼2.1 s retrieval latency.

Problem

Retrieval-augmented generation (RAG) is the dominant agent memory mechanism but is architecturally blind to time. When a fact is updated (e.g., a config value changes from 1800 s to 3600 s), both versions remain in the store with near-identical embeddings — contradictions score higher cosine similarity to the original (mean 0.812) than genuine rephrased duplicates do (mean 0.800). AUROC for separating duplicates from contradictions via cosine is 0.59 (near chance), and maximum achievable precision at any threshold is 0.67 — far below what a safe auto-update rule requires. This is a structural impossibility, not a tuning problem: no similarity threshold can safely distinguish "restates" from "contradicts."

Method

MemStrata introduces a temporal-validity memory layer between the agent and its LLM:

Write path — deterministic supersession: 1. Exact-duplicate short-circuit via normalized text hash (zero cost). 2. If the incoming turn yields a clean (subject, relation, object) triple, normalize the (subject, relation) key and look up active assertions. If an active assertion with the same key exists but a different object, supersede it: close the old row's validity interval (valid_to, superseded_by) and open a new row. No cosine comparison, no LLM call. 3. Non-triple prose falls through to a surprise gate (similarity + LLM judge), but this gate only drops exact duplicates; it does not compress near-duplicates (an earlier lossy variant that did this collapsed static recall).

Bi-temporal ledger: Facts are retired, not deleted, preserving valid_from/valid_to/superseded_by for potential as-of-time queries.

Read path: Embed query → cosine top-\(k\) over active facts only (superseded rows excluded) → pack original source sentences (not reconstructed triples). No LLM on the read path; latency sits at the embedding floor.

Evaluation uses Qwen2.5-Coder-7B (answer), Qwen2.5-Coder-3B (judges), nomic-embed-text (768-d embeddings), all local at temperature 0.

Marker-free benchmark invariant: Stale and current fact versions are textually identical except the changed value, with no "[OUTDATED]" or similar labels. Only ingestion order distinguishes currency, so only a temporal mechanism can exploit it. Removing a marker from an earlier benchmark dropped baseline accuracy by up to 14 points.

Key Contributions

• Structural impossibility result: Cosine AUROC of 0.59 for contradiction vs. duplicate detection on 98 labeled pairs; contradictions are more embedding-similar to originals than duplicates; max precision ceiling is 0.67.
• Deterministic (subject, relation, object) supersession rule over a bi-temporal ledger — no similarity threshold, no LLM, \(O(1)\) key lookup.
• "Retain, then supersede" design: stores distinct static facts exactly like RAG (preserving recall), compresses only on the contradicted axis (~48% reduction on evolving facts).
• Stale-fact-error elimination: ∼0% stale-fact error across four evolving benchmarks (vs. 15–40% for RAG when forced to answer).
• Marker-free evaluation protocol with unit-test enforcement, plus a forced-answer supplement that strips abstention to expose hidden stale-commitment.

Results

• Static benchmarks (domain, locomo): temporal_v6 ties naive_rag (0.82/0.30 vs. 0.86/0.30). The lossy ablation collapses to 0.62/0.13, isolating the cost of aggressive compression.
• Evolving benchmarks — accuracy (naive_rag → temporal_v6):
• code_mutation: 0.43 → 1.00
• config_migration: 0.25 → 1.00
• dependency_bump: 0.20 → 1.00
• api_evolution: 0.40 → 0.95
• Stale-fact-error rate (forced-answer regime): RAG 15–40%; MemStrata ∼0% across all four evolving benchmarks.
• Latency: temporal_v6 ∼2.1 s (no LLM on read path); LLM-reranking/verification baselines ∼16–18 s (∼8× slower) with no temporal benefit.
• Active-fact compression on evolving benchmarks: ∼48% (contradicted versions retired, distinct facts retained).
• Ablation bracket: removing supersession entirely collapses mean evolving accuracy from 0.99 → 0.33 (indistinguishable from RAG's 0.32), confirming deterministic supersession as the sole cause of the evolving-knowledge gain.

Limitations

• Structured benchmarks only: Evolving benchmarks use single-value templates; triple extractor achieves ~97% supersession there but only ~44% on messier natural-language contradictions (quarantined). Extraction quality — not the supersession mechanism — is the gating factor for unstructured text.
• Ingestion order proxies time: Benchmarks rely on state-A → state-B order rather than explicit timestamps; threading real valid_from timestamps and as-of-\(T\) retrieval is left as future work.
• Single 7B model on consumer hardware: Results may shift with larger models or cloud inference; benchmark sizes (tens of items) isolate mechanisms rather than rank systems at scale.
• Single-judge noise: 3B correctness judge occasionally mislabels stale answers as correct in gate conditions (not an issue for temporal_v6 since stale facts are absent from context).
• Entity canonicalization unresolved: Relation typing and multi-value extraction for the extraction layer are explicit future work.

Relevance to Agentic AI / LLM Agents

Persistent, long-lived agents (coding assistants, ops agents, research trackers) face a memory currency problem that becomes critical as deployed lifetimes grow: RAG accumulates contradictions without resolving them, and the embedding space provides no signal to distinguish stale from current. MemStrata's core result — that staleness detection must be structurally deterministic rather than similarity-based — establishes a hard boundary for RAG-based architectures and offers a drop-in memory layer that eliminates an entire failure class without touching the LLM inference path. The bi-temporal ledger design also enables future as-of-time retrieval, directly relevant to agents that must reason about how system state changed over time. This work connects to the broader push for agent memory systems (Mem0, MemGPT) but uniquely targets validity maintenance rather than recall depth.