Repository navigation
Commit b7688fe
Add top-k sampling support to llm Sampler (#19122)
Summary:
The existing `Sampler` in `extension/llm/sampler` supports greedy
(temperature=0), full multinomial, and top-p (nucleus) sampling, but had
no top-k mode. Top-k is a common companion / alternative to top-p and is
trivial to add given the existing infrastructure.
This change adds:
- `Sampler::set_topk(int32_t)` to enable top-k filtering. `k <= 0` or
`k >= vocab_size` disables it (default).
- A new private `sample_topk` template that uses `std::partial_sort` to
pick the k highest-probability tokens (O(n log k) — heap-based partial
sort), and CDF-samples from the top-k slice (scaling `coin` by the
top-k sum is mathematically equivalent to renormalizing). Same shape
as the existing `sample_topp`. Sums and CDF are accumulated in `float`
so FP16/BF16 inputs don't lose precision over k summands.
- Wiring in `Sampler::sample` so that when top-k is enabled it takes
precedence over top-p — the two modes are mutually exclusive in this
implementation. With both disabled, falls back to multinomial,
matching today's behaviour.
The existing constructors are unchanged, so this is fully
backward-compatible. Float, FP16, BF16, and uint16_t logit dtypes are
all supported via the existing template instantiations.
A follow-up diff will wire `set_topk` into the `text_llm_runner`
`GenerationConfig` so callers can opt into top-k from the runner.
Differential Revision: D1023851041 parent 56da964 commit b7688fe
3 files changed
Lines changed: 178 additions & 1 deletion
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
69 | 69 | | |
70 | 70 | | |
71 | 71 | | |
| 72 | + | |
| 73 | + | |
| 74 | + | |
| 75 | + | |
| 76 | + | |
| 77 | + | |
| 78 | + | |
| 79 | + | |
| 80 | + | |
| 81 | + | |
| 82 | + | |
| 83 | + | |
| 84 | + | |
| 85 | + | |
| 86 | + | |
| 87 | + | |
| 88 | + | |
| 89 | + | |
| 90 | + | |
| 91 | + | |
| 92 | + | |
| 93 | + | |
| 94 | + | |
| 95 | + | |
| 96 | + | |
| 97 | + | |
| 98 | + | |
| 99 | + | |
| 100 | + | |
| 101 | + | |
| 102 | + | |
| 103 | + | |
| 104 | + | |
| 105 | + | |
| 106 | + | |
| 107 | + | |
| 108 | + | |
| 109 | + | |
| 110 | + | |
| 111 | + | |
| 112 | + | |
| 113 | + | |
| 114 | + | |
| 115 | + | |
| 116 | + | |
| 117 | + | |
| 118 | + | |
| 119 | + | |
| 120 | + | |
| 121 | + | |
72 | 122 | | |
73 | 123 | | |
74 | 124 | | |
| |||
186 | 236 | | |
187 | 237 | | |
188 | 238 | | |
189 | | - | |
| 239 | + | |
| 240 | + | |
| 241 | + | |
| 242 | + | |
190 | 243 | | |
191 | 244 | | |
192 | 245 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
44 | 44 | | |
45 | 45 | | |
46 | 46 | | |
| 47 | + | |
| 48 | + | |
| 49 | + | |
| 50 | + | |
| 51 | + | |
| 52 | + | |
| 53 | + | |
47 | 54 | | |
48 | 55 | | |
49 | 56 | | |
50 | 57 | | |
51 | 58 | | |
52 | 59 | | |
53 | 60 | | |
| 61 | + | |
| 62 | + | |
54 | 63 | | |
55 | 64 | | |
56 | 65 | | |
| |||
60 | 69 | | |
61 | 70 | | |
62 | 71 | | |
| 72 | + | |
| 73 | + | |
63 | 74 | | |
64 | 75 | | |
65 | 76 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
8 | 8 | | |
9 | 9 | | |
10 | 10 | | |
| 11 | + | |
| 12 | + | |
11 | 13 | | |
12 | 14 | | |
13 | 15 | | |
| |||
39 | 41 | | |
40 | 42 | | |
41 | 43 | | |
| 44 | + | |
| 45 | + | |
| 46 | + | |
| 47 | + | |
| 48 | + | |
| 49 | + | |
| 50 | + | |
| 51 | + | |
| 52 | + | |
| 53 | + | |
| 54 | + | |
| 55 | + | |
| 56 | + | |
| 57 | + | |
| 58 | + | |
| 59 | + | |
| 60 | + | |
| 61 | + | |
| 62 | + | |
| 63 | + | |
| 64 | + | |
| 65 | + | |
| 66 | + | |
| 67 | + | |
| 68 | + | |
| 69 | + | |
| 70 | + | |
| 71 | + | |
| 72 | + | |
| 73 | + | |
| 74 | + | |
| 75 | + | |
| 76 | + | |
| 77 | + | |
| 78 | + | |
| 79 | + | |
| 80 | + | |
| 81 | + | |
| 82 | + | |
| 83 | + | |
| 84 | + | |
| 85 | + | |
| 86 | + | |
| 87 | + | |
| 88 | + | |
| 89 | + | |
| 90 | + | |
| 91 | + | |
| 92 | + | |
| 93 | + | |
| 94 | + | |
| 95 | + | |
| 96 | + | |
| 97 | + | |
| 98 | + | |
| 99 | + | |
| 100 | + | |
| 101 | + | |
| 102 | + | |
| 103 | + | |
| 104 | + | |
| 105 | + | |
| 106 | + | |
| 107 | + | |
| 108 | + | |
| 109 | + | |
| 110 | + | |
| 111 | + | |
| 112 | + | |
| 113 | + | |
| 114 | + | |
| 115 | + | |
| 116 | + | |
| 117 | + | |
| 118 | + | |
| 119 | + | |
| 120 | + | |
| 121 | + | |
| 122 | + | |
| 123 | + | |
| 124 | + | |
| 125 | + | |
| 126 | + | |
| 127 | + | |
| 128 | + | |
| 129 | + | |
| 130 | + | |
| 131 | + | |
| 132 | + | |
| 133 | + | |
| 134 | + | |
| 135 | + | |
| 136 | + | |
| 137 | + | |
| 138 | + | |
| 139 | + | |
| 140 | + | |
| 141 | + | |
| 142 | + | |
| 143 | + | |
| 144 | + | |
| 145 | + | |
| 146 | + | |
| 147 | + | |
| 148 | + | |
| 149 | + | |
| 150 | + | |
| 151 | + | |
| 152 | + | |
| 153 | + | |
| 154 | + | |
0 commit comments