The Deletion Constraint in Sentence Compression

34 concepts30 papers2 proposals

Sentence compression is a fundamental task in text optimization: given a long sentence, the goal is to produce a shorter version that retains the core meaning and remains grammatically correct. Historically, the most straightforward way to model this task is through token deletion. By treating compression as a binary sequence labeling problem—where every word is either kept ($1$) or dropped ($0$)—the problem becomes computationally clean and highly efficient.

As demonstrated by Katja Filippova et al. in Sentence Compression by Deletion with LSTMs, neural networks like LSTMs can achieve remarkably high readability scores simply by learning which tokens to prune from a large corpus. This extractive approach avoids the massive search space of natural language generation, guarantees that the model will never hallucinate new words, and preserves the exact vocabulary of the source text. It allows for exact global optimization via Integer Linear Programming (ILP), as seen in the work of James Clarke et al. in Constraint-Based Sentence Compression: An Integer Programming Approach, and scales efficiently using approximation strategies like Lagrangian relaxation developed by Kapil Thadani in Approximation Strategies for Multi-Structure Sentence Compression. Even in modern contexts like large language model prompt optimization, Hoyoun Jung leverages discrete token deletion in Discrete Prompt Compression With Reinforcement Learning to maintain interpretability and API compatibility across black-box models.

Yet, despite its mathematical convenience, the deletion-only framework suffers from a fundamental linguistic bottleneck. When humans compress text, they do not merely cross out words; they rewrite, reorder, and synthesize. Restricting a model strictly to token deletion introduces severe constraints that limit the naturalness, fluidity, and ultimate conciseness of the compressed text.

The Linguistic Bottleneck of Pure Deletion

The core limitation of deletion-based compression is its inability to alter the remaining text to fit its new syntactic context. This manifests in several distinct ways:

The Lack of Lexical Substitution and Paraphrasing

A deletion-only model cannot replace a wordy phrase with a concise synonym. For example, it cannot transform "at this point in time" into "now". As argued by Jenine Turner et al. in Supervised and Unsupervised Learning for Sentence Compression and Sourish Chaudhuri et al. in Leveraging Structural Relations for Fluent Compressions at Multiple Compression Rates, this restriction prevents systems from achieving the natural fluidity found in human-authored summaries, forcing the output to remain bound to the exact phrasing of the source.

The Reordering Problem

Natural languages rely heavily on word order to convey grammatical relationships. When words are removed from a complex sentence, the remaining tokens often form an ungrammatical "word salad" or a disjointed, telegraphic sequence. Steven Layne highlights this in Improving Human Text Comprehension through Semi-Markov CRF-based Neural Section Title Generation, noting that deletion-only models frequently produce rigid, ungrammatical titles because they cannot reorder words to satisfy standard linguistic conventions. Juhani Luotolahti echoes this challenge in the context of subtitle generation in Sentence Compression For Automatic Subtitling, where strict space constraints require structural flexibility that deletion alone cannot provide.

Morphological and Contextual Rigidity

In morphologically rich languages, words change their internal structure based on their role in a sentence. Muhammed Yavuz Nuzumlali et al. demonstrate in Analyzing Stemming Approaches for Turkish Multi-Document Summarization that simple token deletion fails when sentences contain high amounts of morphological information, as the model cannot trim or alter suffixes to maintain grammatical agreement. Furthermore, as Chen Li et al. observe in Improving Multi-documents Summarization by Sentence Compression based on Expanded Constituent Parse Trees, deletion-based models cannot adjust verb tenses or case markings when a sentence is shortened, resulting in jarring transitions for the reader.

The Generality Gap

Human summarizers compress information by generalizing specific details into high-level concepts (e.g., rewriting a list of specific items into a single category word). Annie Louis et al. show in Text Specificity and Impact on Quality of News Summaries that standard deletion techniques prevent automated systems from achieving aggressive compression rates because they cannot perform this semantic generalization. Similarly, Yejin Choi notes in Generalizing Image Captions for Image-Text Parallel Corpus that deletion-only simplification cannot replace specific terms with broader categories, limiting the utility of the compressed text.

Mitigating the Constraint via Structural Guidance

To prevent deletion-only models from generating ungrammatical text, researchers initially sought to constrain the deletion process using explicit syntactic and logical rules. Instead of treating deletion as an independent sequence of binary choices, these approaches map sentences to structural representations—such as dependency trees or phrase structure trees—and enforce rules over those structures.

For example, the optimization framework proposed by James Clarke et al. uses linguistically motivated constraints within an ILP solver, enforcing rules like "if you keep a modifier, you must keep its head." To combine statistical learning with hard logical boundaries, Minlie Huang et al. introduce Markov Logic Networks in Using First-Order Logic to Compress Sentences, allowing models to respect global grammatical constraints and local linguistic features simultaneously.

When modern deep learning models emerged, researchers found that pure data-driven sequence labeling still struggled to generalize across domains without making structural errors. To address this, Jing Jiang et al. in Can Syntax Help? Improving an LSTM-based Sentence Compression Model for New Domains injected explicit part-of-speech and dependency features into Bi-LSTMs, enforcing grammatical rules via ILP post-processing.

[Original Sentence] 
The fierce storm, which hit the coast early Monday, destroyed the pier.
  │      │                                              │          │
  └─Drop─┘ (Modifier without head constraint)           └─Keep─────┘

[Syntactically Constrained Deletion]
The storm destroyed the pier.

While these structural guardrails significantly improve readability and prevent "word salads," they only patch the symptoms of the deletion constraint; they do not cure the underlying limitation. The model is still trapped within the vocabulary and word order of the source sentence. As Lu Wang et al. note in A Sentence Compression Based Framework to Query-Focused Multi-Document Summarization and Kristian Woodsend et al. observe in Multiple Aspect Summarization Using Integer Linear Programming, when compression is used as a downstream tool for multi-document summarization, deletion-only frameworks ultimately struggle to pack information densely because they cannot synthesize or reorganize text.

Shifting from Deletion to Abstractive Rewriting

Recognizing that deletion-only compression hits a hard ceiling, the trajectory of the field shifted toward frameworks that allow for true abstractive transformations.

A pivotal step in this direction was taken by Trevor Cohn et al. in Sentence Compression Beyond Word Deletion, which explicitly advocated for moving beyond extractive pruning into abstractive rewriting. To model these complex structural changes mathematically, researchers turned to Synchronous Tree-Substitution Grammars (STSG). Rather than operating on flat strings, STSGs allow models to learn transduction rules between pairs of trees.

The authors of Large Margin Synchronous Generation and its Application to Sentence Compression combined STSGs with a structured SVM framework to handle phrase substitutions and structural reordering. Similarly, Elif Yamangil et al. introduced a nonparametric Bayesian approach in Bayesian Synchronous Tree-Substitution Grammar Induction and Its Application to Sentence Compression to automatically discover a sparse, compact set of rewriting rules. These grammar-based approaches provided the mathematical machinery needed to transition from simple deletion to complex structural transformations, balancing information retention with grammatical correctness.

      [Source Tree]                           [Target Tree]
           NP                                      NP
     ┌─────┼─────┐                                 │
    DT    JJ    NN                                NN
    The  green  car                               Cars

In the era of deep learning, this evolution culminated in hybrid editing frameworks. For instance, Jie Zhang et al. proposed an explicit editing framework in An Operation Network for Abstractive Sentence Compression that treats compression as a combination of deletion and generation operations. By allowing the model to choose whether to delete an existing token or generate a new phrasing entirely, it bridges the gap between the precision of extractive methods and the synthesis power of abstractive generation.

Ultimately, the study of sentence compression reveals a fundamental trade-off in natural language processing: while restricting models to token deletion offers computational simplicity and guarantees factual alignment with the source text, it creates a rigid linguistic ceiling. Overcoming this deletion constraint requires moving toward generative and structural transduction models that can rewrite, reorder, and abstract information just as a human editor would.

Key Foundational Work

Constraint-Based Sentence Compression: An Integer Programming Approach (2006) — contributed 1 concept elements to this direction.
Supervised and Unsupervised Learning for Sentence Compression (2005) — contributed 1 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 30 papers
  2. Version 1 · 2026-10-04 · 28 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_extractive_only_compression_a4bff852,
  title = {extractive-only compression},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/extractive-only-compression/rdr_a4bff852fac44b2fbb0a591d95851fa8},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-21},
}

This exact version (version 2, frozen text):

@misc{lacuna_extractive_only_compression_a4bff852_v2,
  title = {extractive-only compression},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/extractive-only-compression/rdr_a4bff852fac44b2fbb0a591d95851fa8/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-21},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake