Finite Scalar Quantisation

Take the eighteen short English sentences about reports and costs that the rest of this section works on, and give every word in them four numbers describing how it is used. That gives seventy-two words and, because a word occurring in only one sentence comes out with the same description as every other word in that sentence, thirty-five distinct vectors between them. The word cost comes out as 0.5904, 0.5241, −0.1293 and −0.3151.

Four real numbers are exactly what a model that reads continuous vectors wants and exactly what a model that reads whole numbers cannot use. If we want the second kind of model, which is the kind that predicts the next unit of a sequence the way a language model predicts the next word, then cost has to become one number out of a fixed and finite set.

That is the question this page answers, and it is the same question a tokenizer answers for a piece of text, asked of something that was never text in the first place.

The established answer, and a very good one, is to keep a table of representative vectors and to answer with whichever of them is nearest. Six hundred four-coordinate vectors drawn about the origin, rounded to a table of sixty-four representatives found by grouping those same vectors around centres, sit an average squared distance of 0.1368 from the representative they were given. That is a good answer and it is what this page is measured against throughout.

It costs three things. It costs a fit, which is an iterative search that has to be run before a single vector can be rounded. It costs a collection to fit on, which has to look like the vectors that will arrive later. And when the table is learned by gradient inside a model rather than by grouping, it can end up with rows that nothing is ever assigned to, because a row only moves when something is assigned to it, so a row that begins far from the data stays there and takes no part.

The third of those is worth stating carefully, because it is the complaint the method on this page is usually introduced against and it is the one that is easiest to overstate. Fitted by grouping, on the six hundred vectors here, a table of any size from sixteen up to a hundred and sixty uses every single one of its rows. The unused rows are a fact about a particular training loop rather than about tables as such, and Part 5 measures which of the two arrangements actually leaves codes empty.

Suppose the set of codes were decided in advance, by a rule written down before any data arrived, and suppose the rule were cheap enough that finding a vector’s code took no search at all. Then there would be no fit, no collection to fit on and nothing about the codes for a training loop to get wrong. The price would be that the codes sit where the rule put them rather than where the vectors are, and the rest of this page is about how large that price turns out to be.

Finite scalar quantisation is one such rule, and it is about as simple as a rule can be. Push each coordinate into a bounded interval, round it to one of a few evenly spaced levels, and let the code be the combination of what each coordinate chose. None of those three steps consults a collection of vectors.

A coordinate arriving from a model can be any size at all, and a finite set of levels cannot cover the whole number line at a useful spacing. So the first step is to squeeze the coordinate into a bounded interval, and the function used for it is the hyperbolic tangent, which takes any number and returns something strictly between −1 and 1, leaves small numbers almost alone and flattens large ones towards the ends.

bounded  =  tanh(z)     in  (−1, 1)

The word strictly matters in the mathematics and not in the arithmetic a computer actually does. In exact terms the hyperbolic tangent never reaches 1, so the ends of the interval are approached and never attained. In the arithmetic these measurements are made in, the value reaches exactly 1 at an input of 18.99034, and every input larger than that gives the same answer. The first coordinate of the word cost, 0.5904, comes back as 0.5302; an input of 3 comes back as 0.99505.

Place L evenly spaced levels between minus one and one, including both endpoints. There is one fewer interval than there are levels.

level spacing = (1 − (−1)) / (L − 1) = 2 / (L − 1)

Every bounded coordinate will be rounded to one of those levels.

level j  =  −1 + 2 j / (L − 1),   for j = 0 … L − 1

At five levels those are −1, −0.5, 0, 0.5 and 1. At eight they are −1, −5/7, −3/7, −1/7, 1/7, 3/7, 5/7 and 1, spaced two sevenths apart. Notice that zero is a level when L is odd and is not one when L is even, which looks like a detail here and returns in Part 4 as the reason a whole rounding rule has to be corrected.

Each coordinate gets its own level count, so a configuration is a list of them. The one reported most often in the original work is eight levels for the first coordinate and five for each of the other three.

Scale the bounded coordinate so that neighbouring levels are one unit apart. The rounding step can then operate on a unit-spaced grid.

half width = (L − 1) / 2
scaled coordinate = bounded coordinate × half width

The endpoints lie at minus and plus the half width. With an even number of levels, those endpoints are half-integers, so the grid convention must account for that offset.

h  =  (L − 1) / 2

position  =  round( tanh(z) × h )

At five levels the half width is 2, the positions are −2, −1, 0, 1 and 2, and reading a position back as a level is a division by 2. At eight levels the half width is 3.5, and that half is exactly where the trouble in Part 4 comes from. For now take the rule as written and note that it is one multiplication and one rounding per coordinate, with no search and no comparison against anything.

Everything so far applies to one coordinate. Doing it to all four of the word cost’s numbers, at eight levels for the first and five for the rest, is the whole method on one vector, and it is small enough to check with a pencil. The playground at the top of the page has a button that loads exactly these four numbers.

coordinate   value      squashed    × h − offset   position   digit   level
  1 (8 levels)  0.5904    0.5302       1.3557          1        5     3/7
  2 (5 levels)  0.5241    0.4809       0.9618          1        3     1/2
  3 (5 levels) −0.1293   −0.1285      −0.2570          0        2       0
  4 (5 levels) −0.3151   −0.3051      −0.6102         −1        1    −1/2

So the word cost has chosen level 5 of 8 on its first coordinate and levels 3, 2 and 1 of 5 on the others, and the four numbers it will be replaced by are 3/7, 1/2, 0 and −1/2. The squared distance from where it was to where it ended up, measured in the bounded interval, is 0.065215.

The four digits are the answer, but a model that reads whole numbers wants one number and not four. Turning four bounded digits into one number is something we already know how to do, because it is how writing numbers down works. In ordinary decimal, three digits become one number by multiplying the second by ten and the third by a hundred; here the multipliers are the level counts themselves, because that is how many values each digit can take.

code  =  d₀ + L₀ d₁ + L₀ L₁ d₂ + L₀ L₁ L₂ d₃

The four coordinates have eight, five, five and five possible levels. Their place-value multipliers are one, eight, forty and two hundred. The word cost was assigned digits 5, 3, 2 and 1.

code = 5 × 1 + 3 × 8 + 2 × 40 + 1 × 200
     = 5 + 24 + 80 + 200
     = 309

This packs four discrete choices into one integer without losing which level was chosen in each coordinate.

squashed    0.7616   −0.4621    0.1974    0.9951
digits           6         1         2         4

code  =  6 × 1 + 1 × 8 + 2 × 40 + 4 × 200  =  894

Because each coordinate chooses independently of the others, every combination of choices is available and the number of codes is the number of combinations. That is the product of the level counts, and it is the arithmetic that gives the published configuration its size.

8 × 5 × 5 × 5  =  1000

This is where the method differs from a learned table in the way that matters most for anybody planning a system. A table of a thousand vectors has to be found, stored and kept from degenerating; a grid of a thousand codes is four small numbers written in a configuration file. Doubling the first coordinate’s levels from eight to sixteen doubles the code count without adding a single fitted parameter, and a thousand codes is 9.9658 bits, which is what each position of the sequence costs a model downstream.

Going the other way is the same arithmetic in reverse. Divide the code by the first level count and the remainder is the first digit; divide the quotient by the second and the remainder is the second digit, and so on. Each digit then names its level, and the four levels together are the vector the code stands for.

309 ÷ 8  =  38 remainder 5   →   d₀ = 5
 38 ÷ 5  =   7 remainder 3   →   d₁ = 3
  7 ÷ 5  =   1 remainder 2   →   d₂ = 2
  1 ÷ 5  =   0 remainder 1   →   d₃ = 1

Two corners are worth knowing. Code 0 is the vector with every coordinate at −1, and code 999 in the published configuration is the vector with every coordinate at 1, which is what any sufficiently large input lands on. A vector every one of whose coordinates saturates is reproduced exactly, and its rounding error is zero.

There is a claim hidden in all of this that deserves to be made explicit, because without it the method would be doing something different from what a table of representatives does. A table answers with the nearest representative. Rounding each coordinate separately does not obviously answer with the nearest point of the grid, and yet it does.

‖b − g‖²  =  Σ (bᵢ − gᵢ)²,   and each gᵢ is free

Section 6 gave the rule as multiply by the half width and round, and that is what anybody writes the first time. It is right for an odd level count and wrong for an even one, and the way it is wrong is quiet enough that a system built on it will train, produce codes and report plausible numbers.

h  =  (L − 1) / 2

position  =  round( tanh(z) × h )

Look at what the half width is. At five levels it is 2, so the bounded interval becomes −2 to 2 and rounding it gives five whole numbers, which is what was asked for. At eight levels it is 3.5, so the interval becomes −3.5 to 3.5, and the whole numbers strictly inside that are −3 up to 3. There are seven of them.

One example is not evidence, so here is the whole sweep. For every level count from two to twelve, two hundred thousand inputs spread across the range were rounded under both rules and the distinct results counted. The widget draws each level count as a line from −1 to 1, the obvious rule’s levels above the line and the corrected rule’s below.

…

The pattern is exact rather than approximate. At every one of the six even level counts the obvious rule reaches one level fewer than was asked for, and at every one of the five odd counts the two rules agree completely. The worst case is the smallest. Asked for two levels, the obvious rule produces one, because the half width is 0.5 and everything in −0.5 to 0.5 rounds to zero, so the coordinate carries no information at all and nothing raises a complaint.

There is a tempting objection. If the bounded value reached exactly 1, then multiplying by a half width of 3.5 would give 3.5, and rounding that gives 4, so surely the missing outer levels come back at saturation. They partly do, and it does not help, and measuring it turns up something the objection does not predict.

Including inputs large enough that the squashing returns exactly 1, the obvious rule at eight levels reaches nine distinct levels rather than seven, one more at each end. At twelve it reaches thirteen and at four it reaches five. But at two, six and ten it reaches one, five and nine, which is no more than before.

The reason is the tie rule. A value landing exactly half way between two whole numbers is rounded to the even one, so 3.5 becomes 4 and 2.5 becomes 2, and whether the extra levels appear depends on whether the half width’s whole part is odd or even.

Even where they appear the extra levels are no use, since they are reached only by inputs beyond the point at which the squashing has flattened completely. Under the obvious rule at eight levels a system would have seven levels in ordinary use, two more that fire only on saturating inputs, and a total of nine where eight were configured, which is a worse state of affairs than being one short.

The repair is to shift the whole thing by a half before rounding, and to shift it back when a position is read as a level. Subtracting a half moves the interval from −3.5 to 3.5 down to −4 to 3, whose whole numbers are −4 up to 3, and there are eight of them.

offset  =  1/2 when L is even, 0 when L is odd

position  =  round( tanh(z) × h − offset )
level     =  ( position + offset ) / h

Adding the offset back on the way out is what keeps the levels where section 5 said they were, symmetric about zero with one at each end. For an odd level count the offset is zero and nothing changes at all, which is why the two rules agree wherever L is odd and why the sweep in section 13 has an exact pattern rather than a noisy one.

A missing level per coordinate compounds, because the number of codes is a product. Rounding the six hundred vectors under both rules gives the size of the loss, and the surprise is how much it depends on the configuration rather than on the method.

All-even configurations are where it bites. At four levels across four coordinates the obvious rule reaches eighty-one of the two hundred and fifty-six codes configured and the error is 79 per cent higher; at two levels it reaches one code out of sixteen and the whole arrangement answers the same number for every vector. The published configuration is the interesting case, because three of its four level counts are odd, so only the first coordinate is affected, the reachable codes fall from a thousand to eight hundred and seventy-five, and the error rises by four per cent.

A system built on the obvious rule and tested at eight, five, five and five would look almost right.

One consequence of the offset is worth stating on its own, since it looks like a bug the first time it is met. Under an even level count zero is not one of the levels, so the zero vector cannot be reproduced. At eight levels the bounded value is 0, multiplying by 3.5 gives 0, subtracting the half gives −0.5, and the tie rule sends that to the even whole number 0 rather than to −1.

tanh(0) × 3.5 − 0.5  =  −0.5   →   position 0   →   level 1/7

So a coordinate of exactly zero comes back as 1/7 and carries a squared error of 1/49, which is 0.020408, while at five levels zero is a level, comes back as zero and costs nothing. Both are correct. The levels are symmetric about zero either way, and an even number of symmetric levels cannot include the centre.

The cost of saying a vector in codes is how far it had to move to be said, and the natural summary is the mean over the collection of the squared distance from where a vector was to the code it became. Measured in the bounded interval, since that is where the grid lives, on six hundred four-coordinate vectors, that number falls as the codes multiply.

…

The red line is the fixed grid. Sixteen codes cost 0.8200, eighty-one cost 0.2312, and a hundred and sixty cost 0.2828. That last pair is not a mistake and is the subject of section 20.

A number like 0.2312 means nothing on its own, so the widget above draws a second line. At every code count the same six hundred vectors were also rounded to a table of exactly that many representatives, found by grouping those same six hundred vectors around centres. That is the arrangement finite scalar quantisation is doing without, given every advantage, since it is fitted on precisely the vectors it is then judged on.

The fitted table is better everywhere, by between 2.04 and 4.96 times. That is the honest price of the method, and it is worth reading twice before deciding it is small. What is bought with it is that the right-hand column of that table required a fit and the left-hand one did not, and that in a model being trained end to end the fit would be happening inside the training loop and interacting with everything else in it.

The line in section 18 is not monotone, and the reason is a real property of the method rather than an artefact of the collection. Sixty-four codes spent as four, four, two, two cost 0.4828, while fifty-four codes spent as three, three, three, two cost 0.3918. Fewer codes, better spent, is the lower error.

Three configurations of exactly sixty-four codes differ by 29 per cent in error depending only on how the levels are distributed, and giving eight levels to one coordinate while leaving the other three at two is the worst of them by a clear margin. On a collection where every coordinate matters equally, spreading the levels evenly is what pays, and the level counts are therefore a real design choice rather than a formality.

A code that nothing ever lands on is wasted capacity, and it is the failure the fixed grid is often assumed to have removed. It has not been removed, and measuring it is the point of this section. Six hundred vectors rounded on a grid of a thousand codes reach 420 of them, so 580 codes name a point of the box that nothing in the collection went near.

…

Of the 420 that were reached, 293 hold exactly one vector, 88 hold two, 28 hold three, 9 hold four and two codes hold five and six. That is about as even a spread as six hundred vectors over a thousand codes can be, and the emptiness is a consequence of having more codes than vectors rather than of anything going wrong.

The fitted table of the same size is not available for comparison at a thousand codes, but at every size where it is, from sixteen up to a hundred and sixty, it uses every single one of its codes while the grid uses 152 of 160 and 80 of 81.

The seventy-two word vectors are the harder case, and switching the widget to them shows why. They reach 19 codes of the thousand, leaving 981 empty. Part of that is the corpus, since the seventy-two words have only thirty-five distinct vectors between them, but rounding then takes those thirty-five down to nineteen, so lower and estimate, which arrived as different vectors, come back identical.

Section 5 placed the levels evenly between −1 and 1, and the squashing that maps a coordinate into that interval is not linear. So levels that are evenly spaced after squashing are not evenly spaced before it, and they are far more crowded near zero than near the ends. Nothing about where they fall in the original units is chosen, or even looked at.

The consequence is that the scale of the incoming coordinates decides everything, and the method has no opinion about that scale. Multiplying the six hundred vectors by a factor before squashing them, at a fixed configuration of a thousand codes, moves both how many codes are reached and what the rounding costs, and the two do not move together.

Read the first and fourth rows together. At a tenth of the scale the error is 0.0564 and at full scale it is 0.0565, which is the same number to three places, and yet the first reaches thirty codes and the second reaches four hundred and twenty. At eight times the scale the error is six times lower and only a hundred and seventeen codes are reached, because 81 per cent of all coordinates have been pushed past 0.99 and are landing on the ends, where they are reproduced almost exactly and describe almost nothing.

A low rounding error is therefore not by itself evidence that the arrangement is working, and the number of codes reached has to be read beside it.

A configuration of level counts fixes the number of codes exactly, and no property of a collection can change it. Six hundred vectors on a grid of a thousand codes can reach at most six hundred of them, so at least four hundred are empty before anything is measured, and seventy-two word vectors on the same grid leave at least nine hundred and twenty-eight empty by simple counting.

This cuts both ways, and it is worth being clear which way. A method that chose the number of codes from the data would be a method with a fit in it, which is the thing being given up. The fixed count is the price of that, and its practical form is that the level counts have to be chosen by somebody who has looked at the vectors, which is a fit performed by a person rather than by an algorithm.

The last limit is the deepest, and it is a consequence of the set of codes being a product. Every combination of per-coordinate choices exists, whether or not any vector ever wants it, and no combination can be added, removed or moved. Structure between two coordinates is therefore unrepresentable, not badly represented.

Take six hundred vectors whose first two coordinates rise together, at a correlation of 0.9486, and the same draw with that lean taken out. At sixty-four codes the grid’s error is 0.4583 on the leaning collection and 0.4574 on the straight one, which is the same number, so the grid does not notice the lean at all.

What changes is how much of the grid is reachable, since the vectors now occupy a diagonal band and the corners off that band are visited by nothing. Forty-six of the sixty-four codes are used against all sixty-four before.

The fitted table goes the other way. Its error falls from 0.1327 to 0.0834 when the lean is introduced, because a collection concentrated in a band is easier to cover with representatives placed where the vectors are. So a dependence between coordinates is information, one arrangement uses it and the other cannot, and the gap between them widens from 3.45 times to 5.50 times on exactly that account.

Some inputs leave the method undefined rather than merely inaccurate, and some leave it defined with a choice attached that somebody has to make. The table separates the two, since the second kind is where an implementation has to decide something and the decision shows up in the answers.