Pith. sign in

REVIEW 3 major objections 6 minor 16 references

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

T0 review · 3 major / 6 minor · reviewed 2026-08-16 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper claims that exact top-k selection over N elements can be reduced, with a user-specified failure probability ε, to exact selection over a buffer of size k + O((kN)^{1/3}) using a single-pass sampling filter.

desk verdict The core idea is clean and the rank lemma is right, but Theorem 3 is unproven and the asymptotic normal approximation is quietly carrying the whole guarantee. read the letter →

arxiv 2608.12573 v1 pith:V43XH32Q submitted 2026-08-12 cs.LG

Tadeusz Dziarmaga , Witold Sikora , {L}ukasz Struski , Jacek Tabor , Marcin Mazur This is my paper · ORCID
classification cs.LG
keywords top-kselectionprobabilisticfilteringsingle-passalgorithmdistribution-agnosticguaranteenegativehypergeometricdistributionsamplesizeoptimizationGPUsparseautoencoders
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

Prof-K asks whether exact top-k selection can be made much cheaper in the large-N, small-k regime without sacrificing correctness. The algorithm draws a small uniform sample, picks a conservatively low threshold from it, streams all N elements once into a compact buffer, and then runs exact top-k only on that buffer. The paper's central claim is a probabilistic guarantee: for any user-specified failure budget ε, the chance that a true top-k element is missed or the buffer overflows is at most ε, and this holds for any input distribution because it depends only on ranks, not on values. It also derives a closed-form buffer size and an optimal sample size scaling as (kN)^{1/3}, so exact selection ultimately runs over O(k + (kN)^{1/3}) candidates instead of N. Experiments on large synthetic tensors and in sparse autoencoder training report 1.5× to 10× speedups over optimized exact baselines.

What carries the argument

The central object is the negative hypergeometric distribution of the threshold rank R: the position, in the full population sorted in descending order, of the t-th largest value among a uniform sample of size S. Its mass function and moments (Lemma 1) and its normal approximation with finite-population correction (Lemma 2) carry the whole argument, converting tail-probability constraints into explicit choices for the sample rank t and the buffer capacity M. The computational workhorse is the single-pass filter: after the threshold is fixed, the full input is scanned once and only elements at or above τ are written into a preallocated buffer, so the expensive exact top-k stage runs on at most M candidates rather than N.

What would settle it

Compute the exact negative-hypergeometric probabilities Pr(R < k) and Pr(R > M) for the t and M produced by Equations (6) and (11) at a concrete (N,k,ε); if their sum ever exceeds ε, the advertised guarantee fails. Since the claim is distribution-agnostic, checking any single parameter regime where the exact CDF exceeds the normal-tail bound settles the matter.

Watch

Extended reading notes

Core claim

The central discovery is that the rank R of the sample-selected threshold in the fully sorted input follows a negative hypergeometric distribution regardless of the input values, so all failure events can be analyzed purely in terms of ranks. Lemma 1 gives the exact distribution and moments; Lemma 2 approximates it by a normal distribution with a finite-population correction. Splitting the failure budget into ε_A for recall failure and ε_B for overflow, the authors choose the sampled threshold rank t by Equation (6) and the buffer multiplier c by Equation (11), and Theorem 3 states that the total failure probability is then at most ε_A + ε_B = ε. Corollary 4 gives the buffer size M = k + z√(k(N−k)/S), and Theorem 5 says the optimal sample size is proportional to (kN)^{1/3} when k ≪ N. The method falls back to exact top-k if the buffer overflows or too few candidates are retained, so even when the probabilistic guarantee misses, the answer is still correct at the price of rare extra work.

Load-bearing premise

The proof assumes the normal bell-curve approximation to the threshold rank's distribution is conservative, meaning it never understates the chance of getting too few or too many survivors, but the paper only proves asymptotic normality and does not establish that this conservative direction holds at the finite sample sizes used by the parameter formulas.

Editorial extensions

If this is right

  • For k ≪ N, the final exact selection stage runs on M − k = O((kN)^{1/3}) candidates, so a billion-element tensor with k = 100 needs only a few thousand survivors.
  • Users can trade exact recovery for speed by relaxing the recall target while retaining a fallback path that still returns the exact answer when the filter fails.
  • The rank-based analysis makes the guarantee independent of the input distribution, so heavy-tailed or adversarially arranged values do not weaken the bound.
  • In batch settings, the per-call failure probability accumulates across batch elements, so the same ε budget must be allocated with batch size in mind.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The unproven conservative direction of the normal approximation can be tested directly, and if it fails in sparse regimes, the same framework could be made rigorous by replacing Equations (5) and (10) with exact negative-hypergeometric quantiles or a distribution-free concentration inequality.
  • Because the sample is drawn once per call, repeated top-k calls on similar tensors—as in SAE training—could reuse or update the threshold across steps to amortize sampling cost further; the paper does not explore this.
  • The filter is orthogonal to the exact selection kernel, so it could be composed with any optimized GPU selection routine, not just the radix-based baseline used here, potentially making the speedups complementary to future kernel improvements.
  • The (kN)^{1/3} sample-size scaling suggests a natural streaming extension where N is unknown or grows over time, since the required sample size grows sublinearly in the data volume.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 6 minor

Summary. This paper introduces Prof-K, a one-pass sampling-based filter for exact top-k selection. The algorithm samples S indices uniformly, computes a threshold tau as the t-th largest sampled value, retains all elements above tau in a buffer of capacity M, and runs exact top-k on the buffer; on underflow or overflow it falls back to exact top-k on the full input. The authors derive the rank distribution of the threshold (Lemma 1), an asymptotic normal approximation (Lemma 2), parameter choices for t and M (Equations (6) and (11)), a closed-form buffer size (Corollary 4), and an optimal sample size scaling as (kN)^{1/3} (Theorem 5). They report 1.5x-10x speedups over PyTorch topk and RadiK on H100 and RTX 3060, and a 1.044x end-to-end speedup with unchanged quality in BatchTopK SAE training.

Significance. If the central guarantee were established, Prof-K would be a valuable distribution-agnostic primitive: it reduces exact top-k over N elements to selection over roughly k + (kN)^{1/3} candidates with controllable fallback, and the experimental evaluation is extensive and practical. The paper's strengths include the exact combinatorial characterization of the threshold rank, a clean cost model for sample-size optimization, and benchmarks against strong baseline kernels in a realistic training loop. However, the main theoretical claim (Theorem 3) is currently unproven, and the argument depends on using asymptotic Gaussian tails as finite-sample upper bounds; without a rigorous bound, the advertised probabilistic guarantee is not established.

major comments (3)
  1. [Section 4, Theorem 3 and Appendix C] The paper's central theoretical result, Theorem 3, is asserted but not proved. Appendix C contains proofs only for Lemma 1, Lemma 2, Corollary 4, and Theorem 5 (mislabeled as 'Theorems 1, 2, 4, 5'), and there is no proof of Theorem 3 anywhere. Since Theorem 3 is the basis for the advertised 'at most epsilon' failure bound, this is a load-bearing omission rather than a presentational one.
  2. [Equations (5), (10) and Section 4] The parameter choices for t and M are derived by replacing the negative-hypergeometric tail probabilities Pr(R<k) and Pr(R>M) with Gaussian CDF values, and Theorem 3 treats these approximations as upper bounds. Lemma 2 provides only convergence in distribution as N,S grow, with no rate, no Berry-Esseen bound, and no assertion of one-sided conservatism. The paper itself concedes in Section 4 that the Gaussian approximation is 'unreliable' in the sparse regime alpha*S << 1, but it gives no argument that the approximation is conservative in any finite regime. A concrete finite-sample comparison using the exact distribution in Equation (1) for the parameter ranges in the experiments is necessary to determine whether the actual fallback probability can exceed epsilon.
  3. [Abstract and Theorem 3] The abstract states that Prof-K 'recovers the true top-k elements with probability at least 1 - epsilon', but the algorithm always returns the exact top-k because it falls back to exact selection on underflow or overflow. The event bounded by Theorem 3 is the probability of invoking fallback, not the probability of returning a wrong answer. This conflation affects the interpretation of the correctness claim and should be rephrased, for example as 'completes the filtering stage without fallback with probability at least 1 - epsilon'.
minor comments (6)
  1. [Lemma 1] There is a typo in the lemma statement: 'negative hypergemoetric' should be 'negative hypergeometric'.
  2. [Appendix C] The proof headings should be renumbered to match the main text: 'Proof of Theorem 1' refers to Lemma 1, 'Proof of Theorem 2' refers to Lemma 2, and 'Proof of Theorem 4' refers to Corollary 4.
  3. [Figure 4] The caption says 'fixed N = 2^9', but the text and the axes (K up to 2^18) indicate the intended value is N = 2^29; as written, the figure is inconsistent with the reported experimental setup.
  4. [Algorithm 1 and Corollary 4] Corollary 4 states an equality for M, but Algorithm 1 applies a ceiling; please clarify whether the theorem and corollary are intended with exact equality or with the ceiling operation.
  5. [Section 4, Lemma 2] The display in Equation (3) is ambiguous: the denominator should clearly indicate N times the square root of (q(1-q)/S) times (1 - S/N), but the parentheses are missing, making it hard to parse.
  6. [Section 5] The heatmaps in Figure 2 report averages without error bars or variance information; adding confidence intervals or run-to-run variability would strengthen the empirical claims.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: failure budgets are user-specified inputs, the rank distribution is derived combinatorially, and speedups are external benchmarks; the unproven Gaussian-tail conservatism is a rigor gap, not circular reasoning.

full rationale

Prof-K's failure-probability analysis starts from Lemma 1, an exact combinatorial expression for the rank R of the sample threshold under uniform sampling without replacement, which is distribution-free by construction. The parameters t and M are chosen from user-specified failure budgets εA and εB via Equations (6) and (11); these epsilons are inputs, not fitted constants, and the theorem's conclusion (failure ≤ ε) is not used in deriving them. No quantity being 'predicted' appears as a fitted parameter: the correctness guarantee is not calibrated to the test data, and the speedups are wall-clock comparisons against PyTorch topk and RadiK, i.e., external benchmarks. The manuscript contains no load-bearing self-citation: the only external support for asymptotic normality, Lemma 2, is cited to a standard textbook (David and Nagaraja). The concern shared by the reader and the skeptic—that Lemma 2 is asymptotic, that Theorem 3's proof is absent from Appendix C, and that the Gaussian tail has not been shown to be a finite-sample conservative upper bound for the negative hypergeometric tails—is a genuine rigor gap affecting the correctness guarantee. However, that gap is not circularity: it is an unsupported mathematical step, not a reduction of the theorem to its own assumptions, and no fitted parameter is renamed as a prediction. The fallback to exact top-k on underflow or overflow means Theorem 3 is effectively a bound on the fallback rate rather than on final-answer incorrectness, but this is a semantic clarification, not a circular derivation. Accordingly, no circular step is identified and the circularity score is 0.

Assumptions & free parameters 2 free parameters · 4 assumptions · 0 invented entities

No new physical or algorithmic entities are postulated. The only inputs are user-specified epsilon and the data; all parameters are either standard distributional quantities or hand-set implementation bounds. The main burden is the unproven conservative Gaussian approximation.

free parameters (2)
  • tau_B / tau_A cost ratio = 1 (default)
    Introduced in Eq. 13 to set the optimal sample size S*. The paper says a default of 1 performs robustly; it is hand-chosen, not measured, and does not affect the correctness bound.
  • Smin, Smax sample-size bounds = 32768, 131072
    Set in Algorithm 1 to avoid high-variance thresholds and sampling overhead. These are implementation choices, not derived from the theory.
assumptions (4)
  • standard math Rank of the t-th largest sample value in the full sorted input follows the negative hypergeometric distribution (Lemma 1).
    Used to derive the threshold and buffer guarantees; standard result in sampling without replacement and order statistics [16].
  • ad hoc to paper Gaussian approximation to the negative hypergeometric tail is a conservative upper bound for Pr(R<k) and Pr(R>M) at finite N,S.
    Theorem 3 depends on this unproven assumption. Lemma 2 only gives asymptotic normality; no Berry-Esseen or exact tail bound is provided, so the 'at most epsilon' guarantee is not established.
  • domain assumption The streaming pass can uniformly sample S indices without replacement from [N] at low cost.
    The algorithm requires either random access to the tensor or reservoir sampling; the paper does not discuss the cost or implementation of this step for true streams.
  • domain assumption GPU runtime is modeled by C = tau_A S + tau_B M log k (Eq. 13).
    The optimal sample size Theorem 5 is derived from this simplified cost model, which ignores memory movement, synchronization, and kernel launch costs.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Prof-K: Probabilistic One-Pass Filtering for Efficient Top-k Selection." pith.science (2026). https://pith.science/paper/V43XH32Q

@misc{pith2026260812573,
  author       = {Pith},
  title        = {Pith review of: Prof-K: Probabilistic One-Pass Filtering for Efficient Top-k Selection},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/V43XH32Q}},
  note         = {Machine review of arXiv:2608.12573}
}
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 - $\epsilon$, where $\epsilon$ > 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.

Figures

Figures reproduced from arXiv: 2608.12573 by the authors.

Figure 1
Figure 1. The core idea of our Prof-K algorithm. Top: Full data of size N sorted in descending order; the true top-k boundary is marked by a vertical dashed line. Middle: A random sample (solid outlines) is used to compute a threshold τ (green dashed line) as a conservative estimate of the (k/N)-quantile. Bottom: The threshold filter is applied in parallel to the full data. Elements ≥ τ (green) are retained in a compact candi… view at source ↗
Figure 2
Figure 2. Average latency speedup of our method across the [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗
Figure 3
Figure 3. End-to-end latency (ms, log scale) as a function of [PITH_FULL_IMAGE:figures/full_fig_p011_3.png] view at source ↗
Figures from the paper (3 more)
Figure 5
Figure 5. Figure 5: Auxiliary GPU memory over￾head as a function of k for a fixed tensor size (N = 229) (logarithmic scale). Our method’s memory footprint is bounded by a function of the buffer capacity, avoiding OOM errors on massive ar￾rays. which gives N = B · ddict = 50,331,648, K = B…
Figure 6
Figure 6. Figure 6: Runtime comparison in BatchTopK SAE training. [PITH_FULL_IMAGE:figures/full_fig_p012_6.png]
Figure 7
Figure 7. Figure 7: BatchTopK SAE training quality comparison. We compare Torch [PITH_FULL_IMAGE:figures/full_fig_p012_7.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

16 extracted references · 11 canonical work pages

  1. [1]

    Best position al- gorithms for efficient top-k query processing.Information Systems, 36(6): 973–989, 2011

    Reza Akbarinia, Esther Pacitti, and Patrick Valduriez. Best position al- gorithms for efficient top-k query processing.Information Systems, 36(6): 973–989, 2011

    work page 2011

  2. [2]

    Efficient top-k query processing on massively parallel hardware

    Anil Shanbhag, Holger Pirk, and Samuel Madden. Efficient top-k query processing on massively parallel hardware. InProceedings of the 2018 International Conference on Management of Data, pages 1557–1570, 2018

    work page 2018

  3. [3]

    The sparsely-gated mixture-of-experts layer.Outrageously large neural networks, 2:2, 2017

    N Shazeer, A Mirhoseini, K Maziarz, A Davis, Q Le, G Hinton, and J Dean. The sparsely-gated mixture-of-experts layer.Outrageously large neural networks, 2:2, 2017

    work page 2017

  4. [4]

    Gshard: Scaling giant models with conditional computation and automatic sharding.arXiv preprint arXiv:2006.16668, 2020

    Dmitry Lepikhin, HyoukJoong Lee, Yuanzhong Xu, Dehao Chen, Orhan Firat, Yanping Huang, Maxim Krikun, Noam Shazeer, and Zhifeng Chen. Gshard: Scaling giant models with conditional computation and automatic sharding.arXiv preprint arXiv:2006.16668, 2020

    arXiv 2006

  5. [5]

    Switch transformers: Scaling to trillion parameter models with simple and efficient sparsity

    William Fedus, Barret Zoph, and Noam Shazeer. Switch transformers: Scaling to trillion parameter models with simple and efficient sparsity. Journal of Machine Learning Research, 23(120):1–39, 2022

    2022

  6. [6]

    Batchtopk sparse autoen- coders.arXiv preprint arXiv:2412.06410, 2024

    Bart Bussmann, Patrick Leask, and Neel Nanda. Batchtopk sparse autoen- coders.arXiv preprint arXiv:2412.06410, 2024

    arXiv 2024

  7. [7]

    Fast k-selection algorithms for graphics processing units.Journal of Experimental Algorithmics (JEA), 17:4–1, 2012

    ToluAlabi, JeffreyDBlanchard, BradleyGordon, andRusselSteinbach. Fast k-selection algorithms for graphics processing units.Journal of Experimental Algorithmics (JEA), 17:4–1, 2012

    work page 2012

  8. [8]

    Anil Gaihre, Da Zheng, Scott Weitze, Lingda Li, Shuaiwen Leon Song, Caiwen Ding, Xiaoye S Li, and Hang Liu. Dr. top-k: delegate-centric 13 top-k on gpus. InProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, pages 1–14, 2021

    work page 2021

Show all 16 references
  1. [9]

    Parallel top-k algorithms on gpu: A comprehensive study and new methods

    Jingrong Zhang, Akira Naruse, Xipeng Li, and Yong Wang. Parallel top-k algorithms on gpu: A comprehensive study and new methods. InPro- ceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, pages 1–13, 2023

    2023

  2. [10]

    Rtop-k: Ultra-fast row-wise top-k selection for neural network acceleration on gpus

    Xi Xie, Yuebo Luo, Hongwu Peng, and Caiwen Ding. Rtop-k: Ultra-fast row-wise top-k selection for neural network acceleration on gpus. InThe Thirteenth International Conference on Learning Representations, 2024

    2024

  3. [11]

    Radik: scalable and optimized gpu-parallel radix top-k selection

    Yifei Li, Bole Zhou, Jiejing Zhang, Xuechao Wei, Yinghan Li, and Yingda Chen. Radik: scalable and optimized gpu-parallel radix top-k selection. In Proceedings of the 38th ACM International Conference on Supercomputing, pages 537–548, 2024

    2024

  4. [12]

    Language models are unsupervised multitask learners

    Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. Language models are unsupervised multitask learners. OpenAI blog, 1(8):9, 2019

    2019

  5. [13]

    Gemma 2: Improving open language models at a practical size.arXiv preprint arXiv:2408.00118, 2024

    Gemma Team, Morgane Riviere, Shreya Pathak, Pier Giuseppe Sessa, Cassidy Hardin, Surya Bhupatiraju, Léonard Hussenot, Thomas Mesnard, Bobak Shahriari, Alexandre Ramé, et al. Gemma 2: Improving open language models at a practical size.arXiv preprint arXiv:2408.00118, 2024

    2024 arXiv

  6. [14]

    Space-efficient online computation of quantile summaries.ACM SIGMOD Record, 30(2):58–66, 2001

    Michael Greenwald and Sanjeev Khanna. Space-efficient online computation of quantile summaries.ACM SIGMOD Record, 30(2):58–66, 2001

    2001

  7. [15]

    dictionary_learning

    Samuel Marks, Adam Karvonen, and Aaron Mueller. dictionary_learning. https://github.com/saprmarks/dictionary_learning, 2024

    2024

  8. [16]

    John Wiley & Sons, 2004

    Herbert A David and Haikady N Nagaraja.Order statistics. John Wiley & Sons, 2004. A Limitations The primary limitation of Prof-K is that its benefits become less pronounced for smaller input sizesN, where the overhead of sampling and filtering provides less advantage over high...

    2004

Pith tools

Reviewed August 16, 2026 · model on record in the stance chip above.