MemForest: Cutting Agent Memory Write Overhead from O(N) to O(log N) with Hierarchical Temporal Trees
> 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 neglect 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 existing memory state 3. Retrieval: recalling relevant context at query time
Benchmarks show the write path accounts for 70%–90% of total latency. The more memories accumulate, the slower writes become. State-of-the-art baselines like EverMemOS lock throughput into a serial pipeline. MemForest's thesis: the problem isn't that LLMs are slow — it's that the architecture forces the LLM to serially process the entire memory state.
Two Structural Bottlenecks
Bottleneck 1: Serial extraction. Each new session makes the LLM read, extract, summarize, reconcile, and rewrite from scratch. High interaction rates create long queues.
Bottleneck 2: Full-state rewrite maintenance. User profiles, global summaries, and core memory documents are mutable state; every new evidence triggers a full re-read and rewrite. As memories grow from 10 to 1,000 records, maintenance cost rises from O(1) to O(N).
Two common failure modes:
- Independent records + embedding retrieval: embeddings don't encode temporal relations — asking "where did Bob live before moving?" may return the latest or most similar record instead of the true predecessor.
- Mutable summaries: fast lookup of current state, but intermediate states and transition evidence are compressed away.
- Leaves: preserve time-local evidence (raw chunks or extracted facts)
- Internal nodes: summarize contiguous intervals
- Root: supports coarse-grained recall
- Parallel vs. serial extraction: chunked parallel extraction reduces latency from O(session length) to O(chunk size), approaching constant with enough concurrency.
- MemTree vs. flat records: independent records cause wrong-time retrieval; mutable summaries cost O(N) and lose intermediate states; MemTree updates at O(log N) while preserving the full temporal trajectory.
- Local vs. full maintenance: only dirty paths are refreshed; derived artifacts regenerate selectively.
- Code not yet released, limiting reproduction
- Broad multi-hop reasoning on LoCoMo remains challenging; scoped organization may limit cross-scope evidence combination
- Highly parallel extraction needs sufficient compute; small 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: Write-Optimized Database Thinking
MemForest reframes agent memory as a write-efficient temporal data management problem, inspired by write-optimized database indexes (LSM-trees).
| Layer | Function | Key Decision | |-------|----------|--------------| | Parallel extraction | New conversations split into independent chunks processed concurrently | LLM removed from the write critical path | | Canonical fact merging | Fragmented extraction outputs normalized into routable units | No immediate global-state rewrite | | MemTree index | Temporal-scope 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:
On write, new evidence inserts into the scope's tree and only the affected dirty path is refreshed — cost depends on tree height, O(log N), not total memory size N. On retrieval, the system recalls relevant trees, then navigates from interval summaries down to leaf evidence, coarse-to-fine. Derived artifacts (summaries, embeddings, indexes) can be selectively refreshed rather than fully rebuilt.
Canonical Facts: Stable Write Units
Parallel extraction produces fragmented output. MemForest normalizes it into canonical facts containing retrieval-ready text, source-session references, entity mentions, topical signals, and temporal anchors. This makes new evidence mergeable and routable without repeatedly re-reading history, decoupling extraction from maintenance.
Experiments: A Better Speed–Accuracy Pareto Frontier
LongMemEval-S (Qwen3-30B):
| Method | pass@1 Accuracy | Write Throughput (vs. EverMemOS) | |--------|-----------------|----------------------------------| | EverMemOS | ~75% | 1x | | MemPalace | Lower | Higher (append-only chunks) | | MemForest | 79.8% | ~6x |
MemForest beats all stateful baselines on accuracy while delivering ~6x EverMemOS's throughput. On LoCoMo, it excels at temporally structured long-context QA but faces stiff competition 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.
Design Validation
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 rather than a data-management problem. Writes recur with every session and ultimately determine scalability. By applying LSM-tree-style local-update philosophy, MemForest pushes maintenance from O(N) to O(log N) — an architectural reclassification, not an incremental tweak. As agents run for weeks or months and memory grows from KB to GB, write efficiency becomes decisive.
References