Traditional language models view a sentence as a flat sequence of tokens, predicting the next word based solely on the $n-1$ words that came before it. While effective for local fluency, this "n-gram" approach is structurally blind. It struggles with long-distance dependencies—like a verb that must agree with a subject appearing ten words earlier—because the linear distance between related words often exceeds the model's window.
Structured Language Models (SLMs) and Dependency Language Models (DLMs) solve this by replacing the linear sequence with a hierarchical tree. Instead of looking at the immediate predecessor, these models condition a word's probability on its "head" (its parent in a syntax tree) and its "siblings."
The Intuition: Anchors over Neighbors
In a dependency tree, every word is linked to a "head" word that it modifies. For example, in the phrase "the big red apple," the word "apple" is the head of "the," "big," and "red."
Eugene Charniak proposed that the lexical head of a constituent provides a much stronger predictive "anchor" than simple linear order. If a model knows the head is "eat," it can much more accurately predict that the next word might be an object like "pizza," even if several adjectives or adverbs sit between them. Libin Shen and colleagues expanded this by calculating probabilities based on both the parent head and preceding siblings, allowing the model to evaluate the structural coherence of a sentence as it is built.
Capturing Long-Distance Dependencies
The primary advantage of this structural approach is its ability to bridge gaps that linear models cannot see. Houfeng Wang and Longkai Zhang demonstrated this in the context of grammatical error correction. By calculating probabilities within a dependency tree (a TreeNode Language Model), they could catch subject-verb agreement errors where the subject and verb were separated by long, complex clauses.
Similarly, Joseph Gubbins and Andreas Vlachos showed that for sentence completion tasks, traversing paths in a syntactic tree effectively "shortens" the distance between related words. In a tree, the subject and its distant verb are often direct neighbors, even if they are physically far apart in the text.
Incremental Decoding and Shift-Reduce Parsing
A major challenge for SLMs is that, unlike n-grams, the "context" (the tree structure) isn't fully known until the sentence is finished. To use these models in real-time tasks like Machine Translation or Speech Recognition, researchers use incremental shift-reduce parsing.
As a decoder generates words from left to right, a shift-reduce parser maintains a partial parse state. Ciprian Chelba and Milind Mahajan used this to predict the next token by referencing the "exposed heads" of previously identified phrases. This allows the model to capture hierarchical information without waiting for the end of the sentence.
Heng Yu and others applied this to Tree-to-String translation, using the incremental parser to ensure the target language output remained grammatically sound. This synchronization allows the system to balance the local fluency of standard n-grams with the global structural constraints of dependency syntax.
Applications across NLP
The shift from sequences to structures has improved several core areas of language processing:
- Machine Translation: Christopher D Manning and Michel Galley integrated dependency parsers into phrase-based MT decoders, scoring the likelihood of head-modifier relationships to improve translation quality with only a modest increase in computation.
- Speech Recognition: Christopher Collins adapted head-driven statistical parsing for word lattices, showing that structural linguistic probabilities could outperform standard trigrams in noisy audio environments.
- Parsing Accuracy: Juntao Yu demonstrated that DLMs trained on massive unlabeled corpora can be used to "guide" transition-based parsers, providing a stronger signal for predicting grammatical structures than linear word sequences alone.
By treating language as a hierarchy rather than a string, these models move closer to the underlying logic of human grammar, where the relationship between a "head" and its "modifier" is the fundamental unit of meaning.