Greedy Coverage

We work on the same two corpora the merging pages use, so that nothing in the comparison is a difference of data. The small one is four words with their counts, low five times, lower twice, newest six times and widest three, sixteen occurrences in all. The large one is eighteen short sentences of ordinary English about reports and costs and analyses, 72 distinct words across 133 occurrences. Neither contains the sentence this section carries everywhere.

Dr. Alvarez didn't expect the low-cost re-analysis.

Each word is written out as its characters, and the last character of each word carries a mark saying a space follows it, which is what keeps a piece that ends a word apart from the same letters inside one. Counted that way the four words hold 79 positions, weighted by how often each word occurs, and the eighteen sentences hold 648. Those two numbers are what a vocabulary is being asked to cover, and they are the quantity every measurement below is a fraction of.

Merging scores a candidate by how many times two symbols sit next to each other, and it can only ever consider two symbols at a time, because that is what a merge is. On the eighteen sentences the winner of that contest is h followed by the marked e, adjacent 31 times, and the runners-up are t followed by h at 20, r followed by e at 17, and T followed by h at 12. Nothing longer is in the running, since nothing longer exists yet.

Coverage multiplies a candidate’s occurrence count by the number of symbol positions it covers.

he:      31 × 2 = 62
analys:   7 × 6 = 42
expecte:  5 × 7 = 35
re:      17 × 2 = 34

The most frequent pair still wins here, but the remaining order changes. Longer pieces can cover more text despite occurring less often.

The difference is not a refinement of the same idea. A merge count answers how many pieces one join removes from the corpus, which for a pair is how often the pair occurs; a coverage figure answers how much of the corpus a row of the table would account for, which is that occurrence count multiplied by the length of the piece.

Merging cannot ask the second question at all, because it has no candidate longer than two symbols to ask it about, and reaches analys only by making five separate joins and scoring each of them on its own.

So state the thing the vocabulary is for, and then choose to maximise it. Every position in every word should lie under some piece of more than one symbol, because a position left bare is a whole token spent on one character. A vocabulary of a given size is good to the extent that it covers those positions, and each word counts as often as it occurs.

covers(p)  =  Σ over words w   count(w) × (positions of w that p claims)

The rule is then the shortest one on this site. Take the candidate covering the most positions nothing has covered yet, add it to the vocabulary, and repeat until the budget is spent or nothing is left to cover. Candidates are every run of two or more symbols the corpus contains. Single symbols are not candidates, since the alphabet is in the vocabulary anyway and a single symbol covers nothing that was not already going to be its own token.

take   argmax over candidates p   covers(p) restricted to positions still bare

To apply a piece, scan the word from the left. When it matches positions that are still unclaimed, claim them and move past the match. Otherwise move forward one position and try again. We apply selected pieces in their selection order before evaluating a new candidate, so earlier choices affect which positions remain available. The model must retain that order to repeat the same encoding.

ending in widest = 3 positions × 3 occurrences = 9
ending in both words = 3 × (3 + 6) = 27
whole widest = 6 × 3 = 18

Run the rule on low, lower, newest and widest and the first turn goes to newest with its mark, six positions in a word seen six times, which covers 36. Its nearest rivals are ewest with the mark and newes, both five positions in the same six occurrences and worth 30, and then est with the mark, three positions across nine occurrences and worth 27.

Merging’s own first choice on this corpus is the pair e followed by s, which appears nine times; here that pair is not even a separate candidate, since every run containing it is one.

…

Drag the control and watch covered positions fill. The marked ending est loses the first turn to newest because the complete word covers more weighted positions.

newest = 6 × 6 = 36
marked est = 3 × 9 = 27

This choice comes from the coverage objective. It makes no judgment about which candidate is a meaningful word or suffix.

Once newest is selected, positions it covers no longer earn credit for overlapping candidates. The marked ending can now earn credit only in widest, so the next choice is the whole word. The remaining choices finish the coverage.

newest: 6 × 6 = 36
widest: 6 × 3 = 18
low:    3 × 5 = 15
lower:  5 × 2 = 10
total covered = 36 + 18 + 15 + 10 = 79

Those four selections cover every weighted symbol position in this corpus.

The fit then stops, at 16 tokens, however many were asked for. There is no candidate left that covers a position, so asking for 40 rows or 300 gives the same four pieces. That is the same shape of ceiling merging has, where the loop runs out of pairs seen twice, arrived at from a different direction. Here the ceiling is reached when the corpus is entirely covered.

To read a new word, spell it in symbols and apply the chosen pieces in rank order, exactly as the fit did. Whatever a piece claims is a token; whatever stays bare is a single symbol. So lower comes back as one piece, and the unseen unwidest comes back as u, then n, then widest with its mark, because the chosen piece really does occur inside it.

Merging creates longer pieces through intermediate pieces, retaining those earlier entries as possible fallbacks. The coverage rule selects a whole candidate for the positions it newly covers. Once a larger piece already covers those positions, selecting a smaller piece within it adds no coverage there. This difference follows from what the two selection objectives reward.

Choosing the largest immediate gain may rule out a better combination later. To understand that difficulty, first consider a related mathematical problem: choose up to k sets of positions to maximize the weight of their union. We will then check how its assumptions compare with this tokenizer's rules.

That set problem is weighted maximum coverage. Its general form is NP-hard, so no polynomial-time exact algorithm is known for all inputs. This does not make an exact answer impossible: exhaustive search and other exact methods can solve suitable instances. The difficulty is how the work grows in the worst case.

The eighteen sentences supply 815 candidate pieces, and this fit selects 69. Enumerating every possible selection of that size would be an enormous search. Greedy selection gives us a manageable procedure, while leaving open how far its result is from the best achievable one.

For ordinary weighted set coverage, selecting a candidate adds every position in its set to a union. Overlaps are allowed and each position's weight is counted once. This objective is monotone: adding a set cannot lower coverage. It is submodular: the same set can add no more to a larger union than to a smaller union contained within it.

For a nonnegative monotone submodular objective that is zero for the empty set, selecting the largest marginal gain at each step has the following bound under a budget of k equally costly selections:

greedy coverage after k turns   ≥   (1 − 1/e) × best coverage any k pieces reach

This is a worst-case bound of about 0.632 relative to the best selection of the same size. It applies to the weighted-union formulation just described. Our tokenizer adds a different constraint: an occurrence must lie wholly on unclaimed positions, and pieces are applied in rank order. A partial overlap rejects the entire occurrence instead of adding its still-uncovered positions. The theorem therefore does not establish this bound for the tokenizer.

Even for the weighted-union problem, the bound concerns covered positions. It does not bound the number of tokens needed to encode new text. We need to measure that separately, using text beyond the training corpus.

gap after one more selection ≤ (1 − 1/k) × current gap
gap after k selections ≤ B(1 − 1/k)^k ≤ B/e
coverage after k selections ≥ B(1 − 1/e)

Let's check a small tokenizer case directly. Take costing three times and costly three times, giving 39 symbol positions. The best first piece is cost, covering four positions in each of six word occurrences. With two selections allowed, the greedy rule takes cost and then the marked ending ing, reaching 33 positions.

…

Enumerating the possible pairs finds a better result: the two whole words cover all 39 positions. Greedy selection reaches 84.6% of that coverage. The first choice had the largest immediate gain, but it prevented the better two-piece combination.

Encoding length shows another cost. With the greedy pieces, the six word occurrences require 15 tokens; costly becomes cost followed by l and a marked y. With the two whole words, they require six tokens. Coverage and encoded length describe different aspects of the result.

The objective says to cover the most text, and there are two defensible readings of what a covered amount of text is. One counts positions of the spelled word, so the marked final symbol of a word is one position like any other. The other counts characters, and then the marked final symbol stands for two things, the letter and the fact that a word ended, so it is worth two.

in positions    t⎵  is  1
in characters   t⎵  is  2, the letter and the boundary

Neither reading is wrong, and the difference is not uniform. It adds exactly one to every candidate that ends a word, once per occurrence, and nothing to a candidate that does not. So a short suffix gains proportionally more than a long word does, and the ordering of two candidates can change. Whether it does is a question about a corpus rather than about the rule.

It is easy to count the extra end marker for the short ending and overlook it for the whole word. Apply the same character-counting convention to both candidates:

marked est, counting characters = 4 × 9 = 36
marked newest, counting characters = 7 × 6 = 42

There is no tie. The longer word gains from the changed unit too. The marked ewest candidate also reaches 36, which still leaves it below newest.

…

The run selects the same four pieces in the same order, now with scores of 42, 21, 20 and 12 instead of 36, 18, 15 and 10. The unit changes every score here without changing a selection. We need a different comparison to see when the unit can change the winner.

Both leading candidates end a word, so both collect one extra character per occurrence, which is worth 6 to newest and 9 to the ending. The ending does gain more, and the gap it had to close was 9, so closing it by 3 leaves it 6 behind.

For the winner to change, the extra weight must close the original score gap. A word-final candidate can gain on an internal one because only the former contains the marker. Try test, rest and best three times each, against stem, stop and stub five times each. This corpus has 96 symbol positions and 120 characters under the two conventions.

The second corpus exposes a difference that the first did not. The opening st occurs fifteen times, while the marked ending est occurs nine times. Counting the end marker as a separate character changes only the latter’s length.

symbol positions: st = 2 × 15 = 30; marked est = 3 × 9 = 27
characters:       st = 2 × 15 = 30; marked est = 4 × 9 = 36

The winner changes. Switch to the second corpus in the widget to compare both columns.

The consequence runs past the first turn. Counting positions the run is st at 30 then est with its mark at 27; counting characters it is est with the mark at 36 then st at 30. Both vocabularies end up holding both pieces, and they hold them in the opposite order, which matters because the order is what encoding replays. A word that contains both is cut differently by the two.

On the larger corpus the rule runs for 69 turns before nothing is left to cover, reaching 121 tokens in all, and it covers 576 of the 648 positions. The 72 that stay bare are positions no run of two or more symbols can reach any more, which are the leftovers between chosen pieces.

…

In this run the selected gains begin 62, 42, 35, 34, 24, 21, 21 and 16, then continue down to twos. Equal adjacent values mean the selected pieces contributed the same amount on their respective turns. This profile describes the measured run; it is not a proof that the tokenizer's order-dependent objective is submodular.

Ask both methods for 100 tokens on this corpus and both learn 48 rows above the same 51-symbol alphabet, which makes the comparison a fair one. Twelve of the 96 rows are shared. The rest are not, and the difference has a clear shape rather than being scattered.

…

Eighteen of the 48 rows chosen by coverage are whole words of the corpus, against 8 of merging’s 48, and the mean piece is 3.77 characters long against 3.04. Merging’s vocabulary is full of the rungs it climbed, aly and analy and analysi on the way to analysis, ex and exp and ecte on the way to expected. Coverage holds analys and expecte and nothing else from either family, because once analys is in, no shorter piece inside it is worth anything.

Read the corpus the pieces were chosen from and coverage wins at every size, which it ought to, since covering that corpus is precisely what it was maximising. At 60 tokens it reads the 133 word occurrences in 475 pieces against merging’s 531; at 100 it is 296 against 344; at 121, where it has run out of positions, it is 267 against 295.

…

That is 56 pieces saved at 60 tokens, 48 at 100 and 28 at 121, and it is a direct consequence of buying long pieces. A row that covers six positions removes five pieces from the corpus every time it is used, where a row that covers two removes one. The two ceilings differ as well, since coverage stops at 121 tokens when the corpus is covered and merging continues to 137 before it runs out of pairs seen twice.

Switch the widget above to the sentence none of the eighteen contained and the ordering changes hands. Up to 65 tokens coverage is still ahead, reading the sentence in 35 pieces at 60 where merging needs 39. At 70 they have crossed, 35 against 32, and merging leads at every larger size, 32 against 28 at 80, 32 against 27 at 100, and 30 against 25 at 121.

This is the place on the page where the method is worse than the one it is offered against, and the margin is 5 pieces on a sentence of seven words.

Reading either pair of columns alone settles the question the wrong way. The corpus columns say coverage is better at every size and the sentence columns say merging is better from 70 onward, and both are correct measurements of different things. Which one to believe depends entirely on whether the text a model will read resembles the text the vocabulary was chosen from.

The reason for that reversal is one word, and switching the comparison widget to its second panel shows it. The corpus uses expected and never the bare stem, so coverage buys expecte, seven positions across five occurrences. Handed expected it answers two pieces. Handed expect, which the corpus does not contain, it answers e, x, p, e, c and the marked t, six single letters, because expecte is not inside expect and nothing shorter was ever bought.

Merging, at the same size, answers expect in three pieces, exp and ec and the marked t, all of which are rungs it climbed on the way to expected and kept. The same happens to analysis, which coverage reads as analys and the marked is where merging reads it whole. Counted across the sentence about Dr. Alvarez, 24 of coverage’s 32 pieces are bare single symbols against 17 of merging’s 27.

So the length that wins on the training corpus is the same length that loses on new text, and it is one property rather than two. A piece of seven symbols covers seven positions wherever it occurs and occurs in fewer distinct words than a piece of three. Nothing in the objective values the ability to fall back gracefully, since falling back never happens on the corpus being covered.

The objective is a statement about positions and counts, and there is nothing else in it. It cannot prefer a piece that corresponds to a prefix, a stem or a syllable over one that does not, because it has no representation of any of those. A piece is a run of symbols that appears often enough and is long enough, and every run of symbols in the corpus is a candidate on equal terms.

That is not a complaint about the rule; it is the content of the definition. On the eighteen sentences the rule buys expecte, which is the stem expect with the first letter of its ending glued on, and analys, which is analysis with its last two letters missing. Both are correct answers to the question asked, and both would be rejected by anybody dividing those words by hand. The information that would settle it is not in the objective, and adding it means changing what is maximised rather than tuning anything.

Length and frequency enter the objective as a product, so they substitute for one another freely. A word of eight symbols seen a single time is worth 8, and a pair of symbols seen four times is worth 8 as well, and the rule cannot distinguish them. Merging can, and does, since its usual stopping condition refuses any pair seen fewer than twice.

Of the 72 distinct words in the eighteen sentences, 54 occur exactly once. At 100 tokens, 10 of the 48 rows coverage chose are whole words seen once, among them Tuesday with its full stop, Monday with its full stop, dropped, August and Nobody. At 121 tokens it is 13 of 69. Merging, at every one of those sizes, spends none.

Whether that is memorisation or good value is genuinely open, and the answer differs by which text is being read. On the corpus those rows earn their keep, since a whole word bought as one row removes every position of it but one. On any other text they are dead weight, and they are dead weight that displaced a shorter, commoner piece which would have earned something everywhere. Merging’s frequency floor is a decision about the same question, made in the other direction and made without measuring.

We can test a possible repair by limiting candidate length. Currently candidates can contain any run of two or more symbols. A shorter maximum would rule out some whole-word entries and force selection among shorter pieces. The objective does not choose that limit for us, and the two evaluations below need not favour the same setting.

…

At the same 100 tokens, allowing pieces of any length reads the corpus in 296 pieces and the held-out sentence in 32. Capping at five symbols reads the corpus in 324 and the sentence in 28, which is 28 pieces worse on the corpus and 4 better on the sentence, and it cuts the rows spent on words seen once from 10 to 2.

Capping at three goes too far in that direction, 384 and 29. Past eight the ceiling stops binding at all, since the pieces the rule wanted were shorter than that anyway.

Covering more character positions does not tell us whether a piece is a useful word part. The cases below separate the coverage objective from the decisions about ties, vocabulary size and which pieces we allow.