In extractive summarization, the goal is to select a small subset of sentences from a document (or a cluster of documents) that captures the most important information. For years, the default approach was greedy selection: rank sentences by an importance score and pick the top ones until you hit a word limit.
However, research across two decades has shown that this local, one-at-a-time decision-making is fundamentally flawed. It leads to redundancy, poor coverage, and sub-optimal summaries. The field has instead moved toward framing summarization as a global optimization problem, where the system evaluates the quality of the entire summary at once rather than the quality of individual sentences in isolation.
The Greedy Trap
Imagine you are packing a suitcase with a strict weight limit. A greedy approach would be to grab the single most important item (say, your laptop), then the next most important (a heavy winter coat), and so on. By the time you reach the weight limit, you might have three very important items but no room for socks, a toothbrush, or a charger.
In summarization, Hiroya Takamura and Manabu Okumura argue that greedy algorithms fail because they don't account for the global relationship between units. As noted in Text Summarization Model based on Maximum Coverage Problem and its Variant, picking the "best" sentence first often introduces information that overlaps with the "second-best" sentence. If two sentences convey the same key point, a greedy system might pick both, wasting the limited word budget.
Summarization as Combinatorial Optimization
To solve this, researchers like Daniel Gillick and Benoît Favre reframed the task. Instead of asking "Which sentence is best?", they ask "Which combination of sentences covers the most unique concepts?"
This is formally known as the Maximum Coverage Problem (MCP). In the ICSI Summarization System, the authors use Integer Linear Programming (ILP) to find the exact set of sentences that maximizes the weight of unique bigrams (concepts) within a length constraint. This shift transforms summarization from a linguistic ranking task into a mathematical search for a global optimum.
Holistic Inference and Subset Selection
The move toward global views isn't just about math; it's about how models "see" the document. Traditional sequence-labeling models often suffer from "tunnel vision." As Mirella Lapata and Yumo Xu point out in their work on OREO, standard greedy labeling fails to explore the broader search space.
Newer frameworks, such as the one proposed in Unsupervised Multi-document Summarization with Holistic Inference, use metrics like the Subset Representative Index (SRI). Instead of scoring sentences individually, these systems use holistic beam search to select a collection of sentences that collectively maximize information. This ensures that the final summary isn't just a list of high-scoring sentences, but a cohesive set that functions as a representative "reconstruction" of the original text, a concept explored by Chun Chen in Document Summarization Based on Data Reconstruction.
Balancing Importance and Redundancy
The challenge of global optimization is balancing two competing forces: salience (importance) and redundancy.
- Salience: Ensuring the summary contains the most critical information.
- Redundancy: Ensuring that once a piece of information is included, it isn't repeated.
Andy Su and colleagues addressed this in PoBRL by using Reinforcement Learning to blend two separate policies—one for finding critical info and one for avoiding repetition. Similarly, Jun Suzuki and Tsutomu Hirao have long advocated for global optimization frameworks to maintain consistency across entire text clusters, particularly when aligning summaries with source documents.
Why It Works
Global optimization works because it treats the summary as a budgeted resource. In Automatic Summarization as a Combinatorial Optimization Problem, the researchers demonstrate that the best summaries often include "medium-value" shorter sentences that fit together like puzzle pieces, rather than "high-value" long sentences that hog the entire word budget.
By evaluating the collective risk or collective benefit of a sentence set—as seen in the Risk Minimization Framework by Shih-Hsiang Lin—these models achieve a level of information density and narrative coherence that greedy, local methods simply cannot reach.