Over-Tokenized Transformer: Vocabulary is Generally Worth Scaling
Authors: Hongzhi Huang
Defa Zhu
Banggu Wu
Yutao Zeng
Ya Wang
Qiyang Min
zhou Xun
Venue: ICML 2025 poster (2025)
Keywords: LLM
Tokenization
Pre-training
Scaling-laws
Primary area: deep_learning->large_language_models
TL;DR: The input and output vocabulary is decoupled, where the input vocabularies is scaled up large, achieving performance of double-sized models without extra cost.

Abstract: Tokenization is a fundamental component of large language models (LLMs), yet its influence on model scaling and performance is not fully explored. In this paper, we introduce Over-Tokenized Transformers, a novel framework that decouples input and output vocabularies to improve language modeling performance. Specifically, our approach scales up input vocabularies to leverage multi-gram tokens. Through extensive experiments, we uncover a log-linear relationship between input vocabulary size and training loss, demonstrating that larger input vocabularies consistently enhance model performance, regardless of model size. Using a large input vocabulary, we achieve performance comparable to double-sized baselines with no additional cost. Our findings highlight the importance of tokenization in scaling laws and provide practical insight for tokenizer design, paving the way for more efficient and powerful LLMs.

Over-Tokenize Transformer: Vocabulary is Generally Worth Scaling
Hongzhi Huang' Defa Zhu' Banggu Wu
Yutao Zeng'
Ya Wang'
Qiyang Min
Xun Zhou'
Abstract
Tokenization is a fundamental component of large language models (LLMs), yet its influ- ence on model scaling and performance is not fully explored. In this paper, we introduce Over- Tokenized Transformers, novel framework that decouples input and output vocabularies to im- prove language modeling performance. Specifi- cally, our approach scales up input vocabularies to leverage mulli-gram tokens. Through extensive experiments, we uncover a log-linear relationship between input vocabulary size and training loss, demonstrating that larger input vocabularies con- sistently enhance model performance, regardless of model size. Using large input vocabulary, we achieve performance comparable to double- sized baselines with no additional cost. Our find- ings highlight the importance of tokenization in scaling laws and provide practical insight for tok- enizer design, paving the way for more efficient and powerful LLMs.
2.8
Loss
2.7
2.7
Mastan fastias
2.6
Baseder
2.6
IS Fasms
06:1 2M
addd Fasmn
0B-122M
2.5 13M
49M
61M
1.2M
12
Dense Punameters, (log scale)
Vocabulary Size (log scale)
Figure 1: Scaling trend for Over-Encoded models and base- lines OLMo2. We plot the loss with 400B tokens' train- ing. For over-encoding, input vocabulary size is extended from 0.1 to 1.2 and 12.8 million (12x and 128 larger than baseline), referred to as OE-1.2M and 02-12.8M. We observe OB-12.8M with 400M parameters matches the base- line with IB parameters.
smaller models. Thus, it is natural to consider decoupling the input and output vocabularies for separate investigations. Our research is fundamentally based on this idea.
1. Introduction
Starting with synthetic experiments on context-free gram- mar modeling, systematically analyze the effects of to- ken granularity and vocabulary size on models of varying scales. Firstly, it is revealed that larger tokenizers improve the performance of larger models while introducing chal- lenges for smaller ones, which is consistent with previous studies. Furthermore, once the input and output vocabulary is decoupled, we find that scaling up input vocabulary solely keeps improving model, while larger output vocabulary may be harmful to smaller models. This insight motivates the development of Over- Tokenized Transformers, which de- couple the encoding and decoding vocabularies to achieve greater flexibility and performance gains.
The rapid advancements in large language models (LLMs) have been driven by innovations in model architec- tures (Vaswani et al., 2017) and training paradigms (Radford et al., 2019; Brown et al., 2020). Moreover, with the guid- ance of scaling laws (Kaplan et al., 2020), models prove to become stronger with increasing number of parameters or training data. Tokenization, the process of converting raw text into discrete tokens as the input and output of the model, is recently found relevant to scaling laws, where larger models deserve larger vocabulary and achieve better performance under the same training cost (Tao et al., 2024). In fact, expanding the input vocabulary incurs almost no ad- ditional computational cost, whereas expanding the output vocabulary significantly increases the training overhead for
Specifically, we introduce EOeodignoin which uti- lizes large hierarchical n-gram input vocabulary. As shown in Figure 1, our method improves the model scalability by a significant margin. Increasing the input vocabulary size by 128x, our 400M model matches the training loss of a 1B baseline with no additional training cost (see left panel). More interestingly, we observe a strong log-line log-linear relationship between the input vocabulary size and model
Bytedance Seed. Correspondence to: Hongzhi Huang <huanghongzhi.51 @ beteedance.com>.
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Over-Tokenized Transformer: Vocabulary is Generally Worth Scaling
performance, i.e., exponentially increasing the input vocab- ulary size consistently results in a linear decrease in loss (see right panel). These findings represent new dimension in scaling laws and also indicate embedding parameters as a new scalable sparse dimension. Moreover, we propose the concept of Over- DecrrdDeodin()) which leverages larger output vocabulary to provide more aene-grained supervision. We typically treat multi-token prediction methods (Gloeckle et al., 2024; DeepSeek-Al et al., 2024) approximations of OD. Combining OE and OD together, we build Over- Tokenized Transformer, which shows greater potential than apply either OE or OD solely.
tation of the text sequence. Recent empirical studies have systematically investigated the relationship between vocab- ulary size and model performance. Tao et al. (2024) demon- strates that expanded vocabularies enhance both training efficiency and model performance, particularly in larger ar- chitectures. Building on these findings, we argue that vocab- ulary size research should separately consider embedding (input) and unembedding (ouiput). While embedding incurs only lookup costs, unembedding introduces computational costs that scale with vocabulary size. More importantly, we find that input and output vocabularies exhibit distinct scaling behaviors, underscoring the need for independent scaling strategies to optimize model design. Moreover, Liu et al. (2024) revisits n-gram language modeling at massive scale, proposing an oo-gram model trained on trillion tokens, which achieves competitive performance and can effectively complement neural LMs to reduce perplexity.
Although introducing a large amount of embedding parame- ters for OF, the training and inference cost barely increases, as embedding parameters are used in an extremely sparse manner. In practice, we propose efficient engineering solu- tions to mitigate the computational and memory challenges introduced by large vocabularies, resulting an additional training overhead less than 5%.
2.3. Multi-Token Prediction
Multi-Token Prediction (MTP) (Stem et al., 2018; Qi et al., 2020; Gloeckle et al., 2024) has advanced the field of next- token prediction through the introduction of auxiliary objec- tives for simultancous multi- prediction. This method- ology shares fundamental principles with our n-gram mod- eling framework, where multi-token prediction can be theo- retically formulated as an approximation of n--ram unem- bedding utilization (over-decoded models). In our work, we further compare the effectiveness of MTP and over-encoded models, demonstrating that the performance gains from MTP and over-encoded models are complementary and can be combined to achieve even greater improvements.
Through this work, we aim to bridge the gap between tok- enizer design and model scaling, positioning tokenization as critical factor in the continued evolution of large language models.
2. Related Work
2.1. Tokenization Design
Tokenization is a critical component in the development of large language models (LLMMs). Established methods such as Byte-Pair Encoding (BPE) (Sennrich, 2015) and Unigram Language Models (Kudo, 2018) have been widely adopted to create subword vocabularies that balance sequence length and vocabulary size. Recently, alternative paradigms have been proposed to address the computational inefficiencies of byte-level models (Xue et al., 2022; Clark et al., 2022; Tay et al., 2022; Yu et al., 2023). For instance, MegaByte (Yu et al., 2023) combines byte-level modeling with patching by first predicting patches and then predicting bytes within each patch, improving processing efficiency. However, its performance at scale remains inferior to that of tokenizer- based upproaches. Building on this concept, In this work, our findings suggest that applying n-gram embeddings on top of BPE expands the vocabulary size, improving model capability, while BLT (Pagnoni et al., 2024) also has the same finding on byte-level models.
3. Method
3.1. Insights from Synthetic Experiments
We initiate our research on tokenizers on a synthetic lan- guage modeling task to investigate their impact on model performance.
Following the experimental setup in the previous study (Allen-Zhu & Li, 2024), we employ a Context-Free Grammar (CFG) as the target language to generate se- quences composed of 3 distinct characters, with sequence lengths up to 729. With this setup, the ground-truth lan- guage distribution is completely known, enabling precise evaluation of the language models. We train GPT-2 mod- els (Radford et al., 2019) of various sizes on CFG-generated samples using next-token prediction loss and evaluate them based on the accuracy of meder--ennertte sequences, which measures the proportion of valid generations. Additional details regarding the experimental setup can be found in Appendix B.2.
2.2. Scaling Vocabulary
Huang et al. (2021) firstly explores recurrent neural net- works with scalable n-gram embedding table, where mod- ular hashing is used to control vocabulary size. Roy al. (2022) further augments the Transformer architecture with n-grams that are constructed from a discrete latent represen-
Our first experiment aims to compare the performance of
2

---

Over-Tokenizer Transformer: Vocabulary is Generally Worth Scaling
Generation Accuracy
Generation Accuracy
Vanilla GPT
Training
Inference
1,0
1.0
Input Tokens
B
C
D
0.8
0.5
Base Tokens
A
B
C
D
Transformer
F-gmm CPT 85M
spram
zromm
Target Tokens
B
C
D
GPT K5M
g-gom Ioputt KSM
gmam 2-4M
grom Ousut 85M
0.0
0.0 Training Step
Training
Inference
Training Step
2-3mu Encodad
Input Tokens
AR
DC
Figure 2: Performance comparison for models trained on CFG data. The left panel compares 1-gram and 3-gram tokenizers, showing that 3-gram improves larger (85M pa- rameters) models but harms smaller (2.4M parameters) ones. The right panel examines 3-gram usage in encoders and de- coders, revealing consistent gains with 3-gram encoders regardless of model size, while 3-gram decoders degrade performance in smaller models.
Base Tokens
B
Trans
Gram Decoded
Torget Tokens
BC
CD
Figure 3: Illustration of 2-gram encoding/decoding GPT. Note that 2-gram decoding only preserves the predicted next token though next is predicted, which keeps inference cost identical to the vanilla model.
language models using tokenizers with varying levels of granularity. A baseline tokenizer constructs a vocabulary using the three terminal characters defined by the CFG, tokenizing sentences Character-wisely. which we refer as gram tokenizer. We further define n-gram tokenizers, whose vocabulary comprises all 3" possible combinations of n sequential characters. We train both larger and smaller GPT- 2 models using 1-gram and 3-gram tokenizers, respectively.
To maintain comparable inference costs, the n-gram output model does not generate tokens simultaneously. Instead, it samples an n-gram prediction but preserves the next I token only, disregarding extra token predictions during inference. The results for n = 3 of the two variants are shown in the right panel of Figure 2. We find that the two models exhibit different behaviors. The 3-gram encoding model consis- tently enhances performance across all model sizes. How- ever, the 3-gram decoding model improves performance for larger models but degrades it for smaller ones.
As illustrated in the left panel of Figure 2, we observe that a larger tokenizer improves the performance larger mod- els but negatively impacts smaller models. Notably, larger tokenizers result in shorter training sequences, which signif- icantly reduces training cost. Thus, training larger models with 3-gram tokenizer not only reduces training costs but also enhances model performance. An intuitive insight is that larger models benefit from larger vocabularies, improv- ing both training efficiency and performance. This finding is also supported by previous studies (Tao et al., 2024).
We conclude that, when using large tokenizers, the large input vocabulary is always positive while the large output vocabulary can negative for smaller models. We hypoth- esize that the difference lies in their respective roles: the input embedding is responsible for encoding the context into feature embeddings, where larger vocabulary enhances the representational capacity of the feature mapping, thereby positively impacting the model. In contrast, the output vo- cabulary determines the granularity of the prediction task. A larger output vocabulary implies more fine-grained su- pervision signals, which can either be beneficial (c.g.. for large models prone to overfitting) burdensome (e.g., for smaller models suffering from severe underfitting). Mo- tivated by this observation, we extend our exploration to over-tokenized transformers in real-world natural language modeling.
To decouple the influences of enlarging input and output vocabularies, we separately introduce n-gram encoding and decoding models, as illustrated in Figure 3. To begin, the raw text is tokenized character-wisely via 1 I-gram tokenizer. In the n-gram encoding model, imput tokens are converted to n- n-gram tokens at the input layer, making a large input vocabulary of size 3", and the unembedding layer remains 1-gram, predicting next one character. In the n-gram de- coding model, the input remains 1-gram tokens while the target labels (i.e., the next token) converted to n-gram labels, resulting fine-grained classification head that pre- diets the conditional joint distribution of next tokens. Note that the training sequence length remains unchanged and matches the length produced by the 1-gram tokenizer for both variants.
3.2. Over-Tokenizne Tokenized Transformer
Above all, we use a standard natural language tokenizer as the base tokenizer. Then, the challenge arises: the base tokenizer has a vocabulary size V, which usually as large as 10 the n-gram vocabulary with a size of V
3

---

Over-Tokenized Transformer: Vocabulary is Generally Worth Scaling
becomes exceedingly large and impractical. To address this, we propose approximating the large emhedding table through a series of matrix decompositions.
embedding parameters and incurring only minimal addi- tional cost through i dense matrices W, E R xdmodel, this approach significantly enhances performance.
Given a sequence of input ids T2, de from the base tokenizer, we define the n-gram input token zf--) fol- lows:
Overall, the over-encoding process maps an input token to an embedding as follows:
OF (x) = EV 1EVxd(a (x( + Σ m + (x(
(5)
2; (-n) fI); 1.
(1)
where the I-gram embedding [Vxd(x(-1) is implemented consistently with the original Transformer to align with the tied weight design. Generally, m is set to value much larger than V, and the model performance is observed to improve consistently as increases.
where ( zn) is an index mapping function, and out-
of-range indices are padded with zero tokens, i.e., 2t
0, Vi [1,4] One intuitive design treats (21,-..; 2n) p-base number, defining fas as
2n) = Σ 2xp
(2)
Notably, for multiple embedders with m rows, minor adjust- ments (e.g., replacing m with m + 2) are made to ensure each embedder has a unique mapping. This increases the combinatorial capacity of the embedding: otherwise, the slice trick would make no difference. detailed pytorch- like implementation for OE can be found in Appendix A.
where 2 V ensures that f is a bijection. Typically, p is set to V to keep the range of f as compact as possible. Notably,
(-1) x
corresponds to the standard transformer input.
We also acknowledge a concurrent work, BLT (Pagnoni et al., 2024), which employs a similar n-gram hashing em- bedding strategy for byte-level tokens.
General n-gram Embedder. The key to designing flexible r--gam embedder module is to make the vocabulary size configurable. We achieve this efficiently using a simple tiled matrix parameterization approach. Specifically, the tiled matrix parameterization extends an m d embedding table into a V x d embedding table by tiling, where m configurable size. In practice, the lookup process is straightforward: input token (m())) is mapped by taking its modulus with respect to In summary, our n-gram embedder is formalized as
Over-DecodinggODD) Based on the conclusions from our CFG experiments, decoding additional tokens is only effec- tive for sufficiently large models. As matter of fact, previ- ous researches on Multi-Token Prediction (MTP) (Gloeckle et al., 2024) are typically approximations of over-decoding, and share the same conclusion that only large models benefit from future token predictions. Generally, MTP-like meth- ods are viewed as dee-ddeg in this paper. In addition, we explore other solutions for over-decoding in Appendix C for reference.
h E (n) % m)
where h is the output embedding. E mxd is the embed- ding matrix, and % the modulo operation. We denote this n-gram m x embedder as (x)x(((())) This n-gram hash- ing technique is commonly used in previous works (Huang et al., 2021; Roy et al., 2022).
-ver-Tokenized (ransformer(OT), Integrating over- encoding and over-decoding, we obtain over-tokenized transformer. Specifically, we focus on the conditional recur- sive form of MTP proposed in DeepSeek V3 (DeepSeek-A) et al., 2024), which we refer MTP-DS. In this formula- tion, MTP no longer predicts the next few tokens in parallel but instead predicts them sequentially. For the n-th head, the embedding of the next (n - 1) token is concatenated to the layer input as a condition for the next n-th token prediction.
Over-Encoding(OE), We find hierarchical encoding paradigm to be highly effective. Specifically, we compute the input embedding to the GPT model as the sum of 1-, 2-, n-gram embeddings. Additionally, we observe further benefits from using smaller embedding dimensions. An embedder x can be sliced into low-rank decomposed embedders, represented as:
Under MTP-DS architecture, over-encoding enhances the representation capacity of token embeddings and directly participates future token predictions. On the one hand, the future token prediction tasks become easier to learn. On the other hand, the over-encoding can be trained more suf- ficiently. With these advantages, the integration of the two methods yields greater benefits, even on relatively smaller models.
k mx (x(-x)) W.,
Emxdlk (2(-n)) = Σ E
(4)
where W, E 2 Xdmode! projects the embedding vector to match the model dimension. Using the same number of
4

---

Over-Tokenized Transformer: Vocabulary is Generally Worth Scaling
3.3. Engineering Challenges and Solutions
model, replacing the word embedding with over-encoding technique. The original tokenizer used in baseline models is preserved as the base tokenizer in our method. The exper- iments are run with engineering optimized implementation. We refer OF-m to over-encoded models with m x dmodel embedding parameters in total. Typically, we implement with ri = 3, m = 1.28 x 10", i.e. 1E-12.8M, and variate according to dmooel. making Amwddt 2 256.
The over-encoding constructs very large input vocabulary. In theory, the embeddings are sparsely accessed based on token ids, enlarging vocabulary should barely impact the training or inference cost. However, the large embedding parameters can place substantial memory pressure on GPUs. Furthermore, when parameter sharding strategies, such as FSDP (Zhao et al., 2023), are applied during training, the communication of these sparse parameters can severely de- grade training efficiency, further constraining the choice of m (the vocabulary size) to smaller values.
nk
Metrics. We report the average perplexities (PPL) and losses on the Leen-validat inniion dataset as the 'Eval PPL' or 'Eval Loss', along with the metries for zero-shot evaluation on downstream benchmarks. We observe signif- icant volatility in the zero-shot performance indicators for the datasets. For more reliable and consistent results, mainly concern five stable tasks in our analysis: MMLU- Var, Hellaswag, ARC-Challenge, ARC-Easy and PIQA. De- tailed descriptions on these tasks and more comprehensive evaluations can be found in Appendix B.
To mitigate this issue, we recommend using tensor paral- lelism specifically for the over-encoding embedding layer to reduce communication overhead. The embedding table row-wise sharded across all data-parallel (DP) ranks. For given imput, the token is sent the corresponding DP rank that holds its embedding, queried for the embedding vector, and then the resulting embedding is sent back to the original DP rank. This process involves two all-to-all all communications during the forward pass and one all-to-all communication during the backward pass, resulting in a total communication volume significantly lower than that of FSDP.
4.1. Over-Encoding Scaling Trend
Dense Models We follow the experimental setup de- scribed in OLMo2 (OLMo et al., 2024), which is currently the sfate-of-the-art fully open model. We maintain most of the training configurations, but modify the architecture to obtain models with 151M, 400M and IB dense param- eters, which is denoted by OL 151M. OLMo2-400M and OLMo2-1B, respectively. We train OLMo2-15 M and MLMo2-400M models with 400B tokens, and OLMo2-1B with IT tokens. In addition to OE- models, we also run experiments for OE- 1. 1.2M to offer rough scaling trend on vocabulary size.
We implement this optimization and find that training over-encoded model with m 107 on FSDP reduces throughput by less than 5%. In contrast, without this op- timization, FSDP experiences a 25% slowdown and eas- ily runs out of memory for vocabulary sizes exceeding m = x 10
We believe that the current implementation still does not represent the limit of over-encoding performance optimiza- tion. Its greatest advantage is that the vocabulary input is decoupled from the model architecture. This decoupling allows the embedding lookup for the next micro-batch to be performed in advance. For example, we can design a dedicated embedding lookup stage a sipeline-paralle training framework, which overlaps the communication re- quired for embedding lookups with the transformer forward of the current micro-batch. This strategy would maintain training throughput without any performance degradation. Additionally, under this approach, the over-encoding param- eters could be offloaded to the CPU, completely alleviating GPU memory pressure. Notably, similar training frame- works have already been implemented (Fang et al., 2022; Li al., 2023). Over-Encoding could leverage these designs to improve model performance with minimal additional cost.
The result is ploted in Figure 1. From comparisons across model scales, OE models hold consistent improvements from baseline models. Specifically, the OE- 12.8M model achieves comparable performance to a baseline model that is 2.5 times larger in model scale (comparing the 400M OE model with the 1B baseline model). Moreover, the vocabu- lary size of 0F-12.8M, OE-1.2M, and the baseline model (vocabulary size V = 100278) exhibits exponential growth, while their scaling curves maintain approximately equal spacing. This observation suggests a log-linear relationship between vocabulary size and model performance, which we further validate in the ablation studies.
We present the training dynamics for OLMo2- IB models in Figure 4. Compared to the baseline model, OE demon- strates consistently increasing performance gains, with an improvement of 0.12 at 400B tokens that expands to 0. at IT tokens. From the perspective of convergence accel- eration, training loss achieves a remarkable 5.7 speedup. Furthermore, in terms of downstream evaluation, OE ex- hibits substantial acceleration, achieving 3.2x, 3.0x, 2.6x,
4. Experiments
Implementation. Our experiments focus on large lan- guage modeling tasks and basically follow OLMo series works. We maintain the training configuration of baseline
5

---

Over- Tokenized Transformer: Vocabulary is Generally Worth Scaling
Training Loss
MMLU-Var
Hellaswag
Bascine OE-128M
0.66
0.60
3.0
11.14
0.55
0.50
28
0.45
0.30
26-
Baselin:
0.40
Bandin:
OE 12.0
OE-12.5M
0.38
1000
500
1030
Training (B))
Training Tokens(B)) (B)
Training Tokcns((B)
ARC-Challenge
ARC-Easy
PIQA
0.400
0.70
0.375
0.74
0.150
0.72
0.125
0.70
0.309
0.275
0.68
Baedinc
Baszlin:
Baadins
0B:12KM
0.350
06-12.0M
0.66
0B-124M
Training (Bk)
Training Tokens(B)
Training Tokens(BB)
Figure 4: Training curves for OE- 12.8M and baseline model on OLMo2- IB. The metries are smoothed via exponential moving average with weight 0.99 for loss and 0.9 for downstream tasks. We observe significant convergence acceleration for the OE model: 5.7x on loss, 3.2x on MMLU-Var, 3.0x Hellaswag, 2.6x on ARC-Challenge. 3.1x on ARC-Easy and 3.9x on PIQA.
Table 1: Performance of Over-Encoding on MoE architec- ture with 500B tokens' training. The column 'Emb. P.' represents 'Embedding Parameters', 'Downstream' stands for the average of MMLU-Var, Hellaswag, ARC-Challenge, ARC-Easy, and PIQA. For '+OE' rows, we provide metric difference with blue labels.
under the MoE architecture.
We follow the experimental setup described by OL- MoE (Muennighoff et al., 2024). the experiments, OLMoE-1.3B refers a model with 260M active parame- ters and total of 1.3B parameters, while OLMoE-7B refers to models with 1.3B active parameters and a total of 7B pa- rameters. In this setting, the base tokenizer has vocabulary size V = 50280, and we train 500B tokens for all these models.
Model
# Emb. P.
Loss.
Downstream
OLMoE-1.3B
51M
2.554
0.510
+0E-12.8M
IB.1B
2.472 -0.082
0.524 +0.014
The results are shown in Table 1. We first compare the train- ing loss. At two different model scales, OB-12.8M achieves approximately the same improvement in loss compared to the baseline, despite decreases in the proportion of embed- ding parameters as the model scales up (i.e., 10x dense parameters for OLMoE-1.3B and 3.7x for OLMoE-7B). However, in terms of downstream evaluation metrics, the performance improvement of OE diminishes. We hypoth- esize that this reduction related the sparse parameters utilized in the MoE architecture, which may overlap with the benefits provided by sparse embedding parameters.
OLMoE-7B
102M
2.305
0.601
+OF-12.8M
26.3B
2.229 .0.076
0.608 +0.007
3.1 x and 3.9x speedups on Mar,-Var, Hellaswag, ARC- Challenge, ARC-Easy and PIQA, respectively. thorough evaluation is ploted in Appendix B.3.
MoE Models Sparse Mixture-of -fxture-of-Expertss (MoE) mod- els (Shazeer al., 2017) have also achieved great success in recent years. These models aim to introduce sparse Feed- Forward Network (FFN) modules, enabling the addition of a large number of sparse parameters to improve model performance while keeping the same number of activated parameters, making the training and inference costs un- changed. Similarly, we evaluate the effectiveness of OE
4.2. Ablation Study
We conduct ablation study basing on the setup of OLMoE- 1.3B. To save computational resources, for ablation variants that are non-promising, we only train for 50B tokens. Other-
6

---

Over-Tokenized Transformer: Vocabulary is Generally Worth Scaling
Table 2: Ablation study on different input vocabulary designs. The downstream tasks follow the eval settings in OLMoE, where MMLU-V stands for MMLU-Van Var, HS for Hellaswag, ARC-C for ARC-Challenge and ARC-E for ARC-Easy. All models are trained with 500B tokens.
Train
Eval
Downstream
Id Model
Loss
PPL1
Loss
PPL1
MMLU-V1
HSt
ARC-C1
ARC-E1
PIQAT
OLMoE-1.3B
2.554
12.864
2.924
18.625
0.327
0.553
0.325
0.622
0.727
2 +E3.2MXd (xl-22)
2.511
12.319
2.887
17.944
0.340
0.569
0.351
0.656
0.734
3
+EE.AMX &f 2))
2.507
12.268
2.882
17.851
0.330
0.573
0.341
0.648
0.731
4
+E (xf-22)
2.503
12.221
2.877
17.754
0.337
0.575
0.345
0.651
0.740
5
+E3.2Mxd|4(11
22)
2.503
12.226
2.876
17.736
0.328
0.575
0.337
0.653
0.734
2.2Mx $12 (1((
6
+iE((23)
2.495
12.127
2.870
17.638
0.340
0.578
0.330
0.636
0.738
+E 12.8Mxx
(x (21)
2.493
12.100
2.881
17.832
0.334
0.569
0.343
0.643
0.730
12.8Mx 412 (x((1))
8
+ *EiE(2.))
2.472
11.854
2.862
17.494
0.342
0.577
0.329
0.645
0.728
wise, we train for 500B tokens to obtain solid conclusions.
Fitted
X
Observed Dala
Vocabulary Size Scaling. We first analyze the scaling behavior of over-encoding based. Specifically, we use the simplest over-encoding setup with fixed n = 2 and & = 1, while varying the value of m. The size of m ranges from 20K to 12.8M. We train on 500B tokens and evaluate the model performance. As shown in the figure, the experimen- tal results reveal logarithmic linear relationship between the training loss and for every 4x increase in m, the training loss decreases by 0.015. Finally, we extracted the loss at 500B tokens and plotted the scaling curve shown in Figure 5. Here, the input vocabulary size is defined as the sum of the sizes of the I-gram and 2-gram vocabularies, i.c., V + m. It is worth noting that the model needs to be suffi- ciently trained to capture these patterns. Figure 9 shows the training loss and loss diff curves in the vocabulary size scal- ing experiments. The larger vocabulary size requires longer training until the gains converge. And the performance gap is stably held after sufficient tokens' training.
Loss
2.53
2.51
2.50
2.49
10'
10"
10"
Vocabulary Size (log scale)
Figure 5: Log-linear relationship is observed between vo- cabulary size m and training loss L, i.e. L = 2.6754 0.0256 x log10 m. The values are collected with 500B to- kens' training on OLMoE-1.31 1.3B models.
reduced memory access: configuration 4 accesses 2d embedding parameters while configuration accesses only 1.5dmmotel per token. Moreover, we validate the benefits of enlarging n from 2 to 3 by comparing C-5 and C-6. With longer-range dependencies introduced, C-6 further improves performance. Lastly, these tricks are then applied on a larger vocabulary with m = 12.8M (comparing C-7 and C-8). We observe even larger gains comparing experiments with = 3.2M. Note that C-6 and C-8 meets our default OE implementation, i.e., OB-3.2M and OF-12.8M respectively, as described in (5).
What's Good for OE, We conducted extensive ablation studies on different configurations for the over-encoding. To ensure fairness, all configurations have the same number of embedding parameters. The results are shown in the Table 2. For simplification, we denote C-i as configuration in the table.
We first validate that slicing the embedding table along the d dimension yields further gains (comparing C-2, C-4, and C-5). Then, C-3 is constructed as a baseline, where we keep using one embedding table but scale up m and scale down d. Such configuration also improves baseline but underperforms C-4 and C-5. We attribute this to the
What's Bad for OE. We also identify certain configura- tions that result in significant performance degradation and should avoid in practice. For this part of the experiments, due to the obvious performance drop, we report results af-
7

---

Over-Tokenized Transformer: Vocabulary is Generally Worth Scaling
Table 3: Ablation study for the hierarchical design of over- encoding. The symbol 'v on the n n-gram column denotes n-gram token (- is adopted. The experiments are con- ducted with m 3. 3.2M, and the metrics are reported after training on 50B tokens.
Table 5: MTP Experiments on DLMoE-1.3BD The loss refers to the next one token prediction loss for MTP methods. Metric difference that improves baseline are marked blue while degrations are marked red.
Model
Loss
Eval Loss
Downstream?
1-Gram
2-Gram
3-Gram
Loss
PPL
baseline
2.554
2.924
0,510
x
x
2.714
15.094
+MTP
2.556 +0.002
2.925
+0.001
0.508 -0.002
x
/
x
2.785
16,205
+MTP-DS
2.555 +0.001
2.926
+0.002
0.511 +0.001
/
/
x
2.678
14.555
OE-12.8M
2.472
2.862
0.524
OT-12.8M
2.481 +0.009
2.869
+0.007
0.537 +0.013
x
4
2.670
14.447
/
x
/
2.684
14.642
/
/
/
4
2.667
14.394
4.3. Over- Tokenize Transformer
In this section, we verify the effectiveness of over-tokenized transformer. We conduct the experiments on OL.MoE-1.3B with 500B tokens' training. As MTP is less efficient for smaller models, implementation has only extra head predicting the next 2 token, and set the weight 0.1 for future token loss. Then, the over-tokenized transformer is con- structed, combining OE-12.8M with MTP-DS, which we refer as OT-
Table 4: Ablation study on hashing conflicts. Note the experiments are kept roughly the same vocabulary size, i.e. 64V = 3.218M. The metries reported after training with 50B tokens.
Model
Loss
PPL.
Eval Loss
Eval PPL.
Results are shown in Table 5. Limited by model capac- ity, MTP shows no improvement, well as its stronger verison MTP-DS. However, with over-encoding plugged, MTP-DS presents greater power. OT further improves the downstream metric by 1. 3% compared to OE, although it slightly sacrifices the loss gains of OE The detailed metrics are presented in Appendix B.4.
baseline
2.714
15.094
3.094
22,060
+B64Vx0 xd
2.702
14.892
3.077
21.710
3x
2.678
14.555
3.054
21.202
ter training on only 50B tokens, and simply use loss and perplexity evaluation metrics.
4.4. Speed Analysis
We analyze training and inference speed for over-encoding in this section. To illustrate training efficiency, we show training throughputs in OLMoE experiments Table where we run OE and baseline under the same hardware configurations. OE in OLMo yields more overhead as we did not carefully optimize engineering configurations.
First, validate the importance of hierarchical qulti-gram tokens. As shown in Table 3, removing the 1-gram vo- cabulary and using only the 2-gram vocabulary leads to a significant performance drop. This may be due to con- flicts in the lookup results the 2-gram table when I-gram information is absent, making it difficult for the model to disambiguate the current semantics. On the other hand, skip- ping the 2-gram tokens and using only 1-gram and 3-gram tokens still shows gains over the baseline but underperforms the proposed model using 1-, 2-, and 3-gram tokens to- gether. Overall, we hypothesize that the model benefits from hierarchical encoding to handle conflicting entries in the embedding table, thereby accurately resolving seman- tics.
OLMoE-1.3B
OLMoE-7B
Hardware
32 A100
64xA100
Baseline
1,211
0.494
+OE 12.8M
1.155 44.3%
0.453 833/%
Table 6:
Training throughputs for OE and baseline. We report average tokens per second in millions.
Another supporting observation is that when we deliberately introduce more encoding conflicts (by setting m to be an exact multiple of V), the gains of over-encoding are signifi- cantly reduced, as shown in Table 4. This observation also suggests that m should set to a value coprime with V to avoid such degeneration.
Theoretically, the additional flops introduced by OE is less than 0.5% (as shown in the table below), as demonstrated in Table 8. The overhead measured in the experiments should mainly be introduced by the all-to-all communication (which is proportional the size of data parallel). And these
8

---

Over-Tokenized Transformer: Vocabulary is Generally Worth Scaling
Dense-1B
MoE-1B/7B
Dense-7B
Batch Size
Phase
Baseline
12.12.8M
Baseline
O 12.-1
Baseline
OE-12.8M
Prefill
20728.7
19446.4
6303,8
6189.0
6571.0
6499.9
Decode
136.2
126.6
28.2
27.9
65.1
63.3
Prefill
36907.5
35902.6
22297.3
22292.1
8
Decode
797.2
760.9
184.9
181.0
232.1
228.6
64
Decode
1422.1
1407.4
860.3
826.7
Table 7: Inference speed for OE and baseline. The sequence length is fixed to 2048, and we report tokens per second for prefilling and decoding separately under various batchsizes. Settings that cause OOM are leave blank.
OLMoE-1.3B
OLMoF-7B
the effectiveness our methods, showcasing significant gains in model performance. Notably, we demonstrated strong log-linear relationship between input vocabulary size and training loss, highlighting new dimension in the scaling laws of LLMs. These results emphasize the impor- tance of tokenizer design as a key driver of advancements in language modeling.
baseline
0.5409
2.3578
+OE 12.8M
0.5430 +0.38%
2.3662 +0.35%
Table 8: GFLOPs per token in the forward pass.
In summary, this work bridges the gap between tokenizer de- sign and model scaling, positioning tokenization critical factor in the development of next-generation language mod- Trans-
communication overheads can be further optimized through engineering techniques in the future.
For inference efficiency, we test the prefill and de- coding throughput on a single A100 GPU using the tranns formers library. For the OE models, the additional embedding parameters are offloaded to the CPU, incurring no GPU memory overhead. The numeric results shown in Table 7. The impact of OE on inference throughput is negligible, especially for larger models or larger batch sizes. In contrast, the sparse parameters introduced by MoE face severe memory access bottlenecks during inference. A very large batch size required for the MoE model to achieve the same throughput as a dense model with the same activated parameters. Considering that the model inference might be carried out on more cost-effective but less computationally powerful inference GPUs, the relative overhead of OE could be further reduced.
els. We believe that the proposed formers framework and the insights derived from our study will inspire further research into tokenization strategies and their role in scaling L.MMs efficiently and effectively.
Acknowledgements
This research was conducted at ByteDDance Inc. We are grateful for the suggestions and discussions from Jundong Zhou, Zihao Huang, Yu Bao, Yike Yuan, Sijun Zhang and other colleagues at ByteDance Seed.
Impact Statement
This paper presents work whose goal is to advance the field of Machine Learning. There are many potential societal consequences of our work, none which we feel must be specifically highlighted here.
5. Conclusion
In this work, have explored over-tokenized transformer for language modeling. By systematically analyzing the im- pact of token granularity and vocabulary size across models of varying scales, we uncover an important scaling phenom- ena that inspires tokenizer design. Our findings reveal that larger input vocabularies consistently enhance model perfor- mance, no matter model scales, while larger output vocabu- lary can be harmful and difficult to learn for smaller models. These insights have significant implications for the contin- ued scaling of LLMs. With such inspirations, we introduce over-encoding technique that scales up the input vocabulary via multi-gram token embeddings. Moreover, we develop over-tokenized transformer combining over-encoding and multi-token prediction. Extensive experiments validated
References
Allen-Zhu, Z. and Li, Y. Physics language models: Part 1, learning hierarchical language structures, 2024. URL https: /ttp:://axxiv.ie/i wttp:/wwwwwr////////.../// 13673.
Bisk, Y., Zellers, R., Gao, J., Choi, Y., et al. Piqa: Reasoning about physical commonsense in natural language. In Pro- ceedings of the AAAI conference on artificial intelligence, volume 34, 2020.
Brown, T., Mann, B., Ryder, N., Subbiah, M., Kaplan, J. D., Dhariwal, P., Neelakantan, A., Shyam, P., Sastry, G., Askell, A., Agarwal, S., Herbert-Vors A., Krueger, G.,
9

---

Huang, W. R., Sainath, T. N., Peyser, C., Kumar, S., Rybach, Over-Tokenized Transformer: Vocabulary is Generally Worth Scaling
Henighan, T., Child, R., Ramesh, A., Ziegler, D., Wu, J., Winter, C.,, Hesse, C., Chen, M., Sigler, E.,, Litwin, M., Gray, S., Chess, B., Clark, J., Berner, C., McCandlish, S., Radford, A., Sutskever, I., and Amodei, D. Language models are few-shot learners. In Larochelle, H., Ranzato, M., Hadsell, R., Balcan, M., and Lin, H. (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 1877-1901. Curran Associates, Inc., 2020. URL httpt::t//......... https::/proceeddnggg neurips. oc pttpppee_fflleepppppp///////////
Z., Zhu, Z., Liu, Z., Li, Z., Xie, Z., Song, Z., Gao, Z., and Pan, Z. Deepseek-v3 technical report, 2024, URL https:
Fang, J., Zhang. G., Han, J., Li, S., Bian, Z., Li, Y., Liu, J., and You, Y. A frequency-aware software cache for large recommendation system embeddings. arXiv preprint arXi::2208.0532/, 2022.
Gloeckle, F., Idrissi, B. Y., Roziere, B., Lapez-Paz, D., and Synnaeve, G. Better & faster large language models via multi-token prediction.
1457c0d6bfccb496555 (tt.eerceb44641118bbbbb8 620 pdf.
Forty-first International Conference on Machine Learning, 2024. URL https: //openreview net ftr.m/orummmmmm/ weerrummid-paan perrddddpEEeeeeeD
Clark, J. H., Garrette, D., Turc, I., and Wieting, J. Canine: Pre-training an efficient tokenization-free encoder for language representation. Transactions of the Association for Computational Linguistics, 10:73-91, 2022.
Hendrycks, D., Burns, C., Basart, S., Zou, A., Mazeika, M., Song, D., and Steinhardt, J. Measuring massive multitask language understanding. Proceedings of the International Conference on Learning Representations (ICLR), 2021.
Clark, P., Cowhey, I., Etzioni, O., Khot, T., Sabharwal, A., Schoenick, C., and Tafjord, O. Think you have solved question answering? try are, the ai2 reasoning challenge. arXiv: 2018.
D., and Strohman, T. Bookup-table recurrent language models for long tail speech recognition. In Interspeech 2021, pp. 2002-2006, 2021. doi: 10.214437/mtesspeechh 2021-340.
DeepSeek-AI, Liu, A., Feng, B., Xue, B., Wang, B., Wu, B., Lu, C., Zhao, C., Deng, C., Zhang, C., Ruan, C., Dai, D., Guo, D., Yang, D., Chen, D., Ji, D., Li, E.,, Lin, F., Dai, F. Luo, F., Hao, G., Chen, G., Li, G., Zhang, H., Bao, H. Xu, H., Wang, H., Zhang, H., Ding, H., Xin, H., Gao, H., Li, H., Qu, H., Cai, J. L.., Liang. J., Guo, J., Ni, J., Li, J. Wang, J., Chen, J., Chen, J., Yuan, J., Qiu, J., Li, J., Song, J.. Dong, K., Hu, K., Gao, K., Guan, K., Huang, K., Yu, K., Wang. L., Zhang, L., Xu, L., Xia, L., Zhao, L., Wang, L.,, Zhang, L.,, Li, M., Wang, M., Zhang, M., Zhang, M., Tang, M., Li, M., Tian, N., Huang, P., Wang, P. Zhang, P., Wang, Q., Thu, Q., Chen, Q., Du, Q. Chen, J. Jin R. L., Ge, R., Zhang, R., Pan, R., Wang, R., Xu, R., Zhang, R., Chen, R., Li, S. S., Lu, S., Zhou, S., Chen, S. Wu, S., Ye, S., Ye, S., Ma, S., Wang, S., Zhou, S., Yu, S., Zhou, S., Pan, S., Wang. T., Yun, T., Pei, T., Sun, T., Xiao, W. L.,, Zeng, W., Zhao, W., An, W., Liu, W., Liang, W., Gao. W. Yu. W. Zhang, W., Li. X. Q., Jin, X., Wang, X., Bi, X., Liu, X., Wang, X., Shen, X., Chen, X., Zhang. X., Chen, X., Nie, X., Sun, X., Wang, X., Cheng, X., Liu, X., Xie, X., Liu, X., Yu, X., Song, X., Shan, X., Zhou, X., Yang, X., Li, X., Su, X., Lin, X., Li, Y. K., Wang, Y. Q. Wei, Y. X., Zhu, Y. X., Zhang, Y., Xu, Y., Xu, Y., Huang, Y., Li, Y., Zhao, Y., Sun, Y., Li, Y., Wang, Y. Yu, Y., Zheng. Y., Zhang. Y., Shi, Y., Xiong, Y., He, Y., Tang, Y., Piao, Y., Wang, Y., Tan, Y., Ma, Y., Liu, Y., Guo, Y., Wu, Y., Ou, Y., Zhu, Y., Wang, Y., Gong, Y., Zou, Y., He, Y., Zha, Y., Xiong, Y., Ma, Y., Yan, Y. Luo, Y., You, Y., Liu, Y., Zhou, Y., WU, Z. F., Ren, Z. Z., Ren, Z., Sha, Z., Fu, Z., Xu, Z., Huang, Z., Zhang, Z., Xie, Z., Zhang, Z., Hao, Z., Gou, Z., Ma. Z.,
Kaplan, J., McCandlish, S., Henighan, T., Brown, T. B., Chess, B., Child, R., Gray, S., Radford, A., Wu, J., and Amodei, D. Scaling laws for neural language models. arXiv preprint arXiv:2001.0836/ 2020.
Kudo, T. Subword regularization: Improving neural net- work translation models with multiple subword candi- dates. arXiv preprint arXiv: 10959, 2018.
Li, S., Liu, H., Bian, Z., Fang. J., Huang. H., Liu, Y., Wang, B., and You, Y. Colossal-ai: A unified deep learning sys- tem for large-scale parallel training. In Proceedings of the 52nd International Conference Parallel Processing, ICPP '23, pp. 766-775, New York, NY, USA. 2023, Asso- ciation for Computing Machinery. ISBN 9798400708435. doi: 10. 00,114///50553333055511 URL ht /ooi. 3605613.
org / /1/ 114111145331
Liu, J., Min, S., Zettlemoyer, I.., Choi, Y., and Hajishirzi, H. Infini-gram: Scaling unbounded n-gram language models to trillion tokens. In First Conference on Language Modeling. 2024. URL https: openreview .nt.t/wiwweeeeeee............... forum? d= 2AyMMMMM..
Muennighoff, N., Soldaini, L., Groeneveld, D., Lo, K., Mor- rison, J., Min, S., Shi, W., Walsh, P., Tafjord, O., Lambert, N., Gu, Y., Arora, S., Bhagia, A., Schwenk, D., Wadden, D.,, Wettig, A., Hui, B., Dettmers, T., Kiela, D., Farhadi, A., Smith, N. A., Koh, P. W., Singh, A., and Hajishirzi, H.
Olmoe: Open mnixture-of-experee language models, 2024. URL www.t:tpp///........ /awxiv www.iivorrro worg/orgsss..................... abwpaaas/999/// 020.0....00.... 02060.
Yan, Z.,, Shao, Zz, Xu, Z., Wu, Z., Zhang, Z., Li, Z., Gu,
10

---

Over-Tokenized Transformer: Vocabulary is Generally Worth Scaling
OLMo, T., Walsh, P., Soldaini, L.., Groeneveld, D., Lo, K., Arora, S., Bhagia, A., Gu, Y., Huang, S., Jordan, M., Lambert, N., Schwenk, D., Tafjord, O., Anderson, T., Atkinson, D., Brahman, F., Clark, C., Dasigi, P., Dziri, N., Guerquin, M., Ivison, H., Koh, P. W., Liu, J., Malik, S., Merrill, W., Miranda, L. J. V., Morrison, J., Murray, T., Nam, C., Pyatkin, V., Rangapur, A., Schmitz, M., Skjonsberg, S., Wadden, D., Wilhelm, C.. Wilson, M., Zettlemoyer, L.., Farhadi, A., Smith, N. A., and Hajishirzi, H. 2 olmo 2 furious, 2024. URL https: /arxiv.. org/ /bsg/bb//// 2501 00656.
Fast character transformers via gradient- based subword tokenization. In International Conference Learning Representations, 2022. URL https:/ openreview net forum Sirrrumiid--tttn110G1
D. Charformer:
Vaswani, A., Shazeer, N., Parmar, N., Uszkoreit, Jones, L.., Gomez, A. N., Kaiser, L. u., and Polosukhin, I. Attention is all you need. In Guyon, I., Luxburg, U. V., Bengio, S., Wallach, H., Fergus, R., Vishwanathan, S., and Garnett, R. (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017. URL httpss:/prooeediingg.. neurip... cc cc/paper__iiees/pppee////// 3 pdf.
Pagnoni, A., Pasunuru, R., Rodriguez, P., Nguyen, J., Muller, B., Li, M., Zhou, C., Yu, L., Weston, J., Zettle- moyer, L., Ghosh, G., Lewis, M., Holtzman, A., and Iyer, S. Byte latent transformer: Patches scale bet- ter than tokens, 2024. URL peatps://arxiv..
Xue, L., Barua, A., Constant, N., Al-Rfou, R., Narang, S., Kale, M., Roberts, A., and Raffel, C. ByT5: To- wards token-free future with pre-trained byte-to-byte models. Transactions of the Association for Com- putational Linguistics, 10:291-306, 2022. doi: 10. I 1162/tal a.04611. URL o org/2022. tacl-1...c111111
Qi, W. Yan, Y., Gong, Y., Liu, D., Duan, N., Chen, J., Zhang, R., and Zhou, M. Prophetnet: Predicting future In Find-
n n-gram for ings of the Association for Computational Linguistics: EMNLP 2020, pp. 2401-2416 2020.
Yu, L., Simig. D., Flaherty, C., Aghajanyan, A., Zettlemoyer, I.., and Lewis, M. Megabyte: Predicting million- byte se- quences with multiscale transformers. Advances in Neu- ral Information Processing Systems, 36:78808-78823, 2023.
Radford, A., Wu, J., Child, R., Luan, D., Amodei, D., and Sutskever, I. Language models are unsupervised multitask learners. 2019.
Roy, A.. Anil, R., Lai, G., Lee, B., Zhao, J., Zhang, S., Wang, S., Zhang, Y., Wu, S., Swavely, R., Tao, Yu, Dao, P., Fifty, C., Chen, Z., and Wu, Y. N-grammer: Augmenting transformers with latent g-grams, 2022. URL https: //arxiv. org/ abs 2207.227.0000 06366.
Zellers, R., Holtzman, A., Bisk, Y., Farhadi, A., and Choi, Y. Hellaswag: Can machine really finish your sentence? arXiv preprint 1905:
2019.
Zhao, Y., Gu, A., Varma, R., Luo, L., Huang, C.-C,, M., Wright, L., Shojanazeri, H., Ott, M., Shleifer, S., et al. Pytorch fsdp: Experiences on scaling fully sharded data parallel. Proceedings of the VLDB Endowment, 16(12):
Sennrich, R. Neural machine translation of rare words with subword units. arXiv preprint 1rXxvv:508.0775 2015.
Shazeer, N., Mirhoseini, A., Maziarz, K., Davis, A., Le, Q., Hinton, G., and Dean, J. Outrageously large neural networks: The sparsely-gate mixture-of-eexpers layer. In International Conference on Learning Representations, 2017. URL https:////// http://ppwewweeeeeeeoeoee for/oommmm id-BlckMDqlg.
2023.
Stern, M., Shazeer, N., and Uszkoreit, J. Blockwise parallel decoding for deep autoregressive models. In Proceedings of the 32nd International Conference on Neural Informa- tion Processing Systems, pp. 10107-10116, 2018.
Tao, C., Liu, Q., Dou, L., Muennighoff, N., Wan. Z., Luo, P., Lin, M., and Wong, N. Scaling laws with vocabulary: Larger models deserve larger vocabularies. arXiv preprint 240i 13623, 2024.
Tay, Y., Tran, V. Q., Ruder, S., Gupta, J., Chung, H. W., Bahri, D., Qin, Z., Baumgartner, S., Yu, C., and Metzler,

---

Over-Tokenized Transformer: Vocabulary is Generally Worth Scaling
A. Pytorch Implementation
We provide pytorch-like pseudocode for Over-Encoding in Algorithm
Algorithm 1 Over-Ehcoding in PyTorch-like style.
HOE parameters:
vocabulary
k: split num
4 the number or neigaboring tokens involved
#Nodel parameters:
V: base vacabulazy size
4 D: model dimension
fTorch Medules
wee = nn Ribedding 1V, d)
oe eeeeeedde Moduleltt ([an. Embedding (m11*2, (// in 11) in range Ok 1)
pe_projs mn.Modulelist ([nn, (D// (k* (n-1)1, b) Sor in range (k* (a-1)1)
def forward (self, imput_ids); input_ [bs, seqiens]
x - R_gram_ids input_ids.
for rarge n+ll:
n_gram_ida F.pad/input_ids, i 11 (1 1)
for in [k]:
(k-2)
x_ oe oe_emeedderssseeeeeeeeeeeeeeeeee [Lndex] (n_gram_ids (m 2 index)) )
[Ladee +- oe_pzofs [index] (X_oe)
/= return x
(n-1)
B. More Experimental Details
B.1. Downstream Benchmarks
We give a detailed description for the major benchmarks used in our experiments.
piqa (Bisk et al., 2020): benchmark designed to evaluate models on commonsense physical reasoning. tests the ability of models to reason about everyday physical interactions and affordances, requiring both textual understanding and physical intuition to solve tasks effectively.
hellaswag (Zellers et al., 2019): dataset that focuses on testing commonsense reasoning and the ability to predict the most plausible continuation given scenario. considered challenging benchmark due to adversarially filtered incorrect options aimed at confusing models.
arc_easy (Clark et al., 2018); subset of the A12 Reasoning Challenge (ARC) benchmark that contains grade-school multiple-choice questions. The questions in this subset relatively straightforward and assess basic scientific knowledge and reasoning.
arc challenge (Clark et al., 2018): the more difficult subset of the ARC benchmark, comprising scientifically challeng- ing multiple-choice questions that require advanced reasoning, background knowledge, and problem-solving skills beyond basic memorization.
mmlu (Hendrycks al., 2021) (Massive Multitask Language Understanding): a large-scale benchmark designed to test models across wide range of academic and professional fields. It includes multiple-choice questions from diverse domains, such humanities, STEM, and social sciences, aiming to measure comprehensive language understanding and reasoning capabilities.
B.2. CFG Experiments
Detailed Setup. We obtain the grammar following (Allen-Zhu & Li, 2024) with the configuration named cfg3f, as illustrated in Figure 6. 20 million sentences are sampled from the grammar, serving fixed training dataset. We use standard GPT2 architecture, where the larger model uses hidden size of 768 and the smaller model 128. Both larger and smaller models have 12 transformer layers, as depth discovered essential to complex CFG modeling (Allen- -henn & Li, 2024). We use Adam W optimizer with = (0.9, 0.98), weight decay 0.1, initial learning rate 3e and batch size 64 x 8. The models are trained with cosine learning rate scheduler for 10 epoch. To evaluate model performance, we 10,000 sample
12

---

Over-Tokenized Transformer: Vocabulary is Generally Worth Scaling
root
|->20 21
19|->18 161181611 18
16]->1511
13|->1112
10
7|->221
16)->131511
13
7|-322
on example sentence
root
1>>21 19
191->18
16]->1413
13
10.-7999
7|-3112
16]->1414
7|-332
20 >>16 17
175
141112210011
11 199
8|-2311
32233312311
21 -1-181881
17|->1514
14 11-1101212
12
81-3331
3313322312
21
18
-101111111
21 21|:>11677
181--151313
15|->1111
12
9/-333
21
18)--11315
2113333121122222233222222222
15
21121333123223331
Figure 6: Left Panel: CFG rules used our experiments; Right Panel: an example of the generated sequences using the rules. This figure taken from (Allen-Zhu & Li, 2024).
10
Genuaativ
-B- Engary 1.M
Trgan GPT XBV Pupun car 1SC Sppin OPT
Fgras GFT LS
-Bh 2inur bqp. 24d
Jugas GFT 194
-Bo Tipir Heeek b4
Jupan io iigoo NM
Training Step
Taininn Step
Traiiin Step
Figure Performance comparison for models trained on CFG data.
sentences from the trained model regooregressively using the raw next token probability. The sentences then verified by the ground-truth grammar, and the ratio of accurate samples is denoted as generation accuracy.
Implementation of n-gram tokenization or over-tokenization. Though we mentioned -s-ziz vocabulary for 7-gram tokenization n-gram over-tokenization in the main text, the actual vocabulary should be 2 + Σm= 3'. The bias 2 stands for the BOSgin Of Sequence) and EOS(End of Sequence) token and extra 3 terms are for the corner cases where the sequence length may not divisible by n. We refer to -ized vocabulary in the main text primarily to emphasize the order of magnitude.
Hierarchical n-gram input further improves. experiment with introducing hierarchical r-gram inputs CFG setting. Initially, we use single size n- n-gram embedding table handle the model's input. To consider hierarchical n-gram modeling, we add n additional embedding tables, where the i-th table has size of V and use i-gram token as input. Notably, the parameters of these the effective parameter count does not increase. Instead, this process re-parameterizes the embedding table to decompose parameters hicrarchically. The experimental results, shown in Figure 7(a), indicate that the model with hierarchically decomposed 3-gram inputs outperforms the model with naive 3-gram inputs. This further validates that even for models with a complete r--ram vocabulary (rather than approximated through matrix decomposition), hierarchically modeling multi-granularity tokens remains highly effective.
embedding tables can be fully merged into the n-gram embedding table, so
Ablation on base tokenizers. We replaced the base tokenizer to investigate whether further increasing the input vocabulary size could lead to additional improvements. Specifically, we expanded the input vocabulary for 2-gram and 3-gram base tokenizers to 2-gram inputs with vocabulary sizes of 2 81 and (3 729, respectively. The experimental results, shown in Figure 7(b) and Figure 7(c), demonstrate that increasing the input vocabulary consistently improves model performance. Another observation is that, when using the 3-gram base tokenizer, the benefit of increased convergence speed from 2-gram inputs becomes notably smaller. We hypothesize that this related to the vocabularies. Similar observations have been made in natural language processing, where larger input vocabularies require more training tokens to realize their expected benefits.
nature of large
13

---

Over-Tokenized Transformer: Vocabulary is Generally Worth Scaling
B.3. OLMo2 Experiments
Detailed metries. We present a detailed training dynamics comparison for models on OLMo2-IB in Figure 11. OE achieves significant improvements across most metrics, while maintaining at least parity the remaining ones.
B.4. OLMoE Experiments
Loss curves for vocabulary scaling. We present the loss curves and loss difference curves in Figure The larger input vocabulary requires longer training obtain all its gains.
Loss curves for OLMoE-7B models. We present the loss curves for OLMoE-7B in Figure 10. The gains of OE have not fully converged in 500B tokens' training. Comparing to the experiments on OLMoE-1.3B it is likely that larger models require more training to fully leverage the power of over-encoding.
Detailed metries for OE. We present detailed training dynamics comparison for OE-12.8M and baseline model in Figure ((OLMoE-1 1.33B) and Figure ((OLMoE-7B)) Our model has significant improvements most evaluation metrics, and has at least comparable performance for the rest.
Detailed metries for OT. We present detailed metries comparing OT-12.8M and OE-12.8M on OLMoE-1.33 in Figure 13, OT is not always better than OE, e.g., Winogrande and Social IQA.
B.5. In-house Experiments
We also perform in-house experiments verify the effectiveness of over-encoding. The in-house baseline adopts MoE architecture, having 400M activated parameters and 4B sparse parameters in total. Then implement OE, scaling up the vocabulary size through a series of open benchmarks under the few-shot settings. Results are shown in Table 9. OE shows significant gains across different domains, including reasoning, knowledge and math ability. Especially, we notice that OE mostly improves knowledge ability. These results demonstrate that OE also improves in-context learning.
36M. We train 600B tokens with in-house pre-training datasets, and evaluate the model
Table 9: Comparison of OE and baseline on in-house models, The models are evaluated on various benchmarks on the few-shot settings. OE improves both reasoning, knowledge and math related benchmarks.
Reasoning Related Benchmarks
ARC Challenge
Drop
BBH
WinoGrande
Hellaswag
Baseline
65.7
34.4
37.1
63.2
66.2
+OE 36M
67.9
36.3
39.5
65.5
67.2
Knowledge Related Benchmarks
MMLU
C-Eval
TriviaQA
MMLU-Pro
AGIEval
Baseline +OE 36M
54.8
61.3
39.7
21.1
39.1
57.9
68.3
49.0
24.1
43.2
Math Related Benchmarks
Ape210K
GSM8K
MATH
Baseline +OE 36M
63.7
40.6
22.7
63.8
46.2
25.3
C. Over-Decoding
Method. From previous experiments on synthetic data, we know that an excessively large output vocabulary is detrimental to small models. Therefore, when designing an over-decoding method based on natural language, we aim to leverage the advantages of n-gram prediction while keeping the decoding vocabulary size as small as possible. We found that product decomposition provides a promising solution this problem.
14

---

Over- Tokenized Transformer: Vocabulary is Generally Worth Scaling
training
val. loss
c4 en
dokna books vol. loss
Baxtine
Besciie
01-12
06
0E-12
35
1.5
27
15
3.2
2.75
1030
1000
1000
530
1020
Joima pis2o
4olma toddit vol.
loss
Basciox
Bancin
Bascine 06 AM
18:-1.-M
06:12.90
10:-11.880
3.5
3.3
2.25
3.5
2.5
2.60
2.4
12
3.0
1.25
750
500
752
1030
250
900
7.0
1006
250
912
750
1000
2.0
530
750
1000
wiki
00202-42uc loss
pile val loss
Banttn
Baniite
Bastine
1.50
Sandine
06:12.1M
5.25
05-12.88
3.25
3.35
2.75
2:50
3.00
2.25
1030
1000
7.1
1060
1.000
wikitest 105 vol. loss
MMLU steth Acc.
MMLU humanities Acc.
MMLU social sci Acc.
4.00
0.34
7.75
0.34
0.575
0.589
3.50
0.30
0.325
0:35
Badit
Bascine
0.205
Bexcine
3.90
00-11
0:24
1000
1000
MMLU AtherAcc. Acc.
bellaswwg Acc.
Challlege Ace.
0.50
0.5
0.40
0.43
0.5
0.5
0.35
0.7
0.30
0.30
08-12
0.25
250
200
750
1000
230
300
750
1000
230
302
750
1000
2.0
300
750
1000
<ic casy Acc.
piga
winegr
openbboo, qu Ave.
0:75
0.623
0.77
0.70
0.5
Bastis
Basiier
0.500
Basciiee
0E-12.5M
12-11..MM
08-12.80 1M
0.235
0E-12.80
0.475
1938
1816
756
1860
750
1000
bookg Ase.
copa Ave.
comtitntteetcc Ave.
social oge Ave.
0.85
0.23
0.44
0.50
Banclo
0:65
Bailix
Baudine
0.42
Bexciine
OE-1125M
96-121M
05-12 08-12.90
0E-12.804
Figure 8: All metrics for OLMo2- comparing 0F-12.8M and baseline.
15

---

Over-Tokenizee Transformer: Vocabulary is Generally Worth Scaling
Baseline
0.00
3.1
0E-3.2M OE-12.86 KM
-0.02
Training Loss
Training
-0.03
2,8
.0.04
Baseline
OE-0.2M
OE-0.8M
OB-3.2M
2.5
-0.06
0B-12.5M
100
200
300
200
300
Training Tokens(B)
Training Tokens(B))
(a) Loss Curves
(b) Loss Diff
Figure 9: Loss curves for vocabulary scaling experiments, where OE models use the setting of n 2, The curves are smoothed with exponential moving average of weight 0.99.
Baseline
0.00
00.0
Training Loss
Training Loss
-0.03
0..44
24
23
-0.07
Buseline
0B-128M
22
100
200
3001
100
Training Tokens(B)
Training Tokens(B)
(a) Loss Curves
(b) Loss Diff
Figure 10: Loss curves for OLMoE-7D 7B experiments. The OE model uses the setting of = 3, k: 4. The curves are smoothed with exponential moving average of weight 0.99. The flat part in baseline a consequence of wandb log missing.
16

---

Over- Woke-Toeedized Transformer: Vocabulary is Generally Worth Scaling
Isaining ppl
val. loss
c4 vol
dolin books val. loss
3.1
22.5
1.4
3.-
34
75
3.4
1.2
32
1.0
28
332
103
vol.
7.4
Busciig 06-12.9M
06 12:5
Bastio
3.5
Baadtti
06 06-12.50 1M
Dandies
0S 06-12.M
3.0
3/2
1.4
14
2.3
1.4
244
100
302
100
100
502
190
330
100
1000
530
1.0
700
100
400
500
102
2000
300
100
500
loss
10c loss
vall
pile vol.
344
Bastine
06-12.4M
1.1
06:12 FM
Bastin
4.
Baadtt 06-12
3.2
2.5
3.4
2.8
2.4
14
2.4
2.5
2.4
32
23
183
wikiiedd 105 val. loss
MMLU stem Acc.
MMLU humonitties Acc.
MMLU social sct Acc.
3.75
06-12.0
0.550
3.90
0.23
3.00
2.75
0:25
0.24
Baddo
0.200
Bardiee
MMLU Acc.
hellawwag Acc.
Acc.
Challenge
0.35
0.350
0.315
0.205
0.325
0:35
0.500
05-120M
0.305
100
200
300
400
302
100
230
300
400
300
180
200
300
400
500
100
200
300
500
atc casy Acc.
piçe Ace:
winograndee
openbook qu Acc.
0.735
0.78
0.700
0.36
0.33
0.675
0.925
0.45
Boxel lon
02-12:5M
0.90
Boelio
0B 128M
Baidiar
O5 12.90
0.28
Bareite
OB 02-12.981
0.58
100
100
181
bookg Ave.
capu Ace.
comminteenee qu Acc.
suciall Aue.
0.655
0.45
44
0.44
0.43
0.59
0.525
Baxtiie
Basiino OB-12AM
Bandior OE 06-12AM
Bardiee 08-12.00
05-12.55
Figure 11: All metrics for OLMoE-1.3B. comparing OF-12.8M and baseline.
17

---

Over- TokeeToeedized Transformer: Vocabulary is Generally Worth Scaling
maining
en val. Joss
64 val.
dolim books val. loss
23
06:124M
4.0
06:12.8
3.5
3.5
14
3.0
20
500
100
100
100
285
dolnsa
dolun reldit
Baacite
Sasciis 02--12.80
Bractinn
Dandies
06:12.M
06-12.1M
O5 02-12.00
1.0
3.75
1.0
3.50
3.25
3.25
3.00
3.00
2.0
160
302
100
400
200
100
700
730
100
992
120
300
710
400
500
100
260
301
400
502
dolou vol.
Ioc loss
m24D-42ore val.
pilc loss
4.0
06-121M
Bistiie
Sancitee
4.25
06-1211
Bandiee
3.5
3.75
3.0
3.0
1.50
2.5
3.00
2.0
1.30
160
100
200
wikiteett 100 vol. loss
MMLU stem Acc.
MMLUU humonities Acc.
MMLU social sci Acc.
0.34
0.34
0.40
032
0.12
0.30
0.14
Sencine
Baslas
0.25
MMLU Acc.
bellaaswag Acc.
sciq/Acc.
Challeeng Acc.
0.45
0.6
0.53
0.35
0:35
0.4
0.30
08-125M
100
202
300
400
200
100
200
300
400
302
300
200
300
400
506
100
200
302
400
300
clayy Ace:
pige Acc.
witsogrande
openbook, qp Ace.
110.0
0.40
8.63
0.590
Rescite
0.225
Baelzx
0.70
Bareite
G8-12 1.854
02-112.94
0B-1255
OB 0B-122900
0.590
100
150
100
200
boolg Ace.
cops Acc.
commonnecise Ace.
social ige Ace.
0.50
0.48
0.45
0.00
0.55
8.75
Busdine
Sesciin
6.30
Baaslln
0.42
Bardiie
06-128M
05-12.8M
OE-12.5M
0B-12.00
8.75
0.40
Figure 12: All metrics for OLMoE-7B, comparing OE-12.8M and baseline.
18

---

Over- mokeeioeddized Transformer: Vocabulary is Generally Worth Scaling
1saininn ppl
val. loss
c4 vol ppi
doime books val. loss
22.5
01122M
00012
3.5
344
30
15.0
1.0
100
vol.
01:12.55
0B-12.00
0B-22.300
0B-12.00
011:2.M
3.2
01:22AM
01:12.00
0T 08-12.9
3.2
15-
34
1.4
3.2
24
100
302
100
100
502
190
330
100
1000
930
180
700
100
400
500
180
200
300
100
500
loss
Joss
vall
pile vol.
3.5
0B-12.4M
OB-123M 0T11AMM
4.
00-12
0B-12.00
07:12AM
1.4
08-12.4
3.2
3.2
2.8
3.5
7.6
2.5
2.4
2.4
24
3.2
23
183
wikiied 105 val. loss
MMLU stem Acc.
MMLU humonitiies Acc.
MMLU social sct Acc.
3.75
0.550
0.32
0.30
1.00
2.75
0.24
OB-121M
0T133M
12
0.200
DB- 12--122.0
MMLU other Acc.
hellawwag Acc.
Acc.
Chaillnge
0.45
0.5
0.35
0.93
0.8
0.35
0.42
0.30
0.33
0.25
07-1188
01-12.0
150
200
300
400
302
100
230
300
400
300
180
200
300
400
300
100
200
300
500
atc casy Acc.
piçe Ace:
winogrande
openbook qu Acc.
0.38
0.36
0.50
0.34
0.43
06-12:5M
06:12.6M
O6
0.2
OE-12
05:12M
01:12M
0.58
01-12.55
01-12285
100
101
bookg Ave.
copu Ace.
commenseenee qg Acc.
suciall Lig Ave.
06535
0.48
0.500
0.535
05- 06:12.35
06 12.5M
06-12.9M
OF 06-12.MM
07:12AM
0.63
01:12M
01-12.4
01-12.1
Figure 13: All metrics for OLMoE-1.3BB, comparing OT-12.8 and 0E-12.8M.
19

---

Over-Tokenized Transformer: Vocabulary is Generally Worth Scaling
For the n-gram decoding vocabulary, the product embedding decomposition parameterizes a V"-sized embedding table using n separate V-sized embedding tables, formulated as:
6₂
B x (x (x/V\-1)
Σ Ey(3),
(6)
j=1
where é is the reparameterized 2-gram embedding, and 2 2n correspond to the reverse mapping of the function f given as described in 2. Then, during training, we compute the next n-gram token prediction loss on the reparameterized embeddings {ē
n
L CE(LE (2()))) Σ ceehE
where h represents the output hidden state, CE(;;) -) denotes the cross-entropy loss, and the loss decomposition is detailed later.
A notable challenge is that the decoding embedding is densely activated, making the unembedding layer computationally expensive, particularly for smaller models. To address this, we optionally apply a low-rank decomposition by projecting the last hidden state to a smaller dimension. Additionally, we reweigh these losses using a set of hyperparameters X1, An resulting in the final training loss:
C = Σ (EW,
(8)
where Wy is the optional projection matrix corresponding to the j-th embedding table. We typically set A 1 and Vi > 1, I 1. A pytorch-like implementation is provided in Algorithm 2.
Derivation of Loss Decomposition We provide a detailed derivation of the loss decomposition in (7). Recall that {ē: are the n nr-gram token embedding table. Each of them is reparameterized by é; = Σド= Ez(2,) with i= = 2, V2. We denote Ez)z), then é; E)= ozyy Cross-entropy loss using n-gram token prediction task on {ē:} can be written as:
((h,((t)) E) = llo exp(he, = log
exp(h(E, e!?))
Σ, (ho(
Σ E exp(h(E, 0.n)))
II, (xe()
II, exp(hee!) (
lolog log
-log
Ex..... II exo(
(1))
11, (E., exp (he!))
exp(he
exp(he
= log
log Σ,, exp(he!) (3)
Eshh, Ey),
(9)
Σx, exp (he (1)
where zy is the next-j token, and (+()) -, xy Vi-1, Hence, with product embedding decomposition, the n-gram token prediction can be decomposed to multiple next-j token prediction loss, which can be calculated efficiently.
Discussion. Based on product embedding decomposition, we propose a training objective similar to MTP (Gloeckle et al., 2024). Formally, we remove the additional transformer layer introduced by the multiple prediction heads in MTP. Instead, we directly decode the next to n tokens from the last hidden state using n different vocabularies.
From the perspective of MTP, the nonlinear transformation introduced by directly using new vocabularies in the prediction heads not weaker than adding a transformer layer. Moreover, since the unembedding process is a computational bottleneck. using a new set of parameters does not reduce training throughput compared to MTP.
From the perspective of Over-decoding, we retain the potential to scale up the output vocabularies. This means that the training process provides finer-grained supervision signals, which may enable the model to learn better representations. However, this approach is likely only practical for sufficiently large models. On one hand, larger models have a smaller proportion of computation spent on unembedding. On the other hand, larger models offer greater capacity to take advantage of this setup.
20

---

Over-Tokenized Transformer: Vocabulary is Generally Worth Scaling
Algorithm 2 Over-Decoding in PyTorch-like style.
HOD parameters:
number next tokens involved
lamodas: 1sst of n-1 ellemant,, ind ing losa weights for next 1+1 boken pred dimenalon For low rank decomposition
NNdeel parameters:
d V: base vocabula any 5ize
4 D: model dimension
#Torch Modules
wte nt. Embedding IV, d) detault next token embedaling table od_eabs an (oduleliii)t
an, Sequentiall
ne. mi.Linear (D, d) if b !- d else gn. Indenittyyll on.trnnar(d) V)
for i in cange(n-1)1) losa www.rroontntrooyccssstl
def (eelf, input_ids, hidden_statesi:
input_ids: [bs, seqiens]
[ba, seqiens, DJ
loss ce ce_loss (e_ (F.1ineaz (bidder 11, wte.weight. input_idat;; 1:1] for in range (2, n+ll:
oss lambdas(1-2) le_less lod_ [1-2] (hidder_states( (z-1)), input_" [a 1:))
return 1oas
0.12
Baseline
Ap-0.
OD A2-02
OD Ay-
On Ag-1.0
Training Loss
Training Loss
0.000
0.06
0.04
-0.010
8.02
0.00
100
200
300
400
500
100
200
300
400
500
Training Tokens(B)
Training Tokens(B)
OLMoE-1.3B
OLMoE-7B
Figure 14: Loss diff curves comparing over-decoded models and baselines. OD models the setting of n 2 and Ag [0.1,0.2,0.5, 0.5, 1.0]. The curves smoothed with exponential moving average of weight 0.99.
C.1. Experiments
We conduct experiments for Over-Decoding under OLMoE settings, where both OLMoE-1.3B and OLMoE-7B are considered. We train 500B tokens for all the experiments.
OD improves baseline with sufficient training. We first observed that over-decoding significantly lags behind the baseline in the early stages of training. However, after training on more than 200B tokens, over-decoding begins to outperform baseline. This experiment is conducted on both 1.3B and 7B OLMoE models, where we set n = 2. As shown in Figure 14, the next-one-token loss for over-decoding surpasses the baseline with a steeper slope. Downstream metrics, as illustrated in Table 10, also show slight improvements with proper loss weight choosen. Typically, find training loss converges to similar values regardless of loss weights. But from the downstream tasks, smaller weight leads to better overall performance.
21

---

Over-Tokenizee Transformer: Vocabulary is Generally Worth Scaling
Table 10: Ablation study on loss weights for OD. The column downstream represents the average score of MMLU-Var, Hellaswag, ARC-Challenge, ARC-Easy and PIQA.
Model
Loss
Eval Loss
MMLU-Var
Hellaswagt
Are-Challenget
Arc-Easyt
PIQAt
OLMoE-1.3B
2.554
2.924
0.327
0.553
0.325
0.622
0.727
+OD Àạ 0.1
2.549
2.920
0.325
0.553
0.331
0.610
0.721
+OD Àạ 0.2
2.549
2.918
0.327
0.551
0.323
0.633
0.728
+OD Aς 0.5
2.549
2.918
0.325
0.553
0.308
0.619
0.727
+OD X2 1.0
2.555
2.923
0.328
0.550
0.320
0.629
0.722
OLMoE-7B
2.306
2.670
0.385
0.695
0.414
0.740
0.775
+OD 0.1
2.304
2.672
0.387
0.691
0.409
0.724
0.776
22


Reviews:
[{"review_id": "3pSDElQL0I", "reviewer": "Reviewer_rXP1", "summary": "This paper reveals the scaling law of vocabulary size. They decouple the encoding and decoding vocabulary and introduce Over-Tokenized Transformers. Using CFG, they demonstrate the advantages of larger vocabulary size in synthetic settings. With this intuition, they design and train language models with larger encoding vocabulary. They show that larger vocabulary leads to clear improvement on model performance with less training steps.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the time and effort you have taken to review our manuscript, and are truly thankful to the reviewers for the insightful comments. As a response, we address each point individually.\n\n### The choice of using n-gram tokens.\nContinuing to train BPE to obtain a larger vocabulary is indeed a more natural approach, and we have also attempted such a practice in our early experiments, where we keep frequent bigrams to construct a large one-to-one embedding table and discard unfrequent bigrams. However, the experimental results show that this approach is not better than simply hashing. This may be because the frequencies of the expanded embeddings differ too greatly (the hottest and the coldest can differ by a factor of 10,000), resulting in the parameters of the expanded embeddings not being sufficiently trained. In contrast, the hashing-based method can ensure that all expanded embeddings have an equal access frequency, thereby ensuring sufficient training and better scalability. Of course, we also encourage future work to continue exploring in this direction and to achieve end-to-end encoding of multi-granularity tokens directly from the tokenizer.\n\n### The slope of the scaling line is too small.\nAs for the slope of the embedding parameters' scaling curve, we are not proposing to replace the scaling law of the standard dense parameters, but rather to provide an additional, nearly **COST-FREE**, second growth curve. From this perspective, as long as this scaling benefit exists, it remains a better solution.\nTypically, you can keep scaling up the embedding parameters with negligible inference cost and barely any additional training costs other than the GPU memory usage (please refer to our response to Reviewer wJC2 for numberic results). To inference, the large embedding table can simply be offloaded to CPU. And in fact, the issue of GPU memory overhead during training can also potentially be addressed through CPU offload and prefetch (might be solved in future work). Under these circumstances, as long as we scale it up to a large enough extent, e.g., 128 times the original vocabulary size, we can achieve significant performance improvements, e.g., 400M OE loss is on par with the 1B baseline.\n\n### Typos in Equations.\nThanks for your careful reading. We apologize for the confusion on our formulations. Yes, there is a typo in equation (5). We leverage both 1-, 2-,.., n-gram tokens, so the equation is expected to be\n$$\\texttt{OE}(x)= \\mathbb{E}^{V\\times d}(x^{(-1)}) +\\sum_{i=2}^{n} \\mathbb{E}^{m\\times \\frac{d}{n}|k}(x^{(-i)})$$\nAs for parameter k, it indicates a slicing factor. And flattening this equation should result in:\n$$\\texttt{OE}(x)= \\mathbb{E}^{V\\times d}(x^{(-1)}) +\\sum_{i=2}^{n} \\sum_{j=1}^{k}\\mathbb{E}^{m\\times \\frac{d}{nk}}(x^{(-i)})W_{i,j},$$ where $$W_{i,j}\\in \\mathbb{R}^{\\frac{d}{nk}\\times d}$$\nWe hope this could make the formulation clear. We'll revise the paper in the camera-ready version.", "claims_and_evidence": "1. Under the CFG task, the larger models can benefit from larger vocabulary size, but small models do not. Moreover, the scaling up of encoder vocabulary size is better than the scaling up of decoder size. Although Figure 2 perfectly demonstrates this claim, I feel that it would be better to provide more fine-grained analysis on these claims. The synthetic nature of the CFG task may make it possible for more fine-grained analysis.\n\n2. The authors further show that scaling up the encoding vocabulary size with n-gram for language models can give much faster convergence for the training loss. It also improves the performance on models on benchmarks. They adopt a variety of metrics and implement many ablation studies. I find these claims to be convincing.", "methods_and_evaluation_criteria": "The combination of loss/perplexity and the scores on benchmarks make the results convincing.", "theoretical_claims": "N/A", "experimental_designs_or_analyses": "No.", "relation_to_broader_scientific_literature": "Not sure.", "essential_references_not_discussed": "Not sure.", "other_strengths_and_weaknesses": "1. The tokenization plays a key role in language modeling, but is not well-discussed in the literature. The authors provide some valuable insights for better understanding of this crucial component of LLMs.\n2. Can authors comment on the choice of using n-gram for scaling-up vocabulary size? A natural way of scaling up vocabulary size would be keep running the BPE algorithm and get more tokens. This approach also makes more sense since it is adaptive to the data distribution. Directly merging tokens to be n-grams will lead to many \"wasted\" tokens.\n3. Although the scaling law seems to be clear, the slope of the scaling line is too small, making the overall improvement seems to be negligible. The loss and the scores of the OE models are still very close to the base model.", "other_comments_or_suggestions": "There seems to be some typos. Equations (4) and (5) are confusing. The texts seem to indicate that all k-gram encodings will be used (k=1,..,n). But the equations conflict with the description.", "questions_for_authors": "No", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "aaa9kYG7rs", "reviewer": "Reviewer_ye13", "summary": "This paper introduces a novel method of scaling vocabulary size for LLMs, where given an existing tokenizer, the model constructs n-gram representations on-the-fly. Several algorithmic optimizations (matrix decompositions) are made to limit the size of the embedding table while handing the exponential growth of n-gram embeddings. Namely: n-gram representations are tiled across a fixed vocabulary size, m, and their hidden dimensions are low-rank -- only projected back to d_model when needed. m then becomes a knob to control how much memory one wants to allocate to n-gram representations. This decomposition though preserves the sparse lookup nature of embedding table, preventing massive FLOP overhead (although there is some overhead from the new projection). Extra memory costs are handled by hardware/engineering optimizations to shard the memory across many GPUs. Authors show that scaling m, and introducing n-gram representations greatly improve performance on both synthetic, training dynamics, and 0-shot downstream tasks, for OLMo2 models up to 1B dense and 7B MoE (~1B activated). Authors show that there exists a log-linear relationship between scaling vocabulary size and training loss. Vocabulary size is able to be scaled up to 12.8M.", "questions": "", "limitations": "", "rating": 5, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the time and effort you have taken to review our manuscript, and are truly thankful to the reviewers for the insightful comments. As a response, we address each point individually.\n\n### Performance on Few-shot Tasks\nWe have conducted few-shot evaluations for in-house experiments. Our in-house baseline follows MoE architecture with 400M activated parameters and a total of 4B sparse parameters. And we implement OE to scale up embedding table m to 36M. Here, we share some of the results.\n#### Reasoning Related Benchmarks:\n|                | ARC Challenge | Drop  | BBH   | WinoGrande | Hellaswag |\n| -------------- | ------------- | ----- | ----- | ---------- | ------- |\n| Baseline | 65.7          | 34.4  | 37.1  | 63.2       | 66.2    |\n| +OE 36M        | 67.9          | 36.3  | 39.5  | 65.5       | 67.2    |\n\n#### Knowledge Related Benchmarks:\n|                | MMLU  | C-Eval | TriviaQA | MMLU-Pro | AGIEval |\n| -------------- | ----- | ------ | -------- | -------- | ------- |\n| Baseline | 54.8  | 61.3   | 39.7     | 21.1     | 39.1    |\n| +OE 36M        | 57.9  | 68.3   | 49.0     | 24.1     | 43.2    |\n\n#### Math Related Benchmarks\n|                | Ape210K | GSM8K | MATH |\n| -------------- | ------- | ------ | ---- |\n| Baseline | 63.7    | 40.6   | 22.7 |\n| +OE 36M        | 63.8    | 46.2   | 25.3 | \n\nWe will add these results to our paper in the camera-ready version.\n\n\n### Analysis of the training & inference speed\nWe put thorough analysis on response to Reviewer wJC2. In conclusion, OE has 4% and 8% training overhead on OLMoE 1.3B and OLMoE 7B. We emphasize the larger overhead in OLMoE7B is owing to that we did not carefully optimize engineering configurations. Theoretically, OE only introduces less than 0.4% FLOPs. The overhead measured in the experiments should mainly be introduced by the all-to-all communication (which is proportional to the size of data parallel). And these communication overheads can be further optimized through engineering techniques in the future.\n\nAs for inference, we tested the prefill and decoding throughput on a single A100 GPU using the transformers library. For the OE models, the additional embedding parameters are offloaded to the CPU, incurring no GPU memory overhead. The impact of OE on inference throughput is negligible (around 2%).\n\n\n### How would one choose the sparsity tradeoff given fixed memory budget if combining both MoE and OE?\nIt's an interesting question. First of all, it must be admitted that the performance of OE with the same number of sparse parameters is not as good as that of MoE. However, we'd like to emphasize that scaling up the parameters of MoE is not free. During the inference, MoE increases the GPU memory overhead. Moreover, under small batch sizes, there are memory access bottlenecks, and the inference efficiency is usually far from reaching that of a dense model with the same activated parameters (as shown in the inference speed table on our response to Reviewer wJC2). In contrast, during the inference process, OE can be completely offloaded to the CPU, incurring no GPU memory overhead, and the reduction in efficiency is almost negligible. Our recommended approach is to first determine the size of MoE according to the inference requirements, and then use the remaining GPU memory to scale the embedding table.\n\nIn addition, considering that OE has a good property during the training phase: the input of OE only depends on the token id, it provides more room for engineering optimization. For example, during the training phase, OE can possibly be offloaded to the CPU and the embeddings of the next micro batch can be prefetched and overlap with current micro batch's forward. On this occasion, OE and MoE can operate independently without interfering with each other. We are also exploring different engineering solutions for this issue.\n\n\n### Related work & Equation Typos\nThanks for your careful reading, equation 5 has some typos. The correct formula should be:\n$$\\texttt{OE}(x)= \\mathbb{E}^{V\\times d}(x^{(-1)}) +\\sum_{i=2}^{n} \\mathbb{E}^{m\\times \\frac{d}{n}|k}(x^{(-i)})$$\nAnd we appreciate the suggestions on paper writing and related work. We will improve the paper in the camera-ready version.", "claims_and_evidence": "Claims in this paper are generally sound and the authors provide compelling empirical evidence of the effectiveness of their method. They show that the method works across a wide array of experimental settings at reasonably large scale: synthetic, training loss, holdout perplexity, 0-shot downstream, for models up to 1B Dense and ~1B activated 7B sparse MoE, for 500B tokens. To the best of my understanding, the authors do not overclaim any aspect of their paper. The results genuinely look quite strong. Authors report results even when not the most flattering for their method (OLMoE-7B, Table 1).", "methods_and_evaluation_criteria": "Yes, the authors relatively large scale models from scratch, using standard OLMo settings comparable to the baseline. For evaluation, the use of holdout perplexity is meaningful for architecture design. Moreover, the authors provide a full suite of zero-shot tasks, which is sufficient for this work. It would strengthen the work also to include few-shot tasks, to demonstrate that the method preserves in-context learning abilities. \n\nA major motivation of this paper is to show the value of scaling vocabulary size / parameters. The authors also effectively show this in log-linear relationship in Figure 5, which is quite compelling.", "theoretical_claims": "The authors do not make any theoretical claims. The description of their method is sound.", "experimental_designs_or_analyses": "Yes, the experimental design is sound: all ablations are done on completely fixed settings, ablating only the proposed change to the vocabulary and comparing against the baseline. I do not see any issues with the author's analysis, see \"Claims And Evidence\" section.", "relation_to_broader_scientific_literature": "While as the authors note that there has been studies regarding scaling vocabulary size in the past. To the best of my knowledge, this work is quite novel for a variety of reasons:\n\n1. It uses an unigram vocabulary as the baseline, as it does not change the tokenizer. \n2. It dynamically allows for control over the extra sparse capacity allocated for n-gram representations, similar to sparse methods like MoEs.\n3. It's the first time that vocabulary can be dynamically grown in the model, and the quality is shown to improve with larger dynamic vocabularies.\n\nThe closest work to this in the byte-level transformer space, which tries to do similar at the byte level (aggregate bytes into byte-grams or tokens), however this is typically with the goal of improving byte-level models to match token-level performance. Here, we show that token-level models gain even more performance by going n-gram. \n\nThis an exciting new direction in the field and could open up new avenues for modeling scaling, worthwhile of further exploration.", "essential_references_not_discussed": "Related work is a bit sparse.\n\nPrior works that have aggregated character-level n-grams in different ways are missing:\n- CANINE https://arxiv.org/abs/2103.06874\n- Charformer https://arxiv.org/abs/2106.12672\nAuthors only cite MegaByte, which is not the first instance of this. Early works in character-models discussed above also previously pioneered decoupling of input and output vocabularies.\n\nAuthors are missing some of the very first examples of MTP, such as blockwise decoding (2018): https://arxiv.org/abs/1811.03115", "other_strengths_and_weaknesses": "Strengths of this paper has been well covered in previous sections. This is an exciting, novel, modeling improvement that has the capability of unlocking new scaling avenues in the field. The empirical results are thorough and convincing. \n\nWeaknesses: More thorough analysis of the training and inference speed would be welcome, as this could be a major blocker for adoption. This would strengthen the efficiency results reported in Section 3.3. Especially as the OE method is light on additional FLOPs, but not FLOP-neutral (extra up-projection).", "other_comments_or_suggestions": "Description and notation of the method could be written to be easier to follow. In particular the use of excessive superscripts, and E -- typically reserved for expected value, is a little confusing. The i in the summation of Eq (5) isn't passed anywhere.", "questions_for_authors": "Is there a slowdown in walltime for training, or the ms/step for decoding?\n\nBoth OE and MoE incurs memory cost, is there any advantage in preferring one type of sparsity for another? Do they unlock different types of capabilities? How would one choose the sparsity tradeoff given fixed memory budget if combining both MoE and OE?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "8oD1QzCwvs", "reviewer": "Reviewer_DdYQ", "summary": "This paper proposed methods to create much larger input/output vocabularies for transformers. For the input, (causal) n-grams embeddings are used. These are hierarchical in that they are the sum of n-grams for multiple values of n, including the original single valued token. Similarly they suggest Over Decoding where n-grams are predicted (but only the initial token is used as the auto-regressive input). They find that while Over Encoding helps in most settings, Over Decoding is only helpful for large models.\n\nThey evaluate Over Encoding based on c4 language modeling an a handful of downstream tasks and find that it yields significant gains in performance and training speed.\n\nThey also do ablations about which parts of their Over Encoding scheme are the most important and find that the hierarchical nature is important and that hash collisions should be minimized.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the time and effort you have taken to review our manuscript, and are truly thankful to the reviewers for the insightful comments. As a response, we address each point individually.\n\n## About Questions on Claims And Evidence\nAs far as the over-encoding technique itself, indeed, it is typically a network module that improves performance and is irrelevant to the tokenizer. However, we believe the insight behind is worth noticing for the tokenizer design:\n1. We show that the encoding and decoding in tokenization should be separately considered to maximize model performance. One should be careful in increasing decoding vocabulary.\n2. Hierarchical designs improve OE, but can multi-granularity tokens be properly considered in tokenizer design itself? \nBy introducing OE, we show that simply leveraging hashed n-gram tokens could yield significant improvements to LLM. We could expect this gain to be pushed further with delicate tokenizer designs.\n\nAs for the \"more efficient LLM\", we mainly consider our efficiency on the proper use of sparse embedding parameters, similar to MoE, which improves model performance with negligible training and inference overheads. It is efficient as you can obtain powerful models with possibly half training and inference budget.\n\n## About tease apart the gains.\nThe reviewer mentioned:\n> It would be nice to see experiments that teased apart if the gains are from having such a larger vocabulary or from the explicit modeling of n-gram composition. It would have been nice to see an ngram representation made of the sum of each token in the n-gram with shared embeddings\n\nActually, we tried such an approach in the early stage of our research. Summing n-gram tokens from a shared embedding doesn't work because there is no positional distinction for each token in the n-gram (addition is commutative). This makes the current input token unclear, which is detrimental to the model's performance. If we simply remove the condition of sharing embeddings and apply n different embedding tables to these n tokens, the model can achieve some benefits. Later, we found that the gains from this implementation are close to those predicted by the OE scaling curve with \\(m=(n - 1)\\times V\\). Essentially, this implementation is a product decomposition for the full n-gram embedding table. Alternatively, you can also view it as OE using a special hash function, and the choice of hash function isn't crucial for OE.\n\nIn addition, our ablation study has also ablated the effect of increasing vocabulary size and n-gram composition. In Figure 5, we fix n=2 and varied vocabulary size, showing the gains from scaling vocabulary size. In Table 3, we fix the embedding parameters and ablated gains introduced by hierarchical n-gram composition. We conclude that both vocabulary size and well-designed n-gram composition are important to OE.\n\n## About the under-trained tokens\nIt's an interesting perspective to consider under-trained tokens. However, we believe OE should not have such a problem. Under-trained tokens are potentially harmful mainly due to their under-trained embedding vectors. For OE, n-gram embeddings are equally visited during training owing to the many to one hashing. Though there might be some unknown n-gram tokens occur during inference, their embedding vectors are guaranteed to be frequently trained. So, we believe the unseen n-gram tokens are more like a normal spelling mistake and will not cause catastrophic consequences. Moreover, the token embeddings should contain at least one well-trained uni-gram embedding under the hierarchical design, which also improves robustness against unseen n-grams.\n\n## What kind of text benefits the most from over-encoding \nExamining how n-gram embedding contributes to some specific token is kind of difficult. As the n-gram embeddings improve the keys and values in the attention layer simultaneously. As a result, it is difficult to tell where the improvements on specific tokens come from. However, from the evaluation results, we do notice that OE has significantly larger improvement in knowledge-related tasks (see few-shot results in our response to Reviewer ye13). We hypothesis that coarse-grained token embeddings help memorizing concepts of proper nouns, which are usually broken into several tokens under the base tokenizer.\n\n## About the Relevance of BLT\nWe are sorry for the word 'patching' that misleads the understanding. We typically want to talk about the n-gram embedding technique used in BLT. They apply n-gram byte embeddings to the byte-level sequence, which does not reduce byte sequence length as well. We'll revise the paper to make this more clear.\n\n## Related Work & Writing Issues\nWe appreciate the suggestions on related work and paper writing. We'll improve the paper in the camera-ready version.", "claims_and_evidence": "There claims are supported, their method shows strong improvement in multiple setting with multiple models and seems like they would extend to other seeings.\n\nHowever, some claims in the probe like \"insight for tokenizer design\" and mentions of \"more efficient LLMs\" seem like overreach given they don't actually reduce sequence lengths or change how tokens created, instead their method is more akin to a specialized input layer that explicitly models things like n-grams.", "methods_and_evaluation_criteria": "Yes, they include both intrinsic evaluation on c4 language modeling and extrinsic evaluation on other datasets.", "theoretical_claims": "N/A", "experimental_designs_or_analyses": "In figure 4 there are claims about \"convergence acceleration\", however, from the training loss it seems like their models have not converged, i.e., the training loss is still decreasing. These speed ups should probably be framed as time to reach the performance as the baseline models instead.\n\nIt would be nice to see experiments that teased apart if the gains are from having such a larger vocabulary or from the explicit modeling of n-gram composition. It would have been nice to see an ngram representation made of the sum of each token in the n-gram with shared embeddings instead of making new unrelated embeddings for \"the\" and \"the fox\" (only the \"fox\" token is included in the hierarchical embedding).", "relation_to_broader_scientific_literature": "Recent works like https://arxiv.org/abs/2405.05417 discuss how under-trained tokens in LLMs can be used to facilitate unwanted model behavior. Using Over-Encoding means there will most likely be far more under-trained tokens (not only unseen unigrams but unseen bi or tri grams). It seems so analysis on how a technique like this effects LLM safety would be prudent.", "essential_references_not_discussed": "Their \"General n-gram Embedder\" which looks up indexes modulo m such that different token could share an index is very similar to the hash-based embeddings from works like vowpal wabbit and fasttext. The study of how this embedding technique interacts with transformers in novel, but these works should be discussed with respect to the method.\n\nThe dense projections in their Over-Encoding section is very similar to the soft prompt reparameterization in works like https://arxiv.org/pdf/2101.00190 and https://arxiv.org/abs/2305.03937 so they should be mentioned.", "other_strengths_and_weaknesses": "The left side of figure 3 is very similar to standard transformer data flow diagrams (like the one on the right) but is communicating how the tokens are used. This makes it very confusing as it is read very differently from the right side. Also having Input tokens on the top of the right hand part of the image is non-standard which makes it a bit harder to read than a standard input on bottom image.", "other_comments_or_suggestions": "To me, it seems that the title of the paper \"Vocabulary is Generally Worth Scaling\" implies something different that what is studied. The title suggests a study that scale the size of the vocabulary meaning more unique words/types would be in the vocab (e.g. more merge operations are done in BPE so that less frequent words are still getting their own tokens). Their approach is more akin to making bigram and trigram tokens which was unexpected.\n\nIndexing the ablation studies as things like C-3 makes reading difficult as it tells you nothing about what is being ablated.\n\nOn line 096 they refer to this work as \"n-gram patching\" similar to BLT. However, the \"patching\" in BLT is about reducing the sequence length while this work maintains the original sequence length, but has causal n-gram embeddings.", "questions_for_authors": "Did you explore anything like what kind of text benefits the most from over encoding? For example, on average do you see a large boost in performance when processing a word like \"unfortunate\" that was broken into multiple tokens, i.e. [\"un\", \"fortunate\"] where the n-gram token is simulating what happens if that work wasn't split into subwords?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "hzMTwBs8eC", "reviewer": "Reviewer_wJC2", "summary": "This paper proposed a new framework called over-tokenized transformer for language modeling, which decouples input and output vocabularies for performance improvement while leveraging the $n$-gram tokens. They have experimentally shown a log-linear relationship between the input vocabulary size and the model training loss and found that larger input vocabulary contributes to performance improvement, albeit larger output vocabulary would require larger model size due to over-fitting.\nWith extensive experimental results, this work highlights the importance of tokenization design in large language models, discussing the design of both input embedding and output unembedding.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We appreciate the time and effort you have taken to review our manuscript, and are truly thankful to the reviewers for the insightful comments. As a response, we address each point individually.\n## Analysis of the training & inference speed\nTo illustrate training efficiency, we show training throughputs in OLMoE experiments in the following table, where we run OE and baseline under the same hardware configurations. OLMoE-7B yields more overhead as we did not carefully optimize engineering configurations.\n\n**Table**. Training throughputs for OE and baseline. We report average tokens per second in millions.\n|               | OLMоE-1.3B        | OLMоE-7B         |\n| ------------- | ----------------- | ---------------- |\n| Hardware      | 32  A100         | 64  A100        |\n| baseline  | 1.211           | 0.494          |\n| +OE 12.8M   | 1.155 (-4.63%)  | 0.453 (-8.3%)  |\n\nTheoretically, the additional flops introduced by OE is less than 0.5% (as shown in the table below). The overhead measured in the above experiments should mainly be introduced by the all-to-all communication (which is proportional to the size of data parallel). And these communication overheads can be further optimized through engineering techniques in the future.\n\n**Table**. FLOPs per token in the forward pass.\n|  | OLMoE-1.3B | OLMoE-7B |\n| --- | --- | --- |\n| baseline | 0.5409 G | 2.3578 G  |\n| +OE 12.8M | 0.5430 G (+0.38%) | 2.3662 G (+0.35%) | \n\nFor inference speed, we tested the prefill and decoding throughput on a single A100 GPU using the `transformers` library. **For the OE models, the additional embedding parameters are offloaded to the CPU, incurring no GPU memory overhead**. The numeric results are shown in the following table. The impact of OE on inference throughput is negligible, especially for larger models or larger batch sizes. In contrast, the sparse parameters introduced by MoE face severe memory access bottlenecks during inference. A very large batch size is required for the MoE model to achieve the same throughput as a dense model with the same activated parameters. Considering that the model inference might be carried out on more cost-effective but less computationally powerful inference GPUs, the relative overhead of OE could be further reduced.\n\n**Table**. Inference speed for OE and baseline. The sequence length is fixed to 2048, and we report tokens per second for prefilling and decoding separately under various batchsizes. Settings that cause OOM are leave blank.\n|  |  | Dense-1B | Dense-1B | MoE-1B/7B | MoE-1B/7B | Dense-7B | Dense-7B |\n| --- | --- | --- | --- | --- | --- | --- | --- |\n|  |  | baseline | OE-12.8M | baseline | OE-12.8M | baseline | OE-12.8M |\n| bs=1| prefill | 20728.7 | 19446.4 | 6303.8 | 6189.0 | 6571.0 | 6499.9 |\n|  | decode | 136.2 | 126.6 | 28.2 | 27.9 | 65.1 | 63.3 |\n| bs=8 | prefill | 36907.5 | 35902.6 | 22297.3 | 22292.1 | - | - |\n|  | decode | 797.2 | 760.9 | 184.9 | 181.0 | 232.1 | 228.6 |\n| bs=64| prefill | - | - | - | - | - | - |\n|  | decode | 1422.1 | 1407.4 | 860.3 | 826.7 | - | - |\n\nThese analysis will be added to our paper in camera-ready version.\n\n## About Inference Diversity\nThis is an interesting perspective. We believe that theoretically there should be no difference, and we haven't observed such a phenomenon in practice either. In fact, examples of synthetic data can well answer this question. In the CFG task, if the problem of decreased output diversity exists, the predicted next token probability should have a larger difference from the groundtruth distribution that is calculated according to the grammatical rules. We actually calculated the KL divergence in our experiments, and the OE also shows better performance compared to the baseline, indicating that OE can model the grammar better and generate sequences as diverse as the language itself can be. \n\n## About Questions on Validation\nRegarding the experimental setup, we mainly followed the experiments of OLMo and used its training data and evaluation protocols. Specifically, the evaluations include: the validation sets of public text datasets (such as C4-en-validation), on which we calculate the next token prediction loss/perplexity as the evaluation metrics; and open benchmarks (such as hellaswag), on which we calculate the zero-shot accuracy. \n\nFigure 4 in the paper shows some of the evaluation set metrics that we are mainly concerned (explained in line 220~230). You can find comprehensive evaluation results on Figure 8 in the appendix, where we show the eval losses could has consistent gains.\n\n## Writing Issues\nWe appreciate the suggestions on paper writing. We'll improve the paper in the camera-ready version.", "claims_and_evidence": "With clear correlation between vocabulary size and training loss, their claim is well supported. Leveraging multi-gram tokens in language model is a straight forward idea, and this enhances better contextualization, resulting in lower training loss. On the other hand, I am very curious how this approach impact in terms of inference speed as the proposed approach significantly increase the model parameter size. Inference speed is pragmatically important, thus it would be interesting to compare each model in terms of the inference speed. Additionally, I feel this approach probably loses diversity in the search space at inference. If so, do you have any idea on how to diversify text generation?", "methods_and_evaluation_criteria": "Does Figure 4 report all training losses/metrics for each task? How about the valid loss/metrics?", "theoretical_claims": "N/A", "experimental_designs_or_analyses": "Please see the comments in Claims And Evidence and Methods And Evaluation Criteria.", "relation_to_broader_scientific_literature": "The idea of over-tokenization Transformer could be beneficial as the proposed approach is applicable to any types of large language models. It would be interesting to apply it into a multilingual language modeling.", "essential_references_not_discussed": "- Liu et al. \"Infini-gram: Scaling Unbounded n-gram Language Models to a Trillion Tokens\" in Proc of COLM 2024.", "other_strengths_and_weaknesses": "N/A", "other_comments_or_suggestions": "- l.104 (Tao et al., 2024) demonstrates that -> Tao et al.(2024) demonstrate that\n- l.083 2.3. Multi-Token Prediction and n-Gram Modeling -> 2.3. Multi-Token Prediction and $n$-Gram Modeling\n- Figure 4 - consider displaying the number (e.g., \"5.7x\") in a different position. Hard to read them.", "questions_for_authors": "Please see the questions in each section.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {"ethical_review_concerns": "N/A"}}]

Author rebuttal:

Meta-review: This paper introduces a method for decoupling input and output vocabularies. The authors propose to scale input vocabularies using hierarchical, hashed n-grams, showing strong empirical results on large models, and significant performance improvement on smaller models. The results show a log-linear relationship between input vocabulary size and training loss. Reviewers all agreed on the novelty, strong results, and potential impact of this work. Initial concerns regarding clarity (notation, figures), wall-time, and missing related work were mostly addressed in the authors' rebuttal. Despite other minor suggestions from the reviewers, the core contribution is sound and significant for ICML.
Decision: Accept (poster)