Heavy-Tailed Memory Traces in Long-Horizon Language Agents

Xinyuan Song; Zekun Cai

cs.AIJul 9, 2026

Heavy-Tailed Memory Traces in Long-Horizon Language Agents

Authors: Xinyuan Song, Zekun Cai

Organizations: Emory University, Atlanta, GA, USA · The University of Tokyo, Tokyo, Japan · LocationMind, Tokyo, Japan

Abstract

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;\tau)\propto r^{-\tau}$ .

Graph family	$\sigma_{100}$	$\sigma_{500}$	$\sigma_{1000}$	Slope	$R^{2}$
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.

\sigma_{\mathrm{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

x_{\min}

Topology	$\hat{\alpha}$	$p_{\rm gof}$	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.

\hat{\alpha}

is the fitted tail exponent,

p_{\rm gof}

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

p_{\rm gof}\geq 0.10

Figure 4. Heavy-tail audit across graph topologies under semantic LLM policies. Left: fitted tail exponent

\hat{\alpha}

. Middle: bootstrap goodness-of-fit, with

p_{\rm gof}=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 ( $\tau=1.0$ )	155.7	0.214	0.805
Uniform ( $\tau=0$ )	156.0	0.236	0.861
Shuffled ranks ( $\tau=1.0$ )	155.9	0.249	0.889
Reversed ranks ( $\tau=1.0$ )	156.1	0.267	0.917

Table 6. Memory-allocation ablation under matched context budgets.

Figure 6. Effect of

\tau

on memory concentration across three seeds. Gini, skew, and max/median ratio increase consistently with

\tau

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

\pm

sample standard deviation.

Appendix figures & tables2 assets

Supplementary material from the paper’s appendix.

Appendix

	Gini coefficient			Top-10% share (%)			$\sigma_{\mathrm{top10}}$			Scaling
Graph family	100	500	1,000	100	500	1,000	100	500	1,000	Slope	$R^{2}$
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

\sigma_{\mathrm{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

R^{2}

summarize the scaling of

\sigma_{\mathrm{top10}}

with graph size.

Gini coefficient
Retrieval method	Uniform degree	Exponential degree	Scale-free	Modular	Mixed
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.

Memory Management for LLM Agents

See all 92 papers

Weighted Memory Tree: Remembering What Matters for Long-Horizon LLM Agents
Aug 21, 2026Quang Dao, Purvi Kathalkar, Kenneth EatonLLM Agent Memory Memory Management for LLM Agents
Rose-Hulman Institute of Technology · Georgia Institute of Technology · Georgia Tech Research Institute
Harness the Memory: A Holistic Evaluation of Memory Substrates in Memory Agents
Aug 15, 2026Wei-Chieh Huang, Weizhi Zhang, Yuchen Wu +12LLM Agent Memory Memory-Augmented Agents
University of Illinois Chicago · University of Washington · McGill University +2
LeanMem: Simple and Efficient Long-Term Memory for LLM Agents
Aug 4, 2026Yuxin Liao, Le Wu, Min Hou +3LLM Agent Memory Persistent Memory for Language Models
Hefei University of Technology

Aug 21, 2026J/K move · Enter open · S save

Weighted Memory Tree: Remembering What Matters for Long-Horizon LLM Agents

Quang Dao, Purvi Kathalkar, Kenneth Eaton

Rose-Hulman Institute of Technology · Georgia Institute of Technology · Georgia Tech Research Institute

LLM Agent Memory Memory Management for LLM Agents Agent Memory Management Long-Horizon LLM Agents

Open paper AskPDF arXiv

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.

Abstract

Memory Management for LLM Agents

Explore similar work

Weighted Memory Tree: Remembering What Matters for Long-Horizon LLM Agents

Harness the Memory: A Holistic Evaluation of Memory Substrates in Memory Agents

LeanMem: Simple and Efficient Long-Term Memory for LLM Agents