Formalize, Don't Optimize: The Heuristic Trap in LLM-Generated Combinatorial Solvers

Problem
This preprint addresses the limitations of Large Language Models (LLMs) in solving complex combinatorial problems through direct reasoning. It highlights the challenges in synthesizing executable solvers using LLMs and questions the efficacy of different representation paradigms for solver construction. The authors identify a gap in understanding how LLMs should represent solvers and whether they should optimize search processes, which has implications for the design of neuro-symbolic systems.

Method
The authors introduce CP-SynC-XL, a benchmark comprising 100 combinatorial problems with 4,577 instances, to evaluate three paradigms for solver construction: (1) native algorithmic search using Python, (2) constraint modeling via a Python solver API (Python + OR-Tools), and (3) declarative constraint modeling using MiniZinc with OR-Tools. The evaluation focuses on correctness and coverage of solutions generated by LLMs across these paradigms. The study employs a paired code-level audit to trace performance regressions to specific heuristic traps encountered during optimization attempts. The authors advocate for a design principle where LLMs are primarily used to formalize problem components, while the verification of search optimization is conducted separately.

Results
The findings reveal that the Python + OR-Tools paradigm achieves the highest correctness across LLMs, while MiniZinc + OR-Tools, despite utilizing the same backend, exhibits lower absolute coverage. Native Python solutions are more likely to yield schema-valid outputs that fail verification. On the heuristic optimization front, prompting for search optimization results in only marginal speed-ups (1.03-1.12x), with a bimodal distribution of effects: many instances experience slowdowns, and correctness significantly declines for a subset of problems. The authors attribute these regressions to the heuristic trap, where LLMs replace complete search strategies with local approximations or introduce unverified bounds, leading to suboptimal performance.

Limitations
The authors acknowledge that their findings are limited to the specific combinatorial problems included in the CP-SynC-XL benchmark and may not generalize to all combinatorial domains. They also note that the reliance on LLMs for search optimization can lead to significant correctness drops, particularly in complex problem instances. Additionally, the study does not explore the potential of hybrid approaches that might combine the strengths of different paradigms more effectively.

Why it matters
This work has significant implications for the design of LLM-generated combinatorial solvers, suggesting a shift towards using LLMs for formalization rather than optimization. By highlighting the heuristic trap, the authors provide a cautionary framework for future research in neuro-symbolic systems, emphasizing the need for rigorous verification of LLM-generated optimizations. This could lead to more reliable and efficient combinatorial solvers, ultimately enhancing the applicability of LLMs in complex problem-solving scenarios.

Authors: Haoyu Wang, Yuliang Song, Tao Li, Zhiwei Deng, Yaqing Wang, Deepak Ramachandran, Eldan Cohen, Dan Roth
Source: arXiv:2605.12421
URL: https://arxiv.org/abs/2605.12421v1