Sentence compression is the art of trimming a sentence down to its core meaning. In an ideal world, an automated system could simply scan a sentence, identify the least informative words, and delete them.
However, language is not a linear sequence of independent words; it is a hierarchical structure of nested dependencies. When compression algorithms treat sentences as flat sequences, they inevitably produce ungrammatical "word salad." For instance, a model might delete a head noun while retaining its modifying adjective, or drop a verb while keeping its direct object.
To solve this, a major direction in natural language processing focuses on syntactic preservation. By forcing compression models to respect the hierarchical relationships between words, researchers ensure that even aggressively shortened sentences remain fluent and grammatically intact.
The Failure of Flat Deletion
Early or naive approaches to sentence compression often framed the task as a binary sequence labeling problem: for every word in a sentence, the model decides whether to keep it or delete it. As Nomoto (2008) observes, treating compression as a simple sequence labeling task frequently yields unintelligible text because it ignores underlying syntactic structures.
This failure stems from what Gupta et al. (2009) call the "locality assumption"—the mistaken belief that a deletion decision can be made locally without looking at the broader sentence architecture. When a model operates under this assumption, two primary linguistic errors occur:
- Head-Modifier Violations: In grammar, modifiers (like adverbs and adjectives) depend on their heads (like verbs and nouns). If a model deletes the head but keeps the modifier (e.g., keeping "quickly" but deleting "ran"), the remaining text becomes a fragmented artifact (Clarke et al., 2006; Bingel et al., 2016).
- Argument Dropping: Verbs have strict lexical requirements regarding their arguments (subjects, objects, and complements). Non-lexicalized or flat models often prune away mandatory verb complements, leaving the sentence structurally incomplete (Daumé III et al., 2002; Turner et al., 2005).
As the target compression rate becomes more aggressive, the tension between brevity and fluency intensifies (Chaudhuri et al., 2009; Berg-Kirkpatrick et al., 2011). Without structural boundaries, explicit content deletion creates a steep trade-off where information density comes at the direct expense of grammatical correctness (Zhang et al., 2018).
Compression as Global Optimization
To prevent these structural breakdowns, researchers introduced global inference frameworks, most notably using Integer Linear Programming (ILP). Instead of making isolated word-by-word choices, ILP allows a system to evaluate the entire sentence at once, optimizing for word informativeness while enforcing strict linguistic rules.
The intuition behind this approach is elegant: we can translate grammatical rules into mathematical constraints. For example, to preserve a dependency relation, we can introduce an implication constraint:
$$\text{If Modifier is retained} \implies \text{Head must be retained}$$
In the framework developed by Clarke et al. (2006) and expanded in Clarke et al. (2008), these constraints are combined with an $n$-gram language model. The optimization objective balances the semantic weight of the chosen words against the probability of their sequence, all while operating within a rigid boundary of syntactic rules.
This global perspective ensures that the model cannot accidentally isolate a modifier or drop a required verb argument. Similar ILP formulations have been successfully deployed to jointly handle content selection and compression in broader summarization tasks, ensuring that multi-sentence outputs remain readable and referentially clear (Woodsend et al., 2010; Durrett et al., 2016).
Operating Directly on Trees
While ILP overlays constraints onto a linear sequence, an alternative and highly effective strategy is to abandon the linear sequence altogether and operate directly on the sentence's syntax tree. If language is shaped like a tree, compression should be framed as tree pruning.
[jumps] <-- Root (Must keep if arguments are kept)
/ \
[fox] [over]
/ \
[the] [dog]
\
[lazy] <-- Leaf (Optional modifier)
By utilizing dependency parsing, models can identify the grammatical core of a sentence (the root verb and its core arguments) and safely prune away peripheral subtrees (such as prepositional phrases or non-essential modifiers) (Liu et al., 2010).
For example, Nomoto (2008) limits a model's search space exclusively to syntactically valid candidates generated via dependency truncation. Similarly, Wang (2013) uses a tree-pruning approach paired with a beam search decoder to strip away irrelevant details while maintaining a stable grammatical backbone. Bingel et al. (2016) formalize text simplification as a tree-labeling task using Conditional Random Fields (CRFs) over dependency trees, ensuring that entire subtrees are deleted or paraphrased as cohesive units.
Overcoming Computational Overhead
Historically, optimizing over complex tree structures was computationally expensive. To bridge this gap, researchers developed sparse optimization and localized search techniques. Yao et al. (2015) introduced a recursive dependency-tree pruning method solved via an efficient Alternating Direction Method of Multipliers (ADMM) framework.
To accelerate this further, Yao et al. (2017) proposed a "Greedy Flipping" algorithm. Instead of invoking heavy global solvers, this method runs a randomized local search that traverses dependency trees, evaluating word deletions while instantly verifying syntactic policy constraints. This achieves the grammatical precision of global optimization at a fraction of the computational cost.
The Neural Era and Data Realities
The transition to deep learning and sequence-to-sequence architectures did not eliminate the need for structural awareness. Even powerful neural network models, when left unconstrained, are prone to deleting arbitrary functional words or generating nonsensical fragments (Xu et al., 2019). To counter this, modern architectures often feature a hybrid design—such as pairing a neural sentence-selection module with a linguistically-informed syntactic compression module to ensure factual and grammatical integrity (Xu et al., 2019).
Finally, this research direction highlights a critical insight regarding training data. Gupta et al. (2009) discovered that human-generated "gold standard" compression corpora frequently violate basic grammatical rules when viewed purely through a deletion lens. This occurs because human editors do not just delete words; they perform complex, abstractive syntactic transformations.
This finding underscores why hardcoded syntactic constraints and tree-based operations are so vital: because training data is often structurally inconsistent, models cannot rely on statistical imitation alone to learn grammar. They require an explicit, structurally-enforced understanding of syntax to compress text reliably.
Key Foundational Work
A Noisy-Channel Model for Document Compression (2002) — contributed 2 concept elements to this direction.
Supervised and Unsupervised Learning for Sentence Compression (2005) — contributed 1 concept elements to this direction.