# Unigram tokenization

> Unigram tokenization (Kudo 2018) scores a segmentation by a product of independent piece probabilities. EM fits them, pruning drops the 20–25% of pieces whose removal costs the least likelihood, Viterbi decodes, and sampling from P(x|X)^α gives subword regularization.

Source: https://www.mlfoundry.in/learn/unigram-tokenization  
Section: Deep Learning › Large Language Models (LLMs)  
Level: advanced · 15 min read · updated 2026-10-13

**Unigram tokenization:** is the subword method of Taku Kudo, "Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates" (ACL 2018). A vocabulary $V$ of pieces carries probabilities $p(x)$ that sum to 1. A segmentation $\mathbf x=(x_1,\dots,x_M)$ of a string $X$ has probability $P(\mathbf x)=\prod_i p(x_i)$, with the pieces treated as independent. Encoding takes the most probable segmentation by **Viterbi**. Training alternates **EM** re-estimation of $p$ with **pruning** the pieces whose removal loses the least likelihood, starting from a large seed vocabulary. Because the model is probabilistic, segmentations can also be **sampled**. Training a translation model on sampled segmentations is what Kudo called *subword regularization*.

**Byte-pair encoding (BPE)** and **WordPiece** are deterministic: a word always gets the same pieces. Kudo's starting point was that the same text admits many segmentations. `Hello world` could be `Hell·o world` or `H·ello world`, and a model that only ever sees one of them learns nothing about the others. Showing the network several segmentations of each sentence works like data augmentation. It makes the model more robust to segmentation noise, which matters most in low-resource and out-of-domain translation, where the paper reported its largest gains. BPE has no probabilities to sample from, so Kudo needed a tokenizer that is a proper probability model over segmentations. The unigram language model is the simplest one.

The direction of construction is also reversed. BPE and WordPiece build *bottom-up*, starting from characters and adding merges. The unigram method works *top-down*. It starts with far too many candidate pieces and deletes the least useful until the target size is reached. The **SentencePiece** library, which Kudo released with Richardson the same year, uses the unigram model by default.

## The model and its decoder

$$
P(\mathbf x)=\prod_{i=1}^{M}p(x_i),\qquad \sum_{x\in V}p(x)=1,\qquad \mathbf x^\ast=\arg\max_{\mathbf x\in S(X)}P(\mathbf x)
$$

- $S(X)$: all segmentations of $X$ into vocabulary pieces; exponentially many, up to $2^{n-1}$ for $n$ characters
- $p(x)$: probability of piece x, independent of its neighbours (a unigram language model)
- $\mathbf x^\ast$: the Viterbi segmentation, used when encoding at inference time

The pieces of $X$ form a **lattice**. Nodes are the character boundaries $0,\dots,n$, and every vocabulary piece $X[i{:}j]$ is an edge from $i$ to $j$ with weight $\log p$. A segmentation is a path from $0$ to $n$, and its log-probability is the sum of its edge weights. The best path is a one-line dynamic program:

$$
\text{best}[0]=0,\qquad \text{best}[j]=\max_{i<j,\;X[i:j]\in V}\Big(\text{best}[i]+\log p\big(X[i{:}j]\big)\Big)
$$

- $\text{best}[j]$: log-probability of the best segmentation of the prefix $X[0{:}j]$; a back-pointer to the argmax $i$ recovers the path
- $O(nL)$: cost, with $L$ the longest piece (SentencePiece caps pieces at 16 characters by default)

Replace max by log-sum-exp and the same recursion becomes the **forward algorithm**. It gives $\log\sum_{\mathbf x\in S(X)}P(\mathbf x)$, the marginal likelihood of the string. A matching backward pass gives the posterior probability of every edge. Training and sampling both need these.

## Training: EM, then prune

For a fixed vocabulary, the segmentations are hidden variables, and the corpus log-likelihood sums over them:

$$
\mathcal L=\sum_{s=1}^{|D|}\log P\big(X^{(s)}\big)=\sum_{s=1}^{|D|}\log\!\!\sum_{\mathbf x\in S(X^{(s)})}\!\!P(\mathbf x),\qquad p_{\text{new}}(x)=\frac{\mathbb E[c(x)]}{\sum_{y\in V}\mathbb E[c(y)]}
$$

- $D$: the training corpus, in practice word types weighted by their counts
- $\mathbb E[c(x)]$: E-step: expected number of times piece $x$ is used, summed over all segmentations weighted by their posterior (forward–backward)
- $p_{\text{new}}$: M-step: normalise the expected counts. Each EM round cannot decrease the likelihood

EM fits the probabilities but cannot choose the vocabulary. Kudo handles that greedily. For each piece $x_i$, define $\text{loss}_i$ as how much $\mathcal L$ drops when $x_i$ is removed and its probability mass is redistributed. Sort by loss, keep the top $\eta$ (80% in the paper), and run EM again.

**The vocabulary loop (Kudo 2018, as implemented in SentencePiece)**

1. **Seed.** Build a large initial vocabulary from all characters and the most frequent substrings, found with an enhanced suffix array. SentencePiece's default seed size is 1,000,000 pieces.
2. **EM.** Fix the vocabulary and re-estimate $p(x)$ with a few EM iterations over the lattices of the corpus.
3. **Score.** Compute $\text{loss}_i=\mathcal L(V)-\mathcal L(V\setminus\{x_i\})$ for every piece. SentencePiece approximates it by re-segmenting each occurrence of $x_i$ with the remaining pieces.
4. **Prune.** Keep the top $\eta$ of pieces by loss, 80% in the paper and `shrinking_factor=0.75` in SentencePiece. Single characters are always kept, so every string remains encodable.
5. **Repeat** steps 2–4 until $|V|$ reaches the target, for example 32,000, then run a final EM.

> Figure: Top: unigram training runs in the opposite direction to BPE. It starts from a seed vocabulary of every character plus the most frequent substrings, fits piece probabilities by EM (forward–backward expected counts, then renormalisation), and deletes the pieces whose removal costs the least likelihood. Single characters always survive. The loop repeats until the target size is reached. Bottom: inference on the lattice of relating, using the toy vocabulary from the interactive figure. The Viterbi path relat·ing (log P = −7.28) narrowly beats re·lating (−7.40). Their posteriors over all 58 segmentations are 0.457 and 0.406. Subword regularization samples from P^α instead of always taking the top path.

## Subword regularization: sampling segmentations

$$
P(\mathbf x\mid X)\approx\frac{P(\mathbf x)^{\alpha}}{\sum_{\mathbf x'\in S_\ell(X)}P(\mathbf x')^{\alpha}}
$$

- $\alpha$: smoothing: $\alpha\to0$ is uniform over segmentations, $\alpha=1$ is the model posterior, and $\alpha\to\infty$ always returns Viterbi
- $S_\ell(X)$: the $\ell$-best segmentations, or all of $S(X)$ when $\ell=\infty$
- $\ell=\infty$: exact sampling over the whole lattice by **forward-filtering backward-sampling**: run the forward pass with weights $\alpha\log p$, then walk back from $n$, choosing each incoming edge with probability $\propto e^{\text{fwd}[i]+\alpha\log p}$

In training, every sentence is re-segmented each time it is drawn into a mini-batch. The encoder and decoder see `relat·ing` once and `re·lating` the next time, and occasionally `re·l·at·ing`. At test time, decoding uses Viterbi again, or the paper's $n$-best variant, which translates several top segmentations and keeps the best-scoring output. With SentencePiece this is two arguments: `enable_sampling=True, alpha=0.1, nbest_size=-1`, where $-1$ means $\ell=\infty$. The BPE counterpart came later as BPE-dropout (Provilkov, Emelianenko and Voita, ACL 2020), which randomly skips merges.

**Settings and where it is used**

- **Paper:** Kudo, "Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates", ACL 2018
- **Pruning:** keep the top $\eta=80\%$ by loss per round (paper); `shrinking_factor=0.75` in SentencePiece
- **Seed:** all characters plus frequent substrings from a suffix array; SentencePiece `seed_sentencepiece_size=1000000`
- **Piece length:** SentencePiece `max_sentencepiece_length=16` by default
- **Sampling:** `nbest_size` = $\ell$ ($-1$ for the full lattice), `alpha` = $\alpha$
- **Models:** **T5** (32,000 pieces), **ALBERT** (30,000), XLNet (32,000): SentencePiece unigram vocabularies
- **Evidence:** Bostrom & Durrett, "Byte Pair Encoding is Suboptimal for Language Model Pretraining" (Findings of EMNLP 2020): unigram segmentations align better with morphology, and models pretrained on them matched or beat BPE on downstream tasks

> Figure: A toy unigram model with 46 pieces: all 26 letters plus 20 longer pieces, with pseudo-counts that sum to 361. Every vocabulary piece inside the word is a bar labelled with its log-probability, and the numbers above the boundaries are the Viterbi scores best[j]. relating (the default) has 20 lattice arcs and 58 segmentations, with log Σ P = −6.495. The Viterbi path is relat·ing (−7.278), but re·lating (−7.396) is close: their posteriors are 0.4572 and 0.4064, then re·lat·ing 0.0675 and rel·at·ing 0.0507. At the default α = 0.2 these flatten to 0.1013, 0.0989, 0.0691 and 0.0652. Only 1 of the 12 seeded draws is the Viterbi path, and 7 of them are distinct. α = 0 gives every segmentation 1/58 = 0.0172, and α = 2 sharpens the top two to 0.5481 and 0.4331. unrelated is unambiguous: un·related has posterior 0.9088, which falls to 0.1187 at α = 0.2 and rises to 0.9972 at α = 2, where all 12 draws are un·related. Click a row or a highlight button to outline that segmentation in the lattice.

## Worked example: Viterbi, EM and pruning by hand

Use the figure's vocabulary: $\log p(\texttt{r})=-3.943$, $\log p(\texttt{re})=-2.200$, $\log p(\texttt{rel})=-4.097$, $\log p(\texttt{a})=-3.809$, $\log p(\texttt{relat})=-4.790$, $\log p(\texttt{relate})=-4.279$ and $\log p(\texttt{related})=-4.097$. Run Viterbi on `related`:

Viterbi on “related” (log-probabilities in nats, computed in Python)

| j | prefix | best last piece | best[j] |
| --- | --- | --- | --- |
| 1 | r | r | −3.943 |
| 2 | re | re | −2.200 |
| 3 | rel | rel | −4.097 |
| 4 | rela | a (after rel) | −4.097 − 3.809 = −7.907 |
| 5 | relat | relat | −4.790 |
| 6 | relate | relate | −4.279 |
| 7 | related | related | −4.097 |

**From one word to the training loop**

1. **Decode.** At $j=7$ the candidates are `related` $(-4.097)$, `relat`+`ed` $(-4.790-2.334=-7.124)$, `relate`+`d` $(-8.559)$, `rel`+`ated` $(-8.600)$ and `r`+`elated` $(-8.733)$. Viterbi keeps the single piece.
2. **Posterior.** The forward algorithm over all 35 segmentations gives $\log P(X)=-4.003$, so $P(\texttt{related}\mid X)=e^{-4.097+4.003}=0.9106$, and `relat·ed` gets $0.0441$.
3. **E-step** on the corpus `unrelated` ×4, `related` ×6, `relating` ×3, whose log-likelihood is $\mathcal L=-69.464$. The expected count of `related` is 9.106 out of 21.501 piece uses: almost $6\cdot0.9106$ from `related` plus $4\cdot0.9088$ from `un·related`, plus a little from `u·n·related`.
4. **M-step.** $p(\texttt{related})$ goes from $6/361=0.0166$ to $9.106/21.501=0.4235$. The 16 pieces that appear in none of these three words drop to zero, and one EM step raises $\mathcal L$ to $-28.782$.
5. **Prune** (table below). Remove each piece in turn, renormalise the rest, and recompute $\mathcal L$. A negative loss means the corpus is more likely *without* the piece, because its probability mass was wasted on these words.

Pruning loss on the 3-word corpus, with probabilities renormalised after removal. Ranks 8–14 (elated, ated, relate, ng, ting, el, ti) are omitted; all are kept. Computed in Python.

| piece | loss = L(V) − L(V∖{x}) | η = 80% of 20 multi-character pieces: keep 16 |
| --- | --- | --- |
| related | 23.605 | keep (rank 1) |
| un | 22.771 | keep (rank 2) |
| relat | 2.132 | keep (rank 3) |
| lating | 1.456 | keep (rank 4) |
| ing | 0.774 | keep (rank 5) |
| lat | 0.043 | keep (rank 6) |
| rel | −0.028 | keep (rank 7) |
| re | −0.446 | keep (rank 15) |
| late | −0.463 | keep (rank 16, the last kept) |
| ate | −0.846 | drop (rank 17) |
| at | −0.982 | drop (rank 18) |
| in | −1.535 | drop (rank 19) |
| ed | −1.551 | drop (rank 20) |

Notice that `ed` is pruned even though it has the second-largest prior count (35). On this corpus Viterbi never uses it, because `related` covers that ending. Pruning judges a piece by what the corpus *loses* without it, not by how frequent it looks.

```python
import math, random
from collections import defaultdict

def lattice(word, logp, max_len=16):
    """All (start, end, piece) arcs whose piece is in the vocabulary."""
    return [(i, j, word[i:j]) for i in range(len(word))
            for j in range(i + 1, min(len(word), i + max_len) + 1) if word[i:j] in logp]

def viterbi(word, logp):
    best, back = [0.0] + [-math.inf] * len(word), [0] * (len(word) + 1)
    for i, j, p in sorted(lattice(word, logp), key=lambda a: a[1]):
        if best[i] + logp[p] > best[j]:
            best[j], back[j] = best[i] + logp[p], i
    pieces, j = [], len(word)
    while j > 0:
        pieces.append(word[back[j]:j]); j = back[j]
    return pieces[::-1], best[-1]

def logaddexp(a, b):
    if a == -math.inf: return b
    m = max(a, b); return m + math.log(math.exp(a - m) + math.exp(b - m))

def forward_backward(word, logp, alpha=1.0):
    arcs, n = lattice(word, logp), len(word)
    fwd, bwd = [0.0] + [-math.inf] * n, [-math.inf] * n + [0.0]
    for i, j, p in sorted(arcs, key=lambda a: a[1]):
        fwd[j] = logaddexp(fwd[j], fwd[i] + alpha * logp[p])
    for i, j, p in sorted(arcs, key=lambda a: -a[0]):
        bwd[i] = logaddexp(bwd[i], alpha * logp[p] + bwd[j])
    return arcs, fwd, bwd

def em_step(corpus, logp):
    """E: expected piece counts over all segmentations. M: renormalise."""
    counts, loglik = defaultdict(float), 0.0
    for word, freq in corpus.items():
        arcs, fwd, bwd = forward_backward(word, logp)
        logZ = fwd[-1]; loglik += freq * logZ
        for i, j, p in arcs:
            counts[p] += freq * math.exp(fwd[i] + logp[p] + bwd[j] - logZ)
    total = sum(counts.values())
    return {p: math.log(c / total) for p, c in counts.items() if c > 0}, loglik

def sample(word, logp, alpha, rng):
    """Forward-filtering backward-sampling: an exact draw from P(x|X)^alpha / Z."""
    arcs, fwd, _ = forward_backward(word, logp, alpha)
    pieces, j = [], len(word)
    while j > 0:
        cand = [(i, p) for i, jj, p in arcs if jj == j]
        w = [math.exp(fwd[i] + alpha * logp[p] - fwd[j]) for i, p in cand]
        i, p = rng.choices(cand, weights=w)[0]
        pieces.append(p); j = i
    return pieces[::-1]

counts = {c: 2 for c in "abcdefghijklmnopqrstuvwxyz"}
counts.update(e=12, a=8, t=9, n=7, r=7, i=7, l=5, d=5, u=3, g=3, s=6, o=6,
              un=30, re=40, rel=6, relat=3, relate=5, related=6, late=8, lat=4, ate=14, at=20,
              ated=4, ed=35, el=5, ing=30, ng=4, ti=6, ting=5, lating=2, elated=3)
counts["in"] = 25
T = sum(counts.values())
logp = {p: math.log(c / T) for p, c in counts.items()}           # 46 pieces, T = 361

print(viterbi("relating", logp))     # (['relat', 'ing'], -7.2779...)
print(viterbi("unrelated", logp))    # (['un', 'related'], -6.5848...)
rng = random.Random(0)
print([" ".join(sample("relating", logp, 0.2, rng)) for _ in range(4)])
# ['re lat i n g', 'rel at ing', 're l at ing', 'r el at ing']

corpus = {"unrelated": 4, "related": 6, "relating": 3}
new_logp, ll = em_step(corpus, logp)
print(round(ll, 3), len(new_logp))                  # -69.464 30   (16 unused pieces drop out)
print(round(math.exp(new_logp["related"]), 4))       # 0.4235
print(round(em_step(corpus, new_logp)[1], 3))        # -28.782

# The library version (not run here):
# import sentencepiece as spm
# spm.SentencePieceTrainer.train(input="corpus.txt", model_prefix="uni", vocab_size=32000,
#                                model_type="unigram")
# sp = spm.SentencePieceProcessor(model_file="uni.model")
# sp.encode("relating", out_type=str)                                   # Viterbi
# sp.encode("relating", out_type=str, enable_sampling=True, alpha=0.1, nbest_size=-1)
```

Unigram tokenization from scratch: lattice, Viterbi, forward–backward, one EM step, and forward-filtering backward-sampling (plain Python, run; outputs in comments). The SentencePiece calls at the end were not run here.

> **A probability model, not a merge list:** BPE's output is a fixed function of the merge order, so it has no notion of a second-best segmentation. A unigram tokenizer assigns a probability to *every* segmentation. That gives you Viterbi, $n$-best lists, marginal likelihoods and exact sampling from the same lattice and the same two dynamic programs. It also makes vocabulary selection a likelihood problem, which BPE and WordPiece only approximate greedily.

> **α is not a temperature you can set high for free:** Small $\alpha$ means aggressive regularization. At $\alpha=0.2$ the figure's `relating` returns its Viterbi path only 10% of the time, and draws like `r·e·l·a·ti·ng` appear. Each such draw is a longer sequence, and so a costlier training step, with tokens the model rarely sees at test time. Tune $\alpha$ (and $\ell$) on validation data. Turn sampling **off** for evaluation and inference, where you want the deterministic Viterbi output.

> **The independence assumption:** $P(\mathbf x)=\prod p(x_i)$ ignores context completely: `ing` is equally likely after `relat` and after `str`. This is deliberate. It keeps the lattice a simple path graph, so Viterbi, forward–backward and sampling stay linear in the string length. The downstream neural model, not the tokenizer, is responsible for modelling context.

**Strengths**

- Principled: vocabulary and probabilities chosen by corpus likelihood
- Multiple segmentations with probabilities: n-best, marginals, sampling
- Subword regularization improves robustness, especially for low-resource and out-of-domain data
- Linear-time Viterbi and FFBS on the lattice; default model in SentencePiece

**Limitations**

- Training is heavier than BPE: a large seed vocabulary and repeated EM over lattices
- Pruning is greedy and its loss is approximated in practice
- Sampling lengthens sequences and adds a hyperparameter (α, ℓ) to tune
- Context-free piece probabilities; segmentations can look odd for rare words

**Question:** In subword regularization with α → 0, what happens to the sampled segmentations?

- A. They always equal the Viterbi segmentation
- B. They become uniform over all segmentations in S(X), however improbable
- C. They follow the model posterior P(x | X) exactly
- D. Sampling becomes impossible because Z = 0

**Answer:** B. They become uniform over all segmentations in S(X), however improbable — $P(\mathbf x)^\alpha\to1$ for every segmentation, so each of the $|S(X)|$ candidates gets probability $1/|S(X)|$, which is $1/58=0.0172$ for `relating` in the figure. $\alpha=1$ gives the posterior, and $\alpha\to\infty$ concentrates on Viterbi.

**Question:** Why does unigram training always keep single-character pieces when pruning?

- A. They have the highest loss
- B. So that every string in the training alphabet still has at least one segmentation, avoiding out-of-vocabulary failures
- C. Because EM cannot assign them probability
- D. To make the vocabulary size a power of two

**Answer:** B. So that every string in the training alphabet still has at least one segmentation, avoiding out-of-vocabulary failures — If a character were pruned, any word containing it would have no path through the lattice. Keeping all single characters guarantees $S(X)\neq\varnothing$ for any text over the training alphabet. Characters outside it are handled by `<unk>` or by **SentencePiece**'s byte fallback.

**Key points**

- Unigram tokenization (Kudo, ACL 2018): $P(\mathbf x)=\prod_i p(x_i)$ over pieces. Encoding takes the Viterbi path through the lattice of every vocabulary piece in the string, in $O(nL)$.
- Training is top-down: a large seed vocabulary, EM with forward–backward expected counts, then keep the top 80% (SentencePiece: 75%) of pieces by likelihood loss. Single characters always survive.
- Subword regularization samples $\mathbf x\sim P(\mathbf x\mid X)^\alpha/Z$ every time a sentence is seen, exactly over the whole lattice by forward-filtering backward-sampling.
- α interpolates between a uniform distribution (α → 0), the posterior (α = 1) and Viterbi (α → ∞). Use sampling only in training.
- It is the default model in SentencePiece and is used by T5, ALBERT and XLNet.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
