PACMI: Provenance-Aware Cascading Memory Invalidation for Long-Term LLM Agents

Yiqi Wang; Jiaqi Liu; Jiaqi Zhang; Zhangkai Wu; Yiqun Duan; Mingkai Zheng; Taotao Cai

cs.LGOct 5, 2026

PACMI: Provenance-Aware Cascading Memory Invalidation for Long-Term LLM Agents

Authors: Yiqi Wang, Jiaqi Liu, Jiaqi Zhang, Zhangkai Wu, Yiqun Duan, Mingkai Zheng, Taotao Cai

Organizations: University of Southern Queensland · Southern University of Science and Technology · Jiangsu University · The University of Sydney · Uploading Inc.

Abstract

LLM agents rely on long-term memory to retain and reuse information when performing tasks over long horizons. Existing methods provide limited support for handling memories that become outdated as new observations or domain evidence arrive. Such outdated memories may remain semantically relevant, continue to affect dependent records, and retain value as historical evidence. This calls for two capabilities: dependency tracking to identify downstream effects and historical preservation to retain useful past records. We propose Provenance-Aware Cascading Memory Invalidation (PACMI), a framework that represents memories and new evidence in a provenance graph with typed dependency edges. PACMI assigns records to a four-state validity lattice, propagates validity changes to dependent memories, and uses the resulting states for retrieval and stale-premise detection. We also introduce a diagnostic benchmark with 100 cases and 300 queries across five domains. The evaluation separates node, context-, and answer-level performance. PACMI achieves the highest final-answer accuracy on this benchmark, and its paired difference from the strongest baseline is significant under an exact McNemar test. The premise checker achieves perfect precision, recall, and F 1 on the controlled query distribution. Cascading propagation primarily improves memorystate correctness: removing it increases final-answer errors from 3 to 11, but the paired difference does not reach the 0.05 significance threshold. Code and data will be made publicly available.

Figures & tables

Figure 1: Overview of PACMI. Starting from an annotated pre-update provenance graph, PACMI inserts new evidence, classifies evidence–memory relations, propagates validity changes along typed dependency edges, performs validity-aware retrieval, and checks whether the query assumes a superseded fact before response generation.

Figure 2: Running example of cascading memory invalidation. New evidence $e_{2}$ updates memory $m_{1}$ , changing $m_{1}$ to superseded ; propagation through supports changes $c_{1}$ to needs-verification , and propagation through used-by changes $d_{1}$ to historical-only , while the related hard negative $m_{2}$ remains active . Validity-aware retrieval then prioritizes the new evidence and active memories.

	Node identification				Context		Accuracy by query type			Answer level
Method	DR $\uparrow$	AR $\uparrow$	UI $\downarrow$	OI $\downarrow$	SIC $\downarrow$	CVER $\uparrow$	Q1 $\uparrow$	Q2 $\uparrow$	Q3 $\uparrow$	Final $\uparrow$	Reuse $\downarrow$
Vector RAG	–	–	–	–	0.53	0.58	0.95	0.28	1.00	0.74	0.10
Recency-RAG	–	–	–	–	0.47	0.66	1.00	0.39	0.95	0.78	0.04
LLM-Only Update	1.00	–	0.68	0.00	0.49	0.64	1.00	0.47	0.42	0.63	0.03
CUPMem-style	0.93	–	1.00	0.00	0.40	0.76	0.97	0.43	1.00	0.80	0.03
A-MEM-style	–	–	–	–	0.47	0.88	1.00	0.71	1.00	0.90	0.00

Table 1: Main results on the stale-memory dependency benchmark. Arrows give the preferred direction. “–” marks a metric the method cannot produce: Vector RAG, Recency-RAG, and A-MEM-style make no explicit invalidation decision, and only propagation-enabled methods predict downstream affected nodes. Per assumption A3, the AR/UI columns verify propagation correctness rather than comparative advantage. Point estimates are shown here; percentile 95% confidence intervals from 10,000 case-level bootstrap resamples are reported in Appendix F .

Variant	AR $\uparrow$	UI $\downarrow$	SIC $\downarrow$	Acc $\uparrow$	Prem. $\uparrow$	Hist. $\uparrow$
PACMI	1.00	0.00	0.34	0.99	1.00	1.00
w/o Provenance	0.00	1.00	0.37	0.97	0.98	1.00
w/o Cascade	0.00	1.00	0.41	0.96	0.98	0.99
w/o Validity States	1.00	0.00	0.56	0.97	0.98	1.00
w/o Premise Check	1.00	0.00	0.34	0.83	0.80	1.00
w/o Hist. Preserv.	1.00	0.00	0.20	0.77	0.99	0.36

Table 2: Ablation. AR, UI, and SIC are state- and context-level; Acc, Prem., and Hist. are answer-level. All variants have OI

=0.00

. Recall-at-depth and percentile 95% case-bootstrap confidence intervals for all numeric cells are reported in Appendices F and H .

Method	Per update	Per query	Total
Vector RAG	0	0	0
Recency-RAG	0	0	0
LLM-Only Update	1	0	100
CUPMem-style	1	0	100
A-MEM-style	1	0	100
PACMI	1	$\leq 1$	400

Table 3: Auxiliary LLM calls, excluding the one answer-generation call every method issues per query and the evaluation judge. “Per update” counts calls triggered by one new-evidence item; “per query” counts calls issued at question time. The last column totals auxiliary calls over the benchmark’s 100 updates and 300 queries.

Appendix figures & tables13 assets

Supplementary material from the paper’s appendix.

Appendix

Domain	Cases	Old Mem.	New Evid.	Queries	Affected
Personal Profile	20	120	20	60	40
Location & Preference	20	120	20	60	40
Work & Project	20	120	20	60	40
Finance & Recommendation	20	120	20	60	40
Tool / Workflow State	20	120	20	60	40
Total	100	600	100	300	200

Appendix

Table 4: Statistics of the stale-memory dependency benchmark.

Method	Parameter	Value
PACMI, Vector RAG, Recency-RAG,	top- $k$ (final context)	5
LLM-Only Update, CUPMem-style
A-MEM-style	seed top- $k$	5
A-MEM-style	maximum expanded context	8
Recency-RAG	similarity weight	0.7
Recency-RAG	recency weight	0.3

Appendix

Table 5: Key hyperparameters used in the main experiments.

TP	FP	FN	TN	Prec.	Rec.	$F_{1}$
100	0	0	200	1.000	1.000	1.000

Appendix

Table 6: Intrinsic premise-detector results. Q2 is the positive class; Q1 and Q3 are negative.

Method	DR	AR	UI	OI	SIC	CVER
Vector RAG	–	–	–	–	0.534 [0.520, 0.548]	0.583 [0.565, 0.600]
Recency-RAG	–	–	–	–	0.473 [0.456, 0.489]	0.659 [0.639, 0.680]
LLM-Only Update	1.000 [1.000, 1.000]	–	0.680 [0.590, 0.770]	0.000 [0.000, 0.000]	0.487 [0.468, 0.505]	0.641 [0.619, 0.665]
CUPMem-style	0.930 [0.870, 0.980]	–	1.000 [1.000, 1.000]	0.000 [0.000, 0.000]	0.396 [0.385, 0.407]	0.755 [0.741, 0.769]
A-MEM-style	–	–	–	–	0.467 [0.455, 0.479]	0.882 [0.848, 0.916]
PACMI	1.000 [1.000, 1.000]	1.000 [1.000, 1.000]	0.000 [0.000, 0.000]	0.000 [0.000, 0.000]	0.338 [0.320, 0.355]	0.828 [0.806, 0.850]

Appendix

Table 7: Case-bootstrap intervals for the node- and context-level cells of the main-results table. “–” denotes a method-inapplicable metric.

Method	Q1 Accuracy	Q2 Accuracy	Q3 Accuracy	Final Accuracy	Stale Reuse
Vector RAG	0.950 [0.900, 0.990]	0.280 [0.190, 0.370]	1.000 [1.000, 1.000]	0.743 [0.710, 0.777]	0.100 [0.070, 0.133]
Recency-RAG	1.000 [1.000, 1.000]	0.390 [0.290, 0.490]	0.950 [0.900, 0.990]	0.780 [0.743, 0.817]	0.040 [0.020, 0.063]
LLM-Only Update	1.000 [1.000, 1.000]	0.470 [0.370, 0.570]	0.420 [0.320, 0.520]	0.630 [0.580, 0.680]	0.027 [0.010, 0.047]
CUPMem-style	0.970 [0.930, 1.000]	0.430 [0.330, 0.530]	1.000 [1.000, 1.000]	0.800 [0.767, 0.837]	0.033 [0.013, 0.057]
A-MEM-style	1.000 [1.000, 1.000]	0.710 [0.620, 0.800]	1.000 [1.000, 1.000]	0.903 [0.873, 0.933]	0.003 [0.000, 0.010]
PACMI	1.000 [1.000, 1.000]	0.970 [0.930, 1.000]	1.000 [1.000, 1.000]	0.990 [0.977, 1.000]	0.000 [0.000, 0.000]

Appendix

Table 8: Case-bootstrap intervals for the query-type and answer-level cells of the main-results table.

Variant	Affected Recall	Under-Invalidation	Stale-in-Context	Final Accuracy	Premise Resistance	Historical Preservation
PACMI	1.000 [1.000, 1.000]	0.000 [0.000, 0.000]	0.338 [0.320, 0.355]	0.990 [0.977, 1.000]	1.000 [1.000, 1.000]	1.000 [1.000, 1.000]
w/o Provenance Graph	0.000 [0.000, 0.000]	1.000 [1.000, 1.000]	0.369 [0.351, 0.387]	0.970 [0.950, 0.987]	0.980 [0.950, 1.000]	1.000 [1.000, 1.000]
w/o Cascading Invalidation	0.000 [0.000, 0.000]	1.000 [1.000, 1.000]	0.413 [0.399, 0.426]	0.963 [0.940, 0.983]	0.980 [0.950, 1.000]	0.990 [0.970, 1.000]
w/o Validity States	1.000 [1.000, 1.000]	0.000 [0.000, 0.000]	0.561 [0.549, 0.572]	0.970 [0.947, 0.990]	0.980 [0.950, 1.000]	1.000 [1.000, 1.000]
w/o Premise Checking	1.000 [1.000, 1.000]	0.000 [0.000, 0.000]	0.338 [0.320, 0.355]	0.833 [0.800, 0.867]	0.800 [0.720, 0.870]	1.000 [1.000, 1.000]
w/o Historical Preservation	1.000 [1.000, 1.000]	0.000 [0.000, 0.000]	0.200 [0.200, 0.200]	0.767 [0.733, 0.800]	0.990 [0.970, 1.000]	0.360 [0.270, 0.460]

Appendix

Table 9: Case-bootstrap intervals for all numeric cells of the ablation table.

Comparison	Scope	Errors	Discordant	Exact $p$	$p<0.05$
PACMI vs A-MEM-style	Q1+Q2+Q3	3 / 29	29 / 3	$2.55601\times 10^{-6}$	yes
PACMI vs w/o Cascading Invalidation	Q1+Q2+Q3	3 / 11	11 / 3	0.057373	no
PACMI vs w/o Premise Checking	Q2	3 / 50	48 / 1	$1.77636\times 10^{-13}$	yes

Appendix

Table 10: Two-sided exact McNemar tests for the three reported paired comparisons. Discordant counts are reported as PACMI-only correct / comparison-method-only correct.

Method	New-Evidence Coverage
Vector RAG	0.843
Recency-RAG	1.000
LLM-Only Update	0.863
CUPMem-style	1.000
A-MEM-style	1.000
PACMI	0.987

Appendix

Table 11: New-Evidence Coverage by main method.

Ablation	Implementation
w/o provenance graph	Disables the use of incoming dependency edges for distinguishing directly replaced memories from downstream dependency records and disables all graph propagation. Relation classification, deterministic consistency constraints, direct stale detection, and direct-state assignment remain enabled.
w/o cascading invalidation	Retains the graph and direct stale-memory detection but disables traversal from directly stale nodes to downstream dependent nodes.
w/o validity states	Removes validity-state filtering, state-dependent ranking biases, and validity-state labels from the retrieved context. Other query-time ranking signals remain unchanged.
w/o premise checking	Skips premise detection and always uses the neutral answer-generation prompt.
w/o historical preservation	Excludes superseded and historical-only prior memories from retrieval, including for historical queries.

Appendix

Table 12: Implementation of the PACMI ablations.

Variant	Aff. Rec. $\uparrow$	Under-Inv. $\downarrow$	SIC $\downarrow$	New-Ev. Cov. $\uparrow$
PACMI	1.00	0.00	0.34	0.99
w/o Provenance Graph	0.00	1.00	0.37	0.99
w/o Cascading Invalidation	0.00	1.00	0.41	0.99
w/o Validity States	1.00	0.00	0.56	0.96
w/o Premise Checking	1.00	0.00	0.34	0.99
w/o Historical Preservation	1.00	0.00	0.20	1.00

Appendix

Table 13: State- and context-level ablation results for PACMI. Higher is better for Affected Recall and New-Evidence Coverage; lower is better for Over-Invalidation, Under-Invalidation, and Stale-in-Context. Per assumption A3, the Affected Recall and Under-Invalidation columns verify propagation correctness rather than comparative advantage.

Variant	Final Acc. $\uparrow$	Stale Reuse $\downarrow$	Premise Resist. $\uparrow$
PACMI	0.99	0.00	1.00
w/o Provenance Graph	0.97	0.01	0.98
w/o Cascading Invalidation	0.96	0.01	0.98
w/o Validity States	0.97	0.02	0.98
w/o Premise Checking	0.83	0.02	0.80
w/o Historical Preservation	0.77	0.00	0.99

Appendix

Table 14: Answer-level ablation results for PACMI. Higher is better except for stale memory reuse.

Variant	Current	Stale Premise	Historical
PACMI	1.00	0.97	1.00
w/o Provenance Graph	1.00	0.91	1.00
w/o Cascading Invalidation	0.99	0.91	0.99
w/o Validity States	0.97	0.94	1.00
w/o Premise Checking	1.00	0.50	1.00
w/o Historical Preservation	1.00	0.94	0.36

Appendix

Table 15: Ablation results for PACMI: final-answer accuracy by query type.

Variant	Recall@Depth-1 $\uparrow$	Recall@Depth-2 $\uparrow$
PACMI	1.00	1.00
w/o Provenance Graph	0.00	0.00
w/o Cascading Invalidation	0.00	0.00
w/o Validity States	1.00	1.00
w/o Premise Checking	1.00	1.00
w/o Historical Preservation	1.00	1.00

Appendix

Table 16: Affected-node recall at each dependency depth. Variants without graph propagation miss downstream affected nodes at both depths. As with Affected Recall, these figures verify propagation correctness under assumption A3.

Explore similar work

STALE: Can LLM Agents Know When Their Memories Are No Longer Valid?
May 7, 2026Hanxiang Chao, Yihan Bai, Rui Sheng +2Agentic Memory Gradient Staleness
Wuhan University1, Wuhan, China1 · The Hong Kong University of Science and Technology3, Hong Kong, China23 · The Chinese University of Hong Kong2, Hong Kong, China23
Infini Memory: Maintainable Topic Documents for Long-Term LLM Agent Memory
Jun 9, 2026Suozhao Ji, Baodong Wu, Zehao Wang +8Long-Term Agent Memory Long-Term Memory
1Infinigence AI · 2Tsinghua University · 3Shanghai Jiaotong University
Memory Provenance Laundering in LLM Agents: A Non-Amplification Firewall for Persistent Memory
Jul 31, 2026Jinghan Xu, Yiyong Xiao, Wanru Shao +2Semantic Memory Large Language Model Agents

May 7, 2026, cs.CLJ/K move · Enter open · S save

STALE: Can LLM Agents Know When Their Memories Are No Longer Valid?

Hanxiang Chao, Yihan Bai, Rui Sheng, Tianle Li+1

Wuhan University1, Wuhan, China1 · The Hong Kong University of Science and Technology3, Hong Kong, China23 · The Chinese University of Hong Kong2, Hong Kong, China23

Agentic Memory Gradient Staleness Large Language Model Agents

Open paper AskPDF arXiv

Large Language Model (LLM) agents are increasingly expected to maintain coherent, long-term personalized memory, yet current benchmarks primarily measure static fact retrieval, overlooking the ability to revise stored beliefs when new evidence emerges. We identify a critical and underexplored failure mode, Implicit Conflict: a later observation invalidates an earlier memory without explicit negation, requiring contextual inference and commonsense reasoning to detect. To rigorously evaluate this capability, we introduce STALE, a benchmark of 400 expert-validated conflict scenarios (1,200 evaluation queries across three probing dimensions) spanning over 100 everyday topics with contexts up to 150K tokens. We propose a three-dimensional probing framework that tests State Resolution (detecting that a prior belief is outdated), Premise Resistance (rejecting queries that falsely presuppose a stale state), and Implicit Policy Adaptation (proactively applying updated states in downstream behavior). A systematic evaluation of frontier LLMs and specialized memory frameworks reveals a pervasive gap between retrieving updated evidence and acting on it, with even the best evaluated model achieving only 55.2% overall accuracy. Models often accept outdated assumptions embedded in a user's query, and they struggle to recognize when a change in one aspect of the user's state should invalidate related memories. To establish an initial baseline for state-aware memory, we further present CUPMem, a prototype that strengthens write-time revision through structured state consolidation and propagation-aware search, suggesting that explicit state adjudication is a promising direction for robust agentic memory.

Abstract

Explore similar work

STALE: Can LLM Agents Know When Their Memories Are No Longer Valid?

Infini Memory: Maintainable Topic Documents for Long-Term LLM Agent Memory

Memory Provenance Laundering in LLM Agents: A Non-Amplification Firewall for Persistent Memory