cs.AIFeb 2, 2026

Qrita: High-performance Top-k and Top-p Algorithm for GPUs using Pivot-based Truncation and Selection

Authors: Jongseok Park, Sunga Kim, Alvin Cheung, Ion Stoica

Organizations: University of California, Berkeley

Abstract

Despite their importance in model sampling, efficient implementation of the Top-k and Top-p algorithms poses a significant challenge as model vocabulary grows with each new model release. Existing approaches often rely on sorting, which incurs significant computation and memory overhead on GPUs, or on stochastic approaches that alter the algorithm's output. In this work, we propose Qrita, an efficient Top-k and Top-p algorithm based on pivot-based truncation and selection. Qrita leverages pivot-based search for both Top-k and Top-p with two key techniques: 1. Gaussian-based sigma-truncation, which limits the complexity of the algorithm to O(n), and 2. Quaternary pivot search with duplication handling, which halves the number of pivot search iterations and guarantees deterministic output. We implement Qrita using Triton and evaluate its performance against the Top-k and Top-p kernels of high-performance LLM execution engines such as SGLang and FlashInfer, improving end-to-end serving throughput up to 1.4 times with half the memory usage, while providing the same output as stable sort-based Top-k and Top-p algorithms. Qrita is now the default Triton Top-k and Top-p sampler of vLLM, and its implementation is available at https://github.com/vllm-project/vllm/blob/main/vllm/v1/sample/ops/topk_topp_triton.py.

Figures & tables

Explore similar work

CardsList
  1. Min-kk Sampling: Decoupling Truncation from Temperature Scaling via Relative Logit Dynamics

    Apr 13, 2026Yuanhao Ding, Meimingwei Li, Esteban Garces Arias +3Language Model DecodingAdaptive Inference

  2. LiteTopK: Exploiting the Curse of Dimensionality for a Fused Indexer-TopK Kernel in Long-Context Sparse Attention

    Jul 13, 2026Ziqi Yin, Jianyang Gao, Peiqi Yin +2GPU Kernel OptimizationLLM Inference Acceleration

  3. Prof-K: Probabilistic One-Pass Filtering for Efficient Top-k Selection

    Aug 12, 2026Tadeusz Dziarmaga, Witold Sikora, Łukasz Struski +2Streaming Algorithms