acceptodds
Under review as a conference paper at ICLR 2027

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

Abstract

Top- 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- algorithm with probabilistic correctness guarantees. Prof-K performs a single-pass filtering procedure: a small random sample estimates an adaptive threshold, the input elements are streamed once into a compact buffer, and an exact top- routine on this buffer recovers the true top- elements with probability at least , where 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 and . Empirically, Prof-K achieves - speedups over the highly optimized PyTorch top- and recent RadiK implementations, with the largest gains in the large-scale, small-to-moderate- 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, so the returned set can always be exact and bounds only the frequency of a second pass. We further demonstrate its impact on training BatchTopK Sparse Autoencoders (SAEs), where top- selection constitutes a significant portion of the training cost. The source code is provided in the supplementary materials and will be made publicly available.

Primary area:
infrastructure, software libraries, hardware, systems, etc.
Keywords:
Top-$k$ selection, distribution-agnostic guarantees, sparse autoencoders, gradient sparsification

Reviews

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

This paper proposes a top‑k algorithm termed as Prof-k. The algorithm draws a small uniform sample to compute a conservative threshold, streams the full input once to collect candidate elements into a compact buffer, and then runs exact top‑k over this buffer. The authors derive hypergeometric distribution based theory for optimal sample size, threshold rank and buffer capacity, together with fast closed‑form approximations. Empirically, the authorss implement Prof-K in Triton and evaluate it against torch.topk and RadiK, the state-of-the-art radix selection, on a DGX H100 and an RTX 3060.

Critical strengths
  • The paper addresses a fundamental streaming algorithmic problem, top-k listing.
  • The proposed algorithm is evaluated both theoretically and empirically.
Critical weaknesses
  • From my perspective, the most critical weakness is the novelty. The idea of sampling‑based threshold estimation followed by filtering and fallback retry is classic in selection and quantile literature. The hypergeometric analysis and conservative threshold construction are standard statistical machinery. Prof‑K mainly assembles known components. There are no fundamentally new algorithmic insights for top‑k selection.
  • My second concern is reagrding the fitness of the topic (top-k) to ICLR, as I fail to see a clear link to machine learning research. I would recommend the authors to try a TCS venue.
Questions for authors

Could you explicitly distinguish which parts of Prof‑K constitute genuinely new algorithmic ideas versus known prior sampling‑filter‑retry paradigm in algorithmic literature? Please provide precise citations to closely‑related prior sampling‑based top-k selection schemes and point out concrete technical differences.

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

Prof-K is a GPU algorithm for exact top-k in sparse ML. The method draws a small uniform sample, sets a conservative threshold, streams the input once into a compact buffer, and runs exact top-k on the candidates. On H100 and RTX 3060 it is fastest at large N, with MB-scale extra memory and coverage beyond RadiK’s limit. Inside GPT-2 XL training it speeds up BatchTopK SAE steps by 1.20–1.30× and exact gradient top-k by 1.38×, returning the same set as torch.topk.

Critical strengths
  1. Prof-K provides distribution-independent bounds for both recall failure and buffer overflow, derives optimal threshold and buffer parameters, and detects rare failures at runtime.

  2. Across both H100 and consumer GPUs, Prof-K substantially outperforms torch.topk and RadiK in its target regime while reducing auxiliary memory from gigabytes to megabytes.

Critical weaknesses
  1. The technical novelty is narrow. Sampling a threshold, filtering, and refining with exact top-k is already used in gradient sparsification and related approximate selectors. What is new is mainly runtime failure detection together with hypergeometric parameter selection.

  2. The distribution-free guarantee excludes ties. With many equal values especially in FP16/BF16 or quantized/sparse activations the candidate buffer may overflow deterministically; for an all-equal input, resampling can never resolve the failure.

Questions for authors
  1. The theory assumes distinct values, but the kernel retains all xi≥τx_i \ge \tau. How does exact mode handle tied values, particularly all-equal or heavily quantized FP16/BF16 inputs where every resample may overflow the buffer?

  2. Why are other cited exact GPU selectors, such as Dr. Top-k and RTop-K, omitted from the evaluation?

  3. Exact mode requires a host-side inspection of R after every filtering pass. How does this interact with CUDA graph captured or torch.compile training steps, and can the check and redraw remain on-device?

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

The manuscript introduces Prof-K, a GPU algorithm that accelerates exact top-kk selection by using uniform random sampling to filter out most elements before performing the expensive selection operation. Instead of running an exact top-kk algorithm over all NN elements, Prof-K estimates a threshold from a small uniform random sample, scans the input once to retain elements above that threshold, and then runs exact top-kk on the much smaller candidate set.

Critical strengths

1.) Clear presentation: The manuscript is very well written and easy to follow, with a clear exposition of the algorithm and its motivation.

2.) Strong theoretical foundation: The theoretical analysis provides useful insights into the algorithm's correctness guarantees and parameter selection, supporting the proposed design.

3.) Large-scale evaluation: The experiments cover very large input tensors, scaling to billions of elements, and evaluate performance across a broad grid of input sizes and kk values on both a datacenter GPU and a consumer GPU. This provides meaningful evidence of the algorithm's behavior in the large-NN regime it targets.

Critical weaknesses

1.) Missing competitive baselines: The baseline selection appears incomplete. The manuscript compares Prof-K against PyTorch's topk and RadiK, but omits other optimized GPU top-kk implementations, such as NVIDIA CUB's DeviceTopK and FlashInfer's top-kk. The authors should evaluate against these implementations where comparable, or justify their exclusion, to better establish Prof-K's advantage over existing methods.

2.) Limited end-to-end evaluation: Despite substantial microbenchmark speedups, the end-to-end gains are more modest and demonstrated on only two training workloads. The authors should evaluate Prof-K in an additional application, ideally sparse attention or LLM inference, and report end-to-end latency or throughput to establish whether kernel-level gains translate into meaningful application-level improvements.

3.) Unclear generality across operating regimes: Prof-K appears most effective for large NN and relatively small kk, but its broader applicability remains unclear given its overhead on smaller inputs, reliance on GPU-specific cost calibration, and lack of multi-GPU evaluation. The authors should characterize the crossover points against existing methods and quantify sensitivity to workload configurations, clarifying when Prof-K is preferable.

Questions for authors

1.) What is the main practical motivation for using uniform random sampling over alternatives such as importance sampling? Intuitively, sampling proportionally to an informative score could yield a more effective sample and reduce the frequency of retries. Could the authors clarify the advantages of uniform sampling and discuss whether importance sampling could improve efficiency while preserving the theoretical guarantees?

2.) Could the authors evaluate Prof-K on a broader range of applications, for example, top-kk selection for sparse attention in a larger-scale LLM setting? My concern is less about the scale of the existing experiments and more about how well the approach generalizes across different applications and operating regimes.

I would be happy to increase my score if the authors adequately address these concerns.

Reviewer_VNTPOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

The paper speeds up exact top-k selection on very large GPU tensors when k is small. A small random sample sets a threshold, one streaming pass keeps only elements above it in a compact buffer, and exact selection then runs on that buffer. Because the retained count depends only on ranks, the guarantee holds for any input, and a runtime count detects failure and redraws the sample, so the result is always exact. A Triton implementation is compared with torch.topk and RadiK on two GPUs and used in sparse autoencoder training and gradient sparsification.

Critical strengths
  1. The guarantee is genuinely distribution-free and the output is always exact. Because the analysis depends only on ranks under uniform sampling, it holds for heavy-tailed and adversarial inputs, and the authors verify that the training runs with Prof-K and with torch.topk produce identical selected sets, so the speed-up cannot be coming from a slightly different selection.
  2. The end-to-end evidence is convincing. Reducing step time by 1.20 to 1.30 times in sparse autoencoder training and 1.38 times in gradient sparsification, with identical outputs, shows that the kernel gain survives in a real loop rather than only in a microbenchmark.
Critical weaknesses
  1. The comparison covers only two baselines, torch.topk and RadiK, while the related work discusses RTop-K and Dr. Top-k as strong GPU selectors and does not evaluate them. A claim of state-of-the-art speed needs the strongest available exact kernels, not the two most convenient ones.
  2. The abstract overstates the result. It reports 1.5 to 15 times speed-up over torch.topk and RadiK, but Figure 2 shows Prof-K slower than RadiK in many cells, with ratios around 0.6 to 0.9, and the introduction itself concedes that it trails RadiK for small k on the H100. The range should be stated separately per baseline and per regime, and the duplicated N in Table 1 needs explaining: two rows share a pool size of about 1.1 billion elements yet report 4.48 and 9.69 GPU-hours with nearly the same step time, which cannot both be right.
Questions for authors
  1. Why are RTop-K and Dr. Top-k not compared? If their code is unavailable, say so, because the state-of-the-art claim currently rests on two baselines.
  2. What explains the 4.48 versus 9.69 GPU-hour difference for the two rows with the same N in Table 1?
  3. Please report timing variance and give the speed-up range separately for torch.topk and for RadiK, including the cells where Prof-K is slower.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.