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

Apr 13, 2026

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

The quality of text generated by large language models depends critically on the decoding sampling strategy. While mainstream methods such as Top-kk, Top-pp, and Min-pp achieve a balance between diversity and accuracy through probability-space truncation, they share an inherent limitation: extreme sensitivity to the temperature parameter. Recent logit-space approaches like Top-nσnσ achieve temperature invariance but rely on global statistics that are susceptible to long-tail noise, failing to capture fine-grained confidence structures among top candidates. We propose \textbf{Min-kk Sampling}, a novel dynamic truncation strategy that analyzes the local shape of the sorted logit distribution to identify "semantic cliffs": sharp transitions from high-confidence core tokens to uncertain long-tail tokens. By computing a position-weighted relative decay rate, Min-kk dynamically determines truncation boundaries at each generation step. We formally prove that Min-kk achieves strict temperature invariance and empirically demonstrate its low sensitivity to hyperparameter choices. Experiments on multiple reasoning benchmarks, creative writing tasks, and human evaluation show that Min-kk consistently improves text quality, maintaining robust performance even under extreme temperature settings where probability-based methods collapse. We make our code, models, and analysis tools publicly available.
Jul 13, 2026

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

Indexer-TopK, which computes scores and selects the top-kk candidates, is a key primitive in long-context sparse attention for large language models, vector retrieval for recommendation systems, and vector databases. However, existing GPU-based Indexer-TopK kernels like DeepSeek Sparse Attention (DSA) typically separate scoring from selection and materialize the full score matrix in high-bandwidth memory. This strategy is inefficient for large score matrices, such as those encountered in long-context sparse attention, due to excessive global-memory traffic, costly synchronization, and prohibitive memory overhead. In this study, motivated by the curse of dimensionality, we observe that sparse attention scores exhibit a score concentration phenomenon, with scores falling within a narrow range. Based on this observation, we propose LiteTopK, a sample-filter-select framework that estimates query-data score ranges from a small subset of the data. It uses these estimates to filter scores as they are computed, materializes only the candidates that pass the filter, and selects from the surviving candidates. In particular, we develop two implementations of LiteTopK. The first uses a conservative threshold estimate, while the second pairs a predicted threshold with a fallback strategy. Building on LiteTopK, we further propose LiteDSA, which reuses overlapping key/value entries across neighboring queries to accelerate attention computation. We integrate LiteTopK into vLLM, SGLang, and Megatron-LM. Our evaluation on eight B200 GPUs demonstrates prefill speedups of up to 1.49×\times across GLM-5.2, DeepSeek-V4-Flash, and Hy-4-Preview at a context length of 1M tokens, without compromising model capabilities.
Aug 12, 2026

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

Top-k selection is a fundamental computational primitive with applications spanning databases, information retrieval, signal processing, and modern machine learning workloads, including sparse activations and attention pruning. As data sizes grow, existing approaches become inefficient: exact methods incur high memory and compute overhead, while approximate methods often rely on brittle heuristics that degrade under adversarial or heavy-tailed inputs. In this paper, we introduce Prof-K, a fast, scalable, and distribution-agnostic algorithm for exact top-k selection. Prof-K performs a single-pass filtering procedure: a small random sample estimates an adaptive threshold, the N input elements are streamed once into a compact buffer, and an exact top-k routine on this buffer recovers the true top-k elements on the first attempt with probability at least 1−ε1-\varepsilon, where ε>0\varepsilon>0 is user specified. We derive high-probability guarantees for correctness and buffer size, together with an approximately optimal sample size that minimizes overhead as a function of N and k. Empirically, Prof-K achieves 1.5x-15x speedups over the highly optimized PyTorch topk and recent RadiK implementations, with the largest gains in the large-scale, small-to-moderate-k regime where prior methods struggle most. Unlike previous approaches, these guarantees hold independently of the input distribution, ensuring robustness to adversarial settings. A run-time check detects the rare failures and triggers a retry, so the returned set is always exact and ε\varepsilon bounds only the probability of requiring an additional pass. We further demonstrate its impact on training BatchTopK Sparse Autoencoders (SAEs), where top-k selection constitutes a significant portion of the training cost.