Abstract
Transition-based parsing is a cornerstone of Natural Language Processing (NLP), yet it often faces a trade-off between the speed of template-based methods and the structural completeness of recurrent models. We present the Unified Structure Encoder (USE), a novel attention-based framework that captures the complete state of transition-based parsers—including stacks, buffers, and partial trees—within a single, parallelizable architecture. By decoupling an item's content from its position through structure indicators, USE achieves state-of-the-art parsing accuracy while running up to five times faster than previous transition-based models.
Introduction
Transition-based parsing builds dependency trees by performing a sequence of actions, such as pushing items to a stack or reducing them. To predict the next action, a model must understand the current configuration of its internal structures: the stack (LIFO), the buffer (FIFO), and the partial tree built so far. Historically, researchers have relied on either fast but limited template-based methods that only observe "top-k" items, or structure-based networks like Stack-LSTMs that capture the whole structure but are computationally expensive and difficult to parallelize on GPUs.
Methods
The core innovation of USE is the Two-View Representation of items within the system:
- Structure-Invariant View: Represents the "content" of a word (embeddings, POS tags, character features) which remains constant regardless of its position in the parser.
- Structure-Dependent View: Uses Structure Indicators—learnable vectors that specify an item's position, such as "top of the stack" or "third element in the buffer."
The Unified Structure Encoder (USE)
Instead of sequential LSTMs, USE utilizes Multi-Head Attention (MHA). Each item is represented by the sum of its content embedding and its position indicator. Each attention head is assigned to a specific structure (stack, buffer, etc.), where the query vector represents the current time step and the keys/values represent the items in that structure.
Multiple layers of USE are stacked, allowing the model to learn interactions between different structures. Crucially, this approach allows the model to track "off-structure" information—items recently removed from the stack—by using negative position indicators.
Key Results and Insights
The model was evaluated on the English Penn Treebank (PTB 3.0) and Universal Dependencies (UD 2.2) across 12 languages.
- Accuracy: On the PTB dataset, the USE parser achieved 95.99% UAS (Unlabeled Attachment Score), matching the performance of strong graph-based parsers.
- Efficiency: USE parsed 918 sentences per second, making it 5x faster than the strongest transition-based baseline and roughly 2x faster than popular graph-based parsers like the Dozat & Manning biaffine parser.
By treating "position in a stack" as a learnable embedding, the authors transform a dynamic, sequential problem into a set-based problem that Transformers excel at. This allows the model to process all transition states in a batch simultaneously, bypassing the sequential bottleneck of RNNs.
Conclusion
While USE slightly underperforms some "high-order" graph parsers that use complex global decoding, it provides a superior balance of speed and accuracy. Future work may involve integrating bi-directional transition systems or stronger decoding methods to bridge the remaining accuracy gap while maintaining the significant speed advantages of the USE encoder.
Summary updated