A tree interpretation of arc standard dependency derivation

Projective arc-standard derivations build constituency-style ordered trees from which the dependency arcs are recoverable

arXiv 2026

Zihao Huang1, Ai Ka Lee1, Jungyeul Park2,*

1The University of British Columbia, Vancouver, Canada 2Korea Advanced Institute of Science & Technology (KAIST), Daejeon, South Korea

*Corresponding author

Paper (arXiv) PDF
Left: dependency graph of 'book me the morning flight' with arcs ROOT to book, book to me (IOBJ), book to flight (DOBJ), flight to the (DET), and flight to morning (COMPOUND). Right: the equivalent ordered tree with ROOT dominating book, an IOBJ node over me, and a DOBJ node over DET (the), COMPOUND (morning), and flight.
Figure 1. A dependency graph (a) and its ordered dependency tree representation (b). book heads the IOBJ (me) and DOBJ (flight) dependents, and flight heads the DET (the) and COMPOUND (morning) dependents. In the ordered tree every subtree covers a contiguous span of the sentence, dependents appear on the same side of their head as in the surface string, and each internal node is anchored by one lexical head.

Abstract

Arc-standard derivations over projective dependency trees can be interpreted as the incremental construction of lexicalized ordered trees with contiguous yields. Each SHIFT, LEFTARC, and RIGHTARC transition corresponds to a deterministic tree update, and the resulting ordered tree uniquely determines the dependency arcs introduced by the derivation. We show that this representation is not an arbitrary encoding: a single-headed dependency tree admits such a contiguous ordered representation if and only if it is projective. The proposal is therefore derivational rather than conversion-based, since the ordered object is defined over the transition sequence itself rather than obtained by transforming a completed dependency graph. This gives a tree-theoretic interpretation of arc-standard parsing, in which projective dependency derivations implicitly construct recoverable constituency-style ordered trees. For non-projective inputs, the interpretation can be used through pseudo-projective lifting and inverse decoding. A small implementation study confirms that the mapped derivations are executable in an existing neural transition-based parser.

Keywords Arc-standard Transition-based parsing Shift-reduce Projectivity Ordered dependency tree Dependency vs. constituency Pseudo-projective lifting Stanza PTB-WSJ

Method

Each arc-standard transition over a stack–buffer configuration is reinterpreted as a deterministic update of partial ordered trees:

  • SHIFT creates a singleton tree anchored at the next buffer token and pushes it onto the stack.
  • LEFTARC (stack [… ti tj], arc j → i) attaches ti as a left dependent subtree of the head-anchored tree tj.
  • RIGHTARC (arc i → j) attaches tj as a right dependent subtree of ti.

The paper proves three properties:

  1. Projective characterization (Theorem 1). A single-headed dependency tree admits a rooted ordered representation with leaves in surface order and contiguous subtree yields if and only if it is projective: crossing arcs would force subtree yields to interleave.
  2. Transition correspondence (Theorem 2). Every arc-standard derivation of a projective tree yields a well-defined ordered tree; each step keeps contiguous yields and a unique lexical anchor.
  3. Recoverability (Theorem 3). The dependency arcs are uniquely recoverable from the final ordered tree, since each combination preserves the head's anchor and adds one dependent subtree.

Non-projective trees are handled in practice by pseudo-projective lifting before derivation and inverse decoding after recovery; the formal claim is specific to the projective case. In the implementation study, the native actions of the Stanza transition-based constituency parser are replaced by SHIFT, LEFTARC, and RIGHTARC; the parser predicts the unlabeled ordered tree, arcs are recovered deterministically, and the Stanza graph-based component assigns only the dependency labels.

Table 2. Arc-standard transition sequence and stack evolution for the running example book me the morning flight (Appendix A of the paper). t′ marks a tree that has absorbed a dependent.
StepStackBufferActionRelation added
0[root][book, me, the, morning, flight]SHIFT
1[root, tbook][me, the, morning, flight]SHIFT
2[root, tbook, tme][the, morning, flight]RIGHTARCbook → me
3[root, t′book][the, morning, flight]SHIFT
4[root, t′book, tthe][morning, flight]SHIFT
5[root, t′book, tthe, tmorning][flight]SHIFT
6[root, t′book, tthe, tmorning, tflight][]LEFTARCflight → morning
7[root, t′book, tthe, t′flight][]LEFTARCflight → the
8[root, t′book, t″flight][]RIGHTARCbook → flight
9[root, t″book][]RIGHTARCroot → book
10[root][]DONE

Main Results

  • Executable in an existing parser. With the mapped transitions in the Stanza constituency parser, dependencies recovered from predicted ordered trees on PTB–WSJ (Stanford Dependencies) reach 95.94 UAS / 94.90 LAS.
  • Usable as a target for other tree parsers. Parsing the same ordered trees with an existing in-order parser (Liu and Zhang, 2017) yields 96.76 UAS / 95.92 LAS, and a linearization parser (Vinyals et al., 2015) yields 96.68 UAS / 95.44 LAS.
  • Not a new architecture. The authors present these numbers only to show that the derivation-induced ordered tree is computationally usable as a tree representation from which dependency arcs are recovered deterministically.
Dependency recovery from predicted ordered trees on PTB–WSJ (Table 1 in the paper; the other two rows are reported in Section 5).
Parser for the ordered treeUASLAS
Stanza transition system with mapped SHIFT / LEFTARC / RIGHTARC95.9494.90
In-order parser (Liu and Zhang, 2017)96.7695.92
Linearization parser (Vinyals et al., 2015)96.6895.44

BibTeX

@misc{huang2026treeinterpretationarcstandard,
      title={A tree interpretation of arc standard dependency derivation}, 
      author={Zihao Huang and Ai Ka Lee and Jungyeul Park},
      year={2026},
      eprint={2603.27459},
      archivePrefix={arXiv},
      primaryClass={cs.CL},
      url={https://arxiv.org/abs/2603.27459}, 
}
More projects from KAIST MLP Lab →