cs.CLOct 18, 2026

Memories That Outlive Their Reasons: Dependency-Tethered Memory for Tool-Using LLM Agents

Authors: Yiqi Wang, Jinqian Ju, Jiaqi Zhang, Zhangkai Wu, Yiqun Duan, Zequn Sun, Taotao Cai, Mingkai Zheng

Organizations: University of Southern Queensland Australia · Southern University of Science and Technology China · Jiangsu University China · The University of Sydney Australia · 

Read PDF
Ask AI
Cite

Copy citation

DOINot available for this paper

Abstract

Agents now act on the Web, publishing packages, models and datasets through registry APIs, and remembering past verifications spares them the work. But a verdict rests on premises. When a signing key is revoked, everything built on it stops passing, yet the advisory names only the key, and the old verdicts of its dependents may never share a retrieval window with it. This non-locality of invalidation turns memory into a liability: in long simulated chats, an agent reading a memory of atomic facts publishes 62% of the objects whose failure lies upstream, each backed by a record that was true when written. Yet derivation is local even when invalidation is not. Tether records, at write time, the exact versions each verdict derives from, and at read time withdraws any verdict whose support has failed anywhere in the store; the agent reads the same fields as before. On Fallout, a generator of versioned worlds with hypothesis-blind simulated histories shared by every memory, Tether publishes 0.3% of upstream-failing objects across three domains when relations are stated with their verdicts, with 37% fewer verification calls than checking everything. A-Mem and Graphiti re-verify most candidates (0.83--0.86 checks per candidate), which limits their savings, yet publish 9% of upstream-failing objects; Mem0 relies on memory more and publishes 42%. Flushing every verdict on any failure is as safe as Tether but costs 32% more checks. The gain over fact memory holds with three open-weight backbones, a whole-store window and real Go advisories. These gains depend on capturing dependencies: when relations arrive in sessions apart from their verdicts, Tether's downstream unsafe publication rate rises to 9.4--22.1%. It also degrades with weaker writers that miss dependencies or invalidation events.

Figures & tables

Figure 1. A failure that no single record contains, from a Fallout history. (a) The chain from grouse v2 to onyx v4 is stated once, in session 1; the advisory in session 23 names only the root, the request in session 29 only the leaf, so the request’s window holds grouse ’s passing verdict and nothing about onyx . Tether stores the chain as derived_from edges. (b) A fact memory (Flat) serves the stored verdict and the agent publishes a failing object. Tether serves it as unsettled ( null , shown ?) because its edges reach the failure; the agent checks and holds it. Left: a timeline of sessions 1, 23 and 29, separated by 21 and 5 sessions, with chat bubbles: the user pastes an SBOM stating grouse v2, aspen v3 and onyx v4, and the assistant checks all three as passing; an advisory in passing revokes onyx v4; a live request asks to publish grouse v2. Below the timeline the memory: grouse v2 and aspen v3 passing from session 1, onyx v4 failing from session 23; the request's window holds only grouse v2. Right: Flat shows grouse v2 as passing and the agent publishes it, which is unsafe; Tether shows it with a question mark, because its stored edges reach onyx, and the agent checks and holds it.
Figure 2. Fallout ’s evaluation pipeline with Tether . (a) Each history is recorded once by an agent without memory and shared by every memory under test. (b) After each session a bounded writer updates the store from the transcript and kk retrieved records; Tether ’s writer adds derived_from edges. (c) For a live request Flat and Tether retrieve the same window (dashed box) and serve the same fields; Tether withdraws, over the whole store, any passing verdict whose support has failed or has a higher version on record, and serves it as null (?). Three panels. (a) Record each history once: a scripted user blind to the hypothesis talks to an agent without memory that uses the tools items_list, item_check (pass or fail only) and item_act; the transcripts become shared logs. (b) Write dependencies: the k retrieved records and the session go into one writer call, which adds, updates or removes records in a store of exact-version checks on grouse v2, aspen v3 and onyx v4, linked by derived-from edges from grouse v2 to aspen v3 to onyx v4. (c) Withdraw globally: a live request to publish grouse v2 retrieves a window holding grouse v2; in the whole memory store grouse v2 derives from aspen v3, which derives from failed onyx v4, at distances 2, 1 and 0; withdrawal follows the edges back from onyx v4 when any ancestor is false, null or has a higher version on record. Flat serves grouse v2 as passing, Tether with a question mark, to the live agent.
Figure 3. Fallout -Mixed (reuse). (a) Unsafe publications by distance to the failure: with Flat the agent publishes most failing objects once the failure is upstream (shaded), with Mem0 39–48%, with Tether almost none. (b) Safety against cost. The dashed curve is every random mixture of Flat and always-verify; Tether lies far below it, A-Mem and Graphiti only slightly below and near always-verify’s cost, Mem0 above; hollow squares are global and mention flush over Flat’s stores. The unsafe axis is square-root scaled to separate the safe end. Left: line chart of unsafe publication rate over six strata (before, unaffected, d=0, d=1, d=2, d>=3); Flat rises to 0.55-0.71 at d>=1, Tether stays at or below 0.022, A-Mem and Graphiti between 0.06 and 0.13 at d>=1, Mem0 0.17 at d=0 and 0.39-0.48 at d>=1. Right: scatter of unsafe rate (square-root scale) against checks per candidate: Flat (0.27, 0.293), Mem0 (0.50, 0.227) above the mixing curve; Tether (0.63, 0.005) far below it; Graphiti (0.83, 0.053) and A-Mem (0.86, 0.043) slightly below; always-verify (1.00, 0); global flush (0.83, 0.001) and mention flush (0.53, 0.156) as hollow squares.
 unsafe by distance ddunsafeverification cost 
memoryd=0d{=}0d=1d{=}1d=2d{=}2d≥3d{\geq}3d≥1d{\geq}1allunaffectedallper requestΔ\Delta unsafe vs Tether
Always-verify.000.000.000.000.000.0001.011.004.05−.005-.005 [-.010, -.001]
Flat ( Tether without edges).012.552.615.708.619.293.17.271.08+.288+.288 [.267, .309]
A-Mem.008.059.087.128.089.043.86.863.45+.038+.038 [.026, .051]
Graphiti.067.087.073.105.087.053.85.833.35+.048+.048 [.035, .063]
Mem0.167.402.392.483.422.227.41.502.01+.222+.222 [.199, .246]
Table 1. Main results on Fallout -Mixed under the reuse condition (2,903 candidates per memory, 720 requests). Unsafe is the share of candidates published while failing; checks are per candidate unless noted. The Δ\Delta column gives the difference to Tether with 95% cluster-bootstrap CIs. Missed publications are at most 0.1% of candidates for every memory.
backbonememoryd=0d{=}0d≥1d{\geq}1allchk
gpt-6-lunaFlat.012.619.293.27
 Tether.022.003.005.63
Qwen3.5-27BFlat.063.838.405.13
 Tether.084.114.069.49
Qwen3.5-35B-A3BFlat.088.776.380.21
 Tether.244.301.184.47
Table 2. Other backbones on Fallout -Mixed (reuse, 2,903 candidates each), the same model writing memory and acting on it: unsafe rate at d=0d{=}0 , at d≥1d{\geq}1 and overall, and checks per candidate. A-Mem, Graphiti and Mem0 run on the last two. Graphiti with DeepSeek-V4.1-Flash covers 706 of 720 requests (2,848 candidates): in two worlds the model returned the JSON schema, stopping Graphiti’s build.
 reuseforced
memorysamebeforeafterchksamebeforeafterchk
Flat.575.589.625.33.880.822.827.24
A-Mem.018.028.019.96.419.333.356.62
Graphiti.030.028.029.92.180.222.452.74
Tether.006.094.221.63.012.139.269.64
Table 3. Relations stated in the session that verifies them ( same ), or in one of their own, a verification earlier ( before ) or two later ( after ), on Fallout -Split (959 candidates, 451 at d≥1d\geq 1 ): unsafe rate at d≥1d\geq 1 ; checks per candidate in families with dependencies. Tether ’s edge recall is 1.000, .840 and .658, at precision 1.000.
More in this topic

LLM Agent Memory

Large language model agent memory lets agents retain, organize, retrieve, and update information across interactions and long-running tasks.

See all 373 papers

Explore similar work

CardsList
Aug 22, 2026

MemGuard: Persisting Verifier Signals for LLM-Agent Memory Governance

LLM agents are moving from single-prompt use to long task streams in which reusable memory becomes a core capability for terminal, software-engineering, and web tasks. Such memory is useful only when stored experience remains reliable across hundreds of interactions, but two failure modes break that assumption in practice. The first is unreliable admission: failed trajectories,accidental successes, and misleading observations enter memory because they appear relevant, then mislead later decisions. The second is memory drift: long-running banks accumulate duplicate, stale, and conflicting records that retrieval alone cannot repair. MemGuard's key distinction is to treat verifier output not as a one-shot filter, but as persistent lifecycle metadata. It converts multi-criteria score-token verification into reward, confidence, label, and uncertainty descriptors that are attached to every candidate before activation and reused during retrieval, conflict resolution, summarization, and archival. We evaluate MemGuard on Terminal-Bench 2.0, SWE-Bench Verified, WebArena, and Mind2Web across four backbones, comparing against four memory baselines plus a verifier-only control under matched runtime budgets. Averaged over five seeds, MemGuard achieves the best success metric and lowest average steps in all 16 backbone-benchmark settings, improving over ReasoningBank, the strongest prior baseline among the memory methods we evaluate, with a largest gain of 7.9 success-rate points on WebArena, 5.6 step-success-rate points on Mind2Web, and 2.4-3.5 points on terminal and software-engineering benchmarks. Code is available at https://github.com/whyyyyy123/MemGuard.

Haoyu Wang, Guangyuan Dong, He Liang +5

Nankai University · National University of Singapore · Shanghai Institute of Optics and Fine Mechanics, Chinese Academy of Sciences +5

Persistent Memory for Language ModelsAgent Memory ManagementLLM Agent Reliability
AskPDF
Oct 13, 2026

Many Steps into One: Reasoning Contraction and the Limits of Safe Memory Reuse for LLM Agents

Thought templates, skill libraries, agent memories and caches turn many reasoning steps into one. We call this reasoning contraction. A contracted memory saves reasoning steps and errors until its facts change, then quietly answers wrong. Most systems trust memories by counting successes and failures. We prove that such counters are badly tuned change detectors: a symmetric counter notices a partial change only after a power of its false-alarm horizon, and an unclipped one may never notice it. On five LLMs answering multi-hop questions over edited facts, ExpeL- and ACE-style counters serve 7.0-13.5x more stale answers than certified memories given the same information, and on code tasks with an exact verifier 35-73x more. Safety also has a price. When facts change and each memory is judged only by its own verified outcomes, one number, the certification load, sets how much reasoning any safe memory can skip, and under Zipf demand it yields a scaling law. Our recipe weighs each memory's failures by its own likelihood ratio, certifies its utility against live reasoning, and restarts the certificate when facts change, with the likelihood-ratio detector as the safety net for unannounced changes; for large edits it also invalidates the memory.

Jianghong Zhou, Hao Rong, Chen Lin +1

1ByteDance · 2Scale AI

Agent Memory ManagementLLM Agent SafetyChange-Point Detection
AskPDF
Aug 7, 2026

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.

LLM Agent MemoryPersistent Memory for Language ModelsAgent Memory Management
AskPDF