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

Why is Length Generalization (LG) so dependent on Positional Encoding (PE)? Relative schemes can extrapolate fixed offsets, and absolute schemes fix positions, but both struggle with growing offsets. A new paper proposes a "positional realizability theory" that derives this widely documented empirical pattern through a carefully controlled single-head positional attention abstraction, and precisely identifies the boundary where it holds and fails.

Theoretical Core: The Simulated Transition Operator and α_L

The core tool of the theory is the simulated transition operator $T_L$, which re-evaluates a selected positional kernel that realizes length $L_0$ on a longer grid. Crucially, a scalar $\alpha_L \in [0,1]$ can be read out from $(\Phi, t_n)$ alone before any training. $\alpha_L$ serves as a computable witness for the taxonomy's derivation, rather than a stronger empirical predictor.

Theoretical results include: a relative head-depth row characterization for kernels with a strict unique global maximum (Theorem 2), an absolute/relative duality that derives the pattern (Proposition 4), an uncertainty result for learning absolute positions, and a static expressive capacity bound. A sufficiency theorem (Theorem 1) links $\alpha_L$ to length generalization, while the general deterministic case remains an exact open conjecture (correcting a tempting but invalid "outer-span" argument).

Positional kernel is a similarity function induced by positional encoding (PE) in the attention mechanism, used to measure the relative or absolute relationship between query positions and key positions. In single-head attention, the positional kernel typically appears as a scalar function $k(i,j)$, where $i$ and $j$ are the position indices of the query and key, respectively. For relative positional encoding, the kernel depends only on the offset $i-j$; for absolute positional encoding, it depends on the specific values of $i$ and $j$. The "kernel transition" in the theory refers to re-evaluating the behavior of a kernel selected at training length $L_0$ on a longer grid, thereby determining whether it can achieve length generalization. The mathematical properties of the positional kernel (such as a unique global maximum and continuity) directly determine the possibility of length generalization, which is the basis for the analysis of the simulated transition operator $T_L$.

Experimental Validation: α_L Precisely Separates Generalizing and Non-Generalizing Units

Experiments confirm this structure: in controlled single-head mechanisms, $\alpha_L$ precisely separates the generalizing and non-generalizing (PE, task) units in the taxonomy (2625 trained-model measurements in total, stable at vocabulary size 64 and dimension 128). This means that, based solely on the scalar $\alpha_L$, one can determine before training whether a given combination of positional encoding and task can achieve length generalization.

The study also points out that these results transform the existing PE taxonomy into a positional kernel transition theorem, and identify content and depth mechanisms that escape the theorem.

Single-head positional attention abstraction is a theoretically simplified model: it retains only one attention head, and that head attends only to positional information (ignoring token content), thereby reducing the length generalization problem to the analysis of the behavior of a positional kernel on a long grid. This abstraction strips away the complexity of multi-head interactions and content mixing, enabling researchers to precisely derive the mathematical properties of positional encoding. This abstraction corresponds to the "minimal working unit" of the positional channel in an actual Transformer; if generalization fails even in this simplified model, it is even harder for the full model to compensate through content mechanisms. The controlled single-head mechanisms in the experiments are built on this abstraction to ensure that the measurements directly reflect the generalization ability of the positional kernel, rather than interference from other factors.

Theoretical Boundary: Focus Only on the Positional Channel

The theory concerns only the positional channel itself. Tasks whose targets depend on token content, including standard length generalization test suites (such as addition and sorting), fall outside the scope of Theorem 2. This clarifies the applicable boundary of the theory: it explains the properties of the positional encoding scheme itself, not content-related generalization ability.

Length generalization test suites are standard benchmarks for evaluating model performance beyond the training length; common tasks include addition (adding two multi-digit numbers), sorting (sorting a sequence of numbers), and copying. These tasks typically require the model to maintain correct output on sequences longer than those seen during training, thus challenging the extrapolation ability of positional encoding. However, the target outputs of these tasks depend on token content (such as the values of numbers), not merely positional relationships. Therefore, the positional realizability theory can only explain the contribution of the positional channel and cannot cover generalization behavior arising from the interaction between content and position. This explains why the theory excludes addition and sorting from the scope of Theorem 2, and points out that content mechanisms may "escape" the constraints of the positional channel.

Significance and Open Questions

This work bridges the gap between empirical observations and theoretical explanations, providing computable theoretical guidance for the choice of positional encoding. At the same time, the general deterministic case remains an open conjecture, and how content and depth mechanisms break through the constraints of the positional channel is also a direction for future research.

One-line Summary

A new paper proposes a positional realizability theory that derives the dependency boundary between length generalization and positional encoding using single-head attention.

Paragraph Summary

This paper proposes a "positional realizability theory" aimed at explaining why length generalization depends on positional encoding. The core of the theory is the simulated transition operator T_L and the scalar α_L, the latter of which can be computed from the positional kernel and task before training and serves as a computable witness that precisely separates generalizing and non-generalizing units. Experiments validate the separating ability of α_L across 2625 training runs, stable at vocabulary size 64 and dimension 128. The theory derives a relative/absolute positional encoding duality, an uncertainty result for learning absolute positions, and a static expressive capacity bound, but it applies only to the positional channel itself; content-related tasks (such as addition and sorting) fall outside the scope of Theorem 2. The general deterministic case remains an open conjecture, and content and depth mechanisms can evade the theory.