What a Token Is

We will use one sentence throughout this page and revisit it in the later tokenization lessons. It contains several useful boundary cases while remaining short enough to inspect.

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

The full stop after Dr. belongs to an abbreviation. The apostrophe is part of a contraction. A hyphen joins low-cost, and re- appears at the start of re-analysis. A splitting rule must decide how to handle each case. We will begin with spaces alone so those decisions are easy to see.

The numerical layers on this site need numbers in place of those text pieces. The tokenizer supplies the IDs, and an embedding layer can then look up trainable vectors. If re-analysis. and re-analysis are two separate vocabulary entries, as the scheme in Part 3 makes them, they start with separate identities. A model can still learn a relationship between their vectors from context, but the token IDs do not provide that relationship themselves.

A token is one piece produced by the chosen scheme. For inspection, the SDK keeps that piece beside its ID. The encoding records these tokens in the order they occur, so a reader can check which text each ID represents.

token       =  ( a piece of text ,  a whole number )
encoding    =  the tokens one text became, in order

Cutting the running sentence at every space gives seven pieces, and against the table Part 2 builds those seven pieces carry the numbers 3, 2, 14, 19, 43, 28 and 32. A model sees only that second list. Everything it will ever know about the sentence has to arrive through those seven numbers and through the order they came in.

Dr.            3
Alvarez        2
didn't        14
expect        19
the           43
low-cost      28
re-analysis.  32

It is tempting to read those seven numbers as measurements, since every other number on this site is one. They are not. A token number is a position in a list, and the only question it answers is which entry of the list this piece is. Nothing follows from one number being larger than another, and nothing follows from two numbers being close.

The list this page builds is in alphabetical order, so neighbouring numbers hold pieces that happen to share a first letter. That produces both kinds of accident at once. The pieces at 29 and 30 are not and notes, which share three letters and nothing else, and they are as close as two numbers can be. The word The is at 6 and the word the is at 43, the same word with one letter capitalised, at a different position in the vocabulary.

A vocabulary is a list of pieces, fixed once it is built, with each piece owning its position in the list. Position zero is the first entry, position one the second, and the number a piece goes in as is simply where it sits. There is no second table of numbers to keep in step with the first, which is the whole reason for making the position the number rather than storing a number beside each piece.

The tables on this page are built from six sentences, the running sentence and five more from the same notebook, which is small enough that the whole list fits on a screen and is worth reading through in the playground above. Cutting those six sentences at spaces gives 47 distinct pieces, and the table holds 48 entries, the extra one being the reserved entry Part 4 is about. Cutting them into single characters gives 37 distinct pieces and a table of 38.

The first promise is the one that makes learning possible at all. Whenever the same piece appears, in whatever sentence and in whatever position, the same number comes out. If that were not so, a model that had learned something about a word in one sentence would have learned nothing about the same word in the next, and every occurrence would be a fresh start.

Encoding the running sentence and a second sentence from the same six shows it. The word the is the fifth piece of the first and the tenth piece of the second, and it carries the number 43 in both.

Dr. Alvarez didn't expect the low-cost re-analysis.
  3    2      14     19    43      28        32

The drift was small, though it was larger than the effect she expected.
  6   15   47    40      44   26  47    27    42   43    17    39     20

The second line also shows the promise being kept in a way that will annoy a reader. The word was appears twice in that sentence and is 47 both times, which is the promise working. But The at the front is 6 while the further along is 43, and expect at 19 and expected. at 20 are two unrelated entries as far as the table is concerned. The promise is about pieces being identical as strings, and it says nothing about their being the same word.

The second promise runs the other way. Given a run of numbers, each one is looked up by position and the pieces are glued back together, so a person can read what a model was shown and a model that produces numbers can have its output read. Both matter. Without it a generated sequence would be a list of integers nobody could evaluate.

encode    text     →  numbers
decode    numbers  →  text

Decoding is the shorter half, since it has nothing to decide. Look each number up, refuse any number no entry owns, glue. What varies between schemes is only the glue, and for the whole-word scheme here the glue is a single space, which turns out in Part 5 to be the thing that stops the round trip being exact. Running both halves on the running sentence gives back the sentence character for character, under both cutting rules.

The number of entries is not free, because a model gives every entry a row of its own. Whatever a model learns about a piece lives in that row, the rows are learned from the text, and a row belonging to a piece that turns up twice in the training text is learned from two occurrences.

Take a row of 768 numbers, which is an ordinary width. The whole-word table here has 48 entries and the character table has 38, and each entry needs one such row, so the count of numbers a model has to learn is the count of entries multiplied by the width of a row.

whole words        48 × 768  =  36,864 numbers
single characters  38 × 768  =  29,184 numbers

36,864 / 29,184  ≈  1.26

The whole-word table asks for about a quarter more numbers than the character table, and none of them has been learned yet. At the scale of six sentences neither figure means much. What matters is which of the two grows, and how fast, once the text is not six sentences, which is section 11.

The smallest units worth using are the characters themselves. Every character of the six sentences becomes an entry, spaces and punctuation included, which gives 37 entries. The running sentence then becomes 51 numbers, one for each character it contains, and the space carries a number of its own like everything else.

D  r  .  ␣  A  l  v  a  r  e  z  ␣  d  i  d  n  '  t  ...
11 29  5  1 10 24 33 15 29 19 37  1 18 23 18 26  2 31

Two things follow from a table this small. The first is that almost nothing is ever unseen, since a new sentence in the same language is spelled out of letters the corpus has already met. The second is that a single character carries almost no information about the writing, so a model reading this stream has to learn that the seven characters A l v a r e z in that order are a name, and it has to learn that before it can learn anything about the person.

The other end of the trade is to make every run of non-space characters an entry. The six sentences give 47 of those, and the running sentence becomes seven numbers. Each number now carries a great deal, since low-cost arrives as one thing rather than as eight characters a model must reassemble.

What it costs is visible in the table itself. Because the cut happens only at spaces, the full stop rides along on the last word, so the six sentences give both re-analysis at 31 and re-analysis. at 32 as separate entries, and both She at 5 and she at 39, and both The at 6 and the at 43. Three pairs out of 47 entries hold one word twice over, and each of those six entries has a row of parameters learned from half the text it should have had.

The running sentence is 51 numbers one way and 7 the other, a little over seven times as many, on the same writing. That ratio is the second of the two numbers a scheme is judged on, and it is the one a model’s running cost is measured against.

pairs of positions, by character   51 × 51  =  2,601
pairs of positions, by word          7 × 7  =     49

2,601 / 49  ≈  53

Character tables are described everywhere as the small ones, and over enough text they are. Over a little text they are not, and the crossover is worth seeing because it is the reason a small experiment can point the wrong way. I fed the six sentences in one at a time and measured both tables after each.

…

After the first sentence the character table holds 25 entries and the whole-word table holds 8, so the character table is three times the size. It stays larger through the fourth sentence, 37 against 30. Between the fourth and the fifth the lines cross, and by the sixth they are 38 against 48. The character line has almost stopped moving, because the six sentences use 375 characters in all and draw them from an alphabet that was nearly complete after four of them.

The word line has not slowed at all, and it is still adding eight entries a sentence at the sixth.

Everything so far assumed the piece being looked up is in the list. The interesting case is the other one, and it is not rare. The same growth measurement says how often it happens. Fitting on the first five sentences and then reading the sixth, which those five have never seen, 8 of its 12 words are absent from the word table while 1 of its 60 characters is absent from the character table.

The character column falls to nothing at the fourth sentence and then rises by one at the fifth, because the sixth sentence opens with a capital S and the five before it never used one. The word column does not fall at all. Two thirds of an ordinary sentence is missing from a word table built on five sentences, and the reason the same thing does not happen at the scale of a million words is only that the fraction gets smaller, never that it reaches zero.

The common answer is to reserve one entry that means “something else” and hand its number back for anything the list does not hold. That is the extra entry both tables on this page carry, sitting at number 0, and it is why 47 distinct words come to 48 entries. Every text then encodes, whatever is in it, and nothing ever refuses.

…

The first two blocks are the cost. Both sentences are seven words long, both use six words the table holds, and each has one word it does not, so both come out as the same seven numbers. A model shown either of them is shown the identical input.

It is worth being precise about what is lost, because the loss is total rather than partial. The number 0 does not carry a blurred version of calibration. It carries nothing about it at all, not its length, not its letters, not whether it was a name or a verb. Reading the numbers back gives the same sentence for both, with the same gap in the same place.

The calibration drift was larger than expected.
The temperature drift was larger than expected.

both  →  6  0  15  47  27  42  20
back  →  The [UNK] drift was larger than expected.

Notice how mild this looks on these two sentences and how bad it would be on a page where the unseen words are the names, the quantities and the technical terms, which is exactly where unseen words concentrate. The words a corpus has already met many times are the common ones, so the pieces a stand-in swallows are disproportionately the ones carrying the content.

The other answer is to have no such entry and refuse. The same 47 words without a reserved entry give a table of 47, and putting the same sentence to it produces no encoding at all, with the piece it could not place named. That is the third block above.

Refusing is not obviously worse. It is louder, which is usually what one wants from a mistake, and it can be the correct behaviour rather than a limitation. A scheme whose pieces are guaranteed to cover every possible text should never reach a stand-in, so giving it one would hide a fault in the cutting rule behind a plausible-looking encoding. What refusing costs is that it is now the caller’s problem, and a system that has to answer something cannot simply decline to read the input.

The third answer deserves its own section, because it is the one that shows the other two are choices rather than necessities. Text stored on a computer is a sequence of bytes, and there are exactly 256 possible byte values, so a table of all 256 spells every text that can be written and needs no reserved entry and no corpus to be built from.

Put the sentence that carries two letters the six sentences never used to each of the two tables. The character table substitutes twice and gives back [UNK]ngstr[UNK]m where the writing said something else. The byte table has nothing unknown to it, comes back exactly, and pays for that in length, 71 numbers against the character table’s 69, because the two accented letters take two bytes each.

Dr. Alvarez didn't expect the low-cost re-analysis in Ångström units.

characters        69
Å                 two bytes, 195 and 133
ö                 two bytes, 195 and 182
everything else   67 characters, one byte each

bytes             67 + 2 + 2  =  71

The sharpest test of a scheme is to encode a text and decode the numbers immediately, with no model in between, and compare what comes back against what went in, character for character. Anything the scheme discards shows up as a difference, and nothing else does.

…

The running sentence comes back exactly under both rules, and it is the weakest of the three cases, since it has one space between every pair of words and uses only pieces the six sentences already held. The two texts below it are where the schemes part.

The second text is the running sentence with one doubled space and one line break in place of a space. Under the whole-word rule it still becomes the same seven numbers, none of them unseen, and it still decodes without complaint. What comes back has single spaces everywhere and no line break, so it is a different string from the one that went in.

This is not a fault that could be fixed by a bigger table. The whole-word rule keeps runs of non-space characters and keeps nothing about what lay between them, so the information was discarded at the cut and no amount of learning downstream recovers it. Gluing with a single space is a guess made once and applied everywhere.

The character rule fails the same two texts for a different reason. On the second text it becomes 52 numbers, one of them the stand-in, because the line break is a character these six sentences never contained, and what comes back has the doubled space preserved and the line break replaced. On the third text it substitutes twice, for the two accented letters.

The distinction between the two failures matters. The character rule could round trip both texts perfectly if the corpus it was built from had contained a line break and an accent, so its failure is a fact about this corpus. The whole-word rule could not round trip the second text however much text it had been built from, so its failure is a fact about the rule. When a scheme reports a loss it is worth asking which of the two kinds it is, since only one of them goes away with more data.

Put the two together and the rule is short. A scheme reproduces exactly what it both keeps and can spell, and nothing else. Keeping means the cut did not discard it; spelling means the table holds the pieces it was cut into.

It follows that any scheme which normalises anything cannot round trip exactly, and this is a choice rather than a defect. Folding capitals together makes The and the one entry instead of the two this page has, which is one fewer row of parameters and twice the text to learn it from, and it makes the capital unrecoverable. Later pages in this section normalise a good deal more than case, rewriting quotation marks and escaping characters, and each of those rewritings is a place where the writing that comes back is not the writing that went in. The honest way to describe such a scheme is to say what it discards, not to claim it is lossless.

Everything on this page reduces to four questions, and every page after it answers the same four differently. Carrying them is enough to read the rest of the section, and enough to compare two schemes that describe themselves in quite different language.

Some of what a scheme has to settle is a genuine choice between defensible answers, and some of it is a case where the idea simply does not extend. The two are worth separating, since arguing about the second is wasted effort. The table gathers both, with what the mathematics says in each.