Language Modeling with Explicit Syntactic Dependencies

45 concepts36 papers1 proposal

Standard language models treat text as a flat, linear sequence of tokens. While this formulation is computationally convenient, it introduces a fundamental blind spot when dealing with the hierarchical nature of human language. Consider a simple sentence containing a long-distance dependency:

The book that I borrowed from the library last week is excellent.

The singular noun book determines the form of the verb is, yet they are separated by a seven-word relative clause. In a flat sequence, a local model (like an $n$-gram) completely loses this connection. Even recurrent neural networks often struggle in these scenarios; as demonstrated in Distinct patterns of syntactic agreement errors in recurrent networks and humans, Tal Linzen et al. found that sequential models frequently rely on linear proximity heuristics rather than true hierarchical representations, leading to systematic errors when intervening words confuse the context.

Dependency-based language modeling addresses this limitation by restructuring the history. Instead of predicting the next word based on its immediate linear predecessors, it conditions predictions on the word's structural head or ancestral path within a syntactic tree, effectively bypassing local modifiers and shortening the distance between related tokens.

Incremental Parsing and Exposed Headwords

To utilize a tree structure during left-to-right text generation or processing, a model cannot rely on a pre-computed, global parse tree. Instead, it must build the tree incrementally.

In the foundational paper A Structured Language Model, Ciprian Chelba introduced the concept of tracking "exposed headwords"—the most structurally significant words in a sentence's partial parse tree. By conditioning the next token on these exposed heads, the model can look past arbitrary local modifiers.

Linear History:     [The] -> [book] -> [that] -> [I] -> [borrowed] -> ... -> [week] -> [is]
                                                                                        ^
                                                                           (Long linear distance)

Structural History: [book] ----------------------------------------------------------> [is]
                                                                                        ^
                                                                           (Direct structural head)

To operationalize this dynamically, a language model can embed a shift-reduce parser directly into its generation loop. As explained in Revisiting the Case for Explicit Syntactic Information in Language Models by Ariya Rastrow et al., the parser incrementally constructs a dependency tree as each word is processed. This mechanism maintains a running state of the sentence's grammatical structure, allowing the model to condition future tokens on structural heads rather than just linear neighbors. This left-to-right synchronization of sequential generation and hierarchical syntax has been widely leveraged to improve machine translation decoding, notably in A Structured Language Model for Incremental Tree-to-String Translation by Heng Yu and A Shift-Reduce Parsing Algorithm for Phrase-based String-to-Dependency Translation by Yang Liu et al.

Reformulating the Probability Space

How does this structural shift alter the underlying mathematics of a language model? A standard language model factorizes the joint probability of a sequence $W = w_1, w_2, \dots, w_T$ linearly:

$$P(W) = \prod_{t=1}^T P(w_t \mid w_1, \dots, w_{t-1})$$

Dependency language models redefine this context window using tree topology. For instance, in A New String-to-Dependency Machine Translation Algorithm with a Target Dependency Language Model, Libin Shen et al. calculate word probabilities based on the word's parent head and its preceding siblings within the dependency tree:

$$P(w_t \mid \text{head}(w_t), \text{siblings}(w_t))$$

This formulation allows the model to evaluate the structural coherence of a sentence during generation. The same core mechanism is utilized by Min Zhang et al. in Utilizing Dependency Language Models for Graph-based Dependency Parsing Models to capture local dependency patterns as ordered sequences of child nodes under a shared head.

Alternatively, a model can calculate probabilities by traversing vertical paths instead of horizontal sequences. In Dependency Language Models for Sentence Completion, Joseph Gubbins et al. applied a Markov property to ancestral paths within a dependency tree. By treating a word's structural ancestors as its primary context, the model drastically shortens the effective distance between related words that are physically separated in a flat string. Similarly, the TreeNode Language Model proposed in Go Climb a Dependency Tree and Correct the Grammatical Errors by Houfeng Wang et al. scores the joint probability of connected subgraphs (a head node and its children) to evaluate structural coherence directly on the tree.

Why Structure Outperforms Sequences

Shifting from a linear history to a structural history yields a powerful inductive bias for several reasons:

  • Linguistic Skeletons and Parameter Efficiency: Linear sequences are noisy; they are filled with adjectives, adverbs, and relative clauses that obscure core relationships. In Exploiting Headword Dependency and Predictive Clustering for Language Modeling, Jianfeng Gao et al. showed that modeling transitions exclusively between core content words (headwords) extracts a "linguistic skeleton." This maintains semantic and grammatical coherence across long spans while requiring significantly fewer parameters than high-order linear $n$-grams.
  • Aligning with Human Grammatical Judgments: Human perception of language acceptability is inherently hierarchical. As demonstrated in Unsupervised Prediction of Acceptability Judgements by Jey Han Lau et al., a model's ability to mirror human grammatical acceptability judgments scales with its capacity to capture abstract structural patterns rather than simple surface-level word sequences.

This structural awareness provides a cleaner, more relevant signal across downstream applications. In speech recognition, Ariya Rastrow et al. showed in Efficient Structured Language Modeling for Speech Recognition that conditioning on structural headwords resolves long-distance ambiguities that cause standard models to fail. In machine translation, Using a Supertagged Dependency Language Model to Select a Good Translation in System Combination by Wei-Yun Ma et al. leveraged structural head conditioning to filter out ungrammatical translation hypotheses. Finally, in Efficient Continue Training of Temporal Language Model with Structural Information, Zhaochen Su et al. demonstrated that masking and forcing the reconstruction of structural dependents allows models to adapt to language evolution far more efficiently by focusing directly on a word's shifting grammatical roles.

Key Foundational Work

A Structured Language Model (1997) — contributed 1 concept elements to this direction.
Disambiguation of Super Parts of Speech (or Supertags): Almost Parsing (1994) — contributed 1 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

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

Latest version (a living page):

@misc{lacuna_dependency_based_language_modeling_57bfd5d4,
  title = {dependency-based language modeling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/dependency-based-language-modeling/rdr_57bfd5d4d8e04bd897f67b4a248d11dd},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 2, frozen text):

@misc{lacuna_dependency_based_language_modeling_57bfd5d4_v2,
  title = {dependency-based language modeling},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/dependency-based-language-modeling/rdr_57bfd5d4d8e04bd897f67b4a248d11dd/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-22},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake