Global Cut-Based Planning for Unsupervised Document Simplification

Simplifying a whole document means deciding, for every sentence, whether to keep it, rewrite it, split it, or drop it. Those decisions depend on each other. If you delete the sentence that introduces "the committee", every later "it" loses its referent. Systems that learn these decisions do so from aligned pairs of complex and simple documents, and such pairs exist almost only for English Wikipedia and news. Systems that need no aligned data work one sentence at a time, so they cannot make the cross-sentence choices that make up much of real simplification. We propose treating the per-sentence plan as one joint labeling problem, solved exactly or near-exactly with graph cuts. The costs come only from unaligned text and off-the-shelf tools. The inter-sentence penalties encode references and discourse links, so no locally cheap deletion can leave the document broken.

The idea comes from a neighbouring field that faced the same structure. In 3D reconstruction, an unsigned distance field (UDF) stores each point's distance to a surface with no inside/outside sign. Recovering a mesh from it cannot be done by local per-voxel decisions, because noise near the surface produces holes and tears. The fixes that worked were global: a minimum cut that peels one layer off a doubled surface, and multi-label graph-cut partitioning of space. We carry that lesson, not the geometry, into text. Local sentence decisions tear discourse, and a global cut over a sentence graph can repair it.

Core Claim

We claim that a document plan chosen by minimizing one energy over a sentence graph gives better unsupervised document simplification than either independent per-sentence decisions or sentence-level unsupervised rewriting. "Better" means fewer orphaned references, less degenerate over-deletion, and higher document-level simplification scores. The energy has one cost per sentence and a penalty for each linked pair of sentences, and it is built without aligned data. The keep-versus-delete part of this energy can be solved exactly. The full four-way plan can be solved with a standard approximate graph-cut method.

The gain should be largest where aligned data is absent: German and Japanese, and domains outside Wikipedia. There, the only other options are pivot translation, sentence-level systems, or prompting.

Where This Sits

The planning structure comes from Document-Level Planning for Text Simplification. That work predicts Copy, Rephrase, Split, or Delete for each sentence with a RoBERTa classifier over a 13-sentence window, then conditions a BART generator on the plan. It also finds that deletion is driven by wide context while splitting is mostly sentence-internal. That finding motivates our design: deletion needs global coupling, and splitting can stay a local cost. Its classifier, however, is trained on operation labels extracted from aligned Wiki-auto and Newsela-auto data, and it predicts each label without enforcing consistency among them. We remove both dependencies.

Two lines of work motivate the gap. Document-Level Text Simplification: Dataset, Criteria and Baseline shows that deletion is 44% of human edits on D-Wikipedia. It also shows that SARI, a metric that rewards words the system correctly keeps, adds, and deletes relative to references, can be inflated by keeping the lead sentence and discarding the rest. SWiPE finds that 43% of human edits cross sentence boundaries or need document context.

The unsupervised side is sentence-bound. MUSS mines paraphrase pairs with single-sentence embeddings and steers a BART model with control tokens for length, word frequency, and syntactic depth; its mining yields only one-to-one pairs. CUT uses back-translation and simplicity-aware beam search, again per sentence. Iterative Edit-Based Unsupervised Sentence Simplification searches over local edits scored by fluency, readability, and meaning preservation. We reuse MUSS-style control tokens as the executor of our plan, and borrow the edit-search scoring ideas for our per-sentence costs.

GUTS is the one unsupervised paragraph-level system. It trains with reinforcement learning on composite rewards and reports ungrammatical output, rare splitting, and corrupted numbers and dates. This is a constraining negative result: unconstrained token-level optimization over paragraphs is unstable. It pushes us to put the global decisions in a discrete planner and keep generation local and conservative.

On the geometry side, DCUDF uses a dual-graph minimum cut to separate a doubled surface. MIND casts non-manifold reconstruction as multi-region labeling solved by α-expansion, a graph-cut method that repeatedly lets one label claim territory from the others. Both are responses to the failure of local extraction reported by MeshUDF and High Resolution UDF Meshing via Iterative Networks. We take the optimization machinery and its guarantees. We claim nothing about distance fields in text.

Research Program

Each document becomes a graph whose nodes are sentences. Each sentence $i$ gets a label $\ell_i$ from {Copy, Rephrase, Split, Delete, Resolve}. Resolve means "rephrase and replace the leading pronoun with its antecedent mention." The plan minimizes

$$E(\ell) = \sum_i U_i(\ell_i) + \sum_{(i,j)} w_{ij}\, P(\ell_i, \ell_j) + \lambda \sum_i [\ell_i \ne \text{Delete}],$$

where $U_i$ is the cost of giving sentence $i$ a label, $w_{ij}$ is the strength of the link between sentences $i$ and $j$, $P$ is the penalty for an inconsistent pair of labels, and $\lambda$ is a per-sentence price for keeping content.

Per-sentence costs. All terms in $U_i$ are computed without aligned data. The cost of Delete falls with the sentence's peripherality, measured by embedding centrality within the document. It rises with the number of named entities and numbers that appear nowhere else, since deleting those loses unique facts. The costs of Split and Rephrase fall with the sentence's complexity: dependency depth, length, and lexical rarity measured against a simple-language corpus. They rise with the risk that a controllable simplifier fails to preserve the sentence's meaning.

Pair links. Links come from a coreference resolver and a discourse-connective detector. The penalty applies when a sentence is deleted while a later sentence that refers back to it, or opens with a connective depending on it, is kept unchanged. That pair can be made consistent in two ways, deleting both or relabeling the later sentence as Resolve, which rewrites the pronoun as a full mention.

Exactness. Take Copy as 0 and Delete as 1, with $P(1,0)=1$ and $P$ zero otherwise. The pair penalty then satisfies $P(0,0)+P(1,1) \le P(0,1)+P(1,0)$, which is the submodularity condition. So the keep/delete subproblem is solved exactly by a single minimum cut, the textual counterpart of DCUDF's layer-separating cut. The full five-label problem is solved approximately by α-expansion, as in MIND. For documents of tens to hundreds of sentences, both run in milliseconds, so the cost that makes the 3D versions slow does not arise.

Avoiding the deletion shortcut. The price $\lambda$ is swept with parametric max-flow, which returns the whole family of optimal plans across all values of $\lambda$ in one computation. We pick the plan matching a target compression ratio. This stops the method from trading simplicity for deletion, and the compression ratio becomes a user control rather than an artifact of training.

Execution. The plan is carried out by a MUSS-style multilingual controllable simplifier trained only on mined paraphrases, with control tokens set per label. Resolve is done deterministically by string substitution from the coreference chain, so it cannot hallucinate. Multi-sentence fusion and elaborative insertion are left out on purpose. SWiPE's observation that 26% of human simplifications are longer than their sources marks elaboration as a real gap, which we report rather than attempt.

The weights on the cost terms are tuned on 50 development documents per language. Every baseline gets the same tuning budget, and this is the only place any reference data enters.

Baselines

The naive reference point has two parts. The first is the identity output, the complex document copied unchanged. The second is lead-truncation at the same compression ratio as our plan, which directly measures the SARI paradox. Any method that fails to beat lead-truncation on document-level SARI and on human simplicity judgments is not doing simplification.

The strongest unsupervised competitor at comparable model scale is the MUSS simplifier applied to every sentence independently, with no planning. This is exactly our executor minus the planner, so the comparison isolates planning. It is run with the same checkpoint, decoding settings, and tuning budget. MUSS reports 42.65 SARI on ASSET, a sentence-level English benchmark (MUSS). CUT and iterative edit search are run the same way; iterative edit search reports 30.44 SARI on Newsela.

The key ablation keeps our per-sentence costs and removes the pair penalties, labeling each sentence by its cheapest option, with $\lambda$ matched to the same compression ratio. If the orphaned-reference rate and document-level scores do not improve over this ablation, the global-cut idea contributes nothing and the paper's claim fails.

A prompted large language model is run in two ways: end-to-end document simplification, and as a planner that emits the five labels, with generation left to our executor. Both use the same 50 development documents for prompt selection.

Supervised systems serve as upper references rather than competitors. SimDoc reports 50.089 D-SARI on Newsela-S when fully fine-tuned on aligned data and about 30.5 zero-shot. BertSumextabs reports 39.88 D-SARI on D-Wikipedia (Document-Level Text Simplification: Dataset, Criteria and Baseline). No reported result was found on Lacuna for the supervised document planner's generation metrics. Beating it would mean closing a stated fraction of the gap between zero-shot and supervised performance, which we target at half, without any aligned training pairs.

For German, the baselines are GUTS and the German-English-German pivot pipeline, retrained or reproduced under our setup. No reported numeric SARI result was found on Lacuna for either on TextComplexityDE.

Why not just…?

Why not just prompt a large language model to simplify the whole document? This is the real threat. Weak zero-shot numbers such as T5-large's 30.5 D-SARI in the SimDoc paper say little about stronger instruction-tuned models. The evidence that prompting falls short is qualitative: Beyond Sentence-level Text Simplification and Collaborative Document Simplification Using Multi-Agent Systems report coreference breaks and weak control over reading level, and ExpertEase needs multi-agent orchestration to hold consistency. We test this directly. We also run a hybrid in which the language model's label preferences serve as the per-sentence costs inside our cut. If the end-to-end model wins in English, the claim narrows to two regimes where it can still hold: small-model, low-resource languages, and guarantees on orphaned references and number preservation that prompting cannot provide. If the hybrid beats both of its parts, the cut is useful as a consistency layer regardless.

Why not just simplify each sentence and concatenate? In Document-Level Planning, sentence-level BART applied across documents lost to document-planned generation on every reported metric. SWiPE puts 43% of edits beyond its reach. We still run this baseline fully, with MUSS, CUT, and edit search, because it is the honest unsupervised state of the practice.

Why not just use an extractive summarizer for deletions? A summarizer picks salient sentences, but it knows nothing about references between them. It is essentially our ablation with salience as the only cost. The ablation settles whether pair links matter beyond salience.

Why not just pivot through English? On French, MUSS reports pivoting at 33.48 SARI against its own 41.73. GUTS finds that pivoting loses on readability and meaning preservation for German paragraphs. We include the pivot on the German and Japanese data so this is measured at document level, not assumed.

Proposed Experiments

English. Evaluation uses D-Wikipedia, Newsela-S, and SWiPE test sets, with document-level SARI (which adds length penalties to resist the deletion shortcut), SARI, Flesch-Kincaid grade level, and BERTScore meaning preservation. None of these corpora's aligned pairs are used for training.

Low-resource languages. Evaluation uses TextComplexityDE and GWW for German and the Japanese document-level dataset. Here the planner is built from the same unaligned recipe with language-specific coreference tools.

Diagnostics. Two automatic checks accompany every system. The orphaned-reference rate is the share of output pronouns whose antecedent was deleted or unresolved, measured by re-running coreference on the output. Fact retention is the share of source numbers, dates, and entities preserved. Three-way human judgments of simplicity, coherence, and faithfulness are collected on 100 documents per language.

Decisive checks. The first is whether full planning beats the ablation without pair links on the orphaned-reference rate by a clear margin, and on document-level SARI at matched compression. Without that, the global-cut idea fails. The second is whether the plan family from the $\lambda$ sweep dominates lead-truncation at every compression ratio on human simplicity and faithfulness. The third is whether the German and Japanese gains over GUTS, the pivot, and sentence-level MUSS exceed the English gains, as the scarcity argument predicts.

A null result on the first check, with gains coming only from better per-sentence costs, would be reported as the finding. It would mean the lesson from mesh extraction does not transfer to text.