Replaying Last Epoch's Beam: Exact Parallel Verification for Early-Update Training

Some sequence models are trained by running a beam search inside the training loop. Beam search keeps the top K partial outputs at each step. These "early-update" methods run that search and stop the moment the correct partial output is pushed out of the top K. They then update the model to prefer the correct prefix over whatever beat it. This fixes a real weakness of ordinary word-by-word training: the model learns from the mistakes it actually makes during search. The cost is speed. The search must advance one step at a time, and each step depends on the previous beam. Beam-search optimization for neural sequence models is reported to train about 3.3× slower than standard training (Sequence-to-Sequence Learning as Beam-Search Optimization).

Our observation is that consecutive epochs are highly redundant. When the same sentence comes back an epoch later, the model has changed only slightly, so its beam at most steps is probably the same as before. We propose to store each sentence's beam trajectory and treat it as a guess, or "draft," of the new search. We would then check all steps of that draft at once, in a single parallel forward pass. Serial search restarts only from the first step where the draft and the current model disagree. The idea comes from speculative execution in Markov chain Monte Carlo sampling, where idle processors evaluate predicted future states ahead of time. Here the prediction comes from the training history itself rather than from a separate approximate model. The check is exact, so the training updates are the same ones serial early-update training would produce. Only the wall-clock time changes.

Core Claim

Serial beam search inside training can be replaced by "draft, verify in parallel, repair." This yields exactly the same early updates, and max-violation updates, as the serial algorithm. Because training drift between epochs is small, the number of serial rounds per sentence should shrink sharply as training proceeds.

This reverses the pattern seen in speculative MCMC. There, speedups are near-linear during burn-in and drop to roughly $\log_2 J$ on $J$ cores once the chain is stationary, because accept/reject outcomes become coin flips (Accelerating MCMC via Parallel Predictive Prefetching). In our setting, drafts should be poor early, when parameters move fast, and accurate late, when parameters settle. Late training is also exactly when failures become rare and early updates stop saving compute by halting.

Relation to Prior Work

Four lines of work define the setting and supply the updates we must reproduce exactly:

All of these parallelize only across sentences, never within one sentence's search. Our proposal keeps their update rules unchanged and changes only how the beam trajectory is computed.

The mechanism borrows from two inference-side sources:

  • Angelino et al. contribute speculative evaluation of predicted future states, verified so that the result matches the serial algorithm exactly. - Dynamic-Width Speculative Beam Decoding contributes the practical tool: a draft forest of beams verified in one pass with a tree-shaped attention mask. It is used only at test time with a separate small draft model.

We differ from both in three ways. We apply speculation to training. Our draft is free, since it is stored from the previous epoch. And the quantity being verified is the first step where the correct prefix leaves the beam, which decides where the gradient is taken.

Research Program

We would build a Transformer-based beam-search-optimization trainer. For each training sentence it stores the previous epoch's beam trajectory: the $K$ prefixes at each step $t=1,\dots,T$, plus the step at which the correct prefix was pruned.

Verification pass. On revisit, one forward pass scores every one-token extension of every stored prefix at every step, using a forest attention mask. The pass then checks, step by step, whether the top K of those extensions under current parameters equals the stored beam at the next step. Let $a$ be the first step that fails.

Serial repair. From the true beam at step $a$, which verification has now computed exactly, we run ordinary serial beam search. We draft again only if the repaired search rejoins the stored trajectory, which is cheap to check.

Updates. The early update, or the max-violation update, is computed on the verified trajectory. By construction it equals the serial update up to floating-point summation order, and we will test that equality directly.

Cost model. If verification accepts on average $L$ steps per round, serial rounds per sentence fall from about $T$ to about $T/(L+1)$. Each round costs one wider forward pass. This is the standard speculative-execution accounting.

Analysis. We will measure how $L$ tracks the change in parameters between epochs. We will also study two variants:

  • A partial-refresh variant, which drafts from trajectories that are two or more epochs old, to trade memory for acceptance.
  • Adapting the verification depth to recent acceptance rates, in the spirit of dynamic beam width.

Baselines

Standard word-by-word training ("do nothing"). This is ordinary cross-entropy training where the model always sees the correct previous words, with sentences batched in parallel. It sets the speed ceiling and the accuracy floor. The accuracy gap it leaves is what makes early updates worth paying for: Wiseman and Rush report 23.87 BLEU for their standard baseline versus 25.48 for beam-search optimization on IWSLT 2014 De-En.

Serial beam-search optimization. This is the strongest competitor, implemented as the Wiseman and Rush method on the same Transformer. We run it with the same cross-entropy warm-up, the same beam curriculum, and the same batch size, and we give it an equal tuning budget. We will also tune its batching to make it as fast as possible, so the speed comparison is honest. Beating it means the same BLEU or UAS within noise, identical update steps on a fixed seed, and at least 1.5× lower wall-clock time per epoch after warm-up. The 1.5× bar is the low end of the speedup DSBD reports for the analogous inference problem.

Max-violation training. The same comparison is run with max-violation updates, where the full-length trajectory gives speculation the most serial work to remove.

Ablation 1: small draft model. Drafts come from a small separate model, as in DSBD, instead of the stored trajectory. This isolates whether the training history is the key ingredient.

Ablation 2: stale beams without verification. Stored beams from last epoch are used directly as negative examples, with no checking. This removes exactness entirely.

Why not just…?

Why not just train word by word with bigger batches? It is faster, and nothing in this proposal beats it on speed. However, the published gains of search-based training (25.48 vs 23.87 BLEU on IWSLT, and 34.5 vs 31.0 BLEU on Penn Treebank word ordering for the constrained variant, both from Wiseman and Rush) show it gives up accuracy. There is a risk: those numbers come from recurrent models, and the gap could be smaller for Transformers. We rerun both on the same Transformer. If the gap disappears, the speedup matters less, and we will report that.

Why not just rely on batching across sentences, which already fills the GPU? This is a real threat. With large batches, the GPU is busy doing arithmetic rather than waiting, and speculation adds extra arithmetic. Its advantage appears when batches are limited by the memory needed to hold K beams, which happens with long sequences and wide beams. We will measure throughput at matched memory across sequence lengths and beam widths. If serial beam-search optimization with the best batching matches us everywhere, the claim fails.

Why not just use last epoch's beams as negatives without verifying? This is the cheapest option and may train about as well, since slightly outdated negative examples are only a mild form of off-policy learning. The stale-beam ablation tests this directly. If it matches serial beam-search optimization in accuracy across all three tasks, exact verification is unnecessary. We would then redirect the project toward measuring how stale the negatives can be before training degrades. The concern that noisy candidate pools select outlier negatives (More Test-Time Compute Can Hurt) gives some reason to expect the ablation to drift, but that has to be measured, not assumed.

Proposed Experiments

Tasks and reference numbers. We run three tasks from the file.

  • IWSLT 2014 De-En. Reference: 25.48 BLEU with beam-search optimization, trained 3.3× slower than the standard baseline (Wiseman and Rush).
  • Penn Treebank word ordering. Reference: 34.5 BLEU for the constrained variant.
  • Penn Treebank dependency parsing. References: 91.57 UAS for sequence-to-sequence beam-search optimization, and 94.61 UAS for the globally normalized transition parser of Andor et al., which serves as a ceiling.

Metrics. We record task score, wall-clock time per epoch, serial rounds per sentence, mean accepted length $L$ per epoch, and GPU memory.

Exactness check. On a fixed seed, we compare every update step (the step location and the negative prefix chosen) against serial beam-search optimization. Any mismatch beyond floating-point effects falsifies the method.

Dynamics check. $L$ should rise over training and fall at learning-rate warm restarts. That pattern would confirm that speculation tracks the change in parameters between epochs.

Speed check. We need at least 1.5× wall-clock gain at matched memory in the long-sequence regime. We also report the regime where the gain disappears.