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

Xi Xie, Yong Luo, Hongwu Peng, Caiwen Ding

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.

Introduction

Top-$k$ selection—finding the $k$ largest elements in a set—is a fundamental operation in computer science. In modern deep learning, particularly for sparse training and specialized architectures like MaxK-GNNs, this operation must be performed "row-wise": given a large matrix, find the top-$k$ values in every single row.

Existing GPU top-$k$ implementations, such as those in PyTorch, are often optimized for either a single massive vector or a small batch of very large vectors. However, neural networks frequently operate in a "many-small-vectors" regime, involving millions of rows with lengths typically $\le$ 1024. Standard algorithms like RadixSelect introduce significant overhead in these scenarios, leading to high memory consumption and slower training.

The RTop-K Algorithm

RTop-K addresses these challenges by replacing complex sorting or radix-based methods with a streamlined binary search approach.

Binary Search for Thresholds

Instead of sorting elements, RTop-K searches for a threshold value such that exactly $k$ elements in a row are greater than or equal to it. The algorithm iteratively narrows the range between the row's minimum and maximum values.

Binary search-based thresholding process in RTop-K across iterations.

Early Stopping

A key innovation in RTop-K is the "early stopping" mechanism. 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 produces an "approximate" top-$k$ set that is much faster to compute but still contains the most important features for the model.

GPU-Centric Implementation

The implementation of RTop-K is highly optimized for GPU architectures, specifically targeting the warp level.

  1. Warp-Level Parallelism: RTop-K assigns exactly one warp (32 threads) to handle one row. This mapping allows the algorithm to stay entirely within fast on-chip registers and shared memory during the search phase.
  2. Warp Primitives: The search phase uses high-speed warp primitives like shuffle and ballot for inter-thread communication, avoiding slow global memory accesses.
  3. Phased Execution: The process is divided into three main phases: Loading, Searching (the iterative binary search), and Selecting (extracting the final indices and values).
Detailed GPU implementation phases of RTop-K, highlighting memory usage and warp-level operations.

Experimental Evaluation

The authors evaluated RTop-K by integrating it into the training of various GNN models (GraphSAGE, GCN, and GIN) using large-scale graph datasets like Ogbn-products, Yelp, Reddit, and Flickr.

Performance Results

  • Raw Speedup: RTop-K achieves an average speedup of 11.49$\times$ with early stopping and 7.29$\times$ for exact top-$k$ selection compared to torch.topk.
  • End-to-End Training: Total training time for MaxK-GNNs was reduced by 11.97% to 33.29% across different datasets.
  • Accuracy Preservation: The impact of using approximate top-$k$ selection on final model accuracy was negligible, often staying within 0.1% of the baseline. In some instances, the approximation even slightly improved accuracy, likely providing a regularizing effect.

Conclusion

RTop-K provides a highly efficient solution for row-wise top-$k$ selection on GPUs, particularly for the vector sizes common in neural network hidden layers. By leveraging binary search and warp-level optimizations, it significantly outperforms existing libraries. Future work includes scaling this approach to larger vector sizes through multi-warp coordination or further exploring approximate selection as a deliberate architectural feature.

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 Yong 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