Counting Correlated Siblings Once in Beam-Search Training

Many structured predictors, such as parsers, taggers and translators, are trained with early update: the model runs beam search during training (keeping only the top-$K$ partial outputs at each step), and the moment the correct partial output falls out of the beam, search stops and the model is pushed to score the correct prefix above the survivors. The standard losses treat every survivor in the beam as a separate rival. In practice beams are crowded with siblings, meaning near-identical continuations of one parent hypothesis that differ by a single token. When five siblings of one wrong idea fill the beam, a globally normalized loss counts that wrong idea five times. The gradient then hammers one mistake and barely touches the other, genuinely different competitors.

Game-tree search ran into the same error decades ago. Treating correlated sibling branches as independent lotteries overestimates how much evidence they carry, and correcting for sibling correlation measurably improves play. We propose to carry that correction into search-aware training. In the training loss, each cluster of beam candidates that share a recent ancestor counts as roughly one rival rather than many, and how strongly to discount is set by a measured sibling-correlation parameter. Before building anything, we test whether "crowding evictions", where the correct prefix is pushed out mainly by one cluster of siblings, are common and whether the updates they trigger are low-value.

Core Claim

In globally normalized beam training, as used for transition parsers by Globally Normalized Transition-Based Neural Networks, the loss is the gold score against a log-sum-exp over the beam. We claim that this partition term systematically over-weights sibling clusters. Replacing it with a cluster-discounted version should improve accuracy at a fixed beam size and training budget, and the gain should concentrate on update events where the beam is crowded. The discounted competitor mass is

$$\log Z_\gamma = \log \sum_{c} n_c^{-\gamma} \sum_{y \in c} \exp s(y).$$

Here $c$ ranges over clusters of beam candidates that share an ancestor within the last $L$ decoding steps, $n_c$ is the cluster size, $s(y)$ is the model score of candidate $y$, and $\gamma \in [0,1]$ is a sibling-correlation parameter. Setting $\gamma=0$ recovers the standard beam-CRF loss. Setting $\gamma=1$ makes each cluster contribute roughly its average mass, so near-duplicates count about once.

This mirrors the role of the correlation parameter in On Optimal Game Tree Propagation for Imperfect Players. That paper modified minimax backup so that sibling branches representing one strategic idea are not counted as independent coin flips. The independent product rule lost most of its Kalah games, while the correlated rule beat standard minimax. Clusters are read directly off the search tree, so the method needs no string kernel and no joint transition model. This matters because exact coupled-sibling models like An Efficient Solution to Hidden Markov Models on Trees With Coupled Branches scale as $N^{n+1}$ in the branching factor, which is hopeless when the branching factor is a vocabulary.

Relation to Prior Work

Two lines of decoding work motivate the proposal by documenting sibling crowding, but they act only at test time. Diverse Beam Search splits the beam into groups with a dissimilarity penalty. Determinantal Beam Search selects beam members by maximizing a determinant over a similarity kernel, and it explicitly names training-time use as open future work. Both change which candidates survive in a fixed, maximum-likelihood-trained model. We instead change how surviving candidates are weighted in the training gradient, and we leave the search itself unchanged in the main condition.

Three works supply the training machinery we modify. Incremental Parsing with the Perceptron Algorithm introduced early update. Learning as search optimization generalized it and showed that training and test beam settings must match. That consistency requirement constrains our design: any change to the training search must also be applied at test. Sequence-to-Sequence Learning as Beam-Search Optimization carried early update into neural sequence models with a margin loss against the single best competitor.

A max-based margin is blind to duplicates in the loss itself, so our discount applies to the summed, globally normalized losses of Andor et al. and An Empirical Investigation of Global and Local Normalization. For margin losses, sibling correlation can matter only through when the update fires. Max-Violation Perceptron and Forced Decoding observed that the first eviction is often a near-tie. We test whether those near-tie evictions are disproportionately crowding evictions, which would give a structural explanation for its empirical finding.

Coherent Inference on Optimal Play in Game Trees models values as a random walk down the tree, so that siblings' values are correlated by construction. This supports reading correlation from tree distance. Properties of Forward Pruning shows that pruning errors on different branch types are not interchangeable. That result motivates our refusal to treat all evictions alike.

Research Program

The first stage is diagnostic and could falsify the premise. We instrument standard early-update training of an Andor-style parser and a recurrent tagger. At every update event we record the crowding of the beam: the share of beam mass held by the largest cluster sharing an ancestor within $L$ steps. We also estimate sibling correlation directly, by measuring how often siblings with a common recent ancestor have the same downstream outcome, that is, whether they are correct or incorrect at the next $L$ decisions. The empirical correlation gives a data-driven prior for $\gamma$, in the spirit of how Baum's propagation formula fit its correlation parameter. To measure update value, we take each update's effect on dev loss from short checkpoint replays, then relate that value to crowding. If crowded updates are rare, or are no less useful than uncrowded ones, the project stops here and reports a negative result.

The second stage implements the discounted loss, sweeps $L$ and $\gamma$ under a fixed tuning budget, and compares a fixed $\gamma$ against the $\gamma$ estimated from the diagnostic. The third stage asks whether the discount interacts with how search is run. We cross the loss variant with a training-and-test search that caps the number of children per parent. The cap respects the beam-consistency principle from LaSO.

Baselines

The naive reference point is a locally normalized model trained with cross-entropy and decoded with the same beam. This shows how much any search-aware training buys on each task.

The strongest existing method is standard globally normalized beam training with early update, as in Globally Normalized Transition-Based Neural Networks. That paper reports 94.61% unlabeled attachment score (UAS) on WSJ dependency parsing. On CCG supertagging with a unidirectional encoder, An Empirical Investigation of Global and Local Normalization reports 85.50% accuracy for its search-aware global model versus 83.35% for the local one. It is the strongest competitor because it is exactly our method with $\gamma=0$, so any difference isolates the discount. We reimplement it in our own codebase with identical encoder, features, beam width, warm-up schedule, number of epochs and hyperparameter trials. The published numbers serve only as sanity anchors that our reimplementation should approach. Beating it means a gain over the reimplementation that is consistent across at least three seeds and larger than seed variance, with the gain larger on high-crowding sentences.

Max-violation updates (Max-Violation Perceptron and Forced Decoding) and BSO (Sequence-to-Sequence Learning as Beam-Search Optimization) are run as alternative update rules under the same budget. They test whether choosing a better update step already captures what the discount provides.

The key ablation replaces tree-distance clusters with random clusters of matched sizes. If random grouping helps equally, the gain comes from generic re-weighting of the partition term rather than from sibling structure.

Why not just…?

Why not just enlarge the beam? Larger beams fill with more siblings rather than new alternatives, as reported in both Diverse Beam Search and Determinantal Beam Search. Fast and Accurate Neural Word Segmentation for Chinese found that beam increases gave negligible F1 gains, and BSO training is already about 3.3 times slower than teacher forcing. We nonetheless include a doubled-beam standard model. If it matches the discounted loss at the original beam, our method's value reduces to a compute saving, and we will report it that way.

Why not just use diverse or determinantal beam search at test time? These methods change decoding for a model whose scores were trained under a different search. LaSO's consistency result predicts that this mismatch is costly. We run both on top of the strongest baseline. If test-time diversity alone closes the gap, the training-side change is unnecessary.

Why not just cap the number of children per parent during training and testing? This is the real threat, because a cap prevents crowding directly and is trivial to implement. The two-by-two design (loss discount on or off, crossed with cap on or off, with the cap applied at both training and test) settles the question. If the cap alone matches the full combination, we will drop the loss in favor of the cap and report that. We expect the methods to differ because a cap discards possibly correct siblings, whereas the discount keeps them and only re-weights the gradient. The cap should therefore cost accuracy where the gold continuation is one of several close siblings, and we will measure this separately.

Why not just deduplicate identical prefixes? Exact duplicates are rare. The crowding we target is near-duplicates that differ by one token, which deduplication does not touch. This is checked by the $L=0$ setting of the sweep, which is equivalent to exact matching.

Proposed Experiments

We use four benchmarks from the file. The first is PTB WSJ dependency parsing (sections 2–21 for training, 24 for development, 23 for test, scored by UAS). The second is CCG supertagging with a unidirectional encoder, where search matters most according to Goyal et al. The third is CoNLL 2000 chunking, where LaSO reports an F-score of 94.4. The fourth is IWSLT 2014 German–English translation as a large-branching stress test. There BSO reports 25.48 BLEU and the continuous-relaxation global model 29.27 BLEU, in different setups that we will not compare directly.

The decisive checks are three. First, the diagnostic must show that crowding evictions are frequent and that their updates are less useful. Second, the discount must beat the $\gamma=0$ reimplementation, with the gain concentrated on high-crowding sentences, while random clusters must not. Third, the discount must retain an advantage over the per-parent cap when both are compared fairly.

As a secondary test of the max-violation connection, we check whether near-tie first evictions are mostly crowding evictions. A null result on any of the three decisive checks will be reported as such.