Skip to content

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

Aug 2026 · 2 citations · 33 references
Computer Science

TL;DR

Prof-K is introduced, a fast, scalable, and distribution-agnostic algorithm for exact top-k selection that derives 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.

Abstract

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-\varepsilon$, where $\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.

View source

Similar papers

Preprint Sep 2026

Top-K Is Not a Budget for Hybrid Retrieval

DiBud is presented, which takes an access budget directly as input and incrementally certifies and returns an exact prefix of the RRF ranking over the full lists, and investigates long-tailed costs for completing exact Top-20.

Chunran Zhang · 0 citations

Cortado: Progressive Retrieval of Lossily Compressed Data with Guaranteed Error Bounds

Cortado is compared with state-of-the-art approaches and it is found that it is the only progressive compressor that guarantees the evaluated error bounds on all tested inputs while achieving the highest throughputs, comparable reconstruction quality, and on-par compression ratios.

B. Burtchell, Martin Burtscher · 0 citations
Preprint Aug 2026

Diva++: Dynamic Range Filtering over Hard Workloads

Range filters are compact probabilistic data structures that answer approximate range emptiness queries. They are used in many domains, e.g., in key-value stores, to quickly rule out the existence of keys in a given query range and avoid searching for them in storage. However, all existing range filters exhibit at leas...

Navid Eslami, I. Bercea, Niv Dayan · 0 citations
#machine learning Preprint Sep 2026

Beyond Worst-Case Coreset Bounds for $k$-Clustering via Determinantal Sampling

This work shows that significantly smaller coresets are possible under mild and natural assumptions on the underlying data distribution, and introduces a new correlated sampling framework, called \textit{determinantal sampling}, based on a novel application of determinantal point processes.

Diptarka Chakraborty, Satyaki Mukherjee, Gaurav Vallabhdas Revankar et al. · 0 citations

Oracle-Efficient Online Classification with Stochastic Inputs and Adversarial Outputs

It is shown that a simple Follow-the-Perturbed-Leader algorithm with Gaussian perturbation for each observed context achieves the optimal $\widetilde O(\sqrt{T\log N})$ expected regret for a class of $N$ experts, while requiring one optimization-oracle call per round and no explicit enumeration of the class.

G. Buzaglo, Elad Hazan · 4 citations · ⚡1
Review Sep 2026

Sample-Guided Exact Top-K Selection for Long-Context Sparse Attention

HPC-Ops Top-K is presented, a sample-guided exact selector for ragged sparse-attention score rows that outperforms the fastest verified external exact baseline and outperforms the fastest verified external exact baseline on indexer scores from Hy4-Preview.

Si-Ran Liu, Ya-Long Xue, Theo Tang et al. · 0 citations

Related blog posts

MIT News · Artificial Intelligence Nov 17, 2026

Learning the language of machine learning

By studying the computational foundations of language learning, Associate Professor Jacob Andreas builds intelligent systems that can communicate effectively with humans.

Microsoft Research Blog Nov 16, 2026

TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient

AI coding agents are increasingly help developers fix bugs and build features largely on their own, but every interaction with their models consumes tokens. In each session, an agent sends instructions, tool descriptions, and session history to its model. Most efforts to reduce this cost focus on individual tasks. Yet developers return to the same […] The post TokenEconomizer: Learning from Experience to Make AI Coding Agents More Efficient appeared first on Microsoft Research.

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.