title: Lexinvariant Language Models
summary: Token embeddings, a mapping from discrete lexical symbols to continuous
  vectors, are at the heart of any language model (LM). However, lexical symbol
  meanings can also be determined and even redefined by their structural role in
  a long context. In this paper, we ask: is it possible for a language model to
  be performant without any fixed token embeddings? Such a language model
  would have to rely entirely on the co-occurence and repetition of tokens in the
  context rather than the a priori identity of any token. To answer
  this, we study lexinvariantlanguage models that are invariant to
  lexical symbols and therefore do not need fixed token embeddings in practice.
  First, we prove that we can construct a lexinvariant LM to converge to the true
  language model at a uniform rate that is polynomial in terms of the context
  length, with a constant factor that is sublinear in the vocabulary size.
  Second, to build a lexinvariant LM, we simply encode tokens using random
  Gaussian vectors, such that each token maps to the same representation within
  each sequence but different representations across sequences. Empirically, we
  demonstrate that it can indeed attain perplexity comparable to that of a
  standard language model, given a sufficiently long context. We further explore
  two properties of the lexinvariant language models: First, given text generated
  from a substitution cipher of English, it implicitly implements Bayesian
  in-context deciphering and infers the mapping to the underlying real tokens
  with high accuracy. Second, it has on average 4X better accuracy over synthetic
  in-context reasoning tasks. Finally, we discuss regularizing standard language
  models towards lexinvariance and potential practical applications.
paper_authors._id: 6474186e7afa69c3c7a9a340
paper_authors.name: Qian Huang
paper_authors.status: claimed_verified
paper_authors.statusLastChangedAt: 2023-05-30T18:00:03.949Z
paper_authors._id: 641ab10ea63c4e80623168c9
paper_authors.avatarUrl: /avatars/64bbfe8e09d957ae8e9bd4c862333da7.svg
paper_authors.fullname: Qian Huang
paper_authors.type: user
paper_authors.user: qhwang
paper_authors._id: 6474186e7afa69c3c7a9a341
paper_authors.name: Eric Zelikman
paper_authors.status: claimed_verified
paper_authors.statusLastChangedAt: 2023-06-08T16:08:37.243Z
paper_authors._id: 626aa3efe9326611a509a2fc
paper_authors.avatarUrl: /avatars/4cea5cbd4ee918f1de7ccf191bfdf118.svg
paper_authors.fullname: Eric Zelikman
paper_authors.type: user
paper_authors.user: ezelikman
paper_authors._id: 6474186e7afa69c3c7a9a342
paper_authors.name: Sarah Li Chen
paper_authors._id: 6474186e7afa69c3c7a9a343
paper_authors.name: Yuhuai Wu
paper_authors._id: 6474186e7afa69c3c7a9a344
paper_authors.name: Gregory Valiant
paper_authors._id: 6474186e7afa69c3c7a9a345
paper_authors.name: Percy Liang
paper_authors.status: admin_assigned
paper_authors.statusLastChangedAt: 2023-05-30T09:01:24.511Z
paper_authors._id: 6409651b9e9f790c905b2335
paper_authors.avatarUrl: /avatars/1fb8c80b60f21f65a0a027319101f236.svg
paper_authors.fullname: Percy Liang
paper_authors.type: user
paper_authors.user: percyliang
paper_title: Lexinvariant Language Models
paper_summary: Token embeddings, a mapping from discrete lexical symbols to continuous
  vectors, are at the heart of any language model (LM). However, lexical symbol
  meanings can also be determined and even redefined by their structural role in
  a long context. In this paper, we ask: is it possible for a language model to
  be performant without any fixed token embeddings? Such a language model
  would have to rely entirely on the co-occurence and repetition of tokens in the
  context rather than the a priori identity of any token. To answer
  this, we study lexinvariantlanguage models that are invariant to
  lexical symbols and therefore do not need fixed token embeddings in practice.
  First, we prove that we can construct a lexinvariant LM to converge to the true
  language model at a uniform rate that is polynomial in terms of the context
  length, with a constant factor that is sublinear in the vocabulary size.
  Second, to build a lexinvariant LM, we simply encode tokens using random
  Gaussian vectors, such that each token maps to the same representation within
  each sequence but different representations across sequences. Empirically, we
  demonstrate that it can indeed attain perplexity comparable to that of a
  standard language model, given a sufficiently long context. We further explore
  two properties of the lexinvariant language models: First, given text generated
  from a substitution cipher of English, it implicitly implements Bayesian
  in-context deciphering and infers the mapping to the underlying real tokens
  with high accuracy. Second, it has on average 4X better accuracy over synthetic
  in-context reasoning tasks. Finally, we discuss regularizing standard language
  models towards lexinvariance and potential practical applications.
paper_ai_keywords: token embeddings language model (LM) lexical symbol long context lexinvariant language models true language model context length vocabulary size random Gaussian vectors perplexity Bayesian in-context deciphering synthetic in-context deciphering tasks lexinvariance