MemForest: Cutting Agent Memory Write Costs from O(N) to O(log N)
> Source: MemForest: An Efficient Agent Memory System with Hierarchical Temporal Indexing, ICML 2026, https://arxiv.org/abs/2605.23986
The Problem: Writes Are 10x Slower Than Reads
Existing agent memory systems optimize retrieval but ignore writing. Turning a finished conversation into usable memory requires:
1. Extraction: an LLM converts raw dialogue into structured records 2. Maintenance: merging, updating, and rewriting the existing memory state 3. Retrieval: recalling relevant context at query time
While reads are highly optimized, writes stall on synchronous LLM calls and full-state rewrites. Testing shows (Figure 1) that the write path accounts for 70%–90% of total latency. More memory means slower writes; state-of-the-art baselines like EverMemOS are locked into a serial pipeline.
MemForest's thesis: the problem is not slow LLMs, but an architecture that forces the LLM to serially process the entire memory state.
Two Structural Bottlenecks
Bottleneck 1: Serial extraction. Each new session requires the LLM to read, extract, summarize, reconcile, and rewrite from scratch — high interaction rates create long queues.
Bottleneck 2: Full-rewrite maintenance. Mutable state (user profiles, global summaries, core memory docs) must be re-read and rewritten whenever new evidence arrives, pushing maintenance cost from O(1) to O(N).
Two common failure modes:
- Independent records + embedding retrieval: embeddings don't encode temporal relations, so queries like "Where did Bob live before moving?" may return the most recent or most similar record rather than the true predecessor.
- Mutable summaries: fast current-state lookup, but intermediate states and transition evidence are compressed away.
- Leaves: temporally local evidence (raw chunks or extracted facts)
- Internal nodes: summaries of contiguous intervals
- Root: coarse-grained recall
- Write: insert new evidence, refresh only the affected dirty path — O(log N) by tree height, not O(N) by memory size
- Read: recall relevant trees, then navigate top-down from interval summaries to leaf evidence (coarse-to-fine)
- Maintain: persistent state is separated from derived artifacts (summaries, embeddings, index rows), which can be selectively refreshed
- Parallel vs. serial extraction: latency drops from O(session length) to O(chunk size), approaching constant with enough concurrency
- MemTree vs. flat records: avoids wrong-time retrieval, O(N) mutable-summary costs, and loss of intermediate states
- Localized vs. full-rewrite maintenance: only dirty paths refresh; derived artifacts regenerate selectively
- Code not yet released, limiting reproducibility
- Broad multi-hop reasoning in LoCoMo remains challenging; scoped organization may limit cross-scope evidence combination
- Highly parallel extraction requires sufficient compute; smaller deployments may see reduced gains
- Canonical-fact normalization quality directly affects downstream maintenance; failures can introduce noise
- MemForest: An Efficient Agent Memory System with Hierarchical Temporal Indexing, ICML 2026, https://arxiv.org/abs/2605.23986
- Authors: Han Chen, Zining Zhang, Wenqi Pei, Bingsheng He, Ming Wu, Jason Zeng, Michael Heinrich, Wei Wu, Hongbao Zhang (NUS + Zero Gravity Labs)
MemForest Architecture
MemForest reframes agent memory as a write-efficient temporal data management problem, inspired by write-optimized database indexes (LSM-trees), but maintaining persistent agent memory rather than key-value state.
| Layer | Function | Key decision | |-------|----------|--------------| | Parallel extraction | New conversations split into independent chunks processed concurrently | LLM removed from write critical path | | Canonical fact merging | Fragmented extraction outputs normalized into routable units | No immediate global-state rewrite needed | | MemTree indexing | Temporally scoped memories organized as time-ordered trees | Local updates replace full rewrites |
MemTree: Hierarchical Temporal Index
Each temporal scope (e.g., "Bob's residence history") maps to a tree:
Canonical Facts: Stable Write Units
Fragmented parallel-extraction outputs are normalized into canonical facts containing retrieval-ready text, source-session references, entity mentions, topical signals, and temporal anchors. This decouples extraction from maintenance without repeatedly re-reading history.
Experiments: Speed-Accuracy Pareto Frontier
LongMemEval-S (Qwen3-30B):
| Method | pass@1 accuracy | Write throughput (vs. EverMemOS) | |--------|-----------------|----------------------------------| | EverMemOS | ~75% | 1x | | MemPalace | Lower | Higher (append-only raw chunks) | | MemForest | 79.8% | ~6x |
MemForest beats all stateful baselines on accuracy while achieving 6x EverMemOS's write throughput.
LoCoMo (multi-turn dialogue benchmark): strong on temporally structured long-context QA; competitive but not dominant on broad multi-hop compositional reasoning.
Notably, knowledge-update and temporal-reasoning questions make up 42.2% of LongMemEval-S, and multi-session questions 26.6% — exactly MemTree's sweet spot.
Validated Design Choices
Limitations
Takeaway: Memory Systems Need Database Thinking
MemForest's core insight: agent memory research has long ignored the write path because memory was treated as a retrieval problem, not a data management problem. Write costs are paid on every new session, repeatedly. By applying LSM-tree-style local updates, MemForest reduces maintenance from O(N) to O(log N) — an architectural reclassification rather than incremental improvement. As agents run for weeks or months and memory grows from KB to GB, write efficiency becomes decisive.
> "Memory isn't read into existence — it's written. Write well, and reads will follow."
References