🤖 machine learning

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

The paper introduces Prof-K, a fast, scalable, and distribution-agnostic one-pass algorithm for top-k selection that uses probabilistic sampling to guarantee correctness with high probability while achieving significant speedups over existing methods, particularly in large-scale scenarios.

Original authors: Tadeusz Dziarmaga, Witold Sikora, Łukasz Struski, Jacek Tabor, Marcin Mazur

Published 2026-08-14

📖 4 min read☕ Coffee break read

CC BY 4.0

Original authors: Tadeusz Dziarmaga, Witold Sikora, Łukasz Struski, Jacek Tabor, Marcin Mazur

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are standing in front of a massive, chaotic library containing billions of books. You don't need to read them all; you just need to find the top 100 most interesting ones to put on a special display shelf. In the world of computer science, this is called "Top-k selection." It's a fundamental task that happens everywhere, from organizing search results on the internet to helping artificial intelligence decide which thoughts to focus on and which to ignore. As our digital data grows into mountains of information, the computers tasked with finding these "top" items are getting overwhelmed. Traditional methods try to sort through every single book to be absolutely sure, which is slow and exhausting. Other methods try to guess which books are good based on patterns, but they can get tricked by weird or tricky data. The big question for scientists is: How can we find the best items quickly without getting lost in the noise or making mistakes?

Enter Prof-K, a new method introduced by researchers Tadeusz Dziarmaga and his team at Jagiellonian University. Think of Prof-K as a clever, super-fast librarian who doesn't try to read every book. Instead, the librarian grabs a tiny, random handful of books from the shelves to get a "vibe" of the library. Based on this small sample, they set a "cutoff line"—a threshold of quality. Then, they do a single, lightning-fast pass through the entire library, only picking up books that are clearly above that line and tossing the rest. Finally, they do a careful, exact check only on the small pile of books they actually picked up. The magic of Prof-K is that it uses math to prove that, with very high probability, the true "top 100" books will almost certainly be in that small pile, even if the library contains books with weird, unpredictable, or "adversarial" content.

The researchers found that this approach is incredibly efficient. In their tests, Prof-K was 1.5 to 10 times faster than the highly optimized standard tools currently used by computers (like PyTorch's topk and a tool called RadiK). The biggest wins happened when the library was huge (billions of items) but the number of items needed to keep was relatively small. Unlike older methods that might fail if the data was messy or skewed, Prof-K's guarantees hold true regardless of how the data is distributed. It's like having a filter that works just as well whether the books are neatly organized or thrown in a pile.

Furthermore, the team showed that this speed doesn't come at the cost of quality. When they used Prof-K to train a specific type of AI model called a "Sparse Autoencoder" (which helps AI learn efficient ways to represent data), the model learned just as well as it did with the slower, exact methods. The AI's ability to reconstruct information and its "sparsity" (how focused it is) remained unchanged. In fact, by using Prof-K, the training process became slightly faster overall, shaving off about 4.25% of the total time needed for a long training run. While that might sound small, in the world of training massive AI models, that time adds up to hours of saved computing power.

The paper also provides a mathematical "recipe" for how to set up this filter. The researchers calculated that the ideal size for that initial random sample of books grows slowly—specifically, it scales with the cube root of the total number of items multiplied by the number of items you want to keep. This means even for a library with a billion books, you only need to peek at a tiny fraction (around 4,600 books in their example) to set a reliable cutoff. If the filter accidentally lets in too many or too few books, the system has a safety net: it can instantly switch back to the slow, exact method to ensure nothing is missed.

In short, Prof-K offers a way to make AI and data processing systems faster and more robust without sacrificing accuracy. It turns a problem that usually requires checking everything into a problem that only requires checking a smartly selected few, proving that sometimes, a little bit of randomness and a single pass through the data is all you need to find the best of the best.

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

1. Problem Statement

Top-k selection is a fundamental primitive in databases, information retrieval, and modern machine learning (e.g., sparse activations, attention pruning). As tensor sizes ( $N$ ) grow, particularly in large-scale GPU workloads, the cost of exact top-k selection becomes a bottleneck. This is most acute in the large- $N$ , small-to-moderate- $k$ regime, where only a tiny fraction of elements is retained.

Existing exact methods (sorting, heaps, partitioning) incur high memory movement and synchronization costs relative to the computation performed. While approximate methods exist, they often rely on brittle heuristics or assume specific input distributions (e.g., well-behaved data), making them unreliable under heavy-tailed or adversarial inputs. The challenge is to reduce the computational overhead of top-k selection without sacrificing correctness guarantees or robustness to distribution shifts.

2. Methodology: The Prof-K Algorithm

Prof-K is a probabilistic one-pass filtering algorithm designed to reduce the search space for exact top-k selection. It operates in four stages:

Sampling: A small, uniform random sample of size $S$ is drawn from the $N$ input elements without replacement.
Threshold Estimation: The sampled values are sorted, and a threshold $\tau$ is selected based on a specific rank $t$ within the sample. This threshold serves as a conservative estimate of the $(k/N)$ -quantile of the full population.
Filtering (One-Pass): The full input tensor is streamed once. Any element $x_i \ge \tau$ is retained in a compact candidate buffer of size $M$ (where $M$ is a small multiple of $k$ ). Elements below $\tau$ are discarded.
Refinement: An exact top-k routine is run only on the retained candidates in the buffer to produce the final result.

Fallback Mechanism: If the buffer overflows (more than $M$ elements pass the filter) or if fewer than $k$ elements are retained, the algorithm falls back to a standard exact top-k computation on the full input.

Theoretical Guarantees and Parameter Selection

The core insight is that the rank of the sample-based threshold follows a negative hypergeometric distribution, which depends only on ranks, not values. This allows Prof-K to provide distribution-agnostic guarantees.

The authors derive explicit formulas for the parameters $(S, t, M)$ to ensure the total failure probability is bounded by a user-specified $\epsilon$ :

Recall Failure ( $R < k$ ): Controlled by choosing $t$ such that the threshold is conservatively low.
Buffer Overflow ( $R > M$ ): Controlled by setting the buffer capacity $M$ sufficiently large.

The optimal sample size $S^*$ is derived to minimize total computational overhead (sampling cost + refinement cost). In the sparse regime ( $k \ll N$ ), the optimal sample size scales as:
$S^* \propto (kN)^{1/3}$
This scaling is significantly slower than linear growth in $N$ or $k$ , meaning the sampling overhead remains negligible even for massive tensors.

3. Key Contributions

Distribution-Agnostic Correctness: Unlike quantile-estimation methods that assume specific data distributions, Prof-K derives probabilistic correctness guarantees based solely on the combinatorial properties of uniform sampling. It remains robust against heavy-tailed and adversarial inputs.
One-Pass Filtering with Bounded Failure: The algorithm reduces the exact selection problem from $N$ elements to a small buffer of size $M \approx k$ , with a mathematically bounded probability of failure ( $\le \epsilon$ ).
Optimal Parameter Scaling: The paper provides a theoretical derivation for the optimal sample size $S^* \propto (kN)^{1/3}$ , balancing the cost of sampling against the cost of refining the candidate buffer.
Flexible Accuracy-Speed Trade-off: Users can tune the failure budget $\epsilon$ and buffer multiplier to trade off between strict exactness and maximum speed, with a guaranteed fallback to exact computation if the probabilistic filter fails.

4. Experimental Results

The authors evaluated Prof-K on synthetic benchmarks and a real-world machine learning workload.

Synthetic Benchmarks

Speedups: Prof-K achieved 1.5 $\times$ to 10 $\times$ speedups over highly optimized baselines (PyTorch torch.topk and RadiK).
Regime of Effectiveness: Gains were most pronounced in the large- $N$ , small-to-moderate- $k$ regime.
Memory Efficiency: Unlike radix-based methods (e.g., RadiK) that require $O(N)$ auxiliary space, Prof-K's memory footprint is bounded by the buffer size $M$ , preventing Out-Of-Memory (OOM) errors on massive arrays.
Robustness: Performance remained invariant across Uniform, Normal, and heavy-tailed Pareto distributions.

Real-World Application: BatchTopK Sparse Autoencoders (SAEs)

The authors integrated Prof-K into the training loop of BatchTopK Sparse Autoencoders, where top-k selection is a recurring bottleneck.

Setup: Training on OpenWebText using a Pythia-70m model with a dictionary size of 12,288 and batch size 4,096 ( $N \approx 50$ million).
Kernel Speedup: The top-k kernel runtime decreased from ~2.56 ms to ~1.13 ms (2.27 $\times$ speedup).
End-to-End Impact: The total training step time decreased from ~30.73 ms to ~29.42 ms, yielding a 1.044 $\times$ (4.25%) reduction in total training time.
Quality Preservation: Metrics including Normalized Mean Squared Error (NMSE), cross-entropy degradation, and variance explained showed no measurable difference between Prof-K and exact torch.topk. The probabilistic relaxation did not alter the learned representations or sparsity behavior.

5. Significance and Claims

The paper claims that Prof-K offers a principled, systems-level optimization for large-scale sparse machine learning workloads. Its significance lies in:

Scalability: It effectively addresses the memory-bandwidth bottleneck of top-k selection in large- $N$ regimes where exact methods struggle.
Robustness: It provides rigorous probabilistic guarantees that hold independently of the input distribution, a critical feature for adversarial or heavy-tailed data often encountered in practice.
Practical Utility: It demonstrates that relaxing the recall target (e.g., accepting a small failure probability) yields substantial speedups without degrading the quality of downstream tasks like SAE training.

The authors conclude that while the end-to-end speedup in their specific SAE experiment was modest (~4%), the reduction in the cost of the top-k primitive is significant. They posit that for larger models or longer training runs, these savings will translate into substantial wall-clock time reductions, making probabilistic filtering a viable and robust alternative to exact selection in sparse computing.