# Interchangeable Token Embeddings for Extendable Vocabulary and Alpha-Equivalence

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 22 of its 36 references that are in the map.
- First posted on arXiv 22 Oct 2024.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [The Llama 3 Herd of Models](https://mlsanity.com/paper/2407.21783/) (2024)
- [RoFormer: Enhanced Transformer with Rotary Position Embedding](https://mlsanity.com/paper/2104.09864/) (2021)
- [Multitask Prompted Training Enables Zero-Shot Task Generalization](https://mlsanity.com/paper/2110.08207/) (2021)
- [LeanDojo: Theorem Proving with Retrieval-Augmented Language Models](https://mlsanity.com/paper/2306.15626/) (2023)
- [Llemma: An Open Language Model For Mathematics](https://mlsanity.com/paper/2310.10631/) (2023)
- [Using the Output Embedding to Improve Language Models](https://mlsanity.com/paper/1608.05859/) (2016)
- [Deep Learning for Symbolic Mathematics](https://mlsanity.com/paper/1912.01412/) (2019)
- [Transformers Learn Shortcuts to Automata](https://mlsanity.com/paper/2210.10749/) (2022)
- [Mathematical Capabilities of ChatGPT](https://mlsanity.com/paper/2301.13867/) (2023)
- [Reasoning or Reciting? Exploring the Capabilities and Limitations of Language Models Through Counterfactual Tasks](https://mlsanity.com/paper/2307.02477/) (2023)
- [NormFace: L2 Hypersphere Embedding for Face Verification](https://mlsanity.com/paper/1704.06369/) (2017)
- [End-to-end symbolic regression with transformers](https://mlsanity.com/paper/2204.10532/) (2022)
- [Proof Artifact Co-training for Theorem Proving with Language Models](https://mlsanity.com/paper/2102.06203/) (2021)
- [L2-constrained Softmax Loss for Discriminative Face Verification](https://mlsanity.com/paper/1703.09507/) (2017)
- [AdaCos: Adaptively Scaling Cosine Logits for Effectively Learning Deep Face Representations](https://mlsanity.com/paper/1905.00292/) (2019)
- [Generalization on the Unseen, Logic Reasoning and Degree Curriculum](https://mlsanity.com/paper/2301.13105/) (2023)
- [NaturalProver: Grounded Mathematical Proof Generation with Language Models](https://mlsanity.com/paper/2205.12910/) (2022)
- [Large Language Models are In-Context Semantic Reasoners rather than Symbolic Reasoners](https://mlsanity.com/paper/2305.14825/) (2023)
- [SymFormer: End-to-end symbolic regression using transformer-based architecture](https://mlsanity.com/paper/2205.15764/) (2022)
- [Teaching Temporal Logics to Neural Networks](https://mlsanity.com/paper/2003.04218/) (2020)
- [From Spot 2.0 to Spot 2.10: What's New?](https://mlsanity.com/paper/2206.11366/) (2022)

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

- [On the Ability of Transformers to Verify Plans](https://mlsanity.com/paper/2603.19954/) (2026)
- [Names Don't Matter: Symbol-Invariant Transformer for Open-Vocabulary Learning](https://mlsanity.com/paper/2601.23169/) (2026)

## Abstract (arXiv)

Language models lack the notion of interchangeable tokens: symbols that are semantically equivalent yet distinct, such as bound variables in formal logic. This limitation prevents generalization to larger vocabularies and hinders the model's ability to recognize alpha-equivalence, where renaming bound variables preserves meaning. We formalize this machine learning problem and introduce alpha-covariance, a metric for evaluating robustness to such transformations. To tackle this task, we propose a dual-part token embedding strategy: a shared component ensures semantic consistency, while a randomized component maintains token distinguishability. Compared to a baseline that relies on alpha-renaming for data augmentation, our approach demonstrates improved generalization to unseen tokens in linear temporal logic solving, propositional logic assignment prediction, and copying with an extendable vocabulary, while introducing a favorable inductive bias for alpha-equivalence. Our findings establish a foundation for designing language models that can learn interchangeable token representations, a crucial step toward more flexible and systematic reasoning in formal domains. Our code and project page are available at https://necrashter.github.io/interchangeable-token-embeddings