Dependency parsing

On this page 7

Dependency parsing is the task of analyzing a sentence by connecting every word to the single word it grammatically depends on, called its head, and labeling each connection with a syntactic relation such as subject, object or modifier. The result is a dependency tree rooted in the main verb. Within Speech & language AI, it is a core component of natural language processing that turns flat token sequences into explicit structure that downstream systems can query.

Unlike phrase-structure grammars, which group words into nested constituents, the dependency approach describes direct word-to-word relations. This makes it compact, well suited to languages with free word order, and practical for extracting who did what to whom in information extraction, question answering and relation extraction pipelines.

How a dependency tree represents a sentence

A dependency tree represents a sentence as a directed graph in which every word except the root has exactly one head. In the sentence “The engineer fixed the server”, the verb “fixed” is the root, “engineer” attaches to it as the nominal subject, “server” attaches as the direct object, and each “the” attaches to its noun as a determiner.

Three formal properties define a well-formed tree. It is connected, so every word is reachable from the root; it is acyclic, so no word is its own ancestor; and it has a single head per word. A further property, projectivity, holds when no arcs cross if drawn above the sentence. English is mostly projective, while Czech, Dutch and German contain frequent non-projective structures that some parsers cannot produce.

The most widely used annotation scheme today is Universal Dependencies, a cross-linguistic framework with treebanks for more than 100 languages. The table below lists frequent relation labels from that scheme.

LabelRelationExample (dependent → head)
nsubjNominal subjectengineer → fixed
objDirect objectserver → fixed
amodAdjectival modifierold → server
detDeterminerthe → server
oblOblique nominalnight → fixed (in “at night”)
caseCase marker or prepositionat → night
conjConjuncttested → fixed (in “fixed and tested”)
Common Universal Dependencies relation labels

Transition-based and graph-based parsing algorithms

Dependency parsers fall into two main algorithmic families that differ in how they search for the best tree. Transition-based parsers read the sentence left to right and build the tree through a sequence of actions on a stack and a buffer, such as SHIFT, LEFT-ARC and RIGHT-ARC. A classifier chooses each action, so parsing runs in linear time relative to sentence length.

Graph-based parsers score every possible head-dependent pair and then find the highest-scoring spanning tree. The Eisner algorithm finds the best projective tree in cubic time, while the Chu-Liu-Edmonds algorithm finds the best non-projective tree. Modern graph-based systems use a biaffine attention layer over contextual embeddings to score arcs and labels.

The following comparison summarizes the practical differences between the two families.

PropertyTransition-basedGraph-based
Search strategyGreedy or beam search over actionsGlobal search over all trees
Time complexityLinear, O(n)Quadratic to cubic
Non-projective treesRequires swap or special actionsNative with Chu-Liu-Edmonds
Error behaviorEarly mistakes propagateErrors stay more local
Typical strengthSpeed on long documentsAccuracy on long-range arcs
Transition-based versus graph-based dependency parsing

Since about 2018, both families rely on pretrained transformer encoders such as BERT or XLM-R. The encoder supplies context-sensitive word vectors, and the parsing layer adds only a thin structured decision on top. This shift raised English labeled accuracy into the mid-90 percent range on standard benchmarks.

Measuring dependency parser accuracy

Parser quality is measured by comparing predicted arcs with a gold-standard treebank. The two standard metrics are the unlabeled attachment score (UAS), the share of words assigned the correct head, and the labeled attachment score (LAS), the share with both the correct head and the correct relation label. LAS is always equal to or lower than UAS and is the primary reported metric.

SettingTypical LASMain limiting factor
English news text, transformer parserAbout 92-95%Prepositional phrase attachment
High-resource European languagesAbout 88-93%Morphology and word order
Low-resource languagesAbout 60-80%Small treebanks
Social media or transcribed speechOften 10-20 points lowerNoise and missing punctuation
Typical accuracy ranges by setting

These figures are indicative and depend heavily on the treebank, tokenization and whether gold or predicted part-of-speech tags are used. A score obtained on edited newswire rarely transfers unchanged to chat logs, legal contracts or speech-to-text output.

Where dependency parsing fits in the NLP pipeline

Dependency parsing usually runs after tokenization, part-of-speech tagging and often lemmatization, because heads and labels depend on word categories and forms. Its output then feeds tasks that need explicit grammatical roles rather than surface word order.

  • Relation extraction uses the shortest dependency path between two entities as a strong signal of how they are related.
  • Question answering systems match the subject, verb and object of a question against candidate sentences.
  • Sentiment analysis at the aspect level links opinion words such as “slow” to the feature they modify.
  • Grammatical error correction detects agreement errors between a subject and its verb.
  • Coreference resolution uses syntactic roles to rank likely antecedents.

Large language models have reduced the need for an explicit parsing step in many end-to-end applications, because they encode much syntactic information internally. Explicit parses remain valuable where interpretability, determinism and low cost matter, such as rule-based extraction, linguistic research, controlled generation and annotation tools.

Limitations and common errors in dependency parsing

Most parsing errors concentrate in a small set of ambiguous constructions that require world knowledge or long-range context. Knowing them helps engineers decide whether parser output can be trusted for a particular application.

Error typeCauseMitigation
Prepositional phrase attachmentStructural ambiguity needing world knowledgeDomain fine-tuning, semantic features
Coordination scopeUnclear which conjuncts are joinedLarger context, constrained decoding
Wrong root in fragmentsHeadlines or chat lack a main verbTrain on noisy or informal treebanks
Cascade from tagging errorsWrong part-of-speech inputJoint tagging and parsing models
Domain shiftTraining text differs from target textAnnotate a small in-domain sample
Frequent error types and how to mitigate them

A frequent misconception is that a high benchmark LAS guarantees reliable extraction. Because downstream rules often depend on one or two specific arcs, a single wrong attachment can invert a fact. Production systems therefore validate critical relations with confidence thresholds or secondary checks.

In simple terms

Dependency parsing is a way for a computer to work out which words in a sentence belong to which. It draws arrows from each word to the word it describes or supports, and it names each arrow, for example “this is the subject” or “this is the object”.

Think of a family tree for a sentence. The main action word sits at the top, and every other word hangs from the word it is most closely tied to. Once that tree exists, software can answer who did what to whom, even when the sentence is long or the word order is unusual.

A practical example

A pharmaceutical safety team receives several thousand free-text adverse event reports each month. Analysts need to know which drug caused which symptom, but simple keyword matching confuses sentences such as “Patient stopped drug A after nausea caused by drug B”, where both drugs appear near the symptom.

The team adds a transformer-based dependency parser to its pipeline after named entity recognition. A rule follows the dependency path from each symptom to the verb “caused” and then to its oblique agent, so the system attributes nausea to drug B rather than drug A. On a manually reviewed sample of 500 reports, the parser-based rules reduce misattributed drug-symptom pairs by roughly a third compared with the previous proximity-based method, and reviewers spend less time correcting the extracted table.