CoChat
Sign Up
PreprintCited by 5semigroups and automata theoryComputability, Logic, AI AlgorithmsNeural Networks and Applications

Tighter Bounds on the Expressivity of Transformer Encoders

Open access
Chiang, David, Cholak, Peter, Pillay, Anand·2023·arXiv
DOI 10.48550/arxiv.2301.10743arXiv 2301.10743
Open this paper in CoChat — free accountOpen PDF

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.

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Integrity signals

Registry

DataCite · 10.48550/arxiv.2301.10743

Cites

Statistics

Claims the paper makes

The claims and statistics of this paper haven’t been checked yet.

Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.

A few free checks a day · papers already verified open instantly · results are public

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Some limitations identified in prior work can be overcome with a linear or quadratic number of steps, and a polynomial number of steps covers all problems in P.

    “Some of the limitations identified in prior work (Merrill & Sabharwal, 2023b;Chiang et al., 2023, etc.) can be overcome with a linear or quadratic number of steps, and a polynomial number of steps covers all problems in P.”

    From The expressive power of transformers with chain of thought (2023) · cites this paper as Chiang et al., 2023

Self-check

Percentages, sums and reported differences re-computed from the paper’s own numbers.

The self-check needs the paper’s full text.

Cites

No references could be resolved yet.

Research works printed but not linked: 31

  1. Ba, J. L., Kiros, J. R., and Hinton, G. E. Layer normalization. In NIPS 2016 Deep Learning Symposium, 2016. URL https://arxiv.org/abs/1607.06450. · arXiv
  2. Barceló, P., Kostylev, E. V., Monet, M., Pérez, J., Reutter, J., and Silva, J.-P. The logical expressiveness of graph neural networks. In Proc. ICLR, 2020. URL https: //openreview.net/pdf?id=r1lZ7AEKvB.
  3. Barrington, D. A. M., Immerman, N., and Straubing, H. On uniformity within NC 1 . J. Computer and System Sciences, 41(3), 1990. doi: 10.1016/0022-0000(90)90022-D. · DOI
  4. Bhattamishra, S., Ahuja, K., and Goyal, N. On the ability and limitations of Transformers to recognize formal lan- guages. In Proc. EMNLP, 2020. doi: 10.18653/v1/2020. emnlp-main.576. · DOI · Paper page
  5. Boolos, G. S., Burgess, J. P., and Jeffrey, R. C. Computabil- ity and Logic. Cambridge Univ. Press, 5th edition, 2007.
  6. Büchi, J. R. Weak second-order arithmetic and finite au- tomata. Zeitschrift für Mathematische Logik und Grund- lagen der Mathematik, 6, 1960. doi: 10.1002/malq. 19600060105. · DOI
  7. Chen, Y., Gilroy, S., Knight, K., and May, J. Re- current neural networks as weighted language recog- nizers, 2017. URL https://arxiv.org/abs/1711. 05408v1. arXiv:1711.05408v1. Earlier version of a pa- per presented at NAACL HLT 2018. · arXiv
  8. Chiang, D. and Cholak, P. Overcoming a theoretical lim- itation of self-attention. In Proc. ACL, 2022. doi: 10.18653/v1/2022.acl-long.527. · DOI · Paper page
  9. Ferrante, J. and Rackoff, C. A decision procedure for the first order theory of real addition with order. SIAM J. Com- puting, 4(1), March 1975. doi: 10.1137/0204006. · DOI
  10. Forcada, M. L. and Carrasco, R. C. Finite-state compu- tation in analog neural networks: Steps towards bio- logically plausible models? In Wermter, S., Austin, J., and Willshaw, D. (eds.), Emergent Neural Compu- tational Architectures Based on Neuroscience: Towards Neuroscience-Inspired Computing. Springer, 2001. doi: 10.1007/3-540-44597-8_34. · DOI
  11. Furst, M., Saxe, J. B., and Sipser, M. Parity, circuits, and the polynomial-time hierarchy. Mathematical Systems Theory, 17:13-27, 1984. doi: 10.1007/BF01744431. · DOI
  12. Hahn, M. Theoretical limitations of self-attention in neural sequence models. Trans. ACL, 8, 2020. doi: 10.1162/ tacl_a_00306. · DOI · Paper page
  13. Hao, Y., Angluin, D., and Frank, R. Formal language recognition by hard attention transformers: Perspectives from circuit complexity. Trans. ACL, 10, 2022. doi: 10.1162/tacl_a_00490. · DOI
  14. Immerman, N. Descriptive Complexity. Springer, 1999.
  15. Kleene, S. C. Representation of events in nerve nets and finite automata. In Shannon, C. E. and McCarthy, J. (eds.), Automata Studies, number 34 in Annals of Mathematics Studies. Princeton Univ. Press, 1956. doi: 10.1515/9781400882618-002. · DOI
  16. Kojima, T., Gu, S. S., Reid, M., Matsuo, Y., and Iwasawa, Y. Large language models are zero-shot reasoners. In Proc. NeurIPS, pp. 22199-22213, 2022. URL https: //arxiv.org/pdf/2207.00729.pdf.
  17. McCulloch, W. and Pitts, W. A logical calculus of ideas immanent in nervous activity. Bulletin of Mathematical Biophysics, 5, 1943. doi: 10.1007/BF02478259. · DOI · Paper page
  18. Merrill, W. On the linguistic capacity of real-time counter automata, 2020. URL https://arxiv.org/abs/ 2004.06866. arXiv:2004.06866. · arXiv
  19. Merrill, W. and Sabharwal, A. Transformers can be translated to first-order logic with majority quanti- fiers, 2022. URL https://arxiv.org/abs/2210. 02671v3. arXiv:2210.02671v3. · arXiv
  20. Merrill, W. and Sabharwal, A. The parallelism tradeoff: Limitations of log-precision transformers. Trans. ACL, 2023. URL https://arxiv.org/pdf/2207.00729. pdf. To appear. · arXiv
  21. Merrill, W., Sabharwal, A., and Smith, N. A. Saturated transformers are constant-depth threshold circuits. Trans. ACL, 10, 2022. doi: 10.1162/tacl_a_00493. · DOI · Paper page
  22. Nguyen, T. Q. and Salazar, J. Transformers without tears: Improving the normalization of self-attention. In Proc. International Workshop on Spoken Language Translation (IWSLT), 2019. doi: 10.5281/zenodo.3525484. · DOI
  23. Pérez, J., Barceló, P., and Marinkovic, J. Attention is Turing-complete. J. Machine Learning Research, 22 (75), 2021. URL https://jmlr.org/papers/v22/ 20-302.html.
  24. Robinson, A. and Zakon, E. Elementary properties of ordered abelian groups. Trans. AMS, 96, 1960. doi: 10.1090/S0002-9947-1960-0114855-0. · DOI
  25. Schwartz, R., Thomson, S., and Smith, N. A. Bridging CNNs, RNNs, and weighted finite-state machines. In Proc. ACL, 2018. doi: 10.18653/v1/P18-1028. · DOI
  26. Siegelmann, H. and Sontag, E. On the computational power of neural nets. J. Computer and System Sciences, 50(1), 1995. doi: 10.1006/jcss.1995.1013. · DOI
  27. Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., Gomez, A. N., Kaiser, Ł., and Polo- sukhin, I. Attention is all you need. In Proc.
  28. NeurIPS, 2017. URL https://papers.nips.cc/ paper/7181-attention-is-all-you-need.
  29. Wang, Q., Li, B., Xiao, T., Zhu, J., Li, C., Wong, D. F., and Chao, L. S. Learning deep Transformer models for machine translation. In Proc. ACL, 2019. doi: 10.18653/ v1/P19-1176. · DOI · Paper page
  30. Weiss, G., Goldberg, Y., and Yahav, E. Thinking like Transformers. In Proc. ICML, 2021. URL https: //proceedings.mlr.press/v139/weiss21a.html.
  31. Yun, C., Bhojanapalli, S., Rawat, A. S., Reddi, S. J., and Kumar, S. Are Transformers universal approxi- mators of sequence-to-sequence functions? In Proc. ICLR, 2020. URL https://openreview.net/pdf? id=ByxRM0Ntvr.

Cited by

Sorted by citations

Authors
Chiang, D., Cholak, P., & Pillay, A.
ORCID
Venue
arXiv
Publisher
arXiv
Published
2023
ISSN
2331-8422 (ISSN-L)
DOI
10.48550/arxiv.2301.10743
arXiv
2301.10743
OpenAlex
W4318242594
Cited by
4
References
0
Citations by year
2024: 3 · 2023: 1
Type
posted content
Language
en
Open access
Licence
arxiv.org/licenses/nonexclusive-distrib/1.0/
Locations
  • arXiv (Cornell University) (submittedVersion)
  • arXiv (Cornell University)
Funders
National Science Foundation (1760212, 2054271, 1854136)
Topics
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › semigroups and automata theory
  • Physical Sciences › Computer Science › Computational Theory and Mathematics › Computability, Logic, AI Algorithms
  • Physical Sciences › Computer Science › Artificial Intelligence › Neural Networks and Applications
Keywords
Transformer encoder, expressivity, computational complexity, counter machines, formal language recognition, neural network limitations

About these checks

Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.

Statistics and arithmetic are recomputed, not judged.

Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.

What counts as a claim ›How we measure confidence ›How we check this ›

Are you an author, or do you see a problem with this page? Request a review