RayFST: Accelerating Finite-State Transducer Composition with Ray Tracing Cores

Abstract

Finite-state transducer (FST) composition is a fundamental but computationally expensive operation in domains such as speech recognition and natural language processing. Despite the increasing computational power of GPUs, existing parallelization approaches for FST composition face challenges due to irregular memory access during traversal and the high computational cost of comparing transitions. In this work, we leverage specialized GPU ray tracing (RT) cores to accelerate this non-graphics computation. We introduce RayFST, which maps the FST structure into a 3D spatial representation and retrieves transitions through hardware-accelerated ray intersection. We also present two ray-based optimizations: Ray Forwarding, which performs label matching directly by emitting rays across the two FSTs, and Dynamic Ray Generation, which eliminates invalid rays and balances workloads across rays. Experiments on real-world FST benchmarks show an 8.9 × geometric mean speedup over the state-of-the-art GPU FST library and up to 1.61 × end-to-end training speedup on two FST applications.