Boundary Lattices for Discourse Parsing That Can Cross Its Own Boundaries

Fast parsers for long documents rely on a simple trick. They find sentence and paragraph breaks first, then require every sentence to be parsed as a self-contained piece before any structure links sentences together. This cuts cost from cubic to nearly quadratic in document length. The price is that any true relation crossing a break becomes impossible to predict, and any upstream mistake about where the breaks are cannot be undone. We propose replacing the single fixed segmentation with a small boundary lattice: a compact graph of alternative ways to group text into self-contained blocks, in which some breaks are firm and others may be dissolved. The parser searches over the whole graph in one dynamic program. The parse of each block is summarized only by which unit heads it. This summary is exactly sufficient for the higher-level parse, so equivalent block parses merge without approximation.

The two-sentence version is this. Treat "which boundaries must close off a subtree" as an uncertain, scored decision, represented as a lattice of candidate blocks rather than a single 1-best segmentation. Then parse over that lattice, merging all block-internal derivations that share a head. The result is close to the accuracy of unconstrained parsing at close to the cost of hierarchical parsing, and it recovers relations the hard-boundary systems structurally cannot produce.

Where the two directions meet, and what is missing

Boundary-constrained parsing covers several variants. Chunk boundaries prune a constituency chart (Glaysher & Moldovan): a 3× speedup for a 0.17% accuracy loss on PTB. Clause boundaries split Japanese monologue dependency parsing into two stages (Ohno et al.), which runs 5× faster and raises accuracy from 76.9% to 80.1%, though 6.4% of true dependencies cross clause boundaries and are lost. Discourse parsing has three versions. The Hierarchical Eisner algorithm (Zhang et al.) forces intra-sentence and intra-paragraph units to form closed subtrees. Sentence-First parsing (Zhou & Feng) parses each sentence, keeps its 1-best root unit, and links roots. Granularity-level top-down RST parsing (Kobayashi et al.) reduces the search space to 0.8% of its original size but admits it cannot produce gold relations that violate the paragraph hierarchy. These papers motivate the proposal: they show both the speed payoff and the unrecoverable error floor of hard boundaries.

Lattice-based candidate representation supplies the method. Word graphs in statistical translation (Ueffing et al.) and packed forests for hierarchical derivations (Williams et al.; Huang et al.) compress exponentially many candidates by merging states that face identical futures. Neural recombination (Zhang et al., NMT) merges hypotheses with matching n-gram suffixes. This lets beam size 6 match beam size 12 at twice the speed. The equivalence is only approximate, though: merged states have cosine similarity 0.986, not 1. We borrow the recombination idea and argue that in our setting the equivalence is exact.

Two prior works sit closest. The lattice framework for joint Chinese segmentation and parsing (Wang, Zong & Xue) keeps segmentation ambiguity in a word lattice and raises CTB parsing F1 from 81.17 to 83.42 over the 1-best pipeline. It operates on word boundaries only, however, and reaches agreement by iterative dual decomposition between a tagger and a parser. Our lattice sits over clause, sentence, and paragraph boundaries, and it is consumed by a single exact dynamic program with no iteration. Lattice chart parsing of ASR output (EACL 2009) contributes a mechanism we reuse: tagging chart edges with lattice start and end nodes so that structures from incompatible hypotheses never combine. That work cut chart edges by 81.1% versus N-best parsing. Its lattice, however, encodes acoustic word alternatives, not structural closure constraints.

Core Claim

In an arc-factored discourse dependency parser, the scorer is a contextual encoder run once over the full document. The score of an arc between two elementary discourse units (EDUs, the clause-like minimal pieces of discourse) therefore does not depend on how the rest of the tree was built. Take a block $b$ of consecutive EDUs that forms a closed subtree. Everything the higher-level parse needs from $b$ is its head EDU $h$ and the best internal score

$$I(b,h) = \max_{t \in T(b,h)} \sum_{(i \to j) \in t} s(i \to j),$$

where $T(b,h)$ is the set of projective trees over $b$ rooted at $h$ and $s(i\to j)$ is the encoder's arc score. Two block-internal derivations with the same $(b,h)$ are fully interchangeable for all higher-level scoring. Recombining them is therefore exact, not the suffix-matching approximation of neural MT decoding. This answers the gap the NMT recombination work leaves open for bidirectional encoders: exactness comes from factorization, not from state similarity.

The boundary lattice decides which blocks exist. Candidate boundaries, meaning sentence ends, paragraph ends, and in speech or unpunctuated text predicted clause ends, become lattice nodes. A lattice arc is a candidate block spanning up to $m$ consecutive base segments, scored by a light boundary model $g(b)$ that estimates whether the block closes off a subtree. Dissolving a boundary (a block spanning two sentences) is exactly what permits a cross-sentence arc from a non-root EDU. A document parse chooses a path of blocks through the lattice, a head for each block, and an inter-block tree over those heads. It maximizes

$$\sum_{b \in \text{path}} \big(g(b) + I(b, h_b)\big) + \sum_{(h_b \to h_{b'})} s(h_b \to h_{b'}).$$

With $m=1$ and firm boundaries this reduces to Hierarchical Eisner. With $m$ equal to the whole document it reduces to unconstrained Eisner. The width $m$ and the pruning of $g$ set the dial between the two.

Research Program

We would build the parser in three pieces. The first is the block-internal chart. Each candidate block runs Eisner once and stores $I(b,h)$ for every head. Because candidate blocks overlap, charts for nested blocks share work. The second is an inter-block Eisner that runs over a lattice rather than a sequence. Its items carry start and end lattice nodes as in the EACL 2009 lattice parser, so heads from incompatible block choices never combine. The third is a boundary model that scores blocks from the same shared encoder representations and is trained jointly through the structured max-margin or CRF loss of the whole parse. Joint training addresses the gradient-flow limitation noted for lattice decoding: the lattice topology is fixed per document, but its arc scores receive gradients.

We would also analyze complexity. With $K$ base segments of at most $L$ EDUs and width $m$, block charts cost about $K m (mL)^3$ and the inter-block lattice parse is cubic in the number of lattice head-states. When only boundaries that $g$ finds uncertain may be dissolved, this stays near the Hierarchical Eisner cost. We will measure empirical scaling against document length rather than assert it. The overhead lesson from Glaysher & Moldovan, where an expensive clause identifier made the whole system slower, constrains the design: the boundary model must be a linear-time scorer over already-computed encodings.

Before any training we would run an oracle study. For each treebank we will measure what fraction of gold trees, and of gold arcs, are reachable under hard sentence and paragraph constraints versus lattices of width $m=2,3,4$. The file reports the 6.4% cross-clause figure for Japanese monologue but no crossing rate for SciDTB, CDTB, or RST-DT. We will compute it, and if it is negligible on written text the accuracy argument must rest on the predicted-boundary setting.

Baselines

The naive reference is the hard 1-best pipeline. Boundaries are taken as given, or from a segmenter in the noisy setting, and each block's root is fixed before inter-block linking. This is Sentence-First as described by Zhou & Feng, who report 79.3 UAS on SciDTB and 82.2 UAS on CDTB with BERT. It is the strongest published number on those treebanks in the file, and beating it means higher UAS under the same encoder. For the fair comparison we reimplement it with our exact encoder and arc scorer, tuned with the same hyperparameter search budget, so that differences come from search space alone.

The strongest structured competitor is Hierarchical Eisner (Zhang et al.), reported at 79.1 UAS on SciDTB and 70.2 UAS on RST-DT for the supervised adapted model. It performs exact global inference under hard closure constraints, so it isolates whether dissolving boundaries helps. On RST-DT we also report against the granularity-level parser of Kobayashi et al. at 64.9 UAS and 48.5 LAS in dependency conversion. We run Hierarchical Eisner as our own $m=1$ special case with identical scores, which makes the comparison exact.

The accuracy ceiling is unconstrained Eisner over the whole document with the same arc scores. It can express every projective tree, and our method should approach its UAS while approaching Hierarchical Eisner's time and memory. The key ablation replaces the learned boundary scores $g$ with a constant, which keeps the lattice but not the learned permeability. A second ablation passes the top-$k$ roots per block without the lattice; this separates root ambiguity from boundary ambiguity. All systems share training data, encoder, number of epochs, and hardware. Timings are measured on the same GPU and CPU with batch size fixed.

Why not just…?

Why not just run unconstrained Eisner with a learned penalty for crossing boundaries? This is the most serious alternative, because a soft crossing penalty expresses the same preference our $g$ does. Our parse is essentially that model restricted to lattice-reachable trees. If the oracle study shows width-2 or width-3 lattices reach almost every gold tree, the two should match in accuracy, and the question becomes cost alone. On short SciDTB abstracts cubic Eisner is cheap, and we expect no speed advantage there; we will say so. The claim is tested on RST-DT's long documents and on artificially concatenated documents of growing length, where Zhang et al. report that unconstrained memory grows cubically. If soft-penalty Eisner is both as accurate and affordable at the lengths that matter, the proposal reduces to an efficiency trick, and we will report it that way.

Why not just keep the top-$k$ roots per sentence in a Sentence-First pipeline? This fixes the wrong-root failure of Zhou & Feng cheaply, and our $(b,h)$ table already contains it as the $m=1$ case with all heads kept. What it cannot express is a non-root EDU attaching across a sentence break. The top-$k$ ablation measures how much of our gain comes from root ambiguity alone. If it captures nearly all of the gain, the lattice over boundaries is unnecessary for written text.

Why not just use a top-down pointer network that splits anywhere? RST Parsing from Scratch avoids hard segmentation, and is fast at 19 seconds for the test set, but it reaches only 46.6 full F1 end-to-end and 50.2 with gold segmentation. Its early split decisions are also irrevocable under beam search, and its beam never merges identical sub-problems. We compare on RST-DT span metrics after converting our dependency output, while acknowledging that the conversion adds noise.

Why not just enlarge the beam or use dual decomposition as in the Chinese lattice work? Large beams duplicate identical subproblems; the NMT recombination study shows doubling beam size roughly halves throughput for a 0.06 BLEU difference. Dual decomposition (Wang, Zong & Xue) requires repeated full parses until the tagger and parser agree. Our single dynamic program is exact for its search space, so neither is needed once the factorization holds.

Proposed Experiments

The main experiments run on SciDTB, CDTB, and RST-DT (dependency conversion), measuring UAS, LAS, intra- versus inter-sentential attachment accuracy, and accuracy on the gold arcs that cross sentence or paragraph boundaries. That last subset is the one hard-boundary systems cannot get right by construction. The noisy-boundary regime strips punctuation and paragraph marks and predicts boundaries with a tagger. There we expect the gap to the hard pipeline to grow, since segmentation errors become recoverable. Where the Asu-Wo-Yomu corpus is available, we apply the same lattice to clause boundaries in Japanese monologue. There the 6.4% cross-clause rate from Ohno et al. gives a known target, and their 80.1% accuracy is the reference to beat under their setup.

Efficiency is reported as wall-clock time and peak memory against document length, including concatenated RST-DT documents to stress long inputs. It is compared against both Hierarchical Eisner and unconstrained Eisner.

Three decisive checks settle the proposal. First, on cross-boundary gold arcs our parser must recover a substantial fraction where Hierarchical Eisner recovers none by construction, with no loss on within-boundary arcs. Second, overall UAS must exceed the reimplemented Sentence-First and Hierarchical Eisner baselines and come within noise of unconstrained Eisner. Third, at the longest document lengths, time and memory must stay close to Hierarchical Eisner and clearly below unconstrained Eisner.

Two outcomes would falsify the idea. If the oracle study finds almost no boundary-crossing arcs on written treebanks and the noisy-boundary gains vanish, the lattice is not needed. If the top-$k$-roots ablation matches the full system, dissolving boundaries is not the source of the gain.