Graph-Native Cognitive Memory for AI Agents: Formal Belief Revision Semantics for Versioned Memory Architectures

Young Bin Park

cs.AIMar 18, 2026

Graph-Native Cognitive Memory for AI Agents: Formal Belief Revision Semantics for Versioned Memory Architectures

Authors: Young Bin Park

Abstract

While individual components for AI agent memory exist in prior systems, their architectural synthesis and formal grounding remain underexplored. We present Kumiho, a graph-native cognitive memory architecture grounded in formal belief revision semantics. The structural primitives required for cognitive memory -- immutable revisions, mutable tag pointers, typed dependency edges, URI-based addressing -- are identical to those required for managing agent-produced work as versionable assets, enabling a unified graph-native architecture that serves both purposes. The central formal contribution is a correspondence between the AGM belief revision framework and the operational semantics of a property graph memory system, proving satisfaction of the basic AGM postulates (K2--K6) and Hansson's belief base postulates (Relevance, Core-Retainment). The architecture implements a dual-store model (Redis working memory, Neo4j long-term graph) with hybrid fulltext and vector retrieval. On LoCoMo (token-level F1), Kumiho achieves 0.565 overall F1 (n=1,986) including 97.5% adversarial refusal accuracy. On LoCoMo-Plus, a Level-2 cognitive memory benchmark testing implicit constraint recall, Kumiho achieves 93.3% judge accuracy (n=401); independent reproduction by the benchmark authors yielded results in the mid-80% range, still substantially outperforming all published baselines (best: Gemini 2.5 Pro, 45.7%). Three architectural innovations drive the results: prospective indexing (LLM-generated future-scenario implications indexed at write time), event extraction (structured causal events preserved in summaries), and client-side LLM reranking. The architecture is model-decoupled: switching the answer model from GPT-4o-mini (~88%) to GPT-4o (93.3%) improves end-to-end accuracy without pipeline changes, at a total evaluation cost of ~$14 for 401 entries.

Figures & tables

Dim.	Graphiti	Mem0	Letta	Hindsight	Ours
Version	Bitemporal	Timestamped	Git	None	Immutable+tags
Conflict	Temporal	LLM	Git merge	Conf	AGM Supersedes
Retrieval	BM25+vec	Graph	File	4-net	Hybrid
Formal	None	None	None	None	AGM postulates
URI	×	×	Git	×	kref://
Consol	Temporal	None	Git GC	None	Dream State

Table 1: Architectural comparison with selected concurrent systems.

Asset	Memory	Concept
Project	Scope	Container
Space	Topic	Namespace
Item	Unit	Identity
Revision	Belief $T$	Snapshot
Artifact	Evidence	Pointer
Tag	Status	Mutable ref

Table 2: Structural correspondence between asset management and cognitive memory.

Type	Implementation
Working	Redis buffer (TTL)
Episodic	Conversations
Semantic	Consolidated facts
Procedural	Tool execution
Associative	Graph edges
Meta	Tags + audit

Table 3: Memory type taxonomy and implementation.

Postulate	System Mechanism	Status
Primary formal claims (proved):
$K*2$ Success	New revision contains $A$ ; tag updated	✓
$K*3$ Inclusion	Base-level: $\mathcal{B}*A\subseteq\mathcal{B}\cup\{A\}$	✓
$K*4$ Vacuity	No conflict $\Rightarrow$ no retraction needed	✓
$K*5$ Consistency	Supersedes replaces, not accumulates	✓
$K*6$ Extensionality	Syntactic = logical equiv. for ground atoms	✓

Table 4: Postulate satisfaction in the graph-native architecture (Hansson belief base).

Mode	Context	Reranker	Cost
client	Agent via MCP	Host agent LLM	Zero
dedicated	API / Playground	User’s model	User’s key
auto	Any	Detect context	Adaptive

Table 5: LLM reranking configuration modes.

Guard	Mechanism
Dry Run	Assessment-only mode
Published Protect	Never deprecate “published”
Circuit Breaker	Max 50% deprecation
Error Isolate	Per-action try/except
Audit Report	Markdown report artifact
Cursor Persist	Resume from checkpoint

Table 6: Dream State safety guards.

Threat	Mitigation
PII leakage via summaries	LLM-based redaction before graph ingest. Limitation : LLM redaction has non-zero false negative rates; no formal guarantees.
Membership inference via embeddings	Embeddings are stored per-tenant in isolated database partitions. Limitation : embedding inversion attacks are an active research area.
Prompt injection in Dream State	Consolidation operates on stored metadata, not raw user input; safety guards (circuit breaker, published protection) limit blast radius.
Metadata re-identification	Topics and keywords can be identifying even without PII. Limitation : current redaction targets named entities, not topical fingerprints.
Malicious artifacts via tool output	Artifact pointers are stored, not artifact content; the graph never executes or parses artifact data.
Credential leakage	The ingest pipeline rejects known credential patterns (API keys, tokens) before summarization.

Table 7: Threat model and mitigations for the memory privacy boundary.

Dimension	Flat RAG	Tiered Buffers	Extended Context	Static KG	Kumiho
Retrieval	Embedding only	Embedding + scan	In-context	Query language	Hybrid + graph nav
Statefulness	Stateless	Tiered buffers	Ephemeral	Current state	Versioned history
Relationships	None	None	None	Fixed ontology	6 typed edge types
Provenance	None	None	None	Schema-dependent	Complete lineage
Temporal Nav.	Point-in-time	Current window	Current window	Mostly current	Full history + tags
Consolidation	None	Manual / rule	N/A	Batch ETL	LLM Dream State

Table 8: Comparative analysis across nine evaluation dimensions.

Feature	Graphiti	Mem0g	A-MEM	Letta	MAGMA	Hindsight	MemOS	Kumiho
Property graph storage	✓	✓	(✓)	$\times$	✓	$\times$	$\times$	✓
Hybrid retrieval ( $\geq$ 2 modalities)	✓	(✓)	$\times$	$\times$	(✓)	(✓)	$\times$	✓
Immutable revision history	(✓)	(✓)	$\times$	(✓)	$\times$	$\times$	$\times$	✓
Formal belief revision	$\times$	$\times$	$\times$	$\times$	$\times$	$\times$	$\times$	✓
URI-based addressing	$\times$	$\times$	$\times$	$\times$	$\times$	$\times$	$\times$	✓
Typed edge ontology ( $\geq$ 6)	(✓)	$\times$	(✓)	$\times$	(✓)	$\times$	$\times$	✓

Table 9: Feature comparison with concurrent agent memory systems (as of Feb 2026). ✓ = present, (✓) = partial,

\times

= absent.

#	Principle	Category
1	Structural Reuse	Structure
2	Universal Addressability	Structure
3	Immutable Rev., Mutable Ptr.	Formal
4	Explicit Over Inferred Rel.	Formal
5	Non-Blocking Enhancement	Performance
6	Conservative Memory Mgmt.	Safety

Table 10: Core design principles.

Figure 1: Kumiho dashboard showing the AI Cognitive Memory browser. The selected node ( kumiho.io dashboard Memory page redesign with graph visualization ) displays its summary, kref URI, revision tag ( r=1 , latest ), and creation date. The force-directed graph on the right visualizes typed edges to related memories. Stats cards show total memories (19), spaces (9), connections for the selected memory (3), and Dream State recency (4 days ago). The same graph, SDK, and API that agents use to manage work products is exposed here for human inspection.

Type	Summary	Raw	Ratio
Simple fact	${\sim}$ 12	500	42 $\times$
Preference	${\sim}$ 18	800	44 $\times$
Profile	${\sim}$ 80	4K	50 $\times$
Paper session	${\sim}$ 65	12K	185 $\times$
Planning	${\sim}$ 90	25K	278 $\times$

Table 11: Token compression ratios.

System	Single	Multi	Temp.	Open	Overall	Source
Zep	0.357	0.194	0.420	0.496	—	Zep (2025)
OpenAI Mem	—	—	—	—	${\sim}$ 0.34	Zep (2025)
Mem0	0.387	0.286	0.489	0.477	${\sim}$ 0.40	Zep (2025)
Mem0-Graph	0.381	0.243	0.516	0.493	${\sim}$ 0.40	Zep (2025)
Memobase	0.463	0.229	0.642	0.516	—	Memobase (2025)
ENGRAM	0.231	0.183	0.219	0.086	0.211	Patel and Patel (2025)

Table 12: LoCoMo token-level F1: cross-system comparison (four retrieval categories).

Category	$n$	F1
Single-hop	841	0.462
Multi-hop	282	0.355
Temporal	321	0.533
Open-domain	96	0.290
Retrieval average	1,540	0.447
Adversarial (refusal acc.) †	446	0.975

Table 13: LoCoMo per-category breakdown (

n{=}1{,}986

Innovation	LoCoMo-Plus	LoCoMo F1
Prospective idx	Bridges cue-trigger gap	Improves temporal/multi-hop
Event extraction	Preserves causal chains	Preserves factual detail
LLM reranking	100% goal retrieval hit	Better sibling selection
Graph-aug. recall	Connected memory discovery	Multi-hop 0.355 (best)

Table 14: Architecture consistency across benchmarks.

System	Model	Acc. (%)
RAG (text-ada-002)	text-ada-002	23.5
RAG (text-embed-small)	text-embed-small	24.9
RAG (text-embed-large)	text-embed-large	29.8
Mem0	Various	41.4
A-MEM	Various	42.4
SeCom	Various	42.6

Table 15: LoCoMo-Plus: Kumiho vs. published baselines (

n{=}401

Type	$n$	Correct	4o (%)	4o-mini (%)
Causal	101	97	96.0	96.0
State	100	96	96.0	95.0
Value	100	96	96.0	${\sim}$ 89
Goal	100	85	85.0	${\sim}$ 73
Overall	401	374	93.3	$\mathbf{\sim}$ 88

Table 16: LoCoMo-Plus accuracy by constraint type (

n{=}401

Time Gap	$n$	Acc. (%)	Notes
$\leq$ 2 weeks	35	88.6	More goal-type entries
2 wk – 1 mo	77	97.4	Peak performance
1 – 3 mo	164	93.9	Largest cohort
3 – 6 mo	93	93.5	No degradation
$>$ 6 mo	32	84.4	Cliff eliminated

Table 17: LoCoMo-Plus accuracy by time gap (

n{=}401

, GPT-4o answer).

Post.	Simple	Multi	Chain	Temp.	Adv.	Pass
$K*2$	✓	✓	✓	✓	✓	100%
$K*3$	✓	✓	✓	✓	✓	100%
$K*4$	✓	✓	✓	✓	✓	100%
$K*5$	✓	✓	✓	✓	✓	100%
$K*6$	✓	✓	–	✓	✓	100%
Rel.	✓	✓	✓	✓	✓	100%

Table 18: AGM Compliance Verification (49 scenarios).

Graph-Based Agent Memory

Graph-based agent memory organizes an agent’s experiences, facts, and procedures as linked structures for persistent, evidence-aware retrieval and reuse.

See all 133 papers

MemCog: From Memory-as-Tool to Memory-as-Cognition in Conversational Agents
May 27, 2026Zihan Li, Xingyu Fan, Feifei Li +1Conversational Memory AI Agent Benchmarks
WeChat, Tencent Inc., Beijing, China
Memanto: Typed Semantic Memory with Information-Theoretic Retrieval for Long-Horizon Agents
Apr 23, 2026Seyed Moein Abtahi, Rasa Rahnema, Hetkumar Patel +3Agent Memory Information Retrieval
Moorcheh AI EdgeAI Innovations
Storage Is Not Memory: A Retrieval-Centered Architecture for Agent Recall
May 6, 2026Joshua Adler, Guy ZehaviAgent Memory LLM Agent Memory
Sauron Labs

May 27, 2026J/K move · Enter open · S save

MemCog: From Memory-as-Tool to Memory-as-Cognition in Conversational Agents

Zihan Li, Xingyu Fan, Feifei Li, Wenhui Que

WeChat, Tencent Inc., Beijing, China

Conversational Memory AI Agent Benchmarks Graph-Based Agent Memory Memory-Augmented Agents Agent Memory Management

Open paper AskPDF arXiv

Existing agent memory systems universally follow what we term a Memory-as-Tool paradigm where a single query triggers one-shot retrieval of flat passage lists, suffering from passive invocation, reasoning-retrieval decoupling, and structural mismatch between retrieved fragments and the agent's navigational needs. We propose MemCog, a Memory-as-Cognition system that makes memory access an integral part of the reasoning process. MemCog organizes user knowledge as Navigable Memory Store with associative link graphs, exposes Cross-Dimensional Navigation Interface for multi-step reasoning-driven traversal, and employs Proactive Reasoning Protocol that drives agents to spontaneously initiate memory exploration from conversational context. We additionally construct ProactiveMemBench, the first benchmark for evaluating proactive memory triggering. Experiments show that MemCog achieves state-of-the-art on passive QA benchmarks (92.98 on LoCoMo, 95.8 on LongMemEval) while substantially outperforming baselines on ProactiveMemBench, demonstrating the advantage of Memory-as-Cognition.

Abstract

Graph-Based Agent Memory

Explore similar work

MemCog: From Memory-as-Tool to Memory-as-Cognition in Conversational Agents

Memanto: Typed Semantic Memory with Information-Theoretic Retrieval for Long-Horizon Agents

Storage Is Not Memory: A Retrieval-Centered Architecture for Agent Recall