A generalized transition framework for identifying reduction domains in non-binary constituency parsing

Jungyeul Park, Zihao Huang, Eunkyul Leah JoarXiv 2026 · arXiv

TL;DR

This paper introduces a unified transition framework for non-binary constituency parsing that uses "delimiters" to explicitly mark constituent boundaries on the stack. By identifying the "reduction domain" via these delimiters, the authors eliminate the need for arity-specific actions in bottom-up parsing, significantly simplifying the action space while maintaining competitive accuracy across top-down, in-order, and bottom-up traversal orders.

What Problem Does This Paper Address?

Constituency parsing involves breaking a sentence into nested hierarchical groups (phrases). While many parsers "binarize" these trees (limiting each node to two children), direct non-binary parsing is more linguistically natural but computationally trickier.

The main challenge lies in "reduction": knowing when and how many children to group into a parent phrase. In traditional bottom-up systems, the parser must predict an action like REDUCE-NP#3 (meaning "reduce the top 3 items into an NP"). This requires the model to learn a separate action for every possible combination of label and "arity" (number of children), leading to a massive, sparse action space. While top-down and in-order systems use markers to help, there hasn't been a common mathematical framework that unifies all three traversal orders without relying on arity as a hard-coded parameter.

Methods

The authors propose a delimiter-guided calculus. Instead of the action itself carrying the "count" of children, the parser places a special symbol—a delimiter ($D$)—on the stack to mark the left boundary of a potential phrase.

  1. The Delimiter ($D$): Acts as a "bookmarker" for the start of a constituent.
  2. The Marker ($nt(X)$): Supplies the non-terminal label (e.g., VP, NP).
  3. Unified Reduction: When a reduction occurs, the parser simply looks back to the rightmost delimiter. Everything between that delimiter and the marker is identified as the "reduction domain" (the children).

The paper provides a formal proof of soundness and completeness using stack invariants. They also introduce a "projection-and-lifting" theorem, proving that these delimiter-guided systems are mathematically equivalent to their canonical counterparts—they generate the exact same set of trees.

The characteristic reducible stack suffixes for canonical top-down (TD), in-order (IO), and bottom-up (BU) systems.

Datasets

The researchers evaluated their framework on two standard benchmarks:

  • Penn Treebank (PTB): The gold standard for English constituency parsing.
  • Chinese Treebank (CTB) 5.1: A widely used benchmark for Chinese parsing.

They compared their delimiter-guided versions against "canonical" (standard) implementations of top-down, in-order, and bottom-up parsers.

Key Insights and Ideas

  • Arity is an Emergent Property: The most significant "aha moment" is that the number of children (arity) doesn't need to be a predicted parameter. If you know where a phrase starts (the delimiter) and where it ends, the arity is simply the number of completed items in between.
  • Action Space Simplification: For bottom-up parsing, this approach collapses the action space. Instead of learning hundreds of REDUCE-LABEL#ARITY combinations, the model only needs to learn a small set of labels. On the PTB, this reduced the number of action classes from 251 down to 82.
  • Structural vs. Grammar Licensing: The authors distinguish between "structural" rules (how the stack is manipulated) and "grammar" rules (whether a specific tree is valid according to a treebank). This allows them to prove the system works for any projective tree, regardless of the specific grammar.

Key Results

  • Accuracy Parity: The delimiter-guided parsers achieved nearly identical labeled F1 scores to canonical systems. On PTB, the differences were within 0.11 points for top-down and 0.07 for bottom-up.
  • Efficiency Trade-off: While the action space is smaller, the derivations are longer because the parser takes more steps (e.g., explicitly placing delimiters and markers). For bottom-up parsing, the number of decisions per tree increased by roughly 64-67%.
  • Decoding Speed: Because of the longer derivations and the need to scan the stack for delimiters, the delimiter-guided bottom-up parser was about 9-15% slower than the canonical version. However, top-down and in-order speeds remained largely unaffected.

Limitations and Future Work

  • Speed: The increased number of steps per tree is a clear trade-off. Future work could investigate if the simplified action space allows for smaller, faster neural scorers that might offset this overhead.
  • Greedy Search: The experiments used greedy decoding. Exploring how this framework interacts with beam search or dynamic oracles could provide further insights into its robustness.
  • Beyond Projectivity: The current framework assumes projectivity (no crossing branches). Extending this to non-projective structures would be a significant next step for languages with freer word order.

Summary updated

Abstract

Direct non-binary constituency parsing must identify an ordered sequence of children at each phrase-level reduction. We extend our earlier delimiter-guided bottom-up construction to a common calculus for top-down, in-order, and bottom-up parsing. At reduction, the rightmost delimiter marks the left boundary, the nonterminal marker supplies the mother label, and the completed items in the delimited segment determine the children and arity. We use a stack invariant to prove soundness and completeness and derive the exact length of the static oracle's action sequence. A projection-and-lifting theorem shows that each delimiter-guided system and its canonical counterpart generate the same set of trees under both the structural and grammar-licensed transition relations. In controlled experiments on PTB and CTB, the delimiter-guided parsers achieve similar labeled accuracy to their canonical counterparts across all traversal orders. For bottom-up parsing, delimiter guidance reduces the number of action classes and increases the number of supervised decisions per tree.
BibTeX
@misc{park2026generalized,
  author = {Jungyeul Park and Zihao Huang and Eunkyul Leah Jo},
  title = {{A generalized transition framework for identifying reduction domains in non-binary constituency parsing}},
  year = {2026},
  eprint = {2611.12020},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.12020},
}
Figure