acceptodds
Under review as a conference paper at ICLR 2027

MELT:A Dependency-Aware Defense against Memory Poisoning Attacks Based on Taint Analysis

Abstract

Self-evolving LLM agents update their internal state across sessions, often by storing and reusing long-term memory. This improves performance on long-horizon tasks but also introduces a security risk: attackers can poison long-term memory and allow malicious influence to persist during later retrieval and reasoning. More challenging, poisoned memories may not contain explicit malicious instructions. Malicious intent can be hidden in seemingly plausible facts, relations, or reasoning fragments, or distributed across multiple memories that appear harmless when examined individually. As a result, detection methods that analyze each complete memory as a single unit may fail to identify the resulting security risks. To address this problem, we propose MELT (Memory Exposure and Latent Taint), a fine-grained security analysis framework for memory-augmented LLM agents. MELT decomposes natural-language memories into dependency relations and organizes them in a Memory Dependency Graph (MDG). The MDG captures dependencies both within individual memories and across multiple memories. MELT then performs relation-level taint propagation to track how untrusted information spreads along these dependencies. Finally, it validates tainted relations against independent evidence to identify dependencies that may affect security-sensitive reasoning or behavior. Across 298 evaluation units on the native AgentDojo architecture, MELT detects 81.3% of unauthorized-access attacks and 83.9% of log- or fact-tampering attacks. It also intercepts 66.7% of compositional attacks at retrieval time, with a 0.0% false-positive rate on benign cases. These results show that MELT can identify harmful dependencies hidden in seemingly plausible memories, including attack paths that emerge only when multiple memories are combined.

Primary area:
alignment, fairness, safety, privacy, and societal considerations
Keywords:
LLM Agents, Persistent Memory, Compositional Memory Poisoning, Taint Analysis, Memory Dependency Graph, Agent Security

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_oXurOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper studies poisoning of persistent natural-language memory in LLM agents. Its central observation is that a malicious influence may be distributed across several memories that look benign in isolation and becomes dangerous only after retrieval composes them into a security-sensitive dependency.

Critical strengths

The choice of analysis granularity is well motivated. Treating individual typed relations, rather than whole memory records, as the units of provenance and validation is well matched to attacks whose components are innocuous separately. Re-running the analysis on the joint graph at retrieval time is consequential because it targets dependencies that do not exist when memories are ingested independently.

Critical weaknesses

The evaluation is not specified well enough to support the comparative claims. The paper omits attack-generation details, AgentDojo denominators, benign-set size, baseline calibration, and an end-to-end measure of whether sensitive disclosure or unauthorized action was actually prevented. The reported values are also difficult to reconcile: unauthorized-access and fact-tampering results differ between Tables 1 and 2, and MINJA appears with 45.1%, 85.5%, and 87.5% across insufficiently distinguished settings.

Questions for authors
  1. What are the exact denominators, benign-set sizes, and undefended attack-success rates for every AgentDojo result and for the stated 298 evaluation units?
  2. Why do the full-MELT values in Tables 1 and 2 differ for apparently corresponding attacks, and what precisely distinguishes the 45.1%, 85.5%, and 87.5% MINJA settings?
  3. Can the authors report end-to-end attack success and benign task success before and after enforcement, rather than detection rate alone?
3 comments

We thank the reviewer for the detailed evaluation questions. Q1: Evaluation denominators and attack construction. We added details of the DeepSeek-V4-based attack-generation procedure, covering target-question construction, poisoned-memory generation, adversarial-prompt generation, and memory-formation validation (Appendix A.5). Each of the five non-MINJA AgentDojo attack families comprises 164 original cases. We also clarified the distinction between the 250-episode calibration set and the separate 86-task benign evaluation. The previously reported 298 refers to entities rather than attack evaluation units. Figure 2 now presents ASR with and without defense across all six attack families, while Table R1 reports detailed attack-family results.

Table R1. Attack success rates (ASR), detection rates (DR), and extraction failure rates (EFR) across controlled and AgentDojo environments.

Attack TypeNo Defense ASR ↓MELT ASR ↓MELT DR ↑MELT EFR ↓
(a) Controlled Environment
Unauthorized access71.7%5.0%90.0%10.0%
Fact tampering81.5%11.5%77.5%17.0%
Compositional attack95.0%25.8%50.8%0.0%
Reference rebinding75.0%0.0%100.0%0.0%
Spurious inference81.5%40.7%36.1%45.0%
MINJA95.4%47.1%45.1%55.9%
(b) AgentDojo Environment
Unauthorized access71.3%3.9%81.3%0.0%
Fact tampering87.4%6.7%83.9%0.0%
Compositional attack90.7%25.2%66.7%0.0%
Reference rebinding78.5%0.0%100.0%0.0%
Spurious inference85.2%31.5%53.3%0.0%
MINJA83.1%5.8%85.5%0.0%

Q2: Differences between evaluation settings. We clarified that Table 1 uses separate controlled ablation subsets while maintaining the same models, validation configuration, and evaluation metrics as the main experiments (Appendix A.5). The MINJA detection rates of 45.1% and 85.5% correspond to the controlled benchmark and AgentDojo, respectively (Table R1). Differences in entity-reference clarity may affect dependency extraction. The previously reported AgentDojo detection rates of 85.5% and 87.5% resulted from experimental variation across independent runs under identical settings. To avoid ambiguity, we standardized the MINJA detection rate to 85.5% in Sec. 5.3 and Figure 3, ensuring consistency with the main evaluation. The ablation results use separately selected controlled subsets (Table 1 in the revised manuscript), which explains the differences between their detection rates and those reported in Table R1.

Table R2. Benign task success before and after enabling MELT on AgentDojo.

EnvironmentTasksWithout MELTWith MELTChange (pp)
Workspace3393.94%93.94%0.00
Slack1782.35%70.59%-11.76
Travel20100.00%100.00%0.00
Banking1693.75%87.50%-6.25
Overall8693.02%89.53%-3.49

Q3: End-to-end outcomes and benign utility. We now report ASR with and without MELT across all six attack families (Table R1), evaluating whether poisoned memories induce attacker-targeted harmful instructions or commands in subsequent agent interactions. On AgentDojo, MELT reduces the macro-average ASR from 82.7% to 12.2%, while benign task success declines by only 3.49 percentage points across 86 legitimate tasks (Table R2). These results demonstrate that MELT substantially mitigates harmful outputs while largely preserving benign task performance.

We would greatly appreciate any further feedback or remaining concerns you may have, and we would be more than happy to make additional revisions to address them.

Thanks for the detailed rebuttal. I maintain my score to support this paper.

Reviewer_1tYHOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

MELT proposes a dependency-aware defense against memory poisoning in LLM agents. It constructs memory dependency graphs and performs relation-level taint propagation and validation to detect malicious influences within and across memories.

Critical strengths

The paper addresses an important challenge in persistent-memory security, particularly attacks that emerge through dependencies between seemingly benign memories. Its relation-level taint analysis provides a meaningful approach to detecting such threats. Experiments across controlled environments and AgentDojo, together with ablation studies, support the proposed framework.

Critical weaknesses

The effectiveness of MELT depends heavily on accurate dependency extraction, with a 45% extraction failure rate on spurious-inference cases in the controlled evaluation. Compared with published memory defenses such as A-MemGuard, the distinct benefits of explicit dependency tracking could also be more clearly established.

Questions for authors

How robust is MELT to dependency-extraction errors, and what added value does relation-level tracking offer over existing memory defenses?

3 comments

We thank the reviewer for highlighting the role of dependency extraction.

Q1: Extraction robustness and relation-level tracking. We refined the RQ1 analysis to clarify that dependency extraction is a major bottleneck for spurious-inference attacks, with a 45.0% extraction failure rate and a 36.1% detection rate (Sec. 5.2). Missing reasoning relations cannot be validated downstream, leading to missed detections. Unlike memory-level consistency or consensus analysis, MELT tracks relation provenance and cross-memory dependency paths to identify unsafe relations arising from individually plausible memories. We acknowledge dependency extraction accuracy as an ongoing limitation and explicitly discuss this limitation in the Conclusion (Sec. 7).

We would greatly appreciate any further feedback or remaining concerns you may have, and we would be more than happy to make additional revisions to address them.

Thank you for the clarification and audit analysis. I will keep my rating unchanged at Weak Accept.

Reviewer_fGyBOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies memory poisoning in LLM agents, especially cases where several memories look harmless on their own but become harmful when retrieved together. MELT turns memories into a Memory Dependency Graph, tracks their provenance through relation-level taint propagation, and checks sensitive dependencies against trusted observations, policy rules, and an inference validator. The experiments use a controlled environment and AgentDojo with added memory and poisoning layers. The results are encouraging for access violations and fact tampering, while implicit inference and some compositional attacks remain harder to detect.

Critical strengths

Attacks that only become apparent when memories are combined is promising. Checking whole records independently can miss these interactions, so tracking dependencies and their sources is a sensible way to approach the problem. Keeping provenance separate from the final security judgment is also useful, since untrusted information is not automatically malicious.

The retrieval-time ablation gives concrete support for checking memories together. On the dedicated 40-unit compositional subset, interception rises from 0% with explicit-edge-only checking to 75% with propagation over the connected graph (Section 5.4). This is a promising result, even though it comes from a limited setting.

Critical weaknesses
  1. The evaluation does not yet show how much MELT reduces successful attacks on the agent. Most results are detection rates, with retrieval-time interception reported for compositional attacks. I could not find attack success rates before and after applying the defense, or benign task success after memories are filtered. The AgentDojo setup also adds its own memory and poisoning layers, so it matters whether the injected cases actually lead to unsafe behavior without MELT. Flagging a poisoned dependency is useful, but I would like to see that this translates into fewer successful attacks without disrupting legitimate tasks. This is the main gap in the evidence for practical protection.

  2. I am not yet convinced that the comparisons isolate the benefit of the dependency graph. MELT can consult trusted policies and execution records, but Section 5.1 does not clearly establish whether the baselines have equivalent access to this evidence. The retrieval-time ablation is helpful, but comparing explicit-edge checks with graph propagation does not tell us whether a simpler joint-memory validator, given the same model and trusted evidence, could achieve similar results. Since the graph is the main methodological contribution, a comparison under the same evidence and false-positive constraints would make the case for it much stronger.

  3. The inference validator seems to leave a gap for unsupported but internally consistent poisoning. In Appendix A.3, its score is p_con - p_ent. A mostly neutral prediction therefore gives a score near zero, below the 0.12 threshold when the other validation channels are unavailable. Yet identifying unsupported dependencies is part of the stated goal. There is also a related question about trust: if the premise is assembled from poisoned memories, a malicious conclusion may be consistent with that premise without being trustworthy. I would like to see this limitation addressed with concrete examples and defense-aware attacks. This matters under Section 2.2, where the attacker knows the defense, while adaptive attacks are left to future work in Section 7.

Questions for authors
  1. Evaluation clarification: Were the attack cases verified to succeed against the underlying agent without a defense? Can you provide attack success rates with and without MELT, together with benign task success after filtering?

  2. Comparison clarification: Did MEMSAD and MemAudit receive the same trusted policy and observation evidence as MELT? If so, how was it supplied? A joint-memory validation baseline using the same model and evidence would also help establish the added value of the graph.

  3. Method clarification: What does MELT do when a sensitive dependency receives a neutral NLI prediction and no trusted evidence is available? How is the premise constructed to avoid treating other poisoned memories as sufficient support? An example or existing result for this case would materially affect my assessment.

4 comments

We thank the reviewer for the constructive comments.

Q1: Attack success and benign task performance. We added attack success rates (ASR) with and without MELT across six attack families in both controlled and AgentDojo environments (Figure 2). As summarized in Table R1, MELT reduces the macro-average AgentDojo ASR from 82.7% to 12.2%. Evaluation on 86 benign AgentDojo tasks shows a decrease of only 3.49 percentage points in task success (Table R2; Appendix A.6).

Table R1. Attack success rates (ASR), detection rates (DR), and extraction failure rates (EFR) across controlled and AgentDojo environments.

Attack TypeNo Defense ASR ↓MELT ASR ↓MELT DR ↑MELT EFR ↓
(a) Controlled Environment
Unauthorized access71.7%5.0%90.0%10.0%
Fact tampering81.5%11.5%77.5%17.0%
Compositional attack95.0%25.8%50.8%0.0%
Reference rebinding75.0%0.0%100.0%0.0%
Spurious inference81.5%40.7%36.1%45.0%
MINJA95.4%47.1%45.1%55.9%
(b) AgentDojo Environment
Unauthorized access71.3%3.9%81.3%0.0%
Fact tampering87.4%6.7%83.9%0.0%
Compositional attack90.7%25.2%66.7%0.0%
Reference rebinding78.5%0.0%100.0%0.0%
Spurious inference85.2%31.5%53.3%0.0%
MINJA83.1%5.8%85.5%0.0%

Table R2. Benign task success before and after enabling MELT on AgentDojo.

EnvironmentTasksWithout MELTWith MELTChange (pp)
Workspace3393.94%93.94%0.00
Slack1782.35%70.59%-11.76
Travel20100.00%100.00%0.00
Banking1693.75%87.50%-6.25
Overall8693.02%89.53%-3.49

Q2: Dependency graph contribution and baseline evidence. We clarified the evidence available to MEMSAD and MemAudit (Sec. 5.1). MEMSAD uses memory records, user queries, and user information extracted from logs, whereas MemAudit relies on memory records, observed harmful outputs, and counterfactual replay without requiring trusted policies. We also evaluated a graph-free baseline (−MDG in Table 1 and Table R3) using the same validation models and trusted evidence. As shown in Table R3, removing MDG reduces the mean detection rate from 64.3% to 24.7% across four controlled ablation subsets, highlighting the importance of dependency-level modeling (Sec. 5.4).

Table R3. Component ablation results on controlled benchmark subsets. All values are detection rates (DR).

ConfigurationUnauthorized AccessFact Tampering (Log)Fact Tampering (Num)Spurious Inference
Full MELT82.0%55.0%84.0%36.1%
Without policy validation54.0%55.0%44.0%36.1%
Without observation validation82.0%55.0%84.0%36.1%
Without inference validation38.0%44.0%44.0%0.0%
Graph-free (−MDG)32.7%15.3%14.7%36.1%

Q3: Neutral predictions and trust assumptions. We clarify that NLI premises are constructed from upstream reasoning relations within the evaluated memory dependency graph (MDG), rather than from arbitrary stored memories, while preserving memory provenance (Sec. 4.2). A neutral prediction without applicable trusted evidence neither establishes a security violation nor authorizes access to sensitive resources. Such memories retain their taint provenance and are reassessed upon joint retrieval, enabling MELT to identify newly formed security-sensitive dependencies (Sec. 4.3; Appendix A.3).

Importantly, MELT's trusted evidence consists of system-owner-defined access-control policies and authoritative execution records established independently of the memory store, such as permissions governing financial transaction statements. Under our threat model, attackers cannot modify this evidence, which provides an independent basis for validating security-sensitive dependencies. This trust boundary aligns with prior agent-security research that distinguishes attacker-controlled content from protected authorization and enforcement mechanisms (Debenedetti et al., 2026; Ouyang and Hou, 2026; Louck, 2026).

Debenedetti, E., Shumailov, I., Fan, T., Hayes, J., Carlini, N., Fabian, D., Kern, C., Shi, C., Terzis, A., & Tramèr, F. (2026). Defeating Prompt Injections by Design. 2026 IEEE Conference on Secure and Trustworthy Machine Learning (SaTML). https://doi.org/10.1109/SaTML68715.2026.00040

Ouyang, C., & Hou, R. (2026). MemLineage: Lineage-Guided Enforcement for LLM Agent Memory. arXiv preprint arXiv:2605.14421. https://arxiv.org/abs/2605.14421

Louck, Y. (2026). Securing LLM-Agent Long-Term Memory Against Poisoning: Non-Malleable, Origin-Bound Authority with Machine-Checked Guarantees. arXiv preprint arXiv:2606.24322. https://arxiv.org/abs/2606.24322

We would greatly appreciate any further feedback or remaining concerns you may have, and we would be more than happy to make additional revisions to address them.

Dear Reviewer,

We hope you are well. With the discussion period drawing to a close, we wanted to check whether our response has adequately addressed your concerns. We have added attack success rates before and after MELT, evaluated benign task performance on 86 AgentDojo tasks, and introduced a graph-free baseline to isolate the contribution of dependency modeling. We have also clarified the evidence available to existing baselines, the handling of neutral predictions, and the trust assumptions underlying our defense.

If any concerns remain, or if further clarification would be helpful, we would be very glad to hear your thoughts and respond before the discussion closes.

Thank you for your careful reading and constructive feedback.

Best regards,
The Authors

Dear Reviewer,

We hope you are well. As the discussion period draws to a close, we would like to kindly follow up on our response to your constructive comments.

We have carefully revised our manuscript in response to your suggestions, including adding attack success rates and benign task evaluations, introducing a graph-free baseline to demonstrate the contribution of dependency modeling, and clarifying the handling of neutral predictions and our trust assumptions.

We sincerely hope these revisions have addressed your concerns. If there are any remaining issues or areas that require further clarification, we would be very grateful for your feedback and would be happy to address them.

If you find that our revisions have satisfactorily resolved your concerns, we would also greatly appreciate it if you could consider updating your assessment accordingly.

Thank you again for your valuable feedback and time.

Best regards,
The Authors

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.