FlashFPS: Efficient Farthest Point Sampling for Large-Scale Point Clouds via Pruning and Caching

Point-based Neural Networks (PNNs) have become a key approach for point cloud processing. However, a core operation in these models, Farthest Point Sampling (FPS), often introduces significant inference latency, especially for large-scale processing. Despite existing CUDA- and hardware-level optimizations, FPS remains a major bottleneck due to exhaustive computations across multiple network layers in PNNs, which hinders scalability. Through systematic analysis, we identify three substantial redundancies in FPS, including unnecessary full-cloud computations, redundant late-stage iterations, and predictable inter-layer outputs that make later FPS computations avoidable. To address these, we propose $\mathit{\text{FlashFPS}}$, a hardware-agnostic, plug-and-play framework for FPS acceleration, composed of $\mathit{\text{FPS-Prune}}$ and $\mathit{\text{FPS-Cache}}$. $\mathit{\text{FPS-Prune}}$ introduces candidate pruning and iteration pruning to reduce redundant computations in FPS while preserving sampling quality, and $\mathit{\text{FPS-Cache}}$ eliminates layer-wise redundancy via cache-and-reuse. Integrated into existing CUDA libraries and state-of-the-art PNN accelerators, $\mathit{\text{FlashFPS}}$ achieves 5.16$\times$ speedup over the standard CUDA baseline on GPU and 2.69$\times$ on PNN accelerators, with negligible accuracy loss, enabling efficient and scalable PNN inference. Codes are released at https://github.com/Yuzhe-Fu/FlashFPS.