Reproduce “Sample-Guided Exact Top-K Selection for Long-Context Sparse Attention” 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
Siran Liu, Yang Xue, Theo Tang, Changxu Shao, Qian Cheng, Haimeng Ren, Donghua Jiang, Haipeng Ming and 6 more
Tencent Inc. developed HPC-Ops Top-K, an exact Top-K selection operator for long-context sparse attention that uses a sample-guided three-phase algorithm to reduce full-row scans. The operator achieved a 1.55x geometric mean speedup over external baselines, scaling up to 1.75x for 1M context lengths, and reduced latency by up to 13.31 ms in framework-level traces.
Key insights
- Identifying a compact superset of the Top-K elements (an upper tail) requires significantly less precision than pinpointing the exact K-th rank boundary, enabling effective early filtering.
- Fixed-stride partial views of long score rows reliably provide globally calibrated boundary estimates without relying on prior invocation history.
- The inherent 'sink and recency' structure of sparse attention scores, concentrating at context endpoints, further enhances the reliability and accuracy of sampled boundary estimation.
Summary by alphaXiv.
Tip: change arxiv.org to autoarxiv.org in any arXiv abstract link to open the paper here.