A Fair Rematch for Dynamic Beam Pruning

Speech recognizers and other sequence decoders search over many partial hypotheses at once and discard unpromising ones. The beam width, meaning how many hypotheses or how wide a score margin survives each step, sets both cost and accuracy. A long line of work argues that this width should change during decoding: widen it where the audio is ambiguous and narrow it where the audio is clear. The reported gains are large, including a 14x speedup against 5x for a static beam at comparable error, and the elimination of a 50% runtime blow-up on noisy audio. The evidence behind them is weak, though. Each method was built into its own decoder, often a proprietary one, and tuned on its own development data. It was usually evaluated on data that cannot be shared, and compared against a static baseline whose tuning budget is not stated. Nobody has run these controllers side by side on the same decoder, with the same data and the same tuning effort.

This proposal re-implements the main dynamic beam controllers behind one small interface. The interface separates "what the decoder scores" from "how many hypotheses to keep," and the controllers are then evaluated on open speech data degraded in controlled, released ways. Two questions follow. The first is whether the controllers still beat a fairly tuned simple baseline once calibration data and test data diverge. The second is whether controllers with feedback loops turn tiny numerical nondeterminism into different search paths, which would make their latency and accuracy figures irreproducible across hardware.

Core Claim

We hypothesize that a large share of the reported advantage of dynamic beam control comes from two sources. One is matched calibration: controller constants fit on data drawn from the test distribution. The other is weak static baselines that tune only a score margin and not a cap on the number of active hypotheses. If that is right, then under a shared interface and an equal tuning budget, a two-knob static baseline (score margin plus count cap) should recover most of the gain on in-distribution audio. The remaining advantage of the dynamic controllers should be concentrated in two places: tail latency under noise, and cross-condition transfer.

We further hypothesize that closed-loop controllers are measurably less reproducible than open-loop ones. A closed-loop controller adjusts the width based on how many hypotheses survived the previous step. An open-loop controller sets the width from a signal computed independently of the search. Small score differences across GPUs flip pruning decisions near the threshold, and feedback carries those flips forward. Both claims can be falsified, and either outcome changes how dynamic pruning results should be reported.

Research Program

The interface is the methodological core. At each decoding step the decoder exposes a fixed summary: the sorted scores of active hypotheses, the step index, and an optional side-channel confidence signal. The controller returns two numbers, a score margin and a maximum hypothesis count. The design borrows the separation strategy of OmniEvaluator, which splits evaluation into data, inference, post-processing and metric stages so that backends and metrics can be swapped. That system treats decoders as black boxes and only scores finished outputs. We instead open the search loop itself. The SMCTC design, which slots new resampling strategies into a fixed Monte Carlo engine, is the closer software analogy: the decoder engine stays fixed and the controller changes.

Behind this interface we re-implement four published controllers. The first is confidence-guided dynamic pruning from A confidence-guided dynamic pruning approach, which widens the beam through a sigmoid of frame-level confidence and is open-loop given its confidence model. The second is the self-tuning regulator from Dynamic beam pruning strategy using adaptive control, which steers the width to track a reference curve of active hypotheses and is closed-loop. The third is prior score range normalization from Efficient beam width control … prior score range normalization, which sets the width before search from a cheap first pass. The fourth is a learned per-step width predictor trained with the asymmetric loss of Beam-Width Prediction for Efficient Context-Free Parsing, transplanted from parse chart cells to decoding frames.

Each original relied on components we do not have, such as GMM catch-all models, the VoiceRex decoder, and HMM instance counts. We replace each with the nearest neural equivalent, for example a small CTC model as the cheap prior pass, and document every substitution as a deviation. Every run records its configuration, code hash, seeds and hardware in the manner of DeepDIVA.

The decoders are a CTC acoustic model with lexicon-constrained n-gram beam search, which is where width matters most, and an attention encoder-decoder with token-level beam search. The second decoder tests whether conclusions carry across decoder families.

The data are open. We use LibriSpeech and TIMIT, both used for reproducible speech benchmarking in NAS-Bench-ASR, and WSJ, the corpus of A fully differentiable beam search decoder. NAS-Bench-ASR fixed decoding settings across all its runs, so dynamic search was never in its scope. Its clean read speech also does not create the search explosions that motivate dynamic pruning. We therefore release a seeded degradation script. It adds babble built by overlapping other LibriSpeech utterances at fixed signal-to-noise ratios from clean down to 0 dB. It also adds speed and pause perturbations that move prosodic boundaries, which the boundary-driven work in Use of prosodic features for speech recognition identifies as regions of high search uncertainty. Every degraded condition can be regenerated exactly from the released seed, which replaces the proprietary call-center audio that grounds the strongest noise-robustness claim.

Cost is reported in two currencies. The first is wall-clock real-time factor on named hardware. The second is a hardware-independent count of hypothesis expansions per second of audio, which removes the dependence of reported speedups on the authors' machines.

Baselines

The naive reference is a static beam with a single score margin, tuned once on clean LibriSpeech development data and then frozen. This is roughly the configuration that the original papers compared against. It shows what a practitioner gets by default, and it reproduces the setting in which dynamic methods were reported to win. Beating it is necessary but not interesting.

The strongest competitor is a two-knob static baseline: score margin plus a hard cap on active hypotheses. It gets the same tuning budget as the dynamic controllers, the same number of development evaluations, chosen by the same search procedure. A count cap already bounds the cost per frame regardless of noise, which is the main benefit claimed for prior score normalization and the regulator. For this reason it is the competitor most likely to erase the published gains. No reported result found on Lacuna for a margin-plus-cap baseline compared against these controllers.

The strongest published dynamic result is confidence-guided pruning on Verbmobil '96. It reaches a time factor of 0.07 at about 1% absolute WER increase, a 14x speedup, where classical beam pruning reached 5x at a similar WER increase (Fabian & Lieb). For noise robustness, prior score normalization reported a 21.4% computation reduction at equivalent accuracy, and conventional decoding grew up to 50% slower at 20 dB (Kobashikawa et al.). For the regulator, the reported real-time factor fell from 4.26 to 1.92 at 72.72% versus 72.67% word accuracy on the Chinese 863 corpus (STR). As a modern accuracy anchor, the differentiable decoder reached 5.1% WER on WSJ nov92 at beam 500, where the ASG baseline needed 8,000 (Collobert et al.).

A dynamic controller counts as beating the two-knob baseline under one of two conditions. It can lie on a better WER-versus-expansions Pareto curve, with non-overlapping seed intervals, at matched average cost. Or it can show lower 95th-percentile per-utterance cost at equal WER on degraded conditions it was not calibrated on.

Two ablations isolate the key ingredients. The first compares matched calibration, with constants fit on the same degradation as the test, against mismatched calibration, with constants fit on clean audio only. Every controller and the two-knob baseline get this treatment, which separates "adaptivity" from "having seen the test conditions." The second ablation runs each controller with and without the side-channel confidence signal. This separates gains from extra information from gains from the control law itself.

Why not just…?

Why not just tune a static beam separately for each condition? Per-condition tuning is an oracle. A deployed recognizer does not know the noise level of the next call, which is the motivating fact in Kobashikawa et al.. We still run it, as an upper bound for static search. If dynamic controllers calibrated only on clean audio approach this oracle on noisy conditions, adaptivity is doing real work. If they do no better than the frozen two-knob baseline, it is not.

Why not just cap the number of active hypotheses? This is the real threat, and the proposal is built around it rather than against it. A count cap gives flat per-frame cost by construction, and the regulator in STR is in effect a smoothed, curve-following version of it. Where a cap could fall short is accuracy at ambiguous boundaries: it keeps the same number of hypotheses where the correct one is ranked low as where it is ranked first. Per-frame analysis of where the correct path drops out of the beam will show whether that happens. If the cap matches the dynamic controllers on both Pareto and tail metrics, we will report that as the main finding.

Why not just release each method's code instead of building a shared interface? Separate releases would reproduce each paper's own decoder, which is the source of the incomparability. OmniEvaluator found up to 80-point score swings on identical models from harness differences alone. Comparing pruning methods across different decoders, lattice formats and score scales would mix those effects with the control law. The interface is justified only if it adds negligible overhead. We measure that overhead directly, comparing the static baseline run through the interface against the same logic written inline.

Why not just train a differentiable decoder so that small beams suffice? The differentiable decoder still uses a fixed beam at inference. It costs about 30 minutes per epoch on WSJ against a few minutes for ASG, and it overfits when bootstrapped from late-stage models (Collobert et al.). It is complementary rather than a substitute. We treat its reported numbers as an accuracy anchor and do not re-implement it.

Proposed Experiments

The first decisive check is the in-distribution rematch. All controllers and both static baselines are calibrated on clean LibriSpeech development data and evaluated on clean test data with both decoders. We report WER-versus-expansions Pareto curves over three seeds. The prediction is that the two-knob baseline lies within seed noise of the best dynamic controller. If confidence-guided pruning instead retains a speedup at matched WER anywhere near the published 14x-versus-5x gap, the "weak baseline" hypothesis is wrong.

The second check is transfer under shift. Constants calibrated on clean LibriSpeech are applied unchanged to the seeded babble conditions, to the prosodic perturbations, and cross-corpus to WSJ and TIMIT. We measure both average cost and 95th-percentile per-utterance cost. The prediction is that open-loop prior normalization keeps tail cost flat, as originally reported, while sigmoid constants fit on clean data either over-prune or blow up. Matched-calibration runs quantify how much of each method's advantage disappears without them.

The third check is reproducibility of search trajectories. Identical configurations run on two GPU types and on CPU, with deterministic flags set. DeepDIVA found such flags unreliable, so we also verify bitwise identity of the acoustic scores. Divergence is measured in three ways: the fraction of frames whose width decision differs, the variance of expansions per utterance, and output transcript disagreement. The prediction is that the closed-loop regulator shows larger divergence than open-loop controllers and static beams for the same score perturbation. We confirm causation by injecting controlled score noise of known magnitude on a single machine.

The released artifacts are the interface, the four controllers with documented deviations, the degradation seeds, and the full run provenance. Any future dynamic pruning paper could then report results against the same two-knob baseline on the same regenerable conditions.