Global Optimization for Text Summarization

253 concepts165 papers1 proposal

Imagine you are packing a backpack for a long hike, and you have a strict weight limit. A greedy approach to packing would have you look at all your items, pick the single most valuable one, put it in the bag, and repeat the process until the bag is full.

But what if picking two slightly smaller items would yield a higher total value than that one massive item? By making irreversible early choices, a greedy strategy frequently misses the optimal combination.

In text summarization, the "backpack" is the summary length budget (e.g., a strict limit of 100 words or 500 characters), and the "items" are sentences, phrases, or semantic concepts. Traditional extractive summarization systems rely on greedy heuristics to pick sentences sequentially. As noted by Daniel Gillick et al. in The ICSI Summarization System at TAC 2008, these local decisions fail to find the global optimum because they cannot efficiently balance the overlapping information between multiple sentences at the same time.

To maximize information density under strict constraints, a prominent research direction treats summarization not as a sequential guessing game, but as a problem of global combinatorial optimization.

Framing Summarization via the Knapsack Problem

To solve summarization globally, we can reframe the task as a classic resource allocation problem: the Knapsack Problem or the Maximum Coverage Problem. Instead of scoring sentences in isolation, the goal is to maximize the aggregate value of the information contained within the summary, subject to a hard capacity constraint.

Wen-tau Yih et al. demonstrated this shift in Multi-Document Summarization by Maximizing Informative Content-Words. Rather than treating sentences as the atomic units of selection, they focused on maximizing the total score of informative content-words across the entire summary. By using a global search strategy, their system evaluated combinations of sentences to ensure the most valuable mixture of information was packed into a strict word limit.

This framing applies equally well to tight physical interfaces. For example, Yu Gong et al. in Automatic Generation of Chinese Short Product Titles for Mobile Display treated text compression as a resource allocation problem, using dynamic programming to maximize word importance within the strict character limits of mobile screens.

The Engine of Global Selection: Integer Linear Programming

The dominant mathematical tool used to enforce these global trade-offs is Integer Linear Programming (ILP). ILP allows researchers to define binary decision variables (for instance, $x_i = 1$ if sentence $i$ is included in the summary, and $0$ otherwise) and optimize a global objective function under linear constraints.

Consider the concept-based optimization framework popularized by Daniel Gillick et al. Instead of maximizing arbitrary sentence scores, the objective function maximizes the coverage of unique "concepts" (such as word bigrams). If two sentences share the same bigram, the ILP formulation ensures that the bigram's weight is only counted once in the objective function.

As Feng Jin explains in The THU Summarization Systems at TAC 2010, this mathematical setup implicitly manages redundancy. The solver is disincentivized from picking repetitive sentences because they consume the word budget without increasing the objective score. By solving the optimization problem globally, the system finds the exact combination of sentences that packs the maximum amount of unique information into the allowed space.

Enforcing Structural and Linguistic Constraints

One of the greatest strengths of the ILP framework is its flexibility. It allows researchers to introduce complex, non-local constraints directly into the optimization process. Summarization is not just about picking a "bag of words"; the output must be grammatically coherent and structurally sound.

When moving from extracting whole sentences to compressing them, we must ensure that trimming a sentence does not destroy its syntactic integrity. In Constraint-Based Sentence Compression: An Integer Programming Approach, James Clarke et al. introduced linguistically motivated linear constraints into an integer programming model. For example, a constraint can dictate that if a modifier word is kept in the compressed sentence, its head noun must also be kept.

This structural awareness can be scaled up to handle entire documents by leveraging discourse trees. Tsutomu Hirao et al. formulated summarization as a "Tree Knapsack Problem" in Single-Document Summarization as a Tree Knapsack Problem. By converting rhetorical structure trees into dependency trees, they used ILP to maximize content significance while enforcing parent-child structural dependencies: a child node (a supporting detail) can only be selected if its parent node (the main thesis) is also included in the summary.

Joint Optimization of Content and Form

Because an ILP solver evaluates all variables simultaneously, it enables systems to handle multiple stages of the summarization pipeline at once, rather than relying on a fragile, step-by-step assembly line where early errors cascade downward.

For instance, Lidong Bing et al. developed a framework in Abstractive Multi-Document Summarization via Phrase Selection and Merging that breaks source documents down into noun and verb phrases. The ILP solver then simultaneously selects and merges these cross-document fragments into entirely new sentences, optimizing for information salience and grammatical validity in a single mathematical step.

Similarly, Chen Li et al. demonstrated in Document Summarization via Guided Sentence Compression that joint optimization allows a system to compress sentences on the fly while selecting them. This ensures that the final summary achieves maximum bigram coverage across the entire document set while strictly adhering to a predefined word count budget.

Key Foundational Work

Reluctant Paraphrase: Textual Restructuring under an Optimisation Model (1997) — contributed 4 concept elements to this direction.
History & citationVersion 2 · 2026-10-04

Current · Permanent link

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

Latest version (a living page):

@misc{lacuna_global_summary_optimization_1f3ec45c,
  title = {global summary optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/global-summary-optimization/rdr_1f3ec45c1998472fb3bfd9cb08beeecb},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 2, frozen text):

@misc{lacuna_global_summary_optimization_1f3ec45c_v2,
  title = {global summary optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/global-summary-optimization/rdr_1f3ec45c1998472fb3bfd9cb08beeecb/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-20},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake