1 Introduction↩︎

Tokenization sits at the entry point of almost every language model. Nearly all modern language models use subword tokenization based on BPE [1], which greedily merges frequent adjacent pairs with a simple and well-understood algorithm. It follows surface frequency without an explicit linguistic model, and recent work documents failure modes including undertrained tokens, poor morphological alignment, and vocabulary inefficiency [2]–[4]. The UnigramLM tokenizer [5] instead assigns probabilities to a vocabulary of pieces and defines a language model over segmentations. It is often reported to produce more morphologically plausible tokens [6], [7]. Compression, an important factor in the cost of training and using large language models, shows mixed results in comparisons with BPE [6], [8].

Unigram tokenization is attractive in part because of its representation as a simple list of tokens with scores: dropping tokens, pruning low-value entries, or combining vocabularies amounts to editing that list and re-normalizing scores. In BPE, by contrast, the vocabulary is tied to an ordered merge list, so removing or repairing tokens can require reasoning about downstream merge dependencies, as in recent work on BPE vocabulary cleanup [3]. The difficulty lies instead in Unigram training. Standard Unigram starts from suffix-array substring mining, estimates probabilities with forward-backward marginal EM over the segmentation lattice, and reaches the target vocabulary size through loss estimates in iterative pruning [9]. This paper continues a line of work asking how the different components of Unigram training affect the properties of the resulting tokenizer. Prior work showed that the iterative pruning schedule and several SentencePiece defaults can be simplified with little loss, and sometimes with better compression [8]. MinGram applies the same question to the remaining heavy components. Can we make the addition of a Unigram-style tokenizer to existing BPE-based implementations as simple as possible, and how can we optimize compression while maintaining some of the attractive morphological properties of Unigram?

We introduce MinGram, a minimalist Unigram tokenizer that keeps the token-list representation but changes the focus towards compression and simplicity. It replaces the three main components of standard Unigram training:

1. marginal EM is replaced by Hard EM on a minimum-token path

2. iterative pruning is replaced by a single simple score-based pruning step

3. suffix-array initialization is replaced by a BPE-derived seed vocabulary

It keeps a learned Unigram score as a tiebreak among equally short segmentations, avoiding the pure least-token rule that can hurt morphology [10], [11]. This places MinGram on a new point in the compression–morphology Pareto frontier, with strong compression combined with moderate morphological alignment. The resulting tokenizer training requires little more than an implementation of its inference process, and in particular side-steps the need for lattices, forward-backward passes, loss-estimators in pruning, or substring mining.

2 Background and Related Work↩︎

2.0.0.1 BPE and UnigramLM.

Byte-Pair Encoding [1] iteratively merges the most frequent adjacent symbol pair until the vocabulary reaches a target size. The Unigram tokenizer [5], [9] treats tokenization as probabilistic inference. A vocabulary \(\mathcal{V}\) with token probabilities \(p(\cdot)\) defines a distribution over segmentations \(s = (s_1, \ldots, s_k)\) of a sequence \(\mathbf{x}\) via \(p(s \mid \mathbf{x}) \propto \prod_i p(s_i)\). Training starts from a large candidate vocabulary and alternates EM updates of \(p\) with pruning steps that remove low-utility tokens, until \(|\mathcal{V}| = n\). For a more detailed treatment of the implementation and mathematical background, see [8] and [12], respectively.

2.0.0.2 Adapting BPE.

A line of recent work modifies BPE to optimize various aspects. [13] recommend dropping rare subword units using training and test-time filtering. ScaffoldBPE [14] and PickyBPE [3] implement a removal rule based on relative rather than absolute counts. Several recent methods relax pretokenization to allow multi-word tokens and improve compression, including SuperBPE [15] and BoundlessBPE [16]. Finally, recent work by [17] introduces a parity-aware variant that changes the merge objective to improve cross-lingual compression fairness. These interventions are effective but often introduce complex workarounds due to the merge-list-based representation and application in BPE. MinGram is in part motivated by these recent advances, as many such modifications are easier in the Unigram representation.

2.0.0.3 Compression and morphology.

Two common intrinsic measures of tokenizers are compression (as measured by e.g. tokens per character on held-out text) and morphological alignment, the extent to which a tokenizer’s segmentations reflect a language’s morphological structure. Tokenizer choice can affect downstream language-model performance, and compression has been linked to translation performance [18], but such effects have not been consistent in more recent studies [10], [19]. The downstream evidence for morphological alignment specifically is also mixed [20], [21].

2.0.0.4 Minimum-token inference.

A separate line of work modifies tokenizer inference independently of training, motivated by tokenizer inference speed and model inference costs. [11] evaluate different inference algorithms, including greedy variants and least tokens, and find that a pure least-token rule lowers morphological alignment relative to greedy decoding. [10] introduce PathPiece, a tokenizer which performs exact minimum-token inference and also trains vocabularies for this objective, but find that this objective does not consistently improve downstream performance. Optimizing compression during training is a difficult problem, but ConvexTok [22] recently formulated vocabulary construction as a linear program, yielding tokenizers with near-optimal compression.

3 MinGram↩︎

MinGram keeps the Unigram representation: a vocabulary with one score per token. It changes the inference and training procedure around that representation. Standard Unigram starts from a suffix-array candidate set, estimates token probabilities with marginal EM over the segmentation lattice, and reaches the target vocabulary size through iterative pruning. MinGram replaces these steps, aiming for simplicity and high compression: Hard EM on a minimum-token path, a BPE-derived seed vocabulary, and one flat score-pruning step.

[alg:mingram] summarizes the full training procedure. The implementation follows this procedure directly, with deterministic tie-breaking and atomic-token preservation handled in the encoder and pruning routines.

3.1 Minimum-path inference↩︎

Standard Unigram tokenization scores a segmentation using a probabilistic model over segmentations. A common word can be split as root+s if the split has higher total probability than the whole-word token, even though it uses one more token. The same issue appears in marginal EM: probability mass is assigned across the full segmentation lattice, while compression depends on the paths that determine token count.

MinGram makes token count the primary decoding objective: \[\label{eq:mingram-objective} s^*(\mathbf{x}) = \arg\min_{s \in \mathcal{S}(\mathbf{x})} \left( |s| - \delta \sum_i \log p(s_i) \right),\tag{1}\] where \(\delta\) is chosen small enough that one additional token always costs more than any possible log-probability gain. Thus the decoder first minimizes token count, then uses the Unigram score to choose among equally short segmentations. For a fixed vocabulary, the primary objective gives the best compression available to that vocabulary. The secondary score preserves useful frequency information without allowing it to choose a longer segmentation. In case of an exact tie (which is common with long spans of identical characters), our implementation prefers the segmentation with longest leading tokens.

3.2 BPE-seeded initialization↩︎

Standard Unigram begins from a large suffix-array candidate set, typically 1M substrings, then prunes it down to the target vocabulary size. This seed is broad but wasteful: the process is complex, and efficient suffix-array construction with tokenizer-specific filtering is not widely implemented, leading to sub-optimal alternatives such as common substrings.

MinGram instead initializes from a BPE vocabulary trained on the same corpus, similar to PathPiece and SaGe [10], [23]. We train BPE to size \(\lceil f \cdot n\rceil\), where \(f\) is a small overshoot factor, and use its tokens as the initial candidate vocabulary. This gives a compact seed whose tokens have already survived a compression-oriented construction process. We initialize \(\log p(t)\) from each BPE token’s corpus frequency.

3.3 Minimum-path training↩︎

Given this seed vocabulary, MinGram estimates token scores with Hard EM under the same minimum-path objective used for decoding. In the E-step, each training sequence is segmented as \(s^*\) from 1 , and counts are accumulated only along that path. In the M-step, token scores are updated by normalized log-frequency: \[\log p(t) \gets \log\left(\frac{\mathrm{count}(t)}{\sum_{t'} \mathrm{count}(t')} \right)\] This removes the forward-backward pass used by marginal Unigram EM. After the EM iterations, MinGram prunes once to the target vocabulary size by flat score pruning, following [8]. We find that \(N_{\text{em}}=2\) suffices, and an outer loop to slowly prune is not required in the regime of relatively small \(f\), as shown in 9.

The default MinGram method keeps this pruning step deliberately simple: after the final Hard-EM pass, it removes the lowest-score non-atomic tokens in one step.

We also evaluate a compression-oriented variant, MinGram-PP (MinGram with PathPiece-style Pruning), whose final pruning rule instead iteratively removes the 10% of tokens whose deletion least increases the corpus token count [10]. This method is notably slower and more complex to train, but retains the simple inference algorithm.

4 Experimental Setup↩︎

We compare both MinGram variants against a range of other tokenizers: BPE, standard Unigram, Unigram with Flat Score Pruning [8], PathPiece-BPE [10], and ConvexTok [22]. We also test variants of standard Unigram and FSP with BPE-based initialization. 1 summarizes how these methods differ in seed vocabulary, decoding objective, and pruning rule. All experiments use SCRIPT encoding with character-boundary constraints as the atomic alphabet [24], and train tokenizers with 32,768 learned tokens in addition to the required atomic tokens. The main setting trains one tokenizer per language on a 5 GB FineWeb/FineWeb-2 sample for English, German, Finnish, Russian, Arabic, and Korean, and evaluates compression on held-out Goldfish corpora for the same languages [25]. All BPE-initialized methods use an overshoot factor close to optimal for compression, using a large initial vocabulary (\(f=8\)) for MinGram-PP and PathPiece and a mostly BPE-derived vocabulary for other BPE-initialized methods (\(f = 1.15\)).

For measuring morphological alignment, we follow MorphAlign [26], measuring the IBM1 alignment score at threshold \(0.01\), multiplied by \(100\), which we refer to as the ‘MorphAlign Score’, on English, German, and Finnish.

6pt

5 Intrinsic performance↩︎

4pt

1 summarizes the main compression–morphology tradeoff. Both MinGram variants show high compression, combined with moderate MorphAlign Score. Notably, MinGram-PP essentially ties with PathPiece for optimal compression, while maintaining much higher MorphAlign Score compared to other compression-optimized methods such as ConvexTok and PathPiece. Our proposed simpler MinGram algorithm is notably more sensitive to the choice of overshoot factor, losing compression when using a larger initial vocabulary, where MinGram-PP keeps gaining compression, saturating at \(f=5\text{--}8\). The MinGram \(f\)-trace shows that at higher overshoot factors, the compression gains reduce. [app:fsweep,app:em-ablation] show this effect is in part due to the aggressive pruning, which has detrimental effects at high \(f\), but not at the default setting of \(f=1.15\).

Unigram and FSP variants with BPE initialization show characteristics similar to MinGram, losing a little compression performance due to the different objective, but clustering close together due to their similar vocabulary. Overall the different variants show a subtle tradeoff, with a Pareto front mainly defined by default Unigram, FSP, and MinGram variants. Additional results in 10 show the morphology gap between MinGram and PathPiece can be clearly attributed to the secondary term with a Unigram score objective. In terms of these two metrics, BPE is Pareto-dominated by many Unigram-family methods in this intrinsic comparison, which all have both lower token count and higher MorphAlign Score.

2 reports the per-language compression numbers, which are fairly consistent across languages. 3 gives the MorphAlign breakdown. English and German show the clearest ordering: Unigram is highest, the compression-oriented reference methods and BPE are lowest, and MinGram lies between them, closer to the FSP and BPE-initialized variants than to either endpoint.

¿tbl:tab:tokenization-examples? illustrates the morphology side of the tradeoff with representative words, including the same compression-oriented reference methods. The examples match the aggregate pattern: MinGram often avoids BPE’s most fragmented segmentations, but standard Unigram and FSP retain some cleaner morphology-oriented splits.

6 Downstream language modeling↩︎

6pt

As a controlled downstream experiment, we train depth-24 nanochat [27] language models, using the default setup of 5.86B tokens of the (primarily English) ClimbMix dataset [28] and measure performance in bits-per-byte (bpb) and the DCLM CORE score [29], following [30]. We use 20 random seeds per method based on power calculations performed after 5 seeds per tokenizer.

Results in 4 show MinGram variants among the best in bits-per-byte, with Unigram-family methods dominating the top of the ranking. ConvexTok and PathPiece-BPE fall clearly behind, and BPE is worst. This metric is also highly consistent across seeds, which makes the differences generally significant.

The CORE score shows high variability with low scores for many tasks, as models are undertrained for many of the benchmarks. MinGram-PP performs best, but only default Unigram, BPE and ConvexTok show significantly worse performance. Larger models and more training data are required to better separate tokenizer performance. Finally, we inspect the number of rare tokens in the models’ training corpus, a proxy for under-trained vocabulary entries [2]: MinGram has the fewest, suggesting the pruning strategy is less sensitive to outliers in training data. We attribute the difference in the number of rare tokens between MinGram and PathPiece to PathPiece’s objective (shared by MinGram-PP), which keeps semi-rare tokens from being shattered into many fragments and retains them in the vocabulary. For example, MinGram-PP and PathPiece vocabularies include , which is represented as in default MinGram. 12 gives additional examples of rare tokens and their frequencies in the training corpus.

1.8pt

7 Conclusion↩︎

MinGram occupies a new point on the compression–morphology Pareto frontier. It compresses better than both BPE and standard Unigram while retaining moderate morphological alignment, and it does so with a procedure that needs little beyond tokenizer inference: no suffix array, forward-backward pass, or iterative pruning loop. The default method trades a small amount of maximal compression for this simplicity, and is more sensitive than standard Unigram to the size of the initial vocabulary. Careful pruning reduces this sensitivity, but fully closing the compression gap requires the more complex iterative rule of MinGram-PP. That variant essentially matches PathPiece-BPE for the strongest compression in our comparison, yet retains more of the longer rare tokens, which suggests the pruning rule could be made more robust to outliers in the training data without sacrificing compression. We recommend the default MinGram for most settings: it has the simplest training, is among the best on downstream bits-per-byte (better than MinGram-PP), and produces the fewest rarely occurring tokens in a cross-corpus setting. MinGram-PP is preferable when token-count compression is the dominant cost, for instance to shorten sequences and reduce serving cost at scale: its added complexity is confined to training, while inference is identical to MinGram and emits fewer tokens. It matches the strongest token-count compressors, trading a small bits-per-byte penalty and more rarely-used vocabulary entries for roughly 0.5 percentage points of additional compression. Our downstream results also caution against optimizing token count alone: the methods that optimize token count without a probability score were among the worst in bits-per-byte, while tokenizers that retain a Unigram score, including the equally compression-strong MinGram-PP, modeled text best. More broadly, this adds to the evidence that compression alone is the wrong objective for tokenizer design: a Unigram-style language-modeling score, even one used only to break ties in segmentation, measurably improves the resulting tokenizer and carries through to downstream modeling.

Limitations↩︎

Our downstream evaluation is narrow. It uses a single small model (depth-24 nanochat), a single training corpus (ClimbMix), one vocabulary size, and a 5.86B-token budget, all in English. Compression differences were clearly resolved in bits-per-byte, but the DCLM CORE task scores were too noisy at this scale to separate most methods: only default Unigram, BPE, and ConvexTok were significantly worse than the best, while the remaining methods were statistically indistinguishable. The downstream ranking we report therefore rests on bits-per-byte rather than task performance, and both are likely to change at larger model and data scales.

Morphological alignment is evaluated only where UniMorph-based MorphAlign data are available: English, German, and Finnish. These are useful probes but do not cover the full range of scripts, segmentation conventions, or morphological systems in our six compression languages.

8 Effect of the BPE-derived initial vocabulary size↩︎

1 shows MinGram’s \(f\)-trace averaged across the MorphAlign-evaluated languages. This appendix examines the sensitivity to the overshoot factor \(f\) defining the size of the BPE vocabulary in different tokenizers using a BPE-initialized vocabulary.

2 shows compression as a function of \(f\) for the BPE-init methods, measured as percentage change relative to Default Unigram. Unigram-BPE-Init and FSP-BPE-Init coincide at \(f = 1\) by construction; MinGram and PathPiece-BPE use the same BPE-seed size axis but differ in training and inference. Increasing \(f\) first improves compression, with the six-language mean minimum at \(f = 1.15\) for the main BPE-init Unigram-family methods. This point is the default used in the main intrinsic comparisons. At larger \(f\), Unigram-BPE-Init moves back toward the Default Unigram baseline, while MinGram also weakens. Including a run with gradual pruning (\(p=0.9\)) shows that this high-\(f\) loss is partly a one-step pruning effect. With a very large BPE seed, single-step score pruning must discard many competing long candidates at once, while iterative pruning recovers \(>1\) pp of compression at \(f = 5\) by allowing the model to resegment between pruning steps, though its optimum remains at \(f=1.15\). The more careful compression-optimized methods, PathPiece and MinGram-PP, benefit from larger initial vocabularies, saturating at around \(f=5\text{--}8\).

9 EM Iterations and Pruning Schedule↩︎

This section motivates the MinGram defaults: \(N_{\text{em}}= 2\) inner EM iterations and single-step pruning (\(p = 0\)). It also investigates to what extent the compression difference between MinGram and MinGram-PP can be closed by more careful pruning.

5 reports MorphAlign and compression as functions of \(N_{\text{em}}\in \{0, 1, 2, 3, 4\}\) for MinGram at \(f = 1.15\) on English, German, and Finnish, with PathPiece-BPE included as a minimum-token reference point. \(N_{\text{em}}= 0\) drops MorphAlign substantially because BPE-derived counts are a poor prior for score-based pruning. At least one EM pass is needed to re-estimate probabilities under the MinGram objective. One to three iterations are all reasonable choices; we use \(N_{\text{em}}= 2\) as the default. PathPiece-BPE is more compression-oriented than these MinGram settings, but has lower MorphAlign even than the no-EM MinGram variant.

6 compares single-step pruning (\(p = 0\)) with iterative pruning (\(p = 0.9\)), both using MinGram’s score-based criterion. This isolates the pruning schedule from the separate token-count rule of MinGram-PP. To make the comparison visible, the table shows the single-step mean and the iterative-minus-single-step delta over English, German, and Finnish. For \(f \leq 1.15\), the candidate pool is small enough that both schedules effectively collapse to the same outcome, covering the default setting. Larger \(f\) values recover some compression under iterative pruning, but require extra corpus tokenizations and do not improve MorphAlign. We therefore retain single-step pruning as the default.

10 Effect of the Unigram Score Objective↩︎

The comparison of MinGram-PP with PathPiece suggests the effect of the small term with a Unigram score in the objective (1 ) is to increase morphological alignment without affecting compression. To confirm and quantify this effect in the default MinGram algorithm, we compare the default Unigram log-probability score tiebreak against two controls while keeping both the primary minimum token count objective fixed. 7 shows that when replacing the token log-probability scores with random values, MorphAlign Score decreases to that of PathPiece. Furthermore, when we invert the term to prefer lower-probability paths, the MorphAlign Score decreases even more to the lowest among all methods. Compression is identical across all three MinGram policies by construction because they all optimize the same minimum-token-count objective. This result shows that the Unigram objective, despite being a secondary tie-breaker term, still has a large effect on the chosen segmentation.

11 Rényi Entropy Diagnostic↩︎

¿tbl:tab:renyi-entropy? reports a Rényi-efficiency diagnostic using the definition of [31] and the \(\alpha = 3\) setting used by [32]: \(H_3 / \log_2 |V_{\mathrm{used}}|\), where \(V_{\mathrm{used}}\) is the nonzero vocabulary on the held-out evaluation corpus. This diagnostic measures how uniformly a tokenizer uses its active vocabulary, rather than how many tokens it emits. We use it only as an intrinsic probe; [32] show that Rényi efficiency is not a reliable standalone proxy for downstream quality. BPE has the highest held-out Rényi-3 efficiency in every language, with ConvexTok consistently second. MinGram-PP, MinGram and PathPiece-BPE lie in a narrow band just below these.

3pt

12 Examples of rare tokens↩︎

¿tbl:tab:undertrained-token-examples? shows examples of the tokens seen at most 718 times in the full ClimbMix training corpus, based on a frequency threshold of \(10^{-7}\). This corresponds to those shown in the rare token count column in 4. Results show interesting similarities between ConvexTok, PathPiece, and MinGram-PP, and show that the default MinGram tokenizer resulted in zero never-seen tokens in this cross-corpus setting, and its 10th example falls above the threshold. We also note that a few tokens like appear in the default Unigram tokenizer vocabulary, caused by their last-minute resegmentation into .

3pt

References↩︎