Reproduce “Characterizing the Expressivity of Fixed-Precision Transformer Language Models” on OpenResearch

Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.

Universal app for Apple silicon and Intel. Requires macOS 11 or later.

About this paper

Jiaoda Li, Ryan Cotterell

Fixed-precision transformers with strict causal masking, soft attention, and no positional encodings are shown to recognize exactly the language class LTL[P]. The characterization is equivalent to several automata- and algebraic formalisms, and length-generalization experiments support the predicted boundary: left-deterministic languages are learned reliably, while parity, counting, and other excluded languages are not.

Key insights

  • Numerical underflow gives fixed-precision soft attention a finite effective attention span, but this limitation does not prevent exact recognition of the full LTL[P] class.
  • The architecture captures left-to-right accumulation of information but cannot generally express cyclic state behavior such as parity or unbounded counting; unique hard attention remains strictly more expressive.
  • Empirical length generalization follows the formal boundary: transformer models succeed on left-deterministic languages and fail to reach perfect accuracy on languages outside the class, whereas LSTMs solve all tested tasks.

Summary by alphaXiv.

Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.