# 18. Generation strategies > Given the model’s scores, how do you actually pick the next word? LLM by Hand · Theory · runs in your browser · interactive page: https://llm.liko.page/learn/generation/ Level 17 always took the word with the top score (greedy). This level shows the other ways to pick. The model’s job ends with one score per word in its vocabulary. Turning those scores into the next word is a separate decision, and it changes the text a lot. The same model can write plain text, random text, or the same words again and again, depending only on how you pick. This level uses one tiny example from start to end: after “the cat sat on the”, five candidates with these scores. | word | mat | sofa | rug | roof | moon | |---|---|---|---|---|---| | score | 2.0 | 1.5 | 1.0 | 0.0 | −1.0 | ## 1. Greedy: always take the top word The simplest rule: turn the scores into probabilities with softmax (level 10) and take the most likely word. No randomness at all. ★ marks greedy’s pick. *[Interactive lab: Pick — open the page to use it]* **Question.** Scores: mat 2.0, sofa 1.5, rug 1.0, roof 0.0, moon −1.0. With T = 1, greedy picks mat. Use e² ≈ 7.4, e^1.5 ≈ 4.5, e¹ ≈ 2.7, e⁰ = 1, e^−1 ≈ 0.4. What probability does softmax give mat? (2 decimals) *Answer it on the page to check your work.* Temperature from level 10 still works here: divide every score by T before softmax. Small T sharpens the probabilities, large T flattens them. **Predict.** You sample (not greedy) with T = 0.01, so every score is multiplied by 100. What does sampling do now? A. Picks mat almost every time, like greedy B. Picks all five words about equally C. Picks the same words as at T = 1, just as often *Answer it on the page to check your work.* ## 2. Top-k: only the k best words get a chance Sampling from all five words means “moon” sometimes wins. With a vocabulary of 50,000 words, there are thousands of unlikely words. Together they have a real probability, so sometimes one of them is picked and the sentence stops making sense. **Top-k** keeps only the k most likely words, sets the rest to 0, and divides by the new total so the kept probabilities add up to 1 again. Then it samples. Switch the lab to “top-k”. **Question.** Probabilities: mat 0.46, sofa 0.28, rug 0.17, roof 0.06, moon 0.03. Top-k with k = 2 keeps mat and sofa and divides by their total. What is sofa’s new probability? (2 decimals) *Answer it on the page to check your work.* **If you are stuck: Why divide again after cutting the words?** The kept probabilities no longer add up to 1. With k = 2, mat and sofa together have about 0.46 + 0.28 = 0.74. A random pick with weights needs weights that add up to 1, so divide each by 0.7439. The order stays the same; only the scale changes. ## 3. Top-p: keep words until they cover p of the probability A fixed k does not fit every case. After “the cat sat on the”, maybe ten words are reasonable. After “2 + 2 =”, only one is. **Top-p** (also called nucleus sampling) adapts: 1. Sort the words by probability, largest first. 2. Go down the list. Keep a word if the words ranked *above* it add up to less than p. So the word that pushes the total past p is still kept, and every word after it is dropped. 3. Divide the kept words by their new total. Switch the lab to “top-p” with p = 0.9. **Question.** Sorted probabilities: 0.4631, 0.2809, 0.1704, 0.0627, 0.0231. Top-p with p = 0.9 keeps words, starting from the largest, until the running total reaches 0.9. How many words does it keep? *Answer it on the page to check your work.* Now write it. `np.argsort(-probs)` gives the word indices from most to least likely, and `np.cumsum` gives running totals: `np.cumsum([0.5, 0.3, 0.2])` is `[0.5, 0.8, 1.0]`. The total of the words *above* a word is its running total minus its own probability. **Code question.** Finish `top_p`: `keep_sorted` must be True for every word to keep, in sorted order. Fill in the blank (`____`): ```python def top_p(probs, p): order = np.argsort(-probs) # most likely first sorted_p = probs[order] cum = np.cumsum(sorted_p) # running totals keep_sorted = ____ keep = np.zeros(len(probs), dtype=bool) keep[order] = keep_sorted # back to the original word order out = np.where(keep, probs, 0.0) return out / out.sum() probs = softmax(np.array([2.0, 1.5, 1.0, 0.0, -1.0])) print("cum:", np.round(np.cumsum(np.sort(probs)[::-1]), 4)) print(np.round(top_p(probs, 0.9), 4)) ``` *Answer it on the page to check your work.* ## 4. Beam search: the best word is not always the best start Greedy picks the best *word* at each step. That does not give the best *sentence*. Here is a tree of two steps. The first word is a, the or one; each has its own probabilities for the second word. **Question.** First word: a 0.5, the 0.4, one 0.1. After a: dog 0.4, cat 0.3, fox 0.3. After the: dog 0.9, cat 0.05, fox 0.05. After one: dog 0.5, cat 0.25, fox 0.25. Greedy takes the best word at each step. What is the probability of the two-word sentence greedy writes? (2 decimals) *Answer it on the page to check your work.* **Predict.** First word: a 0.5, the 0.4, one 0.1. After a: dog 0.4, cat 0.3, fox 0.3. After the: dog 0.9, cat 0.05, fox 0.05. After one: dog 0.5, cat 0.25, fox 0.25. Greedy writes “a dog”, with probability 0.20. Beam search with width 2 keeps the two best first words (a and the) and then looks at all their second words. Will it find a better sentence than greedy’s 0.20? A. Yes, it finds one with higher probability B. No: “a” was the best first word, so the best sentence starts with “a” C. No: with only two words, every method finds the same sentence *Answer it on the page to check your work.* **Beam search** keeps the `width` best partial sentences at every step instead of just one, extends each of them, and keeps the best `width` again. Width 1 is greedy. *[Interactive lab: Beam — open the page to use it]* **Question.** First word: a 0.5, the 0.4, one 0.1. After a: dog 0.4, cat 0.3, fox 0.3. After the: dog 0.9, cat 0.05, fox 0.05. After one: dog 0.5, cat 0.25, fox 0.25. What is the probability of the best sentence that beam width 2 finds? (2 decimals) *Answer it on the page to check your work.* **Deeper: In code, beam search adds logs instead of multiplying** A sentence’s probability is a product of many numbers below 1. A 100-word sentence where every word has p = 0.1 has probability 10⁻¹⁰⁰. Models compute with 32-bit numbers, and in them that is already exactly 0 (the smallest is about 10⁻⁴⁵). The smallest normal 64-bit number is about 10⁻³⁰⁸, a few hundred words later. Once the products become 0, all sentences get the same score. So beam search adds natural logs (ln) instead: ln(a × b) = ln a + ln b. The 100-word sentence scores 100 × ln 0.1 ≈ −230.3, an ordinary number, and comparing these sums ranks sentences exactly like comparing the products. **Deeper: Why chat models rarely use beam search** Beam search finds sentences the model rates as very likely. For translation, where there is roughly one right answer, that is what you want. For open-ended writing it gives bad results: the most likely text is short, plain and repetitive, because “safe” common words always score well. It also needs `width` times as much arithmetic. There is a second problem: longer sentences multiply more numbers below 1, so beam search prefers to stop early. Implementations divide the sum of the logs by the length to compensate. ## 5. Why greedy repeats itself Now a real model, built in three steps: 1. **Rules.** Sentences follow one pattern, “the ⟨animal⟩ ⟨verb⟩ ⟨on or in⟩ the ⟨place⟩ .”, with cat, sat, on and mat more common than the other choices. 2. **Text.** `demo.py` writes 3,000 sentences (21,000 words) from those rules. 3. **Model.** The simplest possible language model: it looks at the last two words, and the probability of each next word is how often it followed those two words in the text. 4% of every prediction is spread over all 14 words, so words that never appeared there are possible but rare. **Predict.** A counting model looks at the last two words. It has seen “the cat sat on the mat .” far more than any other sentence. Greedy writes 14 words starting from “the”. What do you expect? A. The same sentence again and again B. Fourteen words, all different C. It stops after one sentence *Answer it on the page to check your work.* *[Interactive lab: Repeat — open the page to use it]* Greedy writes the most common sentence, then lands back on “. the”, which is exactly where it started. Same input, same choice, forever. Real models loop the same way, on longer cycles. A **repetition penalty** lowers the score of words that were already written. The version here subtracts a fixed amount for every earlier use: score = ln p − penalty × (times written). This counting version is often called a frequency penalty. Another common version lowers a used word’s score only once, no matter how many times the word appeared. Drag the penalty to 1.0 and select the second “cat”/“dog” position. **Question.** After “. the”, ln p(cat) = −0.7752 and ln p(dog) = −1.1852. “cat” has already been written once, “dog” never. With penalty 1.0, score = ln p − 1.0 × (times written). What is cat’s score? (4 decimals) *Answer it on the page to check your work.* **If you are stuck: If the penalty fixes loops, why not make it large?** Because it lowers the score of every repeated word, including the ones a sentence needs. “the” and “.” must appear in every sentence of our rules. Push the penalty to 3 and watch the lab: the rules start to break. In practice the penalty stays small, and sampling (sections 2 and 3) does most of the work of avoiding loops. ## 6. Diversity against quality The sentence rules are ours, so the model’s output can be graded exactly: does every word sit where the rules allow? Below, each strategy writes 200 continuations of six words after “the”. **Predict.** Sampling at T = 2 flattens the probabilities, so the 4% for “any word” matters a lot more. Of 200 six-word continuations, what fraction do you expect to follow the sentence rules? A. About 100% B. About 80% C. About 20% *Answer it on the page to check your work.* *[Interactive lab: Tradeoff — open the page to use it]* From `demo.py` (fixed random numbers, so these do not move): | strategy | different continuations (of 200) | follow the rules | |---|---|---| | greedy | 1 | 100% | | T = 0.5 | 47 | 100% | | T = 1 | 96 | 81% | | T = 2 | 192 | 20% | | top-k 3 | 53 | 98% | | top-p 0.9 | 62 | 100% | Greedy is perfectly correct and says one thing. High temperature says everything, mostly wrong. Top-p keeps all the reasonable words and drops the many unlikely words, which is why it is the usual default, often combined with a temperature a bit below 1. **Try it** Find a setting in the lab with more than 100 different continuations and at least 95% following the rules. Is it possible here? Which setting gets you closest? **Question.** After “on the” the model gives mat 0.3445, rug 0.2451, park 0.1984, roof 0.1835, and 0.0029 to each of the other 10 words. Top-p with p = 0.9 keeps how many words? *Answer it on the page to check your work.* ## 7. Writing is a loop Every strategy on this page runs inside the same loop: run the model on everything written so far, pick one token, append it, run again. Count tokens from 0. Written naively, the step that predicts token 100 recomputes all the work for tokens 0 to 99, which the earlier steps already did. Most of it doesn’t need redoing. In a model with the causal mask (level 15), each token’s k and v depend only on that token and the ones before it, and those never change once they are written. So a real model stores every token’s k and v when it is computed, in a **KV cache**. Then each step gives the model only the newest token and computes only that token’s q, k and v. Take a small case. Tokens 0, 1 and 2 have already been processed by the model, so their k and v are in the cache. The model has just picked token 3. To predict token 4, it gives token 3 to the model. | | without a cache | with a cache | |---|---|---| | tokens given to the model | 0, 1, 2, 3 | 3 | | q computed for | 4 tokens | 1 token | | k and v computed for | 4 tokens | 1 token, then 3 rows come from the cache | | scores | 4 × 4, but only the last row is used | 1 × 4: exactly that last row | **Question.** With a KV cache: tokens 0, 1, 2 are in the cache, and token 3 is given to the model. How many rows does Q have at this step? *Answer it on the page to check your work.* Without a cache, the work grows with every token. Writing tokens 0 to 99 one at a time computes k for 1 token, then 2, then 3, and so on up to 100. **Question.** No cache. Writing tokens 0 to 99 one at a time, the k of 1 token is computed at the first step, 2 at the second, …, 100 at the last. How many k computations is that in total? *Answer it on the page to check your work.* **Question.** Tokens 0 to 98 have already been processed by the model, and their k and v are in the KV cache. The model has just picked token 99. To predict token 100, it gives token 99 to the model. For how many tokens must it compute k and v now? *Answer it on the page to check your work.* [Level 20](/learn/inference-cost/) shows how big that cache gets, and one way models shrink it. ## 8. Put it together A real sampler combines two of this page’s tools: divide the scores by the temperature (level 10), keep only the top k, and turn the result into probabilities that add up to 1. `np.sort(x)[::-1]` sorts from largest to smallest, so `np.sort(x)[::-1][k - 1]` is the k-th largest score. As with masks in level 15, `np.where(cond, a, b)` takes a where `cond` is True and b everywhere else, and a score of −∞ gets probability 0 after softmax. **Code question.** Write the sampler’s filter: divide the scores by T (given), keep only the k largest, and return probabilities that add up to 1, with 0 for the dropped words. Fill in the blank (`____`): ```python def filter_probs(scores, T, k): z = scores / T ____ scores = np.array([2.0, 1.0, 0.5, -1.0]) print(np.round(filter_probs(scores, 1.0, 2), 4)) ``` *Answer it on the page to check your work.* That is the whole path from scores to text. [Level 19](/learn/modern-llm/) returns to the block itself: three parts that today’s models have changed. ## You can now - Turn scores into the next word with greedy, temperature, top-k or top-p, and compute the kept probabilities by hand. - Score whole sentences in beam search and see when it beats greedy. - Count the work a KV cache saves: one new q, k and v per step instead of all of them.