# Lexinvariant Language Models

arXiv: https://arxiv.org/abs/2305.16349 · HTML: https://mlsanity.com/paper/2305.16349/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 28 references that are in the map.
- First posted on arXiv 24 May 2023.

## Builds on (most cited first, 13 of 13)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding](https://mlsanity.com/paper/1810.04805/) (2018)
- [Language Models are Few-Shot Learners](https://mlsanity.com/paper/2005.14165/) (2020)
- [Exploring the Limits of Transfer Learning with a Unified Text-to-Text Transformer](https://mlsanity.com/paper/1910.10683/) (2019)
- [Efficient Estimation of Word Representations in Vector Space](https://mlsanity.com/paper/1301.3781/) (2013)
- [Training Compute-Optimal Large Language Models](https://mlsanity.com/paper/2203.15556/) (2022)
- [The Pile: An 800GB Dataset of Diverse Text for Language Modeling](https://mlsanity.com/paper/2101.00027/) (2020)
- [Adafactor: Adaptive Learning Rates with Sublinear Memory Cost](https://mlsanity.com/paper/1804.04235/) (2018)
- [ByT5: Towards a token-free future with pre-trained byte-to-byte models](https://mlsanity.com/paper/2105.13626/) (2021)
- [Data Recombination for Neural Semantic Parsing](https://mlsanity.com/paper/1606.03622/) (2016)
- [Learning to Recombine and Resample Data for Compositional Generalization](https://mlsanity.com/paper/2010.03706/) (2020)
- [Can Sequence-to-Sequence Models Crack Substitution Ciphers?](https://mlsanity.com/paper/2012.15229/) (2020)
- [Globally Normalized Reader](https://mlsanity.com/paper/1709.02828/) (2017)

## Built on by (most cited first, 3 of 3)

- [Invariant Learning Dynamics of Transformers in Inductive Reasoning Tasks](https://mlsanity.com/paper/2607.11875/) (2026)
- [LLMs are not stochastic parrots: Evidence for meaning-mediated abstraction from conlang-like tasks](https://mlsanity.com/paper/2609.34187/) (2026)
- [Contextual trajectory and incremental contextual displacement: Towards using LLMs to understand dynamic, utterance-specific meaning construction](https://mlsanity.com/paper/2610.00840/) (2026)

## Abstract (arXiv)

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 textita priori identity of any token. To answer this, we study textitlexinvariantlanguage 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.