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

Excerpt

arXiv:2608.12573v2 Announce Type: replace 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