betaFeedback

WorksComputer Science

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

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.

Introduction

Exact arborescence inference is a standard component of graph-based dependency parsing. Given scores for individual head–dependent arcs, the decoder selects a highest-scoring tree subject to the required structural constraints [9]. The Chu–Liu/Edmonds (CL/E) algorithm provides the classical basis for this computation [4, 6]. Neural parsers retain this separation between learned arc scores and exact tree inference, including parsers using biaffine scoring [5]. CL/E resolves directed circuits among provisionally selected arcs through contraction and recovers original arcs through expansion. Recent comparisons of implementations of Edmonds’ algorithm show that practical performance depends on graph structure and the data structures used [2].

Frederick C. Bock’s 1971 algorithm [1] solves the rooted arborescence problem through a matrix-based representation. It retains the original matrix and node indices, represents contracted components by shared labels, and selects entering arcs using column adjustments. Starred predecessors record provisional links, while barred references guide the transfers that replace them. These operations are interleaved in the original Algol procedure through label-directed control flow. Their interaction requires a precise account to establish that a modern implementation preserves the original computation.1

We give an executable reformulation that separates candidate search, column adjustment, backward tracing, contraction, and star-and-bar transfer while preserving their dependencies and assignment order. In exact arithmetic, we prove its operational correspondence with Bock’s original procedure under matching input conventions, scan order, and tie resolution. Corresponding maintained states yield the same candidate choices, component partitions, and final original arcs.

We also establish the relationship between the reformulation and CL/E. Under a prescribed component schedule and a common ordering of original arcs for resolving ties, we prove correspondence with Tarjan’s implementation of Edmonds’ method [13], using the corrected value and recovery rules [3]. This correspondence aligns component formation, adjusted selection values, and recovered arc sets, including when the optimum is nonunique. A separate analysis establishes optimal-value equivalence with the Dozat-derived CL/E implementation used in Stanza ([10]) under the stated score conventions and exactly-one-root-child constraint. These results distinguish correspondence between coupled executions from equality of optimal values and identity of native returned trees.

We integrate reformulated Bock into Stanza for prediction and loss-augmented inference. Experiments on dependency conversions of the Penn Treebank (PTB) ([7]; [8]; [11]) and Chinese Treebank (CTB) ([17]; [16]) compare local cross-entropy with CL/E-and Bock-based structured-hinge training under shared architecture, features, and optimization settings. Each condition uses its corresponding decoder for development selection and final prediction. On identical scores from the selected PTB and CTB local-CE models, CL/E, original Bock, and reformulated Bock return identical development and test parses and objective values. These results establish Bock as an alternative exact oracle for dependency parsing and structured training.

Exact inference in dependency parsing

For a sentence of n≥1n \ge1 tokens, index the tokens by 1,…,n1, \ldots, n and let node 00 denote an artificial ROOT. An arc i→ji \to j assigns node ii as the head of token jj. An arc-factored parser assigns a finite real score S[i,j]S[i,j] to each admissible arc i→ji \to j and scores a tree by summing its arc scores ([9]). Rows of SS index heads and columns index dependents. The scores may depend on the entire sentence; arc factorization concerns their additive contribution to the tree objective.

A rooted spanning arborescence contains exactly one incoming arc for each token, no incoming arc for node 00, and a directed path from node 00 to every token. These conditions allow several tokens to attach directly to the artificial root. A single-root dependency tree additionally requires exactly one outgoing arc from node 00: precisely one token has head 00. This additional constraint must therefore be enforced when using an arborescence algorithm for single-root dependency parsing. No projectivity constraint is imposed.

Self-loops and arcs entering node 0 are forbidden. Any further restrictions are imposed identically for both decoders. Forbidden arcs are excluded from selection and represented by −∞-\infty in the score matrix; the column corresponding to node 0 is unused in the parsing objective. Let T1\mathcal{T}_1 denote the set of single-root dependency trees containing only admissible arcs. Exact decoding solves

T^∈arg max⁡T∈T1∑(i,j)∈TS[i,j].(1)\widehat{T} \in\operatorname*{arg\,max}_{T \in\mathcal{T}_1} \sum_{(i,j)\in T} S[i,j]. \tag*{(1)}

If T1\mathcal{T}_1 is empty, the instance is infeasible. Bock’s procedure minimizes costs using the same matrix orientation: rows index initial nodes (heads), and columns index terminal nodes (dependents). For each admissible arc, we therefore set

C[i,j]=−S[i,j],(2)C[i,j] = -S[i,j], \tag*{(2)}

and assign +∞+\infty to forbidden arcs. Throughout, +∞+\infty and −∞-\infty are symbolic exclusion sentinels: forbidden arcs are omitted from candidate sets before cost or score arithmetic. For every feasible tree, its total cost is the negative of its total score. Consequently, minimum-cost and maximum-score decoding have exactly the same optimal trees when their admissible arcs and root constraints agree.

Equality of optimal values, identity of returned trees, and correspondence between executions are distinct claims. On a feasible instance, two exact decoders for (1) attain the same optimal score in exact arithmetic. They necessarily return the same tree when the optimum is unique, but may select different trees when several optimal exist. Correspondence between executions requires a relation between their maintained states and a proof that their operations preserve that relation. Neither equal objective values nor identical final trees alone establishes such a correspondence.

Reformulating Bock’s algorithm

Original procedure and maintained state

Bock’s procedure computes a minimum-cost arborescence with a designated root ([1]). We retain the nodes 0,…,n0, \ldots, n and cost convention of Section 2, with finite costs for admissible arcs and +∞+\infty for forbidden arcs. The entry C[i,j]C[i,j] is the cost of assigning head ii to dependent jj. The root is node 00; restricting it to exactly one child requires a separate constraint. Appendix A gives the original procedure. For the comparison, take its origin to be node 1 and subtract one from every node index. Represent the original empty predecessor value 0 and empty bar pair (0,0)(0,0) by ⊥\perp, distinguishing them from node 0.

The procedure processes nonroot columns in increasing order. The array U1[j]U_1[j] records the cumulative adjustment applied to column jj, and I∗[j]=iI^*[j]=i records a provisional, or starred, arc i→ji\to j. A barred pair B[j]=(Iˉ[j],Jˉ[j])B[j]=(\bar{I}[j],\bar{J}[j]) stores an original arc reference. When B[j]≠⊥B[j]\ne\perp, Iˉ[j]\bar{I}[j] and Jˉ[j]\bar{J}[j] are respectively the head and dependent of the referenced arc; Jˉ[j]\bar{J}[j] need not equal jj. Backward tracing writes the current candidate into empty bar entries, and transfers may subsequently redirect these references. If installing an arc displaces an existing star, the bar read at its dependent supplies the next candidate. In the original procedure, equal positive SPAN labels represent a contracted component, and negative labels temporarily mark components visited during a backward trace. Algorithm 1 presents our reformulation of Bock’s procedure.

Reformulated procedure

We retain U1U_1, I∗I^* and BB, and replace SPAN by an array comp⁡\operatorname{comp} and an explicit trace set. Component labels remain unchanged during tracing. A contraction assigns the active component’s label to the traced components, preserving the represented partition without creating a fresh label.

For the current column KK, let H=comp⁡[K]H=\operatorname{comp}[K] be the label of its active component. Candidate selection considers precisely the arcs satisfying

1≤j≤K,comp⁡[j]=H,1\le j\le K,\quad\operatorname{comp}[j]=H,
0≤i≤n,comp⁡[i]≠H,C[i,j]<+∞.(3)0\le i\le n,\quad\operatorname{comp}[i]\ne H,\quad C[i,j]<+\infty. \tag*{(3)}

Among these arcs, the procedure minimizes C[i,j]−U1[j]C[i,j]-U_1[j], examining dependents in increasing jj and, for each dependent, heads in increasing ii, and retaining the first minimum. Adding this minimum to the adjustments of the active component makes the selected candidate’s adjusted cost zero and leaves every current candidate with nonnegative adjusted cost.

The backward trace follows starred predecessors from the candidate’s head ii. Returning to the active component identifies a circuit and triggers contraction. Reaching an empty predecessor instead initiates a transfer. Each transfer first redirects every processed bar referring to the current

Algorithm 1 Reformulated Bock procedure

Figure 1. Algorithm 1 Reformulated Bock procedure

candidate, then reads the bar at its dependent jj, replaces that bar, and installs the candidate. The global replacement must precede the local read, since it may change the reference that determines the next candidate.

Example Consider nodes 0, 1, 2, with root 0 and admissible arcs 0→10\to1, 0→20\to2, 1→21\to2, and 2→12\to1 of costs 50, 60, 10, and 20, respectively. This is the instance in Appendix § 8 with every node index reduced by one. At K=1K=1, the procedure installs 2→12\to1 with U1[1]=20U_1[1]=20. At K=2K=2, selecting 1→21\to2 gives U1=(0,20,10)U_1=(0,20,10). The backward trace records TRACE⁡={1}\operatorname{TRACE}=\{1\} and B[1]=(1,2)B[1]=(1,2), then returns to the active component, detecting the circuit 1→2→11\to2\to1. Contraction yields comp⁡=(0,2,2)\operatorname{comp}=(0,2,2). The renewed search compares adjusted costs 50−20=3050-20=30 for 0→10\to1 and 60−10=5060-10=50 for 0→20\to2. It selects 0→10\to1 and updates U1U_1 to (0,50,40)(0,50,40). The transfer reads and clears B[1]B[1], replaces the star 2→12\to1 by 0→10\to1, then installs the stored candidate 1→21\to2 and sets B[2]=(2,1)B[2]=(2,1).

Algorithm 1 Reformulated Bock procedure

Require: Cost matrix CC on nodes 0,…,n0,\ldots,n

Ensure: Minimum-cost predecessor array, or INFEASIBLE

1: For all jj, set U1[j]←0U_1[j]\leftarrow0, I∗[j]←⊥I^*[j]\leftarrow\perp, B[j]←⊥B[j]\leftarrow\perp, and comp⁡[j]←j\operatorname{comp}[j]\leftarrow j. 2: for K=1,…,nK=1,\ldots,n do 3: &nbsp;&nbsp;repeat 4: &nbsp;&nbsp;&nbsp;&nbsp;H←comp⁡[K]H\leftarrow\operatorname{comp}[K]. 5: &nbsp;&nbsp;&nbsp;&nbsp;Choose the first minimum (i,j)(i,j) of C[i,j]−U1[j]C[i,j]-U_1[j] satisfying (3). 6: &nbsp;&nbsp;&nbsp;&nbsp;If no candidate exists, return INFEASIBLE. 7: &nbsp;&nbsp;&nbsp;&nbsp;DU←C[i,j]−U1[j]DU\leftarrow C[i,j]-U_1[j]. 8: &nbsp;&nbsp;&nbsp;&nbsp;Add DUDU to U1[q]U_1[q] for every q≤Kq\le K with comp⁡[q]=H\operatorname{comp}[q]=H. 9: &nbsp;&nbsp;&nbsp;&nbsp;v←iv\leftarrow i; TRACE⁡←∅\operatorname{TRACE}\leftarrow\varnothing. 10: &nbsp;&nbsp;&nbsp;&nbsp;while I∗[v]≠⊥I^*[v]\ne\perp and comp⁡[v]≠H\operatorname{comp}[v]\ne H do 11: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;Add every q≤Kq\le K with comp⁡[q]=comp⁡[v]\operatorname{comp}[q]=\operatorname{comp}[v] to TRACE. 12: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;If B[v]=⊥B[v]=\perp, set B[v]←(i,j)B[v]\leftarrow(i,j). 13: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;v←I∗[v]v\leftarrow I^*[v]. 14: &nbsp;&nbsp;&nbsp;&nbsp;end while 15: &nbsp;&nbsp;&nbsp;&nbsp;If comp⁡[v]=H\operatorname{comp}[v]=H, set comp⁡[q]←H\operatorname{comp}[q]\leftarrow H for every q∈TRACE⁡q\in\operatorname{TRACE}. 16: &nbsp;&nbsp;until comp⁡[v]≠H\operatorname{comp}[v]\ne H 17: &nbsp;&nbsp;&nbsp;&nbsp;e←(i,j)e\leftarrow(i,j); d←⊥d\leftarrow\perp. 18: &nbsp;&nbsp;&nbsp;&nbsp;repeat 19: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;(i,j)←e(i,j)\leftarrow e. 20: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;For every q≤Kq\le K with B[q]=eB[q]=e, set B[q]←dB[q]\leftarrow d. 21: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;f←B[j]f\leftarrow B[j]; B[j]←dB[j]\leftarrow d. 22: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;a←I∗[j]a\leftarrow I^*[j]; I∗[j]←iI^*[j]\leftarrow i. 23: &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;If a≠⊥a\ne\perp, set d←(a,j)d\leftarrow(a,j) and e←fe\leftarrow f. 24: &nbsp;&nbsp;&nbsp;&nbsp;until a=⊥a=\perp 25: &nbsp;&nbsp;end for 26: &nbsp;&nbsp;return I∗I^*. The final array I∗=(⊥,0,1)I^* = (\perp, 0, 1) defines the arborescence 0→1→20 \to1 \to2 of cost 50+10=6050 + 10 = 60; the residual bar entry does not affect the selected tree.

The selections and transfer match the original procedure. The reformulation records the backward trace explicitly in TRACE rather than marking component labels negatively, and stores each bar pair in a single entry of BB rather than in parallel arrays.

Faithfulness to original Bock

The reformulation preserves the operations of the original Bock procedure while changing how components and backward traces are represented. The original SPAN serves two purposes: equal absolute labels identify members of the same component, while negative labels temporarily mark components visited during a backward trace. The reformulation separates these roles. The array comp maintains component membership without changing labels during tracing, and TRACE collects all processed vertices belonging to each visited component. Thus, negating a component’s SPAN label in the original procedure corresponds to adding its members to TRACE. If the trace returns to the active component, the original procedure assigns a fresh label to the active and negatively marked components, whereas the reformulation assigns the active label to all vertices in TRACE. Both merge exactly the same components. If the trace terminates without a circuit, restoring the negative SPAN labels corresponds to simply discarding TRACE, leaving the component partition unchanged.

Assume exact arithmetic and the same scan order and first-minimum tie rule. Initially, the column adjustments, starred predecessors, and barred pairs agree after the index conversion, and the component arrays represent the same partition. Whenever these relations hold before a candidate search, the procedures examine the same ordered candidate set with identical adjusted costs, select the same minimum, and update U1U_1 identically. The backward traces follow the same starred predecessors and fill the same empty bar entries. The transfer phase likewise preserves the original order of global bar replacement, local bar read, and star update, producing identical BB and I∗I^*. Induction over candidate searches, backward-trace steps, transfer iterations, and column advances therefore establishes these relations at corresponding phase boundaries. The procedures return the same predecessor array and objective value, or both report infeasibility.

Computational complexity

Assume unit-cost arithmetic, comparisons, and array access, with TRACE represented by a Boolean mask. Each successful candidate search either completes a column or contracts at least two components. There are nn columns and at most n−1n-1 contractions, so the procedure performs O(n)O(n) searches; an empty candidate set terminates the computation. Each candidate scan costs O(n2)O(n^2). A backward trace follows a path in the starred forest and therefore visits at most n+1n+1 vertices. Scanning the component labels at each visited vertex therefore costs at most O(n2)O(n^2) per trace. Column adjustments and component relabelling each cost O(n)O(n).

The transfer completing a column uses at most nn iterations. Within a contracted component, it first acts in the constituent containing the entering arc’s dependent and, if different, then in the constituent containing the component’s previous internal root, the vertex without an internal starred predecessor. The same decomposition applies recursively within each constituent. Because the two constituents are disjoint, induction over nested contractions shows that each dependent receives at most one new star during the transfer. Each iteration scans at most nn bar entries and performs a constant number of local assignments, giving O(n2)O(n^2) time per transfer. Consequently, Algorithm 1 runs in O(n3)O(n^3) time. The cost matrix occupies O(n2)O(n^2) storage, while the maintained arrays and trace mask require O(n)O(n) additional storage. Bock’s original procedure has the same O(n3)O(n^3) time and O(n2)O(n^2) total-space upper bounds: its candidate scans and transfers have the same asymptotic costs, while span marking and relabelling require at most O(n2)O(n^2) work per trace. The same upper bounds hold on an infeasible instance, since the procedure terminates at its first empty candidate set.

Equivalence with CL/E

Correspondence with corrected Tarjan

The comparison with Tarjan concerns the rooted arborescence problem before imposing the single-root constraint. We assume that an arborescence rooted at node 0 exists. Tarjan’s original formulation maximizes total arc weight over branchings, which may contain several trees [13]. We use its sign-reversed, minimum-value formulation and enforce maximum cardinality before minimizing cost. Initialize it with

d(i,j)=C[i,j]−Λd(i,j)=C[i,j]-\Lambda

for every admissible arc. Here Λ\Lambda is a positive formal symbol enforcing cardinality priority on admissible arcs: affine expressions are ordered first by their coefficient of Λ\Lambda and then by their real part. It is distinct from +∞+\infty, which indicates excluded arcs. A branching has at most nn arcs, and a feasible rooted arborescence attains this cardinality. Since no arc enters node 00, every branching with nn arcs is rooted at 00. Minimizing the transformed objective therefore selects precisely the minimum-cost rooted arborescences.

We use Tarjan’s corrected value comparisons and recovery procedure [3]. A root component is a strongly connected component of the selected graph with no selected arc entering it from outside. Tarjan extracts a minimum-current-value unexamined arc whose dependent lies in a chosen root component. An internal arc is discarded; an external arc is selected. If the selection closes a circuit of components Q1,…,QmQ_1,\ldots,Q_m, with circuit arc eℓe_\ell entering QℓQ_\ell, the update is

h=max⁡ℓd(eℓ),d(i,j)←d(i,j)−d(eℓ)+h,j∈Qℓ.(4)\begin{aligned} h&=\max_{\ell}d(e_\ell),\\ d(i,j)&\gets d(i,j)-d(e_\ell)+h,\qquad j\in Q_\ell. \tag*{(4)} \end{aligned}

The update applies only to unexamined arcs. Each selected arc retains its value at extraction.

Bock processes columns in increasing order. We prescribe Tarjan’s component schedule to follow Bock’s active component, continuing with the merged component after a contraction. Pair each Bock candidate search with Tarjan’s state immediately before its next external extraction, after any internal extractions. Both executions resolve equal-value choices by increasing original dependent index and then increasing original head index. All arc identities are retained through contraction.

For each contraction, consider its immediate constituent components Q1,…,QmQ_1,\ldots,Q_m and its original circuit arcs e1,…,eme_1,\ldots,e_m, including the closing arc. These records describe the execution history without changing either algorithm. For an original arc e=(i,j)e=(i,j), write dep⁡(e)=j\operatorname{dep}(e)=j for its dependent. Define the internal expansion rooted at xx by E({x},x)=∅E(\{x\},x)=\varnothing and, when x∈Qsx\in Q_s, by

E(Q,x)=E(Qs,x)∪⋃ℓ≠s({eℓ}∪E(Qℓ,dep⁡(eℓ))).(5)E(Q,x)=E(Q_s,x)\mathbin{\cup}\bigcup_{\ell\ne s}\left(\{e_\ell\}\cup E(Q_\ell,\operatorname{dep}(e_\ell))\right). \tag*{(5)}

Removing ese_s from the constituent circuit leaves an out-tree rooted at QsQ_s. Induction on the contraction history therefore shows that E(Q,x)E(Q,x) is an internal arborescence rooted at xx.

The corresponding recursive bar representation is defined as follows. If the internal root of QQ lies in QsQ_s, each constituent QℓQ_\ell with ℓ≠s\ell\ne s has internal root dep⁡(eℓ)\operatorname{dep}(e_\ell), external star eℓe_\ell, and root bar ese_s. The constituent QsQ_s inherits the external star and root bar of QQ. The same description holds recursively inside every constituent. Its internal stars are exactly E(Q,x)E(Q,x), where xx is its internal root. Stars and bars in this representation are identified by their original arcs.

Lemma 1 (Transfer and recursive expansion). Suppose a recorded component Q⊆{1,…,K}Q\subseteq\{1,\ldots,K\} has the recursive bar representation, with external star pp and root bar bb. Assume that no bar outside QQ names an internal circuit arc in its history. Here pp is empty or enters QQ, and bb is empty or has its dependent outside QQ.

Let the current candidate ee enter QQ at xx, and let the preceding displaced arc zz be empty or have its dependent outside QQ. A finite consecutive segment of the transfer in Algorithm 1 installs ee at xx, replaces the internal stars by E(Q,x)E(Q,x), and installs root bar zz. It returns the old external star pp as the displacement and reads the old root bar bb as the next candidate. Outside QQ, only the initial global substitution e↦ze\mapsto z can change bars, and no star changes. The complete transfer stops at this segment precisely when pp is empty.

Proof. An original arc belongs to the circuit of at most one contraction: after its endpoints are merged, it is internal to every later component containing them. The recursive representation and the locality hypothesis therefore identify references to an omitted circuit arc precisely at the nonroot constituent roots of that contraction. The same locality holds inside each constituent, since the arcs referenced by nonempty inherited outer bars have their dependents outside that constituent.

Induct on the contraction history of QQ. For a singleton, b≠eb\ne e: this is immediate if bb is empty; otherwise, their dependents lie on opposite sides of QQ. One transfer iteration reads bb, installs zz and ee, and returns pp, as required.

Otherwise, let QsQ_s contain the old internal root and let x∈Qtx \in Q_t. Apply the induction hypothesis inside QtQ_t. Since ee enters QQ from outside, its initial substitution changes no bar in another constituent of QQ. If t=st=s, the segment returns pp, bb, and the omitted circuit arc remains ese_s.

If t≠st \ne s, the first segment returns displaced arc ete_t and next candidate ese_s. The displacement is nonempty, so the transfer continues inside QsQ_s, now with candidate ese_s and preceding displacement ete_t. Its initial substitution es↦ete_s \mapsto e_t redirects all remaining references at the other constituent roots. The induction hypothesis for QsQ_s returns pp, bb. The new root constituent is QtQ_t, the omitted arc is ete_t, and every other constituent has entering star eℓe_\ell and root bar ete_t. This is precisely the recursive representation rooted at xx.

Every substituted label after the initial substitution is internal to QQ, so locality gives the asserted outside effect. Recursive segments act in smaller constituents, and the two constituents used when t≠st \ne s are disjoint. The segment is finite, using at most ∣Q∣|Q| iterations. Every intermediate nonroot constituent returns its nonempty circuit arc, so the stopping rule suppresses no required continuation.

Theorem 1 (Coupled Bock–Tarjan executions). In exact arithmetic, the prescribed schedule is well defined. At every paired search, the component partitions coincide, the active component is a root component, and both external candidate sets contain exactly the admissible original arcs entering it from outside. These arcs are unexamined by Tarjan. The executions select the same external arc and contract the same directed component circuit, with the same original circuit arcs.

For every current component QQ, an offset βQ\beta_Q satisfies

d(i,j)=C[i,j]−U1[j]+βQ(6)d(i,j) = C[i,j] - U_1[j] + \beta_Q \tag*{(6)}

on every unexamined external arc entering QQ.

After each completed prefix K=0,…,nK=0,\ldots,n, corrected Tarjan recovery on the corresponding prefix record returns exactly Bock’s starred arc set. The recovered branching has roots {0}∪{K+1,…,n}\{0\} \cup\{K+1,\ldots,n\}. In particular, the final rooted arborescences coincide even when the optimum is nonunique.

Proof. We use a joint induction over candidate searches and completed transfers. Maintain equality between Bock’s components and Tarjan’s strong components. Their common quotient is an out-forest, and Bock’s crossing stars are exactly its selected arcs. Every current component has the recursive bar representation with an empty root bar. Its internal root carries the unique external entering star when the component is nonroot, and an empty star otherwise. During column KK, the active component has internal root KK, whose star is empty. The origin and unprocessed vertices remain singleton components with empty stars and bars. In addition to (6), maintain that each nonroot component’s offset is the frozen value of its entering selected arc.

Initially, all components are singletons, all stars and bars are empty, and (6) holds with β{v}=−Λ\beta_{\{v\}}=-\Lambda. Suppose the invariants hold at a candidate search with active component QQ. Its empty external star makes it a root of the common quotient. Moreover, Q⊆{1,…,K}Q \subseteq\{1,\ldots,K\}: the origin or an unprocessed singleton stops a backward trace before it can be marked or contracted. Thus Bock’s restriction to processed columns excludes no arc entering QQ.

Every admissible arc entering QQ from outside is unexamined by Tarjan. A discarded internal arc remains internal under subsequent mergers, while a previously selected external arc entering QQ would contradict rootness. Feasibility of the full rooted instance guarantees an entering arc for every nonempty component excluding node 00. Internal extractions change neither the selected graph nor the external candidates or their values. Furthermore, every finite queue value retains the form −Λ-\Lambda plus a real number under (4), so Tarjan’s branching stopping rule does not reject an eligible external arc.

Equation (6) differs from Bock’s comparison by a component-wide constant. The common original-arc tie order therefore gives the same choice ee. For e=(i,j)e=(i,j), the values before the column adjustment are d(e)=C[i,j]−U1[j]d(e)=C[i,j]-U_1[j], so (6) gives d(e)=DU+βQ−d(e)=DU+\beta_Q^-. After Bock’s column adjustment, set

βQ+=βQ−+DU=d(e).\beta_Q^+ = \beta_Q^- + DU = d(e).

This preserves (6) for the remaining external arcs, whose Tarjan values have not changed.

Inside each component, the backward starred path reaches its internal root. At a nonroot component it then follows the unique crossing selected arc; at a root component it stops. Hence Bock’s projected trace is exactly the predecessor path in the common quotient forest. Adding ee creates a circuit precisely when its head belongs to the quotient tree rooted at QQ. Both executions then identify the same path and closing arc, and merge the same components.

Only the internal root of each traced nonroot component has an empty bar. The trace writes ee at exactly these roots and preserves their internal bars. Consequently, contraction creates the recursive representation of the union with closing arc ee omitted and internal root KK. The selected graph has exactly this new strong component, and its quotient remains an out-forest.

For each circuit constituent QℓQ_\ell, its offset after the column adjustment equals d(eℓ)d(e_\ell): this follows from the nonroot invariant for the old circuit arcs and the selection identity for the closing arc. An unexamined arc entering the union from outside also entered its constituent from outside. Therefore (4) gives

d+(i,j)=d−(i,j)−d(eℓ)+h=C[i,j]−U1[j]+h.d^{+}(i,j) = d^{-}(i,j) - d(e_\ell) + h = C[i,j] - U_1[j] + h.

The merged offset is hh, and the induction continues at the next candidate search.

If no circuit forms, the trace ends at a different quotient root. It has written temporary references to ee only at the intervening nonroot component roots. Since ee is unexamined, it occurs in no earlier contraction record or bar. The initial transfer substitution e↦⊥e \mapsto\bot clears exactly those temporary references outside QQ. Apply Lemma 1 to QQ with empty external star, root bar, and preceding displacement. The transfer terminates inside QQ, installs ee, and restores its recursive representation rooted at dep⁡(e)\operatorname{dep}(e). All outside stars are unchanged. Both quotient forests acquire the same crossing arc, and QQ becomes nonroot with offset d(e)d(e). The next column is a singleton root, so all induction assertions are preserved.

It remains to identify corrected recovery. At a completed prefix KK, every processed vertex has a star, while the origin and unprocessed vertices have none. The common quotient therefore has precisely the singleton roots {0}∪{K+1,…,n}\{0\}\cup\{K+1,\ldots,n\}. All selections have dependents at most KK. On the graph containing only such arcs, these roots have no eligible incoming arcs, so the prefix construction is terminal.

In the corrected reconstruction forest, each selected original arc is a node ([3, 2]). An arc entering a singleton is its leaf; an arc entering a contracted component becomes the parent of all circuit nodes of the contraction that formed that component, including its closing node. Thus the subtree of an arc entering a component contains exactly the leaves for that component’s original vertices.

Recovery retains a forest-root arc ee and deletes the path from the leaf for dep⁡(e)\operatorname{dep}(e) to that root. At each nested contraction, this path passes through the constituent containing that dependent. Its entering circuit arc is deleted, while the other constituent subtrees survive. Induction on the contraction history gives exactly

{e}∪E(Q,dep⁡(e))\{e\}\cup E(Q,\operatorname{dep}(e))

for an arc entering QQ. The surviving subtrees are disjoint, so their processing order does not affect the recovered arc set.

At a completed prefix, every current nonroot component has its entering selected arc as a reconstruction-forest root; all its internal contraction nodes lie below that root. The remaining root vertices have no incoming selections and require no root-circuit deletion. Recovery therefore gives precisely the recursive expansions represented by Bock’s stars. This proves prefix equality, including the empty prefix. At K=nK=n, only node 0 remains a root, and the common branching is the claimed arborescence. □\square

Equivalence with Dozat-derived CL/E

The Stanza version used in our experiments implements CL/E by contraction and expansion, following Dozat’s code ([10]). We establish its optimal-value equivalence directly from that contraction rule and its single-root inference procedure.

At a contraction stage, let p(j)p(j) be a maximum-scoring admissible head for dependent jj, and let QQ be a directed cycle of these selections. Put σQ=∑j∈QS[p(j),j]\sigma_Q=\sum_{j\in Q}S[p(j),j]. Contracting QQ to node qq gives

S′[i,q]=σQ+max⁡j∈Q(S[i,j]−S[p(j),j]),S'[i,q] = \sigma_Q + \max_{j\in Q}\left(S[i,j]-S[p(j),j]\right),
{#eq:7}

S'[q,k] = \max_{i\in Q}S[i,k],

Equation not extracted

where ii in the first line is a head outside QQ, and kk in the second is a dependent outside QQ. Other surviving scores remain unchanged, self-loops are excluded, and a maximum over no admissible arcs is −∞-\infty. The maximizing original endpoints are retained for expansion.

An optimal rooted arborescence can be chosen to enter QQ exactly once. Indeed, take an optimal tree and an entering arc u→vu \to v whose root-to-uu path avoids QQ. Such an arc exists by taking the first entry along a root path to QQ. Retain this arc and replace the entering arc of every j∈Q∖{v}j \in Q \setminus\{v\} by p(j)→jp(j) \to j. The root still reaches uu and hence vv, and the selected cycle with p(v)→vp(v) \to v removed reaches every vertex of QQ. Every remaining vertex is reachable along an unchanged suffix of its former root path. The result is therefore an arborescence, and its score cannot decrease because each replacement uses a maximum-scoring incoming arc.

For a tree entering QQ once, the first line of (7) accounts for its entering arc and retained cycle arcs. The second line accounts for each outgoing arc. Contracting such a tree gives a tree whose contracted score is at least its original score. Conversely, every contracted tree expands using the stored maximizing endpoints: its entering arc replaces exactly one cycle arc, all other cycle arcs are restored, and every outgoing arc receives its stored original head. The expanded tree has exactly the contracted score. Thus contraction preserves the optimum, and induction over contractions proves exact rooted-arborescence inference.

Column-wise log-softmax subtracts a constant from each dependent column and therefore changes every tree score by the same total constant. It preserves the maximizing trees and gives nonpositive admissible scores. If any dependent has at least two admissible heads, at least one resulting score is strictly negative.

Theorem 2 (Single-root parsing equivalence). Suppose T1\mathcal{T}_1 is nonempty and both decoders receive the same admissible arcs and scores. Assume that the finite scores are nonpositive and, when n>1n > 1, have a strictly negative minimum. In exact arithmetic, the Dozat-derived CL/E and Bock single-root inference procedures both solve Equation (1) and attain the same optimal score.

Proof. For n>1n > 1, let m<0m < 0 be the minimum finite input score, with the unused entry S[0,0]S[0,0] set to zero. The CL/E procedure adds (n+1)m(n + 1)m to every admissible root-arc score, following the root-reweighting approach Stanojević and Cohen, [12]. Every rooted arborescence has nn arcs and an original score between nmnm and 0. The reweighted score of any single-root tree therefore exceeds that of any tree with k≥2k \ge2 root children by at least

nm−(k−1)(n+1)m≥−m>0.nm - (k - 1)(n + 1)m \ge-m > 0.

Hence, every reweighted optimum has exactly one root child. All single-root trees receive the same additive term, so their original ranking is preserved.

The Bock single-root inference procedure first solves the unrestricted rooted problem using (2). If the returned optimum has one root child, it is already optimal over T1\mathcal{T}_1. Otherwise, the procedure enumerates admissible sole root children. For each child, it forces that root arc, excludes every other root arc, and solves the resulting rooted problem. These feasible subproblems partition T1\mathcal{T}_1 according to its unique root child. Selecting their best optimum therefore solves the single-root problem.

For n=1n = 1, the sole feasible root arc determines the unique tree in both procedures. ▫

Complexity comparison

For dense score matrices, the Dozat-derived CL/E procedure has an O(n3)O(n^3) time upper bound for rooted-arborescence inference: there are O(n)O(n) contraction stages, each requiring at most O(n2)O(n^2) work, and expansion does not increase this bound. This matches the bound for Algorithm 1 proved in § 3.4.

For single-root inference, CL/E reweights root arcs and performs one rooted-arborescence computation, retaining the O(n3)O(n^3) time bound Stanojević and Cohen, [12]. The implemented Bock procedure solves one unrestricted rooted problem and, if the returned optimum has multiple root children, at most nn constrained subproblems, one per admissible sole root child. Its worst-case time is O(n4)O(n^4), with O(n2)O(n^2) peak storage when the subproblems are solved sequentially. If the initial optimum has one root child, the procedure returns it in O(n3)O(n^3) time. Under the assumptions of Theorem 2, applying the same root reweighting to Bock’s input scores would give O(n3)O(n^3) single-root inference; the experiments reported here use enumeration.

These bounds concern the particular matrix procedures compared here. Tarjan’s dense-graph implementation achieves O(n2)O(n^2) time for rooted-arborescence inference [13, 2]. The correspondence in Theorem 1 identifies candidate choices, contractions, and recovered branchings, while their computational costs depend on the data structures and operations used to maintain them.

Experiments

We evaluate decoder substitution and structured training on the Penn Treebank (PTB) and Chinese Treebank (CTB), using Stanza’s biaffine parser ([5, 10]). All training conditions share the architecture, linguistic features, admissible arcs, and single-root constraint, with full BERT fine-tuning. Experimental settings, verification procedures, and supplementary comparisons appear in Appendix § 9. Table 1 reports test UAS, LAS, and labeled complete match (LCM). LCM requires every scored token in a sentence to have the correct head and dependency label.

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

Table 1. Test scores (%), reported as means ± sample standard deviations across three seeds. Local CE uses CL/E for development selection and final decoding; for all three PTB models, substituting original or reformulated Bock gives identical development and test predictions. Each hinge condition uses its corresponding decoder for loss-augmented training inference, development selection, and final decoding. Bock denotes the reformulated implementation.

Decoder substitution on identical scores For the three PTB local-CE models, one per seed, we apply CL/E, original Bock, and reformulated Bock to identical development and test score matrices. The admissible arcs, single-root constraint, and tie-breaking rules are shared across all three implementations. All three return identical heads, full relation labels, and original tree-score values on every evaluated sentence, yielding identical UAS, LAS, and complete-match scores for each model.

Structured training We also implement structured arc hinge loss using either CL/E or reformulated Bock. Relation-label cross-entropy and auxiliary losses are common to all conditions. Each hinge condition uses its corresponding decoder for loss-augmented training inference, development evaluation, and final prediction, so the comparison includes both the training oracle and development-dependent decisions. On identical scores, gold trees, task costs, and admissible tree families, exact CL/E and Bock oracles define the same hinge objective. A unique loss-augmented optimum determines the same score subgradient; tied optima permit different valid subgradients. Identical training trajectories additionally require matched initialization, minibatches, stochastic and numerical computations, selected subgradients, and training decisions. Appendix § 9 gives the precise conditions and proof. Additional PTB experiments retain local cross-entropy while using CL/E, original Bock, or reformulated Bock for development evaluation and final prediction. In every seed, training losses differ before the first development evaluation, demonstrating variation without a structured-training oracle. Losses also differ before the first development evaluation in CL/E- and Bock-based hinge training on both PTB and CTB. Development decoding therefore cannot explain the initial variation, whose cause remains undetermined. The final accuracy differences do not isolate the effect of replacing the training oracle.

Parsing accuracy On PTB, hinge training with reformulated Bock exceeds CL/E hinge by 0.08 percentage points in both mean UAS and LAS, and matches local CE’s mean LAS at the reported precision. Despite this similar attachment accuracy, mean LCM is 0.84 percentage points below local CE for Bock hinge and 0.98 points below local CE for CL/E hinge. On CTB, Bock hinge exceeds local CE by 0.86 percentage points in mean LAS and 1.52 points in mean LCM, and exceeds CL/E hinge by 0.78 and 2.01 points, respectively. These higher means accompany greater variation across seeds, with sample standard deviations of 1.08 points for LAS and 2.14 points for LCM. The paired LAS difference between Bock and CL/E hinge changes sign across seeds. These results describe the complete training and model-selection conditions; they establish no accuracy ordering between the inference algorithms on identical scores. Earlier biaffine-parser experiments reported PTB LAS and LCM gains from CL/E hinge and decreases on CTB relative to their local baseline ((Zhang et al., 2019)). Our CL/E-hinge condition has lower mean LCM than local CE on both corpora. The architectures and scoring protocols differ.

Discussion and conclusion

Bock’s column adjustments, component labels, and star-and-bar transfers provide a matrix representation of exact arborescence inference. In exact arithmetic, the reformulated procedure reproduces the original procedure under matching scan and tie rules. The component-dependent cost relation explains the correspondence between candidate choices, while the recursive bar invariant establishes the equivalence of transfer and recovery. Under the 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. Their final rooted arborescences therefore coincide even when the optimum is nonunique. The separate analysis of Dozat-derived CL/E establishes optimal-value equivalence under the stated score and single-root conventions.

These results distinguish optimal values, returned trees, and learning trajectories. On identical scores and admissible trees, exact decoders attain the same optimum value; uniqueness additionally determines the returned tree. For structured-hinge training, on identical scores, gold trees, task costs, and admissible tree families, exact loss-augmented oracles define the same hinge objective, and a unique maximizing tree determines the same score subgradient. Tied optima permit different valid subgradients. Identical training trajectories require agreement in the remaining computations and update decisions as well. Our training conditions use their corresponding decoders for development selection, so their accuracy differences compare complete training and model-selection procedures.

For the local-CE models, the fixed-score comparison yields identical heads, full relation labels, and original tree-score values among CL/E, original Bock, and reformulated Bock on every evaluated development and test sentence. This empirical agreement concerns ordinary decoding from those models. The structured-training experiments use Bock and CL/E for loss-augmented inference, development selection, and final decoding on PTB and CTB. Our analysis complements algorithm-engineering comparisons of arborescence implementations, where practical performance depends on graph structure and data structures ([2]). It establishes Bock as an alternative exact parsing and structured-training oracle, with a faithful reformulated implementation and explicit conditions governing its theoretical and empirical correspondence with CL/E.

Declaration of generative AI in the manuscript preparation process

During the preparation of this work, the authors used OpenAI ChatGPT and Codex to assist with language editing, sentence restructuring, manuscript organization, and improving the clarity and consistency of the technical and mathematical exposition. The authors reviewed and edited all AI-assisted content, verified the formal arguments and implementations, and take full responsibility for the content of the article.

Bock’s original algorithm

Let V={1,…,N}V = \{1, \ldots, N\} be a set of nodes with designated origin j0j_0. Following Bock, we use link for a directed arc and represent the directed network by an N×NN \times N cost matrix CC. For I,J∈VI, J \in V, the entry C[I,J]C[I,J] is the cost of assigning head II to dependent JJ, represented by the link I→JI \to J. Rows index heads and columns index dependents. An entry C[I,J]=+∞C[I,J] = +\infty denotes a forbidden link. We write Bock’s symbolic infinity as +∞+\infty, consistently with the main text; these entries are excluded from candidate selection and exceed every finite comparison value.

A feasible solution TT contains exactly one link entering each node J≠j0J \ne j_0, no link entering j0j_0, and a directed path from j0j_0 to every other node. The minimum-cost arborescence problem is to find such a TT minimizing ∑(I,J)∈TC[I,J]\sum_{(I,J)\in T} C[I,J].

Bock processes the nonorigin columns in increasing index order. A link provisionally selected to enter node JJ is called starred, and its head is recorded in I∗[J]I^{*}[J]. When the iteration for column KK terminates, every processed nonorigin column J≤KJ \le K has exactly one starred entering link, although circuit resolution may subsequently replace that link. Nodes carrying the same positive SPAN label form a span. Every node initially forms a singleton span; assigning a common label to several spans represents their contraction without changing the dimensions or indices of the cost matrix.

At the beginning of each candidate search, the starred links form a directed forest when every current span is treated as a single contracted node. If the backward trace from a candidate’s head reaches the active span, the starred links between spans form a directed path from the active span to the span containing that head. The candidate closes this path into a circuit of spans. This invariant underlies Bock’s circuit test and contraction operation. The principal arrays maintained by the procedure are summarized in Table 2.

The scalar KK identifies the column currently being processed, and H=SPAN⁡[K]H = \operatorname{SPAN}[K] is the label of its active span; the columns J≤KJ \le K satisfying SPAN⁡[J]=H\operatorname{SPAN}[J] = H constitute that span in the current search. The scalar SSSS supplies a fresh label when spans are contracted. The pair (I1,J1)(I_1,J_1) denotes the candidate link, with head I1I_1 and dependent J1J_1, and DUDU is its adjusted cost. At the beginning of each transfer pass, (I2,J2)(I_2,J_2) records the link displaced during the preceding pass. Finally, ZZ stores the objective value of the completed arborescence. The starred array records the provisional link selection, U1U_1 supplies the column adjustments used in the adjusted-cost comparisons, and the span and bar arrays implement circuit contraction and resolution.

For the current column KK, the procedure chooses a link of minimum adjusted cost entering the active span from a different span, and adds that cost to every column adjustment in the active span. It then begins at the head of the selected link and follows starred links backward. If the trace reaches the active span, the selected link closes a circuit with the starred path, so the active span and all spans encountered during the trace are contracted under a common label. Candidate selection is then repeated for the resulting span. If the trace instead reaches a node without a starred entering link, the candidate is installed. Any star thereby displaced is propagated through the candidate pairs stored in the bar arrays until a link is installed without displacing another star. The procedure then advances to the next nonorigin column.

SymbolRole in Bock’s procedure
U1[J]U_1[J]Amount subtracted from the costs of links entering JJ. The adjusted cost of I→JI \to J is C[I,J]−U1[J]C[I,J] - U_1[J]; the procedure changes U1[J]U_1[J] when the span containing JJ is adjusted.
I∗[J]I^*[J]Head of the link currently starred into JJ. Thus, I∗[J]=II^*[J] = I means that I→JI \to J is provisionally selected, whereas I∗[J]=0I^*[J] = 0 means that no link is starred into JJ.
Iˉ[J],Jˉ[J]\bar{I}[J], \bar{J}[J]Arc references used by the star-and-bar transfer. In a nonempty pair, Iˉ[J]\bar{I}[J] is the referenced link’s head and Jˉ[J]\bar{J}[J] its dependent; Jˉ[J]\bar{J}[J] need not equal JJ. A backward trace writes its candidate into an empty entry, and L10 may subsequently redirect that reference to a displaced link. If a star entering JJ is displaced, the entry read at JJ supplies the next candidate. The pair (0,0)(0,0) denotes an empty entry.
SPAN⁡[J]\operatorname{SPAN}[J]Label of the span currently containing JJ. Equal positive labels identify nodes represented as one contracted span; a negative label temporarily marks a span encountered during the backward trace.

caption: tbl:2: Principal arrays maintained by Bock’s procedure.

:::

Algorithm 2 gives a line-mapped summary of this control flow. Labels of the form L2, L3, and so forth are the statement labels in Bock’s original Algol procedure. The input and reporting statements at L1 and L97 are omitted.

Candidate selection and column adjustment At L4, the active-span label is H=SPAN⁡[K]H = \operatorname{SPAN}[K]. The procedure examines columns J≤KJ \le K satisfying SPAN⁡[J]=H\operatorname{SPAN}[J] = H and feasible links I→JI \to J satisfying SPAN⁡[I]≠H\operatorname{SPAN}[I] \ne H. Among these links, it selects (I1,J1)(I_1,J_1) with least adjusted cost C[I,J]−U1[J]C[I,J] - U_1[J]. Because the candidate is replaced only under a strict inequality, ties are resolved by the first minimum encountered in Bock’s scan order: dependents in increasing JJ, with heads in increasing II for each dependent. If no candidate is found, L98 reports the instance infeasible. Otherwise, L5 adds DUDU to the column adjustment of every column in the active span. Immediately after this update, the selected link satisfies C[I1,J1]−U1[J1]=0C[I_1,J_1] - U_1[J_1] = 0 in the current search state. Later adjustments to a contracted span may alter the adjusted cost of a previously starred link.

Backward trace and contraction The original variable JJ is reused as the current node during backward tracing. At L6 it is initialized to the candidate’s head I1I_1, while J1J_1 remains the candidate’s dependent. If SPAN⁡[J]=H\operatorname{SPAN}[J] = H, the backward trace has returned to the active span. By the starred-forest invariant, the traced links between spans form a directed path from the active span to the span containing I1I_1. The candidate I1→J1I_1 \to J_1, whose dependent J1J_1 lies in the active span, closes this path into a circuit of spans. At L7, the procedure increments SSSS and assigns the new label to the active span and every span marked during the trace. It then returns to L4 to search for a link entering the resulting contracted span.

If SPAN⁡[J]≠H\operatorname{SPAN}[J] \ne H and I∗[J]>0I^*[J] > 0, L8 continues the trace. If SPAN⁡[J]>0\operatorname{SPAN}[J] > 0, the span has not yet been marked: L8 sets H1←SPAN⁡[J]H_1 \leftarrow\operatorname{SPAN}[J] and negates SPAN⁡[q]\operatorname{SPAN}[q] for every q≤Kq \le K whose span label is H1H_1. If the bar entry at JJ is empty, L8 records the current candidate by setting (Iˉ[J],Jˉ[J])←(I1,J1)(\bar{I}[J],\bar{J}[J]) \leftarrow(I_1,J_1). A nonempty entry is left unchanged. A newly written entry names the candidate whose backward trace has reached JJ. Contraction preserves the reference, while L10 may subsequently redirect it before it is read as a transfer candidate. The trace then follows the starred link backward by setting J←I∗[J]J \leftarrow I^*[J] and returning to L7. Repeating L7–L8 records the candidate at each encountered node whose bar entry is empty. If I∗[J]=0I^*[J] = 0, the trace has reached a root of the current starred forest, and control falls through to L9.

Star-and-bar transfer The transfer is an exchange chain. At the beginning of each pass, (I1,J1)(I_1,J_1) identifies the candidate link and (I2,J2)(I_2,J_2) the link displaced during the preceding pass; the latter is initialized to (0,0)(0,0) at L9. If starring I1→J1I_1 \to J_1 displaces the existing star into J1J_1, the bar entry at J1J_1 supplies the next candidate in the chain.

Each pass through L10 first replaces every bar entry equal to the current candidate (I1,J1)(I_1,J_1) by the previously displaced pair (I2,J2)(I_2,J_2), thereby redirecting references from the link being installed to the link displaced during the preceding pass. It then reads the candidate stored at J1J_1 into (I,J)(I,J), replaces that bar entry by (I2,J2)(I_2,J_2), saves the head of the existing starred link as I2←I∗[J1]I_2 \leftarrow I^*[J_1], and installs the current candidate by setting I∗[J1]←I1I^*[J_1] \leftarrow I_1. If I2=0I_2 = 0, the installation has not displaced a star, so the exchange chain terminates and control returns to L3. Otherwise, the displaced link

Algorithm 2 Control-flow summary of Bock’s original procedure.

Require: Number of nodes NN; origin j0j_0; cost matrix CC with +∞+\infty for forbidden links

Ensure: Starred array I∗I^* defining a minimum-cost arborescence, or INFEASIBLE

L2 (initialization). For 1≤J≤N1 \le J \le N, set U1[J]U_1[J], I∗[J]I^*[J], Iˉ[J]\bar{I}[J], and Jˉ[J]\bar{J}[J] to 0, and set SPAN⁡[J]←J\operatorname{SPAN}[J] \leftarrow J; set SS←NSS \leftarrow N, K←0K \leftarrow0, and Z←0Z \leftarrow0.

L3 (column advance). If K=NK=N, transfer control to L99; otherwise increment KK. If K=j0K=j_0, return to L3; otherwise continue to L4.

L4 (candidate search). Set DU←+∞DU \leftarrow+\infty and H←SPAN⁡[K]H \leftarrow\operatorname{SPAN}[K]. For every J≤KJ \le K with SPAN⁡[J]=H\operatorname{SPAN}[J]=H and every II with SPAN⁡[I]≠H\operatorname{SPAN}[I]\ne H and C[I,J]<+∞C[I,J]<+\infty, retain (I1,J1)=(I,J)(I_1,J_1)=(I,J) whenever C[I,J]−U1[J]<DUC[I,J]-U_1[J]<DU, and set DU←C[I,J]−U1[J]DU \leftarrow C[I,J]-U_1[J]. If DU=+∞DU=+\infty, transfer control to L98.

L5 (column adjustment). For every J≤KJ \le K with SPAN⁡[J]=H\operatorname{SPAN}[J]=H, set U1[J]←U1[J]+DUU_1[J] \leftarrow U_1[J]+DU.

L6 (trace initialization). Set J←I1J \leftarrow I_1.

L7 (circuit test and contraction). If SPAN⁡[J]=H\operatorname{SPAN}[J]=H, SS←SS+1SS \leftarrow SS+1; for every q≤Kq \le K with SPAN⁡[q]=H\operatorname{SPAN}[q]=H or SPAN⁡[q]<0\operatorname{SPAN}[q]<0, set SPAN⁡[q]←SS\operatorname{SPAN}[q] \leftarrow SS; then return to L4.

L8 (trace continuation or exit). If I∗[J]>0I^*[J]>0, perform the following operations in order: (i) if SPAN⁡[J]>0\operatorname{SPAN}[J]>0, set H1←SPAN⁡[J]H_1 \leftarrow\operatorname{SPAN}[J] and negate SPAN⁡[q]\operatorname{SPAN}[q] for every q≤Kq \le K satisfying SPAN⁡[q]=H1\operatorname{SPAN}[q]=H_1; (ii) if Iˉ[J]=0\bar{I}[J]=0, set (Iˉ[J],Jˉ[J])←(I1,J1)(\bar{I}[J],\bar{J}[J]) \leftarrow(I_1,J_1); and (iii) set J←I∗[J]J \leftarrow I^*[J] and return to L7. If I∗[J]=0I^*[J]=0, fall through to L9.

L9 (transfer initialization). Restore all negative span labels and set (I2,J2)←(0,0)(I_2,J_2) \leftarrow(0,0).

L10–L11 (star-and-bar transfer). For every q≤Kq \le K satisfying (Iˉ[q],Jˉ[q])=(I1,J1)(\bar{I}[q],\bar{J}[q])=(I_1,J_1), set (Iˉ[q],Jˉ[q])←(I2,J2)(\bar{I}[q],\bar{J}[q]) \leftarrow(I_2,J_2). Set (I,J)←(Iˉ[J1],Jˉ[J1])(I,J) \leftarrow(\bar{I}[J_1],\bar{J}[J_1]), then set (Iˉ[J1],Jˉ[J1])←(I2,J2)(\bar{I}[J_1],\bar{J}[J_1]) \leftarrow(I_2,J_2). Set I2←I∗[J1]I_2 \leftarrow I^*[J_1] and I∗[J1]←I1I^*[J_1] \leftarrow I_1. If I2=0I_2=0, return to L3; otherwise set (J2,I1,J1)←(J1,I,J)(J_2,I_1,J_1) \leftarrow(J_1,I,J) and return to L10.

L98 (infeasibility). Report INFEASIBLE, set Z←+∞Z \leftarrow+\infty, and transfer control to L100.

L99 (objective value). Set Z←∑J≠j0C[I∗[J],J]Z \leftarrow\sum_{J\ne j_0} C[I^*[J],J] and report an optimum solution.

L100 (output). Output ZZ, U1U_1, I∗I^*, Iˉ\bar{I}, Jˉ\bar{J}, and SPAN⁡\operatorname{SPAN}.

is (I2,J1)(I_2,J_1), the stored pair (I,J)(I,J) becomes the next candidate, and the assignment (J2,I1,J1)←(J1,I,J)(J_2,I_1,J_1) \leftarrow(J_1,I,J) prepares the next pass through L10. The transfer therefore follows the bar references maintained by backward tracing and global replacement until a candidate is installed at a node without a starred entering link.

When L3 finds K=NK=N, L99 computes Z=∑J≠j0C[I∗[J],J]Z=\sum_{J\ne j_0}C[I^*[J],J]. On feasible termination, I∗[J]=II^*[J]=I specifies the selected link I→JI\to J for every J≠j0J\ne j_0, while I∗[j0]=0I^*[j_0]=0.

Example Consider N=3N=3, origin j0=1j_0=1, and C=(M5060MM10M20M)C=\begin{pmatrix} M & 50 & 60 \\ M & M & 10 \\ M & 20 & M \end{pmatrix}. The feasible links are 1→21\to2 of cost 50, 1→31\to3 of cost 60, 2→32\to3 of cost 10, and 3→23\to2 of cost 20. Although small, this instance exercises both circuit contraction and the subsequent transfer. After L2, U1=(0,0,0)U_1=(0,0,0), I∗=(0,0,0)I^*=(0,0,0), Iˉ=Jˉ=(0,0,0)\bar{I}=\bar{J}=(0,0,0), and SPAN⁡=(1,2,3)\operatorname{SPAN}=(1,2,3); L3 skips the origin column.

For K=2K=2, the active span is H=2H=2. L4 selects 3→23\to2 with DU=20DU=20, and L5 sets U1[2]=20U_1[2]=20. The trace begins at node 3; because I∗[3]=0I^*[3]=0, it reaches L9, and L10 stars 3→23\to2, giving I∗[2]=3I^*[2]=3. Because the trace encounters no starred link, L8 records no bar pair, and Iˉ=Jˉ=(0,0,0)\bar{I}=\bar{J}=(0,0,0).

For K=3K=3, the active span is H=3H=3. L4 selects 2→32\to3 with DU=10DU=10, and L5 sets U1[3]=10U_1[3]=10. The trace begins at J=2J=2. Since SPAN⁡[2]≠H\operatorname{SPAN}[2]\ne H and I∗[2]=3>0I^*[2]=3>0, L8 changes SPAN⁡[2]\operatorname{SPAN}[2] from 2 to −2-2, records (Iˉ[2],Jˉ[2])=(2,3)(\bar{I}[2],\bar{J}[2])=(2,3), and sets J←3J\leftarrow3. On returning to L7, SPAN⁡[3]=H\operatorname{SPAN}[3]=H; the trace has therefore closed the circuit formed by 3→23\to2 and 2→32\to3. L7 assigns the new label 4 by SS+1SS+1 to the active span and the negatively marked span, giving SPAN⁡=(1,4,4)\operatorname{SPAN}=(1,4,4), while leaving the bar entry at node 2 unchanged.

The renewed search compares links entering the contracted span from nodes outside it; in this example, the only such node is 1. Their reduced costs are 50−U1[2]=3050-U_1[2]=30 for 1→21\to2 and 60−U1[3]=5060-U_1[3]=50 for 1→31\to3. Hence, 1→21\to2 is selected with DU=30DU=30, and L5 yields U1=(0,50,40)U_1=(0,50,40).

The trace begins at J=1J=1; because I∗[1]=0I^*[1]=0, control reaches L9, which initializes (I2,J2)=(0,0)(I_2,J_2)=(0,0). On the first pass through L10, the procedure reads (Iˉ[2],Jˉ[2])=(2,3)(\bar{I}[2],\bar{J}[2])=(2,3), clears this entry, displaces 3→23\to2, and stars 1→21\to2. The displaced pair becomes (I2,J2)=(3,2)(I_2,J_2)=(3,2), and 2→32\to3 becomes the next candidate. On the second pass, L10 stores (3,2)(3,2) in the empty bar entry at node 3 and stars 2→32\to3. Since I∗[3]I^*[3] was 0, no further star is displaced and the transfer terminates.

The final starred array I∗=(0,1,2)I^*=(0,1,2) records no entering link for origin 1 and selects 1→21\to2 and 2→32\to3. The remaining bar entry is residual bookkeeping and does not affect this arborescence. L99 therefore obtains Z=50+10=60Z=50+10=60.

Experimental details

Corpora and model We use dependency conversions of the English Penn Treebank and Chinese Treebank 5.1, supplied in CoNLL-U format. PTB uses WSJ sections 02–21 for training, section 22 for development, and section 23 for testing, containing 39,832, 1,700, and 2,416 sentences, respectively. CTB follows the standard dependency-parsing split (Zhang and Clark, 2008): training documents 001–815 and 1001–1136, development documents 886–931 and 1148–1151, and test documents 816–885 and 1137–1147. We exclude four CTB training sentences containing 206 tokens because of malformed annotations, retaining 16,087 training sentences and 437,778 tokens. The 803 development and 1,910 test sentences are unchanged. Every condition uses the same corpus files.

The shared Stanza parser has a three-layer bidirectional LSTM with hidden-size setting 400 [5, 10]. Word and character representations, UPOS, XPOS, and morphological features are identical across conditions. We use gold tokenization and the supplied linguistic features. External static word embeddings and character language models are disabled. BERT is fully fine-tuned in every run (Devlin et al., 2019), using bert-base-cased for PTB and bert-base-chinese for CTB.

Training and model selection Each condition starts independently from the same pretrained BERT model for its language, using seeds 1111, 2222, and 3333. The three seeds run concurrently on a single physical GPU, an NVIDIA A100 80GB PCIe, with conditions executed sequentially within each seed. Deterministic algorithms are disabled. Shared seeds and pretrained-model identifiers do not establish identical initialized tensors or numerical execution.

Training uses a token budget of 5,000 per batch, at most 50,000 updates, 500 BERT warm-up steps, and Stanza’s Adadelta-to-Adam schedule. The hinge margin is one per incorrect head. Relation-label cross-entropy, auxiliary losses, and loss normalization remain unchanged when the arc cross-entropy is replaced by the hinge.

Development evaluation occurs every 100 updates. For the conditions in the main results table, local CE and CL/E hinge use CL/E for development and final decoding; Bock hinge uses reformulated Bock for both. The additional local-CE runs use their designated decoder—CL/E, original Bock, or reformulated Bock—for development and final decoding, with no structured-training oracle. We retain the model with the highest development LAS, preferring the later model when scores tie. Development scores also govern learning-rate scheduling, optimizer transitions, and stopping. At the transition to Adam, training reloads the development-selected best model.

The first recorded training loss is at update 20, before development evaluation at update 100. Each recorded value is the current minibatch’s total normalized loss, including arc, relation, and auxiliary terms, rather than an isolated hinge value.

Structured-hinge training Let T∗∈T1T^* \in\mathcal{T}_1 be the gold tree and write S(T)=∑(i,j)∈TS[i,j]S(T) = \sum_{(i,j)\in T} S[i,j]. The margin-rescaled structured hinge is [15, 14]

L(S,T∗)=max⁡T∈T1[S(T)+Δ(T,T∗)]−S(T∗).(7)L(S,T^*) = \max_{T\in\mathcal{T}_1} \left[S(T) + \Delta(T,T^*)\right] - S(T^*). \tag*{(7)}

Here Δ\Delta is μ≥0\mu\ge0 times the number of incorrect heads. Gold-tree feasibility gives L≥0L \ge0. Loss-augmented inference uses

S~[i,j]=S[i,j]+μ 1[(i,j)∉T∗](8)\widetilde{S}[i,j] = S[i,j] + \mu\,1[(i,j) \notin T^*] \tag*{(8)}

on admissible arcs; forbidden arcs remain excluded. Before inference, column-wise log-softmax is applied to the augmented matrix. It subtracts a constant from each dependent column and therefore preserves all maximizing trees in exact arithmetic. Both oracle implementations use this normalization; identical normalized inputs are assumed in the equivalence theorem below.

The maximizing tree T^\widehat{T} is selected outside automatic differentiation. Evaluating the loss from the original neural scores while holding T^\widehat{T} fixed gives the score subgradient

g[i,j]=1[(i,j)∈T^]−1[(i,j)∈T∗](9)g[i,j] = 1[(i,j) \in\widehat{T}] - 1[(i,j) \in T^*] \tag*{(9)}

on admissible score coordinates.

Theorem 3 (Structured-hinge equivalence). Suppose both oracles receive identical scores, gold tree, margin, and admissible arcs, and the common normalized loss-augmented matrix satisfies the hypotheses of Theorem 2. In exact arithmetic,

Bock and CL/E compute the same value of (7). Every selected maximizer gives a valid score subgradient, and a unique loss-augmented optimum forces the same selected score subgradient.

Proof. Normalization preserves the maximizing trees, and Theorem 2 makes both oracles exact over the same tree family. They therefore attain the same loss-augmented optimum. The affine objective associated with a selected maximizer equals the hinge at the current scores and lies below it everywhere, so its slope (9) is a subgradient. Distinct maximizing trees have distinct arc indicators, while uniqueness forces the same choice.

Matching initial model and optimizer states, minibatches, stochastic and numerical computations, auxiliary losses, selected score subgradients, update rules, and development-dependent decisions yields identical training trajectories: equal states give equal forward computations, parameter gradients, and updates, so induction preserves equality.

Evaluation We compute UAS and LAS with the bundled CoNLL 2018 evaluator (Zeman et al., 2018). Scoring uses integer-ID tokens, includes punctuation, and excludes the artificial ROOT. LAS ignores dependency-relation subtypes. LCM applies the same label convention and counts a sentence as correct exactly when every scored token has both the correct head and the correct base dependency relation.

We reevaluate the saved test predictions without retraining, verify their token alignment with the gold files, and check attachment counts against the evaluator. Per-seed rates are computed from integer counts. Means and sample standard deviations are calculated from full-precision rates and rounded only for presentation.

For CTB, the reformulated-Bock-hinge minus CL/E-hinge LAS differences are +1.32, −0.22, and +1.25 percentage points for seeds 1111, 2222, and 3333, respectively. The higher aggregate mean therefore includes one paired run with lower LAS.

Comparison with earlier structured-hinge experiments Earlier biaffine-parser experiments compare Local-Prob with Global-NProj-Hinge, using CL/E for nonprojective structured inference (Zhang et al., 2019). On PTB, their LAS/LCM scores are 93.75/46.65 for Local-Prob and 93.91/47.78 for Global-NProj-Hinge. On CTB, the corresponding scores are 88.16/33.16 and 87.92/32.77.

The earlier models use fastText embeddings and character CNNs, combine arc and label scores, and use predicted PTB POS tags (Zhang et al., 2019). They exclude punctuation in PTB and CTB evaluation, whereas our main results include it.

We additionally reevaluate our saved predictions using the earlier POS-based punctuation exclusions. For PTB, excluded gold XPOS tags are “,”, “:”, “,”, and “.”; for CTB, the excluded tag is PU. All test sentences are retained.

Under these exclusions, PTB local CE obtains 95.10 LAS and 57.71 LCM, compared with 95.02 LAS and 56.91 LCM for CL/E hinge. CTB local CE obtains 90.56 LAS and 44.24 LCM, compared with 90.61 LAS and 43.73 LCM for CL/E hinge. Punctuation exclusion preserves the directions of these within-study differences. These are alternative evaluations of the same saved predictions.

References

  1. [1]Frederick C. Bock. 1971. An algorithm to construct a minimum directed spanning tree in a directed network. In Benjamin Avi-Itzhak, editor, Developments in Operations Research: Proceedings of the Third Annual Israel Conference on Operations Research, pages 29–44. Gordon and Breach, New York.
  2. [2]Maximilian Böther, Otto Kißig, and Christopher Weyand. 2023. Efficiently Computing Directed Minimum Spanning Trees. In 2023 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX), pages 86–95. Society for Industrial and Applied Mathematics, Florence, Italy.arxiv.org/abs/2208.02590
  3. [3]Paolo M. Camerini, Luigi Fratta, and Francesco Maffioli. 1979. A note on finding optimum branchings. Networks, 9(4):309–312.DOI
  4. [4]Yoeng-Jin Chu and Tseng-Hong Liu. 1965. On the Shortest Arborescence of a Directed Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019. BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding. In Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers), pages 4171–4186, Minneapolis, Minnesota. Association for Computational Linguistics.
  5. [5]Timothy Dozat and Christopher D. Manning. 2017. Deep Biaffine Attention for Neural Dependency Parsing. In Proceedings of the 5th International Conference on Learning Representations (ICLR 2017), Toulon, France. The International Conference on Learning Representations (ICLR).
  6. [6]Jack R. Edmonds. 1967. Optimum Branchings. Journal of Research of the National Bureau of Standards, 71B:233–240.DOI
  7. [7]Mitchell P. Marcus, Mary Ann Marcinkiewicz, and Beatrice Santorini. 1993. Building a Large Annotated Corpus of English: The Penn Treebank. Computational linguistics, 19(2):313–330.
  8. [8]Marie-Catherine de Marneffe, Bill MacCartney, and Christopher D. Manning. 2006. Generating Typed Dependency Parses from Phrase Structure Parses. In Proceedings of the Fifth International Conference on Language Resources and Evaluation (LREC’06), Genoa, Italy. European Language Resources Association (ELRA).DOI
  9. [9]Ryan McDonald, Fernando Pereira, Kiril Ribarov, and Jan Hajič. 2005. Non-Projective Dependency Parsing using Spanning Tree Algorithms. In Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing, pages 523–530, Vancouver, British Columbia, Canada. Association for Computational Linguistics.DOI
  10. [10]Peng Qi, Yuhua Zhang, Yuhui Zhang, Jason Bolton, and Christopher D. Manning. 2020. Stanza: A Python Natural Language Processing Toolkit for Many Human Languages. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics: System Demonstrations, pages 101–108, Online. Association for Computational Linguistics.arxiv.org/abs/2003.07082
  11. [11]Sebastian Schuster and Christopher D. Manning. 2016. Enhanced English Universal Dependencies: An Improved Representation for Natural Language Understanding Tasks. In Proceedings of the Tenth International Conference on Language Resources and Evaluation (LREC 2016), Paris, France. European Language Resources Association (ELRA).DOI
  12. [12]Miloš Stanojević and Shay B Cohen. 2021. A Root of a Problem: Optimizing Single-Root Dependency Parsing. In Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing, pages 10540–10557, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
  13. [13]Robert Endre Tarjan. 1977. Finding Optimum Branchings. Networks, 7(1):25–35.DOI
  14. [14]Ben Taskar, Dan Klein, Mike Collins, Daphne Koller, and Christopher D. Manning. 2004. Max-Margin Parsing. In Proceedings of EMNLP 2004, pages 1–8, Barcelona, Spain. Association for Computational Linguistics.
  15. [15]Ioannis Tsochantaridis, Thomas Hofmann, Thorsten Joachims, and Yaserim Altun. 2004. Support vector machine learning for interdependent and structured output spaces. In Proceedings of the Twenty-first International Conference on Machine Learning (ICML 2004), Banff, Alberta, Canada.
  16. [16]Nianwen Xue. 2007. Tapping the Implicit Information for the PS to DS Conversion of the Chinese Treebank. In Proceedings of the Sixth International Workshop on Treebanks and Linguistic Theories, pages 189–200, Bergen, Norway. Northern European Association for Language Technology (NEALT).
  17. [17]Nianwen Xue, Fei Xia, Fu-dong Chiou, and Marta Palmer. 2005. The Penn Chinese TreeBank: Phrase Structure Annotation of a Large Corpus. Natural Language Engineering, 11(2):207–238.DOI

Paper details

vlnc:W_weumrapg
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 11

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

OpenAI ChatGPT, Codex

View statement
Looking for related papers…
Contents