HackerPapers

arXiv:2301.10743cs.LG

Tighter Bounds on the Expressivity of Transformer Encoders

David Chiang, Peter Cholak, Anand Pillay

Abstract

Characterizing neural networks in terms of better-understood formal systems has the potential to yield new insights into the power and limitations of these networks. Doing so for transformers remains an active area of research. Bhattamishra and others have shown that transformer encoders are at least as expressive as a certain kind of counter machine, while Merrill and Sabharwal have shown that fixed-precision transformer encoders recognize only languages in uniform $TC^0$. We connect and strengthen these results by identifying a variant of first-order logic with counting quantifiers that is simultaneously an upper bound for fixed-precision transformer encoders and a lower bound for transformer encoders. This brings us much closer than before to an exact characterization of the languages that transformer encoders recognize.

arXiv comments
Presented at ICML 2023. Typo corrections in Appendix B and Section 8.1
Journal reference
DOI
Subjects
cs.LGMachine Learning cs.FLFormal Languages and Automata Theory cs.LOLogic in Computer Science

On Hacker News

Linked by 3 identifiable commenters in 5 comments across 5 threads, from Jun 2023 to Jan 2025. Found in 1 HN submission from Apr 2023 to Apr 2023. Open submission discussions.

Comments linking this paper, per year.

Discussed in comments5 threads

  1. Ask HN: How to learn AI from first principles? 1 comment
  2. Turing Complete Transformers: Two Transformers Are More Powerful Than One 1 comment

    • Transformers with fixed precision and any amount of memory are not Turing complete. They're bounded by a variant of first order logic with counting quantifiers. https://arxiv.org/abs/2301.10743 This supports the intuitive idea that they "learn circuits for things" that I've…

      inciampatiView on HNParent context

  3. Ask HN: AI/ML papers to catch up with current state of AI? 1 comment

    • To that, what can these express, precisely, is an interesting question; so for transformer encoders: https://arxiv.org/abs/2301.10743 Another interesting research topic is the trusted generation of tasks for finetuning https://arxiv.org/abs/2306.08568 And I suppose too running…

      meltynessView on HNParent context

  4. Researchers warn of ‘model collapse’ as AI trains on AI-generated content 1 comment

    • The current generation of LLMs will never generalize on problems whose expected complexity is significantly harder than the training set. One way to think of why this is the case is because transformers are learning shortcuts to multistep reasoning tasks [1, 2], but do not learn…

      bmc7505View on HNParent context

  5. Thinking Like Transformers (2021) [pdf] 1 comment

    • This has been built on extensively over the past two years. For instance: Tighter Bounds on the Expressivity of Transformer Encoders https://arxiv.org/abs/2301.10743. I find it interesting that transformers are equivalent to first order logic on circuits with counters. Amazing…

      inciampatiView on HNParent context

Submitted to Hacker News

Connected through shared HN threads, not inferred similarity or a recommendation.