Unification Constraints as a Decoding Filter for Joint Syntax–Discourse Parsing

Parsers that build one tree for a whole document, with grammar trees for each sentence nested under a tree of rhetorical relations between clauses ("this clause is the condition for that one", "this sentence elaborates on the previous one"), currently learn everything from very little data. The main discourse treebank covers only 385 newspaper articles. The best joint parser in our material scores 52.2 F1 end to end and needed a dropout rate of 0.5 to avoid overfitting. Much of what such a parser has to learn is not statistical. A clause reporting someone's speech ("analysts said that…") has a predictable syntactic shape. A discourse boundary almost never falls in the middle of a noun phrase. The nucleus of a relation, meaning its central clause, is anchored at the main verb of a sentence. A much older line of work showed how to write regularities like these declaratively and run them for free. In Lexical Functional Grammar (LFG), each phrase carries a feature structure, a nested record of grammatical attributes such as subject, tense and predicate. LFG rules can be compiled into Definite Clause Grammars (DCGs), Prolog grammar rules in which shared logic variables play the role of those features. A constraint is then checked the moment a rule applies: unification of shared variables either succeeds or fails on the spot.

We propose to compile a small LFG-style grammar of syntax–discourse interactions into DCG-style clauses and use it as an incremental filter inside a neural joint syntax–discourse parser. The grammar is not meant to replace the parser. At each step it either licenses or vetoes a proposed transition, according to whether the feature structures of the constituents being joined unify, and it can also be applied as a soft penalty. The claim is narrow and testable. When annotated documents are scarce, hard cross-level agreement constraints should improve end-to-end discourse parsing more than giving the same information to the network as input features, and the advantage should shrink as training data grows.

What exists and what is missing

The compilation side supplies the mechanism. Frey and Reyle's A Prolog Implementation of Lexical Functional Grammar as a Base for a Natural Language Processing System compiles LFG functional equations into DCG arguments and builds discourse representations incrementally, but only within a sentence and for local anaphora. Eisele and Dörre's A Lexical Functional Grammar System in Prolog contributes open-ended attribute–value lists and threaded "controller lists" for long-distance dependencies. Yasukawa's LFG System in Prolog uses ordered-tree feature structures, which are about 30% faster than lists. We reuse these representations directly.

The same papers also impose a constraint on design. Yasukawa's constraint checking took 19 seconds on an eight-word sentence, while the parse itself took 972 ms. Eisele and Dörre stress that LFG recognition is NP-complete and that blind backtracking recomputes the same constituents. A grammar that searches over a whole document on its own would therefore be hopeless. This is why we let the neural parser propose transitions and use the grammar only to check them. In that setting unification runs once per proposed combination, not across an exponential search.

Gardent and Perez-Beltrachini's RTG based surface realisation for TAG shows that sharing and packing feature-equivalent chart items cuts intermediate structures from 2,018 to 918.31. We reuse that idea to keep beam items with identical feature structures merged. Dymetman's A Simple Transformation for Offline-Parsable Grammars and its Termination Properties tells us which grammar fragment we can guarantee terminates when it is run top-down. We will restrict the grammar to that offline-parsable fragment, so the same grammar can also be used to enumerate trees for diagnostics.

The hierarchical side supplies the setting and the competitor. Zhao and Huang's Joint Syntacto-Discourse Parsing and the Syntacto-Discourse Treebank places Penn Treebank sentence trees under discourse trees from Rhetorical Structure Theory (RST). It parses the combined tree with a greedy shift-reduce system built on a bidirectional LSTM, using four actions: Shift, Combine, Label, and NoLabel. It has no grammar and no feature checking. Kwon et al.'s Considering Nested Tree Structure in Sentence Extractive Summarization with Pre-trained Transformer motivates one of our constraints: inter-sentence relations should attach at each sentence's syntactic root word. Kwon et al. learn this softly with graph attention, whereas we would enforce it as feature percolation. Their small gain on CNN/DailyMail (ROUGE-1 43.86 against 43.55 for plain RoBERTa) also warns us that structural knowledge adds only modestly on top of a pretrained encoder. Kikuchi et al.'s Single Document Summarization based on Nested Tree Structure and TIMERS (TIMERS: Document-level Temporal Relation Extraction) both consume nested trees produced by external parsers and suffer from those parsers' errors. That gives a downstream reason to care about parse quality, but neither work produces trees itself.

No work in our material puts a compiled unification grammar inside a document-scale joint parser. The closest symbolic work stops at the sentence, and the closest document-scale work has no declarative constraints.

Core Claim

Every constituent in the joint tree gets a feature structure. Syntactic nodes carry predicate, subject, complement clause, subordinator and tense, compiled from a compact LFG fragment. Discourse nodes inherit HEAD from their nucleus and record the connective, if any, of their satellite.

Cross-level constraints are written as functional equations and compiled to DCG clauses. Four kinds are planned. First, an EDU boundary (a boundary between elementary discourse units, the minimal clauses of discourse analysis) must coincide with a clause or phrase boundary in the syntax subtree. Second, an Attribution relation requires a satellite whose predicate belongs to the class of communication verbs and whose complement is the nucleus. Third, relations labelled with explicit-connective classes must agree with the satellite's subordinator when one is present. Fourth, a sentence-spanning discourse node's HEAD equals the root predicate of its main clause.

During decoding, a Combine or Label action is executed only if the feature structures of the constituents being joined unify. In soft mode, the parser's score instead becomes

$$s'(a) = s(a) - \lambda\, v(a),$$

where $s(a)$ is the neural score of action $a$, $v(a)$ is the number of constraints it violates, and $\lambda \ge 0$ is tuned on development data. Hard mode is $\lambda \to \infty$.

Before any parsing, the grammar has to pass a coverage check: it should accept nearly all gold trees in the training set. Gold trees it rejects are either annotation noise or grammar errors, and the rejection rate determines whether hard mode is viable at all.

Research Program

We first write the grammar and compile it, using Yasukawa-style identifier variables for feature structures and Dymetman's left-recursion removal for elaboration chains. We report gold-tree acceptance on the training split, broken down by constraint type, and revise or drop constraints that reject more than a small fraction of gold trees. Constraints are drawn only from the training split, so the test set never informs the grammar.

We then reimplement the Zhao and Huang transition parser and add beam search. Two encoder settings are used, their original BiLSTM and a pretrained transformer encoder, because a pretrained encoder might absorb exactly the regularities the grammar encodes. The constraint filter is attached as a check on each action, with feature-equivalent beam items packed in the manner of Gardent and Perez-Beltrachini. We log unification time per document to confirm that the 19-second pathology does not recur at document length.

Finally, we vary the amount of training data, using 10%, 25%, 50% and 100% of the training documents. The central prediction is a gap that shrinks as data grows. If the gap is constant or absent, the claim is wrong.

Baselines

The naive reference point is the reimplemented Zhao and Huang parser without constraints, using greedy decoding as in the original. Its job is to confirm that our reimplementation is faithful. The paper reports EDU segmentation F1 95.4 and end-to-end F1 52.2 on the Syntacto-Discourse Treebank, and we will report how far our reproduction falls from 52.2 before comparing anything else. The pipeline the paper cites as previous best, at 47.3 F1, serves as a floor.

The strongest competitor is the same parser with beam search and a pretrained encoder but no grammar. It is the most likely system to absorb cross-level regularities on its own. Every arm shares data splits, encoder, beam width, and a fixed hyperparameter-search budget. The constrained arm gets no extra trials: its only additional hyperparameter, $\lambda$, is counted inside the shared budget. Beating this baseline means a gain in end-to-end F1 that is significant under a paired bootstrap across test documents at the 25% and 50% data levels. We report full-data results whatever they show.

Three ablations isolate where any gain comes from. A feature-input arm receives the same information the grammar uses (communication-verb class, subordinator, clause-boundary indicators) as embeddings, with no constraint enforcement. This separates "the information helps" from "enforcing it helps". A backbone-only arm enforces only the context-free part of the constraints, the span coincidence rule, without any feature unification, which tests whether the unification machinery adds anything over a span-compatibility check. A soft-versus-hard comparison measures the cost of annotation noise. No reported result was found on Lacuna for constrained decoding on this treebank.

Why not just…?

Why not just feed the constraint information as features to the network? This is the most serious threat, and the feature-input ablation exists to settle it. With 385 documents, a learned feature weight is unlikely to become absolute, so rare but systematic configurations, such as an Attribution relation with an unusual verb, may still be mispredicted. If the feature-input arm matches the constrained arm at every data level, we conclude that enforcement is unnecessary and say so.

Why not just rerank the n-best output of an unconstrained parser with the same rules? Reranking only helps if the correct tree is already in the beam. A greedy shift-reduce parser commits early, so an error at the EDU level cannot be undone later, which is the same propagation that cost the pipeline 4.9 F1 against joint parsing in Zhao and Huang. We include an n-best rerank arm with matched beam width. If it equals the in-decoding filter, the simpler method wins.

Why not just rely on a large pretrained encoder? It may well suffice at full data. Kwon et al.'s small ROUGE-1 gain from explicit structure on top of RoBERTa suggests the margin will be modest. This is why the pretrained encoder appears in every arm, and why the claim concerns the low-data regime and not the full-data headline number.

Why not a pipeline of separate segmenter, sentence parser and discourse parser? Zhao and Huang already show that the joint model beats the best pipeline, 52.2 against 47.3 F1, so we do not revisit this question beyond keeping 47.3 as a floor.

Proposed Experiments

The main experiment is on the Syntacto-Discourse Treebank, reporting EDU segmentation F1 and end-to-end structure-plus-relation F1 across all arms and data levels, with per-relation breakdowns for the constrained relations (Attribution and connective-marked relations) against unconstrained ones. If gains appear only on constrained relations, that supports the mechanism. If gains appear everywhere, that suggests a regularization side effect worth separating out.

The first decisive check runs before any parsing. If the grammar rejects a large share of gold training trees, hard mode is dead and only soft mode is evaluated.

The second decisive check is the data-level curve against the feature-input ablation. The idea succeeds only if the constrained arm's advantage over that ablation is positive at low data and shrinks with more data.

A secondary downstream test feeds each parser's trees into Kikuchi et al.'s nested-tree trimming on the 30 RST-DTB test documents. Their reported ROUGE-1 of 0.354 serves as the reference, and we test whether constrained parses narrow the gap between automatically parsed and annotated trees.

We also report decoding time per document, to show that inline unification at document length stays within a small constant factor of unconstrained decoding.