Contextual Biasing with the Knuth-Morris-Pratt Matching Algorithm

This paper proposes a new method for contextual biasing of speech recognition (ASR) at decode time. The usual practice is to build a WFST for the biasing phrases and use this in a kind of shallow fusion strategy during decoding. The authors posit that such a method is inefficient on TPUs, and hence propose an equivalent string matching technique based on Knuth-Morris-Pratt (KMP) algorithm. They show that this method provides significant improvements in WERs for utterances containing biasing phrases, without causing large degradations when they are not present.

This paper addresses the problem of contextual biasing for speech recognition. The paper proposes to use very popular and efficient KMP algorithm used for pattern searching to bias the ASR decodes with the contextual terms.

Experimental results on the enterprise model and real/TTS audio show usefulness of this approach.

This paper is about contextual biasing for automatic speech recognition (ASR).

Contextual biasing means: Consider Google Home or Alexa, where it is common to play songs, or maybe call someone from the contact list. So when the user speaks, the probability for such words of recently played songs or from person names from the contact list are higher than for other users, and contextual biasing will use that knowledge and boost the scores in the beam search recognition for such words or phrases.

Contextual biasing is not new, and many previous solutions to this exist. In this paper, a new method is proposed, to improve the beam search specifically. The ASR model is not changed. More specifically, the authors propose to use the Knuth-Morris-Pratt algorithm as an efficient way to find biasing phrases in the hypotheses and then boost them.

The Knuth-Morris-Pratt (KMP) algorithm is an algorithm to search for a substring in a given string in an efficient manner. The naive implementation would take O(n * m), n being the long string length, m being the substring length, while KMP can do it in O(n + m).

This provides an alternative formulation to the weighted finite state transducer framework, which conceptually does the same. However, they also use an efficient TPU-friendly implementation of this specific algorithm.

The experiments show that the KMP method on its own performs slightly worse than another model-based biasing method, namely the neural associative memory (NAM). However, KMP and NAM combined give improvements over NAM alone.

Runtime benchmark

Our model is non-streaming (i.e., processes the entire audio before producing results) and the encoder output has a frame rate of 320ms due to time reduction. We measure the run time of our ASR system on a single Google cloud TPU v3 (https://cloud.google.com/tpu/docs/system-architecture-tpu-vm#tpu_v3), for processing a batch of 8 utterances of 15-long random audio, with both B=300 biasing phrases and B=1000 biasing phrases.

Cost of preparation work (biasing phrase encoding for NAM, and failure function computation for KMP) are not shown as they can be done in parallel to audio encoder (and take less time). For much larger # of phrases, one shall perform a quick filtering of biasing phrases (e.g., based on NAM), before sending them for decoding.

Also note that TPU v3 was launched around 2018, and more recent TPU versions could be a few times faster.

CPU WFST-biasing baseline

It is highly non-trivial to set up CPU WFST biasing for the exact model we have in the submission and finish tuning in time. Here we provide biasing results for a model similar to the “large-pass” model from the following paper:

• Ding et al. A Unified Cascade Encoder ASR Model for Dynamic Model Sizes. 2022.

This model has 120M parameters, was trained on 1 million hours (more than the amount of data used in current paper), with a 4.2% WER on the in-house voice search eval set (on which the 900M model in current paper achieves 3.8%).

This model achieves 14.7% WER on Contact-Tag without biasing, matching that of the model in the current paper. WFST-biasing with this model with extensive list of carrier phrases (e.g., "call \$CONTACT", "can you connect me to \\$CONTACT", "please dial \$CONTACT") achieves 3.9%, which is close to the WER of NAM and better than WER of KMP without carrier phrases. These results provide a good sanity check. We are in the process of benchmarking the size and runtime of FST and will provide the results when they are available.

Significance of our approach and “avoiding the FST language”

We shall clarify what we meant by “avoiding the FST language” in a later version. The graph representations of FSTs are generally sparse (there exist no edges between most node pairs). An alternative to our approach is to represent the FST as a list of edges, of the form (start state, end state, input/output label, weight), and perform lookup of these edges to follow the FST on TPU/GPU. Note that this approach still requires first constructing the FST with non-trivial optimizations (e.g., determinization, minimization, weight pushing, etc). Our approach has a clear advantage in its simplicity: as a reviewer commented, it boils down to simply translating our pseudo-algorithms into any deep learning platform with a few loops, without any special FST operations (although realizing its equivalence to WFST requires understanding of automata theory).

Our on-TPU benchmarks show that our method is efficient. The small memory footprint is self-evident: for each utterance we store the failure function table which has the same size of the biasing phrases, and for each hypothesis we store an integer (partial matching length) for each phrase. We did perform KMP biasing with 20K phrases, and the method fits on TPU v3 equipped with 16G memory.

Another important advantage of our method is that it trivially allows automatic differentiation throughout the decoding process (implemented with tf.while loop), and opens the door to learning with the discrete structure of biasing (e.g., by discriminative training).

We thank reviewers for constructive feedback. Here we address a few common concerns (remaining questions from each individual reviewer are addressed below the original review).

Wide applicability of our method

Our method is not limited to ASR. It can be used with any autoregressive sequence model, during decoding or sampling/generation, to promote desired phrases or patterns (one could potentially incorporate more regex capability such as wildcard). For example, one may use our algorithm in LLM generation, to promote certain topics/facts, by providing the model a list of relevant phrases with positive bonuses. Another usage of our method is negative biasing, i.e., if we would like to prevent certain offensive results being decoded, we could provide the list of forbidden phrases and associate them with negative bonuses (or rather, penalties).

Reproducibility

We will open source our implementation, after separating KMP-biasing from the production ASR recipe. Note we have provided accurate details in the pseudo-algorithms; actual implementations are relatively straightforward to obtain, by translating the pseudo-algorithms into tensorflow with proper vectorization. We also discussed memory cost, vectorization over (hyp, extension, phrase), and fast gathering by einsum throughout Section 2.

Comparison on public dataset

We first remark that our voice-search setup is realistic and challenging, which has a vocabulary of a few millions words, with long-tail distribution over a large amount of rare words. Our test sets are used in multiple prior publications, and our NAM baseline matches the most recent publication by Wu et al, 2023 (Dual-Mode NAM).

During the rebuttal period, we manage to experiment with public Librispeech setup by:

• Le et al. 2021a. Contextualized streaming end-to-end speech recognition with trie-based deep biasing and shallow fusion.

Note Librispeech has a vocabulary of 200K words, and all but the top-5K most frequent words are considered rare in this work. Also the OOV rate for Librispeech testsets are low, at 0.6% and 0.8% for test-clean and test-other respectively, see https://arxiv.org/pdf/1902.01955.pdf (Table 1); these are the reasons why we think "non-public" voice-search setup is more important, even though it's proprietary.

We have trained a 300M CTC model, which is a weaker acoustic model than RNN-T used by Le et al 2021a, and performed NAM and KMP biasing on top of CTC. Nonetheless, we obtain improved WERs with both KMP-biasing and NAM+KMP, compared with the “s3” setup, i.e., Deep Biasing-RNNT + WFST, which is the strongest model without external neural LM in Le et al. 2021a. Results for different number of biasing phrases are shown in the table below.

We expect that using our methods with a stronger RNN-T system will further improve WERs.

The paper proposes an application of the Knuth-Morris-Pratt (KMP) pattern matching algorithm as an extension of beam search for ASR decoding. This aims to perform "contextual biasing" to boost the chance that the output will contain rare but contextually-relevant entities. The approach is shown to reduce WER on an English voice search query benchmark. The main weaknesses are that the paper's presentation and use of terminology is not clear enough, that the experimental results lack some relevant baselines, and that the results do not sufficiently support the claims about efficiency. It is also unclear if the method is more generally applicable outside the specific ASR application.

Reject