In most introductory linguistics classes, we are taught that sentences have a nested, hierarchical structure. We draw trees where branches never cross, a property known as projectivity. For many languages like English, this assumption holds most of the time. However, in languages with flexible word order—such as Hindi, Turkish, or Dutch—grammatical relationships frequently "cross" one another.
When a dependency arc between a head and its dependent crosses another arc, the structure becomes non-projective. Modeling these crossing dependencies is not just a theoretical curiosity; it is a computational necessity for capturing the full range of human expression.
The Geometry of Crossing Arcs
To understand why non-projectivity is difficult, imagine a sentence as a sequence of points on a line. In a projective tree, if you draw an arc between two words, every word underneath that arc must be a descendant of the head. This "no-crossing" rule allows parsers to use efficient dynamic programming or simple stack-based algorithms.
But as Prashanth Mannem, Himani Chaudhry, and Akshar Bharati observed in Insights into Non-projectivity in Hindi, roughly 14% of Hindi sentences contain non-projective links. These often occur due to "extraposed" clauses, where a relative clause is moved to the end of a sentence, far from the noun it modifies. Standard parsers, optimized for English-like nesting, simply cannot "see" these long-distance, crossing relationships.
Transitioning Beyond the Stack
Traditional transition-based parsers use a stack and a buffer to build trees in a single linear pass. This is fast ($O(n)$) but inherently projective. To handle crossing arcs, researchers have had to rethink the fundamental "moves" a parser can make.
One elegant solution is the Covington parser, which relaxes the stack constraint to allow comparisons between the current word and any previous word in the sentence. Carlos Gómez-Rodríguez and Daniel Fernández-González have pushed this further. In Non-Projective Dependency Parsing with Non-Local Transitions, they introduced "jumps" that allow the parser to skip over local words to find a non-local head in a single step.
To make these parsers smarter, they developed dynamic oracles (An Efficient Dynamic Oracle for Unrestricted Non-Projective Parsing). Usually, a parser is trained only on "correct" paths. A dynamic oracle allows the parser to make a mistake during training and then calculates the best possible way to finish the tree from that "broken" state, teaching the model how to recover from the ambiguities inherent in flexible word order.
Graph-Based Global Optimization
If transition-based parsing is like building a bridge piece-by-piece, graph-based parsing is like looking at all possible connections at once and picking the best set. This is often framed as finding a Maximum Spanning Tree (MST).
Because an MST algorithm considers every possible edge between every pair of words, it doesn't care if the edges cross. Keith B. Hall demonstrated in K-best Spanning Tree Parsing that even if a simple model struggles to rank the correct non-projective tree first, the "true" tree is almost always within the top 50 candidates.
For even more complex constraints, researchers turn to combinatorial optimization. Alexander M Rush and Michael Collins utilized Dual Decomposition (Dual Decomposition for Parsing with Non-Projective Head Automata) to solve non-projective parsing. Their intuition was to split the hard problem into two easier sub-problems—one that ensures every word has a head, and another that ensures the result is a valid tree—and then iteratively force the two solutions to agree.
Neural Refinement and Iterative Polishing
Modern deep learning has shifted the focus from manual feature engineering to global context. The DENSE model, proposed by Xingxing Zhang and Mirella Lapata, simplifies the problem by treating parsing as "head selection" (Dependency Parsing as Head Selection). By using powerful bi-directional LSTMs to encode the entire sentence, the model can independently pick the most likely parent for each word. Surprisingly, this simple approach produces valid, often non-projective trees 95% of the time without any explicit tree constraints.
The latest frontier involves iterative refinement. In Recursive Non-Autoregressive Graph-to-Graph Transformer for Dependency Parsing with Iterative Refinement, Alireza Mohammadshahi and James Henderson introduced a model that predicts an initial graph and then "polishes" it. This allows the model to untangle crossing dependencies by looking at the entire proposed structure and fixing inconsistencies in parallel, rather than committing to a single crossing arc in a vacuum.
Non-Projectivity Beyond the Sentence
The need to handle crossing links extends beyond traditional grammar. In discourse parsing, where we map the relationships between entire sentences in a document, rhetorical links frequently cross. Sujian Li and Wenjie Li showed that treating discourse as a non-projective dependency graph (Text-level Discourse Dependency Parsing) is more flexible and efficient than traditional nested constituency models.
Even in practical information extraction, like analyzing real estate ads, non-projectivity appears. Johannes Deleu found that 26% of relationships in property listings—such as which features belong to which rooms—exhibit crossing links when mapped to the linear text (Structured prediction on real estate classifieds). Whether we are parsing a Dutch novel or a classified ad, the ability to untangle these crossing arcs is what allows machines to move from simple sequences to deep structural understanding.