Time-Parallel Transducer Training with Class-Factorized Emissions

Speech recognizers built as transducers learn from a grid. One axis is the audio frames, the other is the output tokens, and every cell holds a probability distribution over the whole vocabulary. Training must sum over every monotonic path through this grid. Pruning the grid to a narrow diagonal strip already makes this practical. Two costs remain. The sum over paths is still computed one frame after another, so its sequential depth grows linearly with audio length. And every surviving cell still normalizes over the full vocabulary, which is expensive for Mandarin characters or word-level lexicons.

We propose to remove both costs with one reformulation. Once the grid is pruned to a strip of width $S$, the forward recursion becomes a product of tiny $S \times S$ matrices in the log-probability semiring (the algebra where "add" means log-sum-exp and "multiply" means add). That product can be computed with a parallel prefix scan, a tree-shaped reduction that finishes in $O(\log T)$ steps instead of $T$. The matrix entries are emission probabilities. If each token's probability is factored as "which word class, then which word within the class," every entry costs about $2\sqrt{|V|}$ operations instead of $|V|$. The objective stays exact: it is the same pruned transducer loss, computed in a different order. The aim is to make long-form, large-vocabulary transducer training time-parallel without the accuracy loss of linear-time alignment surrogates.

Core Claim

The bandwidth of a pruned alignment lattice, not the vocabulary size, should set the state dimension of an associative scan. This makes temporal parallelization of the exact transducer objective cheap. Class factorization then makes the cost of building each scan operator scale with $\sqrt{|V|}$. Neither piece exists in the work we found.

Temporal Parallelization of Inference in Hidden Markov Models supplies the method. It parallelizes forward-backward and Viterbi over time with associative scans and reports roughly 6,000x speedups at $T=10^5$, with numerical error below $10^{-16}$. It also constrains the design: its operators are $D \times D$ matrices with $O(D^3)$ composition. Using states equal to vocabulary entries would be hopeless at that cost.

Pruned RNN-T for fast, memory-efficient ASR training motivates the proposal. Its pruning leaves only $S$ label positions per frame. That gives us a natural small $D$, but it keeps both the sequential recursion and a flat softmax over $|V|$.

The Reformulation

Let $a_t \in \mathbb{R}^S$ hold the log forward variables for the $S$ label positions retained at frame $t$, with window start $s_t$ chosen by the pruning stage. One frame step does two things. It first takes a blank transition from frame $t-1$, which shifts by $s_t - s_{t-1}$. It then takes any number of label emissions within frame $t$. Both are linear in the log semiring:

$$a_t = M_t \otimes a_{t-1}, \qquad M_t = L_t \otimes P_t \otimes B_{t-1}.$$

Here $\otimes$ is log-semiring matrix-vector or matrix-matrix product. $B_{t-1}$ is diagonal, holding blank log-probabilities. $P_t$ is the $S \times S$ window shift. $L_t$ is lower triangular, with entry $(u,u')$ equal to the summed log-probability of emitting the target labels $y_{u'+1},\dots,y_u$ at frame $t$. Because $\otimes$ is associative, all $a_t$ follow from a prefix scan. The work is $O(T S^3)$, which is negligible for $S \le 8$. The span is $O(\log T)$, and gradients come from a reverse scan or automatic differentiation.

The entries of $L_t$ and $B_t$ need the joiner's log-probability of a specific token at each cell $(t,u)$. We factor the joiner output as

$$\log P(w \mid t,u) = \log P(c(w) \mid t,u) + \log P(w \mid c(w), t,u),$$

where $c(w)$ is the class of token $w$, and blank is a singleton class. With $C \approx \sqrt{|V|}$ classes of size about $\sqrt{|V|}$, each cell needs one class normalizer and one within-class normalizer. This follows the two-stage decomposition of LightRNN and of On efficient training of word classes and their application to recurrent neural network language models. We move it from language-model output layers into the lattice.

The same factorization applies to the cheap linear "trivial joiner" that Pruned RNN-T uses to choose pruning bounds. That stage evaluates the full $T \times U$ grid and pays for $|V|$ at every cell. With the factorization its cost drops from $O(TU|V|)$ to $O(TU\sqrt{|V|})$. The within-class term only needs the class of the next target token, so its normalizer is computed over that class's members alone.

Research Program

We will build the scan-based loss as a drop-in replacement for the sequential pruned DP in a k2/icefall-style pipeline. The first check is that it is exactly equal to the sequential version, comparing loss and gradients to floating-point tolerance on real lattices.

We will then study the factorized joiner along three dimensions. The first is how tokens are clustered: frequency bins, distributional (Brown-style) classes, and LightRNN-style learned assignments. The second is the number of classes. The third is whether classes are fixed or periodically reassigned. Note that LightRNN's reassignment uses a matching step that costs $O(|V|^2)$; at character-level vocabularies this is affordable, but we will report its cost.

The encoder is held fixed, a standard Conformer-class model, so the effects of the loss can be isolated. Swapping in a linear recurrent encoder such as the one in Resurrecting Recurrent Neural Networks for Long Sequences would make the whole pipeline time-parallel. We treat that as a follow-up, not a confound.

Closest related work and how this differs. Incorporating Class-based Language Model for Named Entity Recognition in Factorized Neural Transducer uses class tokens inside a transducer to recover rare entities, improving entity F1 from 55.6% to 72.6% on Giga-name-test. It does not use classes for lattice efficiency, and it keeps the unpruned sequential grid. Fast and parallel decoding for transducer parallelizes inference, not training, and imposes one symbol per frame. A Differentiable Alignment Framework for Sequence-to-Sequence Modeling via Optimal Transport achieves linear-time alignment by committing to a single monotonic transport plan. That costs accuracy: LibriSpeech 960h WER rises from 2.20% to 2.52%. Our approach keeps soft marginalization within the strip, so it should not pay that price.

Baselines

The naive reference is the unpruned transducer loss in warp-transducer/optimized_transducer. On LibriSpeech, Pruned RNN-T reports these baselines at 211 ms per dynamically batched step, 12.76 GB peak memory, 2.33 train hours per epoch, and 2.61% test-clean WER.

The strongest existing method is Pruned RNN-T itself, at 38 ms per batch, 2.59 GB, 1.17 hours per epoch and 2.56% test-clean WER (Pruned RNN-T). It is the right competitor because it already exploits the diagonal strip. Any gain we claim must come from parallelizing that strip over time and from cheaper normalization, not from pruning.

We will rerun Pruned RNN-T and our method with the same encoder, data, pruning width $S$, number of GPUs, and learning-rate schedule. Their tuning budget is identical: the same number of trial runs per method. Beating it means two things together. First, wall-clock time per epoch and peak memory must be lower at matched WER, within 0.05 absolute on LibriSpeech and within 0.1 absolute CER on AIShell. Second, the advantage must grow with utterance length and with $|V|$, as the cost model predicts.

The file reports no Pruned RNN-T result on AIShell. Its only AIShell numbers are for second-pass rescoring with a neural language model (baseline 11.33% CER, Class-Based Neural Network Language Model for Second-Pass Rescoring in ASR), which is not comparable. We will therefore establish the Pruned RNN-T AIShell number ourselves.

Two ablations isolate the ingredients. One uses the scan with a flat softmax. The other uses the class factorization with the sequential DP. As linear-time alternatives we include CTC and OTTC under the same encoder.

Why not just…?

Why not just use a small subword or byte vocabulary so the softmax is cheap? For English this is a real alternative, and on LibriSpeech with about 500 BPE units we expect class factorization to add little. We will report that honestly. For Mandarin, the character inventory is intrinsic. Bytes or very fine units lengthen the token sequence $U$, which enlarges the alignment grid, and subword fragmentation hurts rare entities (C-FNT). We will train byte-level and small-BPE Pruned RNN-T on AIShell and compare cost and CER directly. If byte-level matches our cost and accuracy, the class half of the proposal is not needed for that regime.

Why not just keep the sequential DP, since the encoder dominates training time? This is the strongest objection. For utterances of 10–20 seconds the DP may be a small share of each step. The scan pays off when $T$ is large, as in long-form audio, chunked streaming training, or high frame rates. We will profile the DP's share of time across utterance lengths. If the share stays small at the longest lengths we can train, we will reframe the scan's contribution around memory and long-form feasibility rather than speed.

Why not just segment long-form audio into short chunks? Segmentation needs reliable boundaries. When it fails, it cuts words or gives a chunk text that does not match its audio. We will compare segmented training against full-length training on concatenated long-form recordings, using the same data.

Why not just use OTTC or CTC, which are already linear-time? Their reported accuracy costs are the reason not to. On TIMIT, OTTC's WER is 8.76% versus 8.38% for CTC, and CTC itself is conditionally independent, with 53.5% of frames assigned to blank (OTTC). Our method keeps the exact pruned transducer objective. Including both as baselines will show whether that exactness is worth its cost.

Proposed Experiments

The first check is equivalence. We compare loss and gradients from the scan and from the sequential pruned DP on LibriSpeech lattices and on synthetic long lattices up to $T=10^5$. These synthetic lattices mirror the Gilbert-Elliott setting of Hassan et al.. We require the mean absolute difference to sit near floating-point precision, and we measure the speedup in span as $T$ grows.

The second check is the full training comparison. We run it on LibriSpeech 960h (WER on test-clean and test-other) and AIShell (character vocabulary of several thousand; CER). We also run Gigaspeech M with a large word-level vocabulary, reporting overall WER against the roughly 14.4% reported for FNT/C-FNT and entity F1 on Giga-name-test. Each comparison reports time per epoch, peak memory, and accuracy.

The third check is the scaling study. We build long-form inputs by concatenating consecutive LibriSpeech utterances from the same speaker into lengths of 1 to 10 minutes. We plot cost against $T$ and against $|V|$ for every method.

The decisive result has three parts. Accuracy must match Pruned RNN-T. The time and memory advantage must grow with $T$ on long-form data and with $|V|$ on AIShell and Gigaspeech. And on the Gigaspeech entity tests, the factorized joiner should not lose rare-word F1, and may gain it, since class sharing pools statistics across rare tokens. If the class factorization costs more than about 0.2 absolute CER on AIShell under every clustering choice, we will conclude it cannot buy efficiency at large vocabulary without hurting recognition, and report the scan alone.