Reformulation and Equivalence of Bock's Algorithm for Exact Dependency Parsing

An executable reformulation of Bock’s 1971 minimum-cost arborescence algorithm, proved equivalent to the original procedure and to Chu–Liu/Edmonds, used as an exact decoder and training oracle in a biaffine dependency parser

arXiv 2026

Yuxi Wang1, Jungyeul Park2,*

1UBC, Canada 2KAIST, South Korea

*Corresponding author

Paper (arXiv) PDF

Abstract

Bock's algorithm provides a matrix-based alternative to Chu–Liu/Edmonds (CL/E) for exact dependency parsing. We present a reformulation that retains original node and arc identities through component labels, column adjustments, and star-and-bar transfers. In exact arithmetic, we prove operational equivalence to original Bock under matching scan and tie rules, and establish correspondence with corrected Tarjan under a prescribed component schedule. A separate analysis establishes optimal-value equivalence with Dozat-derived CL/E under the stated score and single-root conventions. We integrate reformulated Bock into a biaffine dependency parser and evaluate decoding and structured training on the Penn Treebank and Chinese Treebank. These results establish Bock as an alternative exact oracle for dependency parsing and structured training, while distinguishing equality of optimal values from identity of returned trees and training trajectories.

Keywords Bock's algorithm Minimum directed spanning tree Arborescence Chu-Liu/Edmonds (CL/E) Tarjan's algorithm Exact decoding Graph-based dependency parsing Biaffine parser Structured hinge loss PTB / CTB

Method

An arc-factored dependency parser scores every head–dependent arc i → j with S[i, j] and decodes the highest-scoring single-root tree. Bock's procedure (1971) solves the same problem as a minimum-cost rooted arborescence on the cost matrix C[i, j] = −S[i, j]. Unlike Chu–Liu/Edmonds, it never builds contracted graphs: it keeps the original matrix and node indices and represents contracted circuits by shared labels. The reformulation (Algorithm 1 in the paper) separates its interleaved Algol control flow into explicit phases:

  1. Candidate search. For the current column K and its active component H, pick the first arc entering H from outside that minimizes the adjusted cost C[i, j] − U1[j] (dependents scanned in increasing order, then heads).
  2. Column adjustment. Add that minimum to U1 for every processed column in H, so the chosen candidate has adjusted cost zero.
  3. Backward trace. Follow starred (provisional) predecessors from the candidate's head, collecting visited components in an explicit TRACE set (the original marks them by temporarily negating SPAN labels) and writing the candidate into empty bar entries.
  4. Contraction. If the trace returns to H, a circuit has formed: every vertex in TRACE receives the active label (the original assigns a fresh label) and the search repeats.
  5. Star-and-bar transfer. Otherwise install the candidate as a star; each displaced star is replaced using the barred arc reference stored at its dependent, until no star is displaced.

Worked example (from the paper). Nodes 0, 1, 2 with root 0 and arcs 0→1, 0→2, 1→2, 2→1 of costs 50, 60, 10, 20. At K = 1 the procedure stars 2→1; at K = 2 selecting 1→2 closes the circuit 1→2→1, which is contracted. The renewed search compares adjusted costs 50 − 20 = 30 (0→1) and 60 − 10 = 50 (0→2), selects 0→1, and the transfer yields the arborescence 0→1→2 of cost 50 + 10 = 60.

Formal results.

  • Faithfulness to original Bock: in exact arithmetic, with the same scan order and first-minimum tie rule, the reformulation returns the same predecessor array and objective value as the original Algol procedure (or both report infeasibility).
  • Theorem 1 (coupled Bock–Tarjan executions): under a prescribed component schedule and common original-arc tie order, Bock's starred arc set equals the branching returned by corrected Tarjan recovery at every completed column prefix, so the final arborescences coincide even when the optimum is not unique.
  • Theorem 2 (single-root parsing equivalence): the Dozat-derived CL/E used in Stanza (root reweighting) and Bock single-root inference (enumerating the sole root child) both solve the single-root parsing objective and attain the same optimal score.
  • Complexity: the reformulation runs in O(n3) time with O(n2) storage, matching the original Bock procedure and the Dozat-derived CL/E bound for rooted arborescences; the implemented single-root Bock procedure is O(n4) in the worst case.

Main Results

  • Identical decoding on identical scores. For the three PTB local cross-entropy models (one per seed), CL/E, original Bock, and reformulated Bock return identical heads, relation labels, and tree-score values on every development and test sentence, and hence identical UAS, LAS, and complete-match scores.
  • PTB structured training. Hinge training with reformulated Bock exceeds CL/E hinge by 0.08 points in both mean UAS and LAS (95.72 / 94.79 vs. 95.64 / 94.71), and matches local CE's mean LAS (94.79).
  • CTB structured training. Bock hinge exceeds local CE by 0.86 points in mean LAS and 1.52 points in mean LCM, and exceeds CL/E hinge by 0.78 and 2.01 points, but with larger variation across seeds (standard deviations of 1.08 LAS and 2.14 LCM).
  • No accuracy ordering between decoders. The paired LAS difference between Bock and CL/E hinge changes sign across seeds; the authors conclude the results compare complete training and model-selection procedures and establish no accuracy ordering between the inference algorithms on identical scores.
Table 1. Test scores (%) of Stanza's biaffine parser with BERT fine-tuning, mean ± sample standard deviation over three seeds. LCM = labeled complete match. Local CE uses CL/E for development selection and decoding; each hinge condition uses its own decoder for loss-augmented training inference, development selection, and final decoding. Bock = reformulated implementation. (Table 1 in the paper.)
TrainingPTBCTB
UASLASLCMUASLASLCM
Local CE95.71 ± 0.1294.79 ± 0.1055.39 ± 0.6290.07 ± 0.4488.94 ± 0.4939.72 ± 0.94
Hinge (CL/E)95.64 ± 0.1094.71 ± 0.1054.42 ± 0.5990.12 ± 0.2489.02 ± 0.2639.23 ± 1.08
Hinge (Bock)95.72 ± 0.0594.79 ± 0.0854.55 ± 0.8590.88 ± 0.9889.80 ± 1.0841.24 ± 2.14

BibTeX

@misc{wang2026reformulationequivalencebocksalgorithm,
      title={Reformulation and Equivalence of Bock's Algorithm for Exact Dependency Parsing}, 
      author={Yuxi Wang and Jungyeul Park},
      year={2026},
      eprint={2611.00939},
      archivePrefix={arXiv},
      primaryClass={cs.CL},
      url={https://arxiv.org/abs/2611.00939}, 
}
More projects from KAIST MLP Lab →