pith. sign in

arxiv: 2605.00768 · v3 · pith:UL5I747Mnew · submitted 2026-05-01 · 💻 cs.CL

Characterizing the Expressivity of Local Attention in Transformers

Jiaoda Li , Ryan Cotterell This is my paper

Pith reviewed 2026-05-20 23:57 UTC · model grok-4.3

classification 💻 cs.CL
keywords local attentiontransformer expressivitylinear temporal logicregular languagesattention mechanismslanguage recognitionglobal attention
0
0 comments X

The pith

Local attention introduces a second temporal operator to transformers, strictly enlarging the class of recognizable regular languages.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Fixed-precision transformers with global attention match a fragment of linear temporal logic that contains only a single past operator. Adding local attention supplies a second distinct temporal operator, which lets the model recognize a strictly larger set of regular languages. Global attention and local attention turn out to be complementary: each can express properties the other cannot, and models that combine both reach the richest fragment. This logical difference supplies a formal reason why local attention sometimes improves quality even when quadratic cost is not the bottleneck. Experiments on formal-language recognition and natural-language modeling confirm that hybrid global-local models outperform global-only baselines.

Core claim

Fixed-precision transformers with global attention correspond to a fragment of linear temporal logic containing a single past operator. Adding local attention introduces a second temporal operator, strictly enlarging the class of recognizable regular languages. Global and local attention are expressively complementary: neither subsumes the other, and combining them yields the richest fragment.

What carries the argument

The correspondence between fixed-precision transformer attention and fragments of linear temporal logic, where global attention supplies one past operator and local attention supplies a distinct second operator.

If this is right

  • Hybrid global-local transformers recognize a strictly larger set of regular languages than either mechanism alone.
  • Global attention and local attention each capture temporal properties the other misses.
  • Models using both attention types achieve the most expressive fragment among the architectures compared.
  • Observed quality gains from local attention may arise from this added expressivity rather than from efficiency alone.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Attention-type choices in new architectures could be guided by the specific temporal-logic fragment a downstream task requires.
  • Analogous logical characterizations might be derived for other restricted attention patterns such as sliding windows of fixed radius.
  • Targeted tests on formal languages known to need two distinct past operators could map the exact contribution of local attention.

Load-bearing premise

That fixed-precision global-attention transformers can be exactly characterized as a fragment of linear temporal logic with precisely one past operator.

What would settle it

A regular language that requires two temporal operators yet is recognized by a global-only transformer (or vice versa), which would violate the claimed complementarity.

Figures

Figures reproduced from arXiv: 2605.00768 by Jiaoda Li, Ryan Cotterell.

Figure 1
Figure 1. Figure 1: Forbidden configuration in the minimal DFAs of view at source ↗
Figure 2
Figure 2. Figure 2: Minimal DFAs. Nodes represent states and arrows view at source ↗
Figure 3
Figure 3. Figure 3: Heatmap of longest perfect lengths (maximum over runs) across formal languages, attention patterns, and positional view at source ↗
Figure 4
Figure 4. Figure 4: Perplexity on WikiText-2 for local, hybrid, and global attention patterns under different positional encodings. Curves view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The manuscript claims that fixed-precision transformers with global attention correspond to a fragment of linear temporal logic containing a single past operator (extending prior results). It proves that adding local attention introduces a second temporal operator, strictly enlarging the class of recognizable regular languages. Global and local attention are expressively complementary—neither subsumes the other—and their combination yields the richest fragment. These results are supported by formal proofs and experiments on formal language recognition and natural language modeling.

Significance. If the central correspondences hold, the work supplies a formal explanation for why local attention can improve model quality beyond efficiency gains, by linking it to increased expressivity over regular languages. It extends existing logical characterizations of global attention and provides a basis for understanding hybrid architectures. The explicit proofs of enlargement and complementarity, together with experimental corroboration on both synthetic and natural language tasks, constitute the main strengths.

major comments (2)
  1. [§3.3] §3.3, the reduction establishing the local-attention to second-past-operator correspondence: the argument that a fixed-size window plus attention aggregation implements precisely one additional LTL operator (without extra power from softmax or value projection) is load-bearing for the strict-enlargement claim. The derivation must explicitly rule out simulation of additional temporal patterns via repeated local steps or residual global-like behavior within the window.
  2. [§4.2] §4.2, Theorem 3 on complementarity: the separating languages (one recognizable by global but not local, and vice versa) must be constructed and verified in detail to confirm they remain outside the other fragment even after accounting for multiple layers or varying window sizes; without this, the 'neither subsumes the other' claim is not fully secured.
minor comments (2)
  1. [§2] Notation for the LTL fragments (single vs. two past operators) should be aligned more explicitly with the cited prior work on global attention to facilitate direct comparison.
  2. [Table 2] Experimental tables (e.g., Table 2) would benefit from reporting variance or multiple random seeds to make the corroboration of the theory more robust.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading and constructive comments on our manuscript. We address each major comment below, clarifying the relevant proofs and indicating the revisions we will make to strengthen the presentation.

read point-by-point responses

  1. Referee: [§3.3] §3.3, the reduction establishing the local-attention to second-past-operator correspondence: the argument that a fixed-size window plus attention aggregation implements precisely one additional LTL operator (without extra power from softmax or value projection) is load-bearing for the strict-enlargement claim. The derivation must explicitly rule out simulation of additional temporal patterns via repeated local steps or residual global-like behavior within the window.

    Authors: We agree that this correspondence is central to the strict-enlargement result. Section 3.3 proves both directions of the equivalence: local attention with a fixed window recognizes exactly the languages expressible by adding one additional past operator to the single-operator fragment, and conversely. The multi-layer case is handled by showing that compositions of local steps remain within the two-operator LTL fragment, because each local aggregation is strictly bounded by the window and cannot encode unbounded or independent temporal relations. The proof also establishes that value projections and softmax within the local mask cannot simulate global behavior, as the attention scores are confined to the window. We will add an explicit remark and supporting lemma in the revised Section 3.3 to rule out these possibilities more directly. revision: yes

  2. Referee: [§4.2] §4.2, Theorem 3 on complementarity: the separating languages (one recognizable by global but not local, and vice versa) must be constructed and verified in detail to confirm they remain outside the other fragment even after accounting for multiple layers or varying window sizes; without this, the 'neither subsumes the other' claim is not fully secured.

    Authors: The separating languages and their verification appear in the proof of Theorem 3. The global-only language requires arbitrary-distance dependencies that no fixed window (regardless of size or number of layers) can capture. The local-only language requires isolation of strictly local patterns that global attention cannot enforce. The argument already accounts for multiple layers by showing that the global fragment cannot simulate the local one even with arbitrary depth, and vice versa. To address the request for expanded detail, we will include additional verification steps and explicit checks against multi-layer and variable-window simulations in the revised main text or appendix. revision: partial

Circularity Check

0 steps flagged

No circularity: formal proof extends cited prior characterization independently

full rationale

The derivation relies on a cited prior result establishing that fixed-precision global attention corresponds to a single-past-operator fragment of LTL, then provides new proofs that local attention introduces a second operator and that the fragments are complementary. These are independent formal arguments within the logical framework rather than reductions by construction, self-definitions, or fitted inputs. No equations or claims in the paper equate a derived expressivity result directly to its modeling assumptions or to self-citations in a load-bearing way. The work is self-contained as a theoretical extension against external logical benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the prior result linking global attention to a single-past-operator fragment of LTL and on the assumption that local attention can be analyzed inside the same logical model of computation.

axioms (1)
  • domain assumption Fixed-precision transformers with global attention correspond to a fragment of linear temporal logic containing a single past operator.
    This is invoked as an established prior result that the paper extends to local attention.

pith-pipeline@v0.9.0 · 5714 in / 1237 out tokens · 89150 ms · 2026-05-20T23:57:28.882370+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Revisiting Padded Transformer Expressivity: Which Architectural Choices Matter and Which Don't

    cs.LG 2026-05 unverdicted novelty 7.0

    Padded transformers with constant or growing precision are equivalent to L-uniform AC^0 or TC^0, and with looping reach FO-uniform AC^d or TC^d, robust to width and attention mechanism.