Heavy-Tail Memory Traces: A New Approach to Memory Allocation for Long-Horizon Language Agents

Why Agent Memory Deserves a Fresh Look

As language agents take on increasingly complex roles in long-horizon tasks, external memory has gradually become the "frozen world model" they rely on to operate. Yet the dominant approach to evaluating memory systems has a significant blind spot — researchers typically focus on whether a task was completed and how many tokens were consumed, while overlooking a more fundamental question: how memory is actually being used.

This arXiv paper (arXiv:2610.00010v1) argues that what's truly missing from memory system evaluation is "the shape of memory use." Under the constraints of limited context windows and repeated retrieval, agent memory tends to concentrate around a small core region, pushing a large number of rare states into a long tail — where prediction errors accumulate.

A Conservative Tail Audit: Concentration Is Reproducible

The research team characterized this effect through a "conservative tail audit," arriving at a central finding: memory concentration is reproducible, but highly policy-dependent.

Different types of agents exhibit distinctly different memory trace shapes:

• Random-walk agents: Produce retrieval traces compatible with a log-normal distribution.
• Semantic LLM policies: Produce the strongest "core–tail" traces, compatible with a truncated power-law distribution.

This means that the more semantically capable a policy is, the more it tends to form heavy-tailed structures — a small number of core states are accessed frequently, while a large number of peripheral states are pushed into the long tail. This heavy-tail distribution is no longer just a passive side effect; it is a diagnostic signal revealing the intrinsic properties of limited retrieval mechanisms.

Log-normal and truncated power-law distributions both belong to the "heavy-tail" family, but differ in how quickly their tails decay. Log-normal tails decay relatively faster and are suited to describing "incidental concentration" retrieval patterns, where most states are accessed with roughly comparable frequency. Power-law distributions (and their truncated variants) have heavier tails, meaning a small number of core states can be accessed orders of magnitude more often than peripheral ones. In practice, the two can be distinguished by their behavior on a log-log plot: a power-law appears as an approximately straight line, while a log-normal curves downward like a parabola. The team chose the word "conservative" to indicate that they applied stricter statistical testing thresholds when fitting distributions, avoiding the tendency to label any heavy-tailed behavior as a power-law — which makes the finding that "semantic LLM policies produce truncated power-law traces" more credible.

CTWM: Controlling Memory Budget with a Single Exponent

Building on the audit findings, the researchers propose the Core–Tail World Model (CTWM) — a rank-based memory controller.

Its core idea is elegantly simple: use a single exponent parameter $\tau$ to allocate the prompt budget while retaining a summarized representation of the tail. Rather than flatly packing all memory into the context, CTWM dynamically determines resource allocation based on state rank — core states receive richer representation, while tail states are retained in summary form — balancing coverage with token efficiency.

This design directly responds to the heavy-tail structure observed in the audit: since memory naturally exhibits core–tail differentiation, the control strategy should work with this shape rather than against it.

Rank-based resource allocation is a classical approach: instead of relying on raw access frequency, all states are ordered by frequency and weights are assigned based on rank. This provides robustness against extreme values — even if a state is accessed an unusually large number of times, its rank is simply "first," preventing it from monopolizing nearly the entire token budget due to an outsized absolute frequency. The single exponent parameter τ further simplifies tuning: as τ approaches 0, the budget tends toward uniform allocation; as τ increases, resources become increasingly concentrated in top-ranked core states. This allows CTWM to serve as either a conservative "nearly flat" strategy or an aggressive "core-heavy" one, covering a continuous design space without requiring task-specific allocation rules.

Experimental Results Across Three Benchmarks

CTWM was evaluated across multiple environments, showing consistent token savings:

Synthetic Graph World

• Fully preserved state and transition coverage
• Reduced prompt tokens by 5.9% compared to the graph memory baseline
• Lowered lower-half tail prediction error by 13.6%

ALFWorld

• Achieved consistent token savings under the same paired comparisons

LongMemEval

• Achieved 24.48% token reduction
• Maintained aggregate accuracy parity

Notably, these gains come without sacrificing performance — coverage is preserved, accuracy holds steady, and tail prediction error actually decreases. This demonstrates that memory allocation that "follows the heavy-tail shape" can improve efficiency without losing capability.

Heavy-Tail Traces: Both a Diagnostic and a Control Signal

The most insightful contribution of this research is how it repositions the role of "heavy-tail memory traces." They are not merely a diagnostic characterization of limited retrieval mechanisms — they are a control signal that can be actively exploited.

Traditional approaches treat memory as a static asset to be packed into context as completely as possible. CTWM's approach is closer to "structure-aware" resource scheduling: identify the shape of the memory distribution, then allocate the limited budget accordingly. For language agents that need to run over long horizons and repeatedly retrieve external knowledge, this offers a practical path to balancing token cost with long-tail reliability.

Of course, as a newly released preprint, its conclusions still await validation across broader scenarios — for example, whether a single exponent $\tau$ is sufficient for more complex, dynamically shifting real-world tasks, and how tail summaries perform on extremely rare but critical states. But the direction it points — shifting from "how much memory was used" to "what shape did memory use take" — opens a genuinely promising perspective for agent memory system research.

ALFWorld is a text-based household interaction benchmark where agents complete multi-step instructions like "put the apple in the refrigerator" in simulated rooms; it is commonly used to evaluate language model planning and tool-use capabilities. LongMemEval focuses on long-context memory retrieval, requiring models to precisely locate specific facts within conversation histories spanning tens of thousands to hundreds of thousands of tokens — more representative of real long-horizon assistant scenarios. The two benchmarks emphasize different capabilities — the former tests state tracking during action planning, the latter tests precise fact-level retrieval — and CTWM demonstrated consistent token savings on both, suggesting that memory strategies that "follow the heavy-tail shape" generalize across task types rather than overfitting to a specific task structure.