- Rating
- 2(+1)
- Confidence
- 4
- Informativeness
- 1
- Presentation
- 2
- Soundness
- 3
Read review
Paper summary
The paper studies data reduction as preprocessing for finding a maximum independent set (MIS) in a given graph. The idea is to use heuristic reduction rules which are not necessarily maintaining an optimal solution but are fast to apply and yield close to optimal solutions. The authors used an LLM to propose which heuristics to apply. They introduced two settings called "Reduce-then-solve" and "Reduce-as-solve". In the first one, the reduced instance is given to a solver to optimally solve the residual instance, whereas in the second one the reductions continue until the instance is solved. The authors run experiments on some benchmark dataset showing that their approach yields indeed close to optimal solutions in less time compared with applying exact data reductions (which guarantee optimal solutions).
The idea to use ML for data reduction is not new. I find it not surprising that you can heuristically find good solutions with LLMs. The writing consists of rather high-level descriptions (often unclear or imprecise) without any real technical details. So, the paper does not really provide new interesting insights into data reduction for independent set nor any theoretical explanations/guarantees. I also believe that it does not really fit the scope of ICLR.
Critical strengths
Heuristic data reduction based on LLMs can improve running times to solve hard MIS instances near optimally.
Critical weaknesses
I do not really see why data reduction for MIS belongs to ICLR (except for using LLMs).
There are no deeper insights gained from the experiments. It seems not surprising that you can gain some advantage on some datasets from using heuristics. I find this not convincing enough.
Questions for authors
Do the experiments give any information which could improve our understanding of data reduction for MIS?
What about other optimization problems?
5 comments
[Authors Response (2/3)]
Understanding of data reduction for MIS. The reviewer asks whether the experiments improve our understanding of data reduction for MIS. They do, and this is the core of our contribution. We invite the review to reconsider our methods with the following evidence. Our experiments first show where exact reduction stops working. We then evaluate three methods designed to keep reducing graphs beyond that point.
- Where exact reduction stops working. On the hard benchmark, all seven standard exact rules fire on 0% of instances, yet the stronger check still cost up to 138s per graph (Fig. 2, Tab. 6). Exact reduction can therefore remain correct while giving no practical benefit.
- GenReduce: reduce beyond exact rules. LLM-guided program search generates a reduction rule, which we select by its shrinkage, solution quality and runtime. For NP-hard problems, data reduction exists to make an instance small enough for an exact solver to handle. On our hard benchmark, the exact rules remove NOTHING, so the solver must work on the full graph, and Gurobi proves optimality on only 52% of instances within one hour. After GenReduce, Gurobi proves optimality on 78% of the reduced graphs. Although this optimality applies to the reduced graphs, we report it because it shows how much heuristic reduction can do where exact rules do nothing: it turns many instances that are too hard for the solver into smaller ones it can solve completely. To see what this reduction costs, we map the solution of the reduced graph back to the original graph and compare its size with the best solution Gurobi finds on the original instances within one hour. Because the rule is heuristic, it can make mistakes and miss the optimality. Yet, on the benchmark, the recovered solution keeps a median of 97.7% of the optimality. Together, the two results show that our heuristic reduction can make hard instances solvable while losing only a small part of the solution value.
- LocalizedReduce: Standard rollout uses trial solutions to build a single solution. LocalizedReduce instead uses the consensus among trial solutions, meaning the agreement on which vertices to include or discard, to decide which vertices to remove. Because we restrict trial starts to a minimum-degree vertex and its neighbors, total runtime falls by 98% compared with exhaustive rollout, at a cost of 1.3 percentage points in mean ratio (Tab.2).
- CacheReduce: CacheReduce stores trial solutions from earlier steps. At each step, an LLM-learned policy decides whether this stored evidence is enough to include or discard a vertex, or whether fresh trials are needed. Compared with LocalizedReduce, it reduces mean runtime by about 20% more, at a cost of 0.6 percentage points in mean ratio (Tab.1). Together, these results show that data reduction for MIS does not have to stop when exact rules stop firing. Heuristic evidence, gathered and reused at a controlled cost, can keep reducing hard instances.
Theory. The paper does not claim theoretical guarantees. Heuristic reduction gives up optimality guarantees by design, as we state in the abstract and introduction. Our contribution is empirical: we show where exact reduction stops working and how reduction can continue beyond that point. Where a structural argument is available, we use it. For example, LocalizedReduce restricts candidates to N[u] because every maximum independent set intersects N[u] (Section 3). A theoretical analysis of heuristic reduction is an interesting direction, but it is beyond the focus of this submission.
Technical details. The review describes the paper as high-level descriptions without technical details. The paper provides:
- pseudocode for both frameworks (Algorithms 1 and 2);
- the full prompts and the verbatim code of the selected rules (Appendix D);
- all seven exact rules with justifications (Appendix C);
- definitions of all metrics (Appendix B). We invite the reviewer to point to any specific part that remains unclear, and we will clarify it.
[Authors Response (3/3)]
Other optimization problems. The design of our methods can be reused for other problems, but the algorithms in this paper are specific to MIS. We chose MIS because it has one of the richest collections of expert-designed reduction rules, which makes it the most demanding setting for showing where exact reduction stops working. With the limited time and computing resource, we added a quick trial experiment. We kindly guide the reviewer to the comments for all.
We hope this effort, our explanation on the overall design, together with the reviewer's own assessment that our results are sound, can motivate the reviewer to kindly reconsider the score accordingly.
[1] Kool et al. Attention, Learn to Solve Routing Problems! ICLR 2019.
[2] Böther et al. What's Wrong with Deep Learning in Tree Search for Combinatorial Optimization. ICLR 2022.
[3] Acikalin et al. Learning to Explore and Exploit with GNNs for Unsupervised Combinatorial Optimization. ICLR 2025.
[4] Tang et al. GraphArena: Evaluating and Exploring Large Language Models on Graph Computation. ICLR 2025.
[5] Yang et al. Large Language Models as Optimizers. ICLR 2024.
[6] Großmann et al. Accelerating Reductions Using Graph Neural Networks and a New Concurrent Local Search for the Maximum Weight Independent Set Problem. arXiv 2024.
[Authors Response (1/3)]
We thank the reviewer for the review. The review raises four concerns: novelty, significance, theory and scope. None of them is supported by a concrete argument, and the judgment on novelty in particular comes with no stated basis. Meanwhile, the review rates soundness 3 and lists as a strength that our approach "can improve running times to solve hard MIS instances near optimally." This makes the reviewer's core argument difficult for us to identify. Nonetheless, we will use our best effort to assist the reviewer resolve the concerns.
Scope. LLM-guided program search for combinatorial optimization is clearly within the scope of ICLR. ICLR publishes learning methods for combinatorial optimization [1], including work on MIS and its kernelization [2,3] as well as work on LLMs for optimization and NP-complete graph problems [4-5]. Our work belongs squarely to this line, with a distinct use of the LLM: it generates the reduction rules and the cache policies that our methods deploy. ICLR's reviewer guidelines also explicitly value empirical contributions alongside theoretical ones. The review offers no reason why our work falls outside this line of research.
Novelty and "not surprising.". The claim that using LLM for data reduction is unsupported. Stated this broadly, it could be made against any submission. The related prior work that we cite uses learning to choose which exact reductions to run [6]. Our work targets a different direction: hard instances on which the exact rules no longer fire at all. Once these rules stop firing, further reduction requires giving up some exactness, and our methods do so in a controlled way. To the best of our knowledge, we are first to study this direction as an application work. The remaining argument, that heuristics can "gain some advantage on some datasets", applies to almost any empirical ML methods for NP-hard problem. To the best of our knowledge, no existing work claims universal generalization, whether it is based on ML or on LLM search. Therefore, it identifies no specific weakness in our usage. We evaluate on the standard hard MIS benchmark, DIMACS/BHOSLIB instances. The reduction rules are learned on small graphs and applied to this benchmark without any tuning. Finally, the review describes the LLM as a tool to "propose which heuristics to apply." This misses its second role. In GenReduce, the LLM generates the reduction rule. In CacheReduce, it also generates the cache policy that guides the reduce-as-solve process. The LLM does not find solutions: it generates both programs during training, and it is never called at test time to solve the instances directly (Section 3, Appendix A).