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