Greedy Parsing

The defining performance characteristic of greedy parsing is its O(n) time complexity. Because the parser makes a single pass over the input sequence without revisiting previous decisions, the processing time scales linearly with sentence length. This makes it ideal for high-throughput production environments where latency is critical, such as real-time chatbots or large-scale document processing pipelines.

At each parser state, a trained classifier—often a support vector machine or a neural network—evaluates the current stack and buffer configuration to predict the next action (e.g., SHIFT, LEFT-ARC, RIGHT-ARC). The action with the highest probability score is selected immediately. There is no exploration of alternative paths, which contrasts sharply with beam search strategies that maintain multiple hypotheses.

The primary vulnerability of greedy parsing is error propagation. If the parser makes an incorrect attachment decision early in the sentence, that erroneous state becomes the foundation for all subsequent decisions. The model cannot backtrack to correct the mistake, often leading to a compounding of errors that degrades the overall Labeled Attachment Score (LAS). This is the fundamental trade-off for its speed.

Greedy parsing is inherently a transition-based paradigm. It operates using a state machine defined by:

• A stack holding partially processed tokens
• A buffer containing the remaining input
• A set of actions that manipulate these structures Algorithms like Arc-Eager and Arc-Standard define the specific action sets and the order in which dependencies are constructed.

Unlike graph-based parsers that score all possible arcs globally, a greedy parser makes decisions based on local features extracted from the current parser state. These features typically include the top tokens on the stack, the next token in the buffer, and their associated part-of-speech tags and dependency relations. This local focus is what enables its speed but limits its ability to resolve long-distance ambiguities.

To mitigate error propagation, greedy parsers are often trained using a dynamic oracle. Instead of only learning from perfect gold-standard states, a dynamic oracle defines the optimal action from any valid state, even one reached after a previous error. This teaches the model to recover gracefully from its own mistakes during inference, significantly improving robustness without sacrificing the greedy decoding strategy.

A heuristic search algorithm that maintains a fixed number of the most probable partial parse states at each step, directly mitigating the error propagation inherent in greedy approaches. Unlike greedy parsing's single-path commitment, beam search explores k parallel hypotheses simultaneously.

• Typical beam widths range from 4 to 64
• Increases computational cost by a factor of k
• Often combined with dynamic oracles for robust training

The deterministic parsing paradigm where greedy strategies are most commonly applied. A stack and buffer architecture processes the sentence left-to-right, applying shift-reduce actions to incrementally build a dependency tree.

• Arc-Eager: Attaches dependents as soon as they are complete
• Arc-Standard: Waits until both head and dependent are on the stack
• Greedy transition-based parsers achieve O(n) linear time complexity

An alternative paradigm that scores all possible arcs in a sentence simultaneously, finding the highest-scoring maximum spanning tree via the Chu-Liu/Edmonds algorithm. This global optimization avoids the local decision pitfalls of greedy parsing.

• Naturally handles non-projective dependencies
• Typically slower at O(n³) or O(n²) depending on constraints
• Modern deep biaffine parsers use this approach with neural scoring

A training technique that defines the set of optimal actions from any valid parser state, even after previous errors have occurred. This allows greedy parsers to learn recovery behaviors by exploring non-gold states during training.

• Critical for reducing cascading error propagation
• Enables exploration of states a greedy parser would actually encounter at inference
• Transforms a local classifier into a globally-aware learner

The primary evaluation metric for dependency parsers, measuring the percentage of tokens assigned both the correct syntactic head and the correct dependency relation label. Greedy parsers typically trade a small LAS reduction for significant speed gains.

• Unlabeled Attachment Score (UAS) ignores relation labels
• Modern neural greedy parsers achieve 90-95% LAS on standard treebanks
• The gap between greedy and beam search narrows with stronger encoders

The foundational transition-based algorithm where SHIFT pushes the next input token onto the stack and REDUCE pops the top two items to attach them as a head-dependent pair. Greedy shift-reduce parsers select the single most probable action at each configuration.

• Forms the basis of MaltParser and many production systems
• Action history serves as rich features for classifier decisions
• Can be extended with SWAP transitions for non-projective structures