Lattice-Scoped Gradient Sync for Second-Pass Rescorers

Many search systems work in two passes. A fast, cheap model first proposes a short list of plausible outputs, such as candidate transcripts, next words, or documents. A larger model then rescores only that list. This note asks what the short list implies for training the large model on many machines. When the rescorer is trained only to discriminate among first-pass candidates, the gradient of its output layer is exactly zero for every vocabulary row that never appears in a candidate list. That layer is the huge matrix holding one vector per word or document. Shipping the full dense matrix gradient across the network at every step therefore wastes bandwidth. The first pass already tells each worker, before the backward pass begins, which rows it will touch. We propose to synchronize only those rows under a fixed per-step budget, so that standard ring all-reduce still applies. Rows that overflow the budget are deferred to a later step.

Deferral makes some updates stale: they were computed against older parameters. Here the existing staleness corrections go wrong. They measure staleness globally or per layer, as how far the whole model has moved since the gradient was computed. The rows most often deferred belong to rare tokens: proper nouns, domain jargon, rarely retrieved documents. These are exactly the items behind the vocabulary-mismatch problem. Their own vectors have barely moved, yet a global measure that is dominated by fast-moving common rows would shrink their updates toward nothing. We therefore measure staleness per row. The claim is that this combination, lattice-scoped budgeted synchronization plus per-row staleness correction, cuts output-layer communication substantially while protecting accuracy on rare items, where global corrections hurt.

Core Claim

The proposal rests on three pieces of prior work, each in a different role.

Fast Parallel Training of Neural Language Models supplies the motivation and the closest method. It reports that output-softmax gradients can take up to 50% of multi-GPU training time. It reduces this by sending only a row subset: words in the batch, a fixed top slice of frequent words, and a uniform random sample of the rest. It reports a 2.1x speedup over dense asynchronous SGD with no perplexity increase. That subset is a heuristic set by corpus frequency, and the paper finds that dropping the frequent slice causes divergence. Our subset is instead set by the first-pass candidates. For a candidate-normalized rescoring loss it is exact, because no other row receives gradient.

Gap-Aware Mitigation of Gradient Staleness supplies the staleness method. It replaces step-count penalties with the parameter distance travelled since the read, and reports nearly two orders of magnitude better perplexity than step-count penalization on WikiText-103. It also constrains us. The authors note that over-penalizing small staleness slows learning, which implies a noise floor. They evaluated only dense models in which parameters drift roughly together.

Two-Pass End-to-End Speech Recognition shows why the rescorer must be trained on candidates the first pass generates as training proceeds, not on fixed offline lists. Its gains came from joint fine-tuning and minimum word error rate training on dynamically produced top hypotheses. This is why the active row set changes every step and cannot be fixed in advance.

The correction rule follows. A deferred gradient $g_v$ for row $v$ was computed when that row's vector was $e_v^{\text{read}}$, and the row currently holds $e_v^{\text{now}}$. We apply

$$\tilde g_v = \frac{g_v}{\max(1, G_v)}, \qquad G_v = \frac{\|e_v^{\text{now}} - e_v^{\text{read}}\|}{\bar\Delta},$$

where $\bar\Delta$ is a running average of per-step row movement. The $\max(1,\cdot)$ term is our response to the noise floor reported by Gap-Aware: rows that have not moved are left unpenalized. A rare-token row deferred for 50 steps that nobody else touched has $G_v \approx 0$, so its update passes through intact. A layer-wise Gap would divide the same update by the drift of the whole embedding table.

Research Program

Each data-parallel worker runs the first-pass model on its minibatch and collects the union of candidate tokens, or candidate document identifiers, plus the references. These row indices are exchanged with a cheap index all-gather. This can overlap with the rescorer's forward pass because the first pass finishes earlier.

The global union is ranked by a priority score: how many workers touched the row, multiplied by the deferral age. The top $B$ rows go through a fixed-shape ring all-reduce. The remaining rows accumulate locally in a deferral buffer and are flushed later, either when they win budget or when they reach a maximum age. On flush, the per-row correction above is applied.

The dense backbone is synchronized normally, so the method affects only the output layer. For each output row we track one read snapshot norm and one movement accumulator. This keeps the memory cost of parameter-wise tracking, which the Gap-Aware line flags as an overhead, at $O(|V|)$ scalars rather than $O(|V|d)$, where $d$ is the embedding width.

Beyond building the system, the analysis has two parts. The first measures how large the union of candidate rows is as worker count and first-pass beam width grow, since this decides whether a budget is needed at all. The second measures the distribution of deferral age against token frequency. This connects to the finding of Giladi et al. that stale updates destabilize sharp minima, and to the report in One-Step Gradient Delay is Not a Barrier that one-step delay is harmless but larger delays need mitigation. It tells us whether deferral stays in the harmless regime for frequent rows and enters the risky regime only for the rare tail.

We use two testbeds whose data appear in the file. The first is word-level language-model rescoring on WikiText-103. Its word vocabulary makes the output layer the dominant communication cost, and Gap-Aware used this dataset. A small LM serves as first pass, proposing top-$k$ next-word candidates per position, and a Transformer rescorer is trained with a loss normalized over candidates plus the reference. Test perplexity is still measured with the full softmax, reported both overall and for rare words.

The second is passage rescoring on Natural Questions and MSMARCO, with atomic passage-identifier rows. The first pass is a retriever returning top-100 passages, and the rescorer scores the query against identifier embeddings. Here the output "vocabulary" is the corpus itself, and the long tail consists of passages that share few words with their queries, the gap documented by Yang et al..

Speech recognition is the natural home of two-pass decoding. The only speech data in the file is proprietary Google voice-search traffic, so we do not test ASR and make no ASR claims.

Baselines

The naive reference is synchronous data parallelism with a dense all-reduce of the full output-layer gradient, trained on the same candidate-normalized loss. It is exact and slow, and it fixes the target quality every other method must match within noise.

The strongest existing method on the communication question is the frequency-plus-random row sampling of Fast Parallel Training of Neural Language Models. The reported number to beat is a 2.1x speedup over dense asynchronous SGD with no perplexity increase, on four GTX 1080 GPUs on its own corpora. We reimplement it with its frequent and random slices tuned to the same per-step row budget $B$ as ours, on the same data, model and hardware. Beating it means equal or better full-softmax perplexity and rare-word perplexity at an equal or smaller communicated byte count, or a higher speedup at equal quality.

The strongest dense competitor is synchronous training with 4-bit compression in the style of SDP4Bit (Hao Feng et al.). It is run with the same tuning budget, and wall-clock includes compression compute.

On the staleness side, we keep our communication scheme fixed and compare four ways of handling deferred rows: no correction, step-count scaling as in Staleness-Aware Async-SGD, layer-wise Gap-Aware, and our per-row Gap. This ablation isolates the key ingredient. Per-row correction counts as a win if it improves rare-word perplexity, or Recall@1 on low-frequency passages, over layer-wise Gap without hurting the frequent head.

For the retrieval testbed we report, only as external context, the 50.6% Recall@1 on NQ of A Fresh Take on Stale Embeddings. That paper corrects stale cached document encodings within a single synchronous run, not stale gradients across machines. We also cite Hits@5 of 65.8 on NQ for MINDER. Neither is a like-for-like competitor, because model sizes and pipelines differ. Our real comparison is against dense synchronization of our own rescorer.

Why not just…?

Why not just send the exact union of candidate rows every step, with no budget and no deferral? This is the most serious threat. It is lossless and has no staleness at all. Its cost is that the union changes size every step, which pushes the implementation toward all-gather or point-to-point transfers. Saurabh Agarwal et al. report that such transfers scale poorly compared with ring all-reduce. Whether this matters depends on how fast the union grows with worker count, and that is an empirical question. Our scaling sweep measures it directly. If variable-size exact exchange matches budgeted all-reduce in wall-clock at every worker count we can run, the deferral and staleness component is unnecessary. We would then report the contribution as lattice-scoped exact sparsity alone.

Why not just keep frequency-plus-random sampling? It needs no first pass and has a published 2.1x speedup. Its subset, however, ignores which rare tokens are actually competing in the current batch. Under a candidate-normalized loss it both wastes bandwidth on frequent rows with zero gradient and misses rare competitor rows with nonzero gradient. The matched-budget comparison above settles this. The test that would expose a failure of our idea is rare-word perplexity: if frequency sampling matches us there, the first-pass mask buys nothing.

Why not just compress the dense gradient synchronously? Compression keeps ring all-reduce and avoids staleness. It still pays for the full $|V| \times d$ matrix, most of which is exactly zero here. Agarwal et al. also show that compression compute can cancel the network savings. We measure end-to-end wall-clock, including compression compute, at matched quality.

Why not just use layer-wise Gap-Aware, which already exists? If rare rows are rarely deferred, or if layer drift happens to be small, layer-wise and per-row correction coincide, and the extra $O(|V|)$ bookkeeping is wasted. The staleness ablation, broken down by frequency bucket, decides this.

Proposed Experiments

The decisive experiments are three.

The first is a scaling sweep on WikiText-103 over 8 to 64 workers under a throttled inter-node bandwidth. It reports the size of the candidate-row union, bytes sent per step, and wall-clock to a fixed perplexity for every baseline above. Lattice-scoped budgeted synchronization must reach dense-synchronization perplexity, and it must beat the frequency-sampling mask on rare-word perplexity at equal bytes. Otherwise the core claim fails.

The second is the staleness ablation, broken down by token-frequency decile and, on NQ and MSMARCO, by how often each passage appears in candidate lists. Our prediction is that layer-wise Gap underperforms per-row Gap only in the rare deciles. A uniform gap across all deciles would suggest the gain comes from something other than the mechanism we propose.

The third is a stress test that shrinks the budget $B$ until quality degrades. It locates the deferral age at which per-row correction stops helping. The result maps the boundary, which Gap-Aware left unresolved, between staleness the model tolerates and staleness that destroys learning, for sparse rows specifically.

On retrieval we report Recall@1, Hits@5 and Recall@100 for both the rescorer and the first pass. These show whether protecting rare-row updates actually narrows the lexical-gap failures that motivated this work.