L3.5 · LESSON 5 OF 6

Sampling

Build a smoothed bigram model and connect next-token probabilities to log loss and perplexity.

THE IDEA

Generating text by sampling

To write text, ask the model for the distribution over the next token, draw a token from it, append it, and repeat with the new token as context. Drawing means: pick a random number u between 0 and 1 and take the token whose slice of the probability line contains it. Likely tokens get big slices, unlikely ones small slices, so they still appear sometimes.

token 0 (0.1)

token 1 (0.6)

token 2 (0.3)

random number u0.5

cumulative: 0.1, 0.7, 1 u = 0.5 falls in token 1's range → sampled token 1 greedy always picks token 1 (the largest probability)

demo seed1

20 draws with seed 1: 1 1 1 1 2 2 1 1 1 1 0 1 1 1 2 2 1 2 1 1 counts: token 0 = 1, token 1 = 14, token 2 = 5 (same seed → same draws every time)

The demo generator here is a small one of our own; the Python exercise uses NumPy's. The idea is identical: a seed makes the randomness repeatable, the distribution is unchanged.

Slide u across the probability line. Below it, 20 draws with a seed.

Predict first. Does sampling always choose the most probable token?

Chapter context

A causal language model predicts the next token from the allowed prefix. A bigram model is a transparent starting point: it uses only the immediately preceding token, making counts, uncertainty and sampling easy to inspect.

TRY IT YOURSELF

Part 1. Do it hands-on

Pick tokens by hand from a probability line, then implement sampling, greedy choice and a bigram text generator.

token 0 (0.1)

token 1 (0.6)

token 2 (0.3)

random number u0.5

cumulative: 0.1, 0.7, 1 u = 0.5 falls in token 1's range → sampled token 1 greedy always picks token 1 (the largest probability)

demo seed1

20 draws with seed 1: 1 1 1 1 2 2 1 1 1 1 0 1 1 1 2 2 1 2 1 1 counts: token 0 = 1, token 1 = 14, token 2 = 5 (same seed → same draws every time)

The demo generator here is a small one of our own; the Python exercise uses NumPy's. The idea is identical: a seed makes the randomness repeatable, the distribution is unchanged.

token for u = 0.5 token for u = 0.75 greedy token

To do: Probabilities [0.1, 0.6, 0.3] (tokens 0, 1, 2). Sampling draws a random number u in [0, 1) and picks the token whose cumulative range contains it: 0–0.1, 0.1–0.7, 0.7–1.0. For u = 0.5, which token index?
To do: For u = 0.75?
To do: What does GREEDY selection pick from these probabilities (index)?

Part 2. Do it in code

sample_index(probs, u): walk through the cumulative sums and return the first index i with u < cumulative[i]. If rounding leaves u above the last sum, return the last index. u is in [0, 1).
greedy_index(probs): the index of the largest probability (the first one if tied).
generate(P, vocab, start, n, seed): start from the token start, then n times: take row P[index of current token], draw u = rng.random() with rng = np.random.default_rng(seed), pick sample_index and make it the current token. Return the n generated tokens (not including start). Raise ValueError if a row sums to 0.
empirical_freq(probs, draws, seed): draw `draws` samples from probs with sample_index and np.random.default_rng(seed).random(), and return the observed frequencies as an array.

import numpy as np

def sample_index(probs, u):
    pass

def greedy_index(probs):
    pass

def generate(P, vocab, start, n, seed):
    pass

def empirical_freq(probs, draws, seed):
    pass

Ctrl/⌘ + Enter runs it

Stuck, or something not working? You can come back to it any time.

CHECK YOUR UNDERSTANDING

Does sampling always choose the most probable token?

ANoBYes

Chapter reference: math, worked example & code

This section belongs to the whole chapter, so it is the same on every lesson in it and may cover a different lesson's topic. The code for the experiment you just ran is inside the experiment itself.

Math and notation

P(y\mid x)=\frac{C(x,y)+\alpha}{\sum_j C(x,j)+\alpha V},\quad \operatorname{NLL}=-\frac1N\sum_t\log P(x_{t+1}\mid x_t).

V is the output vocabulary size and alpha is a nonnegative smoothing amount. Perplexity is exp(NLL) for natural-log loss.

Worked example

For ababa, a→b occurs twice and b→a occurs twice. With vocabulary {a,b} and alpha=1, P(b|a)=(2+1)/(2+2)=0.75. An alternating transition then incurs −ln(0.75)≈0.287682 nats, whose perplexity is 4/3.

Reference code

The following example uses the Python standard library and does not call a remote service.

from math import log,exp,isclose
seq='ababa'
count=sum(a=='a' and b=='b' for a,b in zip(seq,seq[1:]))
assert count == 2
prob=(count+1)/(2+2)
assert prob == .75
assert isclose(-log(prob),.2876820724517809)
assert isclose(exp(-log(prob)),4/3)

Python examples are provided for study and local execution; this page does not execute Python.

Common mistakes

Predicting the input token itself can create target leakage. Bigram counts depend on token boundaries. Perplexities across incompatible tokenizers are not directly comparable.