In dependency parsing, we represent the syntactic structure of a sentence by drawing directed arcs from head words to their dependents. If you lay out the words of a sentence linearly from left to right and draw these arcs as semi-circles above the text, a tree is considered projective if no two arcs cross. Formally, if there is a dependency edge between a head and a dependent, all words occurring between them in the sentence must be descendants of that head.
As Joakim Nivre demonstrated in An Efficient Algorithm for Projective Dependency Parsing, enforcing a strict projectivity constraint allows us to build highly efficient, linear-time deterministic parsing algorithms. However, while this geometric assumption holds reasonably well for languages with rigid word order like English, it breaks down in languages with flexible word order or rich morphology—such as German, Czech, or Dutch.
As Jason Eisner et al. observe in Parsing with Soft and Hard Constraints on Dependency Length, a strict projectivity assumption prevents a model from capturing long-distance, crossing relationships common in free-word-order syntax. Jirí Havelka quantified this limitation in Beyond Projectivity: Multilingual Evaluation of Constraints and Measures on Non-Projective Structures, showing that real-world multilingual corpora require parsers capable of handling non-projective syntax.
The Stack Bottleneck in Transition Parsing
To understand why non-projective structures are difficult to parse, consider how transition-based parsers operate. These systems process a sentence from left to right using a stack (to hold words currently being processed) and a buffer (of remaining words). Standard transition actions—such as Shift, Arc-Left, and Arc-Right—operate strictly on the top elements of the stack.
Because elements are pushed and popped sequentially, the parser can only build nested, non-crossing structures. As Jan Buys et al. explain in Generative Incremental Dependency Parsing with Neural Networks, this reliance on standard stack-based transitions fundamentally locks the system into projective geometries, leaving it structurally blind to crossing dependencies.
To overcome this bottleneck, researchers have developed three primary strategies: global graph optimization, data-driven pseudo-projective transformations, and dynamic transition oracles.
Strategy 1: Global Optimization via Spanning Trees
Instead of building a tree step-by-step using a stack, what if we consider all possible word-to-word connections simultaneously? This is the core intuition behind graph-based dependency parsing.
In Non-Projective Dependency Parsing using Spanning Tree Algorithms, Ryan McDonald et al. reframed dependency parsing as finding a Maximum Spanning Tree (MST) within a fully connected directed graph. In this formulation, every word in a sentence is a node, and every pair of words has a directed, scored edge between them.
Projective Stack Parsing (Local):
[ Stack: Word1, Word2 ] <--- Can only link adjacent/top items
Graph-Based MST Parsing (Global):
Word1 <=======> Word2
\\ // <--- Evaluates all global combinations,
\\ // allowing crossing arcs natively
Word3 <====> Word4
By applying the Chu-Liu-Edmonds algorithm, the parser finds the highest-scoring directed spanning tree. Because this graph formulation scores edges independently of linear word order or adjacency, it can find non-projective trees natively in $O(n^2)$ time. This approach bypasses the projectivity constraint entirely by treating syntax as a global optimization problem over a graph rather than a local sequence of stack operations.
Strategy 2: Pseudo-Projective Transformations
If you want to keep the speed and simplicity of a projective transition parser but still need to handle non-projective data, you can use a data-rewriting strategy known as pseudo-projective parsing.
In Pseudo-Projective Dependency Parsing, Joakim Nivre et al. introduced a clever workaround: instead of modifying the parsing algorithm, they temporarily modify the training data.
- Projectivization (Training): When a training sentence contains a crossing arc, the non-projective edge is "lifted" up the tree. The dependent is detached from its true head and re-attached to a higher ancestor until the crossing disappears. To ensure this structural change can be reversed, the original edge label is augmented with a special tag (e.g.,
arc_label_lifted). - Projective Parsing: A standard, highly efficient projective parser is trained on this modified data. It learns to predict both the structure and the augmented labels.
- De-projectivization (Inference): After the parser outputs a projective tree, a post-processing step reads the augmented tags and uses them as a set of instructions to un-lift the edges, successfully restoring the original non-projective crossing arcs.
Strategy 3: Dynamic Oracles and Exploration
A third approach modifies how transition-based parsers learn to navigate complex structural spaces. Traditional transition parsers are trained using a "static oracle"—a rigid teacher that only knows one perfect path of actions. If the parser makes a single mistake during inference, it lands in a state it has never seen before, causing errors to cascade.
To address this, Yoav Goldberg et al. introduced a framework in A Dynamic Oracle for Arc-Eager Dependency Parsing. A dynamic oracle does not just know the gold path; it can calculate the optimal sequence of actions from any arbitrary, imperfect parser state.
By pairing these dynamic oracles with exploration strategies during training, as Miguel Ballesteros et al. demonstrated in Training with Exploration Improves a Greedy Stack LSTM Parser, greedy parsers learn how to recover from mistakes. This error-recovery capability is crucial when dealing with the structural variations and non-projective movements common in morphologically rich languages.