Transformers Can Represent n-gram Language Models

Anej Svete, Ryan Cotterell


Abstract
Plenty of existing work has analyzed the abilities of the transformer architecture by describing its representational capacity with formal models of computation. However, the focus so far has been on analyzing the architecture in terms of language acceptance. We contend that this is an ill-suited problem in the study of language models (LMs), which are definitionally probability distributions over strings. In this paper, we focus on the relationship between transformer LMs and n-gram LMs, a simple and historically relevant class of language models. We show that transformer LMs using the hard or sparse attention mechanisms can exactly represent any n-gram LM, giving us a concrete lower bound on their probabilistic representational capacity. This provides a first step towards understanding the mechanisms that transformer LMs can use to represent probability distributions over strings.
Anthology ID:
2024.naacl-long.381
Volume:
Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers)
Month:
June
Year:
2024
Address:
Mexico City, Mexico
Editors:
Kevin Duh, Helena Gomez, Steven Bethard
Venue:
NAACL
SIG:
Publisher:
Association for Computational Linguistics
Note:
Pages:
6841–6874
Language:
URL:
https://aclanthology.org/2024.naacl-long.381
DOI:
Bibkey:
Cite (ACL):
Anej Svete and Ryan Cotterell. 2024. Transformers Can Represent n-gram Language Models. In Proceedings of the 2024 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers), pages 6841–6874, Mexico City, Mexico. Association for Computational Linguistics.
Cite (Informal):
Transformers Can Represent n-gram Language Models (Svete & Cotterell, NAACL 2024)
Copy Citation:
PDF:
https://aclanthology.org/2024.naacl-long.381.pdf
Copyright:
 2024.naacl-long.381.copyright.pdf