Jiaoda Li: Characterizing the Expressivity of Transformer Language Models

Value of the Information & Strength of the Argument

The talk provides a significant theoretical contribution by precisely characterizing the expressivity of transformers in terms of a well-understood logical fragment. The argumentation is rigorous, building on prior work and addressing technical challenges such as simulating summation with threshold counting. The proof sketches are clear and the experimental validation strengthens the claims. The discussion of limitations, such as the fixed precision assumption, adds to the credibility.

Scientific Rigor, Source Quality, Title Accuracy

The talk is scientifically rigorous, with a clear theoretical framework and proofs. The main source is the paper on arXiv (2505.23623), which is appropriately referenced. The title accurately reflects the content. The presentation is self-contained, providing necessary background on formal languages and logic. The experimental methodology is sound, using a length generalization setting. The talk does not overstate its findings and acknowledges assumptions.

The title accurately reflects the content: the talk characterizes the expressivity of transformer language models in terms of a fragment of temporal logic.

8/10

The talk presents a formal theoretical result with a rigorous proof sketch, supported by experimental validation. The methodology is clearly explained, and the claims are grounded in established formal language theory. The presentation is technical and precise, with appropriate caveats about assumptions.

Markers derived by PSI from the transcript: the creator did not define chapters.

• 00:00Introduction and motivation: characterizing transformer expressivity.
• 02:00Background on formal languages, regular expressions, and star-free languages.
• 05:00Introduction to temporal logic (LTL) and its fragments.
• 08:00First-order logic and its connection to LTL; introduction of PFO2.
• 10:00Main result: transformers can be translated into PFO2.
• 15:00Simulating attention summation with threshold counting.
• 20:00Second direction: LTL_past can be simulated by transformers.
• 25:00Handling fixed precision by using two attention layers.
• 30:00Equivalence to left-deterministic polynomials and partially ordered DFAs.
• 35:00Experimental validation on learnable and non-learnable languages.

• Characterizing the Expressivity of Transformer Language Models — Paper presented in the talk, containing the main theoretical and experimental results.

• On the Expressive Power of Transformers — Related work showing transformers are equivalent to linear temporal logic under similar assumptions.