crit-hub

token-sampling

Token sampling on the GPU

The GPU applies the whole sampling law to the full vocabulary and checks sampled drafts by rejection sampling, so no logit row leaves the GPU and speculation keeps the output distribution.

The animation needs JavaScript; How it works below says the same in words.

The problem

  • Sampling needs the whole logit row, one value per vocabulary token (often hundreds of thousands), and copying it to the CPU every step stalls a decode loop that otherwise stays on the GPU.
  • Each request brings its own rules (penalties, temperature, top-k, top-p, min-p, a seed), and the GPU must apply them exactly as the reference sampler does.
  • Speculative decoding keeps a draft when it matches the model's token, but for a sampled request that test would change which text comes out.

How it works

  1. Penalties come first. Each token already in the output loses a frequency penalty per use plus a presence penalty; logit bias and bans apply at the same point.
  2. Temperature turns the values into weights, and the tokens rank by weight with ties going to the lower id. Top-k keeps the first k ranks, top-p the shortest prefix holding that share of the weight, and min-p drops weights below a fraction of the top one.
  3. A seeded draw, computed from the request's seed and the output position, picks the token where it lands among the kept weights. The same seed gives the same text.
  4. To speculate, a drafter samples drafts from its own law q. One pass of the full model gives a row per draft position, and the GPU runs the same law on each, counting the drafts before it as output.
  5. A draft d stands when u × q(d) is below p(d). The first rejected draft is replaced by a draw from max(p − q, 0), so the text follows the model's own law p exactly.

Configuration

Its options, set per engine in configuration.json. Each is checked against its type and range when the engine loads.

OptionDefaultValuesWhat it sets
roundsnativenative, torchwhat samples inside captured decode rounds (rounds:sampler): native, code/sampling.cu built for the device at load through torch's extension builder (where it does not build, the torch law, with a warning), or the torch law over sorted rows (slower)
configuration.json
{"plugins": {
  "use":     {"sampler": "token-sampling"},
  "options": {"token-sampling": {"rounds": "native"}}
}}

Pays off when

  • Requests sample (temperature above 0, with penalties or top-k, top-p and min-p filters) and the decode step runs entirely on the GPU, for example as a replayed CUDA graph.
  • Sampled requests should draft and verify too, not only greedy ones.

Doesn't pay off when

  • Only greedy decoding is served, and an existing argmax already matches plain decoding bit for bit.
  • Most requests keep many tokens (top-k above 64, or flat rows with no top-k), so rows miss the fast candidate path and the full-vocabulary search can take milliseconds per row.

What must stay true

  • Tokens rank by processed value with ties to the lowest id, and the rules run in the reference sampler's order and precision.
  • Each emitted token uses one draw keyed by seed, output position and purpose, so a rolled-back round needs no generator state.
  • Each verify column counts the drafts staged before it as output for its penalties.
  • A draft stands only when u × q(d) is below p(d) under the law q it was really drawn from. A rejection draws from max(p − q, 0), and a round that keeps every draft adds a bonus token from its last column.