mlsanityData to 14 Oct 2026

Unrealized Expectations: Comparing AI Methods vs Classical Algorithms for Maximum Independent Set

arXiv 2502.03669 ↗First posted 5 Feb 2025cs.LG cs.AI cs.DMcited by 2

On the map: Deep reinforcement learning methods → RL for games and combinatorial optimization

Abstract (arXiv)

AI methods, such as generative models and reinforcement learning, have recently been applied to combinatorial optimization (CO) problems, especially NP-hard ones. This paper compares such GPU-based methods with classical CPU-based methods on the Maximum Independent Set (MIS) problem. Strikingly, even on in-distribution random graphs, leading AI-inspired methods are consistently outperformed by the state-of-the-art classical solver KaMIS running on a single CPU, and some AI-inspired methods frequently fail to surpass even the simplest degree-based greedy heuristic. Even with post-processing techniques like local search, AI-inspired methods still perform worse than CPU-based solvers. To better understand the source of these failures, we introduce a novel analysis, serialization, which reveals that non-backtracking AI-inspired methods, e.g. LTFT (which is based on GFlowNets), end up reasoning similarly to the simplest degree-based greedy, and thus worse than KaMIS. More generally, our findings suggest a need for a rethinking of current approaches in AI for CO, advocating for more rigorous benchmarking and the principled integration of classical heuristics. Additionally, we also find that CPU-based algorithm KaMIS have strong performance on sparse random graphs, which appears to show that the shattering threshold conjecture for large independent sets proposed by Coja-Oghlan & Efthymiou (2015) does not apply for real-life sizes (such as 10^6 nodes).

Key facts. Cited by 2 papers in the map (data through 14 Oct 2026). Placed in RL for games and combinatorial optimization, one of 15 directions in Deep reinforcement learning methods. Builds on 44 of its 88 references that are in the map. First posted on arXiv 5 Feb 2025.

Builds on

44 of 88 references.

References · 44

  1. 2018DAGs with NO TEARS: Continuous Optimization for Structure Learningcited by 752
  2. 2020TUDataset: A collection of benchmark datasets for learning with graphscited by 728
  3. 2018Attention, Learn to Solve Routing Problems!cited by 656
  4. 2018Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizoncited by 623
  5. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 561
  6. 2021Flow Network based Generative Models for Non-Iterative Diverse Candidate Generationcited by 392
  7. 2021GFlowNet Foundationscited by 290
  8. 2021Combinatorial optimization and reasoning with graph neural networkscited by 268
  9. 2023DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimizationcited by 221
  10. 2018Learning to Perform Local Rewriting for Combinatorial Optimizationcited by 185
  11. 2018Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Searchcited by 183
  12. 2019Causal Discovery with Reinforcement Learningcited by 145
32 more
  1. 2020Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learningcited by 140
  2. 2022DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problemscited by 129
  3. 2020Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphscited by 115
  4. 2021Combinatorial Optimization with Physics-Inspired Graph Neural Networkscited by 108
  5. 2020Learning 2-opt Heuristics for the Traveling Salesman Problem via Deep Reinforcement Learningcited by 100
  6. 2020Learning the Travelling Salesperson Problem Requires Rethinking Generalizationcited by 98
  7. 2023DeepACO: Neural-enhanced Ant Systems for Combinatorial Optimizationcited by 78
  8. 2022Diffusion Models for Causal Discovery via Topological Orderingcited by 66
  9. 2020Reinforcement Learning with Combinatorial Actions: An Application to Vehicle Routingcited by 61
  10. 2024A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimizationcited by 59
  11. 2020Learning What to Defer for Maximum Independent Setscited by 54
  12. 2022What's Wrong with Deep Learning in Tree Search for Combinatorial Optimizationcited by 37
  13. 2015Finding Near-Optimal Independent Sets at Scalecited by 33
  14. 2022Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent setcited by 33
  15. 2020Combining Reinforcement Learning with Lin-Kernighan-Helsgaun Algorithm for the Traveling Salesman Problemcited by 31
  16. 2024Position: Rethinking Post-Hoc Search-Based Neural Approaches for Solving Large-Scale Traveling Salesman Problemscited by 24
  17. 2013Limits of local algorithms over sparse random graphscited by 23
  18. 2023Variational Annealing on Graphs for Combinatorial Optimizationcited by 21
  19. 2019G2SAT: Learning to Generate SAT Formulascited by 20
  20. 2022Annealed Training for Combinatorial Optimization on Graphscited by 18
  21. 2022NSNet: A General Neural Probabilistic Framework for Satisfiability Problemscited by 18
  22. 2023Controlling Continuous Relaxation for Combinatorial Optimizationcited by 16
  23. 2021Deep Reinforcement Learning for Combinatorial Optimization: Covering Salesman Problemscited by 13
  24. 2023HardSATGEN: Understanding the Difficulty of Hard SAT Formula Generation and A Strong Structure-Hardness-Aware Baselinecited by 12
  25. 2014Local algorithms for independent sets are half-optimalcited by 9
  26. 2014Branch-and-Reduce Exponential/FPT Algorithms in Practice: A Case Study of Vertex Covercited by 8
  27. 2017Scalable Kernelization for Maximum Independent Setscited by 8
  28. 2016Accelerating Local Search for the Maximum Independent Set Problemcited by 5
  29. 2022Neural Improvement Heuristics for Graph Combinatorial Optimization Problemscited by 4
  30. 2024Differentiable Quadratic Optimization For The Maximum Independent Set Problemcited by 4
  31. 2022A Differentiable Approach to Combinatorial Optimization using Dataless Neural Networkscited by 3
  32. 2015Graph Partitioning for Independent Setscited by 2

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2025: 1; 2026: 1.

2 papers.

  1. 2025LLM-Guided Search for Deletion-Correcting Codescited by 4
  2. 2026On the Slow Convergence to Trivial Solutions of Algorithms for Hard Optimization Problemscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Three methods, one problem: Classical and AI approaches to no-three-in-line
  2. 2025FrontierCO: Real-World and Large-Scale Evaluation of Machine Learning Solvers for Combinatorial Optimization
  3. 2025CO-Bench: Benchmarking Language Model Agents in Algorithm Search for Combinatorial Optimization
  4. 2025ACCORD: Autoregressive Constraint-satisfying Generation for COmbinatorial Optimization with Routing and Dynamic attention
  5. 2024Combinatorial Reasoning: Selecting Reasons in Generative AI Pipelines via Combinatorial Optimization
  6. 2024Transform then Explore: a Simple and Effective Technique for Exploratory Combinatorial Optimization with Reinforcement Learning
  7. 2026Offline Decision Transformers for Neural Combinatorial Optimization: Surpassing Heuristics on the Traveling Salesman Problem
  8. 2026DRAGON: LLM-Driven Decomposition and Reconstruction Agents for Large-Scale Combinatorial Optimization