Lazy Greedy Optimization for Submodular Maximization

31 concepts30 papers

When faced with a massive pool of data, items, or choices, we frequently need to select a high-quality subset under a strict budget constraint. We might want to choose the most informative subset of data to train a machine learning model, select a diverse set of visual tokens to speed up a multimodal large language model, or find the most influential nodes in a social network.

Mathematically, many of these problems can be framed as maximizing a set function $f(S)$ subject to a size constraint $|S| \le k$. If the objective function $f$ satisfies submodularity—a formal mathematical property capturing the law of diminishing returns—a simple greedy algorithm provides a strong theoretical guarantee: it is guaranteed to achieve at least $(1 - 1/e) \approx 63\%$ of the optimal solution's value.

However, the standard greedy algorithm has a massive computational bottleneck. At every step, it must evaluate the marginal gain of every single remaining element to find the absolute best one. If we are selecting $k$ elements from a pool of $n$, this requires $O(n \cdot k)$ evaluations of $f$. When evaluating $f$ is expensive or when $n$ scales to millions, this standard approach becomes completely intractable.

Lazy greedy optimization resolves this bottleneck. By exploiting submodularity, it avoids thousands of redundant calculations, often reducing the number of function evaluations from a linear scan per step to an amortized nearly-constant cost.

The Core Intuition: Upper Bounds That Only Decrease

To understand why lazy optimization works, we must look closely at the definition of submodularity. A function $f$ is submodular if for any two sets $A \subseteq B$ and an element $e \notin B$:

$$f(A \cup \{e\}) - f(A) \ge f(B \cup \{e\}) - f(B)$$

In plain terms, the marginal gain of adding an element $e$ to a smaller set $A$ is always greater than or equal to the marginal gain of adding that same element to a larger set $B$. As our chosen set grows, the value of adding any remaining element can only decrease or stay the same; it can never increase.

The lazy greedy algorithm, popularized in early foundational work by Andreas Krause et al. in Near-optimal Observation Selection using Submodular Functions, exploits this property by maintaining a priority queue (a max-heap) of all remaining elements. The elements are sorted by their last known marginal gains. Crucially, because marginal gains only decrease over time, these stored values serve as valid upper bounds for the true current marginal gains.

The algorithm proceeds as follows:

  1. Pop the Top Element: Pull the element $e$ with the highest upper bound from the priority queue.
  2. Re-evaluate: Calculate its true marginal gain given the current state of the selected set $S$.
  3. Check or Re-insert:
  4. If its updated marginal gain is still greater than or equal to the upper bound of the next element in the queue, stop. Because all other elements' true gains are bounded by their stored values, $e$ is guaranteed to be the absolute best choice for this step. Add $e$ to $S$.
  5. If its updated gain drops below the next element's upper bound, re-insert $e$ into the queue with its new, lower value and repeat the process.
Initial Queue (Upper Bounds):
[ Element A: 10 ] -> [ Element B: 9 ] -> [ Element C: 5 ]

Step 1: Pop Element A and evaluate true gain given current set S.
Suppose true gain drops to 8.5.

Updated Queue:
[ Element B: 9 ] -> [ Element A: 8.5 ] -> [ Element C: 5 ]

Step 2: Pop Element B and evaluate true gain given current set S.
Suppose true gain drops to 8.8.

Since 8.8 is >= the next upper bound (Element A: 8.5), 
Element B is guaranteed to be the optimal choice! Select B.

By leveraging this mechanism, the algorithm skips evaluating the vast majority of elements at each iteration. If an element's upper bound is already lower than the true gain of our current candidate, we never have to look at it. As shown by Khalid El-Arini et al. in Turning down the noise in the blogosphere, this strategy yields the exact same mathematical results as the standard greedy algorithm while executing in a fraction of the time.

Scaling Up Modern Machine Learning

The massive speedups provided by lazy greedy evaluation have made it an essential tool for modern, large-scale machine learning applications where exhaustive search is impossible.

Data Subset Selection and Active Learning

In active learning and core-set selection, the goal is to find a small, highly representative subset of data to train a model without sacrificing accuracy. Kai Wei et al. demonstrated in Submodularity in Data Subset Selection and Active Learning that data likelihoods for common classifiers naturally exhibit submodularity, allowing lazy greedy selection to efficiently find optimal training samples.

More recently, as instruction tuning datasets for large language models have grown to the scale of millions, Alexander Bukharin et al. leveraged lazy greedy optimization in Data Diversity Matters for Robust Instruction Tuning to maximize data diversity on standard hardware, proving that maximizing submodular diversity significantly improves model robustness on difficult, worst-case prompts.

Token Pruning in Multimodal LLMs

When processing long videos or high-resolution images, Multimodal Large Language Models (MLLMs) suffer from an explosion of visual tokens. To combat this, researchers use submodular optimization to prune redundant tokens.

In Beyond Attention or Similarity: Maximizing Conditional Diversity for Token Pruning in MLLMs, Qizhe Zhang et al. utilized fast greedy algorithms to select optimal token subsets in real-time, ensuring that the computational savings of pruning are not negated by the cost of the selection logic itself. Similarly, Janghoon Cho et al. introduced the FLoC framework in FLoC: Facility Location-Based Efficient Visual Token Compression for Long Video Understanding, using a priority-queue-driven lazy greedy algorithm to compress visual data for long video understanding without requiring additional training.

Handling Complex Constraints and Non-Monotonicity

While the vanilla lazy greedy algorithm assumes a simple cardinality constraint ($|S| \le k$) and a monotone function (where adding items always increases or maintains value), real-world problems are often more complex. Researchers have successfully extended the lazy framework to handle these edge cases.

Knapsack Constraints

In many scenarios, items have different costs, and we operate under a total cost budget rather than a count budget. Alina Ene et al. addressed this in A Nearly-linear Time Algorithm for Submodular Maximization with a Knapsack Constraint, designing an algorithm that defers utility calculations via priority queues to achieve nearly-linear running times under arbitrary cost constraints.

Non-Monotone Functions

When adding items can eventually decrease the total value (such as balancing task coverage against expert burnout, as explored by Aristides Gionis et al. in Forming coordinated teams that balance task coverage and expert workload), the function is non-monotone. To handle this, Federico Fusco et al. developed SampleGreedy in Fast Adaptive Non-Monotone Submodular Maximization Subject to a Knapsack Constraint. Their approach combines randomized sampling with lazy evaluation to maintain strong approximation guarantees while running at least a factor of $n$ faster than previous state-of-the-art methods.

Determinantal Point Processes (DPPs)

DPPs are widely used to select diverse subsets, but their inference involves computationally heavy matrix operations. In Lazy and Fast Greedy MAP Inference for Determinantal Point Process, Kaito Fujii et al. combined submodular pruning with specialized Cholesky factorization updates, allowing the algorithm to skip redundant calculations for low-priority items while maintaining exact updates for top candidates.

Real-World Impact Across Domains

The versatility of lazy greedy optimization extends far beyond traditional machine learning pipelines into operations research, graph theory, and security:

By turning the mathematical property of diminishing returns into a computational shortcut, lazy greedy optimization bridges the gap between combinatorial theory and practical engineering, enabling near-optimal selection at a scale that would otherwise be impossible.

Key Foundational Work

Near-optimal Observation Selection using Submodular Functions (2007) — contributed 1 concept elements to this direction.
Better k-best Parsing (2005) — contributed 1 concept elements to this direction.
History & citationVersion 1 · 2026-10-04

Current · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_lazy_greedy_optimization_203656c4,
  title = {lazy greedy optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/lazy-greedy-optimization/rdr_203656c452ce4a9a8dfc1266d8ee9a45},
  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_lazy_greedy_optimization_203656c4_v1,
  title = {lazy greedy optimization},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/lazy-greedy-optimization/rdr_203656c452ce4a9a8dfc1266d8ee9a45/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}

See something wrong? Report a mistake