Mnemis: Dual-Route Retrieval on Hierarchical Graphs for Long-Term LLM Memory

Zihao Tang; Xin Yu; Ziyu Xiao; Zengxuan Wen; Zelin Li; Jiaxi Zhou; Hualei Wang; Haohua Wang

cs.CLFeb 17, 2026

Mnemis: Dual-Route Retrieval on Hierarchical Graphs for Long-Term LLM Memory

Authors: Zihao Tang, Xin Yu, Ziyu Xiao, Zengxuan Wen, Zelin Li, Jiaxi Zhou, Hualei Wang, Haohua Wang,

Organizations: Microsoft

Abstract

AI Memory, specifically how models organizes and retrieves historical messages, becomes increasingly valuable to Large Language Models (LLMs), yet existing methods (RAG and Graph-RAG) primarily retrieve memory through similarity-based mechanisms. While efficient, such System-1-style retrieval struggles with scenarios that require global reasoning or comprehensive coverage of all relevant information. In this work, We propose Mnemis, a novel memory framework that integrates System-1 similarity search with a complementary System-2 mechanism, termed Global Selection. Mnemis organizes memory into a base graph for similarity retrieval and a hierarchical graph that enables top-down, deliberate traversal over semantic hierarchies. By combining the complementary strength from both retrieval routes, Mnemis retrieves memory items that are both semantically and structurally relevant. Mnemis achieves state-of-the-art performance across all compared methods on long-term memory benchmarks, scoring 93.9 on LoCoMo and 91.6 on LongMemEval-S using GPT-4.1-mini.

Figures & tables

Figure 1: Framework of Mnemis together with the workflow of base graph ingestion, hierarchical graph ingestion and search. Left is a real case from LoCoMo.

Figure 2: Mnemis Hierarchical Graph Overview.

LLM	Methods	Multi-Hop	Temporal	Open-Domain	Single-Hop	Overall
$\sharp$ Questions		282	321	96	841	1540
GPT-4o-mini	Full Context	66.8	56.2	48.6	83.0	72.3
	RAG	59.9	62.9	63.5	73.5	68.2
	LangMem	52.4	24.9	47.6	61.4	51.3
	MemOS	64.3	73.2	55.2	78.4	73.3
	Mem0	60.3	50.4	40.6	68.1	61.3

Table 1: Detailed performance (LLM-as-a-Judge score) on LoCoMo by question type. Following the common practice, Category 5 (Adversarial) is excluded from the results.

LLM	Methods	SSU	MS	SSP	TR	KU	SSA	Overall
$\sharp$ Questions		70	133	30	133	78	56	500
GPT-4o-mini	Full Context	78.6	38.3	6.7	42.1	78.2	89.3	55.0
	RAG	88.6	47.4	70.0	63.2	70.5	91.1	67.2
	Mem0	91.4	66.2	34.0	63.9	74.4	96.4	71.1
	Zep	92.9	47.4	53.3	54.1	74.4	75.0	63.2
	Nemori	88.6	51.1	46.7	61.7	61.5	83.9	64.2

Table 2: Detailed performance (LLM-as-a-Judge score) on LongMemEval-S, categorized by question type: single-session-user (SSU), multi-session (MS), single-session-preference (SSP), temporal reasoning (TR), knowledge update (KU), and single-session-assistant (SSA).

Stage	$\sharp$ Prompt Tokens	$\sharp$ Completion Tokens	E2E Runtime(s)
Base Graph Ingestion	$3.87\times 10^{7}$	$1.06\times 10^{6}$	1111.40
Hierarchical Graph Ingestion	$1.39\times 10^{7}$	$9.27\times 10^{5}$	3873.26
Global Selection	$1.37\times 10^{6}$	$1.21\times 10^{5}$	3637.65

Table 3: Detailed LLM cost of Mnemis on LoCoMo using GPT-4.1-mini, reported as the overall number of prompt tokens, completion tokens, and end-to-end runtime for processing the entire dataset. Runtime depends heavily on database latency and parallelism configuration; the reported values are for reference only, and we will continue to optimize it for greater efficiency.

Settings	Multi-Hop	Temporal	Open-Domain	Single-Hop	Overall
System-1 RAG	64.9	76.6	67.7	76.5	73.8
System-1 Graph	84.8	62.6	74.0	88.6	81.6
System-1 RAG + Graph	85.1	84.7	75.0	93.7	89.1
System-1 Re-ranked	88.7	85.0	75.0	92.4	89.1
System-2 Only	88.1	78.5	79.5	92.0	87.7
System-1 + System-2	91.8	90.3	82.3	96.2	93.3

Table 4: Detailed performance (LLM-as-a-Judge score) on LoCoMo by question type.

Figure 3: Mnemis win case on LoCoMo benchmark. While similarity search fixates on the surface-level cause gastritis, Mnemissuccessfully identifies the underlying root cause, namely that Sam is overweight. This condition leads to the gastritis and motivates him to change his lifestyle.

Figure 4: LoCoMo result across different top-

k

settings.

Re-ranker	Multi-Hop	Temporal	Open-Domain	Single-Hop	Overall
Qwen3-Reranker-0.6B	91.8	90.3	79.2	95.2	92.6
BGE-Reranker-V2-M3	90.1	90.0	77.1	96.4	92.7
Qwen3-Reranker-8B	91.8	90.3	82.3	96.2	93.3

Table 5: Detailed performance (LLM-as-a-Judge score) on LoCoMo by question type.

Embedder	Multi-Hop	Temporal	Open-Domain	Single-Hop	Overall
MiniLM	46.1	57.9	64.6	62.5	58.7
BGE-M3	50.0	74.1	63.5	74.0	69.0
Qwen3-Embedding-0.6B	64.9	76.6	67.7	76.5	73.8
Gemma-300M	62.4	78.8	60.4	82.9	76.9

Table 6: Detailed performance (LLM-as-a-Judge score) on LoCoMo by question type.

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 5: Mnemis win case on LongMemEval-S benchmark, where Mnemis successfully retrieve "Company’s Annual Charity Soccer Tournament" from "Sports Events".

User IDs	0	1	2	3	4
LLM-as-a-Judge True Question IDs	31, 8, 74	13, 74, 11	7, 26, 60	6, 160, 59	124, 161, 80
LLM-as-a-Judge False Question IDs	7, 138, 137	73, 47, 20	17, 49, 63	195, 92, 53	165, 166, 6
User IDs	5	6	7	8	9
LLM-as-a-Judge True Question IDs	104, 110, 23	47, 65, 96	25, 97, 94	126, 147, 32	99, 156, 54
LLM-as-a-Judge False Question IDs	55, 19, 119	1, 62, 31	117, 77, 23	102, 39, 70	7, 1, 61

Appendix

Table 7: Sampled Question ID for Human Evaluation in LoCoMo.

Methods	Multi-Hop	Temporal	Open-Domain	Single-Hop	Overall
$\sharp$ Questions	282	321	96	841	1540
Full Context	77.2	74.2	56.6	86.9	80.6
RAG	64.9	76.6	67.7	76.5	73.8
LangMem	71.0	50.8	59.0	84.5	73.4
Mem0	68.2	56.9	47.9	71.4	66.3
Zep	53.7	60.2	43.8	66.9	61.6

Appendix

Table 8: Detailed performance (LLM-as-a-Judge score) on LoCoMo by question type. Following the common practice, Category 5 (Adversarial) is excluded from the results.

Methods	SSU	MS	SSP	TR	KU	SSA	Overall
$\sharp$ Questions	70	133	30	133	78	56	500
Full Context	85.7	51.1	16.7	60.2	76.9	98.2	65.6
RAG	82.9	54.9	86.7	67.7	80.8	94.6	72.6
PREMem	92.9	57.1	36.7	59.4	84.6	12.5	60.8
Mem0	94.3	66.9	86.7	75.9	87.2	96.4	80.8
Nemori	90.0	55.6	86.7	72.2	79.5	92.9	74.6

Appendix

Table 9: Detailed performance (LLM-as-a-Judge score) on LongMemEval-S, categorized by question type: single-session-user (SSU), multi-session (MS), single-session-preference (SSP), temporal reasoning (TR), knowledge update (KU), and single-session-assistant (SSA).

Settings	top- $k$	Multi-Hop	Temporal	Open-Domain	Single-Hop	Overall
System-1 RAG	5	49.6	70.1	65.6	66.8	64.3
	10	64.9	76.6	67.7	76.5	73.8
	30	77.3	82.9	69.8	86.0	82.7
	50	81.6	84.1	71.9	89.1	85.6
System-1 Graph	5	79.4	61.4	75.0	86.7	79.4
	10	84.8	62.6	74.0	88.6	81.6

Appendix

Table 10: Detailed performance (LLM-as-a-Judge score) on LoCoMo by question type.

LLM Memory

Large language model memory studies how models store, retrieve, update, and forget information across prompts, tasks, and interactions.

See all 95 papers

EngramaBench: Evaluating Long-Term Conversational Memory with Structured Graph Retrieval
Apr 23, 2026Julian AcunaLLM Evaluation Memorization in Language Models
MemORAI: Memory Organization and Retrieval via Adaptive Graph Intelligence for LLM Conversational Agents
May 2, 2026Hung Pham Van, Nguyen Manh Hieu, Khang Pham Tran Tuan +4Conversational Memory Graph Retrieval-Augmented Generation
1Independent Researcher · 2Hanoi University of Science and Technology · 3VNU University of Engineering and Technology +1
HiGMem: A Hierarchical and LLM-Guided Memory System for Long-Term Conversational Agents
Apr 20, 2026Shuqi Cao, Jingyi He, Fei TanPersistent Memory for Language Models Hierarchical Memory
East China Normal University, Shanghai, China · Shanghai Jiao Tong University, Shanghai, China

Apr 23, 2026J/K move · Enter open · S save

EngramaBench: Evaluating Long-Term Conversational Memory with Structured Graph Retrieval

Julian Acuna

LLM Evaluation Memorization in Language Models Persistent Memory for Language Models Memorization in Generative Models Memory Agent Benchmarks Graph-Based Agent Memory+1

Open paper AskPDF arXiv

Large language model assistants are increasingly expected to retain and reason over information accumulated across many sessions. We introduce EngramaBench, a benchmark for long-term conversational memory built around five personas, one hundred multi-session conversations, and one hundred fifty queries spanning factual recall, cross-space integration, temporal reasoning, adversarial abstention, and emergent synthesis. We evaluate Engrama, a graph-structured memory system, against GPT-4o full-context prompting and Mem0, an open-source vector-retrieval memory system. All three use the same answering model (GPT-4o), isolating the effect of memory architecture. GPT-4o full-context achieves the highest composite score (0.6186), while Engrama scores 0.5367 globally but is the only system to score higher than full-context prompting on cross-space reasoning (0.6532 vs. 0.6291, n=30). Mem0 is cheapest but substantially weaker (0.4809). Ablations reveal that the components driving Engrama's cross-space advantage trade off against global composite score, exposing a systems-level tension between structured memory specialization and aggregate optimization.

Abstract

LLM Memory

Explore similar work

EngramaBench: Evaluating Long-Term Conversational Memory with Structured Graph Retrieval

MemORAI: Memory Organization and Retrieval via Adaptive Graph Intelligence for LLM Conversational Agents

HiGMem: A Hierarchical and LLM-Guided Memory System for Long-Term Conversational Agents