Pith. sign in

REVIEW 4 cited by

Masked Hard-Attention Transformers Recognize Exactly the Star-Free Languages

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 2310.13897 v4 pith:XFRG7J4U submitted 2023-10-21 cs.FL cs.LGcs.LO

Andy Yang , David Chiang , Dana Angluin This is my paper · ORCID
classification cs.FLcs.LGcs.LO
keywords transformerspositionattentionexactlylanguagesmaskingembeddingsexpressive
verification ladder T0 review T1 audit T2 compute T3 formal

Signed reviews

No signed human review yet.

0 comments
read the original abstract

The expressive power of transformers over inputs of unbounded size can be studied through their ability to recognize classes of formal languages. In this paper, we establish exact characterizations of transformers with hard attention (in which all attention is focused on exactly one position) and attention masking (in which each position only attends to positions on one side). With strict masking (each position cannot attend to itself) and without position embeddings, these transformers are expressively equivalent to linear temporal logic (LTL), which defines exactly the star-free languages. A key technique is the use of Boolean RASP as a convenient intermediate language between transformers and LTL. We then take numerous results known for LTL and apply them to transformers, showing how position embeddings, strict masking, and depth all increase expressive power.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 4 Pith papers

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

  1. Ehrenfeucht-Haussler Rank and Chain of Thought

    cs.LG 2025-01 conditional novelty 8.0 of 10

    A function's Ehrenfeucht-Haussler rank exactly equals the minimum chain-of-thought steps for a single-layer hard-attention Transformer, with matching lower bounds for iterated composition and the k-th-one function.

  2. Simulating Hard Attention Using Soft Attention

    cs.LG 2024-12 accept novelty 8.0 of 10

    Softmax transformers can approximately simulate hard-attention transformers, using a temperature that depends on the reciprocal of the attention-score gap.

  3. Disentangling the Expressivity of RoPE

    cs.LG 2026-08 conditional novelty 7.0 of 10

    Periodic RoPE schedules yield exactly LTL with past operators and modular predicates, while conventional non-periodic RoPE provides only a bounded, precision-limited fixed-offset look-back mechanism.

  4. The Computational Limits of State-Space Models and Mamba via the Lens of Circuit Complexity

    cs.CC 2024-12 conditional novelty 5.0 of 10

    Mamba and state-space models with constant depth and poly(n) precision are shown to lie in DLOGTIME-uniform TC0, the same circuit class as Transformers, so their expressiveness is bounded unless TC0=NC1.

Pith tools