Provable Transformer Context Compression for In-Context Reinforcement Learning

Yajie Zhao; Yingjun Mo; Zhiyong Wang; Bo Tang; Chao Xu; Fang Kong

Source-linked AI summary

Provable Transformer Context Compression for In-Context Reinforcement Learning

Yajie Zhao, Yingjun Mo, Zhiyong Wang, Bo Tang, Chao Xu, Fang Kong

arXiv:2610.20004v1Oct 14, 2026cs.LGcs.AI

TL;DR

Existing in-context RL theory often retains the full interaction history, leaving open the necessary context dimension and memory for exact TD-iterate reproduction and the best approximation with less context. The paper analyzes fixed-policy TD context requirements and constructs an encoder–executor that compresses raw transitions and reproduces queried TD values without parameter updates. With a shared linear decoder, the minimum context dimension to exactly reproduce L empirical TD iterates is kL; below it, best-achievable approximation error has matching upper and lower bounds of order Θ(γm max{1, 1/(m(1 −γ))}).

Problem
Existing in-context RL theory often retains the full interaction history, leaving open the necessary context dimension and memory for exact TD-iterate reproduction and the best approximation with less context.
Source: §1 · pp. 1–2
Method
The paper analyzes fixed-policy TD context requirements and constructs an encoder–executor that compresses raw transitions and reproduces queried TD values without parameter updates.
Source: §4 · p. 4, §6 · p. 10
Results
With a shared linear decoder, the minimum context dimension to exactly reproduce L empirical TD iterates is kL; below it, best-achievable approximation error has matching upper and lower bounds of order Θ(γm max{1, 1/(m(1 −γ))}).
Source: §1 · p. 2
Takeaways & Limitations
For fixed-policy TD evaluation, exact context requirements track the Krylov dimension, while continuous exact retained memory scales as Θ(nkL).
Source: §1 · p. 2
The retained-memory lower bound is class-level for task-uniform continuous encoders; restricted task families can require less memory.
Source: §4.1 · p. 6

Abstract

from arXiv · show

Transformers can perform in-context reinforcement learning without parameter updates. However, existing theoretical constructions often require context sizes that grow with the number of sampled transitions, leading to increasing memory costs in large-scale problems. This raises a fundamental scalability question: how much context is intrinsically necessary to carry out such learning? We answer this question for fixed-policy TD evaluation. We show that, with a shared linear decoder, the minimum context dimension required to exactly reproduce the first $L$ TD iterates is the Krylov dimension induced by the sampled transitions. When the available context dimension $m$ falls below this threshold, exact reproduction is no longer possible. In this regime, we characterize the optimal approximation error and show that it decays as $\Theta(\gamma^m\max\{1,1/(m(1-\gamma))\})$ where $\gamma$ is the discounting factor. Moving from representation complexity to actual memory cost, we characterize the optimal retained memory for exact continuous representations as $\Theta(nk_L)$ and show experimentally that on a sampled task whose exact rank is full but whose numerical rank is small, a context accurate to $10^{-2}$ is $88.7\%$ smaller than the sparse sufficient statistics of TD. Finally, we establish the learnability of the shared executor through pretraining by proving global convergence of an auxiliary objective over effective attention parameters under suitable task diversity. Experiments across diverse TD evaluation problems validate parameter recovery and the predicted context--accuracy tradeoff.

1 INTRODUCTION

Existing in-context RL constructions often retain interaction histories that grow with the horizon, leaving open whether that history is necessary to reproduce learning updates. For fixed-policy TD evaluation, the paper characterizes the required context and memory, the error under limited context, and conditions for learning the shared executor.

Motivation

Existing constructions retain full interaction histories, with task-specific memory scaling as Θ(dN), which can increase inference-time memory and computation costs.The paper frames whether this history is necessary as an open question for TD policy evaluation.Source: §1 · pp. 1–2

Research questions

The paper targets the minimum context dimension and memory needed for exact TD-iterate reproduction, and the best approximation when context falls below that threshold..Source: §1 · p. 2

Contributions

The minimum context dimension for exactly reproducing the first L empirical TD iterates is the Krylov dimension kL; below it, optimal approximation error has matching bounds of order Θ(γ^m max{1, 1/(m(1 − γ))}).The characterization assumes a shared linear decoder.Source: §1 · p. 2
For exact continuous representations answering all state–depth TD queries, the minimum retained memory is Θ(nkL); a sampled task with full exact rank but small numerical rank used 88.7% less memory at 10−2 accuracy than sparse TD statistics.The memory comparison is reported for that sampled task.Source: §1 · p. 2
Under suitable task diversity, an auxiliary objective is globally strongly convex in effective attention parameters, with provable global convergence to the target TD update.Experiments validate parameter recovery, the predicted context–accuracy tradeoff, and memory savings.Source: §1 · p. 2

2 RELATED WORK

Prior work studies ICRL through algorithm implementation, classical TD compression, model reduction, and general context compression. This paper distinguishes its focus as characterizing memory–accuracy limits for in-context TD and compressing raw transitions with fixed-parameter attention.

Theoretical Mechanisms of In-Context Reinforcement Learning

Prior theory studies Transformer execution of RL algorithms through supervised pretraining and reinforcement pretraining, including constructions for classical algorithms and TD-style updates.Examples include Lin et al. (2024), Liang & Lai (2026), and Wang et al. (2025a).Source: §2 · pp. 2–3

Comparison with prior constructions

Table 1 covers constructions that execute TD policy evaluation in the forward pass, reporting theory in task scalars and buffers as float32 array KiB over 100 encodings, excluding parameters and forward scratch.Other ICRL constructions are listed separately because they retain different objects.Source: Table 1 · p. 3

Reinforcement Learning and Traditional Compression

Classical TD policy-evaluation compression uses sufficient statistics such as LSTD and iLSTD, while Krylov subspaces also appear in value approximation and model reduction.The passage also situates this work among classical model-reduction methods.Source: §2 · p. 3

Context Compression

Context compression methods either learn compact representations or select and retrieve tokens or segments; this paper instead studies memory–accuracy limits for in-context TD using raw transitions and fixed-parameter attention.Source: §2 · p. 3

3 PRELIMINARIES

The preliminaries reduce fixed-policy evaluation to TD dynamics in an induced Markov reward process. They define empirical, visitation-normalized batch TD iterates and identify the successive directions those iterates require.

Reinforcement Learning Setting

For a fixed policy, the MDP induces a Markov reward process with transition matrix Pπ and expected one-step reward vector rπ; policy evaluation estimates its value function.The setting uses a discounted, infinite-horizon MDP with finite state space.Source: §3 · p. 3

Empirical TD setting

The analysis focuses on fixed-policy TD dynamics, with N transitions collected under the policy and full state coverage assumed so every state has positive visitation count.The analysis can extend to states with finite-dimensional features.Source: §3 · pp. 3–4

Empirical TD iterates

Starting from zero, the empirical value estimate after each iteration is defined by visitation-normalized batch TD(0).The passage introduces the empirical TD error used in the dynamics.Source: §3 · p. 4

Krylov space

Preserving the first L iterates amounts to preserving the directions r, Ar, through A^(L−1)r; their span is the Krylov space, whose dimension is kL.Here A is defined as γ times the empirical transition matrix.Source: §3 · p. 4

4 CONTEXT AND MEMORY COMPLEXITY OF IN-CONTEXT TD

The section constructs compressed contexts that reproduce TD updates, characterizes the context and memory needed for exact or approximate computation, and proves a pretraining guarantee for learning the executor under suitable task diversity.

4.1 END-TO-END CONSTRUCTION: ENCODER AND EXECUTOR

The encoder compresses raw transitions in two stages, first to n state-level statistics and then to kL Krylov directions, while a shared executor produces queried TD values.The first k sampling depths are preserved exactly; later sample-and-hold depths divide remaining discounted weight into approximately equal portions.Source: §4.1 · p. 5, §4.2 · p. 7
Exact reproduction of the first L empirical TD iterates requires context dimension kL, and a fixed attention encoder-executor constructs such a context in its forward pass.The construction uses Θ(nkL) retained memory, optimal up to a factor of two among continuous exact encoders.Source: §4 · p. 4, §4.1 · p. 5
For exact continuous encoders, the retained-memory lower bound is class-level: restricted task families can admit smaller encoders, while full-rank systems can require at least n² registers.For offline coding, arbitrary encoders and decoders need Θγ(n min{n, L, log(1/ϵ)} log(1/ϵ)) bits for all state–depth queries within error ϵ.Source: §4.1 · p. 6
For feature-based batch TD, the minimum exact context dimension is the feature Krylov dimension kϕL, with retained memory Θ(dkϕL).The fixed-parameter encoder operates on the unnormalized batch TD statistics (M, s0).Source: §4.1 · p. 6

4.2 APPROXIMATION WITH LIMITED CONTEXT

For m below the exact threshold, optimal depth-free worst-case error is Θ(γ^m max{1, 1/(m(1−γ))}), attained by sample-and-hold.When m < 1/(1−γ), every m-dimensional context has worst-case error at least Ψm/64; for finite L, the bounds depend on the number of iterations.Source: §4.2 · p. 7
With m < 1/(1−γ), worst-case error decreases only as 1/m, and the same lower bound applies to feature-based contexts.For 8m ≤ L ≤ 1/(1−γ), the optimal finite-depth error is Θ(L/m).Source: §4.2 · pp. 7–8

4.3 LEARNABILITY OF THE TD UPDATE

Trajectory supervision distinguishes TD update rules, whereas endpoint supervision cannot uniquely identify the step size because different step sizes share a fixed point.The trajectory map has an injective Jacobian at the target; endpoint supervision has a nonzero null direction.Source: §4.3 · p. 8
Under task richness, the calibration objective is globally strongly convex and smooth with unique target (C⋆, W⋆) = (−In, In), reached from any initialization.The theorem identifies the executor, not the encoder.Source: §4.3 · pp. 8–9

5 EXPERIMENTS

Experiments test parameter recovery, the context–accuracy tradeoff, memory use, and learned bottleneck encoders. The reported results support the predicted tradeoff, while learned encoders do not improve with increasing context dimension in the tested range.

Effective parameter recovery

Calibration recovers C = −I24, W = I24 to normalized parameter error 1.0 × 10−15 in 3,000 steps; the depth-30 endpoint surrogate stops at 0.51.The endpoint surrogate's depth-30 output is within 0.04 of TD on held-out tasks, but its trajectory is off by up to 0.63.Source: Figure 1 · p. 9, §5 · p. 9

Context–accuracy tradeoff

On worst-case rings at γ = 0.99, sample-and-hold and anchored hold stay within [0.45, 2.7] × Ψm, while Krylov truncation is up to 37× worse.Their sub-horizon slopes are −0.89 and −0.93 against the predicted −1; Krylov truncation has slope −0.14.Source: §5 · p. 9, Figure 2 · p. 10

Memory usage

At n = 480, the block-cycle context is 94.6% smaller than the statistics, while sampled tabular contexts accurate to 10−2 are 9× smaller than sparse TD on a dense kernel.On a sparse goal-directed gridworld, sparse TD remains the most compact representation.Source: Table 2 · p. 10, §5 · p. 10

Learned bottleneck encoders

Learned bottleneck encoders beat sample-and-hold for m ≤8, but their error stays at 0.61–0.63 or 0.50–0.54 as m increases to 24.Compiled contexts reach 0.10 and 0.03 at m = 24; the reported learned encoders do not discover the Krylov or clock structure.Source: §5 · p. 10

6 CONCLUSION

The paper characterizes the context and memory needed to reproduce TD evaluation, including approximation when context is limited, and studies whether pretraining can recover the shared executor. Its theoretical guarantees focus on TD policy evaluation; extensions to jointly learned encoders and policy control remain open.

6 CONCLUSION

The minimum context dimension for the first L TD iterates is the Krylov dimension, and the paper characterizes the best achievable worst-case error below that threshold.A sample-and-hold method achieves the same approximation rate.Source: §6 · pp. 10–11
A fixed-parameter linear-attention network compresses raw transitions into context and reproduces queried TD values without parameter updates.Its retained memory is within a factor of two of the optimum.Source: §6 · p. 10
Pretraining can recover the shared executor under suitable task diversity, while supervising only the final output cannot identify the TD update rule.Source: §6 · p. 11
The theoretical guarantees cover TD policy evaluation with explicitly constructed encoders; jointly learned encoders and policy control remain open questions.Source: §6 · p. 11

CONTENTS OF THE APPENDICES

The appendix specifies a fixed-parameter, end-to-end attention construction that converts raw transitions into a compact context for exact TD evaluation. It details the architecture, empirical coverage, token operations, and Krylov-direction compilation.

A ARCHITECTURE, HEAD LIBRARY, AND END-TO-END EXACTNESS

Head parameters are fixed by public quantities, while raw records and intermediate statistics are activations; forward-pass gates determine which candidate tokens survive release.Routes depend on public quantities and the current stage, never on task values.Source: A ARCHITECTURE, HEAD LIBRARY, AND… · p. 18

A.1 COVERAGE AND EMPIRICAL SCOPE

Full state coverage makes empirical rows, reward means, and visitation normalization well defined, but does not imply irreducibility or control statistical error.The exact results require no irreducibility; uncovered states need a specified completion or restricted query domain.Source: §A.1 · p. 18

A.2 TOKEN LAYOUT AND SELECTOR HEADS

Tokens share a block layout, and selector heads address the same block across tokens using fixed signed projection maps.The specified token width is 13n + 11.Source: §A.2 · p. 18

A.3 STAGE 1: RAW RECORDS TO STATISTICS

Stage 1 aggregates raw records into state-level counts, reward sums, visitation values, empirical rewards, and discounted transition rows.Chunked aggregation produces the same result while keeping live raw storage at O(Cn) rather than O(Nn).Source: §A.3 · pp. 18–19

A.4 THE STATE-LEVEL CONTEXT

The n state tokens form an exact context: each stores its state identity, discounted empirical transition row, and empirical reward, preserving sampled values through the executor.The construction compresses N records into n state tokens and recovers the empirical value exactly.Source: §A.4 · p. 19

A.5 STAGE 2: DISCOVERING AND COMPILING KRYLOV DIRECTIONS

Stage 2 generates orthogonal Krylov directions from the reward vector and discounted transition operator, then releases candidates after breakdown to retain exactly the first kL directions.Candidate tags support construction of the reduced operator and compiled context.Source: §A.5 · p. 19

A.6 LINEAR FEATURES: PROOF OF THEOREM 4.4

The appendix extends the construction to linear features and establishes its executor identities, exactness, continuity properties, and memory costs. It also describes variants for weighted inner products, limited budgets, and Krylov-anchored computation.

A.6 LINEAR FEATURES: PROOF OF THEOREM 4.4

For linear features, the minimum exact context dimension is the feature-induced Krylov dimension, attained by a context whose executor recovers the queried TD values.Source: §A.6 · p. 20

A.7 EXECUTORS

The time-invariant executor advances its source state by a fixed recurrence, while the depth-counter executor uses public time stamps to select contributions by depth.Source: §A.7 · p. 20

A.8 EXACTNESS AND MINIMALITY

The constructed context exactly reproduces every queried empirical TD value through depth L, and its retained memory is established separately.The minimum exact dimension is kL, and the construction uses exactly kL retained tokens.Source: §A.8 · p. 21

A.9 CONTINUITY WITHIN RANK STRATA; A.10 RANK DISCONTINUITY ACROSS STRATA

The encoder is continuous within each fixed-rank stratum, but exact rank-adaptive encoding is discontinuous across strata.On inputs whose nonzero reciprocal arguments have a positive margin, a ReLU interpolant can replace the reciprocal with arbitrarily small output error and identical prefix decisions.Source: §A.9 · p. 22, §A.10 · p. 22

A.11 VISIT-WEIGHTED INNER PRODUCT

A positive-definite visitation-weighted inner product changes the Krylov norms and duals but preserves exactness, with no division by state counts required.Source: §A.11 · p. 22

A.12 SAMPLE-AND-HOLD ENCODER AND DEPTH-COUNTER EXECUTOR

The sample-and-hold encoder stores selected trajectory values using at most m sample tokens, with peak live storage O(n^2 + nm).Repeated squaring reduces depth to O(log L) at the same peak storage; the described schedule assumes public γ.Source: §A.12 · pp. 22–23

A.13 KRYLOV-ANCHORED ENCODER

The Krylov-anchored encoder compares the TD trajectory with a projected trajectory and matches its closed form to 2.8 × 10^-15.Source: §A.13 · p. 23

A.14 RETAINED, PEAK, AND SHARED MEMORY

Retained context occupies (2n + 1)(kL + 1) locations; peak memory is O(Nn + n^2 + nh) in batch form and O(Cn + n^2 + nh) when streamed.The accounting counts aliased locations once and charges temporary scores and workspace at peak.Source: §A.14 · p. 23

B TWO-HEAD SOFTMAX REALIZATION OF THE EXECUTORS

A two-head softmax layer can compile the reduced TD executors, while continuous exact representations require memory proportional to state count times Krylov dimension. The memory lower bound applies to broad model classes, not necessarily restricted task families.

B TWO-HEAD SOFTMAX REALIZATION OF THE EXECUTORS

The two-head softmax construction compiles the executors by encoding log-probability codes in tokens and applying a task-family-fixed gain.Its exactness is in real arithmetic; the gain amplifies probability-rounding error in floating point.Source: B TWO-HEAD SOFTMAX REALIZATION OF THE… · pp. 23–24

C MEMORY LOWER BOUNDS: REAL REGISTERS AND BITS

Every continuous exact representation on the stated open model sets needs at least nk + k real registers, and a construction achieves this bound.The paper’s attention encoder uses (2n + 1)k context reals, within a factor of two of optimal.Source: C MEMORY LOWER BOUNDS: REAL REGISTERS… · p. 25
The lower bound is class-level: restricted families with fewer trajectory degrees of freedom can require less memory.The paper contrasts the bound for dense rank-k systems with block-cycle tasks, for which an encoder can retain only block labels.Source: C MEMORY LOWER BOUNDS: REAL REGISTERS… · pp. 25–26

C.1 PROOF OF THE MEMORY LAW

The appendix proves continuous-encoding lower bounds, gives an offline retained-bit law, and develops limited-context approximation bounds and constructions. Its lower-bound arguments use trajectory information to constrain the degrees of freedom a representation must retain.

C.1 PROOF OF THE MEMORY LAW

A continuous exact representation on the stated open sets requires at least nk + k registers, and an encoding of exactly that size exists.The lower bound follows by constructing a continuous family whose distinct trajectories determine its parameters.Source: §C.1 · p. 26

C.2 OFFLINE RETAINED-BIT COMPLEXITY

For fixed γ and sufficiently small ϵ, the offline retained-bit complexity is Θγ(n min{n, L, ln(1/ϵ)} ln(1/ϵ)).The law is uniform in n and L, including L = ∞; a factor of order 1/(1 − γ) in the depth term remains open in one regime.Source: §C.2 · p. 27

D LIMITED CONTEXT: PROOFS, THE KRYLOV-ANCHORED HOLD, AND INSTANCE-DEPENDENT RATES

Krylov truncation and projection are not minimax below the exact context threshold; the appendix establishes a worst-case error lower bound of Ψm/64.The lower bound applies when kL > m.Source: §D.1 · p. 28, §D.3 · p. 30

D.1 STATEMENTS

Moment matching spends its budget on early increments, whereas the hybrid Krylov-anchored hold also samples later residuals.The appendix notes that whether a uniformly computable time-invariant encoder attains Θ(Ψm) on every system remains open.Source: §D.1 · p. 28

D.2 THREE TOOLS

The lower-bound tools relate trajectory approximation error to the width of block increments and to orthogonal geometrically decaying vectors.The geometric-family lemma gives a dimension-m obstruction when there are sufficiently many such vectors.Source: §D.2 · p. 29

D.3 THE LOWER BOUND Em ≥Ψm/64

On a directed ring with one rewarded state, every m-dimensional context incurs error at least γ^m/4 under the stated size condition.This instance supplies the lower-bound case used to establish the general Ψm/64 result.Source: §D.3 · pp. 29–30

D.4 THE UPPER BOUND AND THE SAMPLE-AND-HOLD CONTEXT

The appendix develops quantile sample-and-hold and Krylov-anchored constructions for limited context, alongside finite-depth guarantees, instance-dependent bounds, and an adaptive-rank certificate. It also compares moment-matching variants and numerically optimized time-invariant recurrences.

D.4 THE UPPER BOUND AND THE SAMPLE-AND-HOLD CONTEXT

Quantile sample-and-hold achieves error at most e^2Ψm, with its sampling schedule chosen using γ.A schedule fixed independently of γ can be worse by a factor Ω(m) when γ is close to one.Source: §D.4 · p. 30

D.5 FINITE DEPTH

For finite depth, the optimal worst-case error is zero exactly when m ≥ L; quantile sampling attains the stated finite-depth upper bound.When γ ≥ 1/2 and 8m ≤ L ≤ 1/(1 − γ), the error lies between L/(400m) and e^2L/m.Source: §D.5 · p. 30

D.6 PROOF OF PROPOSITION D.1

Krylov truncation has worst-case error exactly γ^m/(1 − γ) over systems with kL > m.The appendix gives a matching lower-bound construction by taking a ring with a small reward perturbation.Source: §D.6 · p. 31

D.7 PROOF OF THEOREM D.2

The Krylov-anchored hold combines projected TD increments with sampled residuals and satisfies an error bound while using an m-dimensional context.It is exact whenever kL ≤ k.Source: §D.7 · p. 32

D.9 A CERTIFIED ADAPTIVE RANK

A threshold on Arnoldi residuals certifies an error bound when it fires; otherwise the output is exact through depth L.The retained rank never exceeds kL, and τ = 0 recovers the exact encoder.Source: §D.9 · p. 33

D.10 NUMERICALLY OPTIMIZED TIME-INVARIANT RECURRENCES

On the tested instance, time-invariant recurrences with optimized modes are within 1.8× of optimal and outperform sample-and-hold.The numerical search establishes achievability of the reported values, not global optimality.Source: §D.10 · p. 33

E EXECUTION DEPTH

The section bounds how many executor layers are needed for single-depth TD queries and shows how context encoding in γ affects those bounds. A doubling executor computes the exact depth-L output in logarithmic depth while retaining compressed context.

E EXECUTION DEPTH

For balanced and state-level contexts, polynomial executors need at least log_3(L − 1) layers, while a doubling executor computes the exact output in ⌊log_2 L⌋ + 2 layers.These bounds agree up to a factor of about 1.58 and an additive constant; the lower bound excludes executors using recip0.Source: E EXECUTION DEPTH · p. 34

E.2 DOUBLING EXECUTOR

The doubling executor uses retained Krylov columns and repeated squaring to accumulate the polynomial needed for the requested TD depth.Its retained memory is at most 2(nkL + kL) + O(n); the looped executor instead emits all L depths in one pass at linear depth.Source: E EXECUTION DEPTH · p. 34, §E.2 · pp. 34–35, §E.3 · p. 35

E.1 STRUCTURE OF THE CONTEXT IN γ

Balanced Krylov and state-level contexts are affine in γ, whereas unnormalized Krylov context entries can have Laurent exponents in [−kL, kL].The balanced-context entries have degree at most one in γ, yielding the stronger depth lower bound for that context.Source: §E.1 · p. 34

E.3 PROOFS

The lower bound follows because a depth-t executor has polynomial degree at most 3t, limiting the γ exponents it can match.For targets with a nonzero γ^(L−1) coefficient, this forces L − 1 ≤ 3te.Source: §E.3 · p. 35

F LEARNABILITY OF THE SHARED EXECUTOR

This section studies whether pretraining can identify the shared executor. A calibration objective yields global convergence under suitable operator diversity, while endpoint-only supervision cannot identify the TD step size.

F LEARNABILITY OF THE SHARED EXECUTOR

Calibration uses an isotropic input and compares the executor’s first two increments with their targets, without requiring a solved value function or target parameters.The encoder remains fixed, and the resulting objective is exactly quadratic.Source: F LEARNABILITY OF THE SHARED EXECUTOR · pp. 35–36
Under suitable operator diversity, the calibration objective has a unique target and gradient descent converges globally from any initialization.The theorem identifies the executor, not the encoder; global identification requires tasks that distinguish all operator directions.Source: F LEARNABILITY OF THE SHARED EXECUTOR · p. 35
Endpoint supervision cannot uniquely identify the TD update: different step sizes can yield the same fixed-point prediction.By contrast, the trajectory-map Jacobian at the target is injective, whereas the endpoint map has a nonzero null direction.Source: F LEARNABILITY OF THE SHARED EXECUTOR · p. 36

G CONNECTIONS TO CLASSICAL STATISTICAL AND REDUCED MODELS

The section connects TD context compression to classical statistical compression, Krylov model reduction, and width bounds, then reports implementation checks and context–accuracy experiments. The experiments compare approximation strategies against a certified lower bound across discount factors and context sizes.

G CONNECTIONS TO CLASSICAL STATISTICAL AND REDUCED MODELS

Classical LSTD and iLSTD summarize batch TD data with GN and bN sufficient statistics, while the TD trajectory also connects to finite-horizon minimal realization and moment matching.For the paper’s supremum-over-depth partial-sum error, moment matching is not minimax; its width bound uses block increments at scale 1/(m(1 − γ)).Source: G CONNECTIONS TO CLASSICAL STATISTICAL… · pp. 36–37

H.1 IDENTITY AND BOUND CHECKS

Identity checks compare attention-level implementations with direct references, while additional numerical checks evaluate stated inequalities and use float64 agreement as the meaning of “exact.”The checks include executor and encoder identities, bound checks, and finite-difference Jacobian ranks.Source: §H.1 · pp. 37–38

H.2 CONTEXT–ACCURACY TRADEOFF (FIGURE 2)

On cyclic tasks with kL = 12, Krylov projection error is 0.86 at m = 11 and 6 × 10^-16 for m ≥ 12; on reversible tasks, it falls from 1.1 × 10^-1 at m = 4 to 1.9 × 10^-14 at m = 20.On the reversible tasks, truncation and sample-and-hold have larger errors at the reported context sizes.Source: §H.2 · p. 38

H.3 THE γ-UNIFORM LAW (FIGURE 3)

Sample-and-hold and anchored hold errors stay within [0.45, 2.7] × Ψm and within 21× of the certified bound, while Krylov truncation is up to 37× worse below the horizon at γ = 0.99.The hold methods have log–log slopes −0.89 and −0.93 against predicted −1; truncation’s slope is −0.14.Source: §H.3 · pp. 38–39, Figure 3 · p. 38
The γ-uniform experiments use structured ring instances and a certified lower bound valid for every m-dimensional context.The bound is computed from orthogonal block increments; the figure compares it with sample-and-hold, anchored hold, and Krylov methods at γ = 0.9 and 0.99.Source: Figure 3 · p. 38, §H.3 · p. 39

H.4 SAMPLED NOISY TASKS (FIGURE 4)

On sampled noisy tasks, exact context rank is full even though numerical rank is small, and anchored hold reaches below sampling error with compact contexts. The memory accounting distinguishes retained context from substantially larger peak task memory and qualifies the scope of the continuous-encoder lower bound.

H.4 SAMPLED NOISY TASKS (FIGURE 4)

Anchored hold falls below sampling error with context dimensions 12, 30, and 5 for tasks with n = 144, 126, and 200, respectively.Across the three tasks exact rank is kL = n, but the numbers of normalized trajectory singular values above 10^-2 are only 9, 25, and 5.Source: §H.4 · p. 39

H.5 MEMORY ACCOUNTING (TABLE 5)

On the dense kernel, contexts accurate to 10^-2 are 9× smaller than sparse TD and 150× smaller than the raw batch; on the sparse goal-directed gridworld, sparse TD remains most compact.The comparison concerns retained representations, not peak memory or speed.Source: §H.5 · p. 40, Table 5 · p. 40
The prototype’s peak task memory is 12–16× the statistics, despite retained context being the claimed memory benefit.Peak memory includes encoding and execution working storage; all three peak-memory terms are Θ(n^2).Source: §H.5 · p. 40, Table 6 · p. 40
Float32 storage and execution reproduce the TD trajectory to between 2.0 × 10^-7 and 6.2 × 10^-7 of its largest entry when using a float64 context.Running the whole pipeline in float32 retains kL = 12 tokens on all four tested sizes and has error between 2.0 × 10^-7 and 4.5 × 10^-7.Source: §H.5 · p. 41, Table 7 · p. 41
The retained-memory lower bound nkL + kL applies uniformly over a class of dense rank-kL models, not to the block-cycle instances themselves.An encoder specialized to the block-cycle family can retain only its n block labels; the reported 2.2× ratio is not instance-level optimality on those tasks.Source: §H.5 · p. 41

H.6 LEARNABILITY EXPERIMENTS

Experiments examine executor learning, finite-precision rank handling, feature-space TD, and learned bottlenecks. Compiled contexts achieve strong accuracy in feature-space tasks, while learned bottleneck errors remain nearly flat as their context budget grows.

H.6 LEARNABILITY EXPERIMENTS

Gradient descent on objective (7) reaches parameter error 1.0 × 10^-15 across five seeds, with held-out error 6.8 × 10^-15, while Adam on Jtraj reaches 7.4 × 10^-2.The Jtraj error falls to 3.3 × 10^-3 after continuing the same schedule to 20,000 steps on three seeds.Source: §H.6 · p. 42
The endpoint objective ends at parameter error 0.51, yet its depth-30 output is within 0.038 of TD while its trajectory error reaches 0.50 at depth 1; it fixes the fixed point, not the update.Source: §H.6 · p. 42

H.7 FINITE-PRECISION RANK BOUNDARY

At ε = 10^-16 the float64 input already equals one; balancing bounds context entries, while tolerance can suppress a genuinely nonzero but negligible direction.The text identifies this behavior with the ε-rank criterion.Source: Table 8 · p. 42, §H.7 · p. 42

H.8 FEATURE-SPACE POLICY EVALUATION (TABLE 2)

Boyan’s chain exact context uses k_phiL = 4 = d and reproduces the trajectory to 9.4 × 10^-16; Krylov projection with m = 1, 2, 3 has errors 0.95, 0.34, 0.14.Source: §H.8 · p. 43
At m = 32, Krylov projection reaches relative error 9.1 × 10^-3–1.06 × 10^-2 on mountain car, at most 3.0 × 10^-7 at m = 48, and at most 6 × 10^-15 at m = 64.These results span the four tested values of N.Source: §H.8 · p. 43
Mountain car’s 32-token context retains 108–117 KiB versus 681–800 KiB for LSTD statistics, independent of N, while sparse prompts grow from 332 KiB to 21 MiB.The reported comparison concerns retained memory, not peak memory.Source: §H.8 · p. 43

H.9 LEARNED BOTTLENECK CONTEXTS (FIGURE 5)

Learned bottleneck encoders beat worst-case-tuned compiled schedules on typical tasks at small m, but their error stays nearly flat as m grows, unlike compiled contexts.At m = 24, the learned ring error exceeds the upper bound e2Ψm by 2.0× for clocked and 1.8× for time-invariant executors; the compiled anchored hold has held-out error 0.026.Source: §H.9 · pp. 44–45, Table 9 · p. 45

I SCOPE AND LIMITATIONS

The results concern fixed-policy evaluation of empirical, visitation-normalized TD; extending the laws to control is open. The guarantees distinguish retained reusable context from peak memory and arithmetic, which are not reduced below statistics or direct TD.

I SCOPE AND LIMITATIONS

The setting is fixed-policy evaluation of empirical, visitation-normalized TD; extending the results to control, where the Krylov space changes with policy, remains open.Source: I SCOPE AND LIMITATIONS · pp. 45–46
Peak memory and arithmetic are not reduced below those of statistics or direct TD; the benefit is retained, reusable context, though sparse numerical TD can be smaller for sparse models.Source: I SCOPE AND LIMITATIONS · p. 45
Only the shared executor is shown to be learnable; joint training of encoders remains open, and trained encoders are evaluated on the paper’s task distribution rather than natural pretraining data.Source: I SCOPE AND LIMITATIONS · p. 45