PaperlayerView exact revision on arXiv

Source-linked AI summary

When Correct Memory Goes Wrong: Fuzzing Persistent Memory Use in LLM Agents

Yuqiao Meng, Luoxi Tang, Yingxue Zhang, Yuchen Yang, Zhaohan Xi

arXiv:2609.38275v1cs.DCcs.AI

TL;DR

Persistent memory can be correct yet misused as queries or memory states change, while existing work offers limited ways to search for such failures systematically. U-FUZZ fuzzes both kinds of changes and, across memory systems and benchmarks including hidden-retrieval settings, finds more failures than simpler baselines.

  • Problem

    Correct stored memory can still be used incorrectly as queries or memory states change, and existing work offers limited ways to search systematically for these failures.

    Source: §1 · p. 1

  • Method

    U-FUZZ starts from memory checkpoints, validates query and memory-state mutations, and uses observed behavior to guide iterative testing without failure labels directing search.

    Source: §1 · p. 2, §4.2 · p. 5

  • Results

    Across multiple memory systems and benchmarks, U-FUZZ uncovers more memory-use failures than simpler testing strategies and remains useful when retrieval is hidden.

    Source: §1 · pp. 2–3, §6 · p. 9

  • Takeaways & Limitations

    Reliable agent memory should be evaluated by how stored information is used under changing requests, not only by what is stored.

    Source: §1 · p. 1, §6 · p. 9

    The evaluation covers representative systems, benchmarks, and mutations rather than an exhaustive test space, and U-FUZZ does not diagnose internal causes or prescribe mitigations.

    Source: A LIMITATIONS AND SCOPE · p. 11

Abstract

from arXiv · show

Persistent memory helps LLM agents carry information across long interactions, but correct memory can still be used incorrectly when queries change or memory states evolve. Existing work mainly studies memory content errors or evaluates fixed test cases, leaving memory-use failures hard to discover systematically. We formulate this issue as a fuzzing problem and categorize such failures into query-related and memory-state failures. We then develop U-Fuzz, which starts from memory checkpoints as test seeds, mutates queries or memory states under explicit mutation obligations, validates each mutant, and uses observed memory behavior to guide iterative testing while keeping failure labels outside the search. We evaluate U-Fuzz across several memory systems against diverse fuzzing baselines, and further test an output-only setting with API-based LLMs where memory retrieval is hidden. Across these settings, U-Fuzz consistently uncovers more confirmed memory-use failures, showing that its search remains effective across different memory architectures and even when only final responses are observable.

1 INTRODUCTION

Persistent memory can be used incorrectly even when its stored content is correct, and existing work offers limited ways to search systematically for such failures. The introduction frames memory-use testing as fuzzing and presents U-FUZZ, which tests query and memory-state changes and finds failures across memory systems, including when retrieval is hidden.

1 INTRODUCTION

  • Existing work mainly studies stored-content reliability and provides limited ways to search actively for incorrect use of valid memory.Such failures can arise from ordinary requests or routine updates even when stored items are free of poisoning.Source: §1 · p. 1
  • Because many valid requests and memory states can produce different behavior, the paper frames failure discovery as fuzzing guided by observed behavior.It is difficult to know in advance which query or memory change will trigger a failure.Source: §1 · p. 1
  • Across diverse memory systems and benchmarks, U-FUZZ finds more unique memory-use failures than diverse baselines and continues finding failures when retrieval is hidden.The evaluation also finds that query and memory-state mutations expose complementary failures, while retrieval feedback helps broaden or refine exploration.Source: §1 · pp. 2–3
  • The paper distinguishes query-related failures, triggered by request changes, from memory-state failures, triggered by changes to stored memory.Examples include paraphrases retrieving different memories and updates leaving an older value in use.Source: §1 · pp. 1–2
  • U-FUZZ starts from memory checkpoints, validates query or memory-state mutants, and uses observed behavior to guide further testing without failure labels directing search.Its mutations cover query changes and controlled updates, deletions, or modifications to unrelated stored information.Source: §1 · p. 2

2 RELATED WORK

Prior work has expanded persistent-memory evaluation and documented reliability risks, but it largely relies on predefined histories, attacks, or test cases. Existing fuzzing and retrieval-aware testing provide related techniques, while generally targeting systems other than persistent agent memory with evolving queries and memory states.

Memory systems and evaluation

  • Memory evaluations cover recall, temporal and multi-session reasoning, updates, abstention, and forgetting, but remain largely tied to predefined histories and fixed test queries.The passage situates this work alongside episodic, structured, dynamically linked, and hierarchical memory systems (Chhikara et al., 2025).Source: §2 · p. 3

Reliability and security of agent memory

  • Reliability studies examine malicious, stale, or conflicting memory and establish that reliability depends on both stored content and subsequent use, but focus mainly on predefined cases or operations.Examples include poisoning and injection studies (Dong et al., 2025) and work on updates, forgetting, and error propagation (Wu et al., 2025; Hu et al., 2026; Xiong et al., 2026).Source: §2 · p. 3

Fuzzing and testing of LLM-based systems

  • Fuzzing and retrieval-aware testing use mutation and coverage to explore LLM-based systems, but primarily target software inputs, prompts, or document retrieval rather than evolving persistent agent memory.Retrieval-aware testing includes coverage criteria and metamorphic mutations for RAG behavior beyond fixed queries (Kim et al., 2026b;a).Source: §2 · p. 3

3 CATEGORIZATION OF MEMORY-USE FAILURES

The paper classifies memory-use failures by which input changes while the other remains fixed: the query or the memory state. This change-based distinction applies whether memory retrieval is explicit or hidden.

3 CATEGORIZATION OF MEMORY-USE FAILURES

  • Memory-use behavior denotes the information selected from memory and used to handle a request, which may be observed as retrieved memories, their ranking, or the response.The notation U(q, M) represents this behavior for query q and memory state M.Source: §3 · p. 3
  • Query-related failures occur when memory use violates the expected relation between queries while the memory state remains fixed.Expected behavior can include preserving relevant support for a paraphrase or avoiding unrelated memory for an unsupported request.Source: §3 · p. 3
  • Memory-state failures occur when memory use violates the expected relation between memory states while the query remains fixed.Relevant updates, deletions, or additions should be reflected in later use, while unrelated changes should not disturb it.Source: §3 · pp. 3–4
  • The categories distinguish failures by the change that triggers them, making the classification agnostic to how memory is integrated into an agent.It applies both to systems with explicit retrieval interfaces and to systems with hidden memory-use mechanisms.Source: §3 · p. 4

4 METHOD

U-FUZZ treats persistent memory use as a fuzzing target by making queries and evolving memory states first-class inputs. It seeds from memory checkpoints, validates mutations against explicit obligations, and uses observed behavior to guide later testing.

4 METHOD

  • U-FUZZ makes queries and evolving memory states first-class fuzzing inputs, generating and validating mutations before executing parent–mutant pairs and retaining useful mutants for later rounds.Failure detection is stored separately and does not guide seed retention or prioritization.Source: §4 · p. 4, §4.3 · p. 6

4.1 SEED INITIALIZATION

  • Seeds pair a checkpoint and query with a mutation descriptor for valid changes and a separate reference containing the expected answer and supporting or invalidated evidence.The mutation descriptor contains no expected answer; the reference is used for evaluation.Source: §4.1 · pp. 4–5

4.2 MUTATION

  • U-FUZZ mutates queries or controlled memory states under seed–operator–target obligations, validates mutants independently of retrieval results, and guarantees coverage only for represented operators and targets.Query changes include meaning-preserving, target-changing, and unsupported requests; memory changes include updates, deletions, and unrelated edits.Source: §4.2 · p. 5

4.3 FUZZING EXECUTION AND EVALUATION

  • Paired executions begin from independent copies of the parent checkpoint, preventing one test’s memory writes from affecting the other execution.When copying is unavailable, checkpoints are recreated in separate sessions.Source: §4.3 · p. 6
  • Failure checks compare parent–mutant behavior with operator-specific expectations, including wrong answers or support, unsupported factual answers, stale or deleted evidence, and changes after unrelated edits.For visible retrieval, missing valid evidence or invalid evidence ranked above it indicates a selection failure; incorrect responses despite valid retrieved evidence occur after selection.Source: §4.3 · p. 6
  • Visible-retrieval systems use coverage, novelty, and divergence feedback; hidden-retrieval systems retain mutants with unseen responses and report only end-to-end failures.Coverage and novelty determine retention for visible retrieval, while divergence further guides prioritization.Source: §4.3 · p. 6

5 EXPERIMENT

Across memory systems and benchmarks, U-FUZZ discovers more unique memory-use failures than baseline strategies, while query and memory-state mutations contribute differently across backends. Its mutation and feedback components complement one another, and it remains effective when retrieval is hidden.

5.1 RQ1: HOW EFFECTIVE IS U-FUZZ AT MEMORY-USE FAILURE DISCOVERY?

  • U-FUZZ consistently discovers more unique memory-use failures than baseline strategies across benchmarks and memory systems while maintaining comparable or stronger memory coverage.Table 1 reports performance under fixed budgets of 8,000 executions for LoCoMo and 4,000 for LongMemEval-S; results are means and standard deviations over three runs.Source: §5.1 · p. 7, Table 1 · p. 7
  • Query mutations work better on Mem0, A-Mem, and MemOS, whereas memory-state mutations are stronger on Graphiti, making the two search directions complementary.The relative importance of the mutation types depends on the backend.Source: §5.1 · p. 7

5.2 RQ2: HOW DOES FUZZING EFFECTIVENESS EVOLVE WITH THE EXECUTION BUDGET?

  • Query-only fuzzing starts faster but saturates earlier, while memory-state fuzzing starts slower and continues finding failures that query-only search cannot reach.Combining both mutation classes lets later rounds continue through one search direction when the other slows, helping avoid early saturation.Source: §5.2 · p. 8

5.3 RQ3: HOW DOES EACH COMPONENT OF U-FUZZ INFLUENCE TO ITS EFFECTIVENESS?

  • Removing any mutation operator reduces failure discovery, with target-changing contributing most among query mutations and update and deletion mattering more on Graphiti than Mem0.Meaning-preserving and unsupported mutations probe failure types that target changes do not capture; unrelated change has a smaller effect as a non-interference test.Source: §5.3 · pp. 8–9
  • Coverage drives broader exploration, while retrieval novelty and parent–mutant divergence help find distinct behaviors among already explored memories.Figure 4 reports changes in UF@B or Cov@B after removing mutation operators or search-feedback indicators.Source: Figure 4 · p. 8, §5.3 · p. 9

5.4 RQ4: DOES U-FUZZ REMAIN EFFECTIVE WHEN RETRIEVAL IS HIDDEN?

  • With retrieval hidden, U-FUZZ retains a consistent advantage across both memory systems and LLM backends, using response novelty as a weaker but useful signal for continuing mutants.Output-only feedback supports end-to-end failure discovery but loses retrieval-level localization: an incorrect response may reflect wrong retrieval or misuse of the right memory.Source: §5.4 · p. 9, Figure 5 · p. 9

6 CONCLUSION

The paper frames incorrect use of correct persistent memory as a reliability problem, and introduces U-FUZZ to search for such failures by mutating queries and memory states. Across multiple systems and benchmarks, it finds failures simpler strategies miss and remains useful when retrieval is hidden.

6 CONCLUSION

  • Across multiple memory systems and benchmarks, U-FUZZ uncovers memory-use failures that simpler testing strategies miss and remains useful when retrieval is hidden.The paper suggests memory reliability should be evaluated by how stored information is used under changing requests and evolving states, not only by what is stored.Source: §6 · p. 9
  • U-FUZZ formulates memory-use failure discovery as fuzzing and mutates both queries and memory states while validating cases and guiding exploration with observed execution behavior.Failure labels are kept outside the search.Source: §6 · p. 9
  • The reliability problem is that correct stored memory may still be used incorrectly as queries or memory states change.Source: §6 · p. 9

A LIMITATIONS AND SCOPE

The evaluation covers representative systems, benchmarks, and the defined query and memory-state mutations, but does not exhaust the test space. U-FUZZ discovers and localizes failures rather than diagnosing their causes or prescribing mitigations.

A LIMITATIONS AND SCOPE

  • The evaluation is limited to representative persistent-memory systems, benchmarks, and the query- and memory-state mutations defined in the work.Source: A LIMITATIONS AND SCOPE · p. 11
  • The explored test space is not exhaustive, and discovered failures may vary with the memory backend, model, and system configuration.Source: A LIMITATIONS AND SCOPE · p. 11
  • U-FUZZ is designed to discover and localize memory-use failures, not diagnose their internal causes or prescribe mitigation strategies.The authors identify additional memory architectures, mutation operators, and deployment settings as future extensions.Source: A LIMITATIONS AND SCOPE · p. 11

B.1 MUTATION CONSTRUCTION AND VALIDATION

U-FUZZ builds mutants from checkpoint seeds by changing one query or memory input at a time, then validates the intended change before execution. Validation relies on query fields, checkpoint provenance, memory operations, and independently observable state rather than the test response or failure outcome.

B.1 MUTATION CONSTRUCTION AND VALIDATION

  • Each seed and mutation obligation fixes one operator and target; checkpoint provenance supplies query fields, replacement or absent targets, and supported memory operations.An LLM may realize free-form query wording but does not choose the target or decide validity.Source: §B.1 · p. 11
  • Meaning-preserving query mutations alter wording while preserving answer-affecting fields, and are accepted only if those fields remain unchanged without new conditions.The four transformations are paraphrasing, shortening removable context, adding nonrestrictive context, and changing syntactic form; semantic checking is only a rejection filter for substantial rewrites.Source: §B.1 · p. 12
  • Target-changing and unsupported query mutations replace one field with a checkpoint-supported target or an absent, type-compatible memory-exclusive target, respectively.Validation checks the replacement against checkpoint provenance, rather than inferring absence from failed retrieval or an incorrect response.Source: §B.1 · p. 12
  • Memory-state mutations update or delete selected facts, or change unrelated information while preserving query-relevant evidence for the unrelated-change control.Updates require the new value to be recorded as later or active but need not physically remove the old value; deletions remove or deactivate selected support.Source: §B.1 · pp. 12–13
  • Before execution, validation checks that the mutant is well formed and the intended query or memory change occurred; only candidates passing all operator-specific checks run.For memory-state changes, checks compare the selected item before and after the operation or use an available backend operation result.Source: §B.1 · pp. 13–14
  • When memory state is hidden, a state mutation counts as validated only if completion is checked independently, such as through an API call, operation log, or management interface.The agent’s test response is not used to validate the mutation; unverified candidates are not counted as validated memory-state tests.Source: §B.1 · p. 14

B.2 IMPLEMENTATION DETAIL OF SEED RETENTION AND ITERATION

U-FUZZ retains and prioritizes mutants using execution feedback rather than failure results. Visible retrieval supplies coverage, novelty, and divergence signals; when retrieval is hidden, retention instead uses response novelty, and retained mutants seed later rounds.

B.2 IMPLEMENTATION DETAIL OF SEED RETENTION AND ITERATION

  • Retrieval coverage and novelty determine mutant retention, while retrieval divergence further prioritizes retained meaning-preserving mutants; failure results are reserved for evaluation.Source: §B.2 · p. 14
  • Coverage measures newly reached memory entries, while novelty marks a new ordered top-k retrieval pattern even when its entries were already reached.A mutant is retained when coverage gain is positive or its top-k pattern is new.Source: §B.2 · p. 14
  • Divergence measures retrieval-ranking change from the parent using RBO, emphasizing agreement near the top; it prioritizes but does not determine retention.Source: §B.2 · p. 14
  • Uncovered mutation obligations receive generation attempts before extra variants for already exercised obligations, and retained mutants compete for remaining budget using available feedback indicators.After execution, coverage and top-k signature records are updated before considering the next mutant.Source: §B.2 · p. 14
  • With hidden retrieval, U-FUZZ cannot use retrieval coverage, novelty, or divergence and instead retains mutants based on previously unseen responses.Retained mutants become seeds in the next round, while failure results remain separate from the process.Source: §B.2 · pp. 14–15

C MUTATION CASE STUDIES

Six examples illustrate U-FUZZ’s mutation operators through benchmark-derived parent–mutant pairs and expected-behavior checks; a mutant need not trigger a failure on every memory backend.

Case Study 1: Meaning-Preserving Query Mutation

  • A meaning-preserving reformulation should retain the supported answer: changing the wording of Melanie’s pet query must preserve its supporting memories and answer.The requested entity, attribute, temporal scope, and answerability remain unchanged.Source: C MUTATION CASE STUDIES · p. 15

Case Study 2: Target-Changing Query Mutation

  • Changing Melanie’s event target from the museum to the pottery workshop should redirect retrieval to evidence supporting the new target and date.The mutant receives a new reference derived independently from the same checkpoint.Source: C MUTATION CASE STUDIES · p. 15

Case Study 3: Unsupported Query Mutation

  • Replacing a supported project target with an unsupported one should make the query unanswerable, so a definite memory-backed ordering exposes a failure.Checkpoint provenance establishes the lack of support before execution.Source: C MUTATION CASE STUDIES · p. 15

Case Study 4: Update Mutation

  • After a valid schedule update, the fixed tennis query should return the new every-other-week frequency rather than stale weekly evidence.The tested backend constructs the updated memory state through its native update behavior.Source: C MUTATION CASE STUDIES · p. 15

Case Study 5: Deletion Mutation

  • After Caroline’s research fact is deleted through the backend’s native operation, retrieving it or answering “Adoption agencies” exposes a deletion failure.U-FUZZ independently verifies the deletion before execution; the post-deletion reference is abstention if no other valid support remains.Source: C MUTATION CASE STUDIES · p. 16

Case Study 6: Unrelated-Change Mutation

  • Adding unrelated information about Caroline should leave the fixed query about Melanie’s instruments and its selected support unchanged.A changed support or answer exposes a non-interference failure.Source: C MUTATION CASE STUDIES · p. 16
Loading 2609.38275v1…