# Parallel Composition of Weighted Finite-State Transducers

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 2 of its 19 references that are in the map.
- First posted on arXiv 6 Oct 2021.

## Builds on (most cited first, 2 of 2)

- [Differentiable Weighted Finite-State Transducers](https://mlsanity.com/paper/2010.01003/) (2020)
- [Composing Finite State Transducers on GPUs](https://mlsanity.com/paper/1805.06383/) (2018)

## Abstract (arXiv)

Finite-state transducers (FSTs) are frequently used in speech recognition. Transducer composition is an essential operation for combining different sources of information at different granularities. However, composition is also one of the more computationally expensive operations. Due to the heterogeneous structure of FSTs, parallel algorithms for composition are suboptimal in efficiency, generality, or both. We propose an algorithm for parallel composition and implement it on graphics processing units. We benchmark our parallel algorithm on the composition of random graphs and the composition of graphs commonly used in speech recognition. The parallel composition scales better with the size of the input graphs and for large graphs can be as much as 10 to 30 times faster than a sequential CPU algorithm.