采样Sampling

Last lesson the vocab turned text into token ids fed to the model; the model computes all the way through (M4a) and finally, at the output layer, emits a row of logits - one raw score per token in the vocab, a higher score meaning the model "favors" it more as the next word. But the next word can be only one, so how do you pick it from tens of thousands of scores? This lesson's topic, sampling, is that last step "from a row of scores to one token".

Sampling is far more than "pick the max". Always picking the top score makes the model rigid, repetitive, dull; but pure randomness babbles. Real sampling is a combo of prune + shape + draw: first cut hopeless candidates, then tune the distribution's softness, push down words that keep repeating, and only then draw one by probability. llama.cpp makes these means into pluggable samplers, strung into a sampler chain.

From logits to a token

First, see sampling's input and output clearly. The input is a candidate array: one record per token in the vocab, holding the token id, its logit (raw score), and a probability p computed later. The output is one selected id among them. What sampling does is work over this array and finally pick one record.

This candidate array is called llama_token_data_array in llama.cpp, each record a llama_token_data. The whole pipeline is essentially repeatedly rewriting this array: some samplers slam certain candidates' logit to negative infinity (a strike-out), some recompute probabilities and re-sort, and the last step selects one, recording its index in the array's selected field.

So the pipeline looks roughly like this: penalties damp repeats first, top-k/top-p chop the long tail, then temperature tunes the softness of what remains, and finally dist draws one by probability (or greedy takes the max). Each step does one small thing; stacked together they are a complete sampling strategy.

Worth stressing: this pipeline touches only logits/probabilities, never the model itself. The model dutifully computes the same row of logits each step; how a word is chosen from them is entirely up to the sampling layer. So "change the generation style" needs no change to the model, just sampling parameters - which is why one model can be rigorous one moment and wildly imaginative the next.

Picture this row of logits as a mountain range of peaks and valleys: the more the model favors a word, the higher its peak. Sampling chooses by the shape of this range - pick only near the high peaks (conservative), or give the foothills a chance too (divergent). Every later sampler is really reshaping this range's outline before deciding where to land. Hold this picture, and top-k and temperature later all become easy. Walking one concrete example through this pipeline makes it click:

The sampler interface

// simplified from include/llama.h
struct llama_sampler_i {
    const char * (*name)  (...);                          // name (nullable)
    void (*accept)(llama_sampler *, llama_token);          // feed back chosen token (nullable)
    void (*apply) (llama_sampler *, llama_token_data_array * cur_p); // edit/rank candidates (required)
    void (*reset)(llama_sampler *);                        // clear state (nullable)
};
struct llama_sampler { const llama_sampler_i * iface; llama_sampler_context_t ctx; };

See what a sampler actually is. llama_sampler_i is just a set of function pointers: apply (the core, rewrites the candidate array), accept (feeds the chosen token back so stateful samplers can keep tally), reset (clear state), plus name/clone/free. With a state blob ctx, it forms a llama_sampler.

Here apply is the only required one - it takes the candidate array and edits it by its own rule (strike some out, re-rank, recompute probabilities). accept is nullable, needed only by samplers with memory: the penalty must remember which tokens appeared before, mirostat must adjust by feedback; both use accept to take "the just-chosen token" into their state.

Abstracting samplers into a unified interface buys composability above all. Since they look alike, they can line up like blocks, each acting on the same candidate array. Next section's "sampler chain" is the direct product of this composability.

A word on the state ctx: it is each sampler's private ledger. A stateless sampler (like top_k) has an almost-empty ctx; a stateful one (penalties/mirostat/grammar) keeps history, parameters, feedback here. Samplers do not interfere with one another, each keeping its own books.

Why are several interface functions marked "nullable"? Because not every sampler needs everything. A pure "one cut" sampler like top_k needs no memory and thus need not implement accept; reset matters only when reusing one sampler across several generations. Making these optional lets the simplest sampler write just an apply - tidy and clear; the interface demands only "the required thing", the rest on demand.

The sampler chain

The sampler chain llama_sampler_chain is itself a sampler - it holds a list of child samplers, and its apply simply runs each child's apply in add-order. This is the classic "composite" pattern: a chain looks like one sampler outside, while inside it is a queue of many.

# pseudocode: build a sampler chain
chain = llama_sampler_chain_init(params)
chain.add(llama_sampler_init_penalties(...))    # damp repeats
chain.add(llama_sampler_init_top_k(40))         # keep top 40
chain.add(llama_sampler_init_top_p(0.95, 1))     # nucleus
chain.add(llama_sampler_init_temp(0.8))          # temperature
chain.add(llama_sampler_init_dist(seed))         # draw by probability
id = llama_sampler_sample(chain, ctx, -1)         # run the whole chain -> return a token id

It is straightforward to use: chain_init an empty chain, chain_add samplers in the order you want, and finally llama_sampler_sample does it all - it reads a position's logits, forms the candidate array, runs the whole chain, returns the chosen token id, and conveniently accepts that token back.

Order matters. The same few samplers in a different arrangement can give different results: generally do penalties and pruning first (shrink the candidate set), then temperature (tune softness), and dist/greedy last (the actual selection). Putting "selection" last is because every earlier step is preparing a more reasonable candidate distribution for that "final kick".

This "chain" design essentially turns "the sampling strategy" into data (a list of sampler configs) rather than hardcoded code. So a user tuning a few parameters on the command line / config can assemble endlessly varied sampling behavior with not a line of the engine trunk changed - once more "gather the parts that vary".

An example of order affecting the result. If you put temperature before top-p, temperature first flattens the whole distribution and then top-p draws the range, so the nucleus comes out larger and more divergent; conversely, top-p fencing first then heating tunes randomness within an already-tightened small set, more controllable. Same parts, different order, subtly different "personality" - exactly the value of leaving order to user config.

In real projects this chain often has a conventional default order. llama.cpp's upper layer (common) roughly arranges "penalties -> pruning (top-k/top-p/min-p etc.) -> temperature -> dist". You need not memorize it, but the big principle suffices: shrink candidates first, tune softness next, draw last. The vast majority of sampling strategies are just additions and subtractions along this main axis.

Common samplers and greedy vs dist

Meet the common samplers. Each owns a stage: some "prune" (shrink the candidate set), some "shape" (change the distribution's form), some "select" (the final call).

Then the two pruning mainstays: top_k keeps the fixed top k by score and strikes out the rest; top_p (nucleus) accumulates by probability from high to low, keeping until the cumulative reaches p - the candidate count is adaptive (few when the distribution is peaked, many when flat). The two often pair: top_k chops the long tail, then top_p closes adaptively.

The "shape" representative is temperature temp: divide logits by a temperature T then softmax. Small T makes the distribution peakier (more deterministic), large T flatter (more random). It does not change the candidate set, only the softness. There are also penalties to damp repeats, mirostat to dynamically tune temperature and hold perplexity, each with a specialty.

A word on the penalties family, since it is closest to everyday experience. It watches recently generated tokens and penalizes oft-repeated words (lowering their logit), so the model is less likely to fall into a "broken record" loop. Common flavors are repeat, frequency, and presence penalties - "penalize if seen", "penalize more the more it appears", "penalize once seen, flatly". Tuning them balances "coherent" against "verbose".

Back to the main loop and the hand-off

Connecting sampling back to the main loop: per generated token, llama_decode (L17) computes logits, the chain picks one id from them, and this id is both turned back into text via the vocab (L20) for display and wrapped into a new batch fed back to llama_decode for the next step. Sampling is the "pick the next word" link in the autoregressive loop.

One hand-off with grammar (L23) to flag early: a grammar constraint is essentially a sampler too (its apply strikes out tokens that break the grammar). But it usually does not go into the main chain; it is a separate object applied before or after the chain per grammar_first - having learned the sampler interface here, grammar in L23 will come naturally.

A practical detail in passing: to make random generation reproducible, the key is dist's random seed. Fix the seed and the sampling parameters, and the same prompt runs to identical results - invaluable for debugging and comparison experiments. Conversely, to vary each run, let the seed change with time. Determinism is firmly in your hands.

Finally, clear a common misconception: sampling cannot conjure abilities the model lacks. It can only work on the row of logits the model gives - good sampling lets a model play to its strengths (fewer blunders, kept diversity), but cannot invent knowledge the model never learned. So when results are poor, first tell "the model is weak" from "the sampling is mistuned": the former needs a different model / fine-tuning (L24), the latter just parameter tweaks.