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.

15 min read1137 wordsadvanced0 viewsupdated 2026-10-13

Definition

Unigram tokenization is the subword method of Taku Kudo, "Subword Regularization: Improving Neural Network Translation Models with Multiple Subword Candidates" (ACL 2018). A vocabulary VV of pieces carries probabilities p(x)p(x) that sum to 1. A segmentation x=(x1,…,xM)\mathbf x=(x_1,\dots,x_M) of a string XX has probability P(x)=∏ip(xi)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 pp 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(x)=∏i=1Mp(xi),∑x∈Vp(x)=1,x∗=arg⁡max⁡x∈S(X)P(x)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)S(X)
all segmentations of XX into vocabulary pieces; exponentially many, up to 2n−12^{n-1} for nn characters
p(x)p(x)
probability of piece x, independent of its neighbours (a unigram language model)
x∗\mathbf x^\ast
the Viterbi segmentation, used when encoding at inference time

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

best[0]=0,best[j]=max⁡i<j,  X[i:j]∈V(best[i]+log⁡p(X[i:j]))\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)
best[j]\text{best}[j]
log-probability of the best segmentation of the prefix X[0:j]X[0{:}j]; a back-pointer to the argmax ii recovers the path
O(nL)O(nL)
cost, with LL 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⁡∑x∈S(X)P(x)\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:

L=∑s=1∣D∣log⁡P(X(s))=∑s=1∣D∣log⁡ ⁣ ⁣∑x∈S(X(s)) ⁣ ⁣P(x),pnew(x)=E[c(x)]∑y∈VE[c(y)]\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)]}
DD
the training corpus, in practice word types weighted by their counts
E[c(x)]\mathbb E[c(x)]
E-step: expected number of times piece xx is used, summed over all segmentations weighted by their posterior (forward–backward)
pnewp_{\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 xix_i, define lossi\text{loss}_i as how much L\mathcal L drops when xix_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. 1Seed. 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. 2EM. Fix the vocabulary and re-estimate p(x)p(x) with a few EM iterations over the lattices of the corpus.
  3. 3Score. Compute lossi=L(V)−L(V∖{xi})\text{loss}_i=\mathcal L(V)-\mathcal L(V\setminus\{x_i\}) for every piece. SentencePiece approximates it by re-segmenting each occurrence of xix_i with the remaining pieces.
  4. 4Prune. 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. 5Repeat steps 2–4 until ∣V∣|V| reaches the target, for example 32,000, then run a final EM.
TRAINING · top-down: start big, prune (Kudo 2018)corpuspre-split wordswith counts(▁ marks spaces)seed vocabularyall characters +frequent substrings(1M in SentencePiece)EM on p(x)E: expected piece countsby forward–backwardM: p(x) = E[c(x)] / Σ E[c]prune by losslossᵢ = L(V) − L(V \ {xᵢ})keep the top 75–80%single characters always keptrepeat until |V| = target (e.g. 32,000), then a final EMINFERENCE · P(x) = Πᵢ p(xᵢ) over a lattice of every piece in the wordrerelrelatlatatlatinginingrelatingsingle characters run along the baseline (not drawn as arcs)Viterbi: relat · ing−4.79 − 2.49 = −7.28runner-up: re · lating−2.20 − 5.20 = −7.40posterior over all 58 segmentations: 0.457 vs 0.406decode: x* = argmax P(x), dynamic programming O(n·L)train-time sampling: x ~ P(x | X)^α / Zα → 0 flattens, α = 1 is the posterior, α → ∞ is Viterbifresh segmentation every time a sentence is seen
fig.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(x∣X)≈P(x)α∑x′∈Sℓ(X)P(x′)αP(\mathbf x\mid X)\approx\frac{P(\mathbf x)^{\alpha}}{\sum_{\mathbf x'\in S_\ell(X)}P(\mathbf x')^{\alpha}}
α\alpha
smoothing: α→0\alpha\to0 is uniform over segmentations, α=1\alpha=1 is the model posterior, and α→∞\alpha\to\infty always returns Viterbi
Sℓ(X)S_\ell(X)
the ℓ\ell-best segmentations, or all of S(X)S(X) when ℓ=∞\ell=\infty
ℓ=∞\ell=\infty
exact sampling over the whole lattice by forward-filtering backward-sampling: run the forward pass with weights αlog⁡p\alpha\log p, then walk back from nn, choosing each incoming edge with probability ∝efwd[i]+αlog⁡p\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 nn-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-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 η=80%\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-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
log P(x) = Σ log p(xᵢ) · |V| = 46 · “relating” has 58 segmentations · log Σ P(x) = −6.4950.00−3.94−2.20−4.10−7.91−4.79−8.73−7.46−7.28relatingr −3.94e −3.40l −4.28a −3.81t −3.69i −3.94n −3.94g −4.79relat −4.79rel −4.10re −2.20el −4.28lating −5.20lat −4.50at −2.89ting −4.28ti −4.10ing −2.49in −2.67ng −4.50numbers above the nodes: best[j] = maxᵢ best[i] + log p(w[i:j]) · Viterbi relat · ing (−7.28)#segmentationlog P(x)P(x | X)P^α / Z (α=0.20)1relat · ing−7.2780.45720.10132re · lating−7.3960.40640.09893re · lat · ing−9.1900.06750.06914rel · at · ing−9.4780.05070.06525re · l · at · ing−11.8600.00470.040512 samples from P^α / Z (forward-filter, backward-sample; seed 1): 1 Viterbi, 7 distinctr·e·l·a·ti·ngrel·at·ingrel·at·in·grelat·ingrel·a·tingrel·at·ingrel·a·tingrel·at·ingr·el·a·tingr·el·a·tingrel·at·in·gre·lat·ingα = 0: uniform over all 58 (0.0172 each) · α = 1: the model posterior · α → ∞: Viterbi only
word
highlight
fig.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(r)=−3.943\log p(\texttt{r})=-3.943, log⁡p(re)=−2.200\log p(\texttt{re})=-2.200, log⁡p(rel)=−4.097\log p(\texttt{rel})=-4.097, log⁡p(a)=−3.809\log p(\texttt{a})=-3.809, log⁡p(relat)=−4.790\log p(\texttt{relat})=-4.790, log⁡p(relate)=−4.279\log p(\texttt{relate})=-4.279 and log⁡p(related)=−4.097\log p(\texttt{related})=-4.097. Run Viterbi on related:

jprefixbest last piecebest[j]
1rr−3.943
2rere−2.200
3relrel−4.097
4relaa (after rel)−4.097 − 3.809 = −7.907
5relatrelat−4.790
6relaterelate−4.279
7relatedrelated−4.097
Viterbi on “related” (log-probabilities in nats, computed in Python)

From one word to the training loop

  1. 1Decode. At j=7j=7 the candidates are related (−4.097)(-4.097), relat+ed (−4.790−2.334=−7.124)(-4.790-2.334=-7.124), relate+d (−8.559)(-8.559), rel+ated (−8.600)(-8.600) and r+elated (−8.733)(-8.733). Viterbi keeps the single piece.
  2. 2Posterior. The forward algorithm over all 35 segmentations gives log⁡P(X)=−4.003\log P(X)=-4.003, so P(related∣X)=e−4.097+4.003=0.9106P(\texttt{related}\mid X)=e^{-4.097+4.003}=0.9106, and relat·ed gets 0.04410.0441.
  3. 3E-step on the corpus unrelated ×4, related ×6, relating ×3, whose log-likelihood is L=−69.464\mathcal L=-69.464. The expected count of related is 9.106 out of 21.501 piece uses: almost 6⋅0.91066\cdot0.9106 from related plus 4⋅0.90884\cdot0.9088 from un·related, plus a little from u·n·related.
  4. 4M-step. p(related)p(\texttt{related}) goes from 6/361=0.01666/361=0.0166 to 9.106/21.501=0.42359.106/21.501=0.4235. The 16 pieces that appear in none of these three words drop to zero, and one EM step raises L\mathcal L to −28.782-28.782.
  5. 5Prune (table below). Remove each piece in turn, renormalise the rest, and recompute L\mathcal L. A negative loss means the corpus is more likely without the piece, because its probability mass was wasted on these words.
pieceloss = L(V) − L(V∖{x})η = 80% of 20 multi-character pieces: keep 16
related23.605keep (rank 1)
un22.771keep (rank 2)
relat2.132keep (rank 3)
lating1.456keep (rank 4)
ing0.774keep (rank 5)
lat0.043keep (rank 6)
rel−0.028keep (rank 7)
re−0.446keep (rank 15)
late−0.463keep (rank 16, the last kept)
ate−0.846drop (rank 17)
at−0.982drop (rank 18)
in−1.535drop (rank 19)
ed−1.551drop (rank 20)
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.

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
1import math, random
2from collections import defaultdict
3
4def lattice(word, logp, max_len=16):
5 """All (start, end, piece) arcs whose piece is in the vocabulary."""
6 return [(i, j, word[i:j]) for i in range(len(word))
7 for j in range(i + 1, min(len(word), i + max_len) + 1) if word[i:j] in logp]
8
9def viterbi(word, logp):
10 best, back = [0.0] + [-math.inf] * len(word), [0] * (len(word) + 1)
11 for i, j, p in sorted(lattice(word, logp), key=lambda a: a[1]):
12 if best[i] + logp[p] > best[j]:
13 best[j], back[j] = best[i] + logp[p], i
14 pieces, j = [], len(word)
15 while j > 0:
16 pieces.append(word[back[j]:j]); j = back[j]
17 return pieces[::-1], best[-1]
18
19def logaddexp(a, b):
20 if a == -math.inf: return b
21 m = max(a, b); return m + math.log(math.exp(a - m) + math.exp(b - m))
22
23def forward_backward(word, logp, alpha=1.0):
24 arcs, n = lattice(word, logp), len(word)
25 fwd, bwd = [0.0] + [-math.inf] * n, [-math.inf] * n + [0.0]
26 for i, j, p in sorted(arcs, key=lambda a: a[1]):
27 fwd[j] = logaddexp(fwd[j], fwd[i] + alpha * logp[p])
28 for i, j, p in sorted(arcs, key=lambda a: -a[0]):
29 bwd[i] = logaddexp(bwd[i], alpha * logp[p] + bwd[j])
30 return arcs, fwd, bwd
31
32def em_step(corpus, logp):
33 """E: expected piece counts over all segmentations. M: renormalise."""
34 counts, loglik = defaultdict(float), 0.0
35 for word, freq in corpus.items():
36 arcs, fwd, bwd = forward_backward(word, logp)
37 logZ = fwd[-1]; loglik += freq * logZ
38 for i, j, p in arcs:
39 counts[p] += freq * math.exp(fwd[i] + logp[p] + bwd[j] - logZ)
40 total = sum(counts.values())
41 return {p: math.log(c / total) for p, c in counts.items() if c > 0}, loglik
42
43def sample(word, logp, alpha, rng):
44 """Forward-filtering backward-sampling: an exact draw from P(x|X)^alpha / Z."""
45 arcs, fwd, _ = forward_backward(word, logp, alpha)
46 pieces, j = [], len(word)
47 while j > 0:
48 cand = [(i, p) for i, jj, p in arcs if jj == j]
49 w = [math.exp(fwd[i] + alpha * logp[p] - fwd[j]) for i, p in cand]
50 i, p = rng.choices(cand, weights=w)[0]
51 pieces.append(p); j = i
52 return pieces[::-1]
53
54counts = {c: 2 for c in "abcdefghijklmnopqrstuvwxyz"}
55counts.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,
56 un=30, re=40, rel=6, relat=3, relate=5, related=6, late=8, lat=4, ate=14, at=20,
57 ated=4, ed=35, el=5, ing=30, ng=4, ti=6, ting=5, lating=2, elated=3)
58counts["in"] = 25
59T = sum(counts.values())
60logp = {p: math.log(c / T) for p, c in counts.items()} # 46 pieces, T = 361
61
62print(viterbi("relating", logp)) # (['relat', 'ing'], -7.2779...)
63print(viterbi("unrelated", logp)) # (['un', 'related'], -6.5848...)
64rng = random.Random(0)
65print([" ".join(sample("relating", logp, 0.2, rng)) for _ in range(4)])
66# ['re lat i n g', 'rel at ing', 're l at ing', 'r el at ing']
67
68corpus = {"unrelated": 4, "related": 6, "relating": 3}
69new_logp, ll = em_step(corpus, logp)
70print(round(ll, 3), len(new_logp)) # -69.464 30 (16 unused pieces drop out)
71print(round(math.exp(new_logp["related"]), 4)) # 0.4235
72print(round(em_step(corpus, new_logp)[1], 3)) # -28.782
73
74# The library version (not run here):
75# import sentencepiece as spm
76# spm.SentencePieceTrainer.train(input="corpus.txt", model_prefix="uni", vocab_size=32000,
77# model_type="unigram")
78# sp = spm.SentencePieceProcessor(model_file="uni.model")
79# sp.encode("relating", out_type=str) # Viterbi
80# 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.

Use when

  • +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

Avoid when

  • −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

Check yourself

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

Check yourself

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

Remember

  • ✓Unigram tokenization (Kudo, ACL 2018): P(x)=∏ip(xi)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)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 x∼P(x∣X)α/Z\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.
← back to Deep Learning roadmap