Incrementality in Deterministic Dependency Parsing
Summary
The paper studies how incremental a deterministic, left-to-right dependency parser can be, in the sense of keeping the partially built structure connected as words arrive. It formalises parsing as a transition system over a stack and an input buffer, and analyses the arc-standard style of transitions (shift, left-arc, right-arc) and its relation to an arc-eager variant. The author shows that strict incrementality cannot be achieved for all structures in a purely bottom-up arc-standard system, while the arc-eager strategy allows a higher degree of incrementality. The analysis connects parsing algorithms to questions of human sentence processing and provides the formal basis for many later transition-based parsers trained with classifiers and static oracles.
How Mova uses it
en/src/parse.rs— the dependency parser is a table-driven arc-standard transition automaton: state = stack + buffer, actions SHIFT / LEFT(label) / RIGHT(label).- Decisions come from tables "feature → action weight", trained with an averaged perceptron against a static oracle derived from UD trees (the transition framework from this paper; feature templates simplified from Zhang & Nivre 2011).
- Adapted into two stages, action type (3 classes) and then the UD label only for arcs, to keep tables small; features are integers (template number + word/tag codes).
- Extended with beam search (8 hypotheses) and early update (Zhang & Clark 2008).
Effectiveness in Mova
The transition system itself is not compared against alternatives (e.g. arc-eager), so its share is not measured separately. Parser results from the en README and en/src/parse.rs, UD English EWT test UAS/LAS: 86.9 / 83.8 with gold tags; 84.2 / 79.8 with Mova's own tags; greedy 83.4 / 79.0; greedy with TnT tags 82.3 / 77.3; PUD 81.5 / 76.3, GUM 81.5 / 76.2; about 58k tokens/s. Adding the beam raised EWT test LAS from 79.00 to 79.77 (dev 77.33 → 79.17, PUD 74.48 → 76.33).
👨🔬💥
More ideas (a second reading)
- I1.
en/src/parse.rs: the arc-standard transitions are the current choice. Add an arc-eager transition set as a variant and compare LAS on EWT test (held out, LAS 79.8 with own tags today) and the share of configurations with at most one component. Decide on the two-fold check (en folds), not on test. - I2.
en parse-eval: report the incrementality share (configurations with at most one and at most three components) next to LAS, on EWT test and on the well-formed subset, as the paper does. This is a cheap diagnostic that costs no training. - I3. Real-time mode: count the words whose head arc is final when the word is read. Measure this share on EWT test and PUD test (test only, as PUD is not ours to train on) against LAS, to see how much accuracy the streaming mode costs.
Library summary
Written for the Research library (claude-opus-5-5) from the paper text, in our own words: the license "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)" does not allow redistributing the text itself. Original — aclanthology.org/W04-0308.pdf
Summary
This paper asks whether deterministic dependency parsing can be strictly incremental, meaning the parser always holds one connected analysis of the words read so far. Using a shift-reduce style transition system (stack, input buffer, arc set), Nivre first shows that strict incrementality is impossible. Some projective three-word configurations cannot be built incrementally: those where the two leftmost words are not directly linked, either as sisters or as grandparent and grandchild. This holds because every reduction without nonterminals must join a head with its dependent. A purely bottom-up (arc-standard) strategy also fails on right-branching chains. An arc-eager strategy fixes that case, and the paper argues it is optimal given the framework's limits. The arc-eager algorithm was paired with a memory-based classifier (TiMBL) and tested on a Swedish treebank. The measure was how many connected components sit on the stack during parsing. About 69% of parser configurations were incremental, and among sentences parsed into well-formed trees the figure was roughly 87%. The work matters for real-time applications such as speech recognition and for cognitively motivated parsing models.
Key points
- Strict incrementality is defined as having at most one connected component on the stack at every parser configuration. In stack terms, this means the stack never grows beyond two tokens before reduction.
- Of the seven projective three-node dependency structures, three cannot be parsed incrementally bottom-up. Two of these, where the leftmost words lack a direct arc, are impossible for any algorithm in the framework. The third, a right-branching chain, is solvable by arc-eager processing.
- The data is a small Swedish treebank (Einarsson, 1976), split into 5054 training sentences and 631 test sentences. The text reports 613 test sentences in the evaluation, with a mean length of 14.0 words. The parser reached 85.7% unlabeled attachment score (reported in Nivre et al., 2004).
- Across 16545 configurations, 68.9% had zero or one stack component, and 94.3% had at most three.
- Restricted to the 444 sentences that yielded well-formed trees, 87.1% of configurations were incremental and 99.5% had at most three components. The abstract states 87.9% instead; the table supports 87.1%.
Interesting ideas
- Proving limits on the smallest cases. Enumerating every possible three-word projective structure is a cheap way to prove what a transition system can and cannot do. The same exhaustive small-case check could expose blind spots in other transition-based parsers or segmenters.
- Counting stack components as a measure. Incrementality is measured by the number of connected components on the stack at each step, which gives a graded score rather than a yes/no verdict. This measure could be reused to compare transition systems for streaming or low-latency NLP, for example parsing live Ukrainian speech transcripts.
- Separating failed parses from algorithm behaviour. Evaluating on all sentences and then only on well-formed outputs shows how much non-incrementality comes from parse failures rather than from the algorithm itself. This split is useful whenever a pipeline metric mixes model errors with design properties.
- Arc-eager versus arc-standard as a design lever. Attaching arcs as early as possible keeps fewer disconnected pieces in memory, especially in right-branching constructions. The paper also argues this costs no extra local ambiguity in dependency representations, which makes arc-eager attractive for memory-sensitive or incremental settings.
- Linking parser design to cognitive theory. The paper connects its results to known memory problems of bottom-up parsing with right-branching structure. Borrowing such theoretical lenses can help explain why one algorithm behaves better than another, instead of only reporting scores.
Cite
@inproceedings{nivre2004incrementality,
title = {{Incrementality in Deterministic Dependency Parsing}},
author = {Nivre, Joakim},
booktitle = {Proceedings of the Workshop on Incremental Parsing: Bringing Engineering and Cognition Together},
year = {2004},
doi = {10.3115/1613148.1613156},
url = {https://doi.org/10.3115/1613148.1613156}
}References
- Steven Abney and Mark Johnson. 1991. Memory requirements and local ambiguities of parsing strategies. Journal of Psycholinguistic Research, 20:233–250. find
- Steven Abney. 1991. Parsing by chunks. In Principle-Based Parsing, pages 257–278. Kluwer. find
- Eugene Charniak. 2000. A maximum-entropy-inspired parser. In Proceedings NAACL-2000. find
- Michael Collins. 1997. Three generative, lexicalised models for statistical parsing. In Proceedings of the 35th Annatual Meeting of the Association for Computational Linguistics, pages 16–23, Madrid, Spain. find
- Walter Daelemans, Sabine Buchholz, and Jorn Veenstra. 1999. Memory-based shallow parsing. In Proceedings of the 3rd Conference on Computational Natural Language Learning (CoNLL), pages 77–89. find
- Walter Daelemans, Jakub Zavrel, Ko van der Sloot, and Antal van den Bosch. 2003. Timbl: Tilburg memory based learner, version 5.0, reference guide. Technical Report ILK 03-10, Tilburg University, ILK. find
- Jan Einarsson. 1976. Talbankens skriftspråks-konkordans. Lund University. find
- Parser configurations Number Percent 928 9.2 7823 77.8 1000 10.0 248 2.5 41 0.4 8 0.1 1 0.0 8751 87.1 9999 99.5 10049 100.0 find
- Lyn Frazier. 1987. Syntactic processing: Evidence from Dutch. Natural Language and Linguistic Theory, 5:519–559. find
- Matthias Trautner Kromann. 2002. Optimality parsing and local cost functions in Discontinuous Grammar. Electronic Notes of Theoretical Computer Science, 52. find
- William Marslen-Wilson. 1973. Linguistic structure and speech shadowing at very short latencies. Nature, 244:522–533. find
- Igor Mel’cuk. 1988. Dependency Syntax: Theory and Practice. State University of New York Press. find
- George A. Miller and Noam Chomsky. 1963. Finitary models of language users. In R. D. Luce, R. R. Bush, and E. Galanter, editors, Handbook of Mathematical Psychology. Volume 2. Wiley. find
- Glyn Morrill. 2000. Inremental processing and acceptability. Computational Linguistics, 26:319–338. find
- Joakim Nivre, Johan Hall, and Jens Nilsson. 2004. Memory-based dependency parsing. In Proceedings of the 8th Conference on Computational Natural Language Learning (CoNLL), pages 49–56. find
- Joakim Nivre. 2003. An efficient algorithm for projective dependency parsing. In Proceedings of the 8th International Workshop on Parsing Technologies (IWPT), pages 149– 160. find our card
- Mark Steedman. 2000. The Syntactic Process. MIT Press. find
- Hiroyasu Yamada and Yuji Matsumoto. 2003. Statistical dependency analysis with support vector machines. In Proceedings of the 8th International Workshop on Parsing Technologies (IWPT), pages 195–206. find our card