1 Introduction↩︎

Language models [1]–[3] typically map tokens into high-dimensional vectors via learned embedding matrices. This allows each token in a discrete vocabulary to be represented by a unique, dense vector. However, this linear scaling creates a vocabulary bottleneck, locking the model into a fixed token capacity and restricting its ability to adapt seamlessly to new domains, or languages.

To mitigate this, previous research has explored token hashing [4]–[7] to fix the parameter footprint of the embedding space. Hash-based models such as the Proformer [8] and the HashFormer [9] use many-to-one mappings, where multiple tokens (e.g., cat, map, and physics) may share the same hash index (e.g., 40). While parameter-efficient, these models are restricted to encoder-based architectures and discriminative training. In generative settings, if a decoder predicts a shared hash index, the model cannot deterministically recover the intended token from the set of colliding candidates. Consequently, this ambiguity has made training causal LMs on hashed spaces practically infeasible.

In this paper, we propose MultiHashFormer, a new framework designed to bypass the vocabulary bottleneck for decoder-based LMs. Drawing inspiration from chaotic dynamic memory systems [10] which leverage distributed, overlapping state spaces for high-capacity pattern retrieval [11], we replace the traditional embedding matrix with a modular hashing interface. Specifically, each token is converted into a unique hash signature consisting of a short sequence of discrete hash IDs generated by multiple independent hash functions, similar to chaotic transitions that allow biological networks to chain together vast vocabularies of concepts [12]. For example, cat is represented as \([12, 40, 56]\) and map as \([99, 40, 3]\). This multi-ID mapping eliminates the token collision problem of previous hash-based methods while allowing the model to scale its vocabulary capacity with a strictly sub-linear parameter footprint. For example, using four hash functions and 16,000 buckets per function, the MultiHashFormer theoretically supports an upper bound of \(16000^{4}\) (approx. 65 quadrillion) unique signatures.

The interface is independent of the sequence processing backbone (e.g., a Transformer [13]) and manages the bidirectional translation between discrete tokens and the hash signatures. At the input, a gated compositional embedding compresses the multi-ID signature into a dense latent vector, providing the backbone with a unified representation for sequence processing (Hash Encoder). At the output, a cascaded predictor reconstructs the hash signature of the next token sequentially, which is then deterministically mapped back to a specific discrete text token in the vocabulary (Hash Decoder). Figure 1 illustrates the MultiHashFormer architecture.

Our main contributions are as follows:

• We introduce the first hash-based framework that supports causal language modeling by preventing token collisions through multi-ID signature generation.

• MultiHashFormer models consistently outperform standard Transformer LMs at 100M, 1B and 3B scales across 10 tasks, while offering better rare word representations.

• We show that our models maintain performance while expanding the vocabulary size from 32K to 48K without any structural changes, or parameter count increase.

2 Related Work↩︎

2.1 Token-Free Models↩︎

LMs rely on an embedding matrix that scales linearly with the vocabulary size. While subword tokenizers like BPE [14] and SentencePiece [15] mitigate vocabulary explosion, they remain constrained by a fixed, data-derived vocabulary that struggles with rare or out-of-domain words.

Token-free models such as AU-Net [16], Bolmo [17], H-Net [18], BLT [19], CANINE [20], and ByT5 [21] bypass the vocabulary bottleneck entirely by operating directly on unicode or byte sequences. However, this approach dramatically increases the input sequence length. Alternatively, T-FREE [22] avoids tokenization by embedding words via sparse activations over locality-based hashed character trigrams. While parameter-efficient, it relies on character-level morphological similarity, making it language-dependent. In contrast, MultiHashFormer is orthogonal to these approaches. It resolves the vocabulary bottleneck while retaining the sequence compression advantages of subword tokenization. By decoupling the parameter matrix from the discrete vocabulary using combinatorial multi-hash mapping rather than sub-character heuristics, MultiHashFormer remains language-agnostic and supports any arbitrary tokenization strategy.

2.2 Factorized and Hash-Based Embeddings↩︎

To compress the memory footprint of standard embedding matrices, prior work has explored parameter reduction techniques. For example, ALBERT [23] uses matrix factorization to decouple the embedding dimension from the hidden dimension. While this reduces the parameter footprint, it still allocates a localized, explicit vector per token, failing to break the linear scaling constraint.

A different approach is to use random hash embeddings [6], which map discrete tokens into a highly compressed set of physical buckets. Architectural extensions like Proformer [8] and HashFormer [9] demonstrate that token hashing can be used to train Transformer-based models. However, compressing a vast vocabulary into a restricted physical bucket space inevitably forces multiple tokens to share the same index. This collision on a single hash function level prevents deterministic token recovery during autoregressive generation, restricting these methods strictly to encoder-only architectures. MultiHashFormer resolves this limitation via the multi-identifier framework detailed in §3.

3 MultiHashFormer↩︎

MultiHashFormer comprises three modules shown in Figure 1: (1) a Hash Encoder that maps a discrete input token to a distributed multi-ID signature and compresses this signature into a single dense embedding; (2) a Sequence Processing Backbone that converts these embeddings into contextualized representations; and (3) a Hash Decoder that auto-regressively reconstructs the multi-ID signature of the next token.

3.1 Hash Encoder↩︎

3.1.0.1 Multi-Hash Indexing.

To map each discrete token \(w\) into the hash signature space, we use \(H\) independent hash functions: \(\mathcal{H}_1(w), \mathcal{H}_2(w), \dots, \mathcal{H}_H(w)\). For any non-padding token, the \(i\)-th coordinate of the signature is computed using the non-cryptographic MurmurHash3 (MMH3) algorithm [24]. The algorithm uses iterative bitwise multiplication and rotation to diffuse the input, ensuring a single-bit change yields a uniform, randomized hash. We use a hash function-specific \(\mathrm{seed}_i\): \[\begin{align} \mathcal{H}_i(w) &= \mathrm{MMH3}(w, \mathrm{seed}_i)\\ &\pmod{B-1} + 1 \quad \text{if } w \neq \mathrm{pad}. \end{align}\] \(B\) denotes the number of discrete hash buckets per function. \(\mathcal{H}_i(\mathrm{pad}) = 0\) is reserved across \(\mathcal{H}\) to denote the padding token. To guarantee that every token in the vocabulary maps to a collision-free multi-hash ID, we use an iterative rehashing strategy. If a new token generates a signature that conflicts with an existing vocabulary entry, we incrementally modify the seed of the final hash function (\(\mathrm{seed}_H\)) until an unused signature is found.

3.1.0.2 Gated Compositional Embedding.

We allocate \(H\) separate embedding matrices \(\mathbf{E}^{(i)} \in \mathbb{R}^{B \times d}\) (where \(i \in \{1, \dots, H\}\)) to each hash coordinate \(\mathcal{H}\), where \(d\) represents the backbone hidden dimension. Because hash buckets are shared globally per function, overlapping tokens that are semantically unrelated inevitably collide. Inspired by the multi-embedding approach of [25], we resolve this ambiguity by compressing the coordinates into a unified token representation via a context-aware compositional gate. To determine the contribution of each bucket, the individual hash embeddings pass through a feed-forward bottleneck network with a compression dimension \(d_z \ll d\), followed by softmax normalization. Finally, a linear adapter matrix \(\mathbf{W}_s\) projects the combined representation into the latent space of the sequence processing backbone: \[\begin{gather} \mathbf{e} = \left( \sum_{i=1}^H \tilde{\alpha}_i \mathbf{E}^{(i)}_{[\mathcal{H}_i(w), :]} \right) \mathbf{W}_{s}, \\ \tilde{\alpha}_i = \frac{\exp^{\alpha_i}}{\sum_{j=1}^H \exp^{\alpha_j}}, ~\alpha_i = \sigma \left( \mathbf{E}^{(i)}_{[\mathcal{H}_i(w), :]} \mathbf{W}_{1} \right) \mathbf{W}_{2}. \end{gather}\] where \(\mathbf{W}_s \in \mathbb{R}^{d \times d}\) represents the structural adapter, \(\mathbf{W}_1 \in \mathbb{R}^{d \times d_z}\) and \(\mathbf{W}_2 \in \mathbb{R}^{d_z \times 1}\) sequentially project the representations to an activation scaler with an non-linear activation above the intermediate bottleneck mainifold. Given an input sequence of tokens \((w_1, w_2, \dots, w_n)\), the Hash Encoder processes each token \(w_i\) to its corresponding hash embedding \(\mathbf{e}_i \in \mathbb{R}^d\).

3.2 Sequence Processing Backbone↩︎

\(\mathbf{X} = [ \mathbf{e}_1, \mathbf{e}_2, \dots, \mathbf{e}_n]^\top\) where \(\mathbf{X} \in \mathbb{R}^{n \times d}\) passes through a standard stack of \(L\) Transformer layers. At each time-step \(t\), the final layer of the backbone emits a contextualized latent vector \(\mathbf{h}_t \in \mathbb{R}^d\): \(\mathbf{h}_t = \mathrm{Transformer}(\mathbf{X}_{[:t,:]})\). Subsequently, \(\mathbf{h}_t\) is fed to the Hash Decoder.

3.3 Hash Decoder↩︎

To map the continuous hidden states back into the multi-hash ID signature space, we implement an auto-regressive Cascaded Predictor. This module iteratively refines its index predictions. It functions as a structured error-correcting system where preceding hashing choices directly constrain and contextualize subsequent token-signature inferences. To anchor this iterative cascade to the sequence context for predicting the next token \(w_{t+1}\), the decoder initializes its prediction loop with the final hidden state of the backbone at the current time-step \(t\). Thus, the root state \(\mathbf{c}^{(1)} \in \mathbb{R}^d\) for the logit computation cascade is defined as \(\mathbf{c}^{(1)} = \mathbf{h}_t\).

3.3.0.1 Logit Computation.

For each sequential hash head \(i \in \{1, \dots, H\}\), the decoder projects the current latent hash state \(\mathbf{c}^{(i)} \in \mathbb{R}^{d}\) to compute a logit distribution \(\mathbf{o}^{(i)} \in \mathbb{R}^{B}\) over the physical bucket allocations. This is executed by slicing a dedicated subspace of the hash head weights \(\mathbf{W}_{o}^{(i)} \in \mathbb{R}^{d \times B}\): \[\mathbf{o}^{(i)} = \mathbf{W}_{o}^{(i)\top}\mathbf{c}^{(i)},\] where \(\mathbf{W}_{o}^{(i)}\) defines the localized parameter weight matrix assigned exclusively to the \(i\)-th coordinate bucket array. Following [26], we tie the input and output embedding weights by setting \(\mathbf{W}_{o}^{(i)\top}=\mathbf{E}^{(i)}\).

3.3.0.2 Soft Embedding Retrieval.

For all non-terminal heads (\(i < H\)), the decoder extracts a continuous representation of its prediction to pass down the cascade. We first compute a normalized probability distribution \(\mathbf{p}^{(i)} \in \mathbb{R}^{B}\) across the bucket candidates via a softmax operation: \[\mathbf{p}^{(i)} = \mathrm{Softmax}(\mathbf{o}^{(i)}).\] Using a hard discrete index during intermediate steps disrupts differentiability. Instead, the module computes a soft bucket embedding \(\mathbf{e}^{(i)} \in \mathbb{R}^{d}\) as the expected value of the shared embedding matrix \(\mathbf{E}^{(i)}\), weighted by the logit probabilities: \[\mathbf{e}^{(i)} = \mathbf{E}^{(i)\top}\mathbf{p}^{(i)}\]

3.3.0.3 State Update via Cascade Mixer.

To propagate the contextualized trajectory to the next signature head, the internal hash state requires an update. We achieve this using a recursive cascade mixer inspired by tree-structured recursive networks [27], [28]. This block concatenates the existing state with the retrieved soft embedding and routes the joint representation through a bottleneck layer. Augmented with a structural residual connection, the subsequent state formulation \(\mathbf{c}^{(i+1)}\) is defined as: \[\mathbf{c}^{(i+1)} = \mathbf{c}^{(i)} +\mathbf{W}_{up}^{(i)\top}\sigma(\mathbf{W}_{dn}^{(i)\top}\begin{bmatrix} \mathbf{c}^{(i)} \\ \mathbf{e}^{(i)}\end{bmatrix}),\] where \(\sigma\) is an element-wise activation, and \(\mathbf{W}_{dn}^{(i)} \in \mathbb{R}^{2d \times b}\) and \(\mathbf{W}_{up}^{(i)} \in \mathbb{R}^{b \times h}\) represent the low-rank projection weights of the bottleneck layer.

3.4 Probability Modeling↩︎

Standard autoregressive LMs decompose the joint probability of the input into a product of conditional probabilities. In contrast, MultiHashFormer leverages the outputs of the Hash Decoder to factorize this token-level prediction. Specifically, the normalized distributions (\(\mathbf{p}^{(1)}, \dots, \mathbf{p}^{(H)}\)) produced iteratively by the cascaded predictor serve directly as the hash-specific conditional probabilities \(P(\mathcal{H}_i(w_t) \mid \cdot)\) for each signature coordinate \(i \in \{1, \dots, H\}\).

3.4.0.1 Training Phase.

The Hash Decoder maps tokens into a virtual vocabulary space \(\mathcal{V}_{virt}\) defined by the total combinations of physical bucket allocations, where \(|\mathcal{V}_{virt}| = B^H\). Because the actual language vocabulary is highly compact relative to this space, it forms a strict subset: \(\mathcal{V}_{actl} \subset \mathcal{V}_{virt}\) and \(|\mathcal{V}_{virt}| \gg |\mathcal{V}_{actl}|\). Consequently, we allow predictions over coordinate combinations that might not map to actual entries in the language vocabulary. This unconstrained formulation simplifies the optimization objective. The training probability distribution for a given token \(w\) is thus optimized via the product of its independent coordinate probabilities: \[P_{train}(w \mid \cdot) = \prod_{i=1}^{H} P(\mathcal{H}_i(w) \mid \cdot).\]

3.4.0.2 Inference Phase.

Allowing unconstrained decoding at inference could cause the model to generate coordinate combinations that do not map to actual semantic entries, leaking probability mass into invalid signatures. To guarantee the generation of valid multi-hash ID sequences, we explicitly exclude all unassigned signature during inference. This requires re-normalizing the probability distribution strictly over the true token vocabulary \(\mathcal{V}_{actl}\): \[\begin{align} P_{inf}(w \mid \cdot) = \frac{\prod_{i=1}^{H} P(\mathcal{H}_i(w) \mid \cdot)}{\sum_{w' \in \mathcal{V}_{actl}} \prod_{i=1}^{H} P(\mathcal{H}_i(w') \mid \cdot)} \end{align}\] By accumulating the log-probabilities of individual hash IDs, the final step is a standard softmax normalization over the valid token space \(\mathcal{V}_{actl}\).

4 Experimental Setup↩︎

4.1 Models↩︎

We evaluate MultiHashFormer models against standard autoregressive LMs across 100M, 1B and 3B parameter scales. All configurations use a decoder-only Transformer backbone based on the Qwen3 [2] architecture. We use Mistral-7B-v0.3 [29], a predominantly English BPE tokenizer with a 32K vocabulary.

4.1.0.1 Baselines.

We use two baseline configurations: (1) A causal LM with a conventional embedding matrix \(\mathbf{E} \in \mathbb{R}^{|\mathcal{V}| \times d}\) and an equivalent LM head \(\mathbf{W}_{o} \in \mathbb{R}^{d \times |\mathcal{V}|}\) (Standard); (2) a variant of Standard with \(k\) additional transformer layers to match the total parameter count of MultiHashFormer (Standard+\(k\)L). This allows us to verify that any performance improvements in MultiHashFormer do not result from increased parameter capacity.² Embedding and LM head weights are tied similar to the MultiHashFormer. We match the hidden dimension \(d\) and the number of attention heads to the MultiHashFormer.

4.1.0.2 MultiHashFormer.

We use the same core sequence processing backbone to the baseline configurations. We denote variants as H\(H\)B\(B\), where \(H\) is the number of independent hash functions and \(B\) is the physical bucket allocation per head. We evaluate two configurations: H3B10K (\(H=3\), \(B=10,240\)), which directly matches the baseline parameter count, and H4B16K (\(H=4\), \(B=16,384\)), our optimal configuration based on §6. For brevity, we fix the embedding matrices and projection layer sizes across all vocabulary settings. The bottleneck projection dimension for both the Gated Compositional Embedding and the Cascade Mixer is set to \(d_z=64\) (where \(d_z \ll d\)).

4.2 Pre-training Data and Hyperparameters↩︎

All models are pre-trained from scratch on a subset of English FineWeb-Edu [30]. Following Chinchilla scaling laws [31], we adjust data volume based on model scale. The 100M models were trained on 10B tokens, and the 1B and 3B models on 100B tokens. We use a global batch size of 256 with a 2,048-token context window. See Table 1 in Appendix 10 for details.

4.3 Evaluation Benchmarks↩︎

4.3.0.1 Core capabilities.

We include LAMBADA [32] for Language Modeling; Commonsense Reasoning (CR) using ARC-Easy [33], COPA [34], OBQA [35], PIQA [36], HellaSwag [37]; and Reading Comprehension (RC) with RACE [38], SciQ [39], SIQA [40]. We evaluate CR + RC using ReCoRD [41].³

4.3.0.2 Rare Words.

To investigate if the shared bucket mechanism of MultiHashFormer improve rare word representations, we evaluate 1B models on the Card-660 dataset [42]. This dataset contains word pairs (rare-rare or rare-frequent) with human-annotated similarity scores. We compute the cosine similarity between the words using the final and second-to-last hidden states corresponding to the last token. Finally, we measure the correlation between these model-derived scores and the human annotations.

4.4 Vocabulary Expansion↩︎

As mentioned in §1, a key theoretical advantage of MultiHashFormer is its ability to expand its vocabulary capacity without increasing its parameter footprint. To evaluate this capability, we test the models on their ability to integrate new tokens during multilingual vocabulary expansion.

4.4.0.1 Continual Pre-training Data.

We continue pre-training (CPT) models on a multilingual corpus containing 6B tokens evenly split across Arabic, Chinese, and Hindi from FineWeb2 [43]. We also include an extra 2B English tokens from FineWeb-Edu [30] to mitigate catastrophic forgetting. Following [44], we add 5K tokens per language, yielding a final vocabulary of 48K tokens.

4.4.0.2 Model Configuration.

For MultiHashFormer, we expand the vocabulary size by registering new unique virtual (multi-hash ID) signatures without adding new parameters. For baselines, the weights of the new tokens within the embedding matrix are initialized using mean initialization, a standard protocol where each new token receives the average embedding of its corresponding source tokens from the original tokenizer [45]–[48]. To reduce computational overhead, we only update the embedding layer, the LM heads for the Standard baselines, and the hash encoder and decoder for MultiHashFormer. Following [49]–[51], the first two and last two Transformer layers are also updated. See Table 2 (Appendix 10) for full details.

4.4.0.3 Evaluation.

We use five multilingual tasks from MuBench [52], which are HellaSwag, TruthfulQA [53], StoryCloze [54], and MMLU [55].⁴ We also include the English benchmarks from §4.3 to track catastrophic forgetting.

5 Results↩︎

5.1 Core Capabilities↩︎

Table [table:performance951B953B] presents the performance of the baselines alongside MultiHashFormer (MHF) models across the 100M, 1B, and 3B parameter scales.

5.1.0.1 Efficacy while scaling parameter counts.

We first observe that as the model capacity increases from 1B to 3B parameters, MHF (H4B16K) consistently outperforms the baseline on 9 out of 11 tasks. Specifically, on the LAMBADA task, MHF (H4B16K) offers substantial gains of 4.93% and 8.62% over the Standard baseline (30.41% and 28.64%) at the 1B and 3B scales, respectively. Although the standard LM baseline achieves higher scores on OBQA at the 1B scale, the overall results indicate the efficacy of MultiHashFormer in capturing contextual dependencies.

5.1.0.2 Gains under strict parameter matching.

When matching the parameter count at the 1B scale, MultiHashFormer variants offer superior performance compared to baselines. Specifically, MHF (H3B10K) and MHF (H4B16K) outperform Standard and Standard+2L baselines on 8 out of 10 tasks, respectively. Notably, MHF (H4B16K) achieves 64.90 on ReCoRD, surpassing the 63.78 of Standard+2L. Similarly, MHF (H3B10K) outperforms Standard on COPA with 71.00 vs. 65.00. These results suggest that decoupling the vocabulary is effective. Allocating more parameters to the embeddings improves performance more than adding more layers to the model on larger scales.

5.1.0.3 Per-task performance.

Looking at specific tasks, we note a performance trade-off based on the hash configuration. On OBQA, models with fewer hash buckets achieve higher accuracy. This reversal likely stems from the long-tail distribution of the dataset. A large bucket allocation fragments the embedding space for sparse vocabulary items, which degrades the representation of rare factual tokens. Conversely, reading comprehension requires high representational capacity to prevent coordinate-level collisions between tokens across complex contexts. At the 1B scale, the lower-capacity MHF (H3B10K) variant underperforms the Standard baseline on SciQ (68.30% vs. 69.90%) and RACE (29.00% vs. 29.38%), although it outperforms the baseline on SIQA (40.48% vs. 39.10%). Expanding the physical bucket allocation to the MHF (H4B16K) configuration improves these scores to 70.20% on SciQ and 31.39% on RACE, surpassing the Standard baseline. MultiHashFormer’s strong performance on LM and reasoning tasks stems primarily from its ability to mitigate the softmax bottleneck [56], which is further analyzed in Appendix 8. This advantage is especially evident in LAMBADA, which requires predicting specific, context-dependent words, and HellaSwag, which tests narrative logic. Our model effectively distinguishes between high-probability candidates that Standard baselines often conflate.

5.1.0.4 Performance saturation at 100M.

At the 100M scale, the decoder size is more important than the vocabulary representation. MultiHashFormer variants do not consistently outperform Standard baselines, especially on COPA, HellaSwag, and ReCoRD. Instead, increasing decoder depth by 4 layers is better across 7 tasks. We attribute this to three constraints of smaller and shallower architectures: (1) restricted hidden dimensions conflate distinct tokens with similar hash signatures; (2) shallower depth prevents the model from contextualizing and disambiguating these embeddings; and (3) narrower hidden states restrict the rank upper bound (see our theoretical analysis in Appendix 8), degrading log-probability estimation. Consequently, MultiHashFormer scales more effectively with larger decoders.

5.2 Rare Word Representations↩︎

Table [table:card660] shows the correlation coefficients on the Card-660 dataset. The MultiHashFormer variants consistently outperform Standard models while maintaining an equivalent parameter count. We find that MultiHashFormer is better at identifying semantically equivalent word pairs (see examples in Appendix 9). This performance gap is particularly evident when analyzing hidden states from the second-to-last decoder layer, where representations are less biased toward the specific training tasks. Our model effectively captures semantic representations of rare vocabulary items by forcing sparse tokens to share representational capacity.

5.3 Vocabulary Expansion↩︎

Figure 2 illustrates the performance of the adapted baselines compared to the adapted MultiHashFormer models at 1B and 3B parameter scales across Arabic, Hindi, Chinese, and English. Notably, both the 1B and 3B MHF (H4B16K) models consistently outperform Standard on 12 and 13 out of 22 multilingual tasks, respectively. They achieve this without the additional 31-million-parameters needed to accommodate 15K new tokens in the expanded vocabulary of the Standard baselines. We further find that MHF (H3B10K) and MHF (H4B16K) perform comparably (difference smaller than 1%) on 15 out of 22 tasks. This indicates that performance remains robust during vocabulary expansion. Furthermore, under a strict parameter-count matching constraint prior to vocabulary expansion, MHF (H3B10K) and MHF (H4B16K) achieve better or comparable performance to the Standard models on the majority of English tasks (6 and 9 out of 10, respectively). This suggests that MultiHashFormer does not suffer from more catastrophic forgetting relative to Standard. It successfully supports a 46.9% larger multilingual vocabulary without a single additional parameter while preserving its core capabilities in English.

6 Analysis↩︎

We further analyze the core architectural components of MultiHashFormer. Due to computational resource constraints, we conduct this analysis at the 1B parameter trained up to 20B tokens.

6.0.0.1 Single vs. Multi-hash ID.

To demonstrate the necessity of Multi-ID signatures, we evaluate three different MultiHashFormer configurations (H4B4K, H4B8K, and H4B16K) against their Single-ID counterparts (H1B4K, H1B8K, and H1B16K). Table [table:single95multi] presents the results on LAMBADA. Models with Multi-ID signatures consistently outperform those using Single-ID signatures across all configurations (B4K, B8K, and B16K). Specifically, the performance difference is higher at lower bucket capacities (B4K), where H4B4K achieves 30.27% accuracy compared to the 4.29% of H1B4K. Expanding the capacity to B16K with Single-ID only improves accuracy to 14.30%. These results suggest that a signature collision severely degrades the core capability of the model. Employing Multi-ID signatures to prevent such collisions is more effective than increasing the number of hash buckets.

6.0.0.2 Varying Hash Functions and Bucket Size.

To evaluate the impact of hash configuration on parameter efficiency and downstream performance, we test various combinations of hash functions (\(H\)) and bucket sizes (\(B\)). Figure 3 illustrates average scores on four core capabilities of MultiHashFormer variants against their embedding parameter counts, across different combinations of \(H\) and \(B\). All MultiHashFormer configurations consistently outperform Standard on Language Modeling and Commonsense Reasoning, including variants that utilize strictly smaller embedding matrices, such as H3B4K, H4B4K, and H3B8K. Although scaling both \(H\) and \(B\) sharply increases the embedding parameter count, the corresponding accuracy scores remain stable. Specifically, the best-performing variant improves over the lowest by only 4%, despite a tenfold increase in parameter count from 10M to 102M. Consequently, the H4B16K variant achieves an optimal balance between parameter efficiency and predictive accuracy. We therefore adopt H4B16K as the primary configuration for the 1B and 3B scaling experiments presented in §5.1.

6.0.0.3 MMH3 vs. LSH.

We also investigate whether incorporating Locality-Sensitive Hashing [57] enhances the general capability of the model by capturing morphological similarity. Because LSH maps structurally similar input features to identical hash buckets with high probability, applying it to character-level trigrams tends to force subwords with similar spelling to share embedding representations. To evaluate this mechanism, we pre-train three additional MHF (H4B16K) variants from scratch at a 1B-parameter scale, keeping the dataset and hyperparameters identical. Table [table:random95lsh] presents the performance of these models on LAMBADA. Increasing the proportion of LSH functions while fixing the total number of hash functions does not yield a consistent accuracy improvement. This outcome suggests that explicitly injecting a morphological inductive bias is not necessary given the inherent computational complexity of LSH compared to MMH3. The standard deterministic random hashing of MMH3 provides sufficient representational flexibility for the network to learn subword relationships entirely end-to-end.

7 Conclusion↩︎

We introduced MultiHashFormer, a generative framework that leverages multi-hash structures to bypass traditional vocabulary bottlenecks. Empirical evaluation demonstrates that it offers improvements both in core capabilities and rare word representations. Furthermore, the framework enables seamless vocabulary expansion without requiring additional parameters.

Limitations↩︎

7.0.0.1 Model size.

Due to computational resource constraints, we restrict our evaluation to models at the 100M, 1B and 3B scales. Following the protocol of [58], 1B and 3B models were trained from scratch within a standard academic budget of 100B tokens. While MultiHashFromer shows an upward performance trajectory with model size, exploring larger scales (e.g., 7B+ parameters) remains a valuable direction for institutions with access to the required computing resources.

7.0.0.2 Single seed.

Due to the high computational cost of pre-training 1B and 3B parameter models from scratch for 100B tokens, conducting multiple training runs was prohibitive under our academic infrastructure constraints. Consequently, our empirical results are based on a single seed per configuration. However, the consistent performance gains observed across both the 1B and 3B scales demonstrate the robustness of the MultiHashFormer framework. This consistency indicates that the improvements introduced by our Hash Encoder and Hash Decoder stem from inductive bias rather than random sampling variance. Furthermore, adopting the established hyperparameter protocols of [59] and [58], we ensure standard and reproducible training dynamics.

Acknowledgments↩︎

We would like to thank Maggie Mi for the valuable feedback. We acknowledge (1) IT Services at the University of Sheffield for the provision of services for high-performance computing; (2) the use of the University of Oxford Advanced Research Computing (ARC) facility; (3) the Isambard-AI National AI Research Resource (AIRR), which is operated by the University of Bristol and is funded by the UK Government’s Department for Science, Innovation and Technology (DSIT) via UK Research and Innovation; and the Science and Technology Facilities Council [ST/AIRR/I-A-I/1023]; and (4) the EuroHPC Joint Undertaking for awarding us access to Leonardo, hosted by CINECA (Italy).

8 Softmax Bottleneck↩︎

8.1 Preliminaries↩︎

Language models (LMs) define the conditional distribution \(P_\theta(w|c)\) by applying a softmax function to a linear projection of the hidden state \(\mathbf{h}_t\):

\[\begin{align} P_\theta(w|c)=\frac{\text{exp }\mathbf{h}_t^\top\mathbf{w}_{w}}{\sum_{w^\prime}\text{exp }\mathbf{h}_t^\top\mathbf{w}_{w^\prime}} \end{align}\]

where both the context vector \(\mathbf{h}_t(c_t; \theta)\) and the word embedding \(\mathbf{w}_{w_t}(w_t; \theta)\) are on a \(d\)-dimensional space. Their inner product, \(\mathbf{h}_t^\top \mathbf{w}_{w_t}\), defines the logit. To analyze the expressive capacity of the softmax function, we define the following three matrices and their log-probabilities:

\[\begin{align} \mathbf{H}_\theta = [\mathbf{h}_{1}, \dots, \mathbf{h}_{n}]^\top, \quad \mathbf{W}_\theta = [\mathbf{w}_{1}, \dots, \mathbf{w}_{\vert\mathcal{V}\vert}]^\top \\ \mathbf{A} = [a_{i,j}]_{n \times {\vert\mathcal{V}\vert}} \in \mathbb{R}^{n \times {\vert\mathcal{V}\vert}}, \text{ where } a_{i,j} = \log p^\ast(w_j|c_i) \end{align}\]

\[\begin{align} \log p^\ast(w|c) &= \log \left( \frac{\exp(\mathbf{h}_t^\top\mathbf{w}_w)}{\sum_{w^\prime} \exp(\mathbf{h}_t^\top\mathbf{w}_{w^\prime})} \right) \\ &= \mathbf{h}_t^\top\mathbf{w}_w - \log \sum_{w^\prime} \exp(\mathbf{h}_t^\top\mathbf{w}_{w^\prime}) \end{align}\]

\(\mathbf{H}_\theta \in \mathbb{R}^{n \times d}\) denote the matrix of \(\mathbf{h}_t\) and \(\mathbf{W}_\theta \in \mathbb{R}^{\vert\mathcal{V}\vert \times d}\) is the projection matrix for all tokens in the vocabulary. The matrix \(\mathbf{A} \in \mathbb{R}^{n \times {\vert\mathcal{V}\vert}}\) contains the log probabilities of the true data distribution. We index \(\mathbf{H}\) and \(\mathbf{W}\) by \(\theta\) to indicate that both represent functions within a joint family \(\mathcal{U}\) parameterized by \(\theta\). In practice, \(\mathbf{H}_\theta\) is realized via a Transformer-based LM, while \(\mathbf{W}_\theta\) is instantiated as a learned token embedding lookup table.

We further define a set of matrices, \(F(\mathbf{A})\), generated by applying a row-wise shift to \(\mathbf{A}\): \[\begin{align} F(\mathbf{A}) = \{ \mathbf{A} + \Lambda \mathbf{J}_{n,{\vert\mathcal{V}\vert}} \mid \Lambda \in \mathbb{R}^{n \times n} \text{ is a diagonal matrix} \} \end{align}\]

where \(\mathbf{J}_{n,{\vert\mathcal{V}\vert}} \in \mathbb{R}^{n \times {\vert\mathcal{V}\vert}}\) denotes the all-ones matrix. This row-wise shift operation effectively adds a unique scalar constant to each element of \(\mathbf{A}\)’s rows. Since the diagonal entries of \(\Lambda\) can be any real values, \(F(\mathbf{A})\) constitutes an infinite set characterized by two key properties:

Given Property [property:property951], we establish:

Following this lemma, expressiveness is framed as follows: does there exist a parameter \(\theta\) and a matrix \(\mathbf{A}^\prime \in F(\mathbf{A})\) satisfying \(\mathbf{H}_\theta\mathbf{W}_\theta^\top = \mathbf{A}^\prime\). LMs learn matrices \(\mathbf{H}_\theta\) and \(\mathbf{W}_\theta\) to factorize a target matrix \(\mathbf{A}^\prime \in F(\mathbf{A})\). For a valid factorization, the rank of the product \(\mathbf{H}_\theta\mathbf{W}_\theta^\top\) must be at least equal to the rank of \(\mathbf{A}^\prime\). Because \(\mathbf{H}_\theta \in \mathbb{R}^{n \times d}\) and \(\mathbf{W}_\theta \in \mathbb{R}^{{\vert\mathcal{V}\vert} \times d}\), the rank of this product is strictly upper-bounded by the embedding dimension \(d\). Consequently, if \(d \geq \text{rank}(\mathbf{A}^\prime)\), a universal approximator can recover \(\mathbf{A}^\prime\). Conversely, if \(d < \text{rank}(\mathbf{A}^\prime)\), no pair \((\mathbf{H}_\theta, \mathbf{W}_\theta)\) can recover \(\mathbf{A}^\prime\), regardless of the expressiveness of \(\mathcal{U}\).

By combining Proposition [proposition:proposition951] with the properties of \(F(\mathbf{A})\) outlined in Property [property:property952], [56] define the Softmax Bottleneck:

This demonstrates that an insufficient dimension \(d\) restricts Softmax from expressing the true data distribution. The conclusion is not restricted to a finite language \(\mathcal{L}\). Because when \(\mathcal{L}\) is infinite, one can always take a finite subset and the softmax bottleneck still exists.

8.2 MultiHashFormer as a Mitigation Strategy↩︎

While training, MultiHashFormer approximates elements in \(\mathbf{A}\) by \[\begin{align} \log p^\ast(w|c) &= \log \prod_{i}^{H} p^\ast(\mathcal{H}_i(w)|c)\\ &= \sum_{i=1}^{H}\log p^\ast(\mathcal{H}_i(w)|c)\\ &= \sum_{i=1}^{H}\log \left( \frac{\exp(\mathbf{c}^{(i)\top}\mathbf{w}^{(i)}_{\mathcal{H}_i(w)})\pi^{(i)}_{\mathcal{H}_i(w)}}{\sum_{j=1}^B \exp(\mathbf{c}^{(i)\top}\mathbf{w}^{(i)})} \right) \\ &= \sum_{i=1}^{H}\mathbf{c}^{(i)\top}\mathbf{w}^{(i)}_{\mathcal{H}_i(w)}\pi^{(i)}_{\mathcal{H}_i(w)} \\ &\quad- \sum_{i=1}^{H}\log \sum_{j=1}^{B} \exp(\mathbf{c}^{(i)\top}\mathbf{w}^{(i)}_{j}) \end{align}\]

The model projects representations to coordinates of the hash signature, using \(H\) localized parameter weight matrices assigned exclusively to \(i\)-th coordinate bucket array, \(\mathbf{W}_o^{(i)} \in \mathbb{R}^{d \times B}\). These coordinates are then mapped to the true vocabulary space via transition matrices \(\pi^{(i)} \in \{0, 1\}^{B \times |\mathcal{V}|}\). Here, each column of \(\pi^{(i)}\) is a one-hot vector, satisfying \(\sum_{j=1}^{B} \pi^{(i)}_{j,k} = 1\) for every column \(k\).

The estimation could be further written in a matrix form:

\[\begin{align} \hat{\mathbf{A}}_{MHF} &= \sum_{i=1}^{H}\mathbf{H}_\theta^{(i)}\mathbf{W}_o^{(i)\top}\pi^{(i)}\\ &\quad-\sum_{i=1}^{H}\log\left(\sum_{j=1}^{B}\exp(\mathbf{H}_\theta^{(i)}\mathbf{W}_o^{(i)\top})\right) \end{align}\]

Consequently, \(\text{rank}(\mathbf{\hat{A}}_{\text{MHF}}) \leq \min(n,B, \vert\mathcal{V}_{actl.}\vert\), \(H \times \min(d, B))= \min(B,H\times d\)), where \(H\) denotes the number of hash functions configured by MultiHashFormer, \(B\) denotes the number of discrete hash buckets per function, and \(d\) is the dimensionality of the latent hash state vectors \(\mathbf{c}^{(i)}\). Given that the rank of Standard baselines is bounded by \(\text{rank}(\mathbf{\hat{A}}_{\text{Standard}}) \leq \min(d, n, \vert\mathcal{V}_{\text{actl.}}\vert) = d\), MultiHashFormer elevates the upper bound of this rank to enhance model expressiveness, while employing multi hash functions and non-linear transformation between latent hash state vectors. This aligns with the intuition that aggregating multiple distinct observations inherently improves estimation accuracy.

During inference, although we exclude all unassigned signatures, the rank upper bound remains invariant between training and inference. This stability stems from the fact that the row-wise partition function does not contribute to the final upper bound of the rank. While MultiHashFormer does not produce an arbitrary rank, it elevates the rank of the conditional distribution matrix. This improvement drives performance gains in high-entropy reasoning tasks, including LAMBADA and HellaSwag.

9 Rare Word Examples from Card-660↩︎

We first look to word pairs with high human-annotated similarity to serve as hard examples for our illustration. Table [table:card66095examples] presents examples of high-similarity word pairs from the Card-660 dataset. We compare normalized human annotation scores against cosine similarities derived from the second-to-last decoder layers of the 1B Standard baseline and MultiHashFormer. Compared to the Standard baseline, MultiHashFormer consistently assigns higher similarity scores to semantically equivalent word pairs, such as abbreviations, aliases, misspellings, and synonyms. Examples from word pairs with low similarities and medium similarities are shown in Table [table:card66095examples95other].

10 Hyperparameters↩︎

10.1 Hyperparameters for Pre-training↩︎

10.2 Hyperparameters for VE Continual-pretraining↩︎

11 MultiHashFormer Abbrevations and Configurations↩︎

Table [table:abbr95mhf] presents the detailed configurations of MultiHashFormer variants along with their abbreviations.

References↩︎