- 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.