Lloyd–Max Quantizers

A quantizer has a fixed number of levels to spend. Put them where the signal lives and the error at 3 bits falls by a quarter. Lloyd–Max finds the spot; NF4 uses it to shrink language models.

Learn how to place a few levels so that a signal loses as little as possible, why the best placement follows a cube-root law, and how audio codecs and 4-bit language models use it.

Choose a source, then switch between Uniform and Lloyd–Max. Drag the bits. Watch the levels crowd where the signal spends its time, and watch the error shrink. Then we build every piece from zero, from the two conditions to the cube-root law to NF4.

You need a little calculus (an integral is an area, a derivative is a slope) and a feel for a probability density (a curve whose area is 1). We build the rest from zero.

Based on Lecture 4 of Stanford EE269: Signal Processing and Quantization for Machine Learning, taught by Mert Pilanci. Lecture slides (non-uniform quantizers, Lloyd–Max optimality and high-rate theory). Every idea is re-taught here in our own words and devices; logistics are one short paragraph near the end.

Spend the levels

3

The signal is 140 samples drawn (seeded, the same every visit) from the chosen density with variance 1; the sources are textbook shapes, not recordings. Uniform means the best clipping range for that source and bit depth, found by search. The errors are exact integrals over the density, not the 140 samples.

Chapter 0

Why Spend Levels Where the Signal Lives

See why equal spacing wastes a quantizer on real signals, and meet the two questions this whole lecture answers

Record yourself saying a sentence on your phone. The microphone makes a wave, and the phone must store that wave as numbers. It measures the height of the wave thousands of times a second and rounds each height to the nearest mark on a ruler.

That rounding is quantization: replacing a smooth number with the nearest of a short list of allowed numbers. Each allowed number is a level. With 3 bits per sample the ruler has 23 = 8 marks, and no more.

Lecture 3 built the simplest ruler, a uniform quantizer. Its marks sit a constant distance apart, called the step size and written Δ. It is easy to build and easy to analyze. This lecture asks whether equal spacing is the smart way to spend eight marks.

The shape of real signals

Look at where the heights of a real wave land. Collect all the samples and count how many fall in each narrow range of heights. The picture of those counts is a histogram. Scaled to total area 1, it becomes a probability density (written fX(x)): a tall curve means “the signal is often here”.

The lecture shows five such histograms. The first is Beethoven’s “Moonlight” sonata, first movement: a sharp spike at zero with thin tails. The second is a rock beat, with an even sharper spike and a few tails that reach far out. The third is the daily return of the S&P 500 stock index: again a spike at zero. The fourth is hourly air temperature in Berlin over two weeks, a lumpy shape with two humps. The fifth is the pixel brightness of handwritten digits, piled up at 0, with a smaller pile at the maximum of 16.

Not one of them is flat. Music and returns peak at zero because the signal is usually quiet and only sometimes loud. The digits pile up at the ends because a pixel is usually either ink or paper. A flat histogram is the exception.

The slide then names the common shapes. Speech and transform coefficients are often peaked at 0, Laplacian-like (a sharp tent with long tails). Sensor noise is often close to Gaussian (the smooth bell). Heavy tails and outliers are common in the activations of machine-learning models.

The waste, made visible

Think of a theatre with equal seats in a row, while the crowd bunches near the stage. Equal seats leave the back rows empty and cram the front. A uniform quantizer does the same with its levels. It gives the tails as many marks as the middle, and the tails almost never get used.

The lecture states it in one line: uniform bins waste resolution where the density is small and under-resolve where the density is large. The fix is just as short: allocate more bins where fX(x) is high. Try it on four shapes.

Count the empty seats

Equal-width bins cover the range from −4 to +4. Each bar is the share of samples that land in that bin. Hollow bars hold under 2% of the signal. Pick a shape, then add bits.

3

The shapes are textbook densities with variance 1 (the two bumps are 1.3 away from the centre, each with spread 0.45), not recordings of the lecture’s signals. The shares are exact integrals of each density. The 2% line is ours, chosen to make the idea easy to see.

Set the Laplacian to 4 bits. Sixteen equal bins cover the range. Eight of them hold under 2% each, and together they hold just 5.6% of the signal. Half the codebook describes a twentieth of the samples. Meanwhile the two middle bins hold about 25% each, and each covers a wide stretch of heights.

That is the cost. Every sample in a middle bin gets rounded to that bin’s centre, so the error there is large, and there are many such samples. The waste in the tails is paid for by error in the middle.

Two questions

The lecture turns the intuition into two precise questions. We use the word distortion for the average squared error between the signal and its quantized version.

  1. Question 1, finite levels. You may use a fixed number of levels. How do you choose the decision regions (which inputs share a level) and the reconstruction values (the levels themselves) to minimize distortion?
  2. Question 2, asymptotic behaviour. Suppose the number of levels grows very large. How should the reconstruction values spread along the real line?

Two results answer them, and the lecture previews both. For the first, we derive two necessary conditions that any best quantizer must satisfy, and we turn them into a local search algorithm. For the second, the density of levels must be proportional to the density of the data raised to the power 1/3. Put more levels where the data is dense, but not in proportion: the cube root softens the rule.

A quantitative taste

How much can a better ruler save? The hero at the top computes it exactly. At 3 bits on a Gaussian signal, the best uniform quantizer leaves a mean squared error of 0.0374, and the best non-uniform one leaves 0.0345: 7.7% lower. At 3 bits on a Laplacian signal, the numbers are 0.0718 and 0.0545: 24.1% lower. The more peaked the source, the more a smart ruler helps.

The lecture ends on a modern use: 4-bit formats for the weights of language models. We reach it in Chapter 9. Before that, we build everything it needs, in the lecture’s order.

The road

  1. The anatomy of a quantizer: thresholds, levels, cells, and how many numbers we must choose.
  2. What “better” means: the distortion integral, a worked example, and why the problem is non-convex.
  3. The two Lloyd–Max conditions: centroids and midpoints, derived line by line.
  4. The algorithm: alternate the two conditions until nothing moves, and meet 1D k-means.
  5. Solutions for Gaussian and Laplacian sources: the numerical tables and what they say.
  6. High-rate theory: the Bennett integral, point density and the cube-root law.
  7. Companding: warp the axis, round uniformly, unwarp.
  8. Quantizers in the wild: µ-law, A-law, dead zones and log quantization.
  9. NormalFloat (NF4): the same idea inside language models.
  10. Checking the theory: three designs side by side, and Zador’s formula.
  11. The field guide: numbers, code, and where to go next.
Why does a uniform quantizer do poorly on a signal whose samples cluster near zero?

Chapter 1

The Anatomy of a Quantizer

Name the fences and the flags, and count exactly how many numbers a designer must choose

Picture a number line with fences planted along it. The fences cut the line into pens. In every pen stands one flag. A number that wanders into a pen is replaced by that pen’s flag. That is the whole machine.

A scalar quantizer works on one number at a time (a “scalar”, as opposed to a list of numbers). The fences are its decision thresholds. The flags are its reconstruction levels, also called codepoints. The designer chooses where both go.

The model, in symbols

With M levels we need M pens, so M + 1 fence positions, counting the two ends of the line. We write them in order, and we let the outer two sit at infinity so that every number belongs to some pen.

Q(x)
The quantizer: it takes a number x and returns the flag of the pen that x falls in.
yk
The reconstruction level of pen k, for k = 0 up to M − 1. This is what the decoder outputs.
tk ≤ x < tk+1
Pen k: every x from fence tk up to, but not including, fence tk+1. The fences obey t0 = −∞ < t1 < … < tM = +∞.
ε
The quantization error: what the input was, minus what the quantizer says it was. X is the random input, so ε is random too.

Every input lands in exactly one pen, so every input has exactly one flag. The error ε is the distance, with sign, between the input and the flag it was swapped for.

Encoder, decoder and the bits between them

In a real system the quantizer is split in two, with a wire between the halves. The encoder takes a number x and finds its pen number k. It sends only k. The decoder receives k and looks up the flag yk. The data flow is short:

x: float → encoder (compare with fences) → k: 0 to M−1 → wire → decoder (table lookup) → yk: float

A fixed-rate quantizer uses M = 2b pens, so the index k takes exactly b bits. With b = 3 there are 8 pens and each sample costs 3 bits, always. (Later in the course, entropy coding lets common pens use fewer bits. Here we fix the rate.) The encoder stores the M − 1 inner fences and compares. The decoder stores the M levels and indexes a table. Neither does any arithmetic beyond that.

pythonimport numpy as np

def encode(x, t_inner):             # x: (n,) floats; t_inner: (M-1,) sorted fences
    return np.searchsorted(t_inner, x, side="right")   # (n,) ints in 0..M-1: which pen

def decode(k, y):                   # k: (n,) ints; y: (M,) levels
    return y[k]                         # (n,) floats: the flag of each pen

y = np.array([-1.5, -0.5, 0.5, 1.5])     # M = 4 levels, so b = 2 bits per sample
t_inner = (y[:-1] + y[1:]) / 2           # the three fences: midpoints, see below
x = np.array([-2.2, -0.1, 0.7, 3.0])
k = encode(x, t_inner)                   # [0 1 2 3]: this is all that crosses the wire
x_hat = decode(k, y)                    # [-1.5 -0.5  0.5  1.5]

Notice what the last line shows: the input 3.0 comes back as 1.5. The outer pens reach out to infinity, so an input far beyond the last level still gets some level. That error is unbounded, but such inputs are rare. This is the overload region.

How many numbers do we choose?

The designer picks M levels y0 to yM−1 and M − 1 inner fences t1 to tM−1. The two end fences are fixed at ±∞. That makes 2M − 1 free numbers. A 3-bit quantizer has 15. A 4-bit one has 31. A symmetric density lets us halve the work, but there is still no formula for most densities. Chapter 4 supplies a procedure instead.

Fences follow flags

The two sets of numbers are not independent. Suppose you already placed the flags. Where should the fence between two neighbouring flags go? Put it so that every input lands in the pen of the nearer flag. The lecture calls this the geometry of Voronoi cells: each flag owns the stretch of line closer to it than to any other. On a line, the cells are just intervals.

Find the fence by asking where the two flags are equally near. The squared distances must be equal:

(x − yk−1)2 = (x − yk)2  ⇒  −2x·yk−1 + yk−12 = −2x·yk + yk2  ⇒  2x(yk − yk−1) = yk2 − yk−12  ⇒  x = (yk−1 + yk)/2

The fence sits at the midpoint. With flags at −1 and 0.5 the fence is at (−1 + 0.5)/2 = −0.25. At −0.3 the nearer flag is −1 (distance 0.7 against 0.8). At −0.2 it is 0.5 (distance 0.7 against 0.8). So the midpoint is the tie, as it should be.

Now drag the flags yourself. The fences follow on their own, and the yellow bars show how much of the total error each pen is responsible for.

Drag the flags

Warm dots are the levels. Purple dashed lines are the thresholds, always at midpoints. Yellow bars are each pen’s share of the distortion. Drag a dot sideways, or use a preset.

Four levels (2 bits) on a density with variance 1. The distortion is the exact integral of the squared error over the density, using the next chapter’s formula. “Lloyd–Max” places the levels with the algorithm of Chapter 4.

Try Even spacing on the Laplacian. The two outer levels sit where the density is low, and the two inner ones carry the load. Now press Lloyd–Max. The inner levels move toward zero, the outer ones stay out, and the fences shift with them.

One more fact for later. Because the pens differ in width, the error is not spread evenly. Lecture 3 treated the error as a uniform random number between −Δ/2 and +Δ/2. That is fine when all pens have the same width Δ. Here each pen has its own error spread, and the next chapters keep track of it exactly.

Two neighbouring levels sit at 1 and 4. Under squared error, where does the threshold between them belong?

Chapter 2

What “Better” Means: The Distortion Objective

Turn “this ruler is better” into one number, compute it by hand, and see why finding the best ruler is hard

You have two rulers with eight marks each. Which one is better for this signal? To compare them we need a score. The lecture picks the most common one: mean squared error (MSE), the average of the squared difference between the input and its quantized version. We call this score the distortion and write it D.

Squaring does two jobs. It makes every error positive, so errors above and below zero cannot cancel. It also punishes large errors more than small ones: an error of 2 counts four times as much as an error of 1.

The distortion integral

The input X is random, with density fX. To average the squared error over all inputs, weight each input’s squared error by how likely that input is, and add it up. Inputs in the same pen share the same flag, so we add up pen by pen.

D
The distortion, E[(X − Q(X))2]: the average squared error of the whole quantizer. Lower is better.
∑k
Add the contributions of all M pens. We write each one as Dk.
∫tktk+1
Sum over every input x in pen k, from its left fence to its right fence.
(x − yk)2
The squared error of an input x that gets replaced by the flag yk.
fX(x)
How likely inputs near x are. It is the weight: where the density is tiny, even a big error adds little to D.

Read Dk as a question about one pen: how far, on average, do the inputs in this pen sit from its flag, counting only how often each one occurs? The design problem is to choose the fences {tk} and flags {yk}, with M = 2b fixed, so that D is as small as it can be.

A worked example, every step

Take the smallest case: a standard Gaussian input N(0, 1), whose density is φ(x) = e−x²/2/√(2π), and M = 2 levels. Put the flags at −1 and +1, and the one fence at 0. By symmetry the two pens contribute equally, so we compute the right pen and double it.

Dright = ∫0∞ (x − 1)2 φ(x) dx = ∫0∞ x2φ dx − 2 ∫0∞ xφ dx + ∫0∞ φ dx

Three half-line integrals appear. The first is half the variance, 1/2. The second is 1/√(2π) ≈ 0.3989, because the integral of x·e−x²/2 is −e−x²/2, which goes from 1 down to 0. The third is half the total probability, 1/2.

Dright = 1/2 − 2(0.3989) + 1/2 = 1 − 0.7979 = 0.2021  ⇒  D = 2 × 0.2021 = 0.4042

Is that good? Try flags at ±a for any a. The same steps give D = 1 − 4a/√(2π) + a². Set the slope to zero: −4/√(2π) + 2a = 0, so a = 2/√(2π) = √(2/π) ≈ 0.7979. Then D = 1 − 2/π = 0.3634.

So the naive flags at ±1 are 11% worse than the best pair (0.4042 against 0.3634, which is 10.1% lower for the best). Even in this tiny case, where you put the flags matters. Notice too that the best a, 0.7979, is exactly the average of the positive half of the Gaussian. Chapter 3 shows this is no coincidence.

Why the problem is hard

The slide says it plainly: the design problem is non-convex, with many local minima, but it has simple necessary conditions. A local minimum is a design where every small nudge makes D worse, even though a different design far away might be better. Think of valleys in a mountain range: you can stand in the bottom of a valley that is not the lowest one.

Two facts are still simple. Fix the fences, and D is a bowl-shaped (convex) quadratic in each flag, with one lowest point. Fix the flags, and the best fences are the midpoints from Chapter 1. Each half of the problem is easy. The trouble is that the two halves feed each other, so moving one fence and one flag together can land in a different valley.

See it in the smallest case that has more than one valley: two levels, and a signal made of three separate bumps. Choose where to put the single fence. The flags then sit at the averages of the two pens (we prove in Chapter 3 that they should). Plot D against the fence position.

Two valleys

Top: a three-bump density, one threshold (purple) and two levels at the pen averages (warm). Bottom: the distortion for every threshold position. Choose a start, then press Run to let the alternating rule walk downhill.

−2.00

Toy density: three bumps (weights 0.36, 0.26 and 0.38 at −3.4, 0 and 3.6, spread 0.3), made up to show two valleys. Each update moves the threshold to the midpoint of the two pen averages. All distortions are exact integrals.

Each valley is a flat floor: any threshold inside a gap between bumps sorts the samples the same way. Start the threshold on the left half and press Run. It falls into the left valley and stays, with D about 2.08. Start on the right and it falls into the deeper valley, D about 1.83. The algorithm never climbs, so where you start decides where you end. That is why the lecture says initialization matters.

What the lecture promises anyway

Slide 18 collects the fine print. The best quantizer may not be unique: two different designs can both be best. A design can satisfy the necessary conditions without being best, so the conditions are necessary and not sufficient. And for log-concave densities, whose logarithm is a concave (cap-shaped) curve, such as the Gaussian, the design satisfying the conditions is unique, so every start reaches the same answer.

Gaussian and Laplacian densities are both log-concave. That covers the sources that matter most in signal processing and machine learning. For lumpy shapes like the one above, expect to restart from several places, or to start from the cleverer design of Chapter 7.

The plan. We cannot solve for the best quantizer in one formula. But we can write down two simple conditions that it must obey, and each one is easy to satisfy alone. Alternating between them gives a method that only ever lowers D.
Why can we not simply set every derivative of D to zero and read off the best quantizer?

Chapter 3

The Two Lloyd–Max Conditions

Derive, line by line, where a flag belongs inside a pen and where a fence belongs between two flags

Suppose a friend hands you a finished quantizer and asks, “Can you improve it?” You cannot redesign everything at once. But you can try two small moves. Park the fences and slide a flag. Or park the flags and slide a fence. If neither move helps, the design is a local optimum.

Each move has a clean answer. The lecture names them C1 (the centroid condition) and C2 (the nearest-neighbour or boundary condition). Stuart Lloyd found them at Bell Labs in 1957, though his paper appeared only in 1982, and Joel Max published them independently in 1960. Hence the name Lloyd–Max.

C1: the flag goes to the pen’s centre of mass

Fix every fence. The pens are now fixed, and they do not overlap, so each pen contributes to D on its own. We can tune each flag separately. Take pen k, from tk to tk+1, and treat y as a free number:

Dk(y) = ∫tktk+1 (x − y)2 fX(x) dx

To find the lowest point of a smooth curve, set its slope to zero. Differentiate under the integral. The derivative of (x − y)2 with respect to y is 2(y − x).

dDk/dy = ∫ 2(y − x) fX(x) dx = 2 [ y ∫ fX(x) dx − ∫ x fX(x) dx ] = 0

The first integral inside the bracket is the probability of the pen. The second is the pen’s first moment. Solve for y:

yk
The best flag for pen k, with the fences held fixed.
E[X | X ∈ pen]
The conditional mean: the average input, given that the input landed in this pen.
∫ x fX dx
Each input value, weighted by how likely it is, summed over the pen. The pen’s first moment.
∫ fX dx
The probability that the input lands in the pen. Dividing by it turns a sum of weighted values into an average.

This is the centroid: the centre of mass of the probability inside the pen. The result is the sensible one. The best single stand-in for a group of values is their average, with likely values counting more. It is a minimum, not a maximum, because the second derivative is 2 ∫ fX dx, which is positive.

There is a tidy way to see the cost of missing the centroid. Call the centroid c and the pen’s probability m. Write x − y = (x − c) + (c − y) and expand the square. The cross term is 2(c − y) ∫ (x − c) f dx, which is zero, because c is the average of x. What remains is exact:

Dk(y) = Dk(c) + m · (y − c)2

A parabola with its tip at the centroid. Move the flag a distance d from the centroid and the pen’s distortion rises by exactly m·d².

A worked centroid

Take a pen from 1 to 2 on the standard Gaussian. Its midpoint is 1.5, but the Gaussian falls fast, so inputs near 1 are likelier than inputs near 2. For the Gaussian, the integral of xφ(x) from a to b is φ(a) − φ(b). So the numerator is φ(1) − φ(2) = 0.24197 − 0.05399 = 0.18798. The probability is Φ(2) − Φ(1) = 0.97725 − 0.84134 = 0.13591.

y = 0.18798 / 0.13591 = 1.383, not 1.5

The best flag leans toward the heavy end of the pen. The half-line pen from Chapter 2 gives the same kind of answer: 0.3989 / 0.5 = 0.7979, the best level for the two-level Gaussian quantizer.

C2: the fence goes where both flags tie

Now fix every flag and move one fence, tk. Only the two pens that touch it can change. Pen k−1 stretches from tk−1 to tk, and pen k from tk to tk+1. Their combined distortion is:

Dk−1 + Dk = ∫tk−1tk (x − yk−1)2 f dx + ∫tktk+1 (x − yk)2 f dx

The fence tk is a limit of integration in both terms. The rule for differentiating an integral by its limit (Leibniz’s rule) says: evaluate the integrand at the limit. The upper limit of the first integral adds its integrand. The lower limit of the second takes its integrand away:

∂(Dk−1 + Dk)/∂tk = (tk − yk−1)2 f(tk) − (tk − yk)2 f(tk) = 0

If f(tk) is positive, divide it out. We need (tk − yk−1)2 = (tk − yk)2. Two numbers have equal squares when they are equal or opposite. They cannot be equal, because yk−1 < yk. So they are opposite: tk − yk−1 = yk − tk, which gives

tk
The fence between pen k−1 and pen k.
yk−1
The flag just below the fence.
yk
The flag just above the fence.

The fence is the midpoint, the same answer Chapter 1 found by geometry. The calculus adds the reading the slide gives: at the boundary, both neighbouring flags are equally good. An input standing on the fence gets the same squared error from either flag, so moving the fence either way would hand some inputs to the worse flag.

See both moves as curves. In flag mode, the plot shows one pen’s distortion as you slide its flag: a parabola whose tip is the centroid. In fence mode, it shows the two neighbouring pens’ combined distortion as you slide their fence: a bowl whose bottom is the midpoint.

Nudge and watch D

A 2-bit Lloyd–Max design for a Gaussian. Choose a flag or a fence, then slide it away from its best position. The curve shows the distortion it controls; the dot is where you are.

+0.50

Gaussian density with variance 1, four levels. All other flags and fences stay at their Lloyd–Max values while one moves. The curve is the exact integral, and the identity Dk(c) + m(y − c)2 from the text gives the flag curve.

Slide a flag to the right of its centroid and the parabola climbs. Slide it left and it climbs just as fast. At zero shift you stand at the tip. Now switch to a fence. Both neighbours lose a little when the fence moves, and the bottom of the bowl is the midpoint. These two minima are the two conditions.

Putting the two together

Summarising the lecture’s slide 25. For an MSE-optimal scalar quantizer, a local optimum satisfies both: nearest-neighbour boundaries tk = (yk−1 + yk)/2, and centroids yk = E[X | X in pen k]. Each condition fixes one set of numbers given the other, so they suggest an alternating minimization: update the fences, then update the flags, and repeat. That is the next chapter.

Two cautions from the slides stay with us. The conditions are necessary, not sufficient, because the problem is non-convex. And the best design may not be unique, although for log-concave densities such as the Gaussian it is.

A pen runs from 0 to 2 on a density that falls steeply as x grows. Under squared error, where is its best reconstruction level?

Chapter 4

The Algorithm: Alternate Until Nothing Moves

Turn the two conditions into a loop, watch it descend, and see that on real data it is exactly 1D k-means

Picture a teacher placing chairs for four groups of students standing in a hall. First each student walks to the nearest chair. Then each chair slides to the average position of its students. Some students are now closer to a different chair, so they walk again. The chairs slide again. After a few rounds nobody moves.

That is the Lloyd–Max algorithm. The students are the input values, the chairs are the flags, and the walking is the fence rule. The lecture first admits something sobering. For most densities and most M there is no closed form for the best fences and flags. The two conditions are implicit and coupled: fences depend on flags, which depend on fences. So we solve them by iteration.

The loop

Given M levels and a density fX (or samples from it):

  1. Initialize the levels y0 < … < yM−1.
  2. Boundary update. Set every inner fence to the midpoint of its two flags: tk ← (yk−1 + yk)/2.
  3. Centroid update. Move every flag to the average of its pen: yk ← ∫x f dx / ∫f dx over [tk, tk+1).
  4. Repeat steps 2 and 3 until D, the fences or the flags stop changing.

Why does it work? Step 2 chooses the best fences for the current flags, so D cannot rise. Step 3 chooses the best flags for the current fences, so D cannot rise. D is never below zero. A sequence that never rises and never goes below zero must settle. The lecture calls this coordinate descent: improve one set of coordinates, then the other. The result is a local optimum (a stationary point), not always the best one.

One run by hand

Take a standard Gaussian and M = 4. Start the flags bunched near the middle, at −0.6, −0.2, 0.2 and 0.6. That is a poor design: D = 0.3521. Round 1, boundary update: the fences go to −0.4, 0 and 0.4. Centroid update: the outer pens reach out to infinity, so the outer flags jump to the average of the whole tail. The flag for the pen below −0.4 is −φ(0.4)/Φ(−0.4) = −0.3683/0.3446 = −1.069. The inner flags become ±0.197. Now D = 0.2007.

Round 2: fences at ±0.633, flags at ±1.240 and ±0.306, D = 0.1461. Round 3: D = 0.1274. Round 4: D = 0.1209. By round 12, the fences are at ±0.980 and the flags at ±1.509 and ±0.452, with D = 0.11748. The best design is fences at ±0.9816 and flags at ±1.5104 and ±0.4528, with D = 0.11748. The first rounds do most of the work. The last ones nudge the fourth digit.

Step the algorithm

Press the main button to alternate the two updates: fences first, then flags. The lower plot shows how far the distortion sits above the best design. Try a bad start on the two-bump density.

Four levels (2 bits) on the textbook densities with variance 1 (the two bumps are 1.3 from the centre with spread 0.45). The best design is found by running the same algorithm to convergence from a compander start (Chapter 7). Distortions are exact integrals.

Run the two-bump density from the piled-left start. The flags crawl in a line before they find the bumps. Now switch to the evenly spread start and compare how fast the distortion falls. A good start saves rounds, and on lumpy densities it decides which valley you reach.

Implementation notes

Slide 29 lists the practical points. For a known formula density, the pen integrals can be done in closed form (rare) or by numerical integration. For empirical data, a list of samples x1 to xn, replace each integral by a sum over the samples. And the start matters, so restart several times when the density has several bumps.

Constraints are easy to add. You can fix a clipping range, so the outer pens are bounded and the overload region is handled by design. You can force the design to be symmetric, which halves the unknowns. Here is the sample version in a few lines:

pythonimport numpy as np

def lloyd_max(x, M, iters=200):          # x: (n,) samples; M: number of levels
    y = np.quantile(x, (np.arange(M) + 0.5) / M)   # (M,) start: equal-probability points
    for _ in range(iters):
        t = (y[:-1] + y[1:]) / 2         # (M-1,) boundary update: midpoints
        k = np.searchsorted(t, x)           # (n,) pen of every sample
        y_new = np.array([x[k == j].mean() if (k == j).any() else y[j]
                          for j in range(M)])  # (M,) centroid update: sample means
        if np.max(np.abs(y_new - y)) < 1e-9: break
        y = y_new
    t = (y[:-1] + y[1:]) / 2
    D = np.mean((x - y[np.searchsorted(t, x)]) ** 2)   # empirical distortion
    return t, y, D

The guard for an empty pen keeps the flag where it was. Without it, the mean of nothing is not a number, and the whole design silently breaks.

This is k-means on a line

Slide 30 gives the data version of the objective. Given samples x1 to xn and M levels, let a(i) be the pen of sample i. The empirical distortion is D̂ = (1/n) ∑i (xi − ya(i))2. That is exactly the objective of k-means, the popular clustering method: start with random centres, then repeat two steps. Assign each observation to the nearest centre. Recompute each centre as the mean of its observations. (See also the k-means lesson.)

The match is step for step. In 1D, the assignment step produces contiguous intervals with boundaries at midpoints: our fence rule. The update step sets each centre to the mean of its members: our centroid rule. As n grows, sample means become conditional expectations, so k-means converges to the population Lloyd–Max design. Check that on samples:

k-means on a line

Dots are samples. Yellow lines join each to its centre. Press Assign, then Update. Green marks show the population Lloyd–Max levels. Try 30 samples, then 600.

Samples are drawn (seeded) from a Laplacian density with variance 1 and M = 4 levels. The population design is the Lloyd–Max solution for the exact density. Each new start picks four random samples as the first centres.

With 30 samples the centres land near the population levels but not on them. With 600 they sit almost on top. Each step still never raises the empirical distortion, so k-means converges, and as the sample grows its answer approaches the density-based design.

Beyond one dimension

Slide 36 previews the bigger picture. Quantize a vector x in Rd with a codebook of M vectors, and minimize E[‖X − Q(X)‖2]. The pens become Voronoi cells in Rd, and Lloyd’s algorithm generalizes with no change: assign to the nearest codeword, move each codeword to its cell’s mean. This is vector quantization, and it is the idea behind learned codebooks and product quantization in modern machine learning.

Why can the Lloyd–Max loop never make the distortion worse from one round to the next?

Chapter 5

Solutions for Gaussian and Laplacian Sources

Read the finished design tables for the two most common shapes, check them against the two conditions, and see what they say about the tails

You have a loop that finds the best design. Before you run it yourself on every new problem, look at what it produces for the two shapes you will meet most. The lecture prints both results for 3 bits, so M = 8 levels, as short tables. Each is a complete quantizer, ready to use.

Slide 27 gave the context: closed-form designs are rare, so a “solution” means one of two things. Either a numerical Lloyd–Max design for a given density and M, which is what these tables are, or a high-rate approximation with analytic spacing, which is what Chapters 6 and 7 build.

The two tables

All values are rounded. Every density has variance 1. The first row and the last row have the thresholds t0 = −∞ and t8 = +∞. The other thresholds are in the left column of each pair.

kGaussian tkGaussian ykLaplacian tkLaplacian yk
0−∞−2.1519−∞−3.0867
1−1.7479−1.3439−2.3796−1.6725
2−1.0500−0.7560−1.2527−0.8330
3−0.5005−0.2451−0.5332−0.2334
400.245100.2334
50.50050.75600.53320.8330
61.05001.34391.25271.6725
71.74792.15192.37963.0867
8+∞none+∞none

The two designs are symmetric because both densities are. That halves the unknowns, and the loop confirms it by landing on mirror images.

Check the table against the two conditions

A good habit: do not trust a table, test it. Take the Gaussian. The midpoint condition says t5 = (y4 + y5)/2 = (0.2451 + 0.7560)/2 = 0.50055. The table says 0.5005. Good. Now the centroid condition for the outermost pen, which stretches from 1.7479 to infinity. For a Gaussian, the average of the tail beyond a is φ(a)/(1 − Φ(a)). Here φ(1.7479) = 0.0863 and the tail probability is 0.0402, so the average is 0.0863/0.0402 = 2.152. The table says 2.1519. Good.

And an inner pen, from 0.5005 to 1.0500. Its midpoint is 0.7753, but the centroid is 0.7560, a little lower, because the Gaussian slopes down across the pen. The table’s level is the centroid, as C1 demands. That is the lesson of Chapter 3 in two numbers.

pythonimport numpy as np
from scipy.stats import norm

y = np.array([-2.1519, -1.3439, -0.7560, -0.2451, 0.2451, 0.7560, 1.3439, 2.1519])   # (8,)
t = np.concatenate([[-np.inf], (y[:-1] + y[1:]) / 2, [np.inf]])   # (9,): C2 gives the fences

# C1 residual: each level against the true centroid of its pen (normal density)
cent = (norm.pdf(t[:-1]) - norm.pdf(t[1:])) / (norm.cdf(t[1:]) - norm.cdf(t[:-1]))
print(np.abs(cent - y).max())            # below 1e-4: just the table's rounding

# distortion D = sum over pens of E[(X - y_k)^2 ; pen k]
m0 = norm.cdf(t[1:]) - norm.cdf(t[:-1])
m1 = norm.pdf(t[:-1]) - norm.pdf(t[1:])
tp = np.nan_to_num(t * norm.pdf(t))             # t*pdf(t), with inf*0 taken as 0
m2 = m0 + tp[:-1] - tp[1:]                      # integral of x^2 pdf over each pen
print((m2 - 2 * y * m1 + y ** 2 * m0).sum())   # 0.03455 at 3 bits

Design table, live

Choose a shape and a number of bits. The program runs the Lloyd–Max loop and lists every fence, level and the share of samples each pen catches. At 3 bits, the Gaussian and Laplacian rows match the lecture’s tables.

3
kFence tkLevel ykShare of samples

Every density has variance 1. The Uniform source lives on −1.73 to +1.73. Values come from running the loop on the exact density (compander start, then Lloyd–Max rounds), so they match the lecture’s rounded tables to the printed digits.

What the tables say

The slide gathers the lessons. Both designs are symmetric. Compared with the Gaussian, the Laplacian has more of its bins near zero and more spread-out outer levels. Read it in numbers. The Laplacian’s innermost level sits at 0.2334 against the Gaussian’s 0.2451, a little closer to zero. Its innermost pen, from −0.5332 to 0.5332, catches 53% of the samples, against 38% for the Gaussian. And its outermost level is 3.0867 against 2.1519, because the Laplacian has long tails to represent.

One honest detail. The slide says “tighter inner thresholds”. The first threshold is in fact slightly larger for the Laplacian (0.5332 against 0.5005). What is tighter is the level next to zero and the amount of data crowded around it. Read the table, not only the caption.

The slide ends with the rule that organises the whole lecture: uniform sources give uniform quantizers, and in general the bin widths adapt to the shape of fX. Pick the Uniform source in the device. The eight levels come out evenly spaced, 0.433 apart. A flat density has no reason to prefer any place.

Where does the error live?

Here is a useful test of any finished design. Add up the distortion Dk of each pen on its own, then ask what share of the total each pen carries. Take the 3-bit Gaussian table. On the positive side, the four pens carry 11.5%, 11.5%, 11.8% and 15.2% of the total error. The negative side mirrors them and carries the other half.

The shares are nearly equal. That is not luck. A pen near zero is narrow, but it catches many samples. A pen in the tail is wide, but it catches few. The two effects cancel. The Laplacian table gives 11.2%, 11.3%, 11.6% and 15.9%, almost the same picture.

Raise the rate and the effect sharpens. At 6 bits there are 64 pens, and nearly all of them carry 1.5% to 1.6% of the error, which is 1/64 each. Only the outermost pen is a little higher, at 2.1%. Chapter 6 explains why: the cube-root rule makes a pen’s density times its width cubed the same everywhere, and that product is what a pen adds to the error. So here is a rule of thumb. If one pen of your own design carries much more error than its neighbours, the design is not settled. Move a level toward that pen. The yellow bars in the Chapter 1 device show the same check on four pens.

Compared with the Gaussian design, what does the 3-bit Laplacian design do?

Chapter 6

High-Rate Theory: Where Should Many Levels Go?

Derive the cube-root law for how thickly to scatter levels, and check it on a small example you can do by hand

Imagine you may spend a thousand levels, not eight. The pens are now tiny. Look closely at any one pen. Over such a short stretch the density barely changes, so inside the pen the input is almost uniformly spread. This is the trick that makes Question 2 solvable: in the high-rate regime (many levels), every pen is locally uniform.

For a uniform input in a pen of width Δ, we already know the error. Lecture 3 found it: the error is spread evenly from −Δ/2 to +Δ/2, so the mean squared error is the average of e² over that range.

(1/Δ) ∫−Δ/2Δ/2 e2 de = (1/Δ) · 2(Δ/2)3/3 = Δ2/12

Step 1: a pen width that varies with position

Now let the pen width depend on where the pen sits: Δ(x). A pen near x catches inputs with probability about fX(x) dx, and it adds about Δ(x)²/12 to the squared error of each. Adding up over all x gives the heuristic that the lecture attributes to Bennett (his 1948 paper is on the reference slide):

D
The distortion of a quantizer with many levels.
1/12
The factor from the uniform error inside a pen: Δ²/12.
∫ … dx
Add the contribution of every position x on the line.
Δ(x)2
The squared width of the pen at x. Narrow pens cost little.
fX(x)
How often inputs land near x. It weights each pen by its use.

Check it against the uniform quantizer. If Δ(x) = Δ everywhere, the integral is Δ² ∫ f dx = Δ², so D ≈ Δ²/12, the old answer. The new formula lets us choose Δ(x) so that the error is spent wisely across x.

Step 2: from pen width to point density

Choosing a width at every x is awkward, because the widths must add up to the whole line with exactly M pens. A cleaner knob is the point density λ(x): the fraction of all levels per unit length near x. Its total is 1, so ∫ λ(x) dx = 1. The number of levels in a short stretch dx is then Mλ(x) dx.

If Mλ(x) levels fit in each unit of length, each pen is 1/(Mλ(x)) wide. So Δ(x) ≈ 1/(Mλ(x)). Put this into the formula:

D
The distortion, now written with the knob λ and the number of levels M.
1/(12M2)
Doubling M cuts D by four. One more bit means twice the levels, so D falls by four times: 6 dB.
∫ … dx
Add up the cost over the whole line.
fX/λ2
Where data is common (large f) we want many levels (large λ). The square in the denominator rewards levels strongly, so the best trade is not obvious.

Step 3: minimise with a Lagrange multiplier

We want the λ that makes ∫ f/λ² dx smallest, with the rule ∫ λ dx = 1 and λ ≥ 0. A Lagrange multiplier handles a rule like that. Add the rule to the target, times a free number ν:

L(λ) = ∫ [ f(x)/λ(x)2 + ν λ(x) ] dx

At the best λ, nudging λ at any single point x must not change L. So we set the derivative with respect to λ, at that point, to zero. The derivative of fλ−2 is −2fλ−3:

−2f(x)/λ(x)3 + ν = 0  ⇒  λ(x)3 = 2f(x)/ν  ⇒  λ*(x) ∝ fX(x)1/3

The constant ν just scales λ so that its total is 1. The second derivative, 6f/λ4, is positive, so this is a minimum. The pen widths follow from Δ(x) = 1/(Mλ(x)), so Δ*(x) ∝ fX(x)−1/3.

In words: the density of levels should be proportional to the density of data raised to the power 1/3. Put more levels where data is dense, but less than in proportion. The cube root flattens the contrast.

A check you can do by hand

Take a made-up density with two regions. Region A runs from 0 to 1 and holds 80% of the probability (f = 0.8). Region B runs from 1 to 4 and holds the other 20% (f = 0.0667). Use M = 100 levels. Three plans:

  1. Even spacing over 0 to 4: Δ = 0.04 everywhere. D ≈ 0.04²/12 = 1.333 × 10−4.
  2. In proportion to the data: 80 levels in A, 20 in B. Pen widths 0.0125 and 0.15. D ≈ (0.8 × 0.01252 + 0.2 × 0.152)/12 = 3.85 × 10−4. That is worse than even spacing: B is starved, and its few big pens cost a lot.
  3. Cube-root rule: weights f1/3 × length are 0.928 for A and 1.216 for B. So A gets 43.3 levels and B gets 56.7. Pen widths 0.0231 and 0.0529. D ≈ (0.8 × 0.02312 + 0.2 × 0.05292)/12 = 8.22 × 10−5.

The cube-root plan has 38% less distortion than even spacing and 79% less than the proportional plan. The densest region got fewer levels per unit length than proportion would give, and the sparse region got more. Slide the exponent yourself on a smooth density.

Raise the density to a power

Level density λ is proportional to fp. At p = 0 levels are spread evenly. Warm dots are 16 of the levels. The lower curve is the distortion estimate for every p. Find its lowest point.

0.60

The estimate is (1/12) ∫ f/λ² dx, which is D multiplied by M², with the levels confined to ±6 (Gaussian), ±14 (Laplacian) or ±12 (spike and tails). It is the high-rate approximation, so it is trustworthy only when pens are small; for large p the tails starve and it is a rough guide. The 1/3 minimum holds for any density.

Drag p from 0 upward on the Gaussian. The estimate falls steeply, bottoms out at p = 1/3 near 2.72, and climbs again. The best p is the same for the Laplacian and for the spike shape. The minimum is always at one third. Only its height changes, because the height is set by the density.

pythonimport numpy as np

x = np.linspace(-6, 6, 24001); dx = x[1] - x[0]       # grid
f = np.exp(-x**2 / 2) / np.sqrt(2 * np.pi)             # Gaussian density

def bennett(p):                                 # D * M^2 when lambda is proportional to f^p
    lam = f**p; lam /= lam.sum() * dx             # normalise so that the integral of lambda is 1
    return (f / lam**2).sum() * dx / 12

for p in (0.0, 0.2, 1/3, 0.5):
    print(round(p, 2), round(bennett(p), 3))  # 12.0, 3.33, 2.72, 5.01: lowest at one third
One region of a signal has 8 times the probability density of another. By the high-rate result, how many times more levels per unit length does the best quantizer give it?

Chapter 7

Companding: Warp, Round Uniformly, Unwarp

Turn the cube-root law into a recipe that needs only a uniform quantizer and one curved function

Hold a magnifying glass over the middle of a number line. The marks near zero spread apart, and the far ends squeeze together. Now round to the nearest mark of an ordinary evenly spaced ruler laid on the warped line, then un-warp. Near zero the effective pens are narrow. Far out they are wide. A uniform ruler has become a non-uniform one.

That is companding, a word made from compressing and expanding. The slides state two facts. Any non-uniform quantizer can be built as a compander. And any compander is the implementation of some quantizer. So the question becomes: which warp gives the best high-rate design?

The pipeline

Three steps, with the data flow named. The first function, g, is the compressor. It maps the real line to the interval from 0 to 1 and never goes down.

x: float → g → u = g(x) in [0, 1] → uniform rounding into M bins → k: 0 to M−1 → g−1 at the bin centre → yk = g−1((k + ½)/M)

The fences in the original axis are where the uniform fences of the compressed axis come back: tk ≈ g−1(k/M). The decoder applies the inverse, the expander. The encoder needs only a nonlinear function and an ordinary rounding. This is why companders were built in hardware long before cheap computers.

Which g?

We want pens of width Δ*(x) ∝ f−1/3, which means level density λ*(x) = f1/3/∫f1/3. Make g climb exactly as fast as the level density. Define its slope as that density:

g′(x)
The slope of the compressor at x. Steep means “magnify here”.
λ*(x)
The optimal level density of Chapter 6. The compressor is steepest where levels should be densest.
g(x)
The area of λ* up to x. It climbs from 0 to 1, like a cumulative distribution.

Why this gives the right pens

The slide proves it with the mean value theorem. The fences tk = g−1(k/M) satisfy g(tk+1) − g(tk) = 1/M. The mean value theorem says that this change in g equals the slope somewhere inside the pen times the pen width: 1/M = g′(ξk) (tk+1 − tk). Substitute g′ = λ* and solve:

tk+1 − tk = 1 / (M λ*(ξk))  ⇒  Δ(x) ≈ 1 / (M λ*(x))

That is exactly the spacing the high-rate result demands. Equal steps on the compressed axis are unequal steps on the original axis, and they are unequal in the right way.

The Gaussian, worked out

For the standard Gaussian, f(x)1/3 ∝ (e−x²/2)1/3 = e−x²/6. That is a bell curve with variance 3. So the optimal level density is a Gaussian N(0, 3), three times as wide as the data. The compressor is that Gaussian’s cumulative distribution: g(x) = Φ(x/√3). The inverse follows at once:

g−1(u) = √3 · Φ−1(u)  ⇒  tk ≈ √3 · Φ−1(k/M)

Compare with the naive plan of equal-probability bins, tk = Φ−1(k/M). The cube-root rule multiplies every threshold by √3 = 1.73, which pushes the outer fences out. The slide puts it as being less aggressive near the tails. For M = 8, the numbers are:

FenceEqual-probability Φ−1(k/8)Compander √3 Φ−1(k/8)Lloyd–Max
t1−1.1503−1.9925−1.7479
t2−0.6745−1.1683−1.0500
t3−0.3186−0.5519−0.5005

The compander lands between the naive plan and the true optimum, and it is closer to the optimum. At only 8 levels it overshoots a little, because the theory assumes many tiny pens.

The Laplacian and the uniform check

For the unit-variance Laplacian, f(x) = (√2/2) e−√2|x|. Raise it to the 1/3 and the exponent shrinks to −β|x| with β = √2/3. So λ* is again a Laplacian, with three times the scale. Its cumulative distribution gives the compressor, and the inverse is a logarithm: for 0 < u < ½, g−1(u) = (1/β) ln(2u), and for ½ ≤ u < 1, g−1(u) = −(1/β) ln(2(1 − u)). For M = 8, the first three fences work out to −2.94, −1.47 and −0.61, against Lloyd–Max’s −2.38, −1.25 and −0.53. Compared with the Gaussian, the Laplacian puts even more resolution near 0.

The sanity check from slide 47: for a uniform source, f is constant, so λ* is constant and Δ* is constant. The best high-rate quantizer for a flat density is a uniform one. The theory contains the old case.

Warp and drop the fences

The pink curve is g(x). Equal steps up the vertical axis (dotted) drop down to fences on the number line. Pink ticks below are the compander’s fences; purple ticks are the true Lloyd–Max fences. Add bits and watch the ticks agree.

3

Numerical integration of f1/3 on ±14; the Laplacian fences differ from the closed form in the third digit because of the cut-off. Distortions are exact integrals for the fences and levels shown (levels at g−1((k + ½)/M)). The Lloyd–Max design starts from the compander’s levels.

At 6 bits the pink and purple rows nearly coincide. At 2 bits the compander is visibly off, and the read-out confirms it: at low rates it can even lose to a well-tuned uniform quantizer (the Gaussian at 3 bits: 0.0406 against 0.0374). Companding is a high-rate recipe. Its real value at low rates is as a starting point.

The recipe, in code

Slide 65 spells out design C: build g from the data density, set thresholds by g−1, then refine with a few Lloyd–Max rounds. For a Gaussian the whole thing is four lines:

pythonimport numpy as np
from scipy.stats import norm

def compander_gauss(M):
    k = np.arange(M + 1)
    t = np.sqrt(3) * norm.ppf(k / M)                          # (M+1,) fences; the ends are -inf and +inf
    y = np.sqrt(3) * norm.ppf((np.arange(M) + 0.5) / M)    # (M,) levels at the bin centres of the warped axis
    return t, y

t, y = compander_gauss(8)
print(np.round(y[4:], 4))      # [0.2725 0.8466 1.5366 2.6572]  vs Lloyd-Max [0.2451 0.7560 1.3439 2.1519]
# then feed y into the lloyd_max loop of Chapter 4 as its starting design
For a standard Gaussian source, the compressor for the high-rate optimal quantizer is g(x) = Φ(x/√3). What does the √3 do?

Chapter 8

Quantizers in the Wild: µ-law, Dead Zones and Logs

Hear why telephones compress before they round, and see how codecs turn small values into zeros

Think of a phone call. A person speaks softly for a moment, then laughs loudly. The line carries 8 bits for each sample of the voice, 8,000 times a second. A uniform ruler with 256 marks would suit the laugh. But the soft voice spans only a few marks, and it comes out buzzy.

The standard fix, used in North American and Japanese telephony, is a compander. The theory of Chapter 7 says which warp is best for a given density. Engineers needed one warp that works for any speaker and any volume, so they chose a logarithm.

µ-law

For an input x with |x| ≤ Xmax, the µ-law compressor is:

g(x)
The compressed value, between −1 and +1. Quantize this uniformly, then expand with the inverse g−1.
sign(x)
Plus or minus one. The curve treats positive and negative inputs the same way.
ln(1 + µ|x|/Xmax)
A logarithm of the scaled size. Near zero it is almost a straight line (steep, so small values get magnified). For large inputs it flattens.
ln(1 + µ)
The value of the numerator at the largest input. Dividing by it makes g reach exactly 1 at Xmax.

A large µ means more compression and more non-uniformity. The North American and Japanese standards use µ = 255. As µ shrinks toward 0, the curve straightens and the quantizer becomes uniform.

A-law is the version common in Europe. It is a piecewise compander: linear near zero, logarithmic farther out. The motivation on the slide is that simple hardware can approximate an optimal non-uniform quantizer this way. The slide’s comparison: µ-law offers better dynamic range but worse distortion for small signals, while A-law gives more resolution for low-level signals, which made it the choice for international calls.

All of these follow one pattern from the lecture. Choose a monotone compressor (log-like, power-law, or learned). Quantize uniformly in the compressed domain. Optionally entropy-code the indices.

Hear it

The measuring stick for speech quality here is the signal-to-quantization-noise ratio (SQNR): the signal’s power divided by the error’s power, in decibels. Higher is cleaner. A uniform quantizer has the same error power whatever the signal, so a quieter signal gets a worse SQNR. A µ-law quantizer makes the error grow with the signal, so quiet and loud parts end up nearly equally clean.

The test signal below is a made-up voice-like buzz with three syllables at different volumes: one near full scale, one at a quarter, and one at 7% of full scale. It is sampled at 8,000 Hz, like a phone line.

Loud, medium, quiet

Top: the signal (blue) and its quantized version (warm). Bottom: the signal-to-noise ratio of each syllable, in decibels. Choose a quantizer and a bit depth, then press the speaker buttons. Start with a low volume on your device.

6

The signal is synthetic: ten harmonics of a 140, 120 and 160 Hz buzz, shaped into three syllables with peak levels 0.9, 0.25 and 0.07 of full scale, 8,000 samples per second. Quantizers are mid-rise over the range −1 to +1. SQNR is computed on the exact samples you hear.

At 6 bits, uniform quantization gives the loud syllable 31.7 dB, the medium one 20.5 dB and the quiet one 9.7 dB. That is the buzz you hear on the quiet syllable. µ-law with µ = 255 gives 26.1, 25.7 and 25.4 dB: the loudest part is a little noisier, and the quietest is 15.7 dB cleaner. For speech, an even cleanliness across volumes is the better trade.

Dead zones

Now a different shape of waste. When a codec such as JPEG (images) or an audio codec transforms a signal, most of the resulting coefficients are tiny. Only a few edges or notes carry energy. A dead-zone quantizer gives the pen around zero extra width. Every coefficient that falls in it becomes exactly zero.

Two things follow, per slide 50. Long runs of zeros compress very well, which is what entropy coding exploits: it gives short codes to common symbols and long codes to rare ones, and the average length of the best such code is the entropy, in bits per sample. And small coefficients matter less to the eye and ear, so zeroing them costs little perceptually. Slide the zero pen wider on a Laplacian signal.

Widen the dead zone

Outside the zero pen every pen is 0.5 wide. The zero pen is as wide as you choose, from 1 to 3 steps. The bars compare three designs: plain, yours, and a plain quantizer re-tuned to your bit rate.

2.0

Laplacian density with variance 1; reconstruction levels at the pen centroids (zero for the zero pen). Entropy is computed from the exact pen probabilities. The “plain at your rate” step is found by search so that its entropy matches yours.

Widen the zero pen to 2 steps. About half the samples become zeros and the entropy drops from 2.97 to 2.47 bits. The distortion rises from 0.0199 to 0.0450. Is that a good trade? The bottom bar says not by itself: a plain quantizer with a larger step (0.72) hits the same 2.47 bits at a distortion of 0.0394, lower than the widened zero pen. For pure mean squared error, a modestly wider zero pen (about 1.2 steps) is the most that pays, and the gain is a percent or two.

So the case for dead zones in codecs is not raw MSE. It is the long runs of zeros, which are cheap to describe, and the perceptual argument. The lecture says exactly that.

Logs and floating point

Sometimes the thing that matters is relative error, |ε|/|x|: a 1 cm error is nothing on a 100 m wall and everything on a 1 cm gap. Log quantization gives roughly constant relative error. For x > 0, take the logarithm, quantize that uniformly, and exponentiate: Q(x) = exp(Quni(ln x)).

A worked contrast. Use a step of 0.1 in the log domain. Neighbouring levels differ by a factor e0.1 = 1.105, so the worst relative error is about 5%, at x = 0.01 or x = 1000 alike. A plain uniform quantizer with step 0.1 makes an absolute error of up to 0.05. At x = 0.1 that is a 50% relative error. At x = 10 it is 0.5%. This is also why floating-point numbers, which store an exponent plus a short mantissa, behave like a log quantizer. Block floating point shares one exponent among a group of numbers. Both ideas return in the next chapter.

Non-uniformity in modern ML systems

The slide previews three places where the same idea shows up. Per-channel scales use a different step Δ for every channel of a tensor. Learned codebooks (vector quantization, product quantization) fit the levels to the data, as Lloyd–Max does, but in many dimensions. Clipping plus a non-linear compander tames outliers. The slide’s summary: many methods are “match the quantizer to the data distribution”.

Why does µ-law companding help a telephone carrying both whispers and shouts at 8 bits per sample?

Chapter 9

NormalFloat: The Same Idea Inside Language Models

See why a bell-shaped pile of weights wants a non-uniform 4-bit codebook, build NF4, and measure what it buys

A language model with 7 billion weights stores each as a 16-bit number: 14 gigabytes. At 4 bits each the same weights take 3.5 gigabytes, which fits on a gaming graphics card. The saving is large. The question is how to choose 16 levels so that the model barely notices.

(The 7 billion is an illustrative size. The arithmetic is 7 × 109 weights × 2 bytes, then × 0.5 byte.)

What the weights look like

The lecture shows a weight matrix from a real model, NVIDIA’s Hymba (November 2024). As a picture it looks like static on a television. As a histogram it is a bell, centred on zero. That matches the earlier chapters: the weights are close to normally distributed. Slide 3 had said the same about sensor noise.

This is a gift. A bell-shaped source is exactly the case Lloyd–Max and high-rate theory handle best. Few weights are large, and the many small ones carry most of the model. Uniform bins would waste levels on the rare large weights and under-resolve the crowded small ones.

NF4, built from the bell

NormalFloat 4 (NF4, Dettmers et al., 2023) is a 4-bit format with 16 discrete levels, spaced non-uniformly: more near zero. The slide says it “minimizes quantization error, especially for small but critical weight values”, and notes it is widely used in QLoRA, a method for fine-tuning large language models on modest hardware.

How are the 16 levels chosen? The idea follows from a bell curve. Place the levels at quantiles of the standard normal, the points that cut its probability into equal slices, so each level serves about the same number of weights. Then rescale the levels to the range −1 to +1, and include an exact zero. The published construction takes 8 positive quantiles, 7 negative ones, and a zero, giving 16 values:

−1, −0.696, −0.525, −0.395, −0.284, −0.185, −0.091, 0, 0.080, 0.161, 0.246, 0.338, 0.441, 0.563, 0.723, 1

Read the gaps. Near zero the neighbouring levels are about 0.08 to 0.09 apart. At the edge the last gap is about 0.28. The slide compares this with a uniform 4-bit grid, whose bins are all 0.1333 wide, and labels bin widths of 0.0624 and 0.3125 on the NF4 side.

NF4 is related to what we derived, but it is not Lloyd–Max. Quantile placement is the “equal-probability bins” plan from Chapter 7. Chapter 7 showed the cube-root rule puts the outer fences √3 times farther out, and Lloyd–Max moves each level to its pen’s centroid. NF4 is a fixed, cheap, data-independent codebook that is close to the optimum for a bell shape. Nobody has to run a loop for each layer.

One scale per block

The codebook lives on −1 to +1, but real weights live on their own scale. So the weights are cut into blocks (QLoRA uses 64), and each block is divided by its largest absolute value, its absmax. After the division every weight in the block lies in −1 to 1. The block keeps its absmax as a separate number, its scale. The data flow for n weights:

w: (n,) float → blocks (n/64, 64) → scale = absmax per block (n/64,) → u = w/scale in [−1, 1] → nearest of 16 levels → idx: (n,) in 0..15 (4 bits each)

Decoding is a lookup and a multiply: ŵ = codebook[idx] × scale. The scale costs a little extra storage per block, which is the price of letting each block use the whole codebook.

pythonimport numpy as np
from scipy.stats import norm

def nf4_codebook(offset=0.9677):
    pos = norm.ppf(np.linspace(offset, 0.5, 9)[:-1])          # (8,) positive normal quantiles
    neg = -norm.ppf(np.linspace(offset, 0.5, 8)[:-1])         # (7,) negative ones
    v = np.sort(np.concatenate([pos, [0.0], neg]))               # (16,) with an exact zero
    return v / np.abs(v).max()                            # scaled to [-1, 1]

def quantize_blocks(w, cb, block=64):
    w = w.reshape(-1, block)                               # (n/block, block)
    scale = np.abs(w).max(axis=1, keepdims=True)             # (n/block, 1): one absmax per block
    idx = np.abs((w / scale)[..., None] - cb).argmin(-1)   # (n/block, block): nearest level, 0..15
    return idx.astype(np.uint8), scale

def dequantize(idx, scale, cb):
    return (cb[idx] * scale).reshape(-1)               # lookup, then undo the scaling

What it buys

Slide 56 puts a uniform 4-bit grid beside NF4 over a bell of weights, and slide 57 compares the errors. On the slide’s weights, the average weighted error is 0.033334 for uniform and 0.027805 for NF4: an improvement of 16.59%. Reproduce the experiment yourself, with a stand-in for the weights.

Quantize some weights

16,384 made-up Gaussian weights are cut into blocks and divided by each block’s absmax. The histogram shows the scaled weights and the 16 levels of the codebook you choose. The bars give the error of all three codebooks.

Illustrative: weights are seeded standard normal draws, not a real model. Error is the mean squared error divided by the weight variance, after dequantizing with each block’s absmax. The fitted codebook is trained on these same scaled weights, so it is slightly optimistic. The uniform grid has 16 levels from −1 to +1, with bins 0.1333 wide as on the slide.

At blocks of 64, the setting QLoRA uses, NF4 beats the uniform grid by about 15%, close to the slide’s 16.59%. The fitted codebook does better still, about 25%, because it matches the actual distribution of the scaled weights.

Now try the failure case. Switch to blocks of 16. NF4 loses to the uniform grid by about 7%. The symptom is the red mark in the read-out. The measurement is the histogram: with only 16 weights per block, the largest one sets the scale, so many scaled values sit near ±1, and the pile is no longer bell-shaped. NF4’s codebook was designed for a bell. The fitted codebook, trained on the true shape, still wins. The fix is either larger blocks or a codebook fitted to what the scaling actually produces. The lecture’s message holds: match the quantizer to the data distribution, and check which distribution you really have.

For a fuller view of quantized fine-tuning, see the LoRA and PEFT lesson. For the wider landscape of weight and activation quantization, see quantization I, quantization II and sparsity and quantization.

Why does a 4-bit codebook for language-model weights place most of its 16 levels near zero?

Chapter 10

Checking the Theory: Three Designs and Zador’s Formula

Race an optimized uniform quantizer, Lloyd–Max and the compander from 1 to 8 bits, and compare each with the asymptotic law

We now hold three recipes for one job. The lecture ends by racing them. It plots the mean squared error against the number of bits for a Gaussian and a Laplacian source, with the error on a logarithmic axis. Before the race, here is exactly what each runner does. These are the slides’ designs A, B and C.

Design A: the best uniform quantizer

Uniform does not mean careless. A fair baseline picks the best range. Let the quantizer cover −Xmax to +Xmax with M equal pens. The step is Δ = 2Xmax/M. The levels are yk = −Xmax + (k + ½)Δ. The fences are tk = −Xmax + kΔ. The two end pens reach out to infinity.

The distortion is now a function of one number, D(Xmax). A small range wastes nothing on the tails but clips big inputs, which creates large overload errors. A large range never clips but makes every step coarse. The best Xmax balances the two: X*max = argmin D(Xmax). One search finds it, by a grid or golden-section method. For a Gaussian at 3 bits the best range is 2.345, so Δ = 0.586 and D = 0.03744, the value we met in the hero.

Design B: Lloyd–Max

Chapter 4’s loop: set fences to midpoints, set levels to centroids, repeat. It uses the density, or samples of it, and a starting design. It converges to a local optimum, and it is the best of the three designs for MSE.

Design C: the high-rate compander

Chapter 7’s recipe: optimise over the point density to get λ* ∝ f1/3, build the compressor g as its running area, then set tk ≈ g−1(k/M) and yk ≈ g−1((k + ½)/M). It needs no loop. The slide also notes the practical refinement: use C as the starting design for B, which is what the devices here do.

Race the designs

Each dot is one quantizer designed for that many bits. Each bit divides the error by about four, so the lines run straight down on a log axis. Switch lines on and off, choose a source, and drag the bit marker to read the numbers.

5

Densities with variance 1. Every design is computed in your browser from the exact density: the best uniform range by search, Lloyd–Max rounds from the compander start (up to 250 for the largest codebooks), the compander at levels g−1((k + ½)/M). Eight bits is the largest the numerical grid resolves well.

Read the picture. All lines slope down at the same rate: one more bit, four times less error. The best uniform line sits above the others, and the gap widens with bits. Lloyd–Max sits lowest. The compander starts above Lloyd–Max at low rates and merges with it at high rates. The dashed Zador line comes from theory alone, and it too joins them at high rates.

Zador’s formula

The Zador line needs no search and no loop. Take the high-rate distortion from Chapter 6, with L = 2b levels, and plug in the optimal density λ* = f1/3/Z, where Z = ∫ f1/3 dx.

f/λ*2 = f · Z2/f2/3 = Z2 f1/3  ⇒  ∫ f/λ*2 dx = Z2 · Z = Z3

D*(b)
The best achievable distortion with b bits per sample, at high rate.
2−2b/12
Each extra bit halves the pen width and divides the error by four. The 12 is the same one as in Δ²/12.
(∫f1/3)3
The one number that carries the shape of the density. A peaked density has a larger value than a flat one of the same variance.

This is Zador’s formula, relating bits to the best mean squared error. For a Gaussian the shape number works out to √3π/2 ≈ 2.72, so D* ≈ 2.72 · 2−2b. For a Laplacian it is 9/2, so D* ≈ 4.5 · 2−2b. Each bit divides D by 4, which is 6.02 dB in signal-to-noise ratio. That is the rule of thumb “6 dB per bit” from Lecture 3, now with the exact constant for each shape.

How accurate is it? Here is the Gaussian, from the exact Lloyd–Max design against the formula:

BitsLloyd–Max (exact)Zador estimateEstimate is too high by
20.11750.170045%
40.009500.0106312%
66.45 × 10−46.64 × 10−43.0%
84.152 × 10−54.151 × 10−50.0%

The formula is a high-rate promise, and the table shows it keeping the promise: poor at 2 bits, within a few percent at 6, exact to four digits at 8.

What the race is worth

Compare Lloyd–Max with the best uniform quantizer at 8 bits. For the Gaussian the uniform error is 2.12 times larger, which equals 0.54 of a bit. For the Laplacian it is 4.41 times larger, which equals 1.07 bits. So a well-designed non-uniform quantizer on a Laplacian signal gives, at 8 bits, what a uniform one would need about 9 bits to match. The lesson’s opening claim, measured: a smart ruler is worth up to a whole bit on peaked signals.

pythonimport numpy as np
from scipy.stats import norm
from scipy.optimize import minimize_scalar

def uniform_D(xmax, M):                          # design A: distortion for a clipping range
    y = -xmax + (np.arange(M) + 0.5) * 2 * xmax / M      # (M,) levels
    t = np.r_[-np.inf, -xmax + np.arange(1, M) * 2 * xmax / M, np.inf]   # (M+1,) fences
    m0 = norm.cdf(t[1:]) - norm.cdf(t[:-1]); m1 = norm.pdf(t[:-1]) - norm.pdf(t[1:])
    tp = np.nan_to_num(t * norm.pdf(t)); m2 = m0 + tp[:-1] - tp[1:]
    return (m2 - 2 * y * m1 + y ** 2 * m0).sum()

best = minimize_scalar(lambda X: uniform_D(X, 8), bounds=(0.5, 6), method="bounded")
print(best.x, best.fun)                          # about 2.345 and 0.03744 at 3 bits (M = 8)

def zador_gauss(b):                              # the asymptotic law
    return (np.sqrt(3) * np.pi / 2) * 2.0 ** (-2 * b)   # 2.72 * 4^-b
By Zador’s formula, what happens to the best mean squared error of a scalar quantizer when you add one bit per sample at high rate?

Chapter 11

Field Guide: Lloyd–Max on One Page

Keep the numbers, the checklist and the core code, and see where quantizer design sits in the course and the field

The lecture’s own summary (slide 58) has five lines. Uniform quantization is rarely optimal when the density is not uniform. MSE-optimal scalar quantizers satisfy two conditions: boundaries are midpoints, and codepoints are conditional means. High-rate theory says level density goes as f1/3 and pen width as f−1/3. Lloyd–Max is alternating minimization, which is 1D k-means. And practical designs include companding (µ-law), dead-zone quantizers, log quantization and NormalFloat. Everything you built here hangs from those five lines.

The numbers to keep

QuantityValueWhy it matters
Free numbers in an M-level design2M − 1 (15 at 3 bits)M levels plus M − 1 inner fences
Best uniform, Gaussian, 3 bitsrange ±2.345, step 0.586, D = 0.03744The fair baseline: tune the range
Lloyd–Max, Gaussian, 3 bitsD = 0.03455; levels ±0.2451, ±0.7560, ±1.3439, ±2.15197.7% below uniform (the slide’s table)
Lloyd–Max, Laplacian, 3 bitsD = 0.05448; levels ±0.2334, ±0.8330, ±1.6725, ±3.086724.1% below uniform (0.07175)
Two-level Gaussianlevels ±√(2/π) = ±0.7979, D = 1 − 2/π = 0.3634The smallest case, by hand
High-rate distortionD ≈ (1/(12M2)) ∫ f/λ2 dxBennett: pens are locally uniform
Optimal level densityλ* ∝ f1/3, pen width ∝ f−1/3Eight times the density gets twice the levels
Gaussian companderg(x) = Φ(x/√3), tk ≈ √3 Φ−1(k/M)Fences √3 times those of equal-probability bins
Zador’s lawD* ≈ 2−2b/12 · (∫f1/3)3: 2.72 · 4−b (Gaussian), 4.5 · 4−b (Laplacian)6.02 dB per bit; exact only at high rate
Lloyd–Max against uniform at 8 bits2.12 times less error (Gaussian), 4.41 times (Laplacian)0.54 and 1.07 bits saved
µ-lawµ = 255 in North America and JapanIn our toy at 6 bits, the quiet syllable gains 15.7 dB
NF416 levels from normal quantiles; slide: 16.59% lower error than uniformOur block-64 simulation: about 15%

Terms in one line each

TermPlain meaning
Threshold (fence), level (flag), penWhere inputs are sorted, what they are replaced by, and the stretch that shares one level
Distortion DAverage squared error, weighted by the density
CentroidCentre of mass of the probability in a pen: the best level for fixed fences
Point density λThe fraction of levels per unit length near x
CompanderWarp, round uniformly, unwarp: any non-uniform quantizer can be built this way
EntropyAverage bits per sample of the best code for the pen indices
AbsmaxLargest absolute value in a block, used as that block’s scale

A checklist for quantizing a signal

  1. Look at the histogram. Is it flat, bell-shaped, peaked with long tails, or lumpy?
  2. Fix the rate. Choose b bits, so M = 2b levels.
  3. Baseline. Search for the best uniform clipping range and record D.
  4. Start well. Use the compander (or equal-probability points from the samples).
  5. Run Lloyd–Max. On lumpy data, restart from several places and keep the lowest D.
  6. Test the answer. Fences should be midpoints of levels, and levels should be pen means.
  7. Measure the gain. If it is under a few percent, a uniform quantizer is simpler.
  8. Check what scaling does. Blocks and normalization change the distribution you quantize.

The core as code

Three functions carry the lecture: a starting design from samples (the compander), the Lloyd–Max loop, and µ-law. The sample loop is Chapter 4’s.

pythonimport numpy as np

def compander_init(x, M, bins=512):               # Chapter 7, from samples instead of a formula
    h, e = np.histogram(x, bins=bins, density=True)    # (bins,), (bins+1,): density estimate
    g = np.cumsum(h ** (1 / 3)); g /= g[-1]            # compressor: running area of f^(1/3)
    return np.interp((np.arange(M) + 0.5) / M, g, e[1:])  # (M,) levels y_k = g^-1((k + 1/2) / M)

def lloyd_max(x, y, iters=200):                    # Chapter 4
    for _ in range(iters):
        t = (y[:-1] + y[1:]) / 2                    # C2: fences at midpoints
        k = np.searchsorted(t, x)                    # (n,) pen of each sample
        y_new = np.array([x[k == j].mean() if (k == j).any() else y[j] for j in range(len(y))])   # C1
        if np.abs(y_new - y).max() < 1e-9: break
        y = y_new
    return y

def mu_law(x, mu=255.0):                        # Chapter 8: x in [-1, 1]
    return np.sign(x) * np.log1p(mu * np.abs(x)) / np.log1p(mu)

def mu_law_inv(u, mu=255.0):
    return np.sign(u) * np.expm1(np.abs(u) * np.log1p(mu)) / mu

x = np.random.default_rng(0).laplace(scale=2 ** -0.5, size=200_000)   # unit-variance Laplacian samples
y = lloyd_max(x, compander_init(x, 8))                         # near the slide's levels (sample noise moves the outer ones a few percent)

Where this sits

Lecture 3 built the uniform quantizer and its Δ²/12 noise. This lecture asked whether equal pens are the right spend and showed they are not, by up to a whole bit. Lecture 5 turns to dithering, a way to make quantization error behave better. The same ideas run through k-means clustering, through vector quantization and product quantization in retrieval and in model compression, and through the audio codecs that decide how speech and music are stored.

The course is EE269, Signal Processing and Quantization for Machine Learning, taught by Mert Pilanci at Stanford. The slides for this lecture are posted on the course slides page, and the course site carries the rest. The deck contains no logistics. The references on its last slide are Lloyd (1982), Bennett (1948), Panter and Dite, and Gersho and Gray’s book on vector quantization and signal compression. Every idea here is re-taught in our own words and devices, with thanks to Professor Pilanci for the lecture.

Keep going

The takeaway. A quantizer is a budget of levels. Spend them where the signal lives: put each flag at the centre of its pen, put each fence halfway between flags, and let the number of levels grow like the density to the one third. The error then falls by four with every bit, and a smart ruler is worth up to a whole bit over an even one.
You must quantize a heavy-tailed, peaked signal to 4 bits. Which plan follows the lecture?

Now press Present or Teach and explain, from memory, how to place eight levels for a signal: why a flag belongs at its pen’s centre of mass, why a fence belongs at a midpoint, why the loop never gets worse, and why many levels follow the cube root of the density. Then go back to the instrument at the top, pick the Spike and tails source at 4 bits, and explain where the levels crowd and why.

EE269 Lecture 4: Non-uniform Quantizers, Lloyd–Max Optimality and High-Rate Theory
The course site · Lecture slides · Back to Gleams