Constrained Optimization for Information Selection

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 2183 papers244 conceptsfrozen 2026-10-04

In many natural language processing tasks, we are faced with a fundamental tension: we have a wealth of potentially useful information, but a strictly limited "budget" in which to present it. This budget might be a 100-word limit for a news summary, a 20-character limit for a mobile product title, or the fixed context window of a Large Language Model (LLM).

The traditional approach to this problem is "greedy selection"—simply picking the most relevant items one by one until the budget is exhausted. However, a growing body of research suggests that framing content selection as a constrained optimization problem—specifically using Integer Linear Programming (ILP) or the Knapsack algorithm—yields significantly better results by finding a global rather than local optimum.

The Greedy Trap and the Knapsack Solution

To understand why simple ranking fails, imagine you are packing a bag with a 10kg limit. You have a 9kg item that is very valuable, and three 3kg items that are each slightly less valuable than the big one, but collectively worth much more. A greedy algorithm takes the 9kg item first and stops. An optimization approach looks at the entire "search space" and realizes the three smaller items are the better choice.

In the context of E-commerce, Yu Gong and colleagues applied this logic to Chinese Short Product Titles. Rather than just truncating long titles, they modeled word selection as a 0/1 knapsack problem. By using dynamic programming to maximize the cumulative importance of tokens within a character limit, they ensured that the most "semantically dense" information reached the user's mobile screen.

Global Optimization via Integer Linear Programming

While the knapsack problem handles simple weight-versus-value trade-offs, more complex tasks require balancing multiple competing objectives like relevance, redundancy, and coherence. This is where Integer Linear Programming (ILP) becomes the tool of choice.

The ICSI Summarization System, developed by Daniel Gillick and Benoît Favre, pioneered this by treating multi-document summarization as a global optimization of "concept coverage." Instead of selecting sentences based on their individual scores, the system selects a set of sentences that maximizes the coverage of unique word bigrams.

The power of ILP lies in its constraints. For example, Mattia Tomasoni used ILP to summarize community Q&A threads by enforcing constraints that balance relevance with novelty. Similarly, Daraksha Parveen and Michael Strube 0001 integrated coherence into the optimization, ensuring that the selected sentences weren't just important, but also flowed logically.

Optimizing the LLM Context Window

The rise of In-Context Learning (ICL) has moved the "budget" from the output (the summary) to the input (the prompt). LLMs are sensitive to the choice and order of few-shot examples, and their context windows are a precious resource.

Jonathan Tonglet and the team behind SEER demonstrated that selecting exemplars is fundamentally a knapsack problem. By treating the prompt as a limited resource, SEER balances semantic similarity with token constraints. This prevents a common failure mode where a single, very long (but highly similar) example "crowds out" other diverse examples that might have provided better guidance to the model.

This philosophy extends to code models as well. Hongyu Zhang introduced DietCode, which prunes unimportant code statements before they reach the model. By assigning each statement a "value" based on attention weights and a "cost" based on token count, DietCode uses 0-1 knapsack optimization to preserve the most semantically dense components of a program, reducing computational overhead by 40% with minimal accuracy loss.

Beyond Text: Video and Structured Data

The principle of constrained optimization is modality-agnostic. In video summarization, researchers like Zhong Ji use the knapsack algorithm to select the highest-scoring video shots that fit within a target duration. In the realm of Knowledge Graphs, Gong Cheng formulated entity summarization as a 0-1 Quadratic Knapsack Problem, which allows the system to penalize redundancy (negative interactions between similar facts) while maximizing the quality of individual triples.

Why It Works: The Shift to Global Reasoning

The recurring success of these methods across 15 years of research—from TAC 2008 to EMNLP 2023—stems from a single insight: Information density is more important than individual item scores.

By framing selection as a mathematical optimization, researchers move away from "local" decisions that are easily swayed by outliers (like a very long, slightly relevant sentence) and toward "global" decisions that maximize the total utility of the available space. As Daniel Gillick noted, while these combinatorial problems are theoretically difficult (NP-hard), modern solvers can find the optimal set of information for most NLP tasks in less than a second, making global optimization a practical and superior alternative to heuristic-based selection.

Papers in this version

Showing 60 of 183 papers.

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 1, frozen text):

@misc{lacuna_constrained_optimization_for_information_1f3ec45c_v1,
  title = {Constrained Optimization for Information Selection},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/constrained-optimization-for-information-selection/rdr_1f3ec45c1998472fb3bfd9cb08beeecb/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}