Skip to content

MultiHashFormer: Hash-based Generative Language Models

Conference: EMNLP 2026
arXiv: 2606.28057
Paper: ACL Anthology
Code: https://github.com/HUIYINXUE/MHF
Area: LLM Reasoning & Generation
Keywords: Autoregressive Language Models, Hash Signatures, Vocabulary Bottleneck, Multilingual Vocabulary Expansion, Softmax Bottleneck

TL;DR

MultiHashFormer encodes discrete tokens into collision-free multi-ID hash signatures and reconstructs them sequentially via a cascaded predictor, breaking the linear vocabulary parameter scaling, mitigating the softmax rank bottleneck, and enabling zero-parameter multilingual vocabulary expansion.

Background & Motivation

Modern autoregressive language models, such as LLaMA, Mistral, and Qwen, universally rely on explicit embedding lookup tables paired with linear language modeling heads. This parameterization assigns every discrete token in a pre-defined vocabulary to a distinct, high-dimensional dense vector, causing the physical parameter footprint of the embedding layers to scale strictly linearly with vocabulary size. As models strive to encompass long-tail domain jargon, rare entities, and dozens of diverse human languages, this linear scaling induces a severe vocabulary bottleneck. Embedding tables alone easily demand hundreds of millions to billions of parameters, creating prohibitive memory overheads during both on-device edge deployment and continual multilingual pre-training.

To compress embedding matrices, prior research has explored token-free architectures (such as ByT5, BLT, and Bolmo) as well as randomized hash embeddings (such as Tito Svenstrup et al.'s Hash Embeddings, Proformer, and HashFormer). However, token-free methods inevitably multiply sequence lengths by several folds, drastically slowing autoregressive inference and magnifying the quadratic computational overhead of attention. Meanwhile, conventional hash embeddings project massive vocabularies into a compact set of physical buckets, resulting in frequent many-to-one collisions where semantically unrelated words (such as "cat" and "map") share the exact same hash index. While bidirectional encoders can resolve such ambiguities using full-sentence context, an autoregressive causal decoder predicting a collided hash index cannot deterministically decode back to the true underlying token, restricting hash embeddings strictly to encoder-only discriminative settings.

Drawing inspiration from chaotic dynamical memory systems where overlapping, distributed state spaces enable immense pattern retrieval capacity, this paper proposes an orthogonal framework that completely bypasses the vocabulary bottleneck in generative decoder-only transformers. Core idea: represent each discrete token as a unique multi-ID hash signature generated by multiple independent hash functions, compress this signature into a dense latent state using gated compositional embeddings at the input, and sequentially reconstruct the next-token signature via an autoregressive cascaded predictor at the output, eliminating hash collisions while simultaneously elevating the softmax rank upper bound to \(\min(B, H \times d)\) without adding any parameters.

Method

Overall Architecture

The MultiHashFormer pipeline is organized into three tightly coupled modules: an input Hash Encoder, a standard Transformer Decoder Backbone, and an output Hash Decoder. Given an input token sequence \((w_1, \dots, w_n)\), the Hash Encoder evaluates \(H\) independent hash functions to produce an \(H\)-dimensional coordinate signature \([H_1(w), \dots, H_H(w)]\) for each token and fuses their physical bucket embeddings through a low-rank gated compositional bottleneck into a continuous embedding vector \(e \in \mathbb{R}^d\). The Transformer backbone executes standard causal multi-head self-attention and feed-forward operations, generating contextualized hidden states \(h_t\) at time-step \(t\). Finally, the Hash Decoder treats \(h_t\) as the root state of an autoregressive cascaded predictor, iteratively decoding the multi-hash coordinates of the subsequent token, which are subsequently re-normalized over the valid vocabulary space to deterministically recover the text token.

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    In["Input Token Sequence (w1, ..., wn)"] --> MHI["Multi-Hash Indexing & Iterative Rehashing<br/>MurmurHash3 generates collision-free H-dim signatures"]
    MHI --> GCE["Gated Compositional Embedding<br/>Bottleneck network computes soft gate weights & projects"]
    GCE --> BB["Transformer Decoder Backbone<br/>Causal self-attention & contextual latent state ht"]
    BB --> CP["Cascaded Predictor<br/>Recursive cascade mixer iteratively decodes hash distributions"]
    CP -->|Training Phase| UObj["Unconstrained Factorized Objective<br/>Direct product of coordinate conditional probabilities"]
    CP -->|Inference Phase| RNorm["Valid Vocabulary Re-normalization<br/>Prune invalid combinations & recover deterministic token"]
    UObj --> OutTrain["Backpropagate Training Loss"]
    RNorm --> OutGen["Generate Next Token wt+1"]

Key Designs

1. Multi-Hash Indexing and Iterative Rehashing: Eliminating Token Collisions for Generative Decoding Prior hashing paradigms suffer from many-to-one collisions under a single hash function, rendering generative inversion ill-posed. MultiHashFormer addresses this fundamental obstacle by employing \(H\) independent, non-cryptographic MurmurHash3 (MMH3) functions \(H_1, \dots, H_H\), each parameterized by a distinct seed \(\text{seed}_i\), to map non-padding tokens into physical bucket allocations \(H_i(w) = \text{MMH3}(w, \text{seed}_i) \pmod{B-1} + 1\), reserving bucket index 0 for padding. By expanding scalar indices into an \(H\)-dimensional tuple \([H_1(w), \dots, H_H(w)]\), the combinatorial capacity of the virtual signature space scales exponentially to \(B^H\). For instance, with \(H=4\) and \(B=16,384\), the system affords an upper bound of \(16384^4 \approx 7.2 \times 10^{16}\) unique signatures, vastly exceeding practical vocabulary sizes. To guarantee zero collisions across the entire vocabulary, an iterative rehashing scheme checks for conflicts upon registering each vocabulary item; if a collision occurs, it incrementally modifies only the seed of the final function (\(\text{seed}_H\)) until an unused signature is found, establishing a strict, zero-parameter injective mapping from discrete vocabulary to signature space.

2. Gated Compositional Embedding: High-Rank Representational Fusion without Dimension Collapse The model maintains \(H\) distinct embedding matrices \(E^{(i)} \in \mathbb{R}^{B \times d}\), where physical bucket vectors are globally shared across all vocabulary tokens. Simply averaging or summing these embeddings would cause representational degeneration when sparse, unrelated tokens overlap in a particular bucket. MultiHashFormer resolves this via a context-aware compositional gate: each bucket embedding vector \(E^{(i)}_{[H_i(w), :]}\) passes through a feed-forward bottleneck network with a small projection dimension \(d_z \ll d\) (\(d_z = 64\)) parameterized by \(W_1 \in \mathbb{R}^{d \times d_z}\) and \(W_2 \in \mathbb{R}^{d_z \times 1}\) to yield a scalar activation \(\alpha_i = \sigma(E^{(i)}_{[H_i(w), :]} W_1) W_2\). Normalized by a softmax operation over the \(H\) coordinates to produce dynamic weights \(\tilde{\alpha}_i\), the final token embedding is assembled and projected through an adapter matrix \(W_s \in \mathbb{R}^{d \times d}\): $\(e = \left( \sum_{i=1}^H \tilde{\alpha}_i E^{(i)}_{[H_i(w), :]} \right) W_s\)$ Unlike traditional matrix factorizations (such as ALBERT) that restrict rank along the hidden dimension, MultiHashFormer factorizes exclusively along the vocabulary dimension, preserving the full hidden representational rank.

3. Cascaded Predictor: Recursive Error-Correcting State Updates for Multi-Head Decoding To autoregressively predict the multi-hash signature coordinates for the next token \(w_{t+1}\), the Hash Decoder initializes its iterative state at root state \(c^{(1)} = h_t\), using the backbone's final contextual latent state. For each sequential coordinate head \(i \in \{1, \dots, H\}\), the model projects the latent state \(c^{(i)} \in \mathbb{R}^d\) using tied output weights \(W_o^{(i)\top} = E^{(i)}\) to derive bucket logits \(o^{(i)} = W_o^{(i)\top} c^{(i)} \in \mathbb{R}^B\), followed by softmax normalization to obtain probabilities \(p^{(i)} = \text{Softmax}(o^{(i)})\). To preserve end-to-end differentiability across intermediate steps (\(i < H\)), the module extracts a continuous expected soft bucket embedding \(e^{(i)} = E^{(i)\top} p^{(i)}\). Inspired by recursive tree networks, the Cascade Mixer concatenates the current state \(c^{(i)}\) with \(e^{(i)}\) and updates the internal state through a low-rank bottleneck layer augmented with a residual skip connection: $\(c^{(i+1)} = c^{(i)} + W_{\text{up}}^{(i)\top} \sigma\left( W_{\text{dn}}^{(i)\top} \begin{bmatrix} c^{(i)} \\ e^{(i)} \end{bmatrix} \right)\)$ where \(W_{\text{dn}}^{(i)} \in \mathbb{R}^{2d \times b}\) and \(W_{\text{up}}^{(i)} \in \mathbb{R}^{b \times d}\). This recursive cascade allows preceding hash decisions to directly constrain and contextualize subsequent coordinate distributions, serving as a structured error-correcting mechanism.

4. Unconstrained Training Factorization and Valid Vocabulary Re-normalization Because the virtual signature space \(|V_{\text{virt}}| = B^H\) is exponentially larger than the actual active vocabulary space \(|V_{\text{actl}}|\), constraining intermediate distributions over only valid tokens during training would introduce an intractable partition function. MultiHashFormer simplifies the training objective by treating the target likelihood as an unconstrained product of independent coordinate probabilities: \(P_{\text{train}}(w \mid \cdot) = \prod_{i=1}^H P(H_i(w) \mid \cdot)\). During inference, to strictly prevent probability mass from leaking into unassigned signatures, the model accumulates coordinate log-probabilities and explicitly normalizes them exclusively over the true language vocabulary \(V_{\text{actl}}\): $\(P_{\text{inf}}(w \mid \cdot) = \frac{\prod_{i=1}^H P(H_i(w) \mid \cdot)}{\sum_{w' \in V_{\text{actl}}} \prod_{i=1}^H P(H_i(w') \mid \cdot)}\)$ Because these log-probability accumulations can be executed in a single batched matrix operation on modern GPUs, this step introduces negligible wall-clock latency (taking 97.38 ms per sample versus 96.42 ms for standard models on an AMD MI300X GPU).

Loss & Training

The network is optimized end-to-end using standard causal next-token cross-entropy over the sequence tokens: $\(\mathcal{L} = - \sum_{t=1}^n \sum_{i=1}^H \log P\left(H_i(w_t) \mid c^{(i)}_t\right)\)$ Because input and output embedding matrices are tied (\(W_o^{(i)\top} = E^{(i)}\)), gradient signals backpropagated through both the encoder and decoder simultaneously refine the shared physical bucket vectors. Crucially, as proven in the paper's mathematical derivations, standard language models suffer from a fundamental Softmax Bottleneck where the log-probability matrix rank cannot exceed the hidden dimension \(\text{rank}(\hat{A}_{\text{Standard}}) \le d\). In contrast, MultiHashFormer estimates the log-probability matrix as a sum of \(H\) localized projections modulated by non-linear cascade states: \(\hat{A}_{\text{MHF}} = \sum_{i=1}^H H_{\theta}^{(i)} W_o^{(i)\top} \pi^{(i)}\), elevating the theoretical rank upper bound to \(\min(B, H \times d)\). This directly enhances the expressive capacity required to capture intricate, high-entropy token transitions.

Key Experimental Results

Main Results

All models are built upon the Qwen3 decoder architecture and the Mistral 32K BPE tokenizer, pre-trained from scratch on English FineWeb-Edu under Chinchilla scaling laws (100M on 10B tokens; 1B and 3B on 100B tokens). Evaluation spans 10 downstream benchmarks across Language Modeling (LAMBADA), Commonsense Reasoning (ARC-Easy, COPA, OBQA, PIQA, HellaSwag), and Reading Comprehension (RACE, SciQ, SIQA, ReCoRD).

Scale Model Configuration Emb Params Dec Params LAMBADA (↑) ARC-Easy (↑) COPA (↑) HellaSwag (↑) RACE (↑) ReCoRD (F1, ↑)
- Random Guess - - - 25.00 50.00 25.00 25.00 19.10
100M Standard Baseline 25M 87M 15.33 41.33 64.00 28.59 26.41 49.47
100M Standard+4L (Depth Match) 25M 116M 19.64 45.08 64.00 29.99 26.79 53.08
100M MHF (H3B10K) 25M 87M 16.40 44.91 61.00 27.81 27.18 48.21
100M MHF (H4B16K) 52M 87M 18.79 45.24 62.00 27.99 28.42 50.11
1B Standard Baseline 65M 0.9B 30.41 59.85 64.00 38.99 29.38 63.20
1B Standard+2L (Depth Match) 65M 1.0B 30.66 60.23 65.00 39.85 29.28 63.78
1B MHF (H3B10K, Param Match) 65M 0.9B 35.78 61.95 65.00 40.45 29.00 64.51
1B MHF (H4B16K, Optimal) 138M 0.9B 35.34 64.35 71.00 41.32 31.39 64.90
3B Standard Baseline 65M 2.8B 28.64 60.23 65.00 39.65 29.76 62.26
3B MHF (H4B16K) 138M 2.8B 37.26 66.88 68.00 42.89 30.91 64.13

At the 1B scale, the strictly parameter-matched MHF (H3B10K) outperforms the Standard baseline on 8 out of 10 tasks, while the optimal MHF (H4B16K) establishes clear leads across reasoning and comprehension benchmarks. At the 3B scale, MHF (H4B16K) achieves decisive gains over the Standard baseline, boosting LAMBADA accuracy from 28.64% to 37.26% (+8.62% absolute improvement) and ARC-Easy from 60.23% to 66.88%. Conversely, at the small 100M scale, restricted hidden dimensions and shallow depths limit the network's ability to disambiguate hash coordinates, allowing the deeper Standard+4L model to achieve superior performance.

Ablation Study

To investigate the necessity of multi-ID signatures and the utility of morphological inductive biases, the authors conducted controlled ablations on the 1B scale trained for 20B tokens, evaluating single-ID (H1) versus multi-ID (H4) configurations across bucket sizes and varying mixtures of Locality-Sensitive Hashing (LSH) and MurmurHash3 (MMH3).

Ablation Focus Model / Bucket Configuration LAMBADA Accuracy (%) Core Architectural Implication
Single-ID vs. Multi-ID H1B4K (Single-ID, B=4,096) 4.29 Severe token collisions collapse autoregressive generation
H4B4K (Multi-ID, B=4,096) 30.27 Combinatorial multi-signatures eliminate collisions (+25.98%)
H1B8K (Single-ID, B=8,192) 8.77 Doubling bucket size yields marginal recovery for single hashes
H4B8K (Multi-ID, B=8,192) 30.47 Performance remains consistently high under multi-ID hashing
H1B16K (Single-ID, B=16,384) 14.30 Single-hash collision rate remains crippling even with 16K buckets
H4B16K (Multi-ID, B=16,384) 30.91 Optimal balance of expressive capacity and predictive stability
Morphological Bias (LSH) LSH : MMH3 = 0 : 4 (Pure MMH3) 30.91 Deterministic randomized hashing provides sufficient flexibility
LSH : MMH3 = 1 : 3 30.60 1 LSH head based on character trigrams provides no clear gain
LSH : MMH3 = 2 : 2 30.80 Equal mixture of LSH and MMH3 shows comparable accuracy
LSH : MMH3 = 3 : 1 31.40 Minor variance within expected training fluctuations
LSH : MMH3 = 4 : 0 (Pure LSH) 31.36 Morphological similarity bias adds compute without significant benefit

Key Findings

  • Multi-ID Signatures Are the Key Enabler for Generative Hashing: Single-ID hash models perform catastrophically on autoregressive prediction (yielding only 4.29% to 14.30% on LAMBADA), whereas multi-ID configurations immediately surge above 30%, proving that eliminating many-to-one collisions is paramount.
  • Superior Representation of Long-Tail and Rare Words: On the Card-660 rare word similarity benchmark, MHF (H4B16K) achieves a Pearson \(r\) of 0.30 and Spearman \(\rho\) of 0.32 at the second-to-last layer, compared to 0.26 and 0.25 for the Standard baseline. The shared physical bucket structure acts as an inductive regularizer, enabling rare tokens to benefit from representations tuned by frequent words sharing coordinate buckets.
  • Zero-Parameter Multilingual Vocabulary Expansion: When expanding the vocabulary by 46.9% (from 32K to 48K tokens across Arabic, Chinese, and Hindi), the Standard baseline requires 31M additional parameters. MultiHashFormer seamlessly accommodates all 15K new tokens purely by registering new virtual signatures without adding a single parameter, matching or exceeding the baseline across 12 to 13 of 22 MuBench tasks without degrading original English performance.

Highlights & Insights

  • Orthogonal Decoupling of Vocabulary from Architecture: By converting token embeddings into a deterministic combinatorial signature interface, MultiHashFormer liberates decoder LMs from linear parameter scaling while retaining all sequence-compression benefits of subword tokenization.
  • Theoretical Elevation of the Softmax Rank Upper Bound: By factorizing output log-probabilities across multiple heads via a non-linear cascaded mixer, the model elevates the matrix rank upper bound from \(d\) to \(\min(B, H \times d)\), explaining its dramatic advantages on high-entropy reasoning tasks like LAMBADA (+8.62% at 3B).
  • Practical Zero-Overhead Inference: The explicit unconstrained training formulation combined with vectorized valid-vocabulary re-normalization during inference ensures minimal runtime degradation (less than 1 ms difference per sample on modern accelerator hardware).

Limitations & Future Work

  • Model Scale Bounded at 3B: Due to academic computational constraints, the empirical evaluation is restricted to models up to 3B parameters and 100B pre-training tokens. Validating the scaling behavior at 7B, 13B, and larger scales remains an open frontier.
  • Single Random Seed for Larger Runs: Pre-training 1B and 3B models from scratch was conducted with a single random seed per setting (though 100M runs over 3 random seeds demonstrated low variance and consistent conclusions).
  • Extension to Multi-Token Prediction: Future work aims to generalize the multi-hash framework across token boundaries to support speculative multi-token prediction (MTP) paradigms.
  • vs. HashFormer / Proformer: Earlier hash-based models employed single-hash or one-to-one bucket mappings, inevitably suffering from collisions that restricted them strictly to masked encoder architectures. MultiHashFormer introduces multi-ID signatures and cascaded decoding, making hash embeddings feasible for causal generative decoders for the first time.
  • vs. Token-Free / Byte-Level Models (ByT5, BLT, Bolmo): Byte-level models bypass vocabularies entirely but cause input sequence lengths to expand dramatically, exacerbating latency and memory consumption. MultiHashFormer retains subword tokenization, preserving compact sequence lengths while decoupling parameter counts.
  • vs. T-FREE: T-FREE avoids subwords through sparse activations over locality-sensitive hashed character trigrams, which imposes an English-centric morphological bias. MultiHashFormer uses language-agnostic MurmurHash3 and end-to-end learning, outperforming T-FREE across all benchmarks while supporting arbitrary tokenizers.

Rating

  • Novelty: ⭐⭐⭐⭐⭐ Pioneering multi-hash signature generation and cascaded decoding to break the generation barrier in hash-based language modeling.
  • Experimental Thoroughness: ⭐⭐⭐⭐☆ Rigorous evaluation across 100M, 1B, and 3B scales, extensive downstream tasks, ablations, rare-word analysis, and continual multilingual expansion.
  • Writing Quality: ⭐⭐⭐⭐⭐ Exceptionally clear exposition, structured mathematical derivations of the Softmax rank bottleneck in Appendix A, and detailed empirical documentation.
  • Value: ⭐⭐⭐⭐⭐ Offers a transformative architectural solution for ultra-large multilingual vocabularies, rare word modeling, and memory-constrained LLM pre-training.