Reproduce “Approximate Top-$k$ for Increased Parallelism” on OpenResearch
Turn your favorite coding agents into research agents that review literature, develop hypotheses, and run experiments.
Universal app for Apple silicon and Intel. Requires macOS 11 or later.
About this paper
Oscar Key, Luka Ribar, Alberto Cattaneo, Luke Hudlass-Galley, Douglas Orr
Researchers from UCL and Graphcore Research introduce a two-stage bucketed approximate top-k algorithm to enhance parallelism on machine learning accelerators, reducing the runtime of the top-k operation by over 4x in LLM sparse attention with minimal impact on accuracy. The method also contributes to an approximately 10% end-to-end speed-up in LLM generation and is provided as a publicly available PyTorch implementation.
Key insights
- Optimal approximate top-k configurations for balancing recall and computational cost are highly dependent on the `k/n` ratio.
- For `k ≪ n`, increasing the number of interleaved buckets (`b`) with `k_b = 1` is efficient, while for `k ∝ n`, increasing `k_b` to avoid the second stage is more effective.
- Interleaved bucket assignment is crucial for robust recall with real-world, correlated data, and small `k_b` values enable highly efficient register-based priority queue implementations.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.