Transformers Can Represent n-gram Language Models
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.
66288180f2b12d4e79b3bc44
Anej Svete
claimed_verified
2024-04-24T15:34:32.677Z
6629228e0e7290809cd6b243
https://cdn-avatars.huggingface.co/v1/production/uploads/noauth/6KfT9MexmALsAywliij5V.jpeg
Anej Svete
user
AnejSvete
66288180f2b12d4e79b3bc45
Ryan Cotterell
admin_assigned
2024-04-24T12:03:04.727Z
639361c996eabec668bdfcfc
/avatars/b719127447ed71eb128f418765cb0cce.svg
Ryan Cotterell
user
rcotterell
Transformers Can Represent n-gram Language Models
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.
Transformer models using hard or sparse attention mechanisms can represent any $n$-gram model, providing insight into their probabilistic representational capacity.
transformer architecture language models probability distributions $n$-gram models hard attention sparse attention