  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 \emph{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 \textit{a priori} identity of any token. To answer
this, we study \textit{lexinvariant}language 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.
