Training Streaming Attention Against Its Worst Delays

Streaming speech recognizers and simultaneous translators listen and speak at the same time. At every moment they decide whether to wait for more audio or to emit the next word. When this decision is made by several attention heads, each looking at different cues, the whole model has to wait for the most hesitant head. That head is the "straggler." Existing fixes train the heads to agree on average and measure delay in audio frames, as if computation cost nothing. Yet users judge these systems by their worst moments: a translator that is usually two seconds behind but sometimes freezes for thirty seconds is unusable. We propose to train streaming multi-head models directly against the tail of their real, wall-clock delay distribution. The first ingredient is the exact probability distribution of the slowest head. The second is a differentiable simulation of how stalls turn into computation backlogs on real hardware. The third is a risk objective that penalizes the average of the worst few percent of delays rather than the mean.

The core observation is that head straggling and compute backlog compound. When one head stalls, output tokens pile up. Once it finally fires, those tokens must be decoded one after another, so the last token in the burst waits for its algorithmic lag plus the decoding time of everything ahead of it. Metrics that count frames miss this amplification entirely. Mean-based training losses barely see it, because it happens on rare utterances. Our claim is that a loss built from the three ingredients above reduces 95th/99th-percentile and maximum wall-clock delay, and cuts the rate of "over-waiting" (falling back to translating only at the end of the input). It should do so at matched mean latency and matched quality, and it should beat both frame-based tail penalties and mean compute-aware penalties.

What the literature establishes and leaves open

Three lines of work motivate the proposal.

The first is multi-head synchronization. Monotonic Multihead Attention (MMA) lets each head choose its own reading position. It keeps heads together with a variance penalty across heads plus an average-latency loss. Mutually-Constrained Monotonic Multihead Attention (MCMMA) builds a waiting threshold into training so that heads catch up to each other, but it is sensitive to that threshold. Head-synchronous decoding (HS-DACS) pools halting confidence across heads and caps waiting at a fixed maximum look-ahead. Cumulative Attention goes further and replaces per-head halting with a single layer-level halting network. Two other papers belong here as well: head-synchronous beam search, which uses a hard inference threshold, and SR-MLT, which deliberately averages over mini-batches to suppress outliers. Every paper in this line measures frames or steps and reports means.

The second line is computation-aware latency, which constrains how delay must be measured. CA* shows that earlier compute-aware metrics wrongly assume the hardware sits idle while audio arrives. It fixes this with a buffer that grows only when computation outpaces incoming speech. Earlier compute-aware formulations sum audio duration and inference time naively, as in SimulMT to SimulST. The survey How "Real" is Your Real-Time Simultaneous Speech-to-Text Translation System? argues that this distinction decides whether a system is deployable. The closest method to ours is ANCAT, which regularizes compute-induced user-perceived latency during training. However, ANCAT acts on per-layer lookahead in an encoder, not on per-head read/write decisions, and it penalizes expected backlog, not its tail.

The third line is tail risk. Going Beyond Your Expectations in Latency Metrics documents heavy right tails in simultaneous speech translation and proposes percentiles, Q-Q plots, and an over-wait metric. Its examples include two systems with the same 2.4-second mean but maximum delays of 31 versus 10 seconds, and top systems that wait for the full input on nearly half of utterances longer than 5 seconds. That paper diagnoses the problem but offers no training remedy. It also analyzes frame-based lag, not CA*. For the risk machinery we reuse Conditional Value-at-Risk (CVaR), the expected loss in the worst $(1-\alpha)$ fraction of outcomes. Relevant prior work includes CVaR policy-gradient methods and CVaR concentration bounds. This supplies the method, not the motivation.

Core Claim

Straggler-induced tail delay in multi-head streaming models can be optimized directly and differentiably, and doing so reduces worst-case wall-clock latency more than any of the following:

  • penalizing head variance,
  • penalizing mean compute-aware delay,
  • clipping waits at inference.

The novelty lies in three specific pieces. The first is to model the layer's halting time as the exact maximum over heads rather than an average. The second is to push that distribution through a smoothed version of the CA* buffer. The third is to apply CVaR to the result.

Research Program

The slowest head. If head $h$ at output step $i$ has halted by source position $j$ with probability $F_{h,i}(j)$, and heads decide independently given their inputs, then the layer's halting CDF is exactly

$$ F_i^{\max}(j) = \prod_{h=1}^{H} F_{h,i}(j). $$

This expression is differentiable and cheap to compute from the halting probabilities MMA already produces. MMA's losses average the heads' expected delays and penalize their variance. The product above instead targets the quantity that actually gates decoding. For collective-halting models such as Cumulative Attention, where one network makes the halting decision, $F_i^{\max}$ is simply that network's halting CDF. The rest of the pipeline applies unchanged.

From stalls to backlog. We build a soft version of the CA* accounting. Let $d_i$ be the expected algorithmic emission time of token $i$ under $F_i^{\max}$, measured in seconds of audio. Let $c$ be the per-token decoding cost measured on the target device. Let $\Delta_i$ be the audio time that arrives between tokens $i-1$ and $i$. The computation buffer then evolves as

$$ \beta_i = \mathrm{softplus}_\tau\big(\beta_{i-1} + c - \Delta_i\big), \qquad D_i = d_i + \beta_i, $$

where $\mathrm{softplus}_\tau$ is a temperature-$\tau$ smooth approximation of $\max(0,\cdot)$ and $D_i$ is the simulated wall-clock delay of token $i$. A burst of tokens released by a stall has small $\Delta_i$, so the buffer grows. This is exactly the amplification that frame-based losses cannot see. Because $c$ depends on the hardware, we sample $c$ during training from a range spanning slow CPU to fast GPU. This addresses the hardware-dependency limitation noted for ANCAT-style objectives.

Penalizing the tail. We use the Rockafellar–Uryasev form of CVaR over all tokens in a mini-batch:

$$ \mathrm{CVaR}_\alpha(D) = \min_{t}\; t + \frac{1}{1-\alpha}\,\mathbb{E}\big[(D_i - t)_+\big]. $$

Here $t$ is a learned scalar threshold that, at the optimum, equals the $\alpha$-quantile of $D$. We use $\alpha \in \{0.9, 0.95\}$. We add a second, utterance-level CVaR on each utterance's maximum $D_i$, which directly targets over-wait. The training loss is cross-entropy plus a weighted sum of these terms. Mean latency is left to the existing average-latency term, which lets us compare systems at matched means.

Diagnostic before method. We first measure how much of the existing tail is actually caused by stragglers. For baseline models, we log per-head halting positions and real wall-clock timings, then attribute every token above the 95th percentile of true CA* delay to one of three causes. Head divergence means the gap between the latest head and the median head exceeds the stall length. Collective hesitation means all heads wait together. Pure compute backlog means no stall occurred, yet the buffer is positive. If divergence explains only a small share of the tail, the head-level component of the proposal is unnecessary. In that case we would report this finding and focus the work on the backlog-plus-CVaR part applied to collective-halting models.

Baselines

The naive reference point is MMA with infinite lookback, trained with its own average-latency and head-variance losses and no further changes. This is the "do nothing" option. Beating it at matched mean delay shows only that the problem is real. For the speech-translation setting we adapt it following SimulMT to SimulST.

The strongest synchronization competitors are Cumulative Attention and MCMMA, evaluated on AISHELL-1 and LibriSpeech where their numbers are reported. Cumulative Attention reports 51.8 frames of latency on AISHELL-1, against 53.4 for HS-DACS. MCMMA reports 6.2% character error rate (CER) on AISHELL-1 and 24.8% word error rate on LibriSpeech test-other. HS-DACS reports 6.8% CER on AISHELL-1. For percentiles, maximum delay, or CA* of any of these models, we found no reported result on Lacuna; producing those numbers is itself part of the contribution. We reimplement all of them in one codebase with the same encoder, data, training steps, and hyperparameter-search budget. We tune each method's own latency knob (MCMMA's threshold, HS-DACS's maximum look-ahead, Cumulative Attention's latency weight) to trace a full quality–latency curve.

The strongest compute-aware competitor is an ANCAT-style objective: the same simulated $D_i$, but penalized by its mean instead of its CVaR. This baseline isolates the risk objective. A second ablation applies CVaR to the frame delay $d_i$ with the buffer removed, which isolates the compute simulation. A third ablation replaces the product-of-CDFs maximum with MMA's head-averaged expected delay, which isolates the straggler modeling.

The proposal wins if, at mean CA* delay within 5% of a baseline's, it lowers the 99th-percentile and maximum delay and the over-wait rate. At the same time, quality must stay within 0.5 BLEU for translation or 0.2 absolute CER/WER for recognition. The margin must hold across three seeds.

Why not just…?

Why not just clip the tail with a hard maximum wait at inference? This is the cheapest option, and we treat it as a real competitor. We run HS-DACS-style caps and head-synchronous thresholds at several settings on every baseline. The evidence against caps as a complete answer is indirect. MCMMA reports 24.8% versus 27.0% WER against HeadDrop, an inference-time patch, attributing the gap to train–test mismatch. Cumulative Attention reaches lower latency without any cap. A cap bounds the frame delay but does nothing about backlog bursts once tokens are released, so the CA tail may survive clipping. Our curves of quality against 99th-percentile CA delay will show whether trained risk-awareness dominates capping. If it does not, capping wins and we will say so.

Why not just use collective halting, which removes stragglers by construction? This is the most serious threat. If Cumulative Attention already has thin CA* tails, our head-level story fails. The diagnostic study answers this directly by measuring Cumulative Attention's tail and attributing its causes. The method is also designed to apply on top of collective halting: its single halting CDF feeds the same buffer-plus-CVaR loss. If the gains appear only there, the contribution narrows to compute-aware tail training, and we will report it that way.

Why not just turn up the average-latency weight? A stronger mean penalty shifts the whole delay distribution left, and this may shrink the tail as a side effect. We therefore compare at matched mean delay along each baseline's full sweep. The claim is about the shape of the distribution, which we check with Q-Q plots as in Going Beyond Your Expectations. If sweeping the mean weight produces the same percentile curve, CVaR adds nothing.

Why not just use one head or a fixed wait-k policy? Both options remove straggling, but at a quality cost. MMA attributes its gains to multiple heads. DiG-SST reports adaptive policies beating fixed ones by 2 to over 3 BLEU on MuST-C English–German. We include a single-head model and wait-k as reference points on the quality–tail plane.

Proposed Experiments

The primary setting is simultaneous speech translation on MuST-C English–German. We also run the long-form synthetic streams of up to 100 seconds used by CA*, because stalls and backlogs compound on long inputs. The secondary setting is streaming recognition on AISHELL-1 and LibriSpeech, where the synchronization baselines have published numbers.

We report quality as BLEU, WER, or CER. We report mean latency with the following metrics:

  • Length-Adaptive Average Lagging (LAAL) and Average Lagging (AL);
  • mean CA*, measured with real timing on two devices (a data-center GPU and a CPU).

We report the tail with the 90th, 95th, and 99th percentiles and the maximum of per-token and per-utterance CA* delay, plus the over-wait rate.

The experiment has three decisive checks. The first is the straggler attribution study described above, which determines whether head-level modeling matters at all. The second is the matched-mean comparison against Cumulative Attention, MCMMA, and the mean-compute baseline: the proposal must lower the 99th-percentile CA* delay and the over-wait rate without a quality loss. The third is the cross-hardware test. We train with sampled decoding cost and test on the slower device; the tail advantage over the frame-only CVaR ablation should grow as hardware headroom shrinks. That growth is the signature of the stall-to-backlog amplification this proposal is built on.