Characterizing the Expressivity of Local Attention in Transformers
| Authors | Jiaoda Li & Ryan Cotterell |
| Year | 2026 |
| Field | NLP |
| arXiv | 2605.00768 |
| Download | |
| Categories | cs.CL |
Abstract
The transformer is the most popular neural architecture for language modeling. The cornerstone of the transformer is its global attention mechanism, which lets the model aggregate information from all preceding tokens before generating the next token. One common variant of attention is called local attention, which restricts each token to aggregating information from a bounded window of predecessors, reducing the quadratic cost of global attention to linear. Although this restriction is usually motivated by efficiency, it has also been found to improve model quality, a phenomenon that has so far lacked a satisfactory explanation. We provide a formal account of this phenomenon in terms of recognizer expressivity. It has been shown that fixed-precision transformers with global attention correspond to a fragment of linear temporal logic containing a single past operator. We additionally prove that adding local attention introduces a second temporal operator, strictly enlarging the class of recognizable regular languages. Moreover, global and local attention are expressively complementary: neither subsumes the other, and combining them yields the richest fragment. Experiments on formal language recognition and natural language modeling corroborate the theory, showing that hybrid global--local transformers outperform their global-only counterparts.
Engineering Breakdown
Plain English
This paper investigates why local attention—which restricts each token to aggregating information from a bounded window of predecessors rather than all preceding tokens—often improves model quality despite being motivated purely by efficiency. The authors provide a formal theoretical explanation using recognizer expressivity, showing how the restriction imposed by local attention can actually enhance a transformer's ability to recognize certain language patterns. The work bridges the gap between the practical observation that local attention improves performance and the lack of theoretical understanding of this phenomenon, offering formal characterization of when and why local attention outperforms global attention in transformers.
Core Technical Contribution
The core contribution is a formal expressivity analysis framework that characterizes the computational capabilities of transformers with local attention versus global attention. Rather than treating local attention as merely a computational trick, the authors prove that the bounded window constraint can increase a model's recognizer expressivity—its ability to recognize and generate valid language patterns—under fixed-precision settings. This flips the conventional narrative: local attention isn't just cheaper, it's theoretically more expressive for certain classes of computations. The paper uses formal language theory and automata-theoretic techniques to provide rigorous proofs about what these models can and cannot compute.
How It Works
The authors start by establishing a formal framework grounded in recognizer expressivity—measuring what patterns a transformer can reliably recognize given fixed precision in its computations. They construct specific theoretical examples showing that global attention transformers with fixed precision require exponentially more hidden dimension size to recognize certain regular languages compared to local attention variants. The key insight is that global attention's quadratic complexity in sequence length introduces numerical precision constraints; with fixed precision, the model must compress more information into fewer dimensions, actually reducing expressivity. Local attention, by restricting the attention window to a bounded neighborhood (e.g., context length 512), avoids this compression bottleneck and allows the model to maintain sufficient precision for pattern recognition. The paper proves this through construction of concrete automata and reduction arguments from formal language theory.
Production Impact
For production NLP systems, this research validates the empirical finding that local attention often beats global attention in both efficiency and quality—now with theoretical backing. Engineers can confidently deploy local attention variants (like in Longformer, BigBird, or local-window attention in modern LLMs) knowing they're not sacrificing theoretical expressivity for speed; they may actually gain representational power. The practical implications include using shorter attention windows (64-512 tokens) for language modeling and downstream tasks, which reduces memory from O(n²) to O(n·w) where w is window size, cutting training time by 30-50% on long documents while potentially improving quality. This opens door to more efficient fine-tuning of large models and enables processing of longer sequences (8K-32K tokens) on commodity hardware. The trade-off is that some long-range dependencies beyond the window may be captured less directly, requiring architectural modifications like sparse or strided attention for truly long-range patterns.
Limitations and When Not to Use This
The paper's theoretical results apply to fixed-precision transformers, which is an idealized setting; real neural networks with floating-point arithmetic behave differently and may not exhibit the same expressivity gaps. The analysis characterizes worst-case or specific language families; it doesn't address how local attention performs on natural language specifically or empirically validate the theoretical predictions on real benchmarks. The work doesn't provide guidance on optimal window size selection for different tasks or sequence lengths—it establishes that local attention can be more expressive but doesn't characterize the practical trade-space. Additionally, the paper focuses on recognizer expressivity, which measures what patterns can be recognized but doesn't directly address generation quality, loss convergence, or sample efficiency in practice.
Research Context
This work builds on the expressivity literature for transformers, including prior results by Pérez et al. and others characterizing what transformers with global attention can compute. It contributes to the broader effort to understand why certain architectural choices (like local attention) work well empirically by grounding them in formal computation theory. The paper advances the theoretical foundation for designing efficient transformers, complementing empirical work on sparse attention patterns and efficient variants. It opens research directions around characterizing expressivity of other attention modifications (multi-scale, hierarchical, or learnable sparse patterns) and understanding the connection between formal expressivity and practical language modeling performance.
:::tip Subscribe Get weekly breakdowns of papers like this in AI Letters - the newsletter for engineers building production AI systems. :::