When we compress a sentence, our goal is to strip away the fluff while preserving its core meaning and grammatical correctness. Early statistical models approached this by treating a sentence as a flat sequence of words, making local deletion decisions token by token. However, as Naman Gupta et al. demonstrated in Evaluating the Syntactic Transformations in Gold Standard Corpora for Statistical Sentence Compression, human compression relies on complex syntactic transformations that flat, locality-based models cannot easily capture. Deleting words independently frequently results in "word salad"—sentences that lack subjects, leave modifiers dangling, or drop crucial verb arguments.
To solve this, a powerful paradigm emerged: treating sentence compression as an operation over a hierarchical syntactic structure, such as a constituency or dependency parse tree. Instead of deleting isolated words, models prune entire syntactic units.
Framing Compression as Tree Pruning
The core intuition behind syntactic compression is that natural language is inherently hierarchical. If you decide to remove a word or phrase, you must also remove everything that depends on it to maintain grammatical integrity.
In a constituency tree framework, as explored by Taylor Berg-Kirkpatrick et al. in Jointly Learning to Extract and Compress, compression is restricted to deleting specific non-essential subtrees, such as relative clauses or prepositional phrases. Similarly, Lu Wang et al. in A Sentence Compression Based Framework to Query-Focused Multi-Document Summarization showed that deleting parent nodes along with their children ensures that the remaining text fragments adhere strictly to a valid linguistic hierarchy.
Alternatively, dependency trees map direct grammatical relationships between words (such as a verb and its object). Tadashi Nomoto utilized this in A Generic Sentence Trimmer with CRFs by tracing paths from leaf nodes to the root to generate a finite set of grammatically plausible candidates. By operating at the level of subtrees, single-author works like Joachim Bingel's Text Simplification as Tree Labeling ensure that if a phrase head is removed, its entire dependent structure is discarded simultaneously, preventing the creation of ungrammatical fragments.
Enforcing Structural Integrity via Optimization
To mathematically guarantee that a compression algorithm respects these tree structures, researchers encode linguistic rules as hard constraints within a global optimization framework, typically Integer Linear Programming (ILP).
In their foundational work, James Clarke et al. in Constraint-Based Sentence Compression: An Integer Programming Approach introduced linear inequalities to enforce dependency constraints: if a dependent word is kept, its head word must also be kept. For example, an adjective cannot survive if the noun it modifies is deleted. James Clarke et al. expanded this in Global Inference for Sentence Compression: An Integer Linear Programming Approach to ensure a verb's core arguments are preserved.
This "head-presence" requirement transforms compression into a structural optimization problem. In Oracle Summaries of Compressive Summarization, Tsutomu Hirao demonstrated that this hierarchical pruning strategy successfully maintains basic grammatical relationships during text reduction. To scale this up efficiently, Kapil Thadani developed approximation strategies in Approximation Strategies for Multi-Structure Sentence Compression using Lagrangian relaxation to decouple local word fluency from global structural dependencies.
Beyond ILP, researchers have framed subtree extraction as a submodular maximization problem. Hajime Morita demonstrated in Subtree Extractive Summarization via Submodular Maximization that "must-link" constraints within dependency graphs successfully maintain high readability by ensuring obligatory arguments are preserved. This was further optimized by Shinsaku Sakaue et al. in Provable Fast Greedy Compressive Summarization with Any Monotone Submodular Function, proving that greedy selection algorithms can efficiently handle these hierarchical constraints.
Syntactic Constraints in the Neural Era
As natural language processing shifted toward deep learning, the insights from syntactic tree pruning remained vital. While neural networks like LSTMs and Transformers excel at capturing local context, they often struggle to generalize across domains or maintain strict grammatical boundaries when deleting tokens.
To address this, Jing Jiang et al. combined deep learning with structural constraints in Can Syntax Help? Improving an LSTM-based Sentence Compression Model for New Domains. By enforcing dependency-based rules via ILP on top of a Bi-LSTM, the authors prevented the generation of ungrammatical fragments and significantly improved cross-domain generalization.
Similarly, Jiacheng Xu et al. introduced "syntactic span pruning" in Neural Extractive Text Summarization with Syntactic Compression, restricting a neural model's deletions to valid syntactic units (like appositives or relative clauses) identified via constituency parsing. This hybrid approach ensures the fluency of modern text-shortening systems while eliminating the risk of semantic fragmentation.
Key Foundational Work
Symbolic word clustering for medium-size corpora (1996) — contributed 1 concept elements to this direction.