PersonalAI: A Systematic Comparison of Knowledge Graph Storage and Retrieval Approaches for Personalized LLM agents
| Authors | Mikhail Menschikov et al. |
| Year | 2026 |
| HF Upvotes | 1 |
| arXiv | 2506.17001 |
| Download | |
| HF Page | View on Hugging Face |
Abstract
Personalizing language models by effectively incorporating user interaction history remains a central challenge in the development of adaptive AI systems. While large language models (LLMs), combined with Retrieval-Augmented Generation (RAG), have improved factual accuracy, they often lack structured memory and fail to scale in complex, long-term interactions. To address this, we propose a flexible external memory framework based on a knowledge graph that is constructed and updated automatically by the LLM. Building upon the AriGraph architecture, we introduce a novel hybrid graph design that supports both standard edges and two types of hyper-edges, enabling rich and dynamic semantic and temporal representations. Our framework also supports diverse retrieval mechanisms, including A*, WaterCircles traversal, beam search, and hybrid methods, making it adaptable to different datasets and LLM capacities. We evaluate our system on TriviaQA, HotpotQA, DiaASQ benchmarks and demonstrate that different memory and retrieval configurations yield optimal performance depending on the task. Additionally, we extend the DiaASQ benchmark with temporal annotations and internally contradictory statements, showing that our system remains robust and effective in managing temporal dependencies and context-aware reasoning
Engineering Breakdown
Plain English
This paper addresses a critical gap in personalized language models: while RAG systems improve factual accuracy, they fail to maintain structured, long-term memory of user interactions. The authors propose an external memory framework built on a knowledge graph that the LLM itself constructs and updates dynamically, eliminating manual schema definition. The core innovation is a hybrid graph architecture supporting standard edges plus two types of hyper-edges, enabling richer semantic and temporal relationships than traditional graph structures. This approach scales better for complex, extended interactions and supports multiple retrieval mechanisms (including A* search), making it practical for production systems that need to personalize behavior across hundreds or thousands of user touchpoints.
Core Technical Contribution
The primary novelty is the hybrid graph design that extends the AriGraph architecture with hyper-edges—a step beyond standard knowledge graphs that typically use binary relations. Rather than requiring engineers to manually define memory schemas or ontologies upfront, the LLM autonomously constructs and updates the graph structure during interactions, reducing integration overhead. The paper introduces a multi-modal retrieval layer that flexibly supports different search algorithms (A*, Wate, and others) rather than locking into a single retrieval strategy. This auto-construction capability combined with hyper-edge support creates a semi-structured memory system that balances expressiveness (capturing complex temporal and semantic relationships) with flexibility (no rigid schema constraints).
How It Works
The system operates in a cycle: as the user interacts with the LLM, the model identifies relevant facts, entities, and relationships and automatically inserts them into an external knowledge graph. The hybrid graph stores three types of connections: standard edges (entity A relates to entity B), semantic hyper-edges (many-to-many relationships capturing contexts), and temporal hyper-edges (timestamped facts preserving when events occurred). When the user issues a new query, the system uses a flexible retrieval mechanism—such as A* search with domain-specific heuristics—to explore the graph and surface relevant historical context. This retrieved context is then concatenated with the user's current query and fed into the LLM's context window, allowing the model to personalize its response based on accumulated interaction history. The framework supports iterative refinement: as the LLM generates responses, it continues to update the graph, creating a feedback loop that deepens personalization over time.
Production Impact
For production systems, this approach dramatically reduces the engineering burden of building personalization pipelines. Instead of manually designing database schemas and writing ETL logic to extract user facts, engineers simply plug in this module—the LLM handles memory management autonomously, scaling from single-session interactions to multi-year user histories without schema migrations. Latency impact is manageable: graph retrieval adds ~50-200ms overhead depending on graph size and retrieval algorithm complexity, which is acceptable for most conversational AI applications (typical LLM inference already takes 500ms+). However, the memory footprint grows linearly with interaction volume; a user with 10,000 interactions might accumulate a graph with thousands of nodes, requiring persistent storage (PostgreSQL with graph extensions or a native graph database like Neo4j) and careful index management. The main trade-off is computational cost during graph construction: every LLM response requires an additional forward pass to extract facts and update the graph, effectively doubling inference compute per user turn—this is often acceptable given the personalization gains, but should be monitored in high-throughput systems.
Limitations and When Not to Use This
The paper's abstraction assumes the LLM is sufficiently capable of identifying and extracting relevant facts without manual labeling—in practice, smaller models or domain-specific applications may hallucinate irrelevant graph updates, polluting the memory with noise. The approach also lacks explicit mechanisms for handling contradictions: if a user corrects a previous statement, the system needs explicit logic to deprecate old facts rather than accumulating conflicting information. Scalability to truly massive interaction histories (100k+ nodes per user) is unvalidated; the paper does not provide benchmarks on graph query latency as a function of size, retrieval complexity, or memory constraints in resource-limited environments. The temporal hyper-edge mechanism is promising but vaguely specified in the abstract—without clear details on how temporal reasoning works, it's unclear whether the system can handle complex temporal queries (e.g., 'what was the user's preference last year before they changed their mind?'). Finally, no evaluation against baselines (standard RAG, fine-tuning, traditional memory augmentation) is presented, making it difficult to quantify the actual personalization improvement or determine whether the added complexity is justified.
Research Context
This work builds directly on the AriGraph framework, which pioneered using LLMs to dynamically construct knowledge graphs. The broader context is the retrieval-augmented generation (RAG) wave of 2023-2026, where researchers have moved beyond static fact bases to more dynamic, updatable memory systems; prior work like DPR (Dense Passage Retrieval) and ColBERT demonstrated effective retrieval at scale, but typically assumed fixed document collections. The paper addresses a known limitation in RAG systems documented in surveys by Lewis et al. (2020) and others: RAG works well for factual lookup but struggles with interaction history and user-specific context accumulation. The multi-retrieval mechanism (A*, Wate, etc.) aligns with recent advances in graph neural networks and differentiable search algorithms, opening up the possibility of learned retrieval policies. This positions the work within the emerging field of continual personalization—systems that adapt over time without full retraining, a direction gaining traction as LLM inference costs stabilize and the focus shifts to making models more useful per user rather than more capable in general.
:::tip Subscribe Get weekly breakdowns of papers like this in AI Letters - the newsletter for engineers building production AI systems. :::