Beam search is a decoding algorithm used in speech recognition to efficiently find the most likely sequence of words from audio input. Speech recognition systems generate many possible word sequences, each assigned a probability by a neural network or statistical model. Evaluating all possible sequences is computationally impractical, as the number grows exponentially with sentence length. Beam search addresses this by tracking a limited number of top candidate sequences (the “beam width”) at each step, pruning less likely options. This balances accuracy and computational efficiency, allowing the system to approximate the best possible output without exhaustive search.
In practice, beam search works by iteratively expanding hypotheses. For example, consider a system processing the audio phrase “play music by [unknown artist].” The acoustic model might initially suggest “play music by” followed by “The Beatles” or “The Beagles” with similar probabilities. With a beam width of 3, the algorithm retains both options alongside other candidates like “play music bee.” As the audio unfolds, subsequent context (e.g., a higher probability for “The Beatles” in the language model) helps resolve the ambiguity. Tools like Kaldi or ESPnet often combine scores from the acoustic model (which maps audio to phonemes or characters) and the language model (which predicts word sequences) to rank hypotheses. Beam search selects the top candidates based on the combined score, avoiding local greedy decisions that could lead to errors, such as prematurely locking into “bee” instead of “by.”
Developers tune beam search based on system requirements. A smaller beam width (e.g., 5–10) speeds up inference for real-time applications but risks discarding valid hypotheses. Larger beams (e.g., 20–50) improve accuracy for offline processing but increase memory and latency. Techniques like length normalization adjust scores to favor longer sequences, countering the bias toward shorter outputs. Some frameworks also integrate domain-specific language models during decoding—for instance, prioritizing medical terms in a clinical ASR system. While beam search is widely used, alternatives like greedy decoding or weighted finite-state transducers (WFSTs) exist, but beam search remains popular for its simplicity and effectiveness in balancing performance and resource constraints.