Heavy-Tailed Memory Traces in Long-Horizon Language Agents

1 Introduction

• The complex-systems analogy motivates a measurement hypothesis, not a claim that agent memory traces demonstrate criticality.The hypothesis asks whether concentrated core–tail structure can be audited and used to improve memory control.Source: §1 · p. 1
• Random-walk agents yield log-normal-compatible retrieval artifacts, whereas semantic LLM policies produce stronger, task-shaped truncated-power-law-compatible core–tail traces.The authors identify semantic-policy traces as the regime where allocation control becomes valuable.Source: §1 · pp. 1–2, Figure 1 · p. 2
• CTWM ranks memories by relevance and transition support, partitions them into core and tail slices, and allocates prompt budget by rank using τ while retaining a measured tail.It requires neither base-model retraining nor a new latent dynamics model.Source: §1 · pp. 1–2, Figure 1 · p. 2
• CTWM improves the token–coverage–tail-error trade-off against a graph-memory baseline and preserves token savings across ALFWorld and LongMemEval.The paper also reports that rank allocation reduces tail-state prediction error.Source: §1 · p. 2
• The work pairs a conservative API-agent memory audit with random-walk and topology controls, and applies the audit-to-control pipeline across synthetic graphs, embodied text environments, and conversational memory.It introduces a rank-based core–tail allocation rule with formal monotonicity guarantees.Source: §1 · p. 2

Long-term memory for language agents

• CTWM complements long-term agent-memory systems by measuring how finite external memory is used over many steps and exposing a scalar allocation parameter.Prior systems use paging (Packer et al., 2023), recency, importance, and relevance (Park et al., 2023), verbal feedback (Shinn et al., 2023), explicit management (Zhong et al., 2024; Xu et al., 2025), relational structures (Anokhin et al., 2024; Rasmussen et al., 2025), or reusable skills and state (Wang et al., 2023).Source: §2 · p. 2

Retrieval and finite context

• Retrieval can improve prediction without weight updates, while long prompts can hide information; CTWM therefore treats prompt budget as an explicit allocation problem (Lewis et al., 2020; Khandelwal et al., 2020; Borgeaud et al., 2022; Liu et al., 2024; Xiao et al., 2024).Source: §2 · p. 2

World models

• Unlike classical learned latent dynamics (Ha and Schmidhuber, 2018; Hafner et al., 2020; Schrittwieser et al., 2020), CTWM studies a frozen language model with external structured memory updated through API calls.Its focus is a finite, auditable memory trace and its resource distribution.Source: §2 · p. 2

Tool use and interactive benchmarks

• Tool-use and environment benchmarks motivate comparing API-reported prompt tokens and paired agent-loop outcomes, rather than offline retrieval scores alone (Yao et al., 2023; Schick et al., 2023; Qin et al., 2024; Li et al., 2023; Patil et al., 2024; Côté et al., 2018; Shridhar et al., 2021; Yao et al., 2022; Yang et al., 2018; Wu et al., 2024; Yao et al., 2024).Source: §2 · pp. 2–3

Graph retrieval and implicit concentration

• Graph retrieval can repeatedly expose a small subset through hubs, propagation, and top-k filtering; CTWM isolates this confound and uses ranked structure when semantic policies induce a stronger audited tail (Edge et al., 2024; Guo et al., 2024; Gutierrez et al., 2024; Brin and Page, 1998).Source: §2 · p. 3

Heavy-tail statistics and criticality

• Because finite-sample tail claims are fragile and a marginal tail alone does not establish criticality, the paper uses conservative terms such as heavy-tailed and truncated-power-law-compatible (Newman, 2005; Kaplan et al., 2020; Martin and Mahoney, 2018, 2019; Clauset et al., 2009; Alstott et al., 2014; Stumpf and Porter, 2012; Virkar and Clauset, 2014; Broido and Clauset, 2019; Bak et al., 1987; Sethna et al., 2001; Beggs and Plenz, 2003; Cocchi et al., 2017).Source: §2 · p. 3

3 Problem Setup and Tail Audit

• The agent records structured states and transitions, retrieves context from finite external memory, and predicts the next state without updating model parameters.Adaptation occurs through memory, retrieval, and prompt construction, rather than gradient updates.Source: §3 · p. 3
• Tail error is the mean prediction loss on the bottom half of states by visit count, avoiding a hand-tuned frequency threshold.The quantile-based definition is intended to be benchmark-agnostic and test whether memory preserves rare states.Source: §3 · p. 3
• The audit calls a fitted tail compatible only when bootstrap goodness-of-fit passes and a likelihood-ratio test significantly favors a truncated power law over a log-normal tail.The audit reports the fitted cutoff and exponent, bootstrap goodness-of-fit, likelihood-ratio statistic, and its standard error; it follows Clauset et al. (2009) and cautions on finite heavy-tailed data (Newman, 2005; Stumpf and Porter, 2012; Virkar and Clauset, 2014).Source: §3 · pp. 3–4
• The compatibility label is not evidence of scale-free topology or full critical dynamics, which require additional evidence (Broido and Clauset, 2019; Sethna et al., 2001).Core–tail notation ranks memory items by retrieval score; lower rank means higher priority, with allocation exponent τ and prompt-slot budget Bt.Source: §3 · p. 4

4 Core–Tail World Model

• CTWM ranks memories instead of relying on uncalibrated retrieval scores, then uses exponent τ to allocate prompt budget between a high-priority core and summarized tail.Figure 2 shows the update-and-retrieval loop, including ranking, partitioning, and logging prediction error, retrieval counts, and token usage.Source: §4 · p. 4, Figure 2 · p. 4
• A smaller τ approaches uniform retrieval, while a larger τ concentrates context on high-rank memories but preserves a measured tail slice.This provides a tunable alternative to unstructured history packing and flat retrieval.Source: §4 · p. 4
• CTWM serializes selected core items as compact rank-ordered hints and tail items as aggregate summaries, separately from the allocation rule.Section 5 crosses verbose versus compact encoding with graph retrieval versus CTWM allocation; Appendix A.2 formalizes frozen-trajectory attribution to separate retrieval logic from policy-induced trajectory changes.Source: §4 · p. 4

5.1 Random-walk control

• Across 54 cells, pure-power-law pass rate was 0% and PSD exponents were 0.048–0.176; concentration rose with graph size in five of six graph families.The random-walk tail is an actionable allocation signal, but not evidence for critical dynamics.Source: §5.1 · pp. 4–5, Table 1 · p. 5

5.2 Retriever mechanism

• State-aware top-k retrieval drives concentration: disabling retrieval lowers Gini 33–45% to 0.29–0.35, while non-preferential retrieval retains 92–94% of scale-free Gini.Uniform frequency sorting yields Gini 0.698, and a symmetric-payload regular graph still yields Gini 0.638.Source: §5.2 · p. 5, Figure 3 · p. 6

5.3 Semantic-policy tails

• Semantic policy yields finite-mean core–tail concentration, with truncated-power-law preferred on the strongest scale-free traces; multiple topologies support compatibility, but scale-free evidence is strongest.The topology sweep supports a conservative conclusion: power-law-compatible concentration extends beyond a single graph family.Source: §5.3 · p. 5, Table 2 · p. 5, Figure 4 · p. 6

5.4 Memory comparison

• Relative to Graph Memory, CTWM reduces prompt tokens by 5.9% and bottom-50% tail error by 13.6%, while preserving full state and transition coverage.This is the central practical result on Synthetic Graph World.Source: Table 3 · p. 5, §5.4 · p. 5

5.5 Ablation

• Compact encoding alone changes Graph Memory tail error only 0.932 → 0.931, while CTWM allocation lowers error under both serialization modes.Frozen-trajectory replay keeps the retrieval backend unchanged; compact hints alter subsequent LLM choices and the visited state–hint trajectory, changing the evaluated tail-state distribution.Source: §5.5 · pp. 5–6, Table 4 · p. 6, Figure 5 · p. 7

5.6 Tau control

• Across seven τ values from 0.25 to 2.0, Gini, skew, and max/median concentration all rise monotonically, making the allocation exponent a closed-loop concentration knob.Clauset α is not used as the control metric because automatically selected xmin is unstable under the sweep.Source: §5.6 · pp. 6–7

5.7 External validity

• Across ALFWorld (Côté et al., 2018; Shridhar et al., 2021), paired token savings are 4–7%; on LongMemEval (Wu et al., 2024), CTWM reduces tokens 24.48% at aggregate accuracy parity.The claim is token efficiency, not universal task improvement: ALFWorld success remains limited under the untuned API ReAct policy, and LongMemEval exposes a multi-session recall blind spot.Source: §5.7 · p. 7, Table 5 · p. 7

• Allocation is the dominant tail-error factor, while compact encoding changes LLM policy behavior rather than the deterministic retrieval map.Matched replay fixes the retrieval map and ranked identifiers; Figure 6 reports the live gap is within 4 × 10^-4 and attributes the observed difference to the policy path.Source: §6 · p. 7, Figure 6 · p. 8
• The topology and τ sweeps are finite audits, not exhaustive environment studies, and ALFWorld results support token-efficiency claims rather than task-success claims.The current API ReAct policy is not strong enough to support an ALFWorld task-success claim; cross-benchmark evidence concerns token efficiency under paired episodes.Source: §6 · p. 7
• LongMemEval exposes a multi-session recall weakness, so aggressive core–tail budgeting should be relaxed for recall-critical queries.Source: §6 · p. 7
• Random walks produce retriever-induced log-normal-compatible concentration, whereas semantic LLM policies can produce truncated-power-law-compatible concentration.The paper does not claim full self-organized criticality: random-walk traces fail pure-power-law and temporal tests, and semantic-policy evidence is distributional rather than avalanche-based.Source: §6 · pp. 7–8
• CTWM uses a single rank exponent τ and compact core–tail serialization to improve the token–coverage–tail-error trade-off while preserving token savings across three benchmarks.Figure 7 shows that increasing τ shifts budget toward the ranked core; its concentration diagnostics are Gini, max/median ratio, and skew.Source: §6 · p. 8, Figure 7 · p. 8

A.1 Allocation rule and proofs

• CTWM defines a rank-based allocation for memory items and places ranks beyond core size K_t in the tail set W_tail,t.The supplied definition identifies τ as the allocation parameter but does not include the full allocation formula.Source: §A.1 · p. 11
• Rank-based allocation provides a portable control across graph, vector, and hand-written memories whose retrieval scores may use incomparable scales.The same τ can be applied across synthetic graphs, ALFWorld histories, and LongMemEval sessions without backend-specific score calibration.Source: §A.1 · p. 11
• For any τ > 0, a higher-ranked memory item receives strictly more budget than a lower-ranked item.This monotonicity preserves the retriever's ordering and prevents serialization or packing from washing out selected memories.Source: §A.1 · p. 11
• The allocation ratio b_t(r; τ)/b_t(s; τ) = (s/r)^τ for r < s, and it increases strictly with τ.Thus τ predictably increases the separation between high- and low-rank items, motivating concentration diagnostics such as Gini, skew, and max/median.Source: §A.1 · p. 11
• For a fixed core size K_t < M_t, core mass C_t(K_t, τ) increases strictly with τ.The controller can lower τ or enlarge the tail summary when rare states are missing, and raise τ when stale context dominates the prompt.Source: §A.1 · p. 11
• As τ approaches zero, each rank receives 1/M_t allocation and the allocation Gini converges to zero.This provides a uniform-allocation fallback when the audit does not support aggressive core concentration.Source: §A.1 · p. 11

A.2 Frozen-trajectory attribution

• Retrieval determines available memories, while serialization affects how the frozen language model reads them and which future states it visits.The theorem attributes live tail-error differences that disappear under matched trajectories to trajectories induced by the policies, not changes in retrieval logic.Source: §A.2 · p. 12
• Replay losses match live losses within 4 × 10−4, indicating that compact-encoding improvements are mediated by policy-induced paths rather than a changed retrieval function.Under fixed-trajectory replay with the same deterministic retrieval map, changing the encoding without changing retrieved hint identifiers cannot alter deterministic replay loss.Source: §A.2 · p. 12

B Benchmark Caveats

• In ALFWorld, both Graph Memory and CTWM score 0/18 in one-shot; in three-shot, Graph Memory scores 1/18 and CTWM 0/18.These results are under the untuned API ReAct policy.Source: B Benchmark Caveats · p. 12
• Across 77 LongMemEval multi-session questions, CTWM answers 0 correctly while Graph Memory answers 3 correctly.LongMemEval shows token savings with accuracy parity overall, but multi-session recall remains a weak point.Source: B Benchmark Caveats · p. 12
• Future controllers should relax core–tail compression when queries explicitly ask for long-range recall.Source: B Benchmark Caveats · p. 12

C Prompt Templates: Compact and Verbose Encoding

• Compact CTWM preserves rank order, removes raw score annotations, aggregates low-rank memories into a typed tail summary, and requests a bounded next-state prediction.The prompt contract includes the current state and action, a small ranked core, and an output with prediction, confidence, and evidence rank.Source: C Prompt Templates: Compact and… · pp. 12–13
• Examples across Synthetic Graph World, ALFWorld, and LongMemEval show compact prompts using ranked evidence while relegating unrelated context or rare facts to the tail.In LongMemEval, the later May correction is ranked above the initial April plan and supplies the answer.Source: C Prompt Templates: Compact and… · p. 13
• Verbose prompts aid auditing with scores and provenance but burden the frozen model with low-value fields; compact encoding can reduce tokens while retaining the tail as an aggregate object.Compact prompts retain rank order, current state and action, a small core, and an explicit tail role.Source: C Prompt Templates: Compact and… · pp. 12–13

D Cutoff Instability Under the Tau Scan

• Clauset ˆα is non-monotone across replicated τ scans because its estimated range begins above a cutoff that changes across runs, a known finite-sample limitation (Clauset et al., 2009; Virkar and Clauset, 2014).Source: D Cutoff Instability Under the Tau Scan · p. 13
• The main text uses Gini, skew, and max/median as control diagnostics, reporting ˆα only as confirmatory.Source: D Cutoff Instability Under the Tau Scan · p. 13