Fast parsers that reason about rich structure usually work in passes. A cheap first pass throws away most candidate word-to-word links, and an expensive second pass picks the best tree from what survives. Today the first pass is tuned to keep a fixed fraction of correct links, and every correct link counts the same. That is the wrong target. Some mistakes stay local: misattaching a prepositional phrase costs one link. Others, such as losing the sentence root or a punctuation anchor, push the whole tree into the wrong shape and cost many links. We propose to train and calibrate the pruning pass against the damage a pruned link would cause downstream, not against how many correct links it keeps. The calibration comes with a finite-sample guarantee: the expected damage from pruning stays below a level the user chooses.
The opportunity exists because two literatures have not met. Coarse-to-fine parsers such as Vine Pruning for Efficient Multi-Pass Dependency Parsing remove about 86% of candidate arcs while keeping more than 98% of correct ones, using a "filter loss" that charges every pruned gold arc equally. Meanwhile, Identifying Cascading Errors using Constraints in Dependency Parsing showed that errors are strongly unequal. Root errors displace structure by more than 9 words on average, and fixing punctuation alone recovered up to 1.8 points of attachment score, almost all of it cascaded gain on other arcs. Pruning is exactly where cascades start, because a pruned arc can never be recovered. Yet no work in our file measures cascades caused by pruning, or uses them to decide what to prune.
Core Claim
At a matched pruning rate, or at matched parsing speed, a coarse pass that is trained and thresholded to minimize predicted downstream damage will give higher final attachment accuracy and exact-match rate than a recall-calibrated pass. Its realized damage will also respect a user-set bound on held-out data. We state the claim for neural second-order dependency parsing, where pruning still matters. Revisiting Higher-Order Dependency Parsers found that second-order scoring still helps on long sentences and long dependencies even with a BERT encoder (a large pretrained language model that supplies context-aware word vectors). It also found that decoding drops from about 1600 to about 460 tokens per second.
Research Program
The program has three pieces, built on a second-order parser with a BERT encoder and dual-decomposition decoding, following Fonseca and Martins. Its first-order arc scores serve as the coarse pass.
Measuring pruning cascades. The first piece measures cascades caused by pruning. Ng and Curran forced gold arcs into single-pass parsers. We do the converse inside the cascade: on a calibration split, we remove one gold arc from the pruned candidate set, rerun the fine pass, and count how many other arcs become wrong. This yields a per-arc counterfactual damage $d(a)$ for gold arc $a$. It is expensive, but it runs offline and only once. It also gives the first map of which arc types act as structural anchors under pruning rather than under unconstrained decoding.
Predicting damage. The second piece is a small damage predictor $\hat d(a)$. It is a regression head on the encoder's arc representation, trained on these counterfactuals, so that damage can be estimated at test time without rerunning anything. The coarse pass is then retrained with a damage-weighted filter loss. Pruning gold arc $a$ costs $\hat d(a)$ instead of 1, which extends Rush and Petrov's filter loss rather than replacing it.
Calibrating the threshold. The third piece sets the pruning threshold with a guarantee. Let $\lambda$ be the threshold on coarse arc probability, and let $P_\lambda(x)$ be the set of gold arcs pruned in sentence $x$. We define the sentence loss
$$L_\lambda(x) = \min\Big(1,\ \tfrac{1}{B}\sum_{a \in P_\lambda(x)} \hat d(a)\Big),$$
where $B$ is a normalizing damage budget. This loss can only grow as $\lambda$ rises, because a higher threshold prunes a superset of arcs. We pick the largest $\lambda$ whose calibration-set average loss, after the standard finite-sample correction for monotone bounded losses, stays below a target $\alpha$. This guarantees $\mathbb{E}[L_\lambda] \le \alpha$ on exchangeable test data.
This extends Conformal Prediction in Hierarchical Classification with Constrained Representation Complexity in two ways. That paper guarantees coverage of label sets in a taxonomy. We control a structured, damage-weighted risk over the candidate arc sets of a parse chart. Plain coverage of gold arcs falls out as the special case $\hat d \equiv 1$.
One caveat matters. The guarantee covers predicted damage, not actual fine-pass errors, since the actual count need not be monotone in $\lambda$. We therefore report the realized counterfactual damage on test data separately, and treat the agreement between the two as an empirical question.
Relation to Prior Work
Hard-threshold cascades (Multilevel Coarse-to-Fine PCFG Parsing, with a tenfold reduction in work and no F-measure loss on the Penn Treebank; and Efficient Third-Order Dependency Parsers, which prunes with a first-order model) supply the setting. Both tune a single uncalibrated threshold on development data. Vine pruning is the closest method. Its outer-arc deferral protects long arcs by length alone, and our damage weights are a learned generalization of that idea to any arc type.
Stacking Dependency Parsers and Stacked Hierarchical Labeling attack cascades from the other side. They train later stages on held-out earlier-stage outputs so the later stages learn to distrust them. That helps when the earlier signal is a soft feature. It cannot help when the earlier stage deletes the option outright, which is why we act at the pruning step.
The cascading-error literature beyond parsing, such as the hierarchical retrieval failures in Brodley et al., motivates the problem. It offers no mechanism for chart parsing.
Baselines
The naive reference points bracket the problem. The first is the first-order BERT parser with no second pass, which is fastest. The second is the unpruned exact second-order parser, which is the accuracy ceiling at roughly 460 tokens per second as reported by Revisiting Higher-Order Dependency Parsers. Every pruned system should land between these two, and the question is where on the speed–accuracy curve.
The strongest existing method is vine-style recall-calibrated pruning. It uses the uniform filter loss of Vine Pruning for Efficient Multi-Pass Dependency Parsing, with its threshold tuned on development data to hit a target gold-arc retention. Its reported figures are about 86% of arcs eliminated with more than 98% of correct arcs kept on the Penn Treebank. For the full non-neural third-order system on that treebank, the reported figure is 93.04% unlabeled attachment score (UAS, the share of words given the correct head) from Efficient Third-Order Dependency Parsers. We found no reported result on Lacuna for a neural pruned second-order parser on UD 2.3 or CoNLL-X, so we will reimplement this baseline on our encoder.
We also include split-conformal pruning with uniform weights. This is the obvious transfer of Mortier et al. and isolates the calibration step from the damage weighting.
Fairness is enforced in three ways. All pruned systems share the encoder, the fine pass, the training data and the hyperparameter search budget. The damage predictor's offline counterfactual compute is reported separately. Comparisons are made at matched pruning ratio and at matched tokens per second.
Two ablations isolate the key ingredient. In one, the learned $\hat d$ is replaced by a random permutation of its values, which keeps the same weight distribution but destroys the link between weight and arc. In the other, $\hat d$ is replaced by the true counterfactual $d$ on test data, which gives an upper bound.
Beating the strongest baseline means two things. At equal pruning rate, the method must show a statistically significant gain in UAS and labeled attachment score (LAS, which also requires the correct relation label), or in exact sentence match, across the UD treebanks. Its gain should be concentrated in long sentences. The permuted-weight ablation must show no such gain.
Why not just…?
Why not just keep more arcs with a looser uniform threshold? Loosening the threshold buys accuracy with speed, and that is precisely the curve we compare on. The claim is that damage weighting moves the curve itself, not just the point on it. Plotting both systems' accuracy against tokens per second settles this directly. If the curves coincide, the idea fails.
Why not just hand-protect root and punctuation arcs, as Ng and Curran's findings suggest? This is the real threat. A per-category rule that never prunes candidate root arcs or punctuation-anchored arcs is cheap, and it could capture most of the benefit on English. We include it as a baseline with per-category thresholds tuned under the same budget. The learned predictor earns its place only if it beats this rule on morphologically rich or non-projective treebanks, such as the Prague Dependency Treebank and the German and Czech UD data, where anchors are less tied to fixed categories. If it does not, we report that the hand rule suffices.
Why not just drop the cascade and use a flat BERT first-order parser? Fonseca and Martins report that second-order scoring still gives consistent gains on long sentences and long dependencies, so there is accuracy left on the table. The flat parser is in our baselines. If pruned second-order systems cannot beat it at its own speed, the whole regime is moot, and we will say so.
Why not just train the fine pass to be robust, as stacking does? A fine pass trained on pruned charts can learn to lean less on unreliable evidence, but it cannot choose an arc that was deleted. We test this by also training every fine pass on pruned charts from held-out folds and checking whether the gap persists.
Proposed Experiments
We will use PTB with the standard splits (sections 2–21 train, 22 dev, 23 test), the six CoNLL-X languages used by vine pruning, the Prague Dependency Treebank, and the 19 UD 2.3 treebanks of Fonseca and Martins. Calibration data is carved from the training set so that development data stays clean for threshold-free model selection. We report UAS, LAS, exact match, tokens per second, pruning ratio, the realized counterfactual damage on test, and the empirical rate at which the risk bound is violated across resampled calibration splits.
Three checks are decisive. First, the realized test risk must stay at or below $\alpha$ across $\alpha$ values, and the realized counterfactual damage must track the predicted damage. If it does not, the guarantee is about the wrong quantity. Second, at matched speed, the cascade-calibrated system must beat both recall-calibrated pruning and the category heuristic on the long-sentence bins. Third, the cascade map from the first piece must show stable, predictable damage across languages. If damage is unpredictable from arc representations, the predictor and everything built on it is unjustified, and that negative result is itself worth reporting.
References
- Vine Pruning for Efficient Multi-Pass Dependency Parsing
- Identifying Cascading Errors using Constraints in Dependency Parsing
- Revisiting Higher-Order Dependency Parsers
- Conformal Prediction in Hierarchical Classification with Constrained Representation Complexity
- Multilevel Coarse-to-Fine PCFG Parsing
- Efficient Third-Order Dependency Parsers
- Stacking Dependency Parsers
- Stacked Hierarchical Labeling
- Content-Based Retrieval from Medical Image Databases: A Synergy of Human Interaction, Machine Learning and Computer Vision