acceptodds
Under review as a conference paper at ICLR 2027

FlashSampling: Fast and Memory-Efficient Exact Sampling

Abstract

Sampling from a categorical distribution is mathematically simple, but in large-vocabulary decoding, it often triggers extra memory traffic and extra kernels after the LM head. We present FlashSampling, an exact sampling primitive that fuses sampling into the LM-head matmul and never materializes the logits tensor in HBM. The method is simple: compute logits tile-by-tile on chip, add Gumbel noise, keep only one maximizer per row and per vocabulary tile, and finish with a small reduction over tiles. In tensor-parallel decoding, FlashSampling replaces the all-gather of logits with streaming peer-to-peer writes: This overlaps GPU-to-GPU communication with computation and HBM loads across up to 8 GPUs, with near-ideal scaling at large batch sizes. Our kernel is exact because decomposes over partitions; grouped variants for online and tensor-parallel settings are exact by hierarchical factorization of the categorical distribution. FlashSampling demonstrates kernel-level speedups on decode workloads across 4 different datacenter GPUs (H100, H200, B200, B300), and in end-to-end vLLM experiments, it reduces time per output token by up to on the models we test. These results show that exact sampling, with no approximation, can be integrated into the matmul itself, consolidating the bandwidth-bound sampling step in an efficient epilogue.

Primary area:
foundation or frontier models, including LLMs
Keywords:
inference accelerating

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_pyASOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper presents FlashSampling, a fused sampling method based on Gumbel-Max that integrates categorical sampling into the LM-head matmul. It computes logits tile by tile without materializing the full tensor in HBM, reducing memory traffic and separate sampling kernel overhead. In multi-GPU settings, FlashSampling replaces the standard all-gather of logits with streaming writes to overlap GPU communication. The authors also integrate FlashSampling into vLLM and demonstrate up to 10% - 3% reduction in time per output token for various model with exact sampling results.

Critical strengths
  1. The proposed method is simple and well motivated. By using the Gumbel-Max trick and tile-wise argmax, FlashSampling can fuse categorical sampling into the LM-head matmul without materializing the full logits tensor in HBM. The mathematical reasoning is clear and easy to follow.

  2. The implementation and experimental results are good. The authors implement Triton kernels and integrate FlashSampling into vLLM. All benchmarks are evaluated on modern GPU architectures like H100, H200, B200, and B300, and demonstrates actual speedups in both kernel-level benchmarks and end-to-end LLM serving.

Critical weaknesses
  1. The current implementation only supports unrestricted multinomial sampling, while commonly used decoding strategies such as top-k and top-p sampling are not supported as listed as future work. I’m not fully convinced how this method currently could be generalized and actually benefit the practical LLM serving especially for some reasoning models.

  2. While the authors evaluate multi-GPU performance up to TP8 in microbenchmarks, the actual e2e vLLM experiments only cover TP1 and TP2. It would be helpful to see how the performance will change in real TP4 serving workloads, especially considering the proposed multi-GPU communication optimization.

Questions for authors
  1. One is somehow mentioned in the weakness. Many model’s default setting does not incorporate unrestricted multinomial sampling. I am curious how commonly this sampling strategy is used in actual LLM serving and could the authors provide some discussion on the practical relevance of this setting?

  2. The contribution 2 mentioned "while grouped, online, and distributed variants are exact in distribution by hierarchical factorization through group log-masses." However I think main text does not mention this variant and Algorithm 1 looks like it does not include the group log-masses. Have these variants actually been implemented and evaluated, or are they mainly extensions?

  3. In Figure 5, the TPOT improvement for Qwen3-1.7B drops significantly at batch size 64, from 10.2% at batch size 32 to only 0.4%, while the other models do not show a similar drop. Could the authors explain this behavior?

3 comments

Thank you for the review and for the three specific questions.

W1 and Q1 (top-k, top-p, and how common unrestricted sampling is). We agree that truncated sampling is the common default. The models in our own evaluation ship with it: Qwen3-1.7B's default is T=0.6, top-k=20, top-p=0.95. The general response describes the fused top-k-then-top-p path and its measurements: with k=20 and p=0.95 it takes 24.7% to 36.0% less kernel time than FI1 at B=1 to 256 on one H200.

Temperature-only sampling is still a real setting. vLLM's own request defaults are temperature=1.0, top_p=1.0, and top-k disabled, and the OpenAI chat completions API has no top-k parameter. vLLM does apply a model's generation_config.json when the model ships one, which is why Qwen3 runs with truncation unless the request overrides it. Temperature-only sampling is also what one uses when samples must follow the model's own distribution.

We also have one data point on a reasoning model. In the GSM8K check of Section 4.6, the vLLM baseline ran Qwen3-1.7B in thinking mode with its default truncation (T=0.6, top-k=20, top-p=0.95), while FlashSampling ran temperature-only at T=0.6. Accuracy was 89.6% against 89.4% (paired bootstrap, p=0.776). The vLLM baseline run temperature-only scored 88.4% (p=0.080 against the truncated baseline, p=0.181 against FlashSampling). On this task, dropping truncation did not change accuracy measurably. We will state these sampling parameters in Section 4.6 and add the temperature-only baseline, which is the matched comparison.

W2 (end-to-end results beyond TP=2). The paper's end-to-end runs use TP=1 and TP=2. At the kernel level the advantage over FI2 grows from 1.3 to 1.6x at TP=2 to 1.6 to 2.3x at TP=4 and 1.9 to 3.0x at TP=8 (Table 6).

Q2 (grouped, online, and distributed variants). The kernel we benchmark is Algorithm 1 throughout, on one GPU and under tensor parallelism. Ranks exchange each tile's perturbed maximum and its index through P2P writes, and Stage 2 takes the argmax over all tiles of all ranks. This is exact pathwise by Lemma D.5 and uses no log-masses. Algorithms I.2 to I.4, which use group log-masses, are extensions and are not part of the reported experiments. The online variant (I.3) targets memory-constrained settings (Appendix D.1), and the log-masses also give log Z when an application needs it (Appendix L). Lemma D.1 connects the two forms: a group's perturbed maximum is distributed as Gumbel(L_k, 1), so exchanging maxima is the log-mass scheme with the Gumbel draws reused. You are right that contribution 2 and the first paragraph of Section 4.3 describe the multi-GPU path in log-mass terms ("a local sample and a local log-mass"), which Algorithm 1 does not use. We will rewrite both to say that the implemented path exchanges perturbed maxima, and we will label I.2 to I.4 as extensions.

Q3 (Qwen3-1.7B at B=64). We do not trust this cell. Three things in the data point to a measurement problem and not to the kernel. Both systems land on almost the same TPOT at B=64, 2.14 ms and 2.13 ms (Table 7). The run-to-run deviation of the cell is 3.6%, against at most 0.8% in every other cell of Table 8. And FlashSampling's TPOT rises by 0.42 ms between B=32 and B=64, after rising by 0.03 ms between B=1 and B=32, while the fused kernel's own latency changes by about 10 µs from B=16 to B=64 (Table 6). We saw the same signature in a later sweep of this model on B200 with FI2 as the sampler: TPOT at concurrency 64 was 3.190 ms in a concurrent sweep and 2.109 ms when that sweep was rerun in isolation. Qwen3-1.7B has the shortest decode step of the four models, so it is the most exposed to host-side interference. We reran Qwen3-1.7B at B=64 on one H200, both systems, five runs each: 2.958 ms for vLLM and 2.739 ms for FlashSampling, a reduction of 7.4% with a standard deviation of 1.2 points, and between 4.8% and 7.6% in each paired run. With top-k=20 and top-p=0.95 on the same model and GPU the reduction at B=64 is 13.4% (general response). We will mark the cell as unreliable in the paper.

Thanks for your response, my concerns have been addressed. I will maintain my score.

Thanks for your prompt response!

Reviewer_fh7SOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

FlashSampling targets the overhead that categorical sampling adds after the LM-head projection in large-vocabulary autoregressive decoding: materializing the [B, V] logits tensor in HBM, launching separate normalize/scan/sample kernels, and — under tensor parallelism — all-gathering logit shards across ranks (§1; §2.1, p.1–2). The method fuses sampling into the LM-head matmul epilogue via the Gumbel-Max trick (Theorem 2.1, p.3): exact categorical sampling needs only the argmax of Gumbel-perturbed logits, not a softmax. A two-stage kernel (Algorithm 1, p.4) computes logits tile-by-tile on chip, adds Gumbel noise, keeps one tile-local maximizer per row (Stage 1), then reduces over vocabulary tiles (Stage 2), never writing the full logits tensor. Under TP, instead of a post-GEMM all-gather, each rank emits per-tile P2P writes from inside the epilogue so communication overlaps the matmul (§3.2, p.4; §4.3, p.7). A simple IO cost model predicts speedup ≈ 1 + 2B/D (§3.3, p.4). Validation: kernel microbenchmarks on four datacenter GPUs (H100/H200/B200/B300), multi-GPU TP runtimes, and end-to-end vLLM TPOT, plus exactness proofs (Theorem D.4, Lemma D.5, p.16) and correctness checks (chi-square; GSM8K 89.4% vs 89.6%, p=0.776; §4.6, p.8).

Critical strengths

S1 — Exactness is genuinely free, not a trade-off. The output is proved exact (argmax decomposition, Lemma D.5; hierarchical factorization, Theorem D.4, p.16) and is empirically indistinguishable from the reference (chi-square at V=512 over 10,000 samples shows no significant difference; GSM8K 89.4% vs 89.6%, paired-bootstrap p=0.776; §4.6, p.8), yet the fused exact sampler is faster than every baseline in the decode regime — including FI2, FlashInfer's own exact Gumbel-Max sampler (up to ~1.43× in Table 4, p.17) — because sampling takes only 2–6% of kernel time versus up to 28.7% for Multinomial (Table 1, p.7). Nothing is traded for the speed, which is the premise the whole paper rests on. S2 — Removing the logits all-gather under tensor parallelism is the most valuable part. The baselines "wait for cuBLAS to finish, then issue an all-gather collective," while FlashSampling "emits per-tile P2P writes, which run concurrently with the matmul, effectively hiding the GPU-to-GPU communication" (§4.3, p.7). This replaces an O(B·V) collective whose cost grows with TP degree (§2.1, p.2) with communication that scales with the number of shards, not vocabulary entries (§D.2, p.14); at (B=16, TP=8) runtime is 87.1 µs vs FI2's 164.2 µs (Table 6, p.18), and at B=256 scaling approaches the ideal 1/TP (§4.3, p.7). In fairness, the single cell where a baseline wins is (B=256, TP=1), where FI2 is marginally faster (669.7 µs vs 676.8 µs, Table 6, p.18; §F, p.17); every other (B, TP) cell favors FlashSampling. This is a structural win, not a constant-factor one.

Critical weaknesses

W1 — No support for top-k or top-p sampling. §D.6 states: "While the FlashSampling theory allows integrating these sampling strategies, we leave the implementation to future work" (p.17). This is consequential because every reported speedup is measured with truncation switched off. The FI1 baseline — which the paper describes as the kernel vLLM uses for top-k/top-p decode — is run with "top_k=-1, top_p=1.0" "for fair comparison" (§4.1, p.5–6). The configuration actually deployed in most serving stacks is therefore never measured, and the paper gives no measurement or estimate of how the speedup changes once per-tile top-k candidates must be kept and reduced (Stage 1 currently writes a single candidate per row per tile, into a buffer of shape roughly [B, #vocab tiles]; §3.2, p.3–4). In my assessment this leaves the measured advantage unrepresentative of real serving configurations, which typically use truncation. In fairness, §D.6 argues the gap is not fundamental: top-k decomposes directly via the Gumbel-Top-k trick (per-tile local top-k, then a global reduction), and top-p can be applied after top-k on only k candidates — a sequential strategy the paper says is "used in practice by vLLM, FlashInfer, and other SOTA top-k top-p algorithms" (§D.6, p.16–17). The residual objection is precise: this path is unimplemented and unquantified, so the paper's measured advantage does not demonstrably transfer to the deployed configuration without evidence.

Questions for authors
  1. (Scale) End-to-end TPOT reduction falls sharply with model scale: peaks of 10.2%±0.8% (Qwen3-1.7B), 8.7%±0.3% (Qwen3-8B), 2.9%±0.2% (Qwen3-32B), and 2.7%±0.1% (Llama-3.3-70B) (§4.5, p.8; Table 8, p.19), consistent with the ≈1+2B/D model as D grows. What end-to-end TPOT reduction do you expect at production model sizes (e.g. ≥100B dense, or large-D MoE), where the LM head is an even smaller fraction of decode time?
  2. (Large batch) The advantage inverts at large batch: in Table 5 (D=8192, p.18), H200 at B=256 is 0.82× vs Multinomial (and 0.65× vs FI2), which §4.4 (p.7) attributes to the Triton matmul being less efficient than cuBLAS, taken as the price of portability. Would a CUTLASS/cuBLAS-based fused epilogue retain the gains — i.e. is the large-batch regression intrinsic to the fused design or an implementation choice?
  3. (Source of gain) §4.4 (p.7) attributes the bulk of the speedup to eliminating separate sampling kernels rather than to HBM traffic (the logits round-trip is ≤6% of traffic). How much of the remaining gain is kernel-launch and scheduling overhead that a better-fused baseline — e.g. a fused FlashInfer path — could also remove, given that FI2 as measured still operates on materialized logits?
3 comments
AuthorsOpenReview ↗

Official Comment by Authors (1/2)

Thank you for the careful reading, including the check of Table 6.

W1 (top-k and top-p). We agree this was the main gap, and we have now implemented and measured the truncated path. The general response gives the algorithm, the exactness argument, and the measurements. On your question about cost: Stage 1 no longer keeps k candidates per tile. It writes one maximum per 8 vocabulary entries, 5.02 MiB at B=64 against 37.09 MiB of FP32 logits, and Stage 2 recomputes at most 256 logits per row. With k=20 and p=0.95 the fused path takes 0.380 ms at B=64 against 0.593 ms for FI1 with the same filters (one H200), and truncation adds 11.7% to the temperature-only kernel.

Q1 (scale). The LM-head shape does not grow with parameter count the way the rest of the model does. Current open MoE models keep D between 2,880 and 7,168: GPT-OSS-120B has V=201,088 and D=2,880, Qwen3-235B-A22B has V=151,936 and D=4,096, and DeepSeek-V3 has V=129,280 and D=7,168. The kernel-level results in Tables 4 and 5 therefore apply to these models as measured. What shrinks is the LM head's share of a decode step. End to end, we expect reductions of the same order as the 32B and 70B results, 0.8 to 2.9% (Table 8); we have not yet measured a model above 100B parameters. At the kernel level the advantage over FI2 rises from 1.3 to 1.6x at TP=2 to 1.9 to 3.0x at TP=8 (Table 6).

Q2 (large batch: intrinsic or implementation). It is an implementation choice for the GEMM, and partly intrinsic for the Gumbel arithmetic. We are porting the kernel to CUTLASS with a custom epilogue. On B200, a CUTLASS GEMM with a fused argmax epilogue is at least as fast as cuBLAS followed by a separate argmax at B = 64, 128, and 256: 242, 258, and 333 µs against 249, 272, and 337 µs at V=151,936, D=4,096, and 356, 388, and 495 µs against 415, 452, and 505 µs at V=128,256, D=8,192. Fusing the reduction into the epilogue does not slow the GEMM. With Gumbel noise added, the CUTLASS kernel runs at 0.99x, 0.89x, and 0.78x of the Triton kernel's latency at D=8,192 for B = 64, 128, and 256, and at 1.12x, 1.04x, and 1.05x at D=4,096. What remains at large B is the cost of two logarithms per logit, which becomes visible once the kernel is compute-bound and which a Gumbel-Max sampler on materialized logits also pays. These are first numbers from the port, which is ongoing.

AuthorsOpenReview ↗

Official Comment by Authors (2/2)

This continues our response (1/2).

Q3 (source of the gain). There are three sources.

(a) Sampling work in a separate pass. Sampling takes 2 to 6% of FlashSampling's kernel time, 5 to 12% of FI2's, and 6 to 29% of Multinomial's (Table 1). FI2 is already close to the better-fused baseline you describe: it draws the sample with Gumbel-Max on the logits without a softmax. What no post-GEMM sampler can remove is that it runs after the GEMM, reads B×V logits back, and does the per-element work in its own pass. In the epilogue the same work runs inside a kernel that is bound by weight loads from HBM at these batch sizes, and it adds about 2% at B ≤ 16 (Table 1). The trend across GPUs fits this reading. The speedup over FI2 at B=1 is 1.20x on H100 (3.35 TB/s), 1.24x on H200 (4.8 TB/s), and 1.35x and 1.33x on B200 and B300 (8.0 TB/s) (Tables 3 and 4), which is what one would see if faster HBM shortens the GEMM more than it shortens the baseline's separate sampling pass.

On how much of this is launch overhead: the Nsight Compute profile behind Table 1 (RTX 3090, V=151,936, D=4,096) shows four kernels after FI2's GEMM. Their summed execution time is 80 µs at B=1, 107 µs at B=16, 200 µs at B=64, and 777 µs at B=256, next to a cuBLAS GEMM of 1,410 to 5,780 µs. These are kernel execution times and exclude the gaps between launches. They grow almost tenfold from B=1 to B=256, so most of FI2's post-GEMM cost at large B is work on the B×V logits, which a FlashInfer path fused into a single post-GEMM kernel would still do. At B=1 the four kernels take 80 µs in total, and that is the most such a path could recover from execution there.

(b) The logits round-trip. Table 9 isolates it by toggling only the logits store inside our kernel. The overhead is 0.5 to 3.6% for B ≤ 64 at D=8,192 and 0.9 to 4.8% at D=4,096, and it reaches 8.1% and 15.2% at B=256.

(c) Communication overlap under tensor parallelism. We ran an ablation that keeps the P2P mechanism, payload, and reduction fixed and moves the peer writes into a separate kernel after the GEMM. On B200 with V=128,256 and D=8,192, the variant without overlap was 0.029 to 0.036 ms slower at TP=4 in every run and 0.035 to 0.036 ms slower at TP=8 in both completed runs.

Reviewer_fh7SOpenReview ↗

Response to the authors' rebuttal

Thank you for implementing the truncated path. This was my main concern, and the response addresses it directly: with Qwen3's default top-k=20 and top-p=0.95, the fused kernel is 24.7–36.0% faster than FlashInfer with the same filters and 41.5–52.7% faster than vLLM's default sampler on an H200, the output matches a full-logits reference row by row, and end-to-end TPOT on Qwen3-1.7B falls by 10.1–18.7%. These are measurements against the samplers that production stacks use, in the configuration they run. I am raising my rating to weak acceptance.

Points I would like the camera-ready to state clearly:

  1. Coverage of the truncated path. It covers k ≤ 28 on a single GPU. Top-p alone and min-p fall back to the standard path, which includes the default generation config of Llama-3.x, one of the paper's own models (temperature 0.6, top_p 0.9, no top_k). Truncation under tensor parallelism is not implemented, so the TP advantage and truncation do not yet combine, and end-to-end truncated results exist only for Qwen3-1.7B. A short table of which sampling configurations take the fused path would help practitioners. With truncation now supported, the GSM8K check in §4.6 can also compare both arms under the same top-k/top-p settings.
  2. Scale (Q1). The expected end-to-end gain at production scale is 0.8–2.9% and has not been measured above 70B. MoE models with a small hidden size, where the LM head is a larger share of a decode step (e.g., Qwen3-30B-A3B with D = 2,048 and Qwen3's default k and p), would be the most informative next measurement and fit on one GPU.
  3. Large batch (Q2). The CUTLASS results show that fusing the argmax does not slow the GEMM, but with Gumbel noise the CUTLASS kernel is still 4–12% slower than Triton at D = 4,096 and was not compared with the baselines at B = 256. The large-batch regression should remain listed as open.
  4. Attribution under TP (Q3). Removing the overlap costs 29–36 µs, while the gap to FI2 at TP = 8 is 77–301 µs (Table 6). Most of the TP advantage therefore comes from sending per-tile summaries instead of full logits, which a non-fused TP-aware sampler (local sampling on each shard followed by a small all-gather, as in Algorithm I.4) could also obtain. Comparing against such a baseline would show what the fusion itself adds under TP.
Reviewer_2uT8OpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper presents FlashSampling, an exact categorical sampler fused into the LM-head GEMM epilogue. Logits are computed tile-by-tile on chip, perturbed with Gumbel noise, and reduced to a per-row argmax candidate without materializing the full logits tensor in HBM. Tensor-parallel decoding replaces the logits all-gather with overlapping P2P writes of tile candidates. Exactness follows from Gumbel-Max plus max/argmax decomposition over vocabulary tiles and hierarchical group factorization. Kernel benchmarks on H100/H200/B200/B300 and a vLLM integration show up to 2.2× kernel speedups and up to ~10% TPOT reduction on small models (smaller gains on 32B/70B).

Critical strengths

The problem is real: logits materialization and sampling kernels are pure overhead in memory-bound decode, especially under tensor parallelism. The design is simple and honestly exact (no approximation claim), with clear separation of pathwise vs. distributional exactness. Evaluation spans four datacenter GPUs, microbenchmarks, multi-GPU scaling, and end-to-end vLLM, with a useful I/O cost model and Nsight analysis.

Critical weaknesses

Algorithmic novelty is thin for ICLR. Gumbel-Max is classical; tile-wise max/argmax reduction is nearly tautological (Lemma D.5); hierarchical group factorization is a known identity. The systems pattern (fuse epilogue to avoid materializing intermediates) follows FlashAttention / Cut Your Losses / EVT-style GEMM epilogues. This reads as an MLSys paper, not a new ML method. The production sampling path is not implemented. Appendix D.6 admits top-p needs a global sort/softmax and is left to future work; top-k is only sketched. Real LLM decoding almost always uses top-k / top-p / min-p. Baselines even disable truncation (FI1 with top_k=-1), so the comparison is not against how these stacks are actually used. End-to-end impact is modest and concentrated on small models. TPOT drops are ~10% / 8.7% on 1.7B/8B but only 2.7–2.9% on 32B/70B; at B=64 on 1.7B the gain is 0.4%±3.6% (noise). Kernel speedups invert at large batch (e.g. 0.81–0.82× vs FI2 at B=256 on H100/H200), where GEMM dominates. Triton vs cuBLAS gap and missing serving baselines. The paper admits Triton’s LM-head matmul loses to cuBLAS at large B, partially canceling fusion gains. No comparison to SIMPLE (same bottleneck, CPU-offload) or a CUTLASS/EVT cuBLAS-epilogue implementation; multi-GPU end-to-end is only TP=2.

Questions for authors

Can you fuse and evaluate the actual production path (top-k → top-p) and compare against vLLM’s default top-k/top-p sampler, not a truncated-off FI1? Under continuous batching with realistic length mixes on 70B-class models, is sampling still on the critical path — and if not, how should we weigh a 2–3% TPOT change? Does fast-math Gumbel (Appendix J) introduce measurable distributional bias over long generations? Can you compare against a cuBLAS/CUTLASS-epilogue version of the same idea and against SIMPLE / other serving-level sampling offloads?

2 comments
AuthorsOpenReview ↗

Official Comment by Authors (1/2)

Thank you for the review. We answer the weaknesses in order and then the questions.

Novelty and fit. We do not present Gumbel-Max, the max decomposition, or group factorization as new. Section 2.2 and Appendix D introduce them as known results, and Lemma D.5 is stated as a simple structural lemma. What the paper contributes is the observation that these identities turn exact sampling into a streaming reduction that fits inside a GEMM epilogue, so the [B, V] logits tensor does not have to exist, together with a kernel that does this and an evaluation of when it pays off. The same reduction lets tensor-parallel ranks send per-tile candidates from inside the epilogue instead of all-gathering logits after the GEMM. Earlier fused-epilogue work covers other operations: attention (FlashAttention), the training loss (Cut Your Losses, Liger Kernel), and approximate top-k (Samaga et al.). None of them performs exact inference-time sampling, and none overlaps cross-GPU communication with the GEMM. On fit, ICLR has published work of this kind, including FlashAttention-2 (ICLR 2024), Cut Your Losses (ICLR 2025, oral), and FlashRNN (ICLR 2025), and the ICLR 2027 call for papers lists "infrastructure, software libraries, hardware, etc." among its topics.

Production sampling path. Please see the general response. In short: the top-k-then-top-p path is implemented, and on one H200 it takes 24.7% to 36.0% less kernel time than FI1 with the same filters at B=1 to 256. FI1 is also re-measured with truncation enabled.

End-to-end impact. Your reading of Table 8 is correct and the paper does not claim more: the TPOT reduction is 7 to 10% for the 1.7B and 8B models (apart from one cell discussed in the next paragraph) and 0.8 to 2.9% for the 32B and 70B models, because the LM head and sampler take a smaller share of each decode step as the model grows. Two facts bear on how to weigh the smaller numbers. The sampler is exact, so the reduction comes with no change in output distribution and no change outside the LM head. And the kernel-level advantage grows with tensor-parallel degree: against FI2 it is 1.3 to 1.6x at TP=2 and 1.9 to 3.0x at TP=8 (Table 6), while the paper's end-to-end runs stop at TP=2.

The 0.4% ± 3.6% cell (Qwen3-1.7B, B=64) is a measurement we do not trust. Its run-to-run deviation is 3.6% against at most 0.8% in every other cell of Table 8, and FlashSampling's TPOT rises by 0.42 ms between B=32 and B=64 (Table 7), far more than the fused kernel's own latency changes between those batch sizes (about 10 µs from B=16 to B=64 in Table 6). We reran the setting on one H200, five runs per system: 2.958 ms for vLLM and 2.739 ms for FlashSampling, a reduction of 7.4% with a standard deviation of 1.2 points across the paired runs. The collapse at B=64 does not come from the kernel, and we will mark the cell in the paper.

Large batch sizes. The inversions are specific to Hopper at B ≥ 128. On Blackwell with D=4,096, FlashSampling is at least as fast as every baseline at every batch size (Table 4). With D=8,192 the only Blackwell cell below 1 is B200 at B=256 against FI2, at 0.97x (Table 5). On H100 and H200 the paper reports the losses at B ≥ 128 in Tables 4 and 5 and attributes them to the Triton matmul in Section 4.4.

AuthorsOpenReview ↗

Official Comment by Authors (2/2)

This continues our response (1/2).

Triton against cuBLAS, and a CUTLASS epilogue. Figure 4 separates the two parts of the kernel. The fused sampling stays cheaper than the baselines' sampling at every batch size (left panel), and the loss at B ≥ 128 comes from the Triton matmul (right panel). To test whether the fused design itself causes the loss, we are building the same kernel on CUTLASS with a custom epilogue. On B200, a CUTLASS GEMM with a fused argmax epilogue is at least as fast as cuBLAS followed by a separate argmax at B = 64, 128, and 256 for both LM-head shapes: 242, 258, and 333 µs against 249, 272, and 337 µs at V=151,936, D=4,096, and 356, 388, and 495 µs against 415, 452, and 505 µs at V=128,256, D=8,192. So fusing the reduction into the epilogue does not slow the GEMM. The CUTLASS Gumbel-Max kernel passes our 10-million-sample chi-squared test. Its latency relative to the Triton kernel at B = 64, 128, and 256 is 0.99x, 0.89x, and 0.78x at D=8,192, and 1.12x, 1.04x, and 1.05x at D=4,096. The cost that remains at large B is the Gumbel arithmetic, two logarithms per logit, which any Gumbel-Max sampler pays, fused or not. These are first numbers from the port, which is ongoing.

SIMPLE. SIMPLE targets the same bottleneck by moving sampling to the CPU and, like the other serving-level methods in Section 5, works on materialized logits. We could not find a public implementation: as of 10 Nov 2026 the arXiv listing links no code and a search for a repository returned none. We therefore cannot run it on our setup, and we will make the comparison in Section 5 explicit about what each approach removes: SIMPLE moves the sampling work off the GPU, while FlashSampling removes the logits tensor and keeps sampling on the GPU inside the GEMM.

Q1 (fuse and evaluate top-k then top-p). See the general response.

Q2 (is sampling on the critical path for 70B-class models). Section 4.5 measures under vLLM continuous batching with Poisson arrivals and 256 output tokens per request. For Llama-3.3-70B at TP=2 the TPOT reduction is 0.8 to 1.2% for B ≤ 8 and 2.5 to 2.7% for B ≥ 16 (Table 8). Sampling is on the critical path at this scale, and it is a small part of it. We read the 70B result as a small improvement that costs nothing in output quality.

Q3 (fast-math Gumbel). No experiment in the paper uses fast-math. Every kernel computes g = -log(-log u) in FP32 (Appendix C) with the standard, accurate logarithm. We tested your question directly. In a chi-squared test with 10 million samples at V=128,000 on B200, the Triton kernel passes (reduced chi-squared 0.998, p = 0.65). In the CUTLASS port, the kernel with accurate logarithms passes the same kind of test (reduced chi-squared 0.995, p = 0.90), and a variant that uses the CUDA fast-math logarithm and division intrinsics is rejected (p = 0.0004). Fast-math therefore does introduce a measurable bias. We will remove the fast-math mode from Appendix J and add the 10-million-sample test to Section 4.6, which currently reports only V=512 with 10,000 samples.

Q4 (cuBLAS/CUTLASS epilogue and SIMPLE). See the first two paragraphs of this part.

Comments on the paper

2 comments
AuthorsOpenReview ↗

General Response (1/2)

We thank all three reviewers for their careful reading and for comments that have improved the paper. All three reviews raise the same main concern. The paper evaluates temperature-only sampling, while deployed configurations usually truncate with top-k and top-p, and Appendix D.6 leaves that path to future work. We have now implemented this path. This response describes it and reports the measurements.

Algorithm. Stage 1 is the same fused GEMM, but its epilogue writes only the largest logit of every 8 consecutive vocabulary entries. Nothing is sorted and no index is stored. Stage 2 finds a threshold that between k+2 and k+4 of these group maxima reach, recomputes the logits of those groups (at most 256 dot products per row), sorts that short list, applies top-k and then top-p, and draws one sample with Gumbel-Max. The result is exact for the top-k-then-top-p order that vLLM and FlashInfer apply by default (footnotes 5 to 7 in D.6): if k groups have a maximum of at least tau, then k logits are at least tau, so every one of the k largest logits is at least tau and lies in one of those groups. The [B, V] logits tensor is never written. k, p, and temperature are read per row inside the kernels, so requests in one batch may use different values. We will add this argument and the results below to the paper.

Scope. The implementation covers top-k up to 28 on a single GPU, which includes the Qwen3 default of k=20. Requests with top-p alone or min-p take the standard path.

Kernel measurements. We timed the fused path against FlashInfer and vLLM at V=151,936, D=4,096, T=0.6, top-k=20, top-p=0.95 (the Qwen3 defaults). The run used one NVIDIA H200. Each entry is the median over five interleaved rounds, in ms.

MethodB=1B=16B=64B=256
FlashSampling, fused top-k then top-p0.3310.3370.3800.723
FI1, same k and p0.4400.4760.5931.114
vLLM default filter and sampler0.5660.6380.7431.528
PyTorch sort, then Multinomial0.6051.0721.9005.418

With truncation on, the fused path takes 24.7%, 29.2%, 36.0%, and 35.1% less time than FI1 at B=1, 16, 64, and 256, and 41.5%, 47.2%, 48.9%, and 52.7% less than vLLM's default path. At B=1, 16, and 64, top-k and top-p add 11.3%, 8.0%, and 11.7% to the latency of the paper's temperature-only kernel on the same GPU.

The output matches a reference computed from the full logits: the same top-k set and the same top-p support in every row at every batch size. The buffers Stage 1 writes are 13.5% of the FP32 logits tensor: 0.08, 1.26, 5.02, and 20.09 MiB at B=1, 16, 64, and 256, against 0.58, 9.27, 37.09, and 148.37 MiB.

Baseline with truncation on. The paper runs FI1 with top_k=-1, top_p=1.0. On the same H200, turning on top-k=20 and top-p=0.95 adds 12.5%, 13.4%, 18.6%, and 21.4% to FI1's latency at B=1, 16, 64, and 256.

AuthorsOpenReview ↗

General Response (2/2)

This continues the general response (1/2).

End to end. We wired the fused top-k path into our vLLM integration and served Qwen3-1.7B at its default sampling parameters (T=0.6, top-k=20, top-p=0.95) on one H200, vLLM's default sampler against FlashSampling, five runs per setting.

Concurrency1248163264
vLLM TPOT (ms)2.2892.4622.5982.6092.5582.7423.167
FlashSampling TPOT (ms)2.0592.0732.1132.1402.2342.4132.737
Reduction10.1%15.9%18.7%17.8%12.7%11.8%13.4%

The reduction is the median over the five paired runs. Its standard deviation across runs is at most 0.4 points up to concurrency 32 and 1.6 points at 64. Both arms produced the same number of output tokens.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.