TRACE: Governing Memory Validity in Evolving Multi-Agent Systems

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. 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 a common five-agent return protocol on Memora, STALE Type II, and a derived ManBench-Return setting, under three ac- tor models. 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 admits stale state, reset 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 gains 18 to 28 points over the strongest memory-policy baseline at roughly 2.3× their tokens, while a write-time consolidation pipeline is more ac- curate still at 3.99× TRACE’s. On Memora, where updates are explicit, ordinary storage semantics suffice and TRACE offers no consistent gain.