A Positional Realizability Theory of Length Generalization in Single-Head Attention

AI summary

Overview

Research area: Machine learning theory — specifically the theory of length generalization (LG) and positional encoding (PE) in transformer attention, sitting at the intersection of attention expressivity results and the empirical "PE taxonomy" literature.

Technical level: Advanced. The paper is a theorem-and-proof paper (linear algebra over positional feature maps, kernel families, argmax/margin arguments), though its central intuition — fit a kernel at a short length, re-evaluate it at a longer length, and count how often the attention still lands on the right key — is explainable without the formalism.

Scope in one sentence: The paper builds an exact, pre-training, data-free theory of which (positional encoding, task) pairs can length-generalize through the positional channel of a single attention head, and maps precisely where that channel stops being the operative mechanism.

What This Paper Is About

Empirically, whether a transformer trained on short sequences works on longer ones depends sharply on the positional encoding: relative schemes like RoPE and ALiBi handle fixed relative offsets, absolute schemes lock fixed positions, learned-absolute encodings typically fail, and growing-offset tasks such as copy and reverse defeat essentially everything. What has been missing is an account that derives this observed pattern from the attention mechanism itself rather than cataloguing it. The authors supply such an account for a deliberately controlled abstraction — one positional-only attention head — via a quantity computed from the PE's feature map and the task's target function alone, before any training.

Key Contributions

1. A realizability framework built on a simulation transfer operator. The authors define an operator T_L that takes the length-L_0-realizing positional kernel parameter W and re-evaluates it on the longer length-L grid (Φ_L W Φ_Lᵀ), with no retraining. From this they define a scalar simulation alignment α_L ∈ [0,1]: the fraction of newly scored rows on which the transferred kernel's strict masked argmax hits the task's target position. α_L is computed from (Φ, t_n) alone — no end-to-end Transformer training, no data samples, no learned Transformer parameters, only a deterministic kernel-selection rule on the PE basis.

2. A sufficiency theorem plus a relative-head necessity theorem. Theorem 1 shows that α_L = 1 (with positive margin on new rows) implies exact length generalization at length L, for any realizing W — including the regularized cross-entropy fit actually used. Theorem 2 gives a deep-row characterization for relative (translation-invariant) kernel families: transfer succeeds iff the required offset is constant on a density-one set of deep rows and that constant is attainable as the strict unique global maximizer of a kernel that already realizes the task at L_0.

3. Supporting results that derive the PE taxonomy. A static expressivity bound (Proposition 1) showing affine positional features can only ever place an argmax at a window endpoint; a learned-absolute underdetermination result (Proposition 2) showing new-row extrapolation is at or below chance; a sinusoidal existence-vs-selection result (Proposition 3); and an absolute/relative duality (Proposition 4) that reproduces the empirical split. The general deterministic-PE case remains an explicit open conjecture (Conjecture 1), and the authors correct a tempting but invalid "outside-colspan" argument.

4. Empirical confirmation and an explicit boundary map. Across 2625 trained-model measurements, α_L separates the taxonomy's generalizing from non-generalizing (PE, task) cells with AUC = 1.0, robust to vocabulary and width. The paper also delineates where the theory stops applying — content-channel escapes (induction, ALiBi prev), under-prediction for low-frequency relative PEs, and content-dependent tasks such as addition and sorting.

Main Findings

• α_L = 1 certifies length generalization. Theorem 1 shows that if the selected kernel solves length L_0 with margin γ_0 > 0 and scores α_L = 1 with margin γ_L > 0 on new rows, then it solves length L with margin min(γ_0, γ_L). The mechanism is the causal mask: rows below L_0 see identical logits at both lengths, so only new rows need checking.

• Relative heads need two conditions, not one. Theorem 2 states that a relative kernel family transfers iff (i) the demanded offset is δ* on all but a vanishing fraction of scored rows, and (ii) δ* is the strict unique global maximizer of some kernel that already realizes the task at L_0. Attainability must be inside the L_0-realizing set, not merely inside the family — otherwise α_L → 1 without solving the task at either length.

• Fixed offsets generalize; growing offsets provably do not. Prev-token and skip-k are realizable by any relative family containing a kernel peaked at k. Copy (δ_L = ⌈L/2⌉) and reverse fail for every kernel with a strict unique global maximizer: the deep-row argmax is pinned to a length-independent constant, so a growing or within-length-varying target is missed on a non-vanishing fraction of rows.

• Affine positional features can never place an interior argmax. Proposition 1 shows that with φ(i) = [1, i]ᵀ, the logit is affine in the key index, so the unique masked maximizer is always the right endpoint, the left endpoint, or a flat tie. Any interior-target task (e.g. prev-token for i ≥ 2) is unrealizable at every length n ≥ 3, for any W. This is why canonical ALiBi — whose basis {1, (i−j)} is affine in the offset — has α_L = 0 on prev-token.

• Learned-absolute extrapolation is at or below chance. Proposition 2 shows that for a selection rule depending only on trained rows, Pr[M_i = t_L(i) | M_i ∈ N_i] = 1/(k−1). Monte-Carlo at L = 30 gives a conditional hit rate of 0.115 against 1/(k−1) = 0.111, with an unconditional rate of 0.034 because the winner lands among the new keys only 30% of the time; at L = 60 the figures are 0.025 / 0.026 / 0.016 with 65%. A rescuing W exists with probability roughly 20–35% in their Monte-Carlo — the selection rule simply cannot find it.

• Sinusoidal PEs: existence is not selection. Proposition 3 shows a kernel realizing any fixed offset exists at all lengths for sinusoidal encodings, yet the L_0-fit does not pick it: sinusoidal prev decays to α_L = 0.45 at L = 60 and 0.34 at L = 128. The paper explicitly refutes the common intuition that sinusoidal fails once the offset exceeds the lowest-frequency period: within the standard 16 frequencies and base 10⁴, the component sin(d·θ_min) with θ_min ≈ 1.78·10⁻⁴ is increasing up to d ≲ 8833, and at L = 17665 the demanded copy offset is exactly 8833, where that kernel attains α_L = 1.

• Absolute/relative duality derives the taxonomy. Proposition 4: relative families generalize fixed relative offsets (α_L = 1 for prev/skip-k), clamped learned-absolute generalizes fixed absolute positions (α_L = 1) but ties exactly on new keys for relative targets (α_L = 0, margin 0), and neither side handles growing offsets. RoPE on attend-first decays at α_L = 0.80, 0.40, 0.20, 0.12, 0.055, 0.039 at L = 30, 40, 60, 128, 256, 512. Directly measured: attend-first clamped-absolute 1.00 vs relative 0.00; prev clamped-absolute 0.00 (an exact tie) vs relative 1.00.

• Clean empirical separation, stated as a witness not a predictor. α_L separates generalizing from non-generalizing cells with AUC = 1.0 across 2625 trained-model measurements, stable at vocab 64 and d = 128. As a practical predictor it matches but does not beat the coarse taxonomy it explains — the authors searched for a winning cell and report the negative.

• Selection-rule dependence is quantified. The reported α_L uses a regularized cross-entropy section (400 Adam steps, weight decay 10⁻⁴); an ablation shows it tracks LG with ρ = 0.91 versus ρ = 0.56 for the min-norm interpolant. The authors therefore call α_L model-free and data-free but selection-rule dependent, not "gradient-free".

• Content and depth are the escape routes. An induction task length-generalizes through the content channel exactly where positional α_L = 0; ALiBi prev generalizes via content despite α_L = 0; and α_L under-predicts low-frequency relative PEs. Tasks whose targets depend on token content — including the standard suite such as addition and sorting — fall outside Theorem 2.

Methodology in Plain English

The authors deliberately strip the problem down to one positional-only attention head (hypotheses S1–S3: single head, one layer, positional-only; "solve" means correct masked row-argmax with margin > 0; content-neutrality on evaluated rows). The procedure has four steps.

Fit. At training length L_0, find a parameter W whose positional kernel Φ_{L_0} W Φ_{L_0}ᵀ realizes the task's required pattern. The authors use a regularized cross-entropy fit (400 Adam steps, weight decay 10⁻⁴), which they argue mirrors how a head is actually trained; as regularization vanishes this approaches the max-margin direction.

Transfer. Apply the same W to a longer grid, P_L = Φ_L W Φ_Lᵀ, with no retraining. The operator is defined on the parameter W, not on the kernel block, because a rank-deficient Φ_{L_0} means two heads with identical L_0 kernels can transfer differently.

Score. Check the old rows (they keep their argmax by the causal-mask identity of Theorem 1) and then count the fraction of new rows in [L_0, L) — restricted to the task's own query region — where the transferred kernel's strict masked argmax equals the target. Exact ties count as failures, which matters for the clamped learned-absolute encoding whose new-row logits tie exactly. This single normalization over the task's own query region is used everywhere, including in Theorem 2.

Separate theory from measurement. The paper is explicit that the fitted kernel certified by Theorem 1 and the trained Transformer measured in experiments are different objects; the gap between them is attributed to selection, content, and depth.

Why This Matters

Impact on research. The paper turns a received empirical checklist into a derived theorem, for a scope where exactness is achievable. It fills a specific gap: RASP-L is a discrete qualitative conjecture, C-RASP[Pos] is task-level and binary, Izzo et al. supply a simulation sufficiency bound evaluated on trained models, and spectral analyses are post-hoc. α_L is pre-training, keyed to the PE's feature map, continuous, single-head, and comes with matched sufficiency and relative-head necessity in one formalism. The impossibility results sit in the lineage of attention expressivity bounds, and the paper is candid about what is novel (the tie-rule-independent deep-row argument and the training-accuracy corollary) versus what overlaps existing intuition.

Real-world applications (implications drawn from the paper's framing):

• Pre-training triage for long-context models: estimate α_L from the feature map and target function to rule out a (PE, task) pairing before spending compute.
• Arithmetic and reasoning workloads: the paper situates LG as a bottleneck for tasks "from arithmetic to long-context reasoning," and identifies where positional realizability cannot carry the target.
• Copying and reversing operations (list reversal, deduplication, span copying), which the theory classifies as growing-offset failures for any relative kernel with a strict unique global maximizer.
• Architecture selection for position-locked tasks: attend-first-style behavior, where clamped absolute encodings score α_L = 1 and relative ones score 0.00.

Industry relevance. A quantity computable before training, from the encoding and the task alone, is directly useful for model-design decisions where every experiment is expensive — and the paper is honest that its value is diagnostic and theoretical rather than a leaderboard improvement.

Future Directions

• Conjecture 1 — the general deterministic case. The characterization is complete for relative families with a strict unique global maximizer; for arbitrary deterministic φ it remains a precise open conjecture, with an erroneous "outside-colspan" argument explicitly corrected rather than papered over.
• Closing the existence-vs-selection gap. Proposition 3 shows a realizing kernel exists for fixed sinusoidal offsets but the L_0-fit does not select it. Characterizing selection rules that recover such kernels — and understanding why the cross-entropy section (ρ = 0.91) beats min-norm (ρ = 0.56) — is a natural next step.
• Extending beyond the positional channel. The content and depth mechanisms that escape the theory (induction heads, ALiBi prev, data routing) are mapped but not formalized; a theory covering multi-head, multi-layer content-dependent computation would reach the standard LG suite (addition, sorting) that currently falls outside Theorem 2.
• Explaining the under-prediction for low-frequency relative PEs, where α_L is systematically pessimistic — a discrepancy the current theory does not account for.

Target Audience

Machine learning theorists and mechanistic-interpretability researchers working on transformer expressivity, positional encoding design, and length generalization. It is most valuable to readers comfortable with linear algebra and argmax/margin arguments who want a rigorous, scoped account of why the PE taxonomy holds — and equally to practitioners designing long-context or reasoning architectures who need to know which (PE, task) pairs are ruled out in advance and, just as importantly, where the positional channel is not the binding constraint. Readers seeking a new state-of-the-art method or benchmark result should note the authors' own framing: α_L matches but does not beat the taxonomy it explains.

Authors’ abstract

Why does length generalization (LG) depend so sharply on the positional encoding (PE)? Relative schemes extrapolate fixed offsets, absolute schemes fix positions, and neither handles growing offsets. We give a realizability theory for a deliberately controlled abstraction, a single positional-only attention head, that derives this well-documented empirical pattern and says precisely where it holds and breaks. The device is a simulation transfer operator $T_L$ that re-evaluates a selected length-$L_0$-realizing positional kernel on the longer grid, with a scalar $α_L \in [0,1]$ read off before any training from $(Φ, t_n)$ alone. Here $α_L$ serves as the computable witness of that taxonomy's derivation, not as a stronger empirical predictor. Our results are a relative-head deep-row characterization for kernels with a strict unique global maximizer (Theorem 2), an absolute/relative duality that derives the pattern (Proposition 4), a learned-absolute underdetermination result, and a static expressivity bound; a sufficiency theorem (Theorem 1) bridges $α_L$ to LG, and the general deterministic case is a precise open conjecture (correcting a tempting but invalid "outside-colspan" argument). Experiments confirm the structure: in the controlled single-head regime $α_L$ exactly separates the taxonomy's generalizing and non-generalizing (PE, task) cells (2625 trained-model measurements; stable at vocab 64/d=128). Together, these results turn the received PE taxonomy into a positional-kernel transfer theorem, and identify the content and depth mechanisms that escape it. The theory concerns the positional channel alone: tasks whose targets depend on token content, including the standard length-generalization suite such as addition and sorting, fall outside Theorem 2.