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

Problem Statement

Large Language Models (LLMs) struggle to solve complex combinatorial problems through direct autoregressive reasoning due to the "reasoning bottleneck" inherent in navigating large search spaces and maintaining global consistency over long-horizon constraints. While recent neuro-symbolic approaches attempt to mitigate this by having LLMs synthesize executable solvers, two critical design questions remain unresolved:

1. Representation: How should the LLM represent the solver? Is a native algorithmic approach (Python) superior to declarative modeling (MiniZinc) or solver-API integration (Python + OR-Tools)?
2. Optimization: Should the LLM be prompted to actively optimize the search process (e.g., via heuristics, pruning, or bounds), or should it strictly formalize the problem for a verified backend?

Prior work often evaluates these settings in isolation or at a problem-level aggregate, failing to decompose instance-level outcomes into correctness, schema validity, and fidelity. Furthermore, the impact of efficiency-oriented prompting on the reliability of generated solvers has not been systematically audited.

Methodology

The authors introduce CP-SynC-XL, a benchmark extending the CP-SynC dataset to include 100 heterogeneous Constraint Satisfaction Problems (CSPs) and Constraint Optimization Problems (COPs), totaling 4,577 parameterized instances. The study evaluates three frontier LLMs (GPT-5.3-CODEX, GEMINI 3.1 PRO, DEEPSEEK-V3.2) across three solver-construction paradigms:

1. Native Algorithmic Search (Python): The LLM generates a standalone Python algorithm using only the standard library, designing the full search procedure (e.g., branch-and-bound, DP).
2. Constraint Modeling via Python API (Python + OR-Tools): The LLM encodes variables, constraints, and objectives using the OR-Tools CP-SAT Python API, delegating the search to the solver.
3. Declarative Constraint Modeling (MiniZinc + OR-Tools): The LLM generates a MiniZinc model, which is then compiled and solved by the same OR-Tools CP-SAT backend.

The study employs a controlled factorial design comparing a baseline prompt (asking only for correctness) against a heuristic prompt (explicitly requesting efficiency-oriented design, such as tighter bounds, pruning, or search annotations).

The evaluation pipeline includes:

• Refinement Protocol: A four-round iterative refinement loop where failed runs (crashes, timeouts, format errors) are fed back to the LLM.
• Metrics:
  • Provided: Fraction of instances returning a schema-conformant output.
  • Correct: Fraction of provided outputs passing the reference verifier.
  • Fidelity: The ratio of Correct/Provided (the share of returned solutions that are actually valid).
• Code-Level Audit: A paired analysis of baseline vs. heuristic solvers to identify specific failure modes and code patterns.

Key Contributions

1. The CP-SynC-XL Benchmark

The authors introduce a large-scale benchmark (4,577 instances) designed to evaluate LLM-synthesized solvers at the instance level, separating provided outputs from verified correctness to measure conditional fidelity.

2. Representational Divergence

The study reveals a significant divergence in solver performance based on the modeling surface, even when the underlying solver backend (OR-Tools CP-SAT) is identical:

• Python + OR-Tools achieves the highest absolute correctness across all LLMs.
• MiniZinc + OR-Tools exhibits lower absolute coverage (more "no solution" timeouts) despite having the same backend, suggesting a bottleneck in the LLM's fluency with the declarative surface rather than the solver's capability.
• Native Python has the highest rate of "silent failures"—returning schema-valid solutions that fail verification—indicating that LLMs struggle to design complete, sound search algorithms from scratch.

3. The Heuristic Trap

The paper identifies a "heuristic trap" where prompting LLMs to optimize search yields unreliable results:

• Marginal Gains, High Risk: Heuristic prompts produce only small median speed-ups (1.03–1.12×) but induce a strongly bimodal effect. While some instances speed up, many others slow down, and correctness drops sharply on a long tail of problems.
• Six Failure Modes: A code-level audit identifies six paradigm-specific failure modes triggered by heuristic prompts:
  • Unverified Bounds (Python + OR-Tools): LLMs inject "tight" bounds that are not theorems, causing infeasibility.
  • Weakened Propagation (Python + OR-Tools): Semantically equivalent rewrites (e.g., Big-M) that cripple the solver's propagation engine.
  • Hard Seeding (Python + OR-Tools): Converting heuristic candidates into hard constraints, removing feasible regions.
  • Loss of Completeness (Python): Replacing complete search with incomplete local search or iteration caps.
  • COP→SAT Collapse (MiniZinc): Incorrectly assuming an optimum value and converting optimization to satisfaction.
  • Redundant Machinery (MiniZinc): Adding excessive auxiliary constraints that overwhelm the solver's flattening process.

Results

• Correctness Ranking: Python + OR-Tools > Python ≳ MiniZinc + OR-Tools. Delegating search to a verified backend (CP-SAT) significantly outperforms native algorithmic design.
• Fidelity Ranking: MiniZinc + OR-Tools > Python + OR-Tools > Python. When a solution is provided, MiniZinc models are most likely to be correct (highest conditional fidelity) because the language's type system and well-formedness checks filter out many encoding errors before the solver runs. Native Python is the least faithful, often returning confident but incorrect solutions.
• Heuristic Impact: On stronger LLMs (GPT-5.3-CODEX, GEMINI 3.1 PRO), heuristic prompts yield marginal, inconsistent gains (±3.6 percentage points). On weaker LLMs (DEEPSEEK-V3.2), heuristic prompts cause significant degradation (e.g., -7.4 pp correctness on Python + OR-Tools).
• Failure Analysis: The dominant baseline failure mode is UNSAT (the solver returns a solution that the reference verifier rejects), primarily caused by natural-language-to-formal-language mistranslations (e.g., dropping constraints, misinterpreting output schemas). Heuristic prompts exacerbate this by introducing unverified bounds and over-constraining the model.

Significance and Design Principles

The paper argues that the primary bottleneck for LLM-generated combinatorial solvers is modeling surface fluency, not the underlying solver's capability. The findings support a conservative design principle:

"Formalize, Don't Optimize."

LLMs should be used primarily to formalize variables, constraints, and objectives for verified solvers. Attempts to have LLMs generate search optimizations (heuristics, bounds, pruning strategies) should be treated with skepticism. The paper concludes that any LLM-authored search optimization must be independently validated before use, as the "heuristic trap" frequently introduces unverified bounds or algorithmic substitutions that reduce both correctness and fidelity. The most reliable strategy is to keep the LLM close to the formalization interface and rely on the solver's native machinery for search.