---
title: "Graph-Based and Neural Dependency Parsing"
module: Linguistic Structure
moduleNumber: 6
lessonNumber: 4
order: 604
summary: >
  Greedy transition parsing commits locally; the graph-based family scores whole
  trees instead. This lesson scores every candidate head-dependent edge and extracts
  the maximum spanning tree with Chu-Liu/Edmonds, develops the biaffine neural scorer
  that made graph-based parsing the accuracy leader, evaluates parsers with the
  unlabeled and labeled attachment scores (UAS and LAS), and closes on where the two
  parser families sit and what they feed downstream.
topics: [Structure]
sources:
  - book: Jurafsky
    ref: "Ch. 14 — Dependency Parsing; §14.5 Graph-Based Dependency Parsing; §14.6 Evaluation"
---

This builds on [dependency parsing](/natural-language-processing/linguistic-structure/dependency-parsing),
which fixed the dependency-tree formalism and built the transition-based parser — a
greedy, linear-time stack-and-buffer machine. That family is fast but limited; the
graph-based family scores whole trees instead, at a higher cost, which is where we
pick up.

## Graph-based parsing

Greedy transition parsing has two weaknesses: it commits locally, so a mistake is
irreversible, and it cannot produce non-projective trees. **Graph-based** parsing
fixes both by scoring _whole trees_ rather than local decisions.[^jm-graph] It is
more accurate than transition-based parsing on long sentences, where a head can sit
far from its dependent, and it produces non-projective trees for free.

The search is over $\mathcal{G}_S$, the space of all trees for a sentence $S$:

$$
\hat{T}(S) = \argmax_{t \in \mathcal{G}_S} \Score(t, S).
$$

To make that argmax tractable we assume the score is **edge-factored** — the tree's
score is the sum of independent edge scores:

$$
\Score(t, S) = \sum_{e \in t} \Score(e).
$$

Under this assumption the parser has two jobs: (1) assign a score to every possible
edge, and (2) find the best tree given those scores.

### Maximum spanning tree

Build a fully-connected weighted directed graph: one vertex per word plus
$\text{ROOT}$, and a scored edge for every possible head-dependent pair (with
$\text{ROOT}$ having outgoing edges only). A **spanning tree** of this graph that
starts from $\text{ROOT}$ is exactly a valid parse, and the highest-scoring one —
the **maximum spanning tree** — is the optimal parse.[^jm-mst]

$$
% caption: The scored graph for "Book that flight": every word can be any other
% word's head, so ROOT and each word send an edge to each other word. The maximum
% spanning tree (blue) is the optimal parse.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  w/.style={draw, minimum width=13mm, minimum height=7mm, font=\small},
  sc/.style={font=\scriptsize, text=black}]
  \definecolor{acc}{HTML}{2348F2}
  \node[w] (root) at (0,0)   {root};
  \node[w] (book) at (3.2,0) {Book};
  \node[w] (that) at (6.6,1.3) {that};
  \node[w] (fl)   at (6.6,-1.3) {f\/light};
  % chosen (MST) edges in blue
  \draw[->, acc, thick] (root.east) -- node[sc, text=acc, above]{12} (book.west);
  \draw[->, acc, thick] (book.east) to[bend right=10] node[sc, text=acc, above=1pt]{7} (fl.north west);
  \draw[->, acc, thick] (fl.north) to[bend right=25] node[sc, text=acc, right]{8} (that.south);
  % other candidate edges (muted)
  \draw[->, black] (root.north east) to[bend left=22] node[sc, above]{4} (that.west);
  \draw[->, black] (root.south east) to[bend right=22] node[sc, below]{4} (fl.west);
  \draw[->, black] (book.north) to[bend left=18] node[sc, left]{6} (that.south west);
  \draw[->, black] (that.south) to[bend left=18] node[sc, left]{5} (fl.north);
\end{tikzpicture}
$$

The **Chu-Liu/Edmonds** algorithm finds it. The idea rests on two facts. First,
every vertex of a spanning tree has exactly one incoming edge, so a natural first
move is greedy: for each vertex, keep only its single highest-scoring incoming
edge. Second, only the _relative_ weights of edges entering a vertex matter —
subtracting a constant from every edge into a vertex leaves the maximum spanning
tree unchanged. If greedy selection happens to yield a tree, it is optimal. When it
instead produces a **cycle**, the algorithm re-scores (subtract each vertex's best
incoming score from all its incoming edges, zeroing the selected ones), contracts
the cycle into a single node, and recurses on the smaller graph; expanding the
contracted node afterward reveals which single cycle edge to delete.[^jm-mst]

```algorithm
caption: $\textsc{Max-Spanning-Tree}(G, root, score)$ — Chu-Liu/Edmonds
$F \gets \{\}$ // one best incoming edge per vertex
for each $v \in V$ do
  $bestInEdge \gets \argmax_{e = (u,v) \in E} score[e]$
  $F \gets F \cup \{bestInEdge\}$
  for each $e = (u,v) \in E$ do
    $score'[e] \gets score[e] - score[bestInEdge]$ // re-score relative to best
if $(V, F)$ is a spanning tree then
  return $(V, F)$
$C \gets$ a cycle in $F$
$G' \gets \textsc{Contract}(G, C)$ // collapse the cycle to one node
$T' \gets \textsc{Max-Spanning-Tree}(G', root, score')$ // recurse
$T \gets \textsc{Expand}(T', C)$ // restore cycle, drop one edge
return $T$
```

On the fully connected graph the number of edges is $m = n^2$, and this version of
the algorithm runs in $O(mn) = O(n^3)$ time; faster implementations reach
$O(m + n\log n)$. Nothing in the procedure references word order, so the
maximum spanning tree may cross itself — that is, graph-based parsing produces
**non-projective** trees whenever the scores favor them, which is precisely what
transition-based parsing cannot do.

### A worked Chu-Liu/Edmonds trace

The one-line description of the algorithm hides the interesting case — the cycle — so
work it through on real numbers. Take three words $a$, $b$, $c$ plus $\text{ROOT}$,
with these edge scores (only the relevant edges shown):

$$
% caption: The scored graph for the trace. ROOT reaches a (score 9) and b (score
% 10); the words score edges among themselves. Greedy selection of each vertex's
% best incoming edge will produce a b <-> c cycle, forcing a contraction.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  w/.style={draw, circle, minimum size=9mm, font=\small},
  sc/.style={font=\scriptsize, text=black}]
  \definecolor{acc}{HTML}{2348F2}
  \node[w] (root) at (0,0)    {root};
  \node[w] (a)    at (2.8,1.5) {a};
  \node[w] (b)    at (2.8,-1.5) {b};
  \node[w] (c)    at (6.0,0)   {c};
  \draw[->, black] (root) -- node[sc, above left]{9} (a);
  \draw[->, black] (root) -- node[sc, below left]{10} (b);
  \draw[->, black] (a) to[bend left=12] node[sc, right]{20} (c);
  \draw[->, black] (c) to[bend left=12] node[sc, left]{30} (b);
  \draw[->, black] (b) to[bend right=45] node[sc, below]{31} (c);
  \draw[->, black] (a) to[bend right=12] node[sc, left]{3} (b);
\end{tikzpicture}
$$

**Round 1 — greedy selection.** For each non-root vertex keep only its single
highest-scoring incoming edge. Vertex $a$'s best incoming edge is $\text{ROOT}\to a$
(9). Vertex $b$'s best is $c \to b$ (30, beating $\text{ROOT}\to b$ at 10 and
$a\to b$ at 3). Vertex $c$'s best is $b \to c$ (31, beating $a\to c$ at 20). The
selected set is $\{\text{ROOT}\to a,\; c\to b,\; b\to c\}$ — and $b \to c \to b$ is a
**cycle**. Not a tree, so recurse.

**Re-score.** Subtract each vertex's best incoming score from all edges into that
vertex, which zeroes the selected edge and makes every other incoming edge negative
by its shortfall. Into $b$: $c\to b$ becomes $30-30=0$, $\text{ROOT}\to b$ becomes
$10-30=-20$, $a\to b$ becomes $3-30=-27$. Into $c$: $b\to c$ becomes $31-31=0$,
$a\to c$ becomes $20-31=-11$. Into $a$: only $\text{ROOT}\to a$, now $0$.

**Contract.** Collapse the cycle $\{b,c\}$ into one node $bc$. An edge entering the
cycle from outside now enters $bc$ with its _re-scored_ weight: $\text{ROOT}\to b$
gives $\text{ROOT}\to bc$ a score of $-20$; $a\to c$ gives $a\to bc$ a score of
$-11$. Edges leaving the cycle keep their original scores.

$$
% caption: After contracting the b-c cycle into one node bc. The re-scored
% edges entering bc are ROOT -> bc (-20) and a -> bc (-11); the recursion now runs
% on this smaller three-node graph and picks the least-bad entry point.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  w/.style={draw, circle, minimum size=9mm, font=\small},
  sc/.style={font=\scriptsize, text=black}]
  \definecolor{acc}{HTML}{2348F2}
  \node[w] (root) at (0,0)   {root};
  \node[w] (a)    at (3.0,1.3) {a};
  \node[w, draw=acc, text=acc] (bc) at (5.6,-0.6) {bc};
  \draw[->, acc, thick] (root) -- node[sc, text=acc, above left]{9} (a);
  \draw[->, black] (root) to[bend right=18] node[sc, below]{-20} (bc);
  \draw[->, acc, thick] (a) -- node[sc, text=acc, right]{-11} (bc);
\end{tikzpicture}
$$

**Recurse and expand.** On the contracted graph, $a$'s best incoming edge is
$\text{ROOT}\to a$ (0) and $bc$'s best is $a\to bc$ ($-11$, since $-11 > -20$). Those
two form a spanning tree of the small graph, so the recursion returns
$\{\text{ROOT}\to a,\; a\to bc\}$. Now **expand** $bc$ back into $b$ and $c$. The edge
into the cycle was $a\to bc$, which came from $a\to c$, so $c$'s head is $a$; that
breaks the cycle exactly at $c$, meaning we _delete_ the cycle edge $b\to c$ and
_keep_ $c\to b$. The final tree is

$$
\text{ROOT}\to a, \qquad a\to c, \qquad c\to b,
$$

with total score $9 + 20 + 30 = 59$. The greedy edge ($b\to c$ at 31) was
dropped because keeping it would leave a cycle; the
contraction found the best _tree_, not the best set of local edges.

### Scoring the edges

The remaining job is scoring an edge. A **feature-based** scorer writes each edge
score as a weighted sum of features — word forms, lemmas, and parts of speech of
the head and dependent, features of the words between and around them, the
candidate relation, its direction, and the head-to-dependent distance:

$$
\score(S, e) = \sum_{i=1}^{N} w_i\, f_i(S, e) = \mathbf{w} \cdot \mathbf{f}.
$$

The weights are trained not to predict a class but to score correct trees above
incorrect ones — **inference-based learning** with the perceptron rule: parse a
training sentence, and if the predicted tree is wrong, lower the weights of the
features present in the wrong parse but absent from the gold parse.[^jm-graph]

A **biaffine** neural scorer is the modern state of the art.[^jm-biaffine] Encode
the sentence once into contextual embeddings $r_1, \ldots, r_n$. For each token,
two feedforward networks produce a **head** representation and a **dependent**
representation:

$$
h_i^{\text{head}} = \FFN_{\text{head}}(r_i), \qquad
h_j^{\text{dep}} = \FFN_{\text{dep}}(r_j).
$$

The score of the directed edge $i \to j$ (head $i$, dependent $j$) is a **biaffine**
function, which mixes a bilinear term (multiplicative interaction) with a linear
term and a bias:

$$
\Score(i \to j) = \mathbf{x}^\top U \mathbf{y} + W(\mathbf{x} \oplus \mathbf{y}) + b,
\qquad \mathbf{x} = h_i^{\text{head}},\ \ \mathbf{y} = h_j^{\text{dep}},
$$

with learned $U$, $W$, $b$. A softmax over all candidate heads $i$ of a fixed
dependent $j$ turns these scores into $p(i \to j)$, trained with cross-entropy; the
resulting scores feed the maximum-spanning-tree extractor.

$$
% caption: The biaffine edge scorer of Dozat and Manning. Each encoded token feeds
% a head-FFN and a dependent-FFN; the biaffine function combines the head vector of
% i with the dependent vector of j into a score for the edge i -> j.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  tok/.style={draw, minimum width=11mm, minimum height=6mm, font=\scriptsize},
  ffn/.style={draw, minimum width=14mm, minimum height=6mm, font=\scriptsize},
  box/.style={draw, minimum width=18mm, minimum height=8mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[tok] (b)  at (0,0)   {book};
  \node[tok] (fl) at (4.4,0) {f\/light};
  \node[ffn] (bh) at (-0.9,1.4) {FFN-head};
  \node[ffn] (fd) at (5.3,1.4)  {FFN-dep};
  \draw[->] (b.north) -- (bh.south);
  \draw[->] (fl.north) -- (fd.south);
  \node[box, draw=acc, text=acc, thick] (bi) at (2.2,2.9) {Bia\/f\/f\/ine};
  \draw[->, thick] (bh.north) to[bend left=12] (bi.west);
  \draw[->, thick] (fd.north) to[bend right=12] (bi.east);
  \node[box, minimum width=32mm] (out) at (2.2,4.3) {score(book $\to$ f\/light)};
  \draw[->, acc, thick] (bi.north) -- (out.south);
\end{tikzpicture}
$$

The full labeled biaffine parser trains **two** classifiers: an edge-scorer, which
picks the tree structure via maximum spanning tree, and a separate label-scorer of
the same form, which assigns the best relation to each edge in that tree.

## Evaluation

An exact-match metric — how many sentences are parsed perfectly — is too pessimistic
to guide development, since one wrong arc condemns a whole sentence. Dependency
parsers are scored at the level of individual words with **attachment accuracy**:
the fraction of words assigned the correct head.[^jm-eval]

> **Definition (Attachment scores).** **Unlabeled attachment score (UAS)** is the
> percentage of words assigned the correct head, ignoring the relation. **Labeled
> attachment score (LAS)** is the percentage assigned both the correct head _and_
> the correct relation. LAS $\le$ UAS always, since a labeled match implies an
> unlabeled one.

Compare a reference and a system parse of `Book me the flight through Houston`,
which has six scored words.

$$
% caption: Reference (top) and system (bottom) parses for "Book me the flight
% through Houston". The system gets 5 of 6 heads right (UAS 5/6) but only 4 of 6
% head+label pairs (LAS 4/6): it mislabels the me arc and reattaches book -> me.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  w/.style={font=\small, inner sep=1.5pt},
  a/.style={->, thick, shorten <=2pt, shorten >=2pt},
  rel/.style={font=\scriptsize, text=black}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % --- Reference ---
  \node[font=\scriptsize\bfseries, anchor=west] at (-0.2,2.5) {Reference};
  \node[w] (Rb)  at (0,0)   {Book};
  \node[w] (Rm)  at (1.7,0) {me};
  \node[w] (Rt)  at (3.2,0) {the};
  \node[w] (Rf)  at (4.7,0) {f\/light};
  \node[w] (Rth) at (6.5,0) {through};
  \node[w] (Rh)  at (8.5,0) {Houston};
  \draw[a, acc] (0,2.0) -- (0,0.45);
  \node[rel, text=acc] at (0,2.2) {root};
  \draw[a] (Rb.north) to[bend left=52] (Rm.north);
  \node[rel] at (0.85,0.9) {iobj};
  \draw[a] (Rb.north) to[bend left=26] (Rf.north);
  \node[rel] at (2.3,1.55) {obj};
  \draw[a] (Rf.north) to[bend left=52] (Rt.north);
  \node[rel] at (4.0,0.75) {det};
  \draw[a] (Rf.north) to[bend left=30] (Rh.north);
  \node[rel] at (6.6,1.15) {nmod};
  \draw[a] (Rh.north) to[bend left=52] (Rth.north);
  \node[rel] at (7.5,0.8) {case};
  % --- System ---
  \begin{scope}[yshift=-3.8cm]
  \node[font=\scriptsize\bfseries, anchor=west] at (-0.2,2.5) {System};
  \node[w] (Sb)  at (0,0)   {Book};
  \node[w] (Sm)  at (1.7,0) {me};
  \node[w] (St)  at (3.2,0) {the};
  \node[w] (Sf)  at (4.7,0) {f\/light};
  \node[w] (Sth) at (6.5,0) {through};
  \node[w] (Sh)  at (8.5,0) {Houston};
  \draw[a, acc] (0,2.0) -- (0,0.45);
  \node[rel, text=acc] at (0,2.2) {root};
  % wrong: me attaches to flight with nsubj (wrong head AND label)
  \draw[a, red] (Sf.north) to[bend left=40] (Sm.north);
  \node[rel, text=red] at (3.3,1.15) {nsubj};
  \draw[a] (Sb.north) to[bend left=26] (Sf.north);
  \node[rel] at (2.3,1.7) {obj};
  \draw[a] (Sf.north) to[bend left=52] (St.north);
  \node[rel] at (4.0,0.75) {det};
  \draw[a] (Sf.north) to[bend left=30] (Sh.north);
  \node[rel] at (6.6,1.15) {nmod};
  \draw[a] (Sh.north) to[bend left=52] (Sth.north);
  \node[rel] at (7.5,0.8) {case};
  \end{scope}
\end{tikzpicture}
$$

The system attaches five of the six words to the correct head — every word except
`me`, which it hangs off `flight` instead of `Book`. That is a **UAS of 5/6**. Of
those five, one more is labeled wrong (in Jurafsky & Martin's version the `book` $\to$
`flight` arc is present but mislabeled), so four words have both the right head and
the right label: an **LAS of 4/6**.[^jm-eval] A third figure, **label accuracy (LS)**,
counts correct labels regardless of attachment. Per-relation **precision and recall**
(how many `nsubj` arcs the system proposed were right, how many gold `nsubj` arcs it
found) diagnose which relations a parser handles poorly, and a confusion matrix
shows which relations it swaps.

## Neural dependency parsers

Jurafsky & Martin describe the neural oracle and the biaffine scorer in outline; the papers
that introduced them are worth reading in their own right, because each fixed a
concrete failure of the linear-model parsers that preceded it.

**Chen and Manning (2014)** built the first neural transition-based parser and
reported the result that started the shift.[^cm2014] Feature-based oracles spend most
of their time not on classification but on **feature extraction**: instantiating and
looking up millions of sparse, hand-conjoined indicator features (the $s_1.t \circ
s_2.t$ templates), which the authors measured at over 95% of parse time. Their model
replaces those templates with dense embeddings of a fixed set of stack and buffer
positions — words, part-of-speech tags, and already-assigned arc labels — concatenated
and passed through a single hidden layer with a cube activation $g(x)=x^3$, chosen so
the hidden units mix triples of inputs and so recover feature conjunctions
automatically. On the English Penn Treebank it reached 92.0 UAS / 89.7 LAS while
parsing over 1000 sentences per second, both faster and more accurate than the
sparse-feature parsers, and it did so with no manually specified feature
combinations.[^cm2014] The lesson others took from it: the value of the sparse
templates was the _conjunctions_, and a small network learns those from embeddings.

**Dozat and Manning (2017)** produced the biaffine graph-based parser sketched
above, and it remains a strong baseline.[^dm2017] Two design choices carry the
result. First, before the biaffine scorer, each token's encoder state passes through
a small feedforward network that strips it down to just the information needed for
head-or-dependent decisions — the recurrence carries a lot of tagging and
morphological detail the arc decision does not need. Second, the scoring is
genuinely **biaffine** rather than a plain bilinear form: the extra linear term
$W(\mathbf{x}\oplus\mathbf{y})$ lets the model capture the prior probability that a
given word is a head at all, independent of the candidate dependent, which a pure
$\mathbf{x}^\top U\mathbf{y}$ cannot express. On the standard English benchmark the
parser reached about 95.7 UAS / 94.1 LAS, then state of the art, and the same
architecture won or placed near the top across dozens of languages in the CoNLL 2017
multilingual shared task.[^dm2017] Feed it a modern pretrained encoder in place of
its biLSTM and the numbers climb further.

Two directions extend these. **Kiperwasser and Goldberg (2016)** showed that a
biLSTM feature extractor could be shared and trained jointly for _both_ the
transition-based and graph-based parsers, closing much of the gap between the two
families and making clear that the encoder, not the inference algorithm, was doing
most of the work.[^kg2016] And once large pretrained encoders arrived, the trend was
to **drop explicit parsing structure**: some systems predict each word's head by a
softmax over positions with no tree constraint at all and only project to a valid
tree at decode time, while others question whether an explicit parse is needed
downstream when a transformer's attention already encodes much syntactic
structure.[^hewitt2019] The parser families in this lesson did not disappear — the
biaffine scorer plus Chu-Liu/Edmonds is still how you get a guaranteed well-formed
tree — but the balance of effort moved decisively from the inference algorithm to the
representation it scores.

## Where this sits

Dependency parsing trades the constituency tree's phrasal structure for a flatter,
lexical picture that puts predicate-argument relations on the surface — the input
the next stage needs. Both parser families are supervised, both
learn from treebanks (built by hand for morphologically rich languages, or
converted from
[constituency treebanks](/natural-language-processing/linguistic-structure/constituency-parsing)
by head rules for English), and both now run on neural encoders. Transition-based
parsing wins on speed with its linear greedy pass; graph-based parsing wins on
accuracy and on non-projective languages by scoring whole trees. The typed arcs
they produce — `nsubj`, `dobj`, and the rest — are the scaffold on which
[semantic roles and information extraction](/natural-language-processing/linguistic-structure/semantic-roles-and-information-extraction)
read off who did what to whom.

[^jm-intro]: **Jurafsky & Martin**, _Speech and Language Processing_ (3rd ed.), Ch. 14 — Dependency Parsing: dependency grammar describes syntax with directed binary grammatical relations from heads to dependents, with no phrasal constituents, and its abstraction from word order suits free-word-order and morphologically rich languages.
[^jm-graph]: **Jurafsky & Martin**, §14.5 — Graph-Based Dependency Parsing: edge-factored scoring, why graph-based parsers beat transition-based ones on long sentences and produce non-projective trees, and the feature-based edge scorer trained by inference-based perceptron learning.
[^jm-mst]: **Jurafsky & Martin**, §14.5.1 — Parsing via finding the maximum spanning tree: the fully connected rooted score graph, the equivalence of best parse and maximum spanning tree, and the Chu-Liu/Edmonds greedy-selection, re-scoring, contract-and-recurse algorithm running in $O(n^3)$ here.
[^jm-biaffine]: **Jurafsky & Martin**, §14.5.3 — A neural algorithm for assigning scores: the biaffine parser of Dozat and Manning, separate head and dependent feedforward networks, the biaffine scoring function $\mathbf{x}^\top U \mathbf{y} + W(\mathbf{x}\oplus\mathbf{y}) + b$, and its separate edge-scorer and label-scorer.
[^jm-eval]: **Jurafsky & Martin**, §14.6 — Evaluation: unlabeled and labeled attachment scores (UAS and LAS), the worked Book me the flight through Houston example giving LAS 4/6 and UAS 5/6, label accuracy, and per-relation precision, recall, and confusion matrices.
[^cm2014]: **Chen & Manning (2014)**, "A Fast and Accurate Dependency Parser using Neural Networks," EMNLP 2014. The first neural transition-based parser: dense embeddings of a fixed set of stack/buffer word, POS, and label positions through a cube-activation hidden layer, replacing sparse feature templates; ~92.0 UAS / 89.7 LAS on the English Penn Treebank at over 1000 sentences/second. They report that feature extraction, not classification, dominated the runtime of prior sparse-feature parsers.
[^kg2016]: **Kiperwasser & Goldberg (2016)**, "Simple and Accurate Dependency Parsing Using Bidirectional LSTM Feature Representations," TACL. A shared biLSTM feature extractor trained jointly with either a transition-based or a graph-based parser, showing the encoder does most of the work and narrowing the gap between the two parser families.
[^dm2017]: **Dozat & Manning (2017)**, "Deep Biaffine Attention for Neural Dependency Parsing," ICLR 2017. The biaffine graph-based parser: per-token head/dependent feedforward reductions of a biLSTM encoding, a biaffine edge scorer mixing a bilinear term with a linear (head-prior) term, and a separate biaffine label scorer; about 95.7 UAS / 94.1 LAS on English, and top results across languages in the CoNLL 2017 shared task.
[^hewitt2019]: **Hewitt & Manning (2019)**, "A Structural Probe for Finding Syntax in Word Representations," NAACL 2019, showed that pretrained transformer representations linearly encode dependency-tree distances; together with graph-based decoders that predict heads by position-softmax and only project to a valid tree at decode time, this reflects the field's shift of effort from the inference algorithm to the learned representation.