Source-linked AI summary
Evaluating Memory Structure in LLM Agents
Alina Shutova, Alexandra Olenina, Ivan Vinogradov, Anton Sinitsin
TL;DR
Long-term memory benchmarks often test recall tasks that do not require complex memory hierarchies, leaving memory organization insufficiently evaluated. The paper introduces StructMemEval, a benchmark of structured knowledge-organization tasks, and finds that retrieval-only systems fail as complexity grows while agentic memory performs better but remains imperfect and sensitive to prompting.
Problem
Existing long-term memory benchmarks emphasize recall and related queries, while recent results show that such tasks may not require complex memory architectures.
Method
StructMemEval evaluates agents on tasks requiring construction of tree, state, counting, and recommendation structures from message histories.
Results
Retrieval-only systems solve small tasks but decline as complexity grows, whereas memory agents scale better and achieve higher accuracy, though not perfectly.
Takeaways & Limitations
Memory organization is a distinct capability: agents can solve structured tasks more reliably when prompted with an organization strategy, but may fail to recognize that structure unaided.
Takeaways & Limitations
Main evaluations use no multiple random seeds, making individual subset-level accuracies potentially noisy, and proprietary models may later be deprecated.
Abstract
from arXiv · showhide
Modern LLM-based agents and chat assistants rely on long-term memory frameworks to store reusable knowledge, recall user preferences, and augment reasoning. As researchers create more complex memory architectures, it becomes increasingly difficult to analyze their capabilities and guide future memory designs. Most long-term memory benchmarks focus on simple fact retention, multi-hop recall, and time-based changes. While undoubtedly important, these capabilities can often be achieved with simple retrieval-augmented LLMs and do not test complex memory hierarchies. To bridge this gap, we propose StructMemEval - a benchmark that tests the agent's ability to organize its long-term memory, not just factual recall. We gather a suite of tasks that humans solve by organizing their knowledge in a specific structure: transaction ledgers, to-do lists, trees and others. Our initial experiments show that simple retrieval-augmented LLMs struggle with these tasks, whereas memory agents can reliably solve them if prompted how to organize their memory. However, we also find that modern LLMs do not always recognize the memory structure when not prompted to do so. This highlights an important direction for future improvements in both LLM training and memory frameworks.
1 Introduction
As LLM tasks grow longer and harder, finite working memory makes external long-term memory necessary. StructMemEval tests whether agents can organize knowledge into task-specific structures rather than merely retrieve facts.
- Longer, harder LLM tasks make it infeasible to keep all information in working memory.
- Long-term memory lets agents offload knowledge to an external database and retrieve it when needed.
- Existing benchmarks mainly test single-hop, multi-hop, and time-based fact recall, which simple retrieval systems can sometimes solve without complex memory architectures.
- StructMemEval focuses on agents organizing knowledge into structures such as graphs, to-do lists, categorized events, and running statistics.
- The benchmark uses ledger, graph, state-tracking, and related tasks that retrieval-augmented agents find difficult, while prompted memory agents solve them more reliably.
2 Background
Long-term memory extends limited transformer working memory through external storage, but existing benchmarks often emphasize recall rather than complex memory organization. This motivates evaluating memory architectures on structured tasks.
- Transformer agents store task-specific information in a KV cache whose capacity is limited for modern models.
- External long-term memory bypasses KV-cache limits by storing knowledge in a database and retrieving it later.
- Memory-augmented LLMs must update stored knowledge when tasks involve changing user preferences or working memory.
- Memory research spans structures including knowledge graphs, hierarchies, cognitive-inspired systems, and note-taking frameworks.
- Existing benchmarks commonly test fact recall, multi-hop lookups, and updates over time, but recent work finds that simple retrieval can outperform complex memory structures on them.
3 StructMemEval
StructMemEval evaluates whether agents can construct and use task-appropriate memory structures across tree, state, counting, and recommendation problems. Its scenarios are designed to isolate memory organization and include optional hints for diagnosing organization versus execution errors.
- Task categories: Tree tasks require maintaining hierarchical relations and answering indirect queries over family or corporate graphs.
- Task categories: State-tracking tasks require following entity state transitions over time, while counting tasks require reconciling totals such as net settlements.
- Task categories: Recommendation tasks aggregate event histories and user feedback into preference judgments and running statistics rather than individual recall.
- Data curation: The dataset includes 207 scenarios and more than 2,000 evaluation questions spanning 10 to 500 messages.
- Benchmark design: StructMemEval contains 51 main problems across tree-based, count-based, state-tracking, and recommendation categories, each with at least 250 messages.
- Benchmark design: The extended set contains 207 scenarios used primarily to analyze scaling across problem lengths, models, memory architectures, and retrieval systems.
- Diagnostic methodology: Optional organization hints diagnose whether failures arise from choosing the wrong structure or from maintaining or using that structure poorly.
4 Evaluations & Analysis
The evaluations test whether agents can organize long-term memory across task sizes, memory frameworks, backbone LLMs, and explicit organization hints. Retrieval-only systems handle small tasks but degrade with complexity, while memory agents scale better; performance remains model- and task-dependent, with distinct structural and hallucination failures.
- 4.1 Retrieval and Memory at Different Problem Sizes: Retrieval-only systems solve small tasks reliably but quickly fail when task complexity exceeds the retrieval window, whereas memory agents scale better on complex scenarios.This comparison spans graph, state-tracking, and accounting tasks, with complexity measured by edges, state transitions, or transactions.
- 4.2 Evaluating Memory Architectures and LLM Controllers: All tested Mem-agent backbones outperform retrieval baselines to some extent, but subset performance varies substantially, with both flash models performing poorly on count-based accounting tasks.Backbones include gemini-3.0-flash, gemini-3.1-pro, gpt-5.5, deepseek-v4-flash, and deepseek-v4-pro.
- 4.3 Memory Organization Hints: Organization hints significantly improve memory-agent performance but do not produce perfect accuracy, and deepseek-v4-flash still achieves zero accuracy on count-based tasks despite detailed prompts.The gap between hinted and unhinted agents is larger than the difference between Mem0 and Mem-agent.
- 4.4 Error Analysis with and without Organization Hints: Without hints, tree-based agents inconsistently partition graphs and miss bidirectional links, while state-tracking agents store connected entries separately and fail to propagate updates.These errors reflect failures to maintain the structure required by the task.
- 4.4 Error Analysis with and without Organization Hints: Count-based failures mainly involve skipped, duplicated, or spurious transactions, where one erroneous record can make the final settlement incorrect over long histories.The accounting subset is especially sensitive because unrelated messages create more opportunities for hallucinated records.
5 Discussion
StructMemEval shows that retrieval-only systems struggle with structured-memory problems, while agentic memory systems perform better but remain imperfect. The authors identify memory-organization errors and hallucinations as major failure sources, while noting noisy subset-level results and proprietary-model availability constraints.
- Retrieval-only systems cannot solve StructMemEval problems, whereas flexible agentic memory systems achieve significantly higher but still imperfect accuracy.
- Wrong answers are largely caused by suboptimal memory organization and hallucinations.
- As interactions lengthen, previously tolerable hallucination rates become problematic for memory-augmented LLMs.
- The main evaluations use no multiple random seeds, so aggregate conclusions are supported but individual subset accuracies can be noisy.
- The study evaluates proprietary LLMs whose availability windows are limited, while also including open-weights models to reduce this dependency.
A Details on Data Collection
StructMemEval scenarios are created through manual task design, LLM-based augmentation, and human verification. The collection covers accounting, recommendation, tree-based, and state-tracking tasks with task-specific scaling and generation procedures.
- Data collection manually creates feasible scenarios, expands them with LLM-generated variants and questions, then verifies scenarios and reference answers by hand.
- Accounting problems: Accounting scenarios vary transaction examples and introduce 10%, 30%, or 50% unrelated messages to test final net settlements.
- Recommendation problems: Recommendation scenarios require exact statistics about activities tried and liked over prolonged user interactions, challenging top-k retrieval.
- Tree-based problems: Tree tasks encode family graphs with unique names, select 10-hop shortest paths, and scale message subsets from 10 to 250 links.
- State tracking problems: State-tracking tasks progress from static controls to scenarios containing up to five state changes affecting final outcomes.
B Details on Memory Frameworks
The evaluation compares retrieval-only, markdown-based mem-agent, and agentic Mem0 memory configurations. It deliberately uses minimal tuning because framework settings and model choice can materially affect results.
- The study evaluates retrieval-augmented LLMs, mem-agent memory, and Mem0 agentic memory configurations.
- Retrieval-augmented LLM: The retrieval baseline searches Mem0’s vector store and feeds retrieved results to the main LLM for answer composition.
- Mem-agent memory: Mem-agent provides locally editable markdown files that the agent can create, modify, and retrieve.
- Mem0 agentic memory: Mem0 agentic memory lets the LLM decide which memories to store and how to formulate retrieval questions.
- Evaluation scope: The initial evaluation avoids extensive hyperparameter tuning because frameworks expose many task-specific configuration choices.
- Evaluation scope: Experiments primarily use gemini-2.5-pro, with additional models evaluated because different backbones can score differently.
C.1 Count-based Tasks
The count-based evaluation compares different retrieval budgets for gemini-2.5-pro and gemini-3-pro. The reported setup indicates that agentic memory performs poorly across budgets in early count-based evaluations because of hallucinations.
- Early count-based evaluations vary retrieval budgets for gemini-2.5-pro under 10% and 30% noise conditions.
- Agentic memory fares poorly across all tested retrieval budgets in the early evaluation due to hallucinations.
- A detailed evaluation reports gemini-3-pro results across different retrieval budgets on count-based tasks.
C.2 State Tracking Tasks
State-tracking accuracy is reported by model, with transition-level results qualified as noisy because each sample is small and overall performance summarized by scenario averages.
- Accuracy is reported separately for each model on the state-tracking tasks.
- Per-transition results are noisy because the sample size is small.
- Avg. denotes the mean accuracy across all scenarios.
D Memory Organization Hints from Section 4.3
The tree-based memory hint specifies a self-managed markdown memory organized around one entity file per person and symmetric colleague links, with explicit procedures for updating and querying relationships.
- The paper provides a full memory-organization hint for tree-based problems, while prompts for state tracking, count-based tasks, and recommender systems appear in supplementary code.
- The system prompt defines an LLM agent that manages memory through Python code blocks.
- Each person receives one snake_case Markdown file whose first line is their full name and whose colleagues section lists direct links.
- Colleague relationships must be symmetric, so adding A–B requires updating both entity files in one Python block.
- Connectivity queries are answered by following colleague links one hop at a time until the target is found or no unvisited links remain.
E Additional Details for Error Analysis
The additional analyses identify accounting errors, model-specific response tendencies, and examples where responses rely on external world knowledge rather than the benchmark’s stored memories, alongside broader-impact considerations.
- Accounting-memory errors comprise omitted transactions, duplicated transactions, and hallucinated transactions, with hallucination identified as most significant.
- Deepseek-v4-flash tends toward short answers, whereas gemini-3.1-pro and gpt-5.5 more often produce one or more paragraphs.
- gpt-5.5-pro can use extensive real-world knowledge about locations and movies instead of relying on memory.
- Table 7 illustrates both a fabricated sandwich transaction absent from the conversation and duplicate entries for the same transaction.
- In the location example, the response recommends Capitol Hill activities even though the expected behavior specifies Alfama, Lisbon and Feira da Ladra.
- The benchmark’s possible indirect ramifications include both beneficial use cases and harmful applications such as doxing or exploiting network vulnerabilities.