TRACE: Governing Memory Validity in Evolving Multi-Agent Systems

Wenjun Xiong; Shengtao Zhang; Shangding Gu; Bo Tang; Zhiyu Li; Feiyu Xiong; Ying Wen; Muning Wen

cs.MASep 27, 2026

TRACE: Governing Memory Validity in Evolving Multi-Agent Systems

Authors: Wenjun Xiong, Shengtao Zhang, Shangding Gu, Bo Tang, Zhiyu Li, Feiyu Xiong, Ying Wen, Muning Wen

Organizations: Shanghai Jiao Tong University · MemTensor(Shanghai) Technology Co., Ltd. · UC Berkeley · Shanghai Innovation Institute

Abstract

Persistent memory lets language-model agents carry information across long-running collaborations, but leaves a lifecycle question open: what may a returning agent still act on once the shared state has changed? A memory can be correctly retrieved, relevant to the current task, and faithful to its source, and nonetheless be inadmissible for action: an itinerary saved before a pause still names the hotel the team has since replaced. We formalize this as temporal memory admission and present TRACE, a training-free layer that treats re-entry as an eligibility decision rather than a storage or retrieval operation, reconciling a departure checkpoint against absence-period updates, resolving explicit and implicit invalidation, and releasing a bounded Return View only when it covers the returning role's open obligations. We evaluate TRACE under three actor models on Memora, STALE Type II, and a derived ManBench-Return setting, each recast as return episodes: one agent departs, four teammates change the shared state, and the agent rejoins. What separates methods is not overall accuracy but whether one can retain valid memory and reject stale memory at once, and no single-policy baseline can: Restore (reinstate the departure checkpoint in full) admits stale state, Reset (start the return from an empty memory) discards valid state, each bottoming out at 0% on one of the two. TRACE is the only method high on both, reaching 92.6-98.3% valid-information availability with 98.4-99.5% invalid-information rejection on ManBench-Return, within 3.8 points of the best baseline's overall accuracy. On STALE Type II it improves Overall over the strongest comparison policy by 22.3 (Qwen), 18.5 (Gemini), and 27.5 (DeepSeek) points at roughly 2.3 times their tokens, while a write-time consolidation pipeline is more accurate still at 3.99 times TRACE's.

Figures & tables

Figure 1: The agent-return dilemma under context evolution. A1 leaves with a coherent travel plan. During its absence, the team replaces the hotel booking, changes the train schedule, and leaves the pickup time unresolved. When A1 returns, its stored itinerary is still relevant and was correct when recorded, yet parts of it are no longer admissible for action.

Figure 2: TRACE at an authenticated return boundary. The system captures one immutable departure-and-delta view, validates candidate items, selects a budgeted set that covers current obligations, and signs a Return View. Private experience is readmitted only when its bound source state survives.

		Memora			STALE Type II			ManBench-Return
Model	Method	Overall $\uparrow$	VIA $\uparrow$	IIR $\uparrow$	Overall $\uparrow$	VIA $\uparrow$	IIR $\uparrow$	Overall $\uparrow$	VIA $\uparrow$	IIR $\uparrow$
Qwen3.5-122B-A10B	Static	63.16	55.39	68.13	28.33	35.00	22.33	84.38	50.00	50.00
	Restore	65.11	42.11	82.24	5.75	14.00	1.00	95.05	50.00	50.00
	Reset	72.40	38.88	99.93	15.83	12.50	3.00	96.38	0.00	100.00
	MemStrata	66.10	55.53	73.02	28.66	32.00	22.50	84.43	50.00	50.00
	MemTX	66.21	55.62	73.57	30.00	33.50	23.50	84.84	50.00	50.00

Table 1: Main comparison across three return benchmarks (%). Overall denotes benchmark-specific overall accuracy (Section 4.3 ). Memora averages the three departure conditions; ManBench-Return averages Old-Valid and Old-Stale using unrounded condition scores. STALE aggregation follows Appendix D.4 . Bold marks the best value within each actor and metric.

Method	Overall $\uparrow$	PR $\uparrow$	IPA $\uparrow$
Static	33.33	26.67	45.00
MemStrata	31.11	36.67	35.00
MemTX	30.00	35.00	33.33
CUPMem	80.56	85.00	75.00
TRACE (Ours)	58.89	55.00	60.00

Table 2: Accuracy and token cost on the STALE Type II subset. Left: Overall (the mean of SR, PR, and IPA) and two native probe accuracies (%), with column maxima in bold. Right: LS versus tokens per episode, with a magnified baseline cluster. All methods are scored over the same 20 planned episodes per bucket; one CUPMem episode exceeded the serving context window and is scored as a failure on all three probes.

Agent	Method	Overall $\uparrow$	VIA $\uparrow$	IIR $\uparrow$
4	Static	77.20	44.26	44.26
4	TRACE	96.19	96.88	98.94
8	Static	76.61	44.20	44.20
8	TRACE	96.04	96.63	98.72
16	Static	76.06	44.23	44.23
16	TRACE	96.21	96.92	98.88

Table 3: ManBench-Return agent-scale diagnostic (%). One agent returns while the number of active agents varies.

Agent	Method	Overall $\uparrow$	VIA $\uparrow$	IIR $\uparrow$
4	Static	77.20	44.26	44.26
4	TRACE	96.19	96.88	98.94
8	Static	76.61	44.20	44.20
8	TRACE	96.04	96.63	98.72
16	Static	76.06	44.23	44.23
16	TRACE	96.21	96.92	98.88

Table 3: ManBench-Return agent-scale diagnostic (%). One agent returns while the number of active agents varies.

Appendix figures & tables14 assets

Supplementary material from the paper’s appendix.

Appendix

Benchmark	Parameter	Value
Memora	Departure fraction	25%, 50%, 75%
	Answer / state-prediction budget	2,048 / 4,096 tokens
	Retrieval: predeparture / absence	10 / 14 sessions
	Recency window: predeparture / absence	2 / 4 sessions
	State-prediction batch size	At most 6 sessions
	Selected-fact budget	12 initially; at most 16

Appendix

Table 4: Experimental parameter settings. Generation budgets are maximum output tokens per call. Predeparture and absence denote the two history segments used in Memora; the STALE departure strata use zero-based session indices.

Departure	Method	Overall $\uparrow$	VIA $\uparrow$	IIR $\uparrow$	FAMA $\uparrow$
25%	Static	62.10	53.91	67.94	37.88
	Restore	65.74	41.12	85.16	34.46
	Reset	72.47	39.19	99.90	39.19
	MemStrata	65.55	54.22	73.68	40.87
	MemTX	65.38	54.72	73.46	41.15
	TRACE	63.98	52.35	70.18	38.75

Appendix

Table 5: Qwen on Memora at three departure points (%). Average is the equal-weight macro-average of the three conditions. Bold marks the best reported value among the six methods in each complete block.

Bucket	Method	Overall $\uparrow$	Dim1 $\uparrow$	Dim2 $\uparrow$	VIA / Dim3 $\uparrow$	IIR $\uparrow$	LS $\uparrow$
Early	Static	35.94	32.81	32.81	42.19	28.12	21.88
	Restore	5.73	1.56	1.56	14.06	1.56	0.00
	Reset	17.19	3.12	39.06	9.38	3.12	0.00
	TRACE	64.06	65.62	68.75	57.81	65.62	48.44
Middle	Static	24.48	21.88	21.88	29.69	18.75	12.50
	Restore	6.25	1.56	3.12	14.06	0.00	0.00

Appendix

Table 6: Qwen on STALE Type II (%). Early, Middle, and Late contain 64, 64, and 72 episodes, respectively, and every episode is retained, so all four blocks report the full sample. Pooled averages the 200 episodes with each bucket weighted by its episode count. MemStrata and MemTX results for Early, Middle, and Late buckets are omitted due to data inconsistencies; only Pooled results are reported. Bold marks the best reported value among the six methods in each block.

Bucket	Method	Overall $\uparrow$	Dim1 $\uparrow$	Dim2 $\uparrow$	VIA / Dim3 $\uparrow$	IIR $\uparrow$	LS $\uparrow$	Tokens/episode $\downarrow$
Early	Static	36.67	30.00	25.00	55.00	20.00	15.00	219,855
	MemStrata	23.33	10.00	25.00	35.00	10.00	5.00	218,115
	MemTX	23.33	15.00	20.00	35.00	10.00	5.00	217,662
	CUPMem	81.67	80.00	85.00	80.00	80.00	70.00	2,127,613
	TRACE (Ours)	73.33	80.00	60.00	80.00	60.00	55.00	316,750
Middle	Static	36.67	30.00	35.00	45.00	30.00	15.00	215,073

Appendix

Table 7: Qwen on the STALE Type II subset by departure bucket. Accuracy and joint metrics are percentages. Aggregate reproduces each method’s reported summary. Every method is scored over the same 20 planned episodes per bucket, including one CUPMem episode that could not complete and is scored as a failure on all three probes (see the note above); its retry cost is included in the token column. Bold marks the highest score within each block; bold token counts highlight CUPMem’s higher cost.

Condition	Method	Overall $\uparrow$	VIA $\uparrow$	IIR $\uparrow$	WSAR $\downarrow$	RSR $\downarrow$
Old-Valid	Static	70.06	0.00	0.00	100.00	29.94
	Restore	96.30	100.00	100.00	0.00	3.70
	Reset	95.75	0.00	100.00	0.00	4.25
	MemStrata	70.25	0.00	0.00	100.00	29.75
	MemTX	70.86	0.00	0.00	100.00	29.14
	TRACE	93.37	95.75	97.57	2.43	6.63

Appendix

Table 8: Qwen on ManBench-Return (%). Average gives equal weight to Old-Valid and Old-Stale using unrounded condition scores; displayed condition values may not reproduce the final decimal. Overall measures final answer correctness; RSR applies only to Old-Valid. Bold marks the best reported value among the six methods in each complete block.

Departure	Method	Overall $\uparrow$	VIA $\uparrow$	IIR $\uparrow$	FAMA $\uparrow$
25%	Static	66.50	52.62	75.50	40.58
	Restore	67.62	43.63	85.96	37.23
	Reset	71.71	43.44	95.04	41.48
	MemStrata	67.95	53.47	76.95	42.37
	MemTX	68.12	53.56	76.97	42.53
	TRACE	64.93	51.11	73.31	38.42

Appendix

Table 9: Gemini on Memora at three departure points (%). Average is the equal-weight macro-average of the three conditions. Bold marks the best reported value among the six methods in each complete block.

Bucket	Method	Overall $\uparrow$	Dim1 $\uparrow$	Dim2 $\uparrow$	VIA / Dim3 $\uparrow$	IIR $\uparrow$	LS $\uparrow$
Early	Static	78.13	73.44	78.13	82.81	71.88	64.06
	Restore	9.90	0.00	6.25	23.44	0.00	0.00
	Reset	8.33	0.00	6.25	18.75	0.00	0.00
	TRACE	91.15	92.19	92.19	89.06	92.19	87.50
Middle	Static	70.31	70.31	64.06	76.56	62.50	60.94
	Restore	8.33	1.56	3.13	20.31	1.56	1.56

Appendix

Table 10: Gemini on STALE Type II (%). Early, Middle, and Late contain 64, 64, and 72 episodes, respectively. Average gives equal weight to the three buckets. MemStrata and MemTX results for Early, Middle, and Late buckets are omitted due to data inconsistencies; only Average results are reported. Bold marks the best reported value among the six methods in each block.

Condition	Method	Overall $\uparrow$	VIA $\uparrow$	IIR $\uparrow$	WSAR $\downarrow$
Old-Valid	Static	76.19	0.00	0.00	100.00
	Restore	99.75	100.00	100.00	0.00
	Reset	97.34	0.00	100.00	0.00
	MemStrata	73.71	0.00	0.00	100.00
	MemTX	73.35	0.00	0.00	100.00
	TRACE	97.84	97.89	98.95	1.05

Appendix

Table 11: Gemini on ManBench-Return (%). Average gives equal weight to Old-Valid and Old-Stale using unrounded condition scores; displayed condition values may not reproduce the final decimal. Overall measures final-answer correctness. Bold marks the best value among the six methods in each block.

Departure	Method	Overall $\uparrow$	VIA $\uparrow$	IIR $\uparrow$	FAMA $\uparrow$
25%	Static	66.66	49.88	78.02	39.72
	Restore	69.22	41.02	91.77	37.57
	Reset	72.52	40.39	99.19	39.95
	MemStrata	68.43	51.78	79.54	42.24
	MemTX	68.69	52.39	79.64	42.66
	TRACE	67.83	50.71	79.67	40.77

Appendix

Table 12: DeepSeek on Memora at three departure points (%). Average is the equal-weight macro-average of the three conditions. Bold marks the best reported value among the six methods in each block.

Bucket	Method	Overall $\uparrow$	Dim1 $\uparrow$	Dim2 $\uparrow$	VIA / Dim3 $\uparrow$	IIR $\uparrow$	LS $\uparrow$
Early	Static	25.00	17.19	17.19	40.63	12.50	12.50
	Restore	6.25	0.00	3.13	15.63	0.00	0.00
	Reset	13.02	0.00	14.06	25.00	0.00	0.00
	TRACE	71.88	76.56	70.31	68.75	70.31	59.38
Middle	Static	24.48	20.31	20.31	32.81	15.63	9.38
	Restore	6.25	0.00	1.56	17.19	0.00	0.00

Appendix

Table 13: DeepSeek on STALE Type II (%). Early, Middle, and Late contain 64, 64, and 72 episodes, respectively. Average gives equal weight to the three buckets. MemStrata and MemTX results for Early, Middle, and Late buckets are omitted due to data inconsistencies; only Average results are reported. Bold marks the best reported value among the six methods in each block.

Condition	Method	Overall $\uparrow$	VIA $\uparrow$	IIR $\uparrow$	WSAR $\downarrow$
Old-Valid	Static	31.06	0.00	0.00	100.00
	Restore	99.88	100.00	100.00	0.00
	Reset	95.39	0.00	100.00	0.00
	MemStrata	52.50	0.00	0.00	100.00
	MemTX	52.38	0.00	0.00	100.00
	TRACE	92.04	91.86	96.89	3.11

Appendix

Table 14: DeepSeek on ManBench-Return (%). Average gives equal weight to Old-Valid and Old-Stale using unrounded condition scores; displayed condition values may not reproduce the final decimal. Overall measures final answer correctness. Bold marks the best reported value among the six methods in each block.

Method	Overall $\uparrow$	VIA $\uparrow$	IIR $\uparrow$	LS $\uparrow$
Full TRACE	52.33	52.50	50.50	39.00
w/o II	26.50	34.00	19.50	18.00
w/o OAS	38.67	35.50	36.00	29.00
w/o CVG	47.33	48.00	44.00	35.00
w/o SBPR	42.00	43.00	38.50	31.00

Appendix

Table 15: Component ablations on STALE Type II with Qwen (%). Bold marks the highest score in each column. Each ablation removes one mechanism.

Method	Overall $\uparrow$	VIA $\uparrow$	IIR $\uparrow$	WSAR $\downarrow$
Static	76.51	44.24	44.24	55.76
TRACE	96.07	96.76	98.83	1.17

Appendix

Table 16: Macro-average across the four agent scales in Table 3 (%). WSAR is the complement of IIR in this admission diagnostic. Bold marks the better value in each column.

Backend	Method	VIA $\uparrow$	IIR $\uparrow$	FAMA $\uparrow$
ScopedMem	Static	55.04	67.77	39.13
ScopedMem	TRACE	52.01	74.19	39.31
Mem0	Static	53.53	68.93	37.81
Mem0	TRACE	53.48	70.06	38.29
Memobase	Static	54.54	67.94	38.52
Memobase	TRACE	53.19	68.33	37.17

Appendix

Table 17: Backend portability on Memora at 50% departure (%). Each Static/TRACE pair shares its backend, actor, and scorer. Bold marks the higher value within each pair.

Explore similar work

Aug 7, 2026cs.AI

TEPA: Revoking Stale Memories for Conflict-Robust Language Agents

Long-term memory enables language agents to reuse past facts, preferences, and task experience. Persistence also creates a central falsifiability problem: when the world changes, stale memories can remain retrievable and pollute the prompt. We characterize this failure mode as memory pollution: degradation caused by active memories that newer conflicting evidence has superseded. We introduce TEPA, a revocable evidence-memory mechanism that makes validity an explicit state of memory. TEPA represents observations as keyed precedents and revokes active precedents when fresh evidence contradicts them under the same key, allowing retrieval to draw from current evidence while preserving revoked history for audit. Across controlled hidden-regime drift, real file-backed executable drift, and preference-update streams, revocation prevents stale active memory from remaining in the retrieval set after reversal. In controlled drift over 50 seeds, append-only and last-write-wins memory fell below no memory during full reversal (append-only and last-write-wins both 0.210, no memory 0.309, TEPA 0.950), and the same pattern reproduced under real file execution (append-only 0.203, no memory 0.298, TEPA 0.950). On clean MemoryAgentBench SH-6k, TEPA matches a strong last-write-wins cache, confirming that current-key replacement is the decisive operation for single-hop fact consolidation. Boundary tests on multi-hop and very long-context MemoryAgentBench settings expose retrieval-chain and context-selection bottlenecks beyond fact-level validity tracking. Together, these results establish lifecycle revocation as a core memory operation for agents that must falsify, audit, and later re-promote evolving knowledge.

Yan Zhou, Yue Ouyang, Kaiyang Zheng +1

School of Mathematics and Statistics, Changsha University of Science and Technology, Changsha, China · School of Biomedical Engineering, Shanghai Jiao Tong University, Shanghai, China.

Long-Term Agent Memory Gradient Staleness Memoryagentbench Bottlenecks

Ask PDF

Aug 4, 2026cs.AI

TARL: Transaction-Aware Reliable Ledgers for Executable Memory Management in Long-Term Agents

Persistent memory helps long-term agents retain knowledge, yet a single update error can repeatedly distort future retrieval and reasoning. Most existing systems reduce memory updating to a binary Write/Hold decision, which cannot distinguish whether new information should be added, ignored, used to revise an outdated belief, rejected as unreliable, or deferred for verification. These choices may share the same binary label while producing fundamentally different memory states. We introduce TARL, a memory state update framework that maps each statement to one of five executable actions. TARL identifies the affected memory, resolves its temporal scope, compares source reliability, and updates accepted, pending, and rejected ledgers. It is further trained by comparing the memory states produced by alternative update operations, encouraging the model to select the operation that leads to the correct result. We also introduce TARL-Mem, a benchmark with fine-grained action labels and next-state targets. Across in-domain, cross-source, temporal, counterfactual, and sequential evaluations, TARL improves action prediction and state recovery, reduces memory pollution, preserves conflicting evidence, and limits cumulative corruption.

Han Xiao, Hongjun Xu, Xin Zhang +2

School of Informatics, Xiamen University

Long-Term Agent Memory Peak Memory Ledger Fine-Grained Actions

Ask PDF

Jul 12, 2026cs.AI

The Compliance Trap: Diagnosing How AI Agents Consume Conflicting Memory

Memory is becoming a core component of long-horizon AI agents, allowing agents to reuse past experience when operating web browsers, software tools, and other interactive environments. Existing work mostly treats memory as a supply problem, asking what experience to write, how to store it, and which entry to retrieve for the next task. Yet we still lack a clear account of how models consume retrieved memory across a multi-step action trajectory. This consumption process matters because it determines not only what memories should be retrieved, but also what models and control policies are needed to use them safely. To diagnose this process, we propose Entry--Propagation--Recovery (E-P-R), a trajectory-level framework that asks where memory first changes an action, whether that change carries forward, and whether the agent can recover after leaving a correct path. We instantiate E-P-R on WebArena and on MemTrapBench, a controlled benchmark we build to isolate these phases. We find that the main failure often begins at entry: agents adopt conflicting memory at the first exposed decision point even when it is task-wrong. Repeated exposure then amplifies this early error, while recovery after divergence is weak. Together, these effects create a compliance trap: across models, conflicting memory induces similar compliance rates, but once agents comply, their success rates collapse to a low floor. Stronger agents therefore suffer larger absolute damage because each compliance event erases more baseline capability. These results suggest that memory-augmented agents should be evaluated not only by retrieval quality or final success rate, but by how they consume memory throughout the trajectory.

Yixiong Chen, Xinyi Bai, Alan Yuille

1Johns Hopkins University · 2Cornell University

Artificial Intelligence Agents Compliance

Ask PDF