# Composing Finite State Transducers on GPUs

arXiv: https://arxiv.org/abs/1805.06383 · HTML: https://mlsanity.com/paper/1805.06383/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 May 2018.

## Built on by (most cited first, 4 of 4)

- [Automata-based constraints for language model decoding](https://mlsanity.com/paper/2407.08103/) (2024)
- [Implementing contextual biasing in GPU decoder for online ASR](https://mlsanity.com/paper/2306.15685/) (2023)
- [Bregman Conditional Random Fields: Sequence Labeling with Parallelizable Inference Algorithms](https://mlsanity.com/paper/2506.00732/) (2025)
- [Parallel Composition of Weighted Finite-State Transducers](https://mlsanity.com/paper/2110.02848/) (2021)

## Abstract (arXiv)

Weighted finite-state transducers (FSTs) are frequently used in language processing to handle tasks such as part-of-speech tagging and speech recognition. There has been previous work using multiple CPU cores to accelerate finite state algorithms, but limited attention has been given to parallel graphics processing unit (GPU) implementations. In this paper, we introduce the first (to our knowledge) GPU implementation of the FST composition operation, and we also discuss the optimizations used to achieve the best performance on this architecture. We show that our approach obtains speedups of up to 6x over our serial implementation and 4.5x over OpenFST.