Over-Tokenized Transformer: Vocabulary is Generally Worth Scaling

ListenFree Vocabulary: Why Input Tokens Scale and Output Tokens Don't11:53

Show notes

This week we dig into **Over-Tokenized Transformer** from ByteDance Seed, which decouples a language model's input and output vocabularies and finds they scale asymmetrically. Input vocabulary can be blown up to ten million entries at near-zero compute cost, yielding a clean log-linear scaling law on training loss — a 400M model matching a 1B baseline for free. We unpack the tiled n-gram hashing trick, the multi-token-prediction connection, and what a huge learned input lookup table might mean for image and video models. **Sources** - Over-Tokenized Transformer: Vocabulary is Generally Worth Scaling (Huang, Zhu, Wu, Zeng, Wang, Min, Zhou — ByteDance Seed)

Subscribe to the channel: https://podcast.lumalabs.link/27a25f51ea81d41a8253f46c6133a35e/feed.xml

TL;DR

Prior vocabulary-scaling work (e.g. Scaling Laws with Vocabulary: Larger Models Deserve Larger Vocabularies) treats the tokenizer’s input and output vocabulary as a single knob $V$ , tied by the softmax output layer. This paper decouples them and finds they scale asymmetrically: input vocabulary can be scaled up almost arbitrarily with near-zero compute cost, output vocabulary cannot. The mechanism: at inference/training, the input embedding is a sparse lookup (cost independent of $V$ ), while the output softmax scales linearly with $V$ . So the authors introduce Over-Encoding (OE) — hierarchical $n$ -gram input embeddings up to $10^7$ entries via tiled-matrix decomposition — combined with Over-Decoding (OD) via multi-token-prediction, together forming the Over-Tokenized Transformer (OT). Headline empirical claim: a 400M OT model matches a 1B baseline’s training loss at no additional compute, and there is a log-linear scaling law between input vocabulary size and training loss — exponential increases in $V_{in}$ produce linear decreases in loss, no observed saturation up to $10^7$ entries.

Key claims

Input vocabulary and output vocabulary scale differently. In CFG synthetic experiments and real LLM training, a larger input vocabulary consistently helps at every model size, while a larger output vocabulary only helps large models and hurts small ones [§3.1, Fig. 2]. Mechanistic explanation: input embedding widens the model’s representational capacity (a lookup), while output vocabulary determines supervision granularity (a fine-grained classification target that can overwhelm underfit small models).
Log-linear scaling law: training loss decreases linearly as input-vocabulary size increases exponentially, holding across model sizes from 151M to 1B and across the OLMo/OLMoE architectures [§4.2, Fig. 5]. Every doubling of the vocabulary tally yields ~0.015 nats of loss reduction, and the trend does not saturate at $V_{in} = 10^7$ .
A 400M OT-12.8M model matches the training loss of a 1B baseline at the same wall-clock cost [Fig. 1, §4.1]. Convergence acceleration on OLMo2-1B: 5.7× on training loss and 2.6–3.9× on five downstream tasks (MMLU-Var, Hellaswag, ARC-C, ARC-E, PIQA).
Over-Encoding via tiled hierarchical $n$ -gram hashing is the algorithmic core: input tokens are combined into $n$ -grams via a bijective index map, each $n$ -gram indexes a tiled sub-embedding, and the final input is the sum of 1-, 2-, …, $n$ -gram embeddings; slicing the embedding table along the hidden dimension into $k$ low-rank pieces improves further at fixed parameter budget [§3.2, Eqs. 3–5].
Modulus $m$ must be coprime with vocabulary base $V$ for the tiled hashing to work — deliberately introducing hash conflicts by picking $m$ as a multiple of $V$ collapses the gains [Table 4, §4.2].
Multi-token prediction (MTP) is an approximation of Over-Decoding — the authors interpret DeepSeek-V3’s MTP-DS scheme as OD, and show OD alone helps only large models; combined with OE (i.e. full OT), MTP-DS gains persist even at smaller scales, improving downstream by +1.3% over OE alone on OLMoE-1.3B [Table 5].
Engineering: sharded row-wise tensor-parallel embeddings replace FSDP for the huge over-encoded table, cutting the over-encoded model’s training-throughput penalty from 25% (FSDP + OOM risk at $V > 10^5$ ) to under 5%. Future direction: pipeline-parallel embedding lookup + CPU offload should reduce this further [§3.3].
Under MoE architectures, OE’s loss gains persist but downstream benefits diminish — OLMoE-1.3B (260M active / 1.3B total) with OE-12.8M shows loss −0.082 and downstream +0.014; OLMoE-7B (1.3B active / 7B total) shows loss −0.076 but downstream only +0.007 [Table 1]. Hypothesized cause: OE’s sparse embedding parameters overlap functionally with MoE’s sparse FFN parameters.

Method

Starting from a Context-Free Grammar synthetic setup (following Physics of LMs Part 1), the authors define $n$ -gram tokenizers whose vocabulary comprises all combinations of $n$ sequential characters, and show larger $n$ -gram tokenizers help large models but hurt small ones — as expected. Then they decouple input and output vocabularies: $n$ -gram-encoding models keep 1-gram output but use $n$ -gram input; $n$ -gram-decoding models do the reverse. The 3-gram encoding model helps at every scale; the 3-gram decoding model helps only large models. This motivates the design.

Over-Encoding at real LLM scale runs into the impracticality of an $n$ -gram table of size $V^n$ when $V \sim 10^5$ . The fix is two-part: (a) treat each $n$ -gram id as a $V$ -base number and reduce modulo a smaller tunable size $m$ , giving a tiled matrix parameterization; (b) slice the embedding along its hidden dimension into $k$ low-rank pieces, each looked up with a unique tile offset, then projected up. In practice they use hierarchical sums of 1-, 2-, and 3-gram embeddings with the 1-gram embedding tied to the original (unmodified) transformer input to keep tied output weights.

Over-Decoding is realized via DeepSeek-V3-style conditional-recursive MTP: an extra head predicts the next-next token given the model’s own prediction of the next token; loss weight 0.1. OT-12.8M is the union of OE-12.8M and MTP-DS.

Engineering: the over-encoded embedding table is row-sharded across data-parallel ranks; forward pass involves two all-to-alls to fetch remote embeddings, backward involves one. This is dramatically cheaper than FSDP’s all-gather-then-shard-gradient pattern when the embedding table dominates parameter count.

Experiments span OLMo2-151M/400M/1B (dense; 400B tokens for 151M/400M, 1T for 1B) and OLMoE-1.3B/7B (500B tokens each).

Results

OLMo2-1B + OE-12.8M vs baseline (1T tokens): loss improvement 0.12 → 0.14 across training; 5.7× training-loss acceleration; 3.2× MMLU-Var, 3.0× Hellaswag, 2.6× ARC-C, 3.1× ARC-E, 3.9× PIQA convergence [Fig. 4].
Vocabulary-size scaling ablation (OLMoE-1.3B, 50B tokens): log-linear loss decrease of ~0.015 per doubling of $m$ across the range $m \in \{2^{16}, 2^{17}, \ldots, 2^{24}\}$ , i.e. $\sim 10^7$ effective vocabulary entries at the top end [Fig. 5, Fig. 9].
OT-12.8M (OE + MTP-DS) vs baseline (OLMoE-1.3B, 500B tokens): loss 2.554 → 2.481 (−0.073); downstream avg 0.510 → 0.537 (+0.027). Vs OE alone: loss +0.009 worse but downstream +0.013 better — a favorable trade for benchmark performance [Table 5].
MoE architecture (OLMoE-7B, 500B tokens): OE-12.8M adds 26.3B parameters (3.7× the base 7B) but training throughput drops <5% and loss improves 2.305 → 2.229 (−0.076) [Table 1].
Embedding-hierarchy ablation: hierarchical 1+2+3-gram beats 1+2-gram beats 2-gram-only (which is worse than baseline, confirming the “hierarchical to disambiguate hash collisions” hypothesis) [Table 3].

Why it’s interesting

The three-paper thread this arrived in triangulates the vocabulary-scaling question from three angles: Scaling Laws with Vocabulary: Larger Models Deserve Larger Vocabularies fits a compute-optimal $V$ under a fixed BPE tokenizer with $V_{in} = V_{out}$ ; Compute Optimal Tokenization argues the unit of the Chinchilla scaling law was tokenizer-bound (bytes, not tokens); this paper argues the symmetry between input and output vocabulary is the load-bearing simplification prior work made — and it is wrong. The asymmetry is exploitable: input vocabulary is (almost) free, so scale it to $10^7$ ; output vocabulary is expensive, so cap it near the compute-optimal Chinchilla point and use MTP-style auxiliary predictions for extra supervision.

Directly connects to Parametric memory — the $10^7$ -entry $n$ -gram embedding table is a learned lookup memory attached to the transformer input, similar in spirit to Meta’s Memory Layers and the Hebbian-fact-store framing of MLPs are Hebbians: Constructing Efficient Fact-Storing MLPs for Transformers but placed at the input rather than in the FFN. Also connects to Byte-Level Language Models: this is the “large sparse input vocabulary” branch of the same design space that byte-level LMs approach from the “small dense input vocabulary” direction. And it prefigures Meta’s concurrent BLT work on $n$ -gram byte hashing at the input.