TL;DR
This paper introduces a "security by design" architecture to protect the semantic memory of LLM-based agents from malicious poisoning attacks. By combining local symbolic inference (using Prolog-like Horn clauses) with Private Information Retrieval (PIR) and digital signatures, the authors demonstrate how agents can access external knowledge bases without exposing their query patterns or falling victim to unauthorized data manipulation.
What Problem Does This Paper Address?
As we move toward Agentic AI—systems where Large Language Models (LLMs) act as autonomous agents in multi-agent environments—security becomes a paramount concern. One of the most insidious threats is a memory poisoning attack, where a malicious agent modifies another agent's memory to subvert its behavior (e.g., tricking a travel agent into buying the wrong ticket or a system agent into deleting a home directory).
The authors argue that current research often treats memory poisoning like standard machine learning data poisoning. However, agent memory is not monolithic; it consists of short-term, episodic, and semantic (factual) systems. This paper specifically targets semantic memory. The challenge is that agents often rely on external, third-party knowledge bases. If these bases are untrusted or compromised, an attacker can inject "triggers" that cause the agent to perform malign actions. The authors aim to break the assumptions that allow these attacks to succeed by making the knowledge base tamper-proof and the retrieval process private.
Methods
The authors propose a hybrid architecture that separates the "thinking" from the "storing":
- Local Prolog-like Inference: Instead of relying solely on an LLM's internal weights, the agent uses a local symbolic inference engine. Knowledge is represented as Horn clauses (facts and rules). This allows for transparent, logical reasoning that is harder to "hallucinate" or manipulate via prompts.
- Digitally Signed Knowledge: Every item in the external knowledge base includes provenance metadata and is digitally signed (using SHA-256). This ensures that even if a server is compromised, the agent can verify the integrity and source of the data before using it for inference.
- Private Knowledge Retrieval: To prevent an untrusted server from learning what an agent is "thinking" about (which could help an attacker craft better poisoning triggers), the authors implement several privacy-preserving protocols:
- Information-Theoretical PIR (IT-PIR): Using two non-colluding servers to retrieve data such that neither server knows which index was queried.
- k-anonymity: The agent hides its real query among $k-1$ random "dummy" queries.
- Bucket Retrieval: The database is divided into buckets, and the agent retrieves an entire bucket to hide the specific item it needs.
Datasets
The authors evaluated their prototype using a custom-built knowledge base designed to test logical complexity:
- Size: 99 facts and rules, resulting in 46 distinct database entries (predicate/arity pairs).
- Benchmarks: They implemented classic Prolog benchmarks, specifically nreverse (naive reverse) for testing deep recursion (depth of 496 for a 30-element list) and the Zebra Puzzle to test complex constraint satisfaction.
- Evaluation Queries: A set of 18 queries was used to measure execution time across different privacy configurations.
Key Insights and Ideas
- Breaking the Optimization Loop: Most poisoning attacks rely on the attacker knowing the "clean" database and how the agent queries it. By using PIR, the agent makes its query patterns invisible, effectively blinding the attacker.
- Symbolic + Neural Hybrid: The paper suggests that "Agentic AI" shouldn't just be an LLM in a loop. By offloading factual reasoning to a symbolic system (Prolog) and using the LLM for higher-level coordination, you gain a "security by design" layer that is much easier to audit than a black-box neural network.
- Efficiency of XOR: A surprising "aha" moment in the results was the efficiency of the IT-PIR implementation. Despite the overhead of querying two servers and performing XOR operations on the results, the performance hit was minimal compared to a standard unprotected baseline.
Key Results
The authors measured the execution time (in seconds) for their 18-query test suite:
- Baseline (No Privacy): ~0.178s
- IT-PIR (2 Servers): ~0.223s
- k-anonymity (k=10): ~0.179s
- Standard Caching: When results were cached locally, the mean execution time dropped significantly to ~0.09s across all methods, showing that the privacy overhead is primarily a "first-read" cost.
Quantitatively, IT-PIR added roughly 25% latency compared to the baseline, which the authors argue is a very reasonable trade-off for the high level of information-theoretical privacy it provides.
Limitations and Future Work
- Single-Machine Prototype: The current implementation runs on a single machine. In a real-world scenario, network latency between agents and distributed knowledge servers would be a significant factor.
- Granularity of Retrieval: Currently, the system retrieves all clauses for a given predicate/arity (e.g., all "mortal/1" facts). The authors suggest moving toward Just-In-Time Indexing (JITI) to allow for more granular, argument-specific queries.
- Communication Security: The prototype does not yet implement secure communication logs or encrypted messaging between the agents themselves, which remains a vulnerability in a truly distributed multi-agent system.
- Collusion: The IT-PIR model assumes servers do not collude. Future work could explore more robust codes (like Locally Repairable Codes) to handle potentially colluding or malicious servers.
Summary updated