The same abc, a different split: training and encoding with Unigram

For the same input abc, the initial model assigns 81% of the segmentation weight to the single-piece path abc. After training, the highest-scoring split is a | bc. The text stays the same; the piece-probability table shared by the entire corpus changes.

That makes “Unigram tokenizes using probabilities” concrete: where do the statistics come from when the segmentations themselves are unknown? Once the table is trained, encoding faces a second problem: finding the best complete segmentation under that table.

The earlier BPE implementation starts with base units and adds merge rules. Here, training starts with a larger candidate set, updates scores, and removes pieces. Deterministic encoding also uses a different criterion: BPE executes learned merge priorities; Unigram compares scores of complete paths.

“Unigram” means each piece uses its own probability independently of the preceding piece. A piece can contain several characters. This small tokenizer model is separate from the Transformer’s next-token prediction model. The original paper, §3.2, describes the path-scoring and vocabulary-training framework. SentencePiece is a toolkit supporting Unigram, BPE, and other algorithms; using it does not by itself identify the chosen algorithm.

Corpus, vocabulary, and segmentations count different things

The corpus is specified in advance. Repeated texts are represented by frequencies: 8 distinct texts and 104 samples.

Normalization is identity, the dummy initial prefix is disabled, and each sample is segmented within its own boundaries. Collecting unique contiguous substrings of length 1–3 gives:

a  b  c  ab  bc  ca  abc  bca  cab

Each of these 9 candidate pieces initially gets p(t) = 1/9; the probabilities sum to 1. The base characters a, b, c are protected, and the target is 6 ordinary pieces. The substring limit, uniform initialization, protected set, and target size are settings of this experiment.

The vocabulary specifies available pieces, but does not yet choose a segmentation for each text. abc has four complete valid paths:

a | b | c
a | bc
ab | c
abc

Thus 8 counts distinct texts, 9 counts vocabulary candidates, and 4 counts segmentations of this text. The initial 1/9 comes from the whole vocabulary, not from the four paths. ca, bca, cab remain entries in that global table even though this input cannot use them.

★ The first E step: piece probabilities become path shares

Five symbols, each with its own scope:

Multiply the probabilities of the pieces along a path. If a piece occurs twice, multiply its probability twice:

w(s) = ∏ p(t), once per occurrence along the path
Z(x) = Σ w(s), over valid paths for x
q(s∣x) = w(s) / Z(x)

For the four initial segmentations:

The denominator is Z(abc) = (1 + 9 + 9 + 81) / 729 = 100/729. Equal piece probabilities do not give equal path weights: the paths multiply different numbers of factors.

81% is the single-piece path’s share given the input abc; the piece probability p(abc) is still 1/9. It does not mean that 81% of the corpus consists of abc, either. The path share is normalized within one input; the piece probability belongs to the global vocabulary.

How much does one text contribute to a count?

With no single known segmentation, distribute counts according to q. The four paths contain a 1, 1, 0, and 0 times:

Expected count of a in one abc
  = 0.01 × 1 + 0.09 × 1 + 0.09 × 0 + 0.81 × 0
  = 0.10

Contribution from 12 copies of abc = 12 × 0.10 = 1.20

The fraction is a weighted statistic; an actual segmentation still contains an integer number of tokens. A path such as a / bc / a contributes 2q to the count of a, not merely q for “being present.”

One p table processes the entire corpus

The next text, ab, has its own denominator:

a | b: w = 1/81
ab:    w = 1/9
Z(ab) = 10/81

q(a | b) = 0.1
q(ab)    = 0.9
24 copies of ab contribute 24 × 0.9 = 21.6 occurrences of ab

Keep p fixed throughout the E step. Each text gets its own w, Z, and q; their contributions are accumulated into C. The first pass produces:

For ab, “other contributions” are ordinary computed counts: 21.6 from ab + 0.664207 from abca + 0.18 from cab = 22.444207. Each uses its own input’s weighted paths. In abca, the paths containing ab are ab / c / a and ab / ca.

Let f(x) be the text frequency and Nₜ(s) the number of occurrences of t in path s:

C(t) = Σ texts x f(x) × Σ paths s q(s∣x) × Nₜ(s)

The total expected token count is 114.614022, which can exceed 104 samples because one text can produce several tokens. Displayed values are rounded; computation uses full precision.

★ M: counts become the next probability table

The teaching implementation uses the classical maximum-likelihood update:

p_new(t) = C(t) / Σ pieces u C(u)

p_new(a)  = 21.096015 / 114.614022 ≈ 0.184061
p_new(ab) = 23.524207 / 114.614022 ≈ 0.205247
p_new(bc) = 29.946421 / 114.614022 ≈ 0.261281

The normalization follows from an optimization problem. E has fixed the path shares. Taking the expected complete-segmentation log score and collecting terms by piece gives Q(p) = Σₜ C(t) ln p(t). M maximizes it subject to Σₜ p(t) = 1.

Introduce a multiplier λ:

J = Σₜ C(t) ln p(t) + λ(1 − Σₜ p(t))

∂J/∂p(t) = C(t)/p(t) − λ = 0
           → p(t) = C(t)/λ

Σₜ p(t) = 1 → λ = Σₜ C(t)
           → p_new(t) = C(t)/Σᵤ C(u)

The next E step now has a new table. Reset C to zero and recompute all paths for the same corpus using the new p. Do not update p immediately after abc and then process ab with a different parameter version.

For the second pass’s a / bc, w ≈ 0.1840613772 × 0.2612806017 = 0.0480916674. Dividing by the new Z(abc) ≈ 0.1632945529 gives about 29.4509%. The input has not changed; contributions from other texts have changed its segmentation distribution through the shared parameters.

Pruning asks what is lost when a piece disappears

EM updates probabilities; shrinking the vocabulary takes another operation. This experiment performs two E→M updates, temporarily disables each removable piece in turn, and compares the corpus loss increase:

L = −Σ texts x f(x) ln Z(x)
Δₜ = L(with t temporarily disabled) − L(original model)

During a trial, freeze all other scores; do not retrain or renormalize them. This measures the path weight lost when the relevant edges disappear from the original graph. The remaining values are used as fixed weights at this point. Renormalize only after selecting and permanently removing a piece.

bca affects only the two copies of abca, removing the path a / bca. Their denominator drops from about 0.0321886861 to 0.0320842005, giving 2 ln(Z_before / Z_after) ≈ 0.00650263, the smallest increase this round.

Here the lowest p happens to coincide with the lowest Δ, but that coincidence is not the pruning rule. Consider a separate constructed table: p(a)=p(b)=0.00001, p(ab)=0.001, p(c)=p(d)=0.4, p(cd)=0.01, p(x)=0.18898. It sums to 1. Let the corpus contain one ab and one cd:

ab has lower probability, but its alternative a / b is extremely poor. cd has a strong alternative. Removal cost depends on text frequencies, existing paths, and replacement paths. A base character with no alternative or fallback must be protected to keep its texts segmentable; this experiment protects a, b, c.

The full training schedule has four rounds:

Eight updates and three removals are teaching settings; reaching the target size does not imply full convergence. SentencePiece 0.2.1’s official trainer includes low-expected-frequency filtering and Digamma updates in M, and uses its own pruning approximation. The C/total update and frozen-score removal trials here make the arithmetic inspectable. The official functions are RunMStep and PruneSentencePieces in unigram_model_trainer.cc.

What becomes fixed: pieces, scores, and IDs

After eight updates:

<unk> separately receives ID 0. The teaching code assigns ordinary IDs in retained-piece order; IDs are not probability ranks. A real model also needs piece types and normalization settings.

Scores in this table are simply ln(p). Logarithms convert path products into sums and are strictly increasing, so the highest product and the highest log score identify the same path. They also avoid underflow from long products: 0.01 ** 200 becomes 0.0 in Python floating-point arithmetic, while 200 × ln(0.01) ≈ −921.034 remains representable. For negative scores, larger is still better.

Now p(a)p(bc) ≈ 0.074826 exceeds p(abc) ≈ 0.023415, so the highest-scoring split of the same abc is a / bc. Encoding reads this fixed table. A new input does not trigger E, M, or pruning.

The training chapter contains 60 steps covering all four rounds. Encoding then uses that training result for abcabc. Two additional cases use a manual probability table as a separate comparison.

★ The final c: finding the best complete path

With the vocabulary fixed, match every available piece at every input position. A position is a boundary between characters. An edge from j to i represents text[j:i]. Only a continuous path from 0 to the end forms a complete segmentation.

abcabc has 16 valid complete paths. The animation enumerates them for verification. To find the highest score, Viterbi dynamic programming reuses prefix results:

best[0] = 0
All other best entries = −∞

best[i] = max { best[j] + ln p(text[j:i]) }
          over valid pieces ending exactly at i

best[i] stores the highest log score covering the first i characters. prev[i] records the boundary the winning path came from. After all positions are processed, follow prev backward from the end.

Why is one best prefix per boundary enough? Two prefixes reaching the same boundary have the same available continuations. Unigram’s future piece scores do not depend on how those prefixes were segmented. Appending the same suffix adds the same score, so a worse prefix cannot overtake the better one. The comparison concerns complete prefix scores, not the largest immediate piece probability.

Before processing the final c, three relevant prefix results are already stored:

Only c, bc, abc end at position 6:

Final c:   best[5] + ln p(c)   ≈ −6.3103
Final bc:  best[4] + ln p(bc)  ≈ −5.1852  ← largest
Final abc: best[3] + ln p(abc) ≈ −6.3470

Store best[6] ≈ −5.1852, prev[6] = 4, then backtrace:

6 ← 4 ← 3 ← 1 ← 0
  bc   a   bc   a

Reverse: a | bc | a | bc
IDs:     [1, 5, 1, 5]

“The preceding b has been processed” means best[5] has been computed; it does not force the final path through 5. The winner can go directly from 4 to 6. Best prefixes at different boundaries remain available, and backtracking determines the final token sequence. The absent whole piece abcabc cannot be an edge, but existing pieces still cover the entire input.

Training’s E step needs weighted contributions from all paths; deterministic encoding needs one highest-scoring path. Efficient E computation can use forward/backward algorithms with log-sum-exp. Viterbi’s max cannot directly replace the expectation calculation.

Decoding and byte fallback: four IDs restore one character

Ordinary decoding looks up IDs:

[1, 5, 1, 5] → ['a', 'bc', 'a', 'bc'] → 'abcabc'

The IDs already specify pieces. No Viterbi search or rescoring is needed. General models also process whitespace markers, dummy prefixes, and related settings. If normalization discarded information, decoding cannot recover it; this ASCII teaching model uses identity and round-trips exactly.

Byte fallback is checked separately using a real SentencePiece 0.2.1 Unigram model. The small corpus includes “你好” but not 😊, and training enables byte_fallback=True. Its IDs belong to this separate model and cannot be mixed with IDs 1–6 above.

Input:      你好😊
Normalized: ▁你好😊
Pieces:     ▁, 你, 好, <0xF0>, <0x9F>, <0x98>, <0x8A>
IDs:        [259, 267, 268, 243, 162, 155, 141]

▁ is the U+2581 whitespace marker; its initial occurrence comes from the dummy-prefix setting. This model reserves 256 BYTE entries covering values 0–255. An unknown character therefore needs neither newly invented IDs nor another BPE pass during fallback.

IDs 0, 1, and 2 are <unk>, <s>, </s>; BYTE entries start at 3, so this model happens to have ID = byte value + 3. That is this vocabulary’s numbering arrangement. The general operation is still a lookup.

Decoding first restores consecutive BYTE pieces to raw bytes:

F0       9F       98       8A
11110000 10011111 10011000 10001010

The leading 11110xxx indicates four bytes in total; the next three 10xxxxxx values are continuation bytes. UTF-8 identifies character boundaries; IDs need no extra “group of four” marker. All four IDs decode to 😊. In this library experiment, decoding only the final three IDs produces ���. Rendering one character does not erase the four token positions processed by the model.

Experimental verification

Training on the corpus and settings above yields probabilities that sum to 1 after every M update; loss does not increase with a fixed vocabulary. The removal order is bca → ca → cab.

Encoding is checked exhaustively on all 363 strings of length 1–5 over a, b, c. Each is encoded with both the trained vocabulary and the animation’s manual comparison vocabulary, giving 726 vocabulary/input cases. Full enumeration, Viterbi dynamic programming, and Hugging Face Unigram produce matching best scores. Tied optima are checked by score and reconstructed text, without requiring identical path choices.

The byte-fallback experiment uses SentencePiece 0.2.1: “你好😊” encodes to the seven IDs above, and decoding the complete sequence restores the original text.

The change from an initial 81% share for whole abc to a final best path a / bc happens in the learned, shared probability table. Once that table is fixed, encoding searches for a complete path and decoding retrieves contents by ID. Those three moments give probabilities, segmentations, and IDs distinct jobs.