Dependency trees: token identity, heads and structural checks

Last updated: 7 Oct 20265 min read

tutorial

A dependency parser predicts head links between tokens. Validate the graph and token offsets before using its labels for extraction or search.

Define the unit of syntax

A dependency record names a token, its head token and a relation label. One token is the root; every other token has exactly one head in a basic tree. Token IDs belong to a specific sentence and tokenizer version, not a document-wide namespace. Store original character offsets beside them. If sentence segmentation changes, the same integer ID may refer to another word. Unicode tokenization and span offsets are prerequisites for reproducible parses.

Check the graph, not just a label list

Reject out-of-range heads, self-links, multiple roots and cycles. Check that every token reaches the root. A parser may still produce a well-formed but linguistically wrong tree, so structural validation is only an intake gate. Keep punctuation and multiword expressions under the chosen annotation convention. An apostrophe, hyphenated product name or code-switched phrase can change token boundaries and every downstream arc.

Evaluate useful relations

Unlabeled attachment measures the selected head; labeled attachment also requires the relation. Calculate them on an agreed tokenization, excluding or including punctuation according to a documented policy. Break out long sentences, nonstandard spelling, mixed scripts and passive constructions. An aggregate attachment score does not prove that the subject-object relation needed by an extractor is correct. Evaluate the end task too, such as identifying the affected service in an incident note.

Control version changes

Bundle sentence segmenter, tokenizer, parser weights, relation map and normalization policy. Compare token boundary differences before comparing arcs across versions; otherwise an apparent parsing regression may be a changed segmenter. Keep a reviewed audit set with messages from the target domain. Dependency paths uses validated trees to generate relation candidates, and the project exercises the full contract.

Implementation

def validate_dependency_tree(heads):
    token_count = len(heads)
    roots = [index for index, head in enumerate(heads) if head == -1]
    if len(roots) != 1:
        raise ValueError("basic tree requires one root")
    for token_index, head_index in enumerate(heads):
        if head_index == -1:
            continue
        if not 0 <= head_index < token_count or head_index == token_index:
            raise ValueError("invalid head index")
        visited = {token_index}
        cursor = head_index
        while cursor != -1:
            if cursor in visited:
                raise ValueError("dependency cycle")
            visited.add(cursor)
            cursor = heads[cursor]
    return roots[0]

assert validate_dependency_tree([1, -1, 1, 2]) == 1

Performance and operating cost

This simple validator follows parent pointers from every token and can take O(t²) time with O(t) temporary space for t tokens. A memoized graph walk reduces validation to O(t), useful for long documents; sentence-length inputs rarely make the simple version expensive. Parser inference, annotation and tokenization changes dominate operating cost. Record structural rejection rate separately from linguistic accuracy.

Common Mistakes

Treating integer token IDs as stable across tokenizer versions.
Using a tree with a cycle because every token has a head.
Comparing attachment scores after changing punctuation or segmentation rules.
Assuming a well-formed graph proves the dependency labels are correct.