{"id":"21d7ba0c-ce4c-4e73-bfde-eea52e27004f","arxiv_id":"2608.12573","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":5.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"Prof-K is a sample-then-filter top-k algorithm that reduces exact selection over N values to exact selection over a small candidate buffer with a distribution-free probabilistic guarantee.","lead":"Prof-K is a shortcut for finding the largest k values in a huge array: it checks a small random sample, guesses a cutoff, and then only looks carefully at values above that cutoff. The method promises a user-chosen probability that the shortcut finds the true top k, with guarantees that do not depend on how the data is distributed.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3's failure bound is unsupported: the Gaussian tail approximation is never shown to be a finite-sample conservative upper bound, and the proof is omitted from Appendix C.","rationale":"The reader's weakest assumption correctly identifies the missing finite-sample conservatism of the Gaussian approximation as the load-bearing gap in the central theorem. My stress-test concurs: Theorem 3 is the main theoretical contribution, and it is unproven. The paper's own admission that the Gaussian approximation fails in the sparse regime, combined with the absence of any proof that it is one-sided conservative in other regimes, makes the stated upper bound on failure probability a conjecture rather than a theorem. The fallback mechanism in the algorithm means the practical consequence is a higher-than-advertised fallback rate rather than incorrect output, but this still invalidates the 'at most epsilon' claim about the efficient one-pass path. I also note the finite-population-correction inconsistency in Eq. (9) versus Corollary 4's proof as additional evidence of incomplete proof hygiene, though the primary issue remains the missing tail bound. The proposed concrete test would settle the matter: exact enumeration of the negative-hypergeometric tails for representative parameters would show whether the Gaussian-based choices of t and M actually meet the epsilon budget. Without such a test or a rigorous proof, the REJECT verdict is appropriate and should remain unchanged.","tokens_in":11435,"tokens_out":9338,"duration_ms":91411,"concrete_test":"For a representative parameter grid (e.g., N in {10^5, 10^6, 10^7}, k in {10^2, 10^3, 10^4}, epsilon = 10^-3 with epsilon_A = epsilon_B = 5e-4), set S = max(32768, S* from Eq. (14)), compute t from Eq. (6) and M from Eq. (11). Directly sum the negative-hypergeometric mass function in Eq. (1) to compute exact Pr(R < k) and Pr(R > M). If either probability exceeds epsilon/2 for any cell of the grid, Theorem 3 is false as stated.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim (Theorem 3) is that choosing t via Eq. (6) and M via Eq. (11) bounds the total failure probability by epsilon. This depends entirely on treating the normal approximation from Lemma 2 as a finite-sample upper bound for the negative-hypergeometric tail probabilities Pr(R<k) and Pr(R>M). Lemma 2 is only asymptotic: it states convergence in distribution as N,S grow, with no rate, no Berry-Esseen bound, and no assertion of one-sided conservatism. The paper provides no finite-sample concentration inequality, no monotonicity argument showing the Gaussian tail dominates the true tail, and no proof of Theorem 3 at all (Appendix C contains only proofs of Corollary 4 and Theorem 5). The paper itself concedes the approximation is 'unreliable' in the sparse regime alpha*S << 1 (Section 4), which shows it is not a uniform conservative bound; for moderate regimes there is no evidence it is conservative either. Because the algorithm falls back to exact top-k on underflow or overflow, the theorem is actually a bound on the fallback rate, not on the correctness rate; the abstract's 'recovers the true top-k elements with probability at least 1−epsilon' is therefore a misstatement, but the efficiency guarantee is still unsupported if the Gaussian tails understate the true probabilities. A concrete finite-sample computation is necessary to determine whether the actual tail probabilities exceed epsilon for typical parameter choices.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":11676,"tokens_out":9651,"duration_ms":87313,"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":[{"comment":"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.","section":"Section 4, Theorem 3 and Appendix C"},{"comment":"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.","section":"Equations (5), (10) and Section 4"},{"comment":"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'.","section":"Abstract and Theorem 3"}],"minor_comments":[{"comment":"There is a typo in the lemma statement: 'negative hypergemoetric' should be 'negative hypergeometric'.","section":"Lemma 1"},{"comment":"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.","section":"Appendix C"},{"comment":"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.","section":"Figure 4"},{"comment":"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.","section":"Algorithm 1 and Corollary 4"},{"comment":"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.","section":"Section 4, Lemma 2"},{"comment":"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.","section":"Section 5"}],"recommendation":"major_revision","confidential_remarks":"The manuscript has a valuable empirical component and a clean combinatorial foundation, but the main theorem is unproven and the Gaussian-tail-to-CDF step is not justified as a finite-sample upper bound. If the authors can supply a rigorous finite-sample proof or revise the theorem to an asymptotic statement with appropriate caveats, the paper could become publishable; in its current form the central guarantee is unsupported."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Honestly, this paper made me want to like it. The sample-a-threshold, filter, refine scheme is natural, the negative hypergeometric analysis is correct, and the empirical speedups (1.5-10x) are plausible for the large-N, small-k regime. The BatchTopK SAE application is a good move: it shows a real workload where top-k is a bottleneck and a 4% end-to-end win is meaningful.\n\nWhat's new is the closed-form buffer and sample-size formulas, and the derivation that the buffer grows like k + O((kN)^{1/3}). The math in Lemmas 1 and 2 checks out, and Corollary 4's finite-population correction is in the right place (the proof and statement agree; the reader's complaint on that point doesn't hold up).\n\nBut the central claim, Theorem 3, is not proven. Appendix C gives no proof for it. The theorem depends on treating the Gaussian approximation in Lemma 2 as a finite-sample conservative upper bound on the tail probabilities Pr(R < k) and Pr(R > M). Lemma 2 is only convergence in distribution, with no rate and no one-sided domination. The paper even concedes the Gaussian is \"unreliable\" when alpha*S << 1, so the theorem can't hold uniformly as stated. Because the algorithm falls back to exact top-k on underflow/overflow, the real guarantee is \"avoids fallback with probability at least 1-epsilon,\" not \"recovers the true top-k with probability 1-epsilon\"—the abstract's phrasing is misleading.\n\nThis is a load-bearing flaw, but it's repairable. A finite-sample analysis (or a Berry-Esseen bound plus a check of the sparse regime) might fix it. As submitted, the headline probability guarantee is unsupported. The experiments also don't report the epsilons used, and no code is released, so the speedups can't be independently checked. The 95%-recall trade-off mentioned in the abstract isn't implemented either.\n\nI'd send this to reviewers: the idea is worth a round of work. Ask for the missing proof or a precise statement of regimes where the guarantee holds, plus code and epsilon reporting. If the authors close the gap, this would be a genuinely useful systems paper. As is, I wouldn't cite the guarantee, but I'd cite the approach as related work.","headline":"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.","tokens_in":12266,"tokens_out":3439,"would_cite":false,"duration_ms":29618,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["top-k selection","probabilistic filtering","single-pass algorithm","distribution-agnostic guarantee","negative hypergeometric distribution","sample size optimization","GPU top-k","sparse autoencoders"],"falsifier":"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.","tokens_in":11178,"feed_emoji":"⚡","tokens_out":8843,"duration_ms":76194,"temperature":0.7,"pith_summary":"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.","feed_headline":"Exact top-k now fits in a k + (kN)^{1/3} buffer instead of N","feed_subtitle":"One sample sets a safe cutoff; scan once, keep survivors, and exact selection runs on that small buffer.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the asymptotic normality of order statistics under sampling without replacement, on which Lemma 2's normal approximation rests.","marker":"[16]"},{"why":"The radix-based GPU top-k implementation used as the primary empirical baseline in the speedup comparisons.","marker":"[11]"},{"why":"Defines the BatchTopK sparse autoencoder training setup used to demonstrate end-to-end impact.","marker":"[6]"}],"fun_headline_variants":["Sample, scan once, exact top-k—with a fallback","One-pass top-k: sample a few, filter, exact result","Top-k without full scan: sample, filter, exact","Prof-K: sample-guided top-k, exact in one pass","Always exact top-k, faster via smart sampling"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Sample, scan once, exact top-k—with a fallback","One-pass top-k: sample a few, filter, exact result","Top-k without full scan: sample, filter, exact","Prof-K: sample-guided top-k, exact in one pass","Always exact top-k, faster via smart sampling"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000597,"raw_usage":{"total_tokens":2860,"prompt_tokens":1078,"completion_tokens":1782,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":694,"completion_tokens_details":{"reasoning_tokens":1698}},"tokens_in":694,"tokens_out":1782,"duration_ms":15506,"temperature":1.0,"reasoning_tokens":1698,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-16T00:05:31.528519+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"John Wiley & Sons, 2004","cited_arxiv_id":null,"evidence_quote":"Supplies the asymptotic normality of order statistics under sampling without replacement, on which Lemma 2's normal approximation rests."},{"cited_title":"Radik: scalable and optimized gpu-parallel radix top-k selection","cited_arxiv_id":null,"evidence_quote":"The radix-based GPU top-k implementation used as the primary empirical baseline in the speedup comparisons."}],"review_version":1}