Interchangeable Token Embeddings for Extendable Vocabulary and Alpha-Equivalence

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

When people read a math or logic expression like "if x and y are odd numbers, x+y is even," they know that changing the names of x and y doesn't change the meaning. Because the variables (x and y) are just placeholders. But today's language models don't naturally understand this idea. If we rename those variables, the model may think the statement means something different.Our research tackles this problem by helping language models learn that some symbols are interchangeable: they look different but mean the same thing in context. We created a way to measure how well a model understands this, and we designed a new method for representing this concept. The key idea is to represent interchangeable symbols in two parts: one that captures their shared meaning and another that keeps each symbol distinct.Our approach helps models better understand variable renaming, and allows them to generalize to unfamiliar vocabulary they have not seen before. It's a step toward making AI systems better at formal reasoning, which is essential for understanding logic, code, and mathematical language.