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:
- Pop the Top Element: Pull the element $e$ with the highest upper bound from the priority queue.
- Re-evaluate: Calculate its true marginal gain given the current state of the selected set $S$.
- Check or Re-insert:
- 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$.
- 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:
- Graph Analytics: Finding influential nodes or maximizing group centrality in massive networks is notoriously slow. Eugenio Angriman et al. demonstrated in Group Centrality Maximization for Large-scale Graphs that a lazy greedy approach can scale group centrality analysis to graphs with tens of millions of edges in under a minute. In fact, a comprehensive benchmark by Zhicheng Liang et al., A Benchmark Study of Deep-RL Methods for Maximum Coverage Problems over Graphs, revealed that these optimized "old school" greedy algorithms consistently outperform modern Deep Reinforcement Learning heuristics in both speed and solution quality for graph coverage problems.
- Black-Box Adversarial Attacks: Generating adversarial examples by querying a model requires finding high-impact pixel perturbations with minimal queries. Seungyong Moon et al. showed in Parsimonious Black-Box Adversarial Attacks via Efficient Combinatorial Optimization that reframing the attack as a submodular optimization and applying a lazy greedy heap strategy allows attackers to find high-impact adversarial changes with significantly fewer queries.
- Spatial Search and Computer Vision: In SubmodBoxes: Near-Optimal Search for a Set of Diverse Object Proposals, a single-author paper by Qing Sun, the author integrated lazy greedy selection directly into a branch-and-bound tree, interleaving bound updates with tree branching to efficiently discover diverse object proposals with strict theoretical guarantees.
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.