The Expressive Geometry of Local Attention: Why Restricting Context Can Expand Capability

The Efficiency Paradox in Transformer Design

The transformer architecture has become the dominant substrate for modern language modeling, yet one of its most puzzling variants continues to challenge our intuitions about computational expressivity. Local attention, which restricts each token to attending only to a fixed size window of predecessors, was originally introduced as an efficiency measure. By reducing the quadratic complexity of global attention to linear cost in sequence length, local attention enables processing of longer documents within fixed computational budgets. However, empirical observations have repeatedly shown that local attention does more than accelerate computation. In machine translation and language modeling tasks, models employing local attention often outperform their global counterparts even when computational resources are held constant. This phenomenon, noted by practitioners but lacking theoretical explanation, forms the central puzzle addressed in "Characterizing the Expressivity of Local Attention in Transformers" by Jiaoda Li and Ryan Cotterell.

The resolution proposed by Li and Cotterell departs from standard complexity theoretic analyses. Rather than examining time or space complexity, they analyze recognizer expressivity through the lens of formal language theory. Specifically, they characterize transformer language models in terms of linear temporal logic (LTL), revealing that local attention does not merely approximate global attention but introduces genuinely distinct representational capabilities.

Temporal Logic and the Semantics of Attention

To understand the theoretical contribution, one must first grasp the correspondence between attention mechanisms and temporal operators. Prior work by Li and Cotterell (2025) established that fixed precision transformers with global attention correspond exactly to LTL[P], the fragment of linear temporal logic containing only the past operator P. This operator allows formulas to assert properties about some previous position in the sequence without bound on how far back the dependency extends. Intuitively, global attention enables the model to aggregate information from arbitrarily distant tokens, mirroring the unbounded reach of the P operator.

Li and Cotterell extend this framework by proving that local attention introduces a second temporal operator: Y, the yesterday operator. While P looks back unboundedly, Y looks back exactly one step (or more generally, a bounded number of steps). This distinction maps cleanly onto the architectural difference between global and local attention. Global attention layers can implement dependencies that span the entire prefix of a sequence, while local attention layers enforce strict locality constraints, effectively bounding the temporal horizon of information aggregation.

The authors further prove that purely local attention collapses expressivity to the class of definite languages. A language is m-definite if membership can be determined solely by examining the final m symbols of the string. This class, first studied by Kleene in 1956, represents the formal analog of n-gram models, where prediction depends only on a fixed length suffix of the context. While this might suggest local attention is strictly weaker than global attention, the critical insight lies in what happens when both are combined.

Complementary Expressivity and Hybrid Architectures

The central theoretical result establishes that global and local attention are expressively complementary. Neither architectural variant subsumes the other. Global attention (LTL[P]) can express dependencies that local attention cannot, particularly those requiring unbounded lookback. Conversely, local attention (LTL[Y]) enables recognition of locally testable languages, a class extensively studied in algebraic formal language theory and closely connected to n-gram models, which pure global attention cannot recognize without additional mechanisms.

When combined into hybrid architectures, the resulting system corresponds to LTL[P,Y], strictly enlarging the class of recognizable regular languages beyond what either mechanism achieves in isolation. This formal separation explains the empirical superiority of hybrid models. The global component captures long distance dependencies and structural constraints, while the local component encodes fine grained local patterns and positional regularities. The interaction between these distinct temporal operators creates representational capacity unavailable to pure architectures.

Empirical Validation and the Window Size One Phenomenon

Li and Cotterell validate these theoretical predictions through experiments on formal language recognition with length generalization. They compare three architectural variants: pure global attention, pure local attention, and hybrid models combining both. The results align precisely with the theory. Hybrid models recognize strictly more languages than either pure variant and demonstrate superior generalization to sequences longer than those seen during training.

A surprising empirical finding concerns the optimal window size for local attention. Across both formal language tasks and natural language modeling on WikiText-2, a window size of one consistently outperforms larger windows. This suggests that the value of local attention lies not in aggregating substantial local context, which global attention could theoretically approximate, but in enforcing a hard constraint on immediate predecessor relationships. The authors additionally test whether sophisticated positional encodings, specifically sinusoidal (SiPE) and rotary (RoPE) embeddings, can compensate for the absence of local attention. Their results indicate that while these encodings improve global attention models, they cannot replicate the expressivity gains provided by explicit local attention mechanisms.

Implications for Modern Language Model Design

This work carries significant implications for how we conceptualize attention mechanism design. Current trends in large language model development often treat local or sparse attention patterns purely as optimization strategies, necessary evils to accommodate longer contexts within hardware constraints. The formal analysis by Li and Cotterell suggests we should view these as expressivity enhancements. When designing hybrid architectures, we are not merely approximating global attention more efficiently; we are expanding the formal representational capacity of the model.

The finding that window size one provides optimal performance invites deeper speculation about the nature of linguistic structure. Natural language exhibits strong local dependencies at the syntactic and lexical levels. Bigram and trigram statistics capture substantial linguistic regularity. By dedicating specific attention heads or layers to strictly local computation, hybrid architectures may better align with the hierarchical and locally constrained structure of human language. This suggests that optimal transformer designs might employ heterogeneous attention patterns, with some layers restricted to immediate neighbors while others maintain global reach.

Furthermore, this formal framework offers a principled approach to architecture search. Rather than treating attention patterns as hyperparameters to be tuned purely on downstream task performance, we can analyze what formal language classes a given pattern enables recognition of. For applications requiring detection of local patterns, such as parsing or certain types of logical reasoning, explicit local attention provides theoretical guarantees that global attention with positional encoding cannot match.

Limitations and Future Directions

Several limitations temper these conclusions. The theoretical analysis assumes fixed precision transformers and restricts attention to regular languages, excluding context free or context sensitive languages that might require additional mechanisms such as recurrence or external memory. The empirical evaluation, while supportive, focuses on length generalization rather than the full complexity of natural language understanding. Additionally, the optimality of window size one, while robust across the tested conditions, may not generalize to all domains or tasks requiring broader local context.

Looking forward, this work raises compelling questions about adaptive attention mechanisms. If global and local attention provide complementary expressivity, might we design architectures that dynamically select between these modes based on input complexity? The correspondence with linear temporal logic also invites exploration of other temporal operators. Could transformers with specialized attention patterns implement the since operator (S) or the until operator (U), thereby capturing richer temporal dependencies? As language models increasingly serve as general purpose computational engines accessed through prompting, understanding their formal recognitional capacities becomes not merely an academic exercise but a practical necessity for predicting their capabilities and limitations.