Names Don’t Matter: Symbol-Invariant Transformer for Open-Vocabulary Learning
İlker Işık, Wenchao Li · 2026
Read Names Don’t Matter: Symbol-Invariant Transformer for Open-Vocabulary Learning by İlker Işık, Wenchao Li (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-23169.txt.
Introduction
İlker Işık and Wenchao Li build a transformer that does not care what symbols are named. Many tokens are interchangeable, like bound variables in logic, where only structure matters. Models trained on fixed vocabularies often fail on unseen symbols, even when the meaning is unchanged.
Their symbol-invariant design treats equivalent symbols as truly equivalent by construction. That should let learning transfer across renamed problems without retraining. Open-vocabulary learning of this kind suits logic, math, and code, where names are arbitrary. Bound variables are the motivating example, since renaming them changes nothing about a formula's actual meaning.
Catalog record
| CREATOR | İlker Işık, Wenchao Li |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 72 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-23169
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Names Don’t Matter: Symbol-Invariant Transformer for Open-Vocabulary Learning İlker Işık, Wenchao Li Abstract Current neural architectures lack a principled way to handle interchangeable tokens, i.e., symbols that are semantically equivalent yet distinguishable, such as bound variables. As a result, models trained on fixed vocabularies often struggle to generalize to unseen symbols, even when the underlying semantics remain unchanged. We propose a novel Transformer-based mechanism that is provably invariant to the renaming of interchangeable tokens. Our approach employs parallel embedding streams to isolate the contribution of each interchangeable token in the input, combined with an aggregated attention mechanism that enables structured information sharing across streams. Experimental results confirm the theoretical guarantees of our method and demonstrate substantial performance gains on open-vocabulary tasks that require generalization to novel symbols. 1 Introduction Recent advances show that Transformer-based architectures can successfully tackle tasks once thought to require explicit symbolic manipulation, such as theorem proving ( Han et al. 2021 ) , mathematical reasoning ( Rabe et al. 2020 ) , and temporal logic solving ( Hahn et al. 2021 ) . These successes are often framed as instances of language modeling over symbolic structures, suggesting that sufficiently expressive sequence models can internalize nontrivial symbolic regularities. This perspective is further supported by theoretical results showing that Transformers can represent the computation of any finite-state automaton ( Liu et al. 2023 ) . However, despite both strong empirical performance and growing theoretical understanding, current neural architectures still lack a principled treatment of open-vocabulary reasoning, a core challenge in many symbolic domains. A defining feature of symbolic systems is that many tokens are interchangeable : they are syntactically distinct but semantically equivalent up to renaming. This phenomenon arises naturally in logic, programming languages, and mathematics, where symbols often act as placeholders rather than carriers of intrinsic meaning. In lambda calculus, for example, the expressions \lambda x.x+1 and \lambda y.y+1 are semantically identical, even though they differ lexically. Similarly, in logic, formulas that differ only by variable names or atomic propositions are considered equivalent. This notion, known as alpha-equivalence , captures the idea that renaming interchangeable tokens should not affect meaning. Humans reason effortlessly under alpha-equivalence, but neural models trained on fixed vocabularies typically do not – they tend to overfit to specific symbol identities and struggle to generalize when presented with unseen or renamed tokens. This limitation is particularly acute in open-vocabulary settings, where the set of symbols encountered at test time may differ from those seen during training. In such cases, standard embedding-based approaches force a trade-off between expressivity and generalization – embeddings must distinguish tokens to enable reasoning, yet any reliance on token identity undermines invariance to renaming. This tension lies at the heart of open-vocabulary neuro-symbolic learning and motivates the need for architectures that are invariant by construction to permutations of interchangeable symbols . Linear-time temporal logic (LTL) ( Pnueli 1977 ) provides a concrete and well-studied example of this challenge. LTL is widely used in formal verification to specify temporal properties of systems, such as whether a proposition always holds or eventually becomes true. Each LTL formula is defined over a finite set of atomic propositions, which are semantically interchangeable: renaming propositions consistently throughout a formula does not change its satisfiability. While prior work has demonstrated that Transformer models can learn to efficiently generate witnesses to LTL formulas and even generalize to longer sequences ( Hahn et al. 2021 ; Shiv and Quirk 2019 ) , generalization across larger or unseen sets of atomic propositions remains problematic. Importantly, LTL is only one instance of a broader phenomenon; the same issue arises in many symbolic domains where alpha-equivalence plays a central role. A recent line of work addresses this problem by constructing random embeddings for interchangeable tokens ( Işık et al. 2025 ) . This strategy enables post-training vocabulary expansion and empirically improves robustness to renaming. However, such random embedding approaches introduce new difficulties: they depend on stochasticity for token discrimination, require careful tuning of additional hyperparameters, and offer no formal guarantees of invariance. In practice, different random seeds can lead to different predictions on alpha-equivalent inputs, meaning that invariance is encouraged statistically rather than enforced structurally. In this paper, we propose a fundamentally different solution. We introduce a Symbol-Invariant Transformer architecture that achieves exact invariance to the renaming of interchangeable tokens by design. Our approach replaces random token differentiation with parallel embedding streams, one for each interchangeable token in the input. In each stream, the token of interest is represented explicitly, while all other interchangeable tokens are treated as placeholders. These streams are processed in parallel by shared Transformer layers and combined through an aggregated attention mechanism that preserves the contribution of each token at its original positions while enabling structured information sharing across streams. As a result, the model can reason about each symbol individually without ever committing to a specific naming scheme. Crucially, this architectural design yields a provable guarantee of invariance: the model’s outputs are identical for any pair of alpha-equivalent inputs, achieving alpha-equivalence by construction. Empirically, we demonstrate that the proposed architecture improves open-vocabulary generalization across symbolic reasoning tasks. In particular, on LTL witness generation, our method not only outperforms existing baselines but also substantially surpasses GPT-5.2, highlighting the effectiveness of an explicit symbol-invariant inductive bias in domains involving alpha-equivalence. We summarize our main contributions as follows: • Architecture . We propose a novel symbol-invariant Transformer architecture with an aggregated attention mechanism. Our method introduces only a small number of additional hyperparameters, can be implemented as a lightweight modification to standard Transformer encoder–decoder architectures, and is compatible with existing generalization techniques such as length-generalizing positional encodings ( Shiv and Quirk 2019 ) . • Theory . Our architecture provides a formal guarantee of invariance to alpha-renaming, ensuring alpha-equivalence by construction. • Empirics . We validate the approach on open-vocabulary symbolic reasoning tasks, demonstrating strong generalization and state-of-the-art performance, including outperforming GPT-5.2 on LTL witness generation. 2 Related Work Işık et al. 2025 introduced a metric for measuring robustness against variable renaming and proposed a novel embedding strategy using random vectors to handle interchangeable tokens, enabling post-training vocabulary expansion. However, as discussed previously, reliance on randomness leads to problems such as lack of theoretical guarantees. Ankner et al. 2023 proposed a transformer architecture that is provably invariant to variable renaming without randomness, though vocabulary expansion was not considered in their work. Olsák et al. 2019 addressed symbol invariance in automated reasoning, but their focus was limited to graph neural networks and did not consider sequence-to-sequence tasks. Related work has also explored domain-specific vocabulary extensions using auxiliary information such as dictionary definitions or gesture components ( Morazzoni et al. 2023 ; Wei et al. 2016 ) , as well as general permutation invariance in transformers ( Lee et al. 2019 ; Xu et al. 2024 ) . While these papers tackle similar challenges, they do not address the specific problem of interchangeable tokens. In computer vision, open-vocabulary image classification models are trained to recognize unseen classes at inference time ( Radford et al. 2021 ; Wu et al. 2024 ; Tan et al. 2024 ) . However, these methods are not applicable to interchangeable tokens as they rely on semantic relationships