Long-horizon language agents are becoming increasingly important for tasks that require persistent interaction, planning, and reasoning over extended trajectories. External memory plays a central role in these agents by preserving past states, transitions, and experiences beyond the limited context window. Existing memory systems, however, are typically evaluated mainly by task success and token cost, with much less attention to how memory usage is distributed across stored information. We show that repeated retrieval can produce heavy-tailed memory usage, where a small set of states is accessed frequently while many others are rarely retrieved and more prone to prediction errors. We study this phenomenon through a systematic tail audit across retrieval policies and graph structures. We find that memory concentration is reproducible but strongly policy-dependent, ranging from log-normal-compatible patterns under random walks to truncated-power-law-compatible heavy tails under semantic LLM policies. Motivated by these findings, we propose Core-Tail Memory Controller (CTMC), a rank-based memory controller that allocates prompt budget with a single exponent τ while preserving summarized information from the tail. Across Synthetic Graph World and ALFWorld, CTMC substantially reduces memory usage while preserving performance, and on LongMemEval it reduces prompt tokens by 24.48% while maintaining aggregate accuracy. These results show that heavy-tailed memory usage is both a measurable property of long-horizon agent memory and a practical signal for improving memory efficiency.
Figures & tables
Figure 1. CTMC agent loop. (a) Retrieve and rank candidates from structured memory. (b) Allocate context between a compact core and a summarized tail using rank-based CTMC. (c) Construct the LLM context, evaluate next-state predictions, and update memory from new interactions.
Method
Persistent memory
Retrieval control
Budget allocation
Tail-aware
Distributional diagnosis
Matched replay
AriGraph ( Anokhin et al., 2024 )
\ding 51
\ding 51
\ding 55
\ding 55
\ding 55
\ding 55
A-Mem ( Xu et al., 2025a )
\ding 51
\ding 51
\ding 55
\ding 55
\ding 55
\ding 55
Zep ( Rasmussen et al., 2025 )
\ding 51
\ding 51
\ding 55
\ding 55
\ding 55
\ding 55
Mem0 ( Chhikara et al., 2025 )
\ding 51
\ding 51
\ding 55
\ding 55
\ding 55
\ding 55
LightMem ( Fang et al., 2026 )
\ding 51
\ding 51
\ding 51
\ding 51
\ding 55
\ding 55
ACON ( Kang et al., 2025 )
\ding 55
\ding 51
\ding 51
\ding 55
\ding 55
\ding 55
Table 1. Comparison with related agent-memory systems. Methods are categorized by persistent-memory construction, retrieval control, explicit budget allocation, tail-aware representation, distributional diagnosis, and matched-replay analysis.
Figure 2. Memory audit and CTMC allocation pipeline. Memory-access traces are collected under random-walk and semantic LLM policies and audited for their tail behavior. The observed concentration then motivates CTMC, which ranks memory candidates and allocates the context budget between a compact high-priority core and a summarized tail according to b(r;τ)∝r−τ .
Graph family
σ100
σ500
σ1000
Slope
R2
uniform
0.152
0.802
1.364
0.505
0.967
exponential
0.333
0.900
1.369
0.433
0.971
scale-free
0.385
0.809
1.349
0.392
0.915
modular
0.162
1.461
1.366
0.573
0.874
mixed
0.231
1.252
1.430
0.541
0.975
baseline-symmetric
0.253
1.190
1.543
0.564
0.999
Table 2. Random-walk control across graph sizes. σtop10 is the standard deviation of access counts among the top 10% most accessed states.
Figure 3. Empirical CCDFs of memory access under random-walk and semantic policies, with fitted truncated-power-law (TPL) and log-normal tails above the estimated xmin .
Topology
α^
pgof
TPL vs. log-normal
scale-free
2.35
0.57
3.22
modular
2.03
0.96
0.60
exponential
2.98
0.36
0.81
uniform
2.91
0.06
1.69
Table 3. Heavy-tail audit across graph topologies under semantic LLM policies. α^ is the fitted tail exponent, pgof is the bootstrap goodness-of-fit p -value, and the final column reports the likelihood-ratio statistic comparing TPL with the log-normal alternative, where positive values favor TPL. A topology passes the tail-fit screen when pgof≥0.10 .
Figure 4. Heavy-tail audit across graph topologies under semantic LLM policies. Left: fitted tail exponent α^ . Middle: bootstrap goodness-of-fit, with pgof=0.10 marking the audit threshold. Scale-free, modular, and exponential graphs pass the screen, whereas uniform graphs do not. Right: evidence favoring a truncated power law over a log-normal tail, strongest for scale-free graphs.
Figure 5. Memory-access concentration under random-walk and semantic policies. Left: normalized access frequency ordered from most to least accessed memory. Right: cumulative access captured by the top-ranked memory fraction.
Method
Tokens/step
Tail error
Full History
3601.1
1.000
Sliding Window
1479.5
0.987
Flat Retrieval
159.9
0.994
Frequency Cache
166.4
1.000
Recency Cache
159.0
1.000
Hierarchical Summary
411.7
0.996
Table 4. Memory-policy comparison on Synthetic Graph World. Tokens/step denotes the average number of prompt tokens used per API-calling step, and tail error measures prediction error on the bottom-50% least-accessed states.
Method
Encoding
Tokens/step
Tail error
Graph Memory
Verbose
170.7
0.932
CTMC
Verbose
200.3
0.856
Graph Memory
Compact
156.4
0.931
CTMC
Compact
155.7
0.805
Table 5. Ablation of memory allocation and encoding. CTMC reduces tail error under both encodings, while compact encoding primarily reduces token cost.
Allocation
Tokens/step
Overall error
Tail error
CTMC ( τ=1.0 )
155.7
0.214
0.805
Uniform ( τ=0 )
156.0
0.236
0.861
Shuffled ranks ( τ=1.0 )
155.9
0.249
0.889
Reversed ranks ( τ=1.0 )
156.1
0.267
0.917
Table 6. Memory-allocation ablation under matched context budgets.
Figure 6. Effect of τ on memory concentration across three seeds. Gini, skew, and max/median ratio increase consistently with τ .
Figure 7. Prompt-token reduction of CTMC relative to Graph Memory across paired configurations.
Figure 8. LongMemEval results by question type. Left: prompt tokens per query. Right: substring-match accuracy. Error bars show seed-level mean ± sample standard deviation.
Appendix figures & tables2 assets
Supplementary material from the paper’s appendix.
Appendix
Gini coefficient
Top-10% share (%)
σtop10
Scaling
Graph family
100
500
1,000
100
500
1,000
100
500
1,000
Slope
R2
Uniform degree
0.5741
0.7550
0.7934
39.53
74.84
78.57
0.152
0.802
1.364
0.505
0.967
Exponential degree
0.6054
0.7618
0.7954
46.46
75.77
78.68
0.333
0.900
1.369
0.433
0.971
Scale-free
0.6045
0.7563
0.7944
46.24
74.70
78.63
0.385
0.809
1.349
0.392
0.915
Modular
0.4851
0.8098
0.8170
30.85
79.56
80.48
0.162
1.461
1.366
0.573
0.874
Mixed
0.4024
0.7867
0.8220
26.66
78.13
80.32
0.231
1.252
1.430
0.541
0.975
Appendix
Table 7. Random-walk memory-access concentration across graph families and graph sizes. Gini measures overall access inequality, Top-10% share is the percentage of accesses captured by the most accessed 10% of memories, and σtop10 is the standard deviation of access counts within this top group. Columns 100, 500, and 1,000 denote the number of graph nodes. Slope and R2 summarize the scaling of σtop10 with graph size.
Retrieval method
Uniform degree
Exponential degree
Scale-free
Modular
Mixed
Gini coefficient
No retrieval
0.334
0.339
0.350
0.333
0.292
Recency
0.577
0.569
0.584
0.472
0.358
State-mate uniform
0.571
0.574
0.595
0.468
0.351
State-aware frequency
0.584
0.608
0.633
0.500
0.435
Max/median
Appendix
Table 8. Retrieval-design controls under the random-walk policy. Each entry is a single-seed measurement. State and transition summaries are matched across retrieval conditions. Gini measures overall inequality in memory access, while Max/median is the ratio between the maximum and median memory-access counts.
Large language model (LLM) agents have demonstrated the ability to solve multi-step tasks requiring planning, tool use, and external information access, yet growing execution histories increase inference cost and expose reasoning to outdated, irrelevant, or misleading information, potentially degrading reasoning quality. Existing memory approaches organize or compress execution histories but provide limited mechanisms for deciding which memories remain active. We introduce the, a hierarchical memory system that organizes execution into tasks, subtasks, and actions while assigning each memory a dynamic retention score. Event-based updates and selection-based decay revise these scores, allowing WMT to preserve useful information, fold completed trajectories, suppress low-utility content, and retain access to folded context. We evaluate WMT on GAIA-Text using Qwen3-8B, Gemma 4 E4B, and Llama-3.1-8B, with ablations and memory-poisoning experiments. Relative to linear memory, WMT improves accuracy by an average of 9.97 percentage points while reducing prompt-token usage by 32.8%. Memory-poisoning experiments show that WMT limits the persistence and propagation of unreliable information. Our results suggest that effective long-horizon agent memory depends less on storing more information than on deciding which information should remain active.
Quang Dao, Purvi Kathalkar, Kenneth Eaton
Rose-Hulman Institute of Technology · Georgia Institute of Technology · Georgia Tech Research Institute
Memory is becoming core infrastructure for long-horizon LLM agents, yet existing evaluations offer limited guidance on which memory substrate, namely the underlying medium in which memory is represented and stored, should be used under different operating regimes. We present a controlled harness evaluation of memory substrates for memory-augmented agents, covering dense and sparse indices, text records, structural stores, hierarchical stores, refinement-based memories, parametric updates, and activation-compatible context mechanisms. Across three backbone models and four benchmark suites spanning user-centric question answering and agent-centric decision-making, we instrument 26 performance and efficiency metrics under a unified harness. Our results show that no single substrate consistently dominates: broad retrieval benefits long-context factual QA, while excessive retrieval can harm sequential decision-making by shifting attention away from action-critical context. Scalability introduces a further routing axis, as substrates that perform well at moderate history lengths can become costly or brittle at longer horizons. These findings motivate substrate routing as a necessary component of adaptive agent memory systems and provide empirical guidance for designing efficient, reliable, and regime-aware long-term memory for LLM agents. Code will be made available upon acceptance.
Wei-Chieh Huang, Weizhi Zhang, Yuchen Wu +12
University of Illinois Chicago · University of Washington · McGill University +2
Long-term memory is essential for LLM-based agents to sustain interactions and reliably leverage distant history. However, existing memory systems typically process heterogeneous dialogue content through a uniform summarization and retrieval pipeline, leading to either excessive token consumption or irreversible loss of fine-grained evidence. We argue that historical dialogue content should be handled differently according to its compressibility, temporal dynamics, and fidelity requirements. Based on this insight, we propose LeanMem, a lightweight long-term memory framework. LeanMem first filters out low-value content, then stores informative segments as compact profile memory, temporally structured event memory, or source-grounded record memory, depending on the nature of the information. During maintenance, only dynamically evolving event memories are selectively updated, avoiding redundant consolidation of stable profiles and immutable records. During inference, LeanMem dynamically selects memory types and allocates retrieval budgets according to query-specific evidence demands, assembling relevant evidence on demand. On LoCoMo and LongMemEval-S with GPT-4.1-mini and Qwen3-8B, LeanMem improves accuracy over the strongest memory-based baseline in every setting, by up to 15.1 points, at the lowest or near-lowest construction cost, inference tokens, and latency. The code and datasets are included in the supplementary materials.