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

• URL: http://arxiv.org/abs/2608.12573v1
• Date: Wed, 12 Aug 2026 20:31:33 GMT
• Title: Prof-K: Probabilistic One-Pass Filtering for Efficient Top-k Selection
• Abstract summary: Prof-K is a fast, scalable, and distribution-agnostic top-k algorithm with probabilistic correctness guarantees.<n>We derive high-probability guarantees for correctness and buffer size, together with an approximately optimal sample size.<n>Prof-K achieves 1.5x-10x speedups over the highly optimized PyTorch topk and recent RadiK implementations.
• Score: 11.90858984464117
• License: http://creativecommons.org/licenses/by/4.0/
• 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 top-k algorithm with probabilistic correctness guarantees. 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 with probability at least 1 - $ε$, where $ε$ > 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-10x 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. By relaxing the recall target (e.g., recovering 95% of the true top-k values), Prof-K additionally provides a principled accuracy-speed trade-off. We further demonstrate its impact on training BatchTopK Sparse Autoencoders (SAEs), where top-k selection constitutes a significant portion of the training cost.

Related papers

• No-Regret Bayesian Optimization with Finite-Library Input-Warped Kernels [1.2432856108679675]
  We propose Finite-Library Input-Warped Bayesian Optimization (FLIWBO), which selects warps from a finite library of smooth input maps by any history-dependent rule.<n>It adapts the input geometry to accelerate learning while retaining high-probability convergence guarantees.<n> Controlled diagnostics show that finite-library warping repairs planted geometry mismatches and identify FLIWBO failure cases.
  arXiv  Detail & Related papers  (2026-09-02T16:04:07Z)
• BAPE: Learning an Explicit Bayes Classifier for Long-tailed Visual Recognition [78.70453964041718]
  Current deep learning algorithms usually solve for the optimal classifier by emphimplicitly estimating the posterior probabilities.<n>This simple methodology has been proven effective for meticulously balanced academic benchmark datasets.<n>However, it is not applicable to the long-tailed data distributions in the real world.<n>This paper presents a novel approach (BAPE) that provides a more precise theoretical estimation of the data distributions.
  arXiv  Detail & Related papers  (2025-06-29T15:12:50Z)
• One Sample is Enough to Make Conformal Prediction Robust [53.78604391939934]
  We show that conformal prediction attains some robustness even with a forward pass on a single randomly perturbed input.<n>Our approach returns robust sets with smaller average set size compared to SOTA methods which use many (e.g. around 100) passes per input.
  arXiv  Detail & Related papers  (2025-06-19T19:14:25Z)
• Robust Conformal Prediction with a Single Binary Certificate [58.450154976190795]
  Conformal prediction (CP) converts any model's output to prediction sets with a guarantee to cover the true label with (adjustable) high probability.<n>We propose a robust conformal prediction that produces smaller sets even with significantly lower MC samples.
  arXiv  Detail & Related papers  (2025-03-07T08:41:53Z)
• Learning the Optimal Stopping for Early Classification within Finite Horizons via Sequential Probability Ratio Test [11.199585259018459]
  Time-sensitive machine learning benefits from Sequential Probability Ratio Test (SPRT), which provides an optimal stopping time for early classification of time series.<n>In finite horizon scenarios, where input lengths are finite, determining the optimal stopping rule becomes computationally intensive due to the need for backward induction.<n>We introduce FIRMBOUND, an SPRT-based framework that efficiently estimates the solution to backward induction from training data.
  arXiv  Detail & Related papers  (2025-01-29T23:54:46Z)
• Equation Discovery with Bayesian Spike-and-Slab Priors and Efficient Kernels [57.46832672991433]
  We propose a novel equation discovery method based on Kernel learning and BAyesian Spike-and-Slab priors (KBASS) We use kernel regression to estimate the target function, which is flexible, expressive, and more robust to data sparsity and noises. We develop an expectation-propagation expectation-maximization algorithm for efficient posterior inference and function estimation.
  arXiv  Detail & Related papers  (2023-10-09T03:55:09Z)
• Efficient Few-Shot Object Detection via Knowledge Inheritance [62.36414544915032]
  Few-shot object detection (FSOD) aims at learning a generic detector that can adapt to unseen tasks with scarce training samples. We present an efficient pretrain-transfer framework (PTF) baseline with no computational increment. We also propose an adaptive length re-scaling (ALR) strategy to alleviate the vector length inconsistency between the predicted novel weights and the pretrained base weights.
  arXiv  Detail & Related papers  (2022-03-23T06:24:31Z)
• Scalable Uncertainty Quantification for Deep Operator Networks using Randomized Priors [14.169588600819546]
  We present a simple and effective approach for posterior uncertainty quantification in deep operator networks (DeepONets) We adopt a frequentist approach based on randomized prior ensembles, and put forth an efficient vectorized implementation for fast parallel inference on accelerated hardware.
  arXiv  Detail & Related papers  (2022-03-06T20:48:16Z)
• Transformers Can Do Bayesian Inference [56.99390658880008]
  We present Prior-Data Fitted Networks (PFNs) PFNs leverage in-context learning in large-scale machine learning techniques to approximate a large set of posteriors. We demonstrate that PFNs can near-perfectly mimic Gaussian processes and also enable efficient Bayesian inference for intractable problems.
  arXiv  Detail & Related papers  (2021-12-20T13:07:39Z)
• Efficient Model-Based Collaborative Filtering with Fast Adaptive PCA [4.878057307346225]
  A model-based collaborative filtering (CF) approach utilizing fast adaptive randomized singular value decomposition (SVD) is proposed. A novel termination mechanism for the adaptive PCA is proposed to automatically determine a number of latent factors for achieving the near optimal prediction accuracy. The proposed model-based CF approach is able to efficiently process Matlab MovieLen data with 20M ratings and exhibits more than 10X speedup over the regularized factorization based approach.
  arXiv  Detail & Related papers  (2020-09-04T15:32:14Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.