PaperlayerView exact revision on arXiv

Source-linked AI summary

The Immutable Past: Formalizing State Mutability and Conflict Resolution in Mutable RAG

Hamed HaddadPajouh, Amir AmiriTabat

arXiv:2609.16073v1cs.CLcs.AI

TL;DR

Append-only RAG memory can let accumulated, contradictory historical states dominate valid updates, and the paper formalizes the resulting retrieval and generation failures. It introduces GC-Mem, which combines contradiction detection with temporal dominance to remove shadowed context. The paper reports that GC-Mem restores more than 90% accuracy.

  • Problem

    Append-only RAG memory retains historical states after updates, allowing semantically equivalent but contradictory stale chunks to dominate retrieval and impair valid-state recall and generation.

    Source: §1 · p. 1

  • Method

    GC-Mem is an inference-time protocol that uses temporal dominance and contradiction detection to remove older conflicting chunks from retrieved context.

    Source: §1 · pp. 1–2, §3.1 · p. 2, §4.2 · p. 4

  • Results

    GC-Mem empirically restores >90% accuracy, and its state-recovery theorem guarantees excision of older contradictions when at least one valid chunk is retrieved.

    Source: §4.2 · p. 4, §8 · p. 9

  • Takeaways & Limitations

    The paper concludes that pure temporal dominance provides a protocol for mutable RAG that restores state consistency where standard mutable RAG fails.

    Source: §8 · p. 9

    The benchmark is synthetic and optimized for single-attribute mutations, so GC-Mem still requires validation on live, concurrent multi-entity mutations using organic interaction logs.

    Source: §7 · p. 8

Abstract

from arXiv · show

Retrieval-Augmented Generation (RAG) serves as the primary memory architecture for long-horizon autonomous agents. However, treating shared memory as an append-only stream introduces \textit{Semantic Shadowing}, a critical failure mode where conflicting historical observations accumulate and statistically dominate valid recent updates. In dynamic environments, this results in severe state divergence as agents retrieve and act upon obsolete facts. This paper formalizes the mechanics of State Mutability to prove that standard dense retrieval suffers from Asymptotic Recall Decay. Furthermore, we formally demonstrate a Majority Vote Trap, revealing that increasing the retrieval context window paradoxically degrades generation accuracy by diluting the attention mechanism under conditions of semantic equivalence. To resolve this, we introduce GC-Mem (Garbage Collection for Memory), a strict inference-time consistency protocol. Unlike heuristic time-decay mechanisms---which indiscriminately destroy valid long-term memory---GC-Mem relies purely on a temporal dominance operator ($\Phi_{\mathcal{T}}$) paired with contradiction detection to surgically excise shadowed context. Evaluated across a rigorous, behaviorally inferred benchmark of 137,760 memory chunks and continuous accumulation sweeps, standard RAG and timestamp re-ranking baselines experience severe degradation. In contrast, GC-Mem empirically recovers $>90\%$ conflict resolution accuracy. We establish strict precision and recall deployment thresholds, ensuring state convergence where standard mutable RAG fundamentally fails.

1 Introduction

The introduction argues that append-only RAG memory lets obsolete states compete with valid updates, creating Semantic Shadowing. It formalizes the resulting retrieval and generation failures and proposes GC-Mem to remove contradictory context before generation.

1 Introduction

  • The motivating setting is long-horizon autonomous workflows, where shared memory is an append-only stream despite factual states changing over time.Examples include changing user preferences, project goals, and infrastructure.Source: §1 · p. 1
  • Semantic Shadowing occurs when old states remain after an entity updates, letting semantically equivalent but contradictory stale chunks dominate dense retrieval.The stated cause is the statistical majority of historical chunks.Source: §1 · p. 1
  • The paper proves that valid-state recall decays asymptotically, attention can fail despite retrieving valid chunks, and multi-factor scoring protects entrenched historical errors.Source: §1 · p. 1
  • GC-Mem uses temporal dominance at inference time to surgically remove logical contradictions from retrieved context before generation.The paper contrasts this with timestamp re-ranking, which it says destroys valid historical reasoning.Source: §1 · pp. 1–2

2 Related Work

The related-work discussion places GC-Mem at the intersection of agent memory, knowledge editing, temporal question answering, and long-context attention. It distinguishes its inference-time filtering of retrieved context from approaches that manage context, edit model weights, or rely on reflection.

2 Related Work

  • Existing agent-memory architectures largely treat memory as a monotonically growing, static knowledge base, while GC-Mem addresses mutable RAG memory.The passage discusses Voyager, Reflexion, MemGPT, GraphRAG, and HippoRAG.Source: §2 · p. 2
  • Unlike parametric editing methods such as ROME and MEMIT, GC-Mem filters retrieved context at inference time using NLI contradiction detection without weight updates.The passage contrasts this with temporal QA over evolving corpora.Source: §2 · p. 2
  • The paper frames the Majority Vote Trap as a mathematical asymptote in mutable memory, extending work on attention degradation when relevant information is surrounded by noise.It states that retrieval of correct states approaches zero as history grows, while stale evidence captures generation attention mass.Source: §2 · p. 2
  • GC-Mem is presented as a feed-forward alternative to multi-turn reflection loops, excising contradictions before generation to avoid their latency and token costs.Source: §2 · p. 2

3 Theoretical Framework

The theoretical framework models memory as timestamped chunks and entity states as piecewise-constant across transitions. It derives retrieval and generation failures under accumulated, semantically equivalent contradictions.

3.1 Problem Formulation

  • The framework represents the shared memory stream at time t as timestamped chunks and models an entity’s ground-truth state as piecewise-constant across transition intervals.For a query after the last transition, the terminal state is the sole valid state, and temporal dominance collapses chained contradictions to it.Source: §3.1 · p. 2, §3 · p. 2

3.2 The Shadowing Failure

  • Old and new states can have embedding similarities indistinguishable up to marginal noise, as illustrated by Figure 1’s noise distribution.Source: §3.1 · p. 3, Figure 1 · p. 3

3.1 Problem Formulation

  • The accumulation hypothesis assumes stale-state chunks greatly outnumber valid-state chunks for an attribute, such as 49 old diet mentions versus one updated mention.Source: §3.1 · p. 3

3.2 The Shadowing Failure

  • Under the accumulation hypothesis, the expected number of valid retrieved chunks tends to zero as an attribute’s history grows, establishing asymptotic recall decay.The passage characterizes the bound as a theoretical worst-case lower bound for recall failure.Source: §3.2 · p. 3, §3.1 · p. 3
  • The Majority Vote Trap predicts generation collapse even when retrieval includes valid evidence, because attention is non-discriminating across semantically equivalent chunks.The stale-state probability mass scales with stale-state representation.Source: §3.2 · p. 3

4 The GC-Mem Protocol

GC-Mem applies a temporal consistency protocol to a fixed retrieved candidate set. Pairwise contradiction detection and temporal dominance remove older conflicting chunks, with a theorem stating the condition under which state recovery follows.

4.1 Memory Architecture and Candidate Retrieval

  • The retrieval architecture forms a frozen candidate set from top-k medium-term memory hits, optionally unioned with a deduplicated short-term recency buffer.The same candidate set is used across Standard RAG, timestamp re-ranking, and GC-Mem for experimental parity.Source: §4.1 · p. 4

4.2 Conflict Oracle and Temporal Dominance

  • A pairwise NLI-based conflict function identifies logical contradictions within the retrieved set, with bounded O(|Rk|^2) operational complexity.Source: §4.2 · p. 4
  • The temporal dominance operator retains a chunk only when no newer retrieved chunk contradicts it; the state-recovery theorem says this excises older contradictions if at least one valid chunk was retrieved.Under that condition, the context is contradiction-free and P(y = Snew) approaches 1.Source: §4.2 · p. 4

5 Experimental Methodology

The experiments use a controlled synthetic benchmark to isolate temporal contradiction effects, with behaviorally inferred states designed to reduce keyword leakage. The evaluation compares parallel answer paths over the same retrieved candidates.

5.1 Dataset Scale and Rationale

  • The Temporal Mutation Benchmark covers 2,016 experiment instances and 137,760 memory chunks across six N:M accumulation ratios and four model architectures.Source: §5.1 · p. 4
  • External datasets FactConsolidation and WikiContradict yielded 0% and 10% CR-Acc, respectively, because they lacked controlled temporal contradiction ratios.Source: §5.1 · p. 4

5.2 The Behavioral Pipeline

  • Behaviorally inferred state constraints suppress keyword leakage to 0–3%, compared with up to 14% in preliminary templates.A secondary GPT-4 quality rater regulates the pipeline.Source: §5.2 · p. 4
  • Standard RAG, Timestamp re-rank, and GC-Mem receive the same retrieved candidate set, isolating differences to conflict detection and temporal dominance.Source: Figure 2 · p. 5

6 Results

Across the reported evaluations, GC-Mem prunes contradictory historical chunks, while timestamp and multi-factor approaches leave key consistency problems unresolved. Its gains depend on conflict detection, and candidate-set growth adds latency.

6.1 Timestamp Baselines vs. GC-Mem

  • Timestamp heuristics discard valid, non-contradicted historical facts along with stale ones; Table 1 reports CR-Acc and marks significant results at p < 0.01.Source: §6.1 · p. 5, Table 1 · p. 5

6.2 Short-Term Memory (STM) Dynamics

  • With STM enabled, standard RAG accuracy rises by exposing new-state evidence, but GC-Mem retains a substantially wider performance gap by pruning shadowed stale chunks.STM also supplies richer temporal context to the conflict oracle.Source: §6.2 · p. 5, Table 2 · p. 6, Figure 3 · p. 6

6.3 Detector Dependency and Deployment Threshold

  • GC-Mem's success is bounded by the model's reasoning capability, and high precision alone is insufficient because recall is decisive.Source: §6.3 · p. 5

6.4 Ablation: The Failure of Multi-Factor Dominance

  • Pure temporal dominance yields 94.7% CR-Acc, while adding usage frequency drops accuracy to 10.5% because stale chunks accumulate usage and stability scores.Table 4 presents the multi-factor scoring ablation.Source: §6.4 · p. 6, Table 4 · p. 7

6.5 Bag-of-Facts Evaluation: Isolating Protocol Ceiling

  • On DeepSeek-V3 in the Bag-of-Facts setting, GC-Mem removes an average of 13.28 shadowed chunks per query and lifts generation accuracy by +42.4 percentage points.The setting places relevant historical and updated chunks directly in context, removing the retrieval bottleneck.Source: §6.5 · p. 7, Table 5 · p. 7

6.6 Computational Overhead and Latency

  • For k = 10 without STM, GC-Mem takes 10.5 seconds per instance; STM raises latency to 15.0 seconds as the larger candidate set increases O(k^2) conflict checks.The larger set can also yield higher global accuracy by enabling more obsolete shadows to be pruned.Source: §6.6 · p. 8, Table 6 · p. 8

7 Discussion and Limitations

GC-Mem should be deployed only when its conflict detector has sufficient recall; the benchmark’s synthetic scope and added latency also constrain where the method has been validated and may be practical.

7 Discussion and Limitations

  • GC-Mem should be used only with a conflict detector capable of >50% recall; very low recall can leave the protocol inert, while partial detection can leave mixed context.The authors report gpt-4.1-mini at 100% precision but <1% recall, and say partial detection, as with gpt-4o, can confuse generation.Source: §7 · p. 8
  • The benchmark is synthetic and optimized for single-attribute mutations, so validation on live, concurrent multi-entity mutations remains future work.For typical k ∈[5, 50], the O(k^2) conflict check adds ∼250ms to a standard 400ms RAG pipeline and may be prohibitive under ultra-low-latency requirements.Source: §7 · p. 8

8 Conclusion

The conclusion argues that semantic shadowing undermines long-horizon standard RAG and reports that GC-Mem restores >90% accuracy. The appendix collects dataset statistics, benchmark breakdowns, and supplementary analyses.

8 Conclusion

  • GC-Mem, using a pure temporal dominance operator, empirically restores >90% accuracy against long-horizon semantic shadowing.The conclusion also states that heuristic time-decay and multi-factor scoring fail to preserve state consistency.Source: §8 · p. 9

A Artifact-Backed Results Appendix

  • The artifact appendix gathers dataset statistics, headline aggregates, per-condition breakdowns, ablations, and supplementary plots, including retrieval recall, conflict removals, latency, and significance summaries.These materials document benchmark cells; the passage does not report their specific values.Source: A Artifact-Backed Results Appendix · p. 10

A.1 Dataset Construction and Composition

  • The dataset materials describe synthetic chat-session composition, including distributions of old, new, and distractor turns and synthetic entity attributes by contradiction severity.The table reports per-instance means and standard deviations; the figure covers Chat-Medium (n=48) and Chat-Large (n=65).Source: Table A.1 · p. 10, Figure A.1 · p. 10, Figure A.2 · p. 11

A.2 Primary Benchmark Tables

  • The primary benchmark tables report accuracy for Standard RAG, timestamp re-ranking, and GC-Mem across dataset and STM conditions, with per-condition recall, shadows removed, errors, and runtime.A separate prompt-mode table reports mean ∆GC for Forced-choice and Allow-unclear prompts by model and STM setting, stating that GC-Mem improves over Standard RAG in all 12 cells.Source: Table A.2 · p. 10, Table A.3 · p. 13, Table A.4 · p. 15
  • The appendix also provides a continued benchmark table and an illustrative multi-turn example showing state change conveyed without explicit status keywords.The figure color-codes turns by scenario role.Source: Figure A.3 · p. 12, Table A.3 · p. 14

A.3 Primary Benchmark Figures

The supplementary figures and tables examine STM, prompt framing, and bag-of-facts conditions. Their captions describe how the comparisons are structured and identify several reported patterns, without supplying most underlying values.

A.3 Primary Benchmark Figures

  • STM raises Recallnew from ∼37% to ∼98%, while also raising both Standard RAG and GC-Mem accuracy; GC-Mem retains a larger gap because it removes contradictions that recency heuristics leave in context.With STM on, more outdated chunks are surfaced and pruned; STM also increases latency while removing more shadows.Source: Table A.5 · p. 15, Table A.6 · p. 16, Table A.8 · p. 17

A.4 Example Prompt

  • The prompt-mode ablation compares Forced-choice with Allow-unclear across models to test GC-Mem’s robustness to prompt framing.Other figures summarize ∆GC by model, dataset, and STM cell, and paired-bootstrap 95% confidence intervals using 10,000 resamples per cell; intervals crossing zero flag weak κ or incomplete cells.Source: Figure A.5 · p. 19, Figure A.7 · p. 20, Figure A.8 · p. 21

A.5 Bag-of-Facts (No-Retrieval) Ablation

  • Bag-of-facts tables report mean accuracy and ∆GC across seven models, per-model results across both dataset sizes, and pooled mean gains alongside baseline accuracy.A separate STM-on comparison says timestamp re-ranking is competitive when retrieval recall is high, while GC-Mem retains an edge in Allow-unclear conditions.Source: Table A.7 · p. 17, Table A.10 · p. 24, Table A.11 · p. 24
  • In the bag-of-facts comparison, GC-Mem’s lift is described as larger for larger candidate sets with more conflicts, and positive bars across synthetic entity types indicate the result is not driven by one attribute family.The appendix also plots shadow counts by model and compares ∆GC with Standard RAG accuracy; the captions say weaker baselines often coincide with more pruning headroom.Source: Figure A.10 · p. 22, Table A.9 · p. 22, Figure A.9 · p. 23

B.1 Proof of Theorem 1: Asymptotic Recall Decay

The proof models top-k retrieval under an accumulation of stale and valid chunks. As stale chunks dominate, dense retrieval’s probability of returning no valid evidence approaches one.

B.1 Proof of Theorem 1: Asymptotic Recall Decay

  • Under uniform sampling without replacement, the expected number of valid retrieved chunks is kM/(N+M).Here, N counts stale-state chunks and M counts valid-state chunks.Source: §B.1 · p. 26
  • Because stale and valid states have nearly indistinguishable embedding similarity, dense retrieval is biased toward the more numerous stale-state phrasings, making the uniform-sampling expectation a strict upper bound.This bound relies on the accumulation condition N ≫ M.Source: §B.1 · p. 26
  • As N grows without bound, the probability of retrieving zero valid evidence approaches 1, establishing Asymptotic Recall Decay.Source: §B.1 · p. 26

B.2 Proof of Theorem 2: The Majority Vote Trap

Even when retrieval includes valid evidence, semantically equivalent contradictory states produce roughly equal query scores, leaving attention unable to distinguish them. The resulting generation probability favors the stale state when stale chunks outnumber valid ones.

B.2 Proof of Theorem 2: The Majority Vote Trap

  • Semantically equivalent states yield roughly identical query dot-products, so softmax over practically uniform logits produces non-discriminating attention.The proof attributes the similar scores to the states’ semantic embeddings being equivalent up to ϵ < 0.10.Source: §B.2 · p. 26
  • A state's generation probability sums attention mass over chunks asserting that state, so the stale state can dominate when its chunks are more numerous.This links the attention assigned to state-asserting chunks to the stale-state preference described in the proof.Source: §B.2 · p. 26
  • With one valid chunk among k−1 stale chunks, generation collapses because attention mass overwhelmingly favors the stale state.The proof considers a mixed retrieved context and concludes that attention dilution can defeat generation even when valid evidence is present.Source: §B.2 · p. 26
Loading 2609.16073v1…