Traditional natural language processing often treats parsing as a "one-shot" task: a model receives a complete sentence, analyzes its structure, and outputs a tree. However, human language processing is fundamentally different. We do not wait for a speaker to finish their sentence before we begin interpreting it; we build mental representations word-by-word.
Research into incremental parsing seeks to bridge this gap, developing architectures that maintain a continuous, evolving hypothesis of a sentence's structure. This direction moves away from linear pipelines toward what Robert J. Bobrow and Bonnie Webber called the Principle of Continually Available Output (CAO), where syntax and semantics interact in real-time to resolve ambiguity.
The Challenge of Full Connectivity
A central debate in incremental parsing is how to maintain a "fully connected" structure. When a human hears the first three words of a sentence, they don't just store three isolated tokens; they integrate them into a single, unified (though incomplete) mental model.
To achieve this computationally, models must often "predict" the existence of nodes that haven't appeared yet. Vera Demberg and Frank Keller addressed this with PLTAG (Psycholinguistically Motivated Tree Adjoining Grammar). PLTAG uses "prediction trees" to bridge the gap between a new word and the existing structure, creating a scaffold for upcoming information. This allows the system to initiate semantic interpretation immediately, rather than waiting for a phrase to close.
However, full connectivity introduces a trade-off: predicting future structure increases computational ambiguity. Vera Demberg noted that anticipating post-modifiers (like adverbs or prepositional phrases) requires "predictive type-raising," which expands the search space as the parser guesses which modifiers might appear.
Parsing Strategies: Top-Down vs. Left-Corner
The "direction" of the parser—how it traverses the hierarchy—significantly impacts its cognitive plausibility.
- Top-Down Parsing: Models like those proposed by Brian Roark build trees from the root node down to the words. This is inherently predictive, as the model must hypothesize a "Sentence" node before seeing any words. Roark demonstrated that these parsers can be highly efficient without traditional dynamic programming, providing real-time partial scores that are useful for tasks like speech recognition.
- Left-Corner Parsing: This strategy balances top-down and bottom-up information. It initiates a phrase from a child node (the "left corner") before inferring the parent. Hiroshi Noji and Yohei Oseki found that left-corner Recurrent Neural Network Grammars (RNNGs) better predict human reading patterns, especially in left-branching languages like Japanese. This suggests that the human brain may favor building structure incrementally from the bottom up as words arrive.
Surprisal and the Garden Path
If a model is truly processing language like a human, it should experience "surprise" when a sentence takes an unexpected turn. This is most evident in garden-path sentences (e.g., "The horse raced past the barn fell"), where the initial words suggest a structure that is invalidated by the final word.
Ethan Wilcox, Roger Levy, and colleagues have treated RNNs as "psycholinguistic subjects" to test this. They found that while standard LSTMs can track simple syntactic states, they often struggle with complex dependencies like reflexive pronoun binding. However, models that maintain explicit structural expectations show high surprisal—a spike in processing difficulty—when encountering words that force a revision of their internal parse, mirroring human eye-tracking and reading-time data.
Mapping Syntax to the Brain
Recent work has moved beyond behavioral data to look at the brain itself. By using fMRI, researchers like Leila Wehbe and Aniketh Janardhan Reddy have shown that the brain's language network represents these evolving, incomplete syntactic structures in real-time.
Using a technique called ConTreGE (Contextualized Tree Graph Embeddings), Reddy and Wehbe demonstrated that neural activity is better predicted by models of incomplete trees than by finalized ones. This supports the idea that the brain is constantly building and updating a "syntactic scaffold." Further research by SUBBA REDDY OOTA and Manish Gupta suggests that different brain regions specialize in different types of incremental structure: the temporal lobe appears tuned to hierarchical phrase structures (constituency), while the angular gyrus focuses on word-to-word relationships (dependency).
Handling Late Information: Tree Rotation
A persistent problem for incremental systems is the "right-adjunct" problem—words that appear late in a sentence but attach to nodes created much earlier. Milos Stanojevic and Mark Steedman proposed a novel solution: Incremental Tree Rotation.
Their CCG parser builds left-branching trees (which are easy to construct word-by-word) and then "rotates" them into right-branching structures as needed. This allows the parser to keep attachment sites "accessible" on the right spine of the tree, enabling it to handle late-arriving modifiers without needing to re-parse the entire sentence from scratch. This mechanism shows that even complex structural revisions can be handled through purely syntactic operations, maintaining the efficiency required for real-time understanding.