Technical Summary: Agent Memory: Characterization and System Implications of Stateful Long-Horizon Workloads

Problem Statement

Large Language Model (LLM) agents are increasingly deployed for long-horizon tasks requiring sustained reasoning over extended interaction histories, such as personal assistants tracking preferences over weeks or code agents maintaining project context across sessions. While early LLMs relied on parametric knowledge and Retrieval-Augmented Generation (RAG) decoupled knowledge from parameters using static external corpora, stateful agents require a mutable memory corpus produced by the agent's own interaction stream.

Relying solely on the model's context window for memory faces three fundamental limits:

1. Capacity: Continuous multi-session interactions inevitably exceed fixed context budgets.
2. Cost: Prefill costs scale quadratically with history length, and KV-cache memory pressure becomes unmanageable across sessions due to cache eviction.
3. Fidelity: Reasoning and recall degrade in long sequences, exhibiting a "U-shaped" performance curve where middle-context facts are lost.

Consequently, agents require external memory systems to persist, selectively retrieve, and update state. However, a rich ecosystem of agent memory systems has emerged with diverse designs (flat retrieval, LLM-mediated extraction, graph-based structures, agentic control flows), yet their system-level behavior remains uncharacterized. Existing benchmarks focus purely on downstream accuracy, ignoring the asymmetric redistribution of computational costs (construction vs. retrieval) that critically impact deployment at scale.

Methodology

The authors present the first systems characterization of agent memory algorithms, spanning the full design space.

1. Taxonomy and Workload Suite

The study introduces a system-oriented taxonomy classifying ten representative agent memory systems along four axes: construction, storage, retrieval, and mutability. These systems are categorized into four paradigms:

• Paradigm I: Long-context memory: Uses the model context itself (e.g., long_context).
• Paradigm II: Flat RAG memory: Deterministic indexing (lexical or vector) without LLM construction (e.g., BM25, EmbedRAG).
• Paradigm III: Structure-augmented RAG memory: Uses an LLM as a fixed extractor to derive facts, summaries, or graphs. Subdivided into append-only (e.g., GraphRAG, HippoRAG v2) and consolidating (e.g., Mem0, SimpleMem).
• Paradigm IV: Agentic control flow: Exposes memory operations to the LLM as part of the decision loop (e.g., A-Mem, Letta, MIRIX).

The evaluation utilizes two benchmark suites:

• MemoryAgentBench (MAB): Evaluates retrieval, test-time learning, long-range understanding, and selective forgetting. The study focuses on LongMemEval_S_* (approx. 360K tokens history, 60 queries per sample) to separate construction costs from retrieval.
• MemoryArena: Contains multi-session tasks to expose freshness-latency tradeoffs in continuous ingestion scenarios.

2. Profiling Harness

The authors built a phase-aware profiling harness (to be open-sourced) that attributes costs to three logical phases: construction, retrieval, and generation.

• API Telemetry: Instruments chat-completion and embedding requests to track token volume, call structure, and latency.
• Hardware Telemetry: Samples GPU counters (NVML/DCGM) to measure power, utilization, VRAM footprint, and energy.
• Experimental Setup: Experiments were run in two regimes: remote construction (OpenAI API) and local construction (NVIDIA H100 with vLLM serving Qwen3 models).

Key Contributions

1. System-Oriented Taxonomy: A classification of agent memory systems along four axes with predicted cost signatures per paradigm.
2. Phase-Aware Profiling: A harness tracking tokens, model calls, GPU utilization, and latency across construction, retrieval, and generation.
3. Comprehensive Characterization: Analysis of construction cost shapes, capability thresholds, amortization structures, freshness scheduling, footprint growth, and retrieval tail behavior.
4. Ten System Recommendations: Actionable guidelines for infrastructure, scheduling, and system selection.

Key Results and Insights

1. Construction Dominates the Lifecycle

Contrary to the assumption that query-time serving is the primary cost, construction energy dominates the agent lifecycle for LLM-mediated systems.

• Energy Spread: Total energy per correct answer varies by over 47× across the suite (from ~4.1 kJ for BM25 to ~185.9 kJ for Letta).
• Cost Shift: Paradigms III and IV shift the majority of end-to-end energy into the construction phase, which is invisible to the user at query time.
• Implication: Accuracy metrics alone are insufficient; operators must account for lifecycle energy, which varies by an order of magnitude even for systems with similar accuracy.

2. Construction is Prefill- and Embedding-Dominated

Construction is structurally a "long-read, short-write" workload dominated by embedding and LLM prefill, with minimal decode time (median decode share is 4.6%).

• Traffic Patterns: Paradigm III.a systems generate large-batch offline indexing traffic, while Paradigms III.b and IV generate sequential, per-event traffic.
• Conflict: Routing both construction (throughput-oriented) and QA (latency-sensitive) through the same endpoint causes head-of-line blocking. Construction jobs occupy KV-cache headroom, stalling latency-sensitive queries.

3. Construction-LLM Choice is Algorithm-Constrained

Operators can downscale the LLM used for construction to reduce costs, but the safe range is algorithm-dependent.

• Graceful Degradation: Systems without hard output contracts (e.g., Mem0, SimpleMem) tolerate smaller construction LLMs with smooth accuracy degradation.
• Capability Floors: Systems with strict output contracts (e.g., MIRIX requiring specific JSON schemas) exhibit a hard floor; falling below a certain model capability (e.g., Qwen3-1.7B) corrupts the memory store entirely, rendering it unusable.

4. The Construction–Serve–Accuracy Frontier

No single system is optimal across construction cost, per-query latency, and accuracy.

• Tradeoffs: BM25 offers fast construction and high aggregate accuracy but slower query times. Mem0 offers the fastest query latency but incurs massive construction costs and lower accuracy.
• Selection: High-volume query workloads favor systems that move work into construction; continuous-ingestion workloads favor low-construction-cost systems.

5. Freshness–Latency Tradeoff in Continuous Sessions

In multi-session workloads, per-session construction time spans five orders of magnitude (from sub-millisecond for BM25 to tens of seconds for Letta).

• Scheduling Dilemma: If construction time exceeds the inter-session arrival interval, operators face a choice: synchronous scheduling (exposing high latency to the user) or asynchronous scheduling (serving stale memory).
• Implication: For strict cross-session dependencies, cumulative construction and retrieval time must be treated as a hard feasibility constraint.

6. Footprint and Token Cost Divergence

• Storage: Per-user memory footprints vary by ~9× at 1M tokens. Multi-view designs inflate storage; consolidating systems can compress it.
• Token Cost: Paradigm IV agentic systems scale super-linearly in token cost as memory stores grow, because each new ingestion queries the expanding store. This makes long-term costs for agentic systems disproportionately expensive compared to their initial footprint.

7. Latency Structure and Tail Behavior

• Deterministic vs. LLM-Bounded: Deterministic systems (Paradigm II) have narrow latency tails (p95/p50 ~1.3×). LLM-bounded systems (Paradigms III/IV) exhibit wide tails (up to 5.9×) because runtime LLM decisions can introduce variable numbers of reasoning or tool-use steps.
• Recommendation: LLM-bounded systems require external iteration caps and timeouts to bound worst-case costs.

Significance and Claims

The paper claims to provide the first systems characterization of agent memory workloads, revealing that design choices drastically and asymmetrically redistribute costs in ways invisible to accuracy metrics.

• System-Level Decision: The authors argue that agent memory system selection must be treated as a system-level decision, not just an accuracy optimization.
• Infrastructure Implications: The work highlights that agent memory imposes system needs beyond traditional LLM serving, specifically requiring distinct handling for construction (background throughput) vs. retrieval (latency-sensitive) and careful management of freshness-latency tradeoffs.
• Modest Scope: The authors acknowledge that their characterization is based on single-node, single-agent scenarios. They note that multi-node/multi-agent consistency and multimodal memory are emerging frontiers not captured in this study, but the proposed taxonomy and methodology provide a foundation for future characterization.

The paper concludes with 10 specific recommendations for operators, covering construction scheduling, capability floors, amortization via query volume, freshness-latency tradeoffs, and fleet-scale management, aiming to guide the deployment of stateful agents at scale.