When we summarize a collection of documents, extract keyphrases, or segment a text, we face a fundamental challenge: how do we select a subset of content that is both highly informative and free of redundancy?
If we evaluate sentences or phrases in isolation, we risk selecting multiple items that convey the exact same information. To prevent this, we must evaluate content globally, scoring entire sets of text units based on how well they cover the source material without repeating themselves.
However, this global perspective introduces a massive computational bottleneck. If a document collection contains $n$ candidate sentences or phrases, there are $2^n$ possible subsets to choose from. Finding the absolute best combination under a strict length or word budget is an NP-hard combinatorial optimization problem. As the volume of text scales, finding an exact solution becomes mathematically intractable.
To solve this, researchers have developed a variety of strategies to scale global optimization, balancing mathematical rigor against computational efficiency.
The Integer Linear Programming Bottleneck
A classic approach to global content selection is Integer Linear Programming (ILP), specifically Binary Integer Programming. In this framework, every candidate sentence or phrase is assigned a binary decision variable, $x_i \in \{0, 1\}$, indicating whether it is included in the final output. High-level properties like coverage, diversity, and grammatical coherence are then encoded as linear constraints and objectives.
For example, Hui Lin et al. note that finding the mathematically optimal subset under a strict budget is inherently NP-hard. To model this globally, Hiroya Takamura et al. framed extractive summarization as a Facility Location Problem in Text Summarization Model based on Facility Location Problem, where selected summary sentences act as "facilities" that must optimally cover the "customer" sentences in the source text. Similarly, Qi Zhang et al. used binary integer programming in Keyphrase Extraction from Online News Using Binary Integer Programming to ensure that extracted keyphrases represent an entire news event rather than just the most frequent terms.
The combinatorial complexity intensifies when moving from simple sentence extraction to compressive summarization, where a system must simultaneously decide which sentences to extract and how to trim or compress them. As Taylor Berg-Kirkpatrick et al. demonstrate in Jointly Learning to Extract and Compress, and as explored by Kristian Woodsend et al. in Automatic Generation of Story Highlights, combining extraction and compression expands the search space exponentially.
Exact ILP solvers rely on strategies like branch-and-bound, which exhibit worst-case exponential time complexity. When processing large document clusters or fine-grained text units—such as the noun and verb phrases used by Lidong Bing et al. in Abstractive Multi-Document Summarization via Phrase Selection and Merging—exact solvers quickly bottleneck, making real-time deployment impossible.
Submodular Functions and Greedy Guarantees
One elegant way to bypass the exponential cost of exact solvers without sacrificing mathematical rigor is to exploit submodularity.
A set function $f$ is submodular if it satisfies the intuitive property of diminishing returns: adding an element to a small set provides a greater or equal increase in value than adding that same element to a larger set. In text selection, adding a sentence about a specific topic to a short summary introduces significant new information; adding that same sentence to a long summary that already touches on the topic adds very little value.
Submodular Diminishing Returns:
Small Summary: { A, B } + New Sentence C --> Large Information Gain
Large Summary: { A, B, D } + New Sentence C --> Small Information Gain
Hui Lin et al. leveraged this property in A Class of Submodular Functions for Document Summarization to model the dual goals of coverage and diversity. They proved that while maximizing a submodular function under a budget constraint remains NP-hard, a modified greedy algorithm provides a powerful shortcut. By iteratively selecting the text unit that maximizes the ratio of information gain to cost, the greedy approach guarantees a solution within a constant factor $(1 - 1/e)$ of the absolute theoretical optimum. This mathematical guarantee allows systems to run exponentially faster than exact solvers while ensuring near-optimal quality.
Relaxations and Graph Cuts
For optimization problems that cannot be easily formulated as submodular functions, researchers have designed alternative algorithmic frameworks to accelerate or approximate discrete optimization.
Lagrangian Relaxation
When an ILP problem is difficult to solve because of a few complex, global constraints (such as a strict length budget across multiple objectives), we can "relax" those constraints. In Lagrangian Relaxation for Scalable Text Summarization while Maximizing MultipleObjectives, Masaaki Nishino et al. demonstrated that by moving hard constraints into the objective function and penalizing their violations using Lagrange multipliers, the primary problem decomposes into independent, easily solvable subproblems. This relaxation allows the system to find near-optimal summaries up to 30 times faster than standard exact solvers.
Graph Cuts
Another acceleration strategy maps the discrete selection problem onto a graph structure, transforming combinatorial search into a network flow problem. In Fast Joint Compression and Summarization via Graph Cuts, Xian Qian et al. bypassed slow ILP solvers entirely by framing joint sentence selection and compression as a min-cut/max-flow problem on a graph. Because network flow problems can be solved exactly in polynomial time, this approach achieves a 100x speedup over traditional ILP methods while maintaining competitive summary quality.
Pruning the Search Space and Alternative Paradigms
Instead of modifying the optimization algorithm itself, we can also scale combinatorial methods by drastically reducing the size of the input pool before optimization begins, or by bypassing discrete optimization entirely.
Candidate Pruning and Segmentation
The authors of Learning-Free Unsupervised Extractive Summarization Model, Pilsung Kang et al., introduced a framework that uses pre-trained sentence embeddings and Principal Component Analysis (PCA) to filter out uninformative sentences. By pruning the candidate pool beforehand, the subsequent ILP optimization operates on a much smaller search space.
Similarly, for tasks like semantic annotation and text segmentation, Yassine Mrabet et al. and Matthias Sperber et al. utilized document partitioning to break massive text corpora into localized segments, keeping individual combinatorial search spaces small and computationally feasible.
Bypassing Discrete Optimization
As document volumes continue to grow, some research directions favor moving away from explicit global optimization entirely:
- Neural Attention: Piji Li et al. proposed a neural "reader-recaller" architecture with cascaded attention mechanisms to distill information without the computational overhead of phrase-selection ILP solvers.
- Reinforcement Learning: Seonggi Ryang et al. recast text summarization as a sequential decision-making task, using reinforcement learning to optimize complex, non-decomposable scoring functions without exact global inference.
- Temporal Heuristics: In an evaluation of news timeline summarization, Demian Gholipour Ghalandari et al. demonstrated that simple, fast heuristics leveraging temporal expressions can often match or outperform heavy global optimization models on extensive news archives, questioning whether complex combinatorial search is always necessary.
Ultimately, the choice of method depends on a strict trade-off: while exact ILP solvers offer mathematical guarantees of optimality for small datasets, scaling to massive text collections requires either the structured approximations of submodular greedy algorithms, algorithmic relaxations like graph cuts, or heuristic pre-filtering.
Key Foundational Work
Automatic Summarization as a Combinatorial Optimization Problem (2009) — contributed 1 concept elements to this direction.
An Inference Model for Semantic Entailment in Natural Language (2005) — contributed 1 concept elements to this direction.