Online Reordering Transitions for Non-Projective Parsing

23 concepts20 papers1 proposal

In natural language processing, transition-based parsers are highly valued for their efficiency. By scanning a sentence from left to right and using a Last-In-First-Out (LIFO) stack, these systems construct syntactic trees in linear time. However, this classic architecture has a fundamental limitation: it can only generate projective trees—structures where dependency arcs do not cross when drawn above the words.

Many human languages feature flexible word order or long-distance extractions that produce non-projective dependencies, where arcs cross. To handle these complex structures without sacrificing the speed and simplicity of transition-based systems, researchers introduced a powerful conceptual shift: instead of changing how the parser draws arcs, the parser can dynamically reorder the words themselves.

The Intuition: Un-Crossing Arcs via Permutation

To understand why online reordering works, imagine a sentence with a crossing dependency as a tangled knot of strings. A standard shift-reduce parser fails because the LIFO stack forces it to resolve dependencies only between the most recently processed, adjacent words.

However, any non-projective tree can be transformed into a projective tree if we permute the linear order of the words in the sentence. If we can find a permutation that groups dependent words together without interleaving unrelated tokens, we can "un-cross" the arcs.

Online reordering transitions embed this sorting mechanism directly into the parsing process. As the parser reads the input sequence, it can choose to temporarily defer a word, allowing later words to pass it. Once the intervening tokens are processed, the deferred word is reintroduced, effectively linearizing a non-projective structure on the fly.

The Mechanism: The SWAP Transition

The standard transition-based framework relies on actions like SHIFT (move a word from the buffer to the stack) and REDUCE (create a dependency arc and remove a word). To enable online reordering, researchers introduced a specialized transition: SWAP.

In the formulation proposed by Nivre (2009), the SWAP transition takes the second-to-top element of the stack and moves it back to the input buffer.

Standard Stack State:  [..., wi, wj]   Buffer: [wk, ...]
After SWAP Transition: [..., wj]       Buffer: [wi, wk, ...]

By shifting $w_i$ back to the buffer, the parser allows $w_j$ to form dependencies with upcoming words like $w_k$ before $w_i$ is processed again. This simple mechanism allows the parser to generate non-projective trees while maintaining an expected linear running time on real-world data.

Concurrently, Titov et al. (2009) introduced a similar swap operation designed to handle non-planar structures by swapping the top two elements of the stack, demonstrating that dynamic reordering is a robust solution for bypassing strict LIFO constraints. This strategy has since been integrated into various parsing frameworks, including arc-hybrid systems where the stack-to-buffer reordering transition acts as an elegant extension to standard projective operations, as shown by de Lhoneux et al. (2017).

Optimizing the Reordering Path

While adding a SWAP action solves the expressiveness problem, it introduces a new challenge: search space complexity. If a parser can swap words arbitrarily, it risks entering infinite loops or executing redundant operations.

To address this, Nivre et al. (2009) designed an improved, "lazy" training oracle. Instead of swapping words as soon as a non-projective configuration is possible, the lazy oracle delays the SWAP operation until it is absolutely necessary to form a valid dependency. This optimization reduces the number of required transitions by up to 80%, significantly accelerating parsing speed.

As parsers transitioned to greedy, machine-learning-driven models, handling mistakes during reordering became critical. Gómez-Rodríguez et al. (2014) developed a polynomial-time dynamic oracle for non-projective parsing. Unlike static oracles that train the parser on a single gold path, a dynamic oracle teaches the parser how to make optimal downstream choices even after it executes an incorrect swap or shift, making greedy non-projective parsers substantially more robust.

Generalizing Beyond Trees to Graphs

The utility of online reordering extends far beyond syntactic dependency trees. Deep semantic analysis—such as Abstract Meaning Representation (AMR) or Enhanced Universal Dependencies—requires parsing text into directed acyclic graphs where a single concept can have multiple parents (reentrancy) and cycles can occur.

The SWAP transition maps naturally to graph parsing. For example, Ballesteros et al. (2017) utilized a swap operation within a Stack-LSTM framework to generate complex AMR graphs directly from text. By reordering elements on the stack, the model can revisit tokens to establish reentrant edges that cross other semantic relations. Similarly, Hershcovich et al. (2020) and Ribeyre et al. (2014) demonstrated that incorporating swap-based reordering allows transition systems to resolve interleaved, non-planar graph topologies without relying on heavy, multi-stage pipeline architectures.

Alternative Architectures for Non-LIFO Processing

While the SWAP transition remains the most common method for linearizing non-projective structures, other researchers have explored alternative ways to break the strict LIFO bottleneck:

  • Deep Stack Jumping: Instead of moving tokens back to the buffer, some systems introduce transitions that allow arcs to form between non-adjacent elements deeper in the stack. Cohen et al. (2011) proved that this jumping mechanism can be formalized using dynamic programming to achieve exact inference in polynomial time.
  • Stack-Free Sets: Moving away from linear memory entirely, Grandury et al. (2019) proposed a "stack-free" transition system for discontinuous parsing. By replacing the stack with a random-access set, the parser can attach constituents out of order in a linear number of steps.
  • Early Precursors: The concept of relaxing the stack dates back to early deterministic parsers, such as the system by Sabah and Rady (1983), which utilized a flexible list-based "detach and resume" mechanism to handle long-distance semantic attachments.

Ultimately, whether implemented via an explicit SWAP action, deep stack access, or random-access memories, the core insight remains identical: by decoupling the processing order of words from their surface linear order, transition-based systems can parse the world's most structurally complex languages with remarkable speed and precision.

Key Foundational Work

Non-Projective Dependency Parsing in Expected Linear Time (2009) — contributed 3 concept elements to this direction.
A Latent Variable Model of Synchronous Syntactic-Semantic Parsing for Multiple Languages (2009) — contributed 1 concept elements to this direction.
Online Graph Planarisation for Synchronous Parsing of Semantic and Syntactic Dependencies (2009) — contributed 1 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 20 papers
  2. Version 1 · 2026-10-04 · 28 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_non_projective_transition_based_parsing_852b2c83,
  title = {non-projective transition-based parsing},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-projective-transition-based-parsing/rdr_852b2c838c9e404a9bce0db6257b57b0},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_non_projective_transition_based_parsing_852b2c83_v2,
  title = {non-projective transition-based parsing},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/non-projective-transition-based-parsing/rdr_852b2c838c9e404a9bce0db6257b57b0/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake