RTop-K: Ultra-Fast Row-Wise Top-K Selection for Neural Network Acceleration on GPUs

Xi Xie, Yuebo Luo, Hongwu Peng, Caiwen Ding

TL;DR

RTop-K is a specialized binary search-based algorithm designed to accelerate row-wise top-k selection on GPUs, a common bottleneck in modern neural networks like Graph Neural Networks (GNNs). By leveraging hardware-aware optimizations and an "early stopping" approximation strategy, it achieves up to an 11.49× speedup over standard PyTorch implementations while maintaining model accuracy.

What Problem Does This Paper Address?

Top-k selection—identifying the $k$ largest or smallest elements in a set—is a foundational operation in computer science. In the context of modern deep learning, we often need to perform row-wise top-k selection. This involves processing millions of relatively small vectors (e.g., hidden dimensions of 256 to 1024) simultaneously.

Existing GPU-accelerated top-k algorithms, like RadixSelect or Bitonic Sort, are typically optimized for single massive vectors or small batches of large vectors. When applied to the "many small vectors" scenario common in GNN training or sparse attention mechanisms, these methods become inefficient due to high resource overhead and unnecessary sorting. The authors identify a clear gap: we need a minimalistic, highly parallel algorithm tailored for large-scale, small-vector row-wise selection.

Methods

The authors introduce RTop-K, which departs from traditional sorting-based approaches in favor of a binary search-based thresholding method.

  1. Binary Search Approach: Instead of sorting, RTop-K finds a threshold value ($thres$) such that exactly $k$ elements are greater than or equal to it. It iteratively refines the range between the vector's minimum and maximum values.
  2. Early Stopping: Recognizing that neural networks are inherently robust to noise, the authors propose stopping the binary search after a fixed number of iterations (e.g., 5–8). This yields an approximate top-k set much faster than an exact search.
  3. GPU-Centric Design: The implementation is meticulously mapped to GPU hardware:
  4. Warp-Level Parallelism: Each vector is processed by a single warp (32 threads). This minimizes synchronization overhead.
  5. Warp Primitives: The algorithm uses fast register-based primitives like shuffle (to share min/max values), ballot (to create bitmasks of elements exceeding the threshold), and popcnt (to count set bits) to avoid slow global memory accesses during the search phase.
  6. Shared Memory: Vectors are loaded into shared memory once, and all search iterations happen locally before the final results are written back to global memory.
Figure 2: Illustration of the binary search-based top-k selection algorithm.

Datasets

The researchers evaluated RTop-K using two distinct approaches:

  • Kernel Benchmarking: Synthetic datasets with normally distributed elements were used to measure raw execution time across various matrix dimensions ($N$ rows, $M$ columns) and $k$ values.
  • End-to-End GNN Training: RTop-K was integrated into the MaxK-GNN framework and tested on four standard graph benchmarks: Ogbn-products, Yelp, Reddit, and Flickr. They evaluated three popular GNN architectures: GraphSAGE, GCN, and GIN.

Key Insights and Ideas

  • Thresholding > Sorting: For most neural network applications, the exact order of the top-k elements doesn't matter—only their values and indices do. By focusing on finding a threshold rather than a full sort, RTop-K eliminates significant computational waste.
  • The Power of Approximation: The "aha moment" is the effectiveness of early stopping. The authors demonstrate that even if the search stops early and misses a few "true" top-k elements, the impact on final model accuracy is negligible. In some cases, this approximation even slightly improved testing accuracy, likely acting as a form of regularization.
  • Hardware-Algorithm Alignment: By assigning one warp per vector, the algorithm perfectly matches the SIMT (Single Instruction, Multiple Threads) nature of GPUs, allowing for extremely efficient communication via warp-level primitives.
GPU implementation stages: Loading, Searching, and Selecting.

Key Results

  • Kernel Performance: RTop-K achieved an average speedup of 7.29× (exact version) and up to 11.49× (with early stopping) compared to PyTorch’s native torch.topk.
  • Training Acceleration: Integrating RTop-K into the training workflow of MaxK-GNNs resulted in overall training speedups ranging from 11.97% to 33.29% across different models and datasets.
  • Accuracy Retention: As shown in Figure 5, the testing accuracy remains remarkably stable across different max_iter settings, confirming that the early stopping approximation is safe for practical use.
Overall training speed-up ratio and testing accuracy across different GNN models.

Limitations and Future Work

  • Vector Size Constraints: The current shared-memory-based implementation is optimized for vector sizes $M \le 8192$. For larger vectors, the limited shared memory per GPU block becomes a bottleneck, requiring a different memory management strategy.
  • Data Distribution Sensitivity: While binary search works well for the typical distributions found in neural networks, its performance could theoretically degrade on extremely skewed or adversarial data distributions where many elements are nearly identical.
  • Hardware Portability: The heavy reliance on NVIDIA-specific warp primitives means porting this to other GPU architectures (like AMD's ROCm) would require significant re-engineering of the low-level kernels.

Summary updated

Abstract

Top-k selection algorithms are fundamental in a wide range of applications, including high-performance computing, information retrieval, big data processing, and neural network model training. In this paper, we present RTop-K, a highly efficient parallel row-wise top-k selection algorithm specifically designed for GPUs. RTop-K leverages a binary search-based approach to optimize row-wise top-k selection, providing a scalable and accelerated solution. We conduct a detailed analysis of early stopping in our algorithm, showing that it effectively maintains the testing accuracy of neural network models while substantially improving performance. Our GPU implementation of RTop-K demonstrates superior performance over state-of-the-art row-wise top-k GPU implementations, achieving an average speed-up of up to 11.49$\times$ with early stopping and 7.29$\times$ without early stopping. Moreover, RTop-K accelerates the overall training workflow of MaxK-GNNs, delivering speed-ups ranging from 11.97% to 33.29% across different models and datasets.
BibTeX
@inproceedings{xie2025rtop,
  author = {Xi Xie and Yuebo Luo and Hongwu Peng and Caiwen Ding},
  title = {{RTop-K: Ultra-Fast Row-Wise Top-K Selection for Neural Network Acceleration on GPUs}},
  booktitle = {International Conference on Learning Representations},
  year = {2025},
  url = {https://openreview.net/forum?id=PHg4rAXFVH},
}
Figure