On Private Knowledge Retrieval and Private Inference for secure multi-agent systems

Vicenç Torra, Maria Bras-AmorósarXiv 2026 · arXiv

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":

  1. 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.
  2. 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.
  3. 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:
  4. Information-Theoretical PIR (IT-PIR): Using two non-colluding servers to retrieve data such that neither server knows which index was queried.
  5. k-anonymity: The agent hides its real query among $k-1$ random "dummy" queries.
  6. 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

Abstract

Multi-agent systems provide a convenient framework for the massive deployment of agents based on Large Language Models (LLMs). It provides a sound framework where agents can interact with existing software to perform actions in an autonomous way. Agentic AI is the new term to denote these AI-based autonomous systems. In real multi-agent systems, agents need to deal with malicious agents some of which can exploit security vulnerabilities to do harm. A memory poisoning attack is an example of exploiting a vulnerability to modify agents knowledge and, thus, affect its behavior. In an agent, there are different types of memory systems (semantic, episodic, and short-term) which have their own characteristics and for which different memory poisoning attacks may be developed. In this paper we focus on semantic memory, we discuss its attack, and mitigation strategies. We introduce private knowledge retrieval and private inference. We propose a signature system in the knowledge base to prevent from undesired manipulation. This should avoid memory poisoning attacks by introducing security by design in the construction of the semantic memory. In our architecture, an agent contains a local Prolog-like inference system (i.e., using Horn clauses to represent knowledge) which accesses an external knowledge base to get the required knowledge. This externally signed knowledge base is accessed privately. We provide different implementations in Python using different privacy levels including k-anonymity and information-theoretical privacy (IT-PIR).
BibTeX
@misc{torra2026private,
  author = {Vicenç Torra and Maria Bras-Amorós},
  title = {{On Private Knowledge Retrieval and Private Inference for secure multi-agent systems}},
  year = {2026},
  eprint = {2611.13696},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.13696},
}
Figure