PaperlayerView exact revision on arXiv

Source-linked AI summary

MultiHashFormer: Hash-based Generative Language Models

Huiyin Xue, Atsuki Yamaguchi, Nikolaos Aletras

arXiv:2606.28057v1cs.CLcs.AIcs.LG

TL;DR

Embedding matrices create a vocabulary bottleneck for causal language models, limiting parameter-efficient vocabulary expansion. MultiHashFormer enables hash-based autoregression with collision-free multi-ID signatures and consistently outperforms standard Transformers across tasks while supporting parameter-free vocabulary expansion.

  • Problem

    Embedding matrices scale linearly with vocabulary size, creating a fixed-capacity bottleneck and limiting causal language models’ seamless adaptation to new domains or languages.

  • Method

    MultiHashFormer replaces token embeddings with collision-free multi-hash signatures and uses hash encoder-decoder modules to support causal autoregressive generation.

  • Results

    Across 10 tasks and 100M, 1B, and 3B scales, MultiHashFormer consistently outperforms standard Transformer LMs and maintains performance when expanding vocabulary from 32K to 48K without more parameters.

  • Takeaways & Limitations

    The framework offers improvements in core capabilities and rare-word representations while enabling vocabulary expansion without additional parameters.

  • Takeaways & Limitations

    Evaluation is limited to 100M, 1B, and 3B parameter models, leaving performance at larger scales unexplored.

Abstract

from arXiv · show

Language models (LMs) represent tokens using embedding matrices that scale linearly with the vocabulary size. To constrain the parameter footprint, prior work proposes hashing many tokens into a single vector within encoder-only models. While this offers parameter efficiency, many-to-one collisions prevent its use in causal LMs. In this paper, we propose MultiHashFormer, a new framework that allows hash-based autoregression. Each token is represented as a unique hash signature, a short sequence of discrete hash IDs, generated by multiple independent hash functions. A Hash Encoder compresses this signature into a single latent vector for processing by a Transformer decoder. Then, a Hash Decoder generates the hash signature of the next token, which is then mapped back to text. We evaluate our approach at the 100M, 1B and 3B parameter scales, demonstrating that MultiHashFormer consistently outperforms standard Transformer LMs across multiple benchmarks. Furthermore, we show that our model handles multilingual vocabulary expansion with a constant parameter footprint without any modifications.

1 Introduction

MultiHashFormer addresses the vocabulary bottleneck and collision problem in hash-based causal language modeling by representing tokens with unique multi-ID hash signatures. It combines hash-based encoding and decoding to support autoregressive generation while maintaining a fixed parameter footprint during vocabulary expansion.

  • Motivation: Embedding matrices scale linearly with vocabulary size, creating a fixed-capacity bottleneck that limits adaptation to new domains and languages.This bottleneck arises because each token is represented by a unique dense vector in a learned embedding matrix.
  • Limitations of Prior Hashing: Many-to-one token hashing is parameter-efficient but prevents deterministic token recovery in decoder-based generative models.Existing hash-based models are therefore restricted to encoder-based architectures and discriminative training.
  • MultiHashFormer: MultiHashFormer prevents collisions by assigning each token a unique hash signature composed of a short sequence of discrete hash IDs.Using multiple independent hash functions yields approximately 65 quadrillion unique signatures.
  • Architecture: A Hash Encoder compresses each multi-ID signature into a dense latent vector, while a cascaded Hash Decoder sequentially reconstructs the next token’s signature for deterministic text mapping.The hashing interface is independent of the sequence-processing backbone, such as a Transformer.
  • Results: MULTIHASHFORMER consistently outperforms standard Transformer LMs at 100M, 1B and 3B scales across 10 tasks, while improving rare word representations.It also maintains performance when expanding vocabulary size from 32K to 48K without structural changes or increased parameter count.

2 Related Work

Prior approaches reduce vocabulary-related parameter costs through subword, token-free, factorized, or hashed representations, but each retains important limitations. MultiHashFormer addresses these limitations with language-agnostic multi-hash mapping that preserves sequence compression and enables autoregressive token recovery.

  • Vocabulary bottleneck: Embedding matrices scale linearly with vocabulary size, while fixed subword vocabularies struggle with rare or out-of-domain words.BPE and SentencePiece mitigate vocabulary explosion but remain constrained by fixed, data-derived vocabularies.
  • Token-free models: Token-free models bypass the vocabulary bottleneck by operating on unicode or byte sequences, but dramatically increase input sequence length.This group includes AU-Net, Bolmo, H-Net, BLT, CANINE, and ByT5.
  • Hashed character representations: T-FREE uses sparse activations over locality-based hashed character trigrams, but its character-level morphological similarity makes it language-dependent.Its approach avoids tokenization while remaining parameter-efficient.
  • Parameter reduction: Matrix factorization reduces embedding parameters but still assigns an explicit localized vector to every token, preserving linear scaling.ALBERT decouples embedding dimension from hidden dimension without breaking the vocabulary-size constraint.
  • Token hashing: Single-function token hashing compresses vocabularies into physical buckets, but collisions prevent deterministic token recovery during autoregressive generation.Random hash embeddings, Proformer, and HashFormer therefore remain restricted to encoder-only architectures.
  • MultiHashFormer: MultiHashFormer resolves hashed autoregression’s collision limitation through a multi-identifier framework, using combinatorial multi-hash mapping rather than sub-character heuristics.It remains language-agnostic, preserves subword sequence compression, and supports arbitrary tokenization strategies.

3 MultiHashFormer

MultiHashFormer combines collision-free multi-hash token signatures with a gated Hash Encoder, Transformer backbone, and autoregressive Hash Decoder. Its cascaded prediction and vocabulary-constrained inference enable structured next-token generation over valid signatures.

  • Architecture: MultiHashFormer comprises a Hash Encoder, Sequence Processing Backbone, and Hash Decoder for encoding tokens, contextual processing, and autoregressive signature reconstruction.The Hash Encoder compresses each distributed multi-ID signature into one dense embedding.
  • Multi-Hash Indexing: Each token receives H independent hash IDs, while iterative rehashing modifies the final hash seed until every vocabulary signature is collision-free.MurmurHash3 computes each coordinate, and the padding signature is reserved as zero across hash functions.
  • Gated Compositional Embedding: Separate bucket embeddings are combined by a context-aware compositional gate and projected through an adapter into the backbone’s latent space.A bottleneck network with compression dimension dz ≪ d produces softmax-normalized bucket contributions.
  • Cascaded Prediction: The Hash Decoder uses an autoregressive cascaded predictor whose prior hash choices constrain and contextualize subsequent signature predictions.Soft bucket embeddings and a recursive cascade mixer update the internal hash state between sequential hash heads.
  • Training and Inference: During training, predictions span the virtual vocabulary of BH coordinate combinations, whereas inference renormalizes probabilities over valid signatures in Vactl.Unassigned signatures are excluded during inference, and accumulated hash-ID log-probabilities are normalized over the true token vocabulary.

4 Experimental Setup

The experiments compare MultiHashFormer with parameter-matched standard autoregressive Transformers at 100M, 1B, and 3B scales, using shared decoder-only Qwen3-based backbones. They assess language modeling, reasoning, reading comprehension, rare-word representations, and multilingual vocabulary expansion under controlled training and evaluation settings.

  • Experimental Setup: Models use decoder-only Transformers based on Qwen3 and are evaluated against standard autoregressive LMs at 100M, 1B, and 3B parameter scales.The tokenizer is Mistral-7B-v0.3, predominantly English, with a 32K vocabulary.
  • Baselines: The baselines include a conventional embedding-and-head causal LM and a Standard+kL variant with added Transformer layers to match MultiHashFormer’s parameter count.Embedding and LM-head weights are tied, while hidden dimension and attention-head count are matched across configurations.
  • MultiHashFormer: MultiHashFormer variants are denoted HHBB and include H3B10K, matching baseline parameter counts, and H4B16K, selected as optimal from §6.H3B10K uses H = 3 and B = 10,240, while H4B16K uses H = 4 and B = 16,384.
  • Training: All models are pretrained from scratch on English FineWeb-Edu with 10B tokens for 100M models and 100B tokens for 1B and 3B models.Training uses a global batch size of 256 and a 2,048-token context window.
  • Core capabilities: Evaluation covers LAMBADA, commonsense reasoning, reading comprehension, and ReCoRD, with normalized accuracy, F1, or standard accuracy depending on task.ARC-E, SIQA, and OBQA use five-shot evaluation; the remaining tasks use zero-shot evaluation.
  • Multilingual vocabulary expansion: Multilingual expansion adds 5K tokens per language to reach a 48K vocabulary, testing Arabic, Chinese, and Hindi continual pretraining while tracking catastrophic forgetting on English benchmarks.The multilingual corpus contains 6B tokens evenly split across the three languages plus 2B additional English tokens.

5 Results

MultiHashFormer generally outperforms standard language-model baselines as model capacity grows, including under strict parameter matching. Its benefits extend to semantic representation and multilingual vocabulary expansion without adding parameters, while smaller models and some tasks show limitations.

  • Efficacy while scaling parameter counts: From 1B to 3B parameters, MHF (H4B16K) outperforms the baseline on 9 out of 11 tasks.On LAMBADA, it gains 4.93% and 8.62% over Standard at the 1B and 3B scales, respectively.
  • Gains under strict parameter matching: At 1B with matched parameter counts, MHF (H3B10K) and MHF (H4B16K) outperform their baselines on 8 out of 10 tasks.MHF (H4B16K) scores 64.90 on ReCoRD versus 63.78 for Standard+2L, while MHF (H3B10K) scores 71.00 versus Standard’s 65.00 on COPA.
  • Per-task performance: OBQA favors models with fewer hash buckets, whereas reading comprehension requires greater representational capacity.The passage attributes OBQA’s reversal to large buckets fragmenting representations for rare factual tokens.
  • Performance saturation at 100M: At 100M, decoder size matters more than vocabulary representation, and adding 4 decoder layers outperforms MHF variants across 7 tasks.MHF does not consistently outperform Standard, especially on COPA, HellaSwag, and ReCoRD.
  • Multilingual vocabulary expansion: After expanding vocabulary from 32K to 48K, MHF remains similar or better than Standard at 1B and 3B without adding parameters.MHF (H4B16K) outperforms Standard on 12 and 13 out of 22 multilingual tasks at 1B and 3B, respectively.
  • Semantic representation: At equivalent parameter counts, MultiHashFormer consistently outperforms Standard models on Card-660 semantic-equivalence correlations.The advantage is particularly evident in the second-to-last decoder layer, where rare vocabulary items receive shared representational capacity.

6 Analysis

The analysis examines MultiHashFormer’s hash-signature design and hash configurations using a 1B-parameter model trained on 20B tokens. Multi-ID signatures prevent collision-related degradation, while H4B16K offers a strong parameter-efficiency and accuracy trade-off.

  • The analysis is conducted at the 1B-parameter scale with models trained on 20B tokens because of computational resource constraints.
  • Single vs. Multi-hash ID: Multi-ID signatures consistently outperform corresponding Single-ID signatures across H4B4K, H4B8K, and H4B16K configurations on LAMBADA.
  • Single vs. Multi-hash ID: 30.27% accuracy versus 4.29% shows H4B4K’s advantage over H1B4K, while H1B16K reaches only 14.30%; collisions severely degrade core capabilities.The results indicate that preventing collisions with Multi-ID signatures is more effective than merely increasing Single-ID bucket capacity.
  • Varying Hash Functions and Bucket Size: The best-performing hash configuration improves over the lowest by only 4% despite a tenfold parameter increase from 10M to 102M.H4B16K is selected as the primary configuration for the 1B and 3B scaling experiments.

7 Conclusion

MultiHashFormer uses multi-hash structures to bypass traditional vocabulary bottlenecks, improving core capabilities and rare-word representations while enabling parameter-free vocabulary expansion.

  • Contribution: MultiHashFormer leverages multi-hash structures to bypass traditional vocabulary bottlenecks.The paper introduces it as a generative framework.
  • Results: Empirical evaluation shows improvements in core capabilities and rare word representations.
  • Results: The framework enables seamless vocabulary expansion without requiring additional parameters.

Limitations · A Softmax Bottleneck · A.1 Preliminaries

The paper limits empirical evaluation to 100M, 1B, and 3B models and uses one training seed per configuration because larger-scale training and repeated runs exceed its academic resource constraints. It also formalizes the softmax bottleneck as a rank limitation: token distributions require a sufficiently large embedding dimension to be exactly represented.

  • Limitations: 100M, 1B, and 3B are the evaluated model scales, while experiments at 7B+ remain future work because of computational constraints.The 1B and 3B models were trained from scratch on 100B tokens within a standard academic budget.
  • Limitations: One seed per configuration was used because repeating 1B- and 3B-parameter pre-training for 100B tokens was computationally prohibitive.The paper reports consistent performance gains across both scales despite this limitation.
  • A.1 Preliminaries: The language-model softmax defines Pθ(w|c) by applying a softmax to a linear projection of the hidden state ht.The context representation and token embedding lie in a shared d-dimensional space, whose inner product defines the logit.
  • A.1 Preliminaries: Hθ contains contextual hidden states, Wθ contains vocabulary-token projection vectors, and A contains true-data log probabilities.Hθ is realized by a Transformer LM, whereas Wθ is a learned token-embedding lookup table.
  • A.1 Preliminaries: F(A) is the infinite set of logit matrices formed by adding a distinct scalar shift to each row of A.Its members recover the true distribution after row-wise softmax, and any two distinct members differ in rank by at most one.
  • A Softmax Bottleneck: Language models learn HθWθ⊤ to factorize a target A′ ∈ F(A), but the product rank is strictly bounded by the embedding dimension d.Exact recovery therefore requires d ≥ rank(A′); if d < rank(A′), no factorization can recover A′ regardless of the expressiveness of U.
  • A Softmax Bottleneck: Under a universal-approximator function family, exact recovery is possible if and only if d ≥ minA′∈F(A) rank(A′).The resulting softmax bottleneck states that if d < rank(A) −1, some contexts cannot match the true distribution, including when the language is infinite.

A.2 MULTIHASHFORMER as a Mitigation Strategy

MultiHashFormer projects representations into hash-signature coordinates and maps them back to vocabulary space through hash-specific matrices. Its multi-hash design raises the conditional-distribution rank bound from d to min(B, H × d), with the bound stable during inference and linked to gains on LAMBADA and HellaSwag.

  • Training: Representations are projected into coordinates of the hash signature using H localized parameter matrices assigned exclusively to coordinate bucket arrays.Each matrix is denoted W^(i)_o ∈ R^(d×B).
  • Training: Transition matrices π^(i) map hash-signature coordinates into the true vocabulary space, with each column of π^(i) being one-hot.The columns satisfy the supplied normalization condition P_B j,k = 1.
  • Expressiveness: rank(Â_MHF) ≤ min(B, H × d), compared with rank(Â_Standard) ≤ d, increasing MultiHashFormer’s rank upper bound.Here, H is the number of hash functions, B the buckets per function, and d the latent hash-state dimensionality.
  • Inference: During inference, excluding unassigned signatures leaves the rank upper bound invariant between training and inference.The row-wise partition function does not affect the final rank upper bound, although MultiHashFormer does not realize arbitrary rank.
  • Results: The elevated conditional-distribution rank drives performance gains on high-entropy reasoning tasks, including LAMBADA and HellaSwag.The passage attributes these gains to improved rank rather than to arbitrary-rank realization.

B Rare Word Examples from Card-660 · C Hyperparameters

The section examines rare Card-660 word pairs by comparing human similarity annotations with decoder-layer cosine similarities from the 1B Standard baseline and MultiHashFormer. MultiHashFormer assigns higher similarities to semantically equivalent pairs, including abbreviations, aliases, misspellings, and synonyms.

  • B Rare Word Examples from Card-660: Table 5 presents Card-660 word pairs with high human-annotated similarity scores normalized to [0, 1].
  • B Rare Word Examples from Card-660: The comparison uses normalized human annotation scores and cosine similarities from the second-to-last decoder layers.
  • B Rare Word Examples from Card-660: The evaluated representations come from the 1B Standard baseline and MultiHashFormer models.
  • B Rare Word Examples from Card-660: Tables 5 and 6 cover high-similarity pairs and low- or medium-similarity pairs, respectively.
  • B Rare Word Examples from Card-660: MultiHashFormer consistently assigns higher similarity scores than the Standard baseline to semantically equivalent word pairs.
  • B Rare Word Examples from Card-660: The semantically equivalent examples include abbreviations, aliases, misspellings, and synonyms.
  • B Rare Word Examples from Card-660: Table 6 defines a human annotation score of 1.00 as indicating semantic equivalence.

C.1 Hyperparameters for Pre-training · C.2 Hyperparameters for VE Continual-pretraining · D MultiHashFormer Abbrevations and Configurations

The appendix specifies pre-training hyperparameters, continual-pretraining hyperparameters, and detailed configurations with abbreviations for MultiHashFormer variants. Tables 7–9 organize these settings by model scale and variant.

  • C.1 Hyperparameters for Pre-training: Table 7 lists pre-training hyperparameters for each model scale.The supplied passage identifies the table but does not provide individual hyperparameter values.
  • C.1 Hyperparameters for Pre-training: The pre-training settings are organized separately for each model scale.This organization is stated in Table 7’s caption.
  • C.2 Hyperparameters for VE Continual-pretraining: Table 8 lists additional hyperparameters for continual-pretraining at each model scale.The supplied passage does not include the individual continual-pretraining settings.
  • C.2 Hyperparameters for VE Continual-pretraining: The continual-pretraining hyperparameters are presented by model scale.This organization is specified in Table 8’s caption.
  • D MultiHashFormer Abbrevations and Configurations: The appendix introduces the abbreviations used for the MultiHashFormer variants.The abbreviation reference is tied to the detailed configurations in Table 9.
  • D MultiHashFormer Abbrevations and Configurations: Table 9 presents detailed configurations of MultiHashFormer variants together with their abbreviations.The supplied passages identify the table’s purpose without giving the configurations themselves.
Loading 2606.28057v1…