Patching Without a Vocabulary

The previous page ended on a bill. Our sentence about Dr Alvarez is 51 bytes, and the vocabulary merged out of eighteen ordinary English sentences reads it as 25 numbers. Across all eighteen of those sentences the byte reading takes 763 numbers and the merged one takes 263, which is a little under three times as many for the same writing, and a model that compares every position with every other does work in proportion to the square of it.

the sentence, as bytes      51
the sentence, merged       25

the corpus, as bytes      763
the corpus, merged        263

So the coverage guarantee is real and it is not free. Nothing can be unfamiliar to a table holding all 256 byte values, and what that buys is paid for in a sequence nearly three times as long, in around eight times the work for the expensive part of a model, and in a distance nearly three times as far for anything the model has to relate across a paragraph. This page is the attempt to get most of that back.

There is an obvious way to shorten a sequence of bytes, and we have already spent two pages refusing it. Find the runs that recur, give each of them an entry in a table, and read a frequent word as one number instead of three. That is what merging does, it is why the merged reading is three times shorter, and it is exactly the thing being given up, since a table learned from a corpus is what fails on writing the corpus never met.

What is left is a narrower question. We may not keep a list of which runs of bytes are worth a name, but nothing stops us deciding, for a particular text, where one piece ends and the next begins. The pieces will not be named and nothing will recognise one when it comes round again. They will merely be boundaries, and the sequence a model reads will be as long as the number of boundaries rather than as long as the text.

A piece here is a run of consecutive bytes with a start and an end, and it is several numbers rather than one. That is the difference from everything earlier in this section. When a merged vocabulary reads the word cost as one piece, that piece has an identity, a number, and a row of its own that the model learns; when this method groups the four bytes of cost into one block, the block is still four byte values and what the model gets is a single vector it works out from them.

a merged piece   =  one number, looked up in a table
a block          =  a run of byte values, and where it starts

So the arrangement has two halves. A small model reads the bytes inside a block and produces one vector for it, and a large model reads the sequence of those vectors and never sees a byte at all. Only the second of those is charged the square of the sequence length, which is why the length that matters is the number of blocks and not the number of bytes. This page is about where the boundaries go, which is the whole of the question a tokenizer would have answered.

Start with the rule that reads nothing. Take the bytes in order, cut after every fourth one, and let the last block be short if the count does not divide. Ten bytes at a block size of four are blocks of four, four and two, beginning at offsets 0, 4 and 8. There is nothing to fit, nothing to store and nothing that can go stale, and the number of blocks is the number of bytes divided by the size, which is known before the text is read.

blocks  =  ⌈ bytes ∕ size ⌉

It is worth being clear that this is a real method and not a straw one. It is what MegaByte does, and the block size is the only knob. The argument for it is that the small model reading the bytes inside a block can learn to repair whatever the cut broke, so the boundaries need not be good ones, they need only be regular. Whether that argument holds is an empirical question about the model rather than about the cutting, and it is not one this page can settle.

Here is the whole of it on our sentence, which is 51 bytes and therefore comes to 13 blocks, twelve of four bytes and a last one of three. Read the blocks across and the sentence is perfectly recoverable, since nothing has been lost, but read each block on its own and almost none of them is anything.

Dr. │Alva│rez │didn│'t e│xpec│t th│e lo│w-co│st r│e-an│alys│is.

The playground above is set to this by default, and dragging the block size moves every cut at once. At a size of one the method is the byte reading again, 51 blocks for 51 bytes and nothing bought; at a size past the length of the text it is one block and the small model has been handed the whole sentence.

One sentence is an anecdote, so put the rule to all eighteen and count. There are 763 bytes across them, which leaves 745 positions a cut could fall in, and 489 of those 745 have a letter or a digit on both sides. Cutting at a position chosen with no regard for the text therefore lands inside a word 65.6 per cent of the time, and that number is the thing every rule on this page has to beat.

…

The orange line is the fixed rule at every block size from one to twelve, and it stays between 57.0 and 74.5 per cent, with the baseline of 65.6 running through the middle of that range. Some sizes are a little better than cutting anywhere and some are worse. That is not a failure of tuning.

A rule that does not read the text cannot know where the words are, so picking a different block size moves the number of blocks without moving the quality of a single cut. The blue line, which is the next Part, is what happens when the text is allowed a say.

There is a second cost, and it is the one that surprises people who have only tested on English. A character can take more than one byte, so a boundary that falls at a fixed offset can land in the middle of one, and neither side of that cut spells anything at all. Take our sentence with a Scandinavian unit of length written into it, 38 characters and 40 bytes, and cut it every four bytes.

Dr. │Ång│str�│�m e│xpec│ted │the │re-a│naly│sis.

This is the design rather than a defect, and MegaByte’s blocks do exactly the same. The bytes are all still there and the text comes back whole when the blocks are read in order; what has happened is that the small model reading one block is sometimes handed half a letter, and it has to learn to work with that. On the eighteen English sentences the case never arises, which is the point worth carrying, since a measurement taken only on English reports that this cost is zero.

Read the sentence about the report one letter at a time and ask yourself, after each, what comes next. After The r you are fairly sure of an e, and after The repor you are practically certain of a t. Then the word ends, and what follows is a space and then anything at all, because the sentence could have gone on to say almost any word. The difficulty of the guess falls through a word and jumps at the join between two.

That is Harris’s observation, and it gives a rule that needs no list. Begin a new piece wherever the next thing is hard to guess. Nothing about it is specific to words or to English; it says only that a boundary is a place where what has gone before stops determining what comes next, which is a statement about the writing rather than about a language, and it works on a script with no spaces for the same reason it works on one with them.

To turn that into a rule we need a number for how hard a guess is. The guesser produces, at each position, a probability for every one of the 256 values the next byte could take, and the quantity we want is Shannon’s entropy of that spread. It is zero when one value has all the probability and largest when the 256 are equally likely, in which case it is exactly 8, since 8 bits is what it takes to name one of 256 things.

H  =  − Σ  p(v) log₂ p(v)          0 ≤ H ≤ 8

The guesser used throughout this page counts, over a corpus, how often each stretch of four bytes was followed by each byte value, and then reads a probability off those counts. Every value gets a small amount added to its count so that nothing has probability zero, which also means a stretch of bytes the corpus never contained comes out flat and therefore at exactly 8 bits. That last case is not a detail and Part 5 is largely about it.

Before anything at scale, here is the smallest example that contains the whole calculation. Count over the single text aab, looking back one byte, and credit every unseen byte value with one observation. Two stretches were seen. The start of a text was followed by a once, and a was followed by a once and b once.

after the start   a has 2∕257, the other 255 have 1∕257 each
after a           a and b have 2∕258, the other 254 have 1∕258
after b           never seen, so all 256 have 1∕256

a      a      b      b
7.99784   7.99572   7.99572   8.00000

H(after the start)  =  (2∕257) × log₂(257∕2)  +  255 × (1∕257) × log₂(257)
                    ≈  0.05452  +  7.94332  =  7.99784

So the ordering is right. The position after a is less uncertain than the position after nothing, which is less uncertain than the position after b. And the ordering is useless, because the three numbers a threshold would have to separate differ in the third decimal place. A threshold of 7.996 does cut this text once, between the third byte and the fourth, giving aab and b, and a threshold anywhere a person would think to put one gives either one block or four.

Given a number at every position there are two ways to decide which positions begin a block, and the Byte Latent Transformer offers both. The first cuts wherever the uncertainty is above a threshold. The second cuts wherever it is more than a threshold above the previous position’s, which the paper calls an approximate monotonic constraint and which is much closer to what Harris actually proposed, since he was watching for a rise rather than for a level.

above a level      cut at i  when  H(i) > t
risen by a step    cut at i  when  H(i) − H(i−1) > t

On text the model knows well the two usually agree, since a word start is both high and higher than the letter before it. They part company on a flat stretch. Where the uncertainty stays at 8 bits for a long run, which is what happens on writing the model has never seen, the first rule cuts at every single position and the second cuts at none of them, because a plateau has no rises.

On our held-out sentence that is 30 blocks under the first rule and 7 under the second, from the identical set of numbers.

Now the case where it works. The model here counted the eighteen sentences, so one of them is text it knows thoroughly, and the sentence about a report expected on Monday is 34 bytes. Cutting wherever the uncertainty passes one bit gives six blocks, and five of them are words.

The │re│port was │expected │on │Monday.

Compare that with the fixed rule on the same 34 bytes, which gives nine blocks and puts six of its eight cuts inside a word. The uncertainty rule makes fewer pieces and better ones at the same time, which is the claim the whole method rests on. The chart below is the number the cut is made from, one bar per byte, and the pattern is what to look at rather than any individual bar.

…

On the sentence it read the bars fall through each word and jump at every space, and the blue bars land on the jumps. Switch to the sentence it did not read and the shape is gone; more than half the bars stand flat against the ceiling, the green ticks marking word starts no longer line up with anything, and the rule cuts at almost every position because almost every position is above one bit.

The four numbers in section 10 were all within three thousandths of 8, and that was not an accident of a tiny corpus. It is what crediting every unseen byte value with one observation does. There are 256 values, so a stretch seen once with one continuation arrives at a spread where the observed value holds two shares and the other 255 hold one each, and that is barely distinguishable from flat.

p(the value that was seen)  =  (n + 1) ∕ (n + 256)

Solve that for nine tenths and the answer is 2,294. A stretch of bytes has to be observed with the same continuation two thousand times before the model is ninety per cent sure of it, and no teaching corpus and very few real ones give any particular four-byte stretch two thousand occurrences. So at the ordinary setting every position of every text comes out near 8 bits, every position looks equally uncertain, and there is no threshold that separates anything from anything.

(n + 1) ∕ (n + 256)  =  0.9
n + 1  =  0.9 n + 230.4
0.1 n  =  229.4
n  =  2,294

The repair is to credit an unseen byte value with far less than one observation. Take the smallest corpus that can show it, one six-word sentence about a cat, read some number of times, and watch two of its positions as the amount credited falls. The third byte is inside the word the; the fifth is the first letter of the word after it.

…

The left panel is the ordinary setting. Twenty copies of the sentence put the position inside a word at 7.4674 bits and the word start at 7.5862, a gap of 0.1189 bits at a height where everything is nearly maximal, and the text comes out as 22 blocks for 22 bytes at every threshold that cuts anything at all.

The right panel credits an unseen byte with a thousandth instead. At twenty copies the same two positions are 0.106 and 1.099, a gap of nearly a whole bit, and a threshold at half a bit falls cleanly between them.

The green markers under the right panel say which corpus sizes produced blocks that are the sentence’s words. There is a sharp edge and it is between seven copies and eight. At seven the sentence still comes to 16 blocks, letters and fragments; at eight it comes to five, and they are the words.

seven copies    16 blocks, and none of them is a word
eight copies     5 blocks, the │cat │sat │on the │mat

The edge is sharp because of where the threshold of half a bit happens to sit, and the numbers either side of it show how little moved. At seven copies twelve of the 22 positions score 0.5005 bits, which is over the threshold by the narrowest of margins, and with four word starts at 1.2535 that makes sixteen positions over the line and sixteen blocks. At eight copies those twelve score 0.4457 and the word starts 1.2253, so only the four are still above it, at the first letters of cat, sat, on and mat, and four cuts make five blocks.

Nothing about the sentence changed between the two. One more copy lowered every uncertainty a little, and a whole class of positions crossed the threshold together. A threshold of 0.6 puts the same edge between five copies and six, and one of 0.4 puts it between nine and ten, which is the sense in which the edge belongs to the setting rather than to the writing.

Eight copies of one sentence is 176 bytes. It is worth saying plainly how little that is, and how much it depends on the sentence being repeated exactly rather than on there being 176 bytes of English. On the eighteen sentences, which are 763 bytes of genuinely varied writing, the same rule needs a context of four bytes rather than two to produce anything word-shaped at all.

The chart in section 14 sweeps how many copies of the sentence were read, and it is fair to ask whether reading the same text twice can possibly teach a model anything. It cannot, and the arithmetic says so exactly. Multiplying every count by a number and then adding a fixed amount to each is the same spread as leaving the counts alone and adding that amount divided by the number.

(k·c + s) ∕ (k·n + 256 s)  =  (c + s∕k) ∕ (n + 256 s∕k)

Measured, twenty copies of the sentence with a thousandth credited to each unseen byte and one copy with a twenty thousandth credited agree at every one of the 22 positions to 1.7 parts in 10¹⁶, and cut the sentence into identical blocks. So the horizontal axis of that chart is really the credit axis in disguise, and the honest reading of the whole Part is that the model has to be either confident or badly calibrated before its uncertainties separate anything, and a small corpus can only buy the second.

It would be convenient if a bigger corpus were the whole answer, and it is not, which the smallest possible case shows. Count twenty copies of the phrase the cat sat, at the same context length and the same credit that recovered the words in section 15, and score the phrase itself. Every position comes out at 0.198144 bits. Not close to each other; equal.

t     h     e     ␣     c     a     t     ␣     s     a     t
0.198 0.198 0.198 0.198 0.198 0.198 0.198 0.198 0.198 0.198 0.198

The reason is that in this corpus the start of a word is exactly as predictable as the inside of one. After the space in the cat the only thing that ever came was a c, so the model is as certain there as it is between the t and the h of the. What made section 15 work was that two different words followed the same short stretch, since e followed by a space led sometimes to cat and sometimes to mat.

So the uncertainty at a word start measures how many different words the corpus put after that stretch, and a corpus with one word there produces none of it.

The last free number is how many preceding bytes the guess is conditioned on, and on the eighteen sentences it does more than the threshold does. Looking back one byte is barely better than cutting anywhere, and each byte added shortens the sequence and improves the cuts at the same time.

A byte of context is one letter, and one letter does not tell you where you are in a word, so the first row is close to the uninformed rate for the same reason the fixed rule is. By four bytes the model is looking at most of a short word and the cuts are more than twice as good, and the fifth byte adds little, which is roughly where the improvement stops on a corpus this small.

It stops because a longer stretch occurs less often, so each extra byte of context leaves more of the text scored under stretches the corpus never contained.

Now the number the whole exercise is for. Across the eighteen sentences, 763 bytes become 129 blocks when they are cut by uncertainty, which is a factor of 5.9, and 197 blocks when they are cut every four bytes. The merged vocabulary on the same eighteen sentences takes 263 numbers, so on this text the uncertainty rule produces a shorter sequence than the learned table does, while holding no table at all.

Put our sentence about Dr Alvarez to the same model. It is 51 bytes, it is ordinary English, it shares most of its words with the corpus, and 26 of its 51 positions come out at exactly 8 bits, because the four-byte stretch in front of each of them never occurred in 763 bytes of text. The rule cuts at every one of those and at several more.

Dr. A│l│v│a│r│e│z│ │d│i│d│n│'│t│ expect │t│h│e │low-│c│o│st│ │r│e│-│a│n│a│lysis.

So the method has not degraded gracefully. On text it knows it gives 5.9 bytes to a block; on text one sentence away from that it gives 1.7, which is worse than cutting every four bytes and is most of the way back to reading the raw bytes. A model would be paying nearly the full byte-level cost on exactly the writing that a byte-level model exists to handle.

On that sentence the merged vocabulary from two pages ago reads it as 25 numbers and the uncertainty rule as 30 blocks, so the thing this page is describing loses to the thing it was meant to replace, on the case that matters. And it loses to the fixed rule too, which takes 13 blocks and has no model behind it at all.

I want to be careful about what this does and does not show. The guesser here read 763 bytes, and a real one reads billions, so the honest statement is that the method needs a model good enough that its uncertainty is informative on text it has not seen, and that nothing on this page establishes how much text that takes.

What the measurement does establish is the direction of the failure. When the guesser is out of its depth the blocks get shorter rather than worse, so the cost lands on the sequence length, which is the one thing the method was bought for.

Everything else in this section produces pieces that are a property of the text and of a table somebody can inspect. Here the pieces are a property of a model, and changing the model changes them with nothing to say that either answer is the right one. Take one sentence the guesser knows and read it under four of them.

The fourth row is the one worth stopping at. Half the corpus was removed, the sentence still comes to six blocks, and the pieces are different, so a downstream model trained on one of these is reading a different sequence from a model trained on the other even where the counts agree. A learned vocabulary has no equivalent of this, since a table is a small artefact somebody can ship and read, whereas a guesser’s uncertainty on a particular stretch cannot be recovered from anything smaller than the whole model.

The number the cut is made at has no value the mathematics prefers, and it does not merely tune the answer, it spans the whole range of possible answers. On the eighteen sentences it takes the total from 188 blocks to 18, and 18 is one block per sentence, meaning the model has been handed each sentence whole and the grouping has done nothing at all.

The row at two bits is the interesting one. Not a single cut falls inside a word, which sounds ideal until you notice that the eighteen sentences have 115 word starts and this setting found 39 boundaries, so the reason none of them is wrong is that there are too few of them for any to be. There is no setting at which the method reports how confident it is in a boundary, and no quantity it produces that a person could threshold on instead.

The deepest limit here is not a degenerate input. It is the method working exactly as designed. Across the eighteen sentences the rule produces 129 blocks with 77 distinct spellings between them, and the run The followed by a space is one of those blocks twelve separate times. Nothing in the method notices. There are twelve runs of four bytes that happen to agree, and each of them is presented to the model afresh.

129 blocks    77 distinct spellings    The␣ appears 12 times

A vocabulary is exactly the thing that would have said those twelve are one word, which is what makes a frequent piece cheap and what lets a model gather up everything it has learned about a word across all its occurrences into one row. Nothing downstream here can count how often a piece appeared or look up what was learned about it, because there is no piece to look up. Handing that job to the model is a real design and it is not a free one.

Gathered in one place, these are the inputs on which the method stops being defined rather than becoming approximate, together with what has to be decided and what turns on it. The ones with a genuine choice attached are the ones worth a reader’s attention, since nothing in the mathematics makes them and somebody has to.