Constituency and Dependency Parsing › Decoding Trade-offs

Parsing decoding searches for an analysis under a model. Chart and graph decoders search tree structures directly. Sequence-to-sequence parsers instead generate an encoding of a tree through successive output-token decisions. Both perform inference, but their candidate spaces and structural guarantees differ.

The main trade-offs are:

• Exact versus approximate search. Unpruned Viterbi CKY and exact arborescence decoding optimize their specified objectives. Greedy transition decoding and finite beam search do not generally guarantee a global optimum.
• Projective versus non-projective. Arc-standard transition systems are projective. Eisner is projective. Chu-Liu/Edmonds handles non-projective trees. Swap-based transition systems extend the transition family but add complexity.
• Local versus global decisions. A transition parser makes local decisions that may be hard to revise. A graph-based parser makes local arc scores but enforces a global tree constraint at decode time. A chart parser combines local constituents into global spans.
• Time and memory. Ordinary greedy arc-standard decoding uses (2n) actions and is linear under the stated fixed-cost assumptions, excluding encoding. Compact CNF CKY has cubic sentence-length time and quadratic chart memory for a fixed grammar. Explicit tree enumeration has different storage costs. Unrestricted dense-graph arborescence decoding can use quadratic or cubic implementations; the single-ROOT constraint also needs accounting.
• Labeling. Joint arc-label scores can affect attachment selection. Labeling an already fixed tree cannot repair its heads. Cross-arc label interactions require a richer factorization.

These trade-offs interact. Exact search over a restricted scoring model and approximate search over a richer model can lead to different accuracy and latency results. Structural guarantees tell you which outputs are possible; they do not rank the models' linguistic accuracy. Compare that accuracy under the same annotation and evaluation protocol.

Table Table parsing-decoders summarizes decoder behavior. Sentence encoding is excluded; the transition row assumes fixed beam width and fixed-cost action scoring, and the chart rows hold the grammar or label inventory fixed. The MST row describes the base dense-graph solver: naively rerunning it for every possible sole ROOT child adds a factor of (n), whereas specialized single-root methods avoid that full repetition. Autoregressive sequence-model cost also depends on its architecture.

The table alone cannot choose a parser without application criteria. Measure encoding and decoding latency together for a latency budget. An unrestricted graph decoder is one option when nonprojective trees are required. For an explicit CFG, CKY after appropriate conversion or Earley on the general grammar are options. A neural scorer can also be combined with an exact decoder. Check the target annotations and permitted structures before comparing measured accuracy and resource cost.