Predict the Next Word

01 Opening

MAYAHere is a complete language model, a toy one we wrote by hand. It is a Python dictionary with twelve keys. Each key is a word, and each value is a small dictionary saying what might come next and how likely it is. After "the", it says cat with probability one half, dog zero point three, mat and rug zero point one each. Read it as a nested lookup: TABLE of "the" gives you an inner dictionary, and TABLE of "the" of "cat" gives you zero point five. Those four numbers add up to exactly one, so whenever the model is sitting on "the", about five times out of ten "cat" comes next. Two entries are not real words: one key marks the start of a sentence, and one possible next word, written with a slash, is a special marker that means stop.

SAMSo it's a dict of dicts. The outer key is the word you're on, and the inner dict maps each possible next word to how likely it is. And that writes text?

MAYARun the loop. That means: start at the start marker, look up its row, pick the next word at random but weighted by those numbers, move to that word, and repeat until you pick stop. That weighted random draw is called sampling. Run it once and it says "a cat sat on a rug and a dog", then stops. Run it again: "the cat slept". Now make the change every engineer wants to make. Instead of drawing a random word, always take the most likely one. It says "the cat sat on the cat sat on the cat sat on", and it never stops. Not in any run.

SAMTaking the best answer every time makes it worse?

MAYAIt loops forever, and by the end of this episode you can prove it has to. And this loop, look up a distribution, choose a word, append it, repeat, is the loop every chat model runs when it answers you.

02 Quick recall

SAMThe book this module follows, Jurafsky and Martin's Speech and Language Processing, says up front what it assumes. Basic probability, some linear algebra, and Python.

MAYAAnd the Foundations module rebuilds all three: the episode on vectors and matrices, the one on probability, and the one on logarithms. Today needs three ideas from them. A probability distribution is a dictionary whose values are non-negative and sum to one, like cat zero point five, dog zero point three, mat and rug zero point one each. A conditional probability is a lookup: given this context, meaning the words so far, how likely is that word. And a logarithm counts how many times you multiply: the log base ten of a thousand is three, because ten times ten times ten is a thousand. So a hundred times a thousand is ten multiplied in twice, then three more times: five in all, and two plus three is five. That is how logs turn long products into sums.

SAMDictionary, lookup, and "how many digits". I can hold those.

03 The phenomenonLanguage

MAYAChapter 1 opens with a one-line definition. A language model is a system that predicts the next word from the previous words. Try it. "So I went to the store and bought a gallon of..."

SAMMilk. Maybe gas.

MAYAYou did not produce one answer. You produced a ranking with confidence attached: milk, very likely; gas, possible; "purple", essentially never. That ranking is the output of a language model: a probability for every word the model knows, all adding up to one. The fixed list of every word the model knows is called its vocabulary, so the output is a probability distribution over the whole vocabulary.

SAMSo in Python terms, the model is a function that takes the list of words so far and returns a dict from every vocabulary word to a float, the floats adding up to one. Why not just output the top word? That's what I'd ship.

MAYATwo reasons. Language is not deterministic, so a writer who always picks the most common word writes like a broken record. And a distribution can be scored.

SAMBecause I can ask "how much probability did you give the word that actually came next?" A single guess is just right or wrong, and wrong tells me very little.

SAMFine, but predicting "milk" seems shallow. How does that become something that answers questions?

MAYAThis is the surprising part. To predict well across billions of sentences, you are forced to learn things. To continue "the square root of nine is", you need arithmetic. After "roses, tulips and", you need to know they are flowers. To finish "the novel was written by", you need facts.

SAMAnd I'd absorb the biases in the text too. If the sentences mostly pair "engineer" with "he", so will my predictions.

MAYASo the bias isn't a bug in the model code. It's in the statistics it was asked to match. Now prompting, which just means handing the model some starting text, called the prompt, and letting it continue. If the text so far is "Question: what is the capital of France? Answer:", the most likely next word is "Paris". Answering is predicting the continuation of a document that happens to contain a question. The book calls this conditional generation: generating text that is conditioned on, meaning steered by, the text you gave it.

SAMWhy not write rules? "If the input says capital and France, say Paris."

MAYAPeople did. In 1966 Joseph Weizenbaum at MIT published ELIZA, which imitated a Rogerian therapist, the style of therapist who mostly turns your own words back into questions, with pattern-matching rules. Type "I am sad about my mother" and a rule produces "Why do you say you are sad about your mother?" Impressive for a page of rules, then hopeless.

SAMBecause every topic needs new rules, the rules collide, and nothing improves by reading more text.

MAYAWhile prediction improves with every sentence. That is the bet the field eventually made.

04 Building the mathMath & data structures

MAYANow the definition, one symbol at a time. The probability of a word given the words before it is written $P(w \mid \text{context})$ . The vertical bar is read "given". Symbol by symbol: capital P is short for "the probability of". Lowercase w is a placeholder for one candidate next word, like "cat". And context means the list of words so far, like "the". So the whole line asks: how likely is it that the next word is w, given the words so far?

SAMThat's a nested lookup. table at context, then at w.

MAYARight: the right side of the bar picks the row, the left side picks the entry. So $P(\text{cat} \mid \text{the})$ is table at "the", then at "cat": zero point five. Every row must be a valid distribution. Our row for "the": cat zero point five, dog zero point three, mat zero point one, rug zero point one. Sum: one.

SAMAnd a whole sentence?

MAYAMultiply the steps. The probability of "the cat", then stop, is the probability of "the" at the start, from the start row, times "cat" after "the", times stop after "cat". Zero point six times zero point five times zero point one: zero point zero three. Compactly, $\prod_{t} P(w_t \mid w_{<t})$ . Symbol by symbol: t is the position in the sentence, one, two, three. $w_t$ is the word at position t. The little "less than t" under the w on the right means all the words before position t. And the big pi, the Greek capital P, for "product", is a for loop that multiplies: start a running product at one, and for each position t, multiply in the probability of that position's word given everything before it. For "the cat" then stop, that's three passes of the loop: zero point six, zero point five, zero point one.

SAMEvery factor is below one, so long sentences get tiny.

MAYATiny, and then exactly zero. In Python, zero point five to the eleven hundredth, eleven hundred halves multiplied together, is zero point zero.

SAMUnderflow: the true answer is smaller than the smallest number a float can hold, so it rounds to zero. The smallest double is around ten to the minus three hundred and twenty four, counting the subnormals, the extra-small values from the episode on logarithms that trade precision for range. And this is about ten to the minus three hundred and thirty one. So the multiply rounds to zero. The fix is logs, right? The log of a product is a sum of logs.

MAYARight. One note on the base first: from here on, log means the natural log, log base e, where e is about two point seven one eight; it's what Python's math dot log computes. Base ten made the counting easy to see, but any base turns products into sums. Eleven hundred copies of the log of a half, about minus zero point six nine each, sum to about minus seven hundred and sixty two. An ordinary number. We write $\log P(w_{1:T}) = \sum_t \log P(w_t \mid w_{<t})$ . Read it as: the log of the probability of the whole sentence, words one through capital T, where capital T is the sentence length, equals a for loop that adds up, for each position t, the log of that step's probability. The big sigma, the Greek capital S, for "sum", is the adding loop. Same loop as before, except the running total starts at zero and uses plus-equals instead of times-equals. For "the cat" then stop: the log of zero point six is about minus zero point five one, the log of zero point five about minus zero point six nine, the log of zero point one about minus two point three. Add them: about minus three point five one. Undo the log, e to the minus three point five one, and you're back at zero point zero three. A culture note: mathematicians switch to logs so habitually they barely mention it. When a paper has a sum where you expected a product, this is why.

SAMNow sampling. How do I draw a word with the right odds?

MAYAPicture a ruler of length one. Lay the probabilities of the start row end to end: "the" takes the first zero point six, "a" takes the rest. Draw a uniform number between zero and one, uniform meaning every value equally likely. At zero point six three seven you are past zero point six, so you say "a". The row after "the" works the same way: cat gets zero up to zero point five, dog up to zero point eight, mat up to zero point nine, rug up to one.

SAMSo I keep a running sum of the probabilities, zero point five, zero point eight, zero point nine, one, and find the first total bigger than my random number. A running sum, then a search.

MAYAExactly. That list of running sums is what math calls the cumulative distribution, or CDF, and finding where your random number lands in it is called inverse-CDF sampling. You'll see that name in the lab.

05 The data structureMath & data structures

SAMSo the model is a dict of dicts. But it only looks at one previous word. The definition said words, plural.

MAYALet us try plural and watch it fail. Key the table on the whole history, the full list of words so far. A real vocabulary, remember, the fixed list of everything the model can read and write, has around fifty thousand entries. Those entries are called tokens: whole words or pieces of words, which is the whole topic of the next episode. For today, a token is basically a word. How many ten-word histories is that?

SAMFifty thousand choices for the first word, times fifty thousand for the second, and so on for ten slots: fifty thousand to the tenth. That's, what, ten to the forty-seven rows? No disk on Earth holds that. And almost every row is a history nobody has ever written, so the first time a user types something new, there's no row at all.

MAYAWhich is nearly every sentence. A table cannot generalize. It knows "the cat sat" and has no idea "the dog sat" should behave similarly. The fix has two parts. Give every word a vector, which, remember, is just a short fixed-length list of numbers, arranged so that words used in similar contexts get similar vectors. The book calls these embeddings. Then replace the table with a function that reads those vectors and outputs a probability for every vocabulary word. That function is a neural network. For now, think of it as a big function built mostly from multiply-and-add steps, like the dot product from the Foundations module, with a few simple non-linear steps mixed in, and whose numbers are tuned automatically from text. We build one later in the course. Similar inputs give similar outputs, so unseen histories still get sensible predictions.

SAMSo an embedding is just a lookup from a word to a short list of floats, and the network is a function from those lists to a probability dict. Give me a concrete picture.

MAYAIn this module's third episode, the lab has you train the smallest version, on a toy corpus, meaning a collection of text, that we generated: thirty-three words, eight numbers each. We score closeness with cosine similarity, which runs from minus one to one and measures how nearly two vectors point the same way. After a second of training, which means letting the computer nudge all those numbers, over and over, so the predictions on the text get better, "cat" has cosine similarity one point zero, to two decimals, with "dog", and "park" sits at zero point nine nine with "garden". Nobody said cats and dogs are animals. They appeared in the same slots, so prediction pulled them together.

SAMCosts, then. Dict lookup is constant time on average. Sampling builds a running sum over the row, linear in the row length, then binary-searches it, logarithmic. Memory is one entry per pair you wrote down.

MAYAAnd a neural model trades that table for a fixed set of parameters, the tuned numbers inside the network, embeddings included, and a forward pass, which is just one call of that function from input to output. A forward pass costs the same whether the history is common or brand new.

06 Code walkthroughCode

MAYATwo functions carry the idea. Sample next takes a row, the little dict of next words and their probabilities, and a uniform number u from zero up to, but not including, one. First a guard: if u is outside that range, raise an error. Then we take the cumulative sum of the probabilities, so each word's segment ends at its running total. Searchsorted finds the first segment whose right edge is strictly greater than u. Then we clamp the index to the last word. With real numbers: for the row after "the", the cumulative sum turns zero point five, zero point three, zero point one, zero point one into zero point five, zero point eight, zero point nine, one. Say u is zero point six two. Searchsorted is NumPy's binary search on a sorted array: the first running total bigger than zero point six two is zero point eight, at index one, so the word is "dog". The clamp is just the min of that index and the last index.

SAMThe clamp is for floating point. Zero point seven plus zero point two plus zero point one, our row for "sat", comes out a hair under one in floating point, and a u in that sliver would fall off the end of the array.

MAYAExactly. Then generate. The context starts as a list holding the start token, our start-of-sentence marker. Then loop at most max tokens times, twenty by default. Each pass: look up the row for the last word in the context, that's context at minus one; draw u from the random generator; choose a word with sample next; and record a trace entry, a little dict saying what the model saw, the u it drew and the word it chose, so we can print it later. With seed zero: the context is just the start marker, its row is "the" zero point six, "a" zero point four, and u comes out zero point six three seven. That's past zero point six, so the word is "a".

SAMAnd break on the stop token, otherwise append the word to the context. So after that first step the context is the start marker, then "a", and the next lookup uses the row for "a".

SAMThat append is the whole trick: the word chosen at step t becomes part of the input at step t plus one, so the model keeps feeding on its own output. That's what "autoregressive" means.

MAYAYes. And we pass the random generator in and draw exactly one number per step, so every run is reproducible from a seed, the starting number for the random generator: same seed, same draws, same sentence.

07 Look insideCode

MAYARun the lab with seed zero and print the trace.

SAMStep zero: last word is the start token, u is zero point six three seven, so "a". Step one: u zero point two seven, row for "a", so "cat". Then "sat", "on", "a", "rug", "and", "a", "dog". Step nine: u is zero point nine three five, which lands in the last tenth of the row for "dog". That's the stop token.

MAYASum the logs of those ten probabilities: minus ten point eight one. About two in a hundred thousand. Now test the sampler without reading its code. Draw ten thousand words from the row for "the". You should see cat about zero point four nine five, dog zero point three zero, mat zero point zero nine eight, rug zero point one zero four. Close, not exact, and closer the more you draw.

SAMA statistical test for a random function.

MAYALast plot: a thousand seeds, histogram of sentence lengths. The median is five words, but the mean is almost seven, because of a long tail: the longest of the thousand runs is fifty-three words. That tail is why there is a length cap.

08 Origin story

MAYAThe prediction game is older than computers playing it. Soon after founding information theory, the mathematics of measuring how much information a message carries, Claude Shannon asked people to guess a text one letter at a time: twenty-six letters plus a space. After each wrong guess you learn the right letter and continue. He published in nineteen fifty-one. The psychologists George Miller and Jennifer Selfridge had studied how context makes words predictable the year before.

SAMWhy letters, not words?

MAYAShannon wanted to measure how much information English carries.

SAMWhich is really a compression question. If you can guess the next letter, it carries little information, the same reason gzip shrinks repetitive log files so well.

MAYAExactly. His estimates came out between about zero point six and one point three bits per letter, versus nearly five bits if all twenty-seven symbols were equally likely: picking one of twenty-seven equally likely options takes, on average over a long text, about four point seven five yes-or-no questions per letter, because two to the four point seven five is about twenty-seven. That gap is redundancy, and a language model is a machine for exploiting it.

SAMAnd the name "language model"?

MAYAThe book credits Fred Jelinek's group at IBM, who from the mid seventies built speech recognizers that used statistical models of word sequences to pick the most plausible transcription, and called that part the language model. Then the neural line: Bengio and colleagues in two thousand three replaced the count table with a neural network and learned embeddings.

SAMThe very fix we just derived.

MAYAThe network design behind today's chat models, called the transformer, came in twenty seventeen; we build one later in the course. By twenty nineteen, prompting a large enough predictor could perform tasks it was never explicitly trained for.

SAMAnd ELIZA was the road not taken.

MAYARules instead of prediction. It also has a darker story about how people respond to machines that talk, which we save for episode three.

09 Where it breaks

SAMFirst gotcha, I assume: my "always pick the best word" idea.

MAYAHere is why it must loop. Always taking the single most likely next word is called greedy choice. With greedy choice, the next word is a pure function of the previous word: same input, same output, every time. Our table has eleven words that can be emitted, every key except the start marker.

SAMSo in twelve steps without a stop, some word repeats. Pigeonhole: twelve items into eleven boxes means some box gets two. And once a word repeats, the deterministic rule replays everything after it. Forever.

MAYAThat is the whole proof. On our table the most likely successors form the cycle the, cat, sat, on, the. Sampling escapes because every lap has a real chance of stop or a detour. Across twenty seeds, greedy stops zero times; sampling stops twenty times. Second gotcha: no length cap. Even sampling does not guarantee termination. A table where "x" always follows "x" never ends, which is why every inference server, the software that runs a trained model for its users, has a maximum-tokens setting: a hard cap on how many tokens it will generate.

SAMThird: multiplying probabilities instead of adding logs. Passes the unit test on five words, returns zero on a real document.

MAYAFourth: a row that does not sum to one. Say a typo makes "the" sum to zero point nine.

SAMThen the ruler has a gap at the end, any u above zero point nine falls into it, and my clamp quietly hands it to the last word. So "rug" comes out twice as often as the table says, and nothing crashes.

MAYAThe worst kind of bug. Validate before you sample.

SAMAnd a soft one: saying the model "knows" things.

MAYAGood instinct. It assigns probabilities that reflect patterns in text. Whether that is knowing is a real debate, and the book has a whole section on the words we use for these systems.

10 Real world and research

SAMSo when I use a chat model, my prompt gets chopped into tokens, the words and pieces of words the model reads, and that's the context. A network computes the next-token distribution, one probability per vocabulary entry. Some decoding rule, meaning the rule for picking, like greedy or sampling, picks a token, it gets appended, and it repeats until a stop token or the cap.

MAYAEvery chat model runs exactly that loop. On screen you'll see two labels we haven't defined yet, logits and softmax. Logits are just raw scores, one per vocabulary entry, and softmax is the step that turns those scores into probabilities adding up to one. We meet both properly in this module's third episode. For scale, the book cites Llama three point one: four hundred and five billion parameters, the tuned numbers inside the network, trained on more than fifteen trillion tokens. Same loop. What changed is the function computing the distribution.

SAMSo the recipe is just "make it bigger"?

MAYABigger in a balanced way. The book quotes the compute-optimal result from Hoffmann and colleagues in twenty twenty-two: for a fixed compute budget, grow the parameter count and the number of training tokens together, each roughly as the square root of the compute. On screen, N is the parameter count, D is the number of training tokens, and C is the compute budget, meaning the total amount of arithmetic you can afford. The little "opt" means the best choice for that budget, and the symbol between them, shaped like a stretched-out Greek alpha, means "grows in proportion to". C to the one half is the square root of C. So four times the compute means about twice the parameters and twice the tokens. A huge model starved of text wastes its budget, and so does a tiny model fed everything. Later in the course, in a paper module on scaling laws and Chinchilla, you fit those curves yourself.

SAMWhat's open, research-wise?

MAYAWhy does pure prediction produce arithmetic and facts, and where inside the network do they live? That is a field called interpretability, the study of what is going on inside a trained network, and it gets its own module later in the course. The book makes the same point about grammar: a predictor also picks up who did what to whom, and which mentions refer to the same person, and researchers have found individual parts of networks that track those relations. Yet the same models rarely stop to ask a clarifying question when a request is ambiguous.

SAMAnd decoding, the rule for picking each next token, is open too. Greedy, sampling, and temperature, a knob we meet later in the course that makes sampling stick closer to the likely words or wander toward unlikely ones, all measurably change answers. Plus the bias question.

11 Recap

MAYAA language model outputs a probability distribution over the next word given the previous words. Generation is a loop: look up, draw, append, repeat, until stop or a cap. A sentence's probability is the product of its steps, and we sum logs because products underflow. A table keyed on whole histories can neither exist nor generalize, hence embeddings and neural networks. Greedy choice makes the loop a deterministic walk that must stop or cycle.

SAMThree questions to answer out loud. Why does a language model output a whole distribution instead of one word? Why can't a table keyed on the entire history be the model? And why does always taking the most likely word loop forever on our table, while sampling escapes?

12 Your turn: the lab

MAYAIn the lab you write the table validator, the inverse-CDF sampler, the generation loop and log-probability scoring, and you draw the table as a graph and watch the loop step by step. The last cell builds the same kind of table from a real paragraph of English and generates from it.

SAMAnd the predictions?

MAYAThree numbers we didn't compute today. The probability that the whole sentence is exactly "a dog", then stop. How many of a thousand seeded runs hit the default cap of twenty words. And what zero point nine to the eleven hundredth prints in Python.

SAMAnd the break-it, where I'm wrong about greedy on purpose.

MAYAWith twenty seeds and error bars. Write your hypothesis down first.