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

As AI agents evolve to handle complex, multi-day tasks, they require a way to remember past interactions. Much like a human assistant must track user preferences across weeks of dialogue, these agents need "memory" to persist state across multiple sessions. However, building these memory systems is not just about accuracy. It involves significant computational overhead.

A new study from researchers at Stanford and KU Leuven reveals that the cost of managing this memory is often hidden from the user. While developers typically focus on how accurately an agent recalls a fact, the authors find that the energy and time spent "constructing" the memory often dwarfs the cost of actually answering a question.

The limits of long-context windows

Currently, many developers attempt to solve the memory problem by simply feeding the entire interaction history into the LLM's context window. This is akin to a student trying to pass an exam by reading every single notebook they have ever written every time a question is asked. While modern models boast massive context windows, this approach hits three walls.

First, continuous interactions eventually exceed any fixed budget. Second, the "prefill" cost (the computational effort required to process all input tokens before the model begins generating text) scales quadratically with history length. Third, models suffer from performance degradation in long sequences. They often lose track of facts buried in the middle of the context .

External memory systems aim to decouple capacity from context length by retrieving only what is necessary. However, the authors argue that we currently lack a clear understanding of the systemic costs these architectures impose.

A taxonomy of memory architecture

To analyze these systems, the authors introduce a taxonomy. It classifies agent memory into four distinct paradigms based on how they manage the "write path" (storing information) and the "read path" (retrieving it).

1. Long-context memory: The simplest form. The entire history is passed directly to the model. There is no specialized construction or storage.
2. Flat RAG memory: This treats memory like a digital filing cabinet. It uses deterministic processes, such as keyword indexing (BM25) or vector embeddings (mathematical representations of text meaning), to store raw history chunks. It does not use an LLM to summarize them.
3. Structure-augmented RAG: These systems use an LLM as a fixed extractor. They pull out specific facts, entities, or relationships. This creates an organized "knowledge graph" or a list of atomic facts. This makes retrieval more precise but requires an upfront LLM cost to build the structure.
4. Agentic control flow: The most complex tier. Here, the LLM acts as its own librarian. The agent decides when to write a memory and which tool to use to search .

Construction consumes the lifecycle

The study’s most striking finding is that the "construction" phase dominates the agent's operational lifecycle. This phase involves the heavy lifting required to ingest and organize data. The authors used a phase-aware profiling harness to attribute costs to construction, retrieval, and generation.

The researchers report that for many sophisticated systems, the energy consumed during construction exceeds the energy used during the actual query phase. When looking at "energy per correct answer," the authors find a massive spread. The difference between a simple system like BM25 and a complex agentic system can exceed 47× .

This means complex systems can be vastly more expensive to run for the same level of accuracy.

Furthermore, the computational shape of construction is highly specific. The authors find that construction is a "long-read, short-write" workload. It is heavily dominated by LLM prefill and embedding tasks. The median decode share (the tokens the model actually generates) is only 4.6% .

This creates a structural conflict. Construction is a high-throughput, background task. Conversely, querying is a latency-sensitive, interactive task. Running them on the same hardware can cause large construction jobs to stall the scheduler. This delays user responses.

Hidden scaling costs and latency tails

The authors also highlight how different choices impact how an agent scales as a user's history grows. In agentic systems (Paradigm IV), the cost of adding new information can scale super-linearly. As the memory store grows, the agent must perform more complex tool calls. It must decide how to merge or rewrite existing records. This causes the token cost per ingestion to climb .

Latency profiles also diverge sharply. Deterministic systems, like those using flat RAG, have predictable, narrow "tails." This means the difference between an average response and a slow one is small. In contrast, LLM-bounded systems exhibit much wider latency tails . This unpredictability occurs because the model decides how many steps to take during the retrieval process.

Limits of the characterization

While the study provides a rigorous framework, it does not address several emerging frontiers. The researchers note they have not explored multi-node or multi-agent deployments. These environments introduce complexities regarding distributed coordination and data consistency. Additionally, the characterization focuses on text. The implications of multimodal memory—incorporating images, audio, and sensor data—remain an open question. Such data would likely amplify the storage footprints and construction costs identified here.

The verdict: Match the workload to the architecture

Is there a "best" memory system? According to the authors, the answer depends entirely on your deployment constraints. No single system maximizes accuracy, low latency, and low construction cost simultaneously .

If you are building a high-volume service with stable histories, you should favor systems that move work into the construction phase. This minimizes per-query latency. If you are dealing with continuous, rapid-fire data ingestion with sparse queries, prioritize low-cost, append-only construction. Ultimately, the authors suggest that engineers must treat memory as a core system-level decision. Accuracy is important, but uncontrolled construction costs will eventually make your agent too expensive to run.

Figures from the paper