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

• URL: http://arxiv.org/abs/2605.12421v1
• Date: Tue, 12 May 2026 17:15:45 GMT
• Title: Formalize, Don't Optimize: The Heuristic Trap in LLM-Generated Combinatorial Solvers
• Abstract summary: Large Language Models (LLMs) struggle to solve complex problems through direct reasoning, so recent neuro-symbolic systems increasingly use them to synthesize executable solvers.<n>We introduce CP-SynC-XL, a benchmark of 100 problems (4,577 instances), and evaluate three solver--construction paradigms: native algorithmic search (Python), constraint modeling through a Python solver API (Python + OR-Tools), and declarative constraint modeling.
• Score: 52.23061619664667
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Large Language Models (LLMs) struggle to solve complex combinatorial problems through direct reasoning, so recent neuro-symbolic systems increasingly use them to synthesize executable solvers. A central design question is how the LLM should represent the solver, and whether it should also attempt to optimize search. We introduce CP-SynC-XL, a benchmark of 100 combinatorial problems (4,577 instances), and evaluate three solver-construction paradigms: native algorithmic search (Python), constraint modeling through a Python solver API (Python + OR-Tools), and declarative constraint modeling (MiniZinc + OR-Tools). We find a consistent representational divergence: Python + OR-Tools attains the highest correctness across LLMs, while MiniZinc + OR-Tools has lower absolute coverage despite using the same OR-Tools back-end. Native Python is the most likely to return a schema-valid solution that fails verification, whereas solver-backed paths preserve higher conditional fidelity. On the heuristic axis, prompting for search optimization yields only small median speed-ups (1.03-1.12x) and a strongly bimodal effect: many instances slow down, and correctness drops sharply on a long tail of problems. A paired code-level audit traces these regressions to a recurring heuristic trap. Under an efficiency-oriented prompt, the LLM may replace complete search with local approximations (Python), inject unverified bounds (Python + OR-Tools), or add redundant declarative machinery that overwhelms or over-constrains the model (MiniZinc + OR-Tools). These findings support a conservative design principle for LLM-generated combinatorial solvers: use the LLM primarily to formalize variables, constraints, and objectives for verified solvers, and separately check any LLM-authored search optimization before use.

Related papers

• LLMs Can Design Near-Optimal OR Algorithms [2.0813318162800702]
  Large language models (LLMs) can design effective algorithms for well-specified operations research (OR) problems.<n>We study inventory control, queueing network control, and assortment optimization.
  arXiv  Detail & Related papers  (2026-08-27T16:01:11Z)
• A Hybrid Nested Harness for Decoupling Structure and Parameters in LLM-Driven Optimization [6.599344783327054]
  In evolutionary algorithms powered by language models, the LLM acts as a single operator that simultaneously updates structural components and continuous parameters.<n>We formalize a hybrid nested search, in which an outer loop has the LLM propose a structural sketch, with numeric gaps, and an innernest tunes the sketch.<n>We validate our framework across three scientific domains: (i) meta-optimizers on closed-form test functions, (ii) code-based policies for systems research and social dilemmas, and (iii) approximate Bayesian inference tasks.
  arXiv  Detail & Related papers  (2026-08-08T14:35:22Z)
• Execution-Verified Reinforcement Learning for Optimization Modeling [49.171122807323634]
  Execution-verified learning framework treats a mathematical programming solver as a deterministic, interactive verifier.<n>Experiments on NL4OPT, MAMO, IndustryOR, and OptiBench across Gurobi, OR-Tools, and COPT show that EVOM matches or outperforms process-supervised SFT.
  arXiv  Detail & Related papers  (2026-04-01T03:39:11Z)
• Online Prompt Selection for Program Synthesis [14.188804919928591]
  Large Language Models (LLMs) demonstrate impressive capabilities in the domain of program synthesis.<n>A key challenge for the user is to identify when an LLM is the right choice of solver, and the appropriate LLM to call for a given synthesis task, but also the right way to call it.<n>We use a multi-armed bandit algorithm to select which symbolic solver, or LLM and prompt combination to deploy in order to maximize a given reward function.
  arXiv  Detail & Related papers  (2025-01-09T13:57:09Z)
• Small Language Models Fine-tuned to Coordinate Larger Language Models improve Complex Reasoning [41.03267013352519]
  Large Language Models (LLMs) prompted to generate chain-of-thought exhibit impressive reasoning capabilities. We introduce DaSLaM, which uses a decomposition generator to decompose complex problems into subproblems that require fewer reasoning steps. We show that DaSLaM is not limited by the solver's capabilities as a function of scale.
  arXiv  Detail & Related papers  (2023-10-21T15:23:20Z)
• ALGO: Synthesizing Algorithmic Programs with LLM-Generated Oracle Verifiers [60.6418431624873]
  Large language models (LLMs) excel at implementing code from functionality descriptions but struggle with algorithmic problems. We propose ALGO, a framework that synthesizes Algorithmic programs with LLM-Generated Oracles to guide the generation and verify their correctness. Experiments show that when equipped with ALGO, we achieve an 8x better one-submission pass rate over the Codex model and a 2.6x better one-submission pass rate over CodeT.
  arXiv  Detail & Related papers  (2023-05-24T00:10:15Z)
• SatLM: Satisfiability-Aided Language Models Using Declarative Prompting [68.40726892904286]
  We propose a new satisfiability-aided language modeling (SatLM) approach for improving the reasoning capabilities of large language models (LLMs) We use an LLM to generate a declarative task specification rather than an imperative program and leverage an off-the-shelf automated theorem prover to derive the final answer. We evaluate SATLM on 8 different datasets and show that it consistently outperforms program-aided LMs in the imperative paradigm.
  arXiv  Detail & Related papers  (2023-05-16T17:55:51Z)
• Large Language Models are Strong Zero-Shot Retriever [89.16756291653371]
  We propose a simple method that applies a large language model (LLM) to large-scale retrieval in zero-shot scenarios. Our method, the Language language model as Retriever (LameR), is built upon no other neural models but an LLM.
  arXiv  Detail & Related papers  (2023-04-27T14:45:55Z)
• PAL: Program-aided Language Models [112.94785609781503]
  We present Program-Aided Language models (PaL) to understand natural language problems. PaL offloads the solution step to a programmatic runtime such as a Python interpreter. We set new state-of-the-art results in all 12 benchmarks.
  arXiv  Detail & Related papers  (2022-11-18T18:56:13Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.