Formalize, Don’t Optimize: The Heuristic Trap in LLM-Generated Combinatorial Solvers Haoyu Wang1 Yuliang Song2 Tao Li3 Zhiwei Deng3 Yaqing Wang3 Deepak Ramachandran3 Eldan Cohen2 Dan Roth1,4
arXiv:2605.12421v1 [cs.AI] 12 May 2026
1
University of Pennsylvania 2 University of Toronto 3 Google DeepMind 4 Oracle AI {why16gzl, danroth}@seas.upenn.edu {yl.song, eldan.cohen}@utoronto.ca {tlinlp, zhiweideng, yaqingwang, ramachandrand}@google.com
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 + ORTools), 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.12×) 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.
1
Introduction
Large Language Models (LLMs) have demonstrated strong performance on mathematical reasoning [Mirzadeh et al., 2024, Jaech et al., 2024, Varambally et al., 2025] and general-purpose code synthesis [Liu et al., 2024a, Comanici et al., 2025], yet complex combinatorial optimization remains a difficult setting. While LLMs can navigate basic logical puzzles [Shojaee et al., 2025], their reasoning degrades on the large search spaces and implicit domain constraints characteristic of real-world combinatorial problems. As problem complexity scales, the autoregressive generation process becomes a “reasoning bottleneck” [Fan et al., 2024, Jiang et al., 2026]: without reliable internal state tracking for forward-checking and backtracking, models commit to early sub-optimal decisions and may lose global consistency across long-horizon constraints. To mitigate this limitation, recent work augments LLMs with external control structures such as A* search [Zhuang et al., 2023], Monte Carlo Tree Search (MCTS) [Liu et al., 2025], or agentic Preprint.
Figure 1: Solution provided (dotted) vs. verified correct (solid) by paradigm and prompt, one panel per LLM (log time axis). Python + OR-Tools attains the highest correctness at the 256 s tail on every LLM; the dotted–solid gap is largest on Python and smallest on MiniZinc + OR-Tools; the heuristic prompt fails to reliably dominate the baseline, previewing the heuristic trap.
working memory [Xu et al., 2025]. These interactive approaches explicitly maintain states and expose intermediate decisions to backtracking or search. However, using an LLM as an interactive search agent in NP-hard domains incurs high inference latency and token cost [Yang et al., 2024, Jiang et al., 2026]; moreover, external memory does not by itself remove heuristic blind spots that can steer the process toward local optima [Wang et al., 2025]. These limitations motivate shifting the computational burden away from direct textual reasoning. One promising strategy leverages LLM-driven program synthesis [Duchnowski et al., 2025, Michailidis et al., 2025]: the LLM writes an instance-agnostic executable artefact that formalizes the problem requirements, while the actual combinatorial search either runs inside that artefact or is delegated to a verified backend. Two open questions run through this synthesis setting: how should the LLM represent the solver, and whether the LLM should actively optimize search by generating heuristics. On representation, we find a representational divergence: LLMs are more successful with a Python solver API than with a declarative modeling language, even when both use the same OR-Tools back-end. On search optimization, we use heuristic trap to denote the recurring pattern in which an efficiencyoriented prompt induces unverified bounds, local approximations, or overcomplicated constraints that sometimes target speed but reduce correctness or fidelity. We study these questions by evaluating three frontier LLMs (GPT-5.3-C ODEX, G EMINI 3.1 P RO, D EEP S EEK -V3.2) on CP-SynC-XL, an extension of CP-SynC [Song and Cohen, 2026], with 100 combinatorial problems and 4,577 instances. We compare three solver-construction paradigms: native algorithmic search (Python), constraint modeling via a Python solver API (Python + OR-Tools), and declarative constraint modeling (MiniZinc + OR-Tools). The contrast we study is the representational surface, with a shared CP-SAT back-end for the two solver-backed paradigms. Figure 1 previews both findings: Python + OR-Tools attains the highest correctness on every LLM, while the heuristic prompt fails to reliably dominate the baseline and can regress sharply on the weakest LLM. These experiments provide an instance-level view of when LLM-generated combinatorial solvers benefit from symbolic delegation and when efficiency-oriented prompting introduces additional risk. Our main contributions are: 1. CP-SynC-XL benchmark: we introduce CP-SynC-XL, a benchmark containing 4,577 parameterized instances for 100 heterogeneous Constraint Satisfaction Problems and Constraint Optimization Problems for evaluating LLM-synthesised solvers. 2. Representational divergence: we show that solver correctness depends primarily on the LLM’s familiarity with the modeling surface rather than with the underlying solver—Python + OR-Tools attains the highest correctness on every LLM despite sharing CP-SAT with MiniZinc + OR-Tools, while native Python exhibits the highest rate of silent failures. 3. Heuristic trap: we show that prompting LLMs to optimize search is unreliable—a small median speed-up masks a sharply bimodal cost associated with six paradigm-specific failure 2
modes that iterative refinement often preserves rather than repairs; our findings support keeping the LLM close to formalization rather than asking it to supply search optimizations.
2
Related Work
LLMs as direct combinatorial solvers. Recent benchmarks show that prompting LLMs to solve NP-hard problems end-to-end deteriorates sharply with instance scale [Fan et al., 2024, Jiang et al., 2026], and that this compositional limit is structural rather than purely informational [Dziri et al., 2023]. Performance is also sensitive to problem representation [Duchnowski et al., 2025]: implicit constraints and natural-language framings are systematically harder than equivalent formal encodings. These findings motivate the shift from direct textual reasoning to symbolic delegation. LLM-as-translator. A second line replaces direct reasoning with translation into a formal language consumed by an external solver. Logic-LM [Pan et al., 2023] and SATLM [Ye et al., 2023] translate natural-language problems into FOL/SAT for off-the-shelf provers, and PAL [Gao et al., 2023] pioneered the broader Program-Aided LM template. In OR-style modeling, NL4Opt [Ramamonjison et al., 2023] and OptiMUS [AhmadiTeshnizi et al., 2024] target MILP, while Wang and Roth [2025] and Song and Cohen [2025] target CSP/CP through dedicated data structures and declarative MiniZinc and PyCSP3 models [Nethercote et al., 2007, Lecoutre and Szczepanski, 2020]. These studies establish that LLMs can often translate problem descriptions into solver-consumable artefacts, but they typically evaluate one surface at a time, one or a few instances per problem, or problem-level success rather than a paired instance-level outcome decomposition. As a result, it is difficult to tell whether a reported success rate comes from the underlying solver, the LLM’s fluency with a particular modeling surface, or the verifier’s tolerance for semantically incorrect solutions. We instead compare three representational surfaces for the same problem set and LLMs, use OR-Tools CP-SAT as the common back-end for the two solver-backed conditions, and separate provided, correct, and conditional fidelity at the instance level. LLMs as algorithmic / heuristic designers. A more recent line uses LLMs to synthesize the algorithm itself. FunSearch [Romera-Paredes et al., 2024] evolves heuristic programs against a fitness function, Eureka [Ma et al., 2023] discovers reward functions, and Evolution-of-Heuristics [Liu et al., 2024b] couples LLM proposal with evolutionary selection; in interactive settings, Wang et al. [2025] treat the LLM as a polynomial-time heuristic queried inside MCTS. The reported successes typically rely on a problem-specific scoring oracle, a population-and-selection loop with many LLM samples, and the freedom to specialize each heuristic to a single problem family. We adopt the synthesis framing but study a regime closer to many deployment settings: single-shot generation with a bounded refinement loop, a uniform rubric across 100 problems, and no test-time evolution.
3
Method
To investigate the two questions raised in Sec. 1—how should the LLM represent the solver, and whether it should attempt to optimize search—we use a controlled factorial design with two axes: the solver-generation paradigm and the prompt. For each natural-language combinatorial problem, the LLM produces a reusable artefact that consumes instance parameters at runtime and returns a solution in the benchmark’s required format. The paradigm fixes the representational surface, spanning native algorithmic search (Python), constraint modeling through the OR-Tools CP-SAT Python API (Python + OR-Tools), and declarative modeling in MiniZinc (MiniZinc + OR-Tools). The prompt toggles between a baseline that asks only for correctness and a heuristic variant that additionally asks for efficiency-oriented design. Within each comparison, we hold fixed the LLM, decoding parameters, instances, evaluator, timeouts, and refinement budget, so differences can be attributed to the paradigm/prompt factors rather than to incidental implementation choices. 3.1
Solver-Generation Paradigms
All paradigms run inside the same evaluation framework: a single orchestration loop that prompts the LLM, executes the generated solver, and validates its output. They share the same problem description, input schema, and required output keys; the per-paradigm paragraphs below describe what artefact the LLM is asked to produce in each case and which solver backend it is allowed to use. 3
Prompt problem setup
Generate solver
Smoke check pass Scaling check pass (small instance) (harder instance) l fai
first pass
First-working artefact
Final artefact
Evaluate (all instances)
fail
Refine with feedback
retry
Figure 2: End-to-end workflow applied to the baseline and heuristic settings. The smoke check verifies that the LLM-generated solver runs and produces a valid output on a small instance. The scaling check re-runs the artefact on a separate mid-difficulty instance under a time budget. Failures at either stage are returned as feedback for refinement. Correctness is verified and runtime recorded during evaluation, when both first-working and final artefacts are run on all instances of the problem.
Native algorithmic search (Python). This paradigm tests the LLM as an algorithm designer. The LLM receives the problem context and is instructed to generate a standalone Python algorithm for solving the problem using only the Python standard library. At runtime, the generated function takes the input instance and returns a solution in the required format. We prohibit the use of backend solving tools, forcing the LLM to design the full algorithm itself through strategies such as pruning, dynamic programming, branch-and-bound, or problem-specific methods. Constraint modeling via the OR-Tools Python API (Python + OR-Tools). This paradigm tests the LLM’s constraint-modeling capability through a Python solver interface. The LLM receives the problem context and is instructed to formulate the problem using the OR-Tools CP-SAT API [Perron et al., 2023]. Rather than explicitly specifying how to find a solution, the LLM encodes problem requirements through decision variables, constraints, and optionally an objective function, while the OR-Tools CP-SAT solver automatically performs the search. Declarative constraint modeling (MiniZinc + OR-Tools). This paradigm tests the LLM as a declarative modeler. The LLM receives the problem context and is instructed to generate a MiniZinc model. MiniZinc is a high-level, solver-independent declarative modeling language for constraint satisfaction and optimization problems [Nethercote et al., 2007]. We adopt the two-step generation pipeline of Song and Cohen [2025] as a strong MiniZinc baseline, where the LLM is first instructed to generate the model and then a Python formatter that maps the solver’s variable assignments into the required format. We use the same CP-SAT solver backend as in the Python + OR-Tools setting. For each paradigm, the baseline prompt asks for a correct solver. The heuristic prompt additionally suggests classical efficiency techniques: stronger variable/value ordering, pruning, and problem decomposition for Python; tighter bounds, redundant or implied constraints, symmetry breaking, and explicit search annotations (e.g. int_search in MiniZinc, AddDecisionStrategy in CP-SAT) for the two solver-backed paradigms. The exact prompt texts are given verbatim in App. B.
3.2
Shared Refinement Protocol
All six (paradigm, prompt) configurations follow the same code-generation pipeline, summarized in Fig. 2. The pipeline applies two validation stages: a smoke check that the artefact runs and emits a schema-valid output on a small instance, followed by a scaling check that it still completes on a harder instance under a tighter time budget. Neither stage verifies solution correctness against the reference solver; SAT/UNSAT checking is deferred to the downstream evaluation described in Sec. 4.2, where both artefacts produced by the pipeline are run on the full per-problem instance pool and their outputs are checked against the reference. The smoke check executes solve_instance(data_dict) for the Python and Python + OR-Tools paradigms, and compiles and solves the model (then runs the formatter) for MiniZinc + OR-Tools; in both cases the returned dictionary is validated against the benchmark’s expected output schema and value ranges. The earliest revision to pass the smoke check is recorded as the first-working artefact; the first revision to additionally pass the scaling check is retained as the final artefact, or the most recent revision if none passes within the refinement budget. Whenever either check fails, the 4
failure—together with the previous artefact and the validation feedback—is fed back to the LLM as a refinement prompt. Each pipeline receives a refinement budget of four rounds.1 The protocol is identical for both prompt options: the prompt determines what the LLM is asked to attempt initially, and refinement iterates that attempt through the same gates. The scaling check is the workflow’s principal efficiency signal: rejecting artefacts that cannot finish a harder instance within a tight budget is intended to encourage more efficient generated solvers. Empirically, refinement is dominated by basic runnability recovery—fixing crashes, format violations, and timeouts—not by speedups on solvers that already run (Sec. C). The pipeline thus yields, per (LLM, paradigm, prompt, problem) tuple, a pair of artefacts—the first-working and the final—that feed both the experiments (Sec. 4) and the heuristic-trap analysis (Sec. 5). Comparing the two artefacts isolates the effect of refinement on correctness, runtime, and optimality. 3.3
Methodological Controls
Two methodological controls keep the comparison clean. External time control. All solver runtime budgets are imposed externally by the evaluation framework, not by the artefact itself. The prompt explicitly forbids the LLM from setting any internal time or step limit in the generated code (e.g., assigning to CpSolver().parameters .max_time_in_seconds) and from registering callbacks whose purpose is early stopping. Without this prohibition we observed that LLMs frequently insert their own per-instance time caps, which would silently truncate search and confound the paradigm-level comparison. Paradigm enforcement. The prompt also rules out common ways the LLM might leave its assigned representational surface. For Python + OR-Tools, the LLM must use ortools.sat.python .cp_model only, with no pure-Python fallback or third-party solvers (gurobipy, etc.); if OR-Tools is unavailable, the artefact must raise a clear RuntimeError. Without this clause LLMs wrap their CP-SAT call in a try/except that hands hard instances back to a hand-rolled Python loop, silently contaminating Python + OR-Tools with the native paradigm.
4
Experiments
How does a frontier LLM’s solving capability change with the representation it uses for the solver, and with whether the prompt asks for efficiency? This section answers the first question—and surfaces the empirical signature of the second, which Sec. 5 dissects mechanistically. After introducing the benchmark and metrics (Secs. 4.1–4.2), we present the main results across paradigms and the fidelity ranking they expose (Sec. 4.3), and close with a five-way outcome decomposition (Sec. 4.4). 4.1
The CP-SynC-XL Benchmark
We introduce CP-SynC-XL, an XL-scale extension of the CP-SynC benchmark [Song and Cohen, 2026]. CP-SynC contains 100 heterogeneous combinatorial problems—58 Constraint Satisfaction Problems (CSPs) and 42 Constraint Optimization Problems (COPs)—drawn from CSPLib and the PyCSP3 problem suite and spanning industrial and academic domains: sequencing (e.g. Car Sequencing, All-Interval Series), scheduling (e.g. Bus Driver Scheduling, Social Golfers), packing and assignment (e.g. Warehouse Location, Template Design), and combinatorial design (e.g. Golomb Rulers, Quasigroup Existence, Nonogram). Let P denote the set of problems. Each problem context p ∈ P is defined as p = (PNL , PIN , POUT ), where PNL is the natural-language problem description, PIN specifies the typed input parameters, and POUT specifies the required output format; each problem ships with a reference verifier for CSP feasibility and COP optimality against a curated reference solver. The original CP-SynC benchmark evaluates each problem on a single provided instance solvable by the reference model within 30 seconds. To probe solving performance more thoroughly, CP-SynC-XL augments this with additional parameter instances per problem. For each problem, we first searched for publicly available instances from sources including CSPLib, MiniZinc challenges, and XCSP3 competitions, and converted applicable instances into the benchmark’s input schema PIN , which yielded external instances for 13 1 Sampling is greedy throughout (T = 0, top-p = 1), and the model-side reasoning setting is held fixed.
5
Table 1: Instance-level outcomes at the 256 s budget. C (correct) = fraction of instances passing the verifier; P (provided) = fraction returning a schema-conformant output; F (fidelity) = C/P, the share of returned solutions that pass the verifier. Bold = best per LLM on each metric. D EEP S EEK -V3.2
GPT-5.3-C ODEX
G EMINI 3.1 P RO
C
C
C
Paradigm
Prompt
P
F
P
F
P
F
Python Python Python + OR-Tools Python + OR-Tools MiniZinc + OR-Tools MiniZinc + OR-Tools
baseline 0.291 0.478 60.9% 0.634 0.781 81.2% 0.606 0.708 85.6% heuristic 0.295 0.568 51.9% 0.630 0.781 80.7% 0.640 0.761 84.1% baseline 0.439 0.523 83.9% 0.702 0.786 89.3% 0.716 0.816 87.8% heuristic 0.365 0.538 67.8% 0.711 0.802 88.7% 0.722 0.814 88.7% baseline 0.300 0.338 88.8% 0.522 0.565 92.4% 0.544 0.588 92.5% heuristic 0.269 0.323 83.3% 0.541 0.597 90.6% 0.508 0.570 89.1%
problems. For the remaining problems, we wrote problem-specific generators with curated parameters controlling instance scale, producing instances at increasing scale (e.g. larger n for N-Queens, more customers and nodes for CVRP). The resulting suite contains 4,577 instances (median 60 per problem). The evaluation suite is agnostic to modeling frameworks and formulations, and checks the solution accuracy of generated solvers at the output-solution level. 4.2
Metrics and Evaluation Protocol
For every (artefact, instance) pair, the evaluation framework records two binary outcomes: (1) Provided, where the artefact returns a schema-conformant output dictionary within the 256 s budget; and (2) Correct, where the provided solution additionally passes the reference verifier (CSP feasibility and COP optimality). The ratio correct/provided is the fidelity ratio of a (paradigm, prompt) pair: the share of returned solutions that pass the verifier; its complement is the rate at which the artefact confidently produces a solution that the verifier rejects. We treat fidelity as a metric of its own in the analysis below. We summarise solver speed with cumulative runtime curves 2 over per-instance solver runtime. For every (LLM, paradigm, prompt) triple and every t ≤ T we report the fraction of instances solved correctly by time t. 4.3
Results
Figure 1 pairs, for every (LLM, paradigm, prompt) triple, the correct curve (solid) and the provided curve (dotted) on a shared log time axis. The solid curve measures how often an artefact has returned a verifier-accepted solution by time t; the dotted curve measures how often it has returned any schema-conformant solution by time t. Their vertical gap is therefore the confident-but-wrong mass, and the ratio between them is the fidelity summarized in Tab. 1. At the 256 s tail, the curves reveal two complementary rankings. Correctness ranks Python + OR-Tools > Python ≳ MiniZinc + OR-Tools on every LLM. On every LLM, the Python + OR-Tools correct curve is higher than both other paradigms over essentially the whole time axis, and the best (paradigm, prompt) pair per LLM at the 256 s tail uses Python + OR-Tools. The advantage is not that the LLM performs more combinatorial reasoning in Python; rather, delegating search to CP-SAT moves the main burden from designing a complete algorithm to encoding the variables, constraints, and objective faithfully. MiniZinc + OR-Tools, by contrast, falls below Python + OR-Tools on every LLM and below Python on D EEP S EEK -V3.2, despite carrying the largest theoretical speed-up surface (global constraints, search annotations). Because both solver-backed paradigms use OR-Tools CP-SAT, this gap is consistent with a surface-fluency bottleneck rather than a weaker back-end.3 Fidelity ranks MiniZinc + OR-Tools > Python + OR-Tools > Python on every LLM. The F column of Tab. 1—the share of returned solutions that pass the verifier, equivalently the ratio of the solid curve to the dotted curve in Fig. 1—inverts the correctness ranking. MiniZinc + OR-Tools maintains ≥ 83% fidelity on every (LLM, prompt) pair; Python + OR-Tools is intermediate (down to 65.0% on D EEP S EEK -V3.2’s heuristic prompt); Python is lowest (bottoming at 51.9% on the same 2 Curves are plotted on a base-2 logarithmic time axis from 0.25 s to T = 256 s, with major ticks at the canonical budgets {0.25, 0.5, 1, 2, 4, 8, 16, 32, 64, 128, 256} s. 3 The construct frequencies of Sec. B.4 make this interpretation more concrete.
6
Figure 3: Five-way outcome decomposition by paradigm and prompt, one panel per LLM. The bins partition the shared instance pool: correct (verifier accepts); suboptimal (feasible COP solution above the optimum); UNSAT (the returned solution, when pinned into the reference verifier, yields an UNSAT verdict on a feasible instance); invalid (returned-and-rejected, typically a violated constraint); no solution (no schema-conformant output within 256 s).
pair). This ranking follows from what it means for each paradigm to provide an answer. In Python, a returned solution is simply the output of a hand-written procedure. In Python + OR-Tools, it is a CP-SAT-feasible assignment to the model that the LLM encoded. In MiniZinc + OR-Tools, it is a CP-SAT-feasible assignment to a model that first had to clear MiniZinc’s type and well-formedness checks. Each step narrows the class of errors that can be hidden by a schema-conformant return value. MiniZinc + OR-Tools therefore has the highest conditional fidelity when it answers, despite its lower overall correct rate. A natural future direction is therefore to train or adapt models with stronger fluency in declarative modeling languages such as MiniZinc, rather than treating the current gap as an intrinsic limitation of declarative solver construction. The heuristic prompt yields marginal, inconsistent gains. The heuristic prompt asks the LLM to improve efficiency without changing the problem semantics; empirically, the effect is much weaker and less stable than this goal suggests. On the stronger LLMs (GPT-5.3-C ODEX and G EMINI 3.1 P RO) every paradigm-by-metric change stays within ±3.6 percentage points (pp) of the baseline—a mix of small positives and small negatives, with no paradigm consistently helped across both LLMs. On the weakest LLM (D EEP S EEK -V3.2) the prompt degrades performance: −7.4 pp of correctness and −16.1 pp of fidelity on Python + OR-Tools, plus −9.0 pp of fidelity on Python. Both halves of this pattern—marginal, inconsistently-signed effects on the stronger LLMs and sizeable, uniformly negative losses on the weakest—are the empirical signature of the heuristic trap; Sec. 5 traces them to specific code-level patterns the LLM injects that plausibly speed up the model on only a fraction of instances while introducing mis-encoding bugs. 4.4
Outcome Decomposition by Paradigm and Prompt
To identify where the provided–correct gap comes from, we decompose every (artefact, instance) outcome (Fig. 3) into five mutually exclusive bins: correct, where the verifier accepts the solution; suboptimal, a feasible COP solution worse than the optimum; UNSAT, where the LLM-generated solver returns a schema-conformant solution but pinning that solution into the reference verifier yields an UNSAT verdict on an instance the reference solver finds feasible; invalid, a returned-and-rejected case, typically a CSP solution violating a mis-encoded constraint; and no solution, no schemaconformant output within the 256 s budget (timeout, crash, or schema violation). Figure 3 shows three recurring patterns: No-solution is the largest non-correct slice on every panel. Inspection of the underlying logs shows these are overwhelmingly 256 s timeouts rather than crashes or malformed outputs—the budget ceiling compounds with whatever encoding errors each paradigm contributes. Suboptimal is a Python failure mode. The suboptimal bin is essentially absent from the solverbacked paradigms—where CP-SAT either proves the optimum or times out—but visible on every 7
Python panel, where hand-rolled COP procedures return feasible-but-non-optimal answers at the budget—an approximation attempt rather than guaranteed optimization. UNSAT is the dominant wrong verdict on the solver-backed paradigms. Once the larger nosolution share of MiniZinc + OR-Tools is netted out, both Python + OR-Tools and MiniZinc + OR-Tools concentrate their wrong-mass on UNSAT rather than invalid: the generated model admits returned assignments that do not satisfy the reference formulation. A manual audit of the top twelve problems by aggregated UNSAT mass on the Python + OR-Tools baseline setting (750 of 837 instances, 89.6%, across all three LLMs) shows that every audited case is a natural-languageto-formal-language mistranslation. We call these baseline mistranslation mechanisms M1–M4: M1 associative recall (the LLM names the problem before it reads it, e.g. a Hamiltonian template imposed on the Travelling-Purchaser problem); M2 long-spec attention drift (one or two textual constraints are silently dropped); M3 output-schema ambiguity between LLM and verifier (the LLM’s decision-variable wiring does not round-trip through the reference); and M4 sentinel-value misreading (overloaded zero/negative markers in the input are encoded as “no edge” or “unreachable”). M2 (38% of the audited UNSAT mass) and M3 (36%) jointly account for ≈ 75% of the audited mass, with M1 (16%) and M4 (10%) covering the rest: the dominant baseline failure is not solver-side reasoning but a fluency-shaped reading of the natural-language specification. App. F presents the audit per problem together with the offending code extracts.
5
Anatomy of the Heuristic Trap
To understand why the heuristic prompt is unsafe on some (LLM, paradigm) pairs, we performed a paired code-level analysis across all three paradigms and three LLMs. This section uses baseline (B) and heuristic (H) to denote the two prompt conditions. Correctness changes are reported as ∆acc = accH −accB in percentage points unless a table explicitly reports fractions; speed changes are reported as tB /tH , so values above 1 mean the heuristic-prompt solver is faster. Two findings organise the section. First, net-positive correctness gains and visible speed-ups concentrate on a narrow set of (LLM, paradigm) pairs. Second, the remaining regressions trace back to six paradigm-specific failure modes whose net effect depends on the LLM. 5.1
Aggregate Heuristic Effects
For GPT-5.3-C ODEX, the macro-averaged correctness change ∆acc (heuristic minus baseline, percentage points) is mildly positive on every paradigm (+1.2, +1.7, +2.2 pp on Python, Python + OR-Tools, MiniZinc + OR-Tools); for G EMINI 3.1 P RO it oscillates around zero (+2.2, −0.6, −1.1 pp); for D EEP S EEK -V3.2 it regresses on every paradigm, by as much as −6.6 pp on Python + OR-Tools. Thus, the same heuristic instruction can be mildly beneficial for one model and harmful for another; aggregating over LLMs would obscure this model-specific effect. The runtime picture is similarly selective. On Python and Python + OR-Tools the median per-problem speed-up tB /tH is ≈ 1.0× for every LLM, and 40–63% of common-correct instances are in fact slower under the heuristic prompt. MiniZinc + OR-Tools is the only paradigm where heuristics operate at the model level so CP-SAT can exploit them deterministically; everywhere else the LLM’s heuristic suggestions either re-express constraints or substitute its own search procedure, and CP-SAT’s propagation already does the work the LLM is trying to add. 5.2
Six Failure Modes Behind the Regressions
A code-level audit of heuristic-prompt solvers identifies six failure modes (A–F) that cover the dominant recurring sources of correctness regressions in our audit. These modes are separate from the baseline mistranslation mechanisms M1–M4 in Sec. 4.4: M1–M4 explain why a baseline solver can return a wrong answer, whereas A–F explain what the heuristic prompt newly changes relative to the paired baseline. Each mode is marked by a conservative source-level detector and then interpreted through paired outcome changes. A unverified “tight” bounds (Python + OR-Tools; 13.5% incidence); B Big-M / MTZ rewrites that weaken propagation (Python + OR-Tools; 4.0%); C hand-computed seeding (Python + OR-Tools; 19.5%); D silent loss of completeness (Python; 16.2%); E COP→SAT collapse against an unproven optimum (MiniZinc + OR-Tools; 0.7%); and F overcomplicated redundant-machinery blow-ups (MiniZinc + OR-Tools; 29.1%). Per-LLM incidence and within-mode 8
Table 2: Failure-mode incidence and within-mode outcome split, per LLM (relevant-paradigm population N ≈ 99 per LLM, slightly smaller for MiniZinc + OR-Tools where some problems do not compile). Inc. is the fraction of that population whose heuristic-prompt solver matches the mode’s detector; ∆acc is the within-mode mean correctness change reported as a fraction (e.g. +0.028 = +2.8 pp); % reg./% imp. partition within-mode problems by ∆acc (≤ −5 pp / ≥ +5 pp); Med. sp. is the median tB /tH on common-correct instances, and %f / %s is the percentage of those instances with tB /tH > 1 / < 1. Bold rows: the (mode, LLM) pair produces a net regression or a > 25% within-mode regression rate. Modes A–D and F use behavioural source-level detectors that are LLM-agnostic; Mode E uses a stricter “base optimises but heuristic satisfies” diff and so reflects an explicit COP→SAT collapse rather than an LLM-rewritten objective bound. Mode
Paradigm
LLM
nmode
Inc.
∆acc
A
Python + OR-Tools
GPT-5.3-C ODEX G EMINI 3.1 P RO D EEP S EEK -V3.2
11 10 19
11.1 +0.028 9.1 10.1 +0.022 0.0 19.2 −0.067 21.1
18.2 10.0 26.3
0.96 0.99 0.95
0.4/ 3.5 4.2/ 1.8 0.0/ 4.7
B
Python + OR-Tools
GPT-5.3-C ODEX G EMINI 3.1 P RO D EEP S EEK -V3.2
2 3 7
2.0 3.0 7.1
+0.150 −0.078 +0.029
50.0 33.3 28.6
50.0 0.0 28.6
0.88 1.00 1.01
20.5/59.1 2.3/ 2.3 37.3/ 3.9
C
Python + OR-Tools
GPT-5.3-C ODEX G EMINI 3.1 P RO D EEP S EEK -V3.2
26 9 23
26.3 9.1 23.2
+0.009 +0.018 +0.061
15.4 0.0 8.7
23.1 11.1 17.4
1.00 1.02 0.96
3.8/ 5.2 6.8/ 0.0 2.9/ 1.3
D
Python
GPT-5.3-C ODEX G EMINI 3.1 P RO D EEP S EEK -V3.2
14 11 23
14.1 +0.018 7.1 11.1 +0.055 9.1 23.2 −0.037 21.7
14.3 18.2 17.4
0.95 1.00 0.97
4.2/17.7 0.0/ 1.7 0.7/ 0.7
E
MiniZinc + OR-Tools
GPT-5.3-C ODEX G EMINI 3.1 P RO D EEP S EEK -V3.2
2 0 0
2.0 −0.334 50.0 0.0 — — 0.0 — —
0.0 — —
0.88 — —
41.2/ 5.9 — —
F
MiniZinc + OR-Tools
GPT-5.3-C ODEX G EMINI 3.1 P RO D EEP S EEK -V3.2
39 11 30
39.8 +0.013 11.3 +0.009 37.5 +0.002
23.1 18.2 30.0
1.17 1.05 0.90
44.0/13.5 25.9/15.7 30.8/26.4
% reg. % imp. Med. sp.
17.9 18.2 30.0
%f / %s
outcome split appear in Tab. 2. Full mechanism descriptions, detector definitions, and source-level code extracts are discussed in App. G. Two patterns cut across the modes; the per-LLM ∆acc and within-mode regression rates cited below are taken from Tab. 2. Mode A’s net effect depends on bound quality, not bound presence. Mode A is net-positive for GPT-5.3-C ODEX and G EMINI 3.1 P RO but net-negative for D EEP S EEK V3.2: GPT-5.3-C ODEX’s “bound” comments are typically correct theorems in disguise, whereas D EEP S EEK -V3.2’s are more often wishful invariants. The resulting swing in ∆acc (−6.7 pp on D EEP S EEK -V3.2 vs. +2.8 pp on GPT-5.3-C ODEX) reflects the verifiability of what each LLM annotates as a bound, not the mode itself. The most-frequent mode is bimodal; the rare modes are high-risk. Mode F drives both MiniZinc + OR-Tools’s genuine speed-ups and its heaviest regressions: the redundant auxiliary structure sometimes carries propagation that CP-SAT cannot derive on its own, and sometimes overwhelms flattening or tightens domains too aggressively—an outcome we cannot predict before the run. Modes B and E are rare in absolute incidence but cripple correctness when triggered (−33.4 pp mean for E on GPT-5.3-C ODEX; 33% within-mode regression rate for B).
6
Conclusion
We studied LLM solver synthesis along two axes: representation and search optimization. Across three frontier LLMs, GPT-5.3-C ODEX, G EMINI 3.1 P RO, and D EEP S EEK -V3.2, Python + OR-Tools attains the highest correctness despite sharing CP-SAT backend with MiniZinc + OR-Tools, while native Python is the most likely to return schema-valid but verifier-rejected answers. This pattern is consistent with the modeling surface itself being a central bottleneck, not only the underlying solver. On the optimization axis, heuristic prompting yields modest MiniZinc + OR-Tools speed-ups but has a bimodal effect: some generated artefacts improve, while others become slower or less correct. A paired code audit traces these regressions to six paradigm-specific failure modes, with the risk 9
concentrated when the LLM replaces solver-native machinery with unverified bounds, hard fixes, or algorithmic substitutions. The practical implication is to use the LLM primarily at the formalisation interface—variables, constraints, objectives, and carefully scoped solver-native annotations—and to subject LLM-authored search optimizations to independent validation.
References Ali AhmadiTeshnizi, Wenzhi Gao, and Madeleine Udell. Optimus: Scalable optimization modeling with (mi) lp solvers and large language models. arXiv preprint arXiv:2402.10172, 2024. Gheorghe Comanici, Eric Bieber, Mike Schaekermann, Ice Pasupat, Noveen Sachdeva, Inderjit Dhillon, Marcel Blistein, Ori Ram, Dan Zhang, Evan Rosen, et al. Gemini 2.5: Pushing the frontier with advanced reasoning, multimodality, long context, and next generation agentic capabilities. arXiv preprint arXiv:2507.06261, 2025. Alex Duchnowski, Ellie Pavlick, and Alexander Koller. A knapsack by any other name: Presentation impacts LLM performance on NP-hard problems. In Christos Christodoulopoulos, Tanmoy Chakraborty, Carolyn Rose, and Violet Peng, editors, Findings of the Association for Computational Linguistics: EMNLP 2025, pages 6628–6651, Suzhou, China, November 2025. Association for Computational Linguistics. ISBN 979-8-89176-335-7. doi: 10.18653/v1/2025.findings-emnlp.352. URL https://aclanthology.org/2025.findings-emnlp.352/. Nouha Dziri, Ximing Lu, Melanie Sclar, Xiang Lorraine Li, Liwei Jiang, Bill Yuchen Lin, Sean Welleck, Peter West, Chandra Bhagavatula, Ronan Le Bras, et al. Faith and fate: Limits of transformers on compositionality. Advances in neural information processing systems, 36:70293– 70332, 2023. Lizhou Fan, Wenyue Hua, Lingyao Li, Haoyang Ling, and Yongfeng Zhang. NPHardEval: Dynamic benchmark on reasoning ability of large language models via complexity classes. In Lun-Wei Ku, Andre Martins, and Vivek Srikumar, editors, Proceedings of the 62nd Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pages 4092–4114, Bangkok, Thailand, August 2024. Association for Computational Linguistics. doi: 10.18653/v1/2024. acl-long.225. URL https://aclanthology.org/2024.acl-long.225/. Luyu Gao, Aman Madaan, Shuyan Zhou, Uri Alon, Pengfei Liu, Yiming Yang, Jamie Callan, and Graham Neubig. Pal: Program-aided language models. In International conference on machine learning, pages 10764–10799. PMLR, 2023. Aaron Jaech, Adam Kalai, Adam Lerer, Adam Richardson, Ahmed El-Kishky, Aiden Low, Alec Helyar, Aleksander Madry, Alex Beutel, Alex Carney, et al. Openai o1 system card. arXiv preprint arXiv:2412.16720, 2024. Xia Jiang, Jing Chen, Cong Zhang, Jie Gao, Chengpeng Hu, Chenhao Zhang, Yaoxin Wu, and Yingqian Zhang. Reasoning in a combinatorial and constrained world: Benchmarking llms on natural-language combinatorial optimization. arXiv preprint arXiv:2602.02188, 2026. Christophe Lecoutre and Nicolas Szczepanski. Pycsp3: modeling combinatorial constrained problems in python. arXiv preprint arXiv:2009.00326, 2020. Aixin Liu, Bei Feng, Bing Xue, Bingxuan Wang, Bochao Wu, Chengda Lu, Chenggang Zhao, Chengqi Deng, Chenyu Zhang, Chong Ruan, et al. Deepseek-v3 technical report. arXiv preprint arXiv:2412.19437, 2024a. Fei Liu, Xialiang Tong, Mingxuan Yuan, Xi Lin, Fu Luo, Zhenkun Wang, Zhichao Lu, and Qingfu Zhang. Evolution of heuristics: Towards efficient automatic algorithm design using large language model. arXiv preprint arXiv:2401.02051, 2024b. Fengze Liu, Haoyu Wang, Joonhyuk Cho, Dan Roth, and Andrew Lo. AutoCT: Automating interpretable clinical trial prediction with LLM agents. In Christos Christodoulopoulos, Tanmoy Chakraborty, Carolyn Rose, and Violet Peng, editors, Proceedings of the 2025 Conference on Empirical Methods in Natural Language Processing, pages 30945–30970, Suzhou, China, November 2025. Association for Computational Linguistics. ISBN 979-8-89176-332-6. doi: 10.18653/v1/ 2025.emnlp-main.1575. URL https://aclanthology.org/2025.emnlp-main.1575/. 10
Yecheng Jason Ma, William Liang, Guanzhi Wang, De-An Huang, Osbert Bastani, Dinesh Jayaraman, Yuke Zhu, Linxi Fan, and Anima Anandkumar. Eureka: Human-level reward design via coding large language models. arXiv preprint arXiv:2310.12931, 2023. Kostis Michailidis, Dimos Tsouros, and Tias Guns. Cp-bench: Evaluating large language models for constraint modelling. arXiv preprint arXiv:2506.06052, 2025. Iman Mirzadeh, Keivan Alizadeh, Hooman Shahrokhi, Oncel Tuzel, Samy Bengio, and Mehrdad Farajtabar. Gsm-symbolic: Understanding the limitations of mathematical reasoning in large language models. arXiv preprint arXiv:2410.05229, 2024. Nicholas Nethercote, Peter J Stuckey, Ralph Becket, Sebastian Brand, Gregory J Duck, and Guido Tack. Minizinc: Towards a standard cp modelling language. In International conference on principles and practice of constraint programming, pages 529–543. Springer, 2007. Liangming Pan, Alon Albalak, Xinyi Wang, and William Wang. Logic-lm: Empowering large language models with symbolic solvers for faithful logical reasoning. In Findings of the Association for Computational Linguistics: EMNLP 2023, pages 3806–3824, 2023. Laurent Perron, Frédéric Didier, and Steven Gay. The cp-sat-lp solver. In Roland H. C. Yap, editor, 29th International Conference on Principles and Practice of Constraint Programming (CP 2023), volume 280 of Leibniz International Proceedings in Informatics (LIPIcs), pages 3:1–3:2, Dagstuhl, Germany, 2023. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. ISBN 978-3-95977-3003. doi: 10.4230/LIPIcs.CP.2023.3. URL https://drops.dagstuhl.de/opus/volltexte/ 2023/19040. Rindranirina Ramamonjison, Timothy Yu, Raymond Li, Haley Li, Giuseppe Carenini, Bissan Ghaddar, Shiqi He, Mahdi Mostajabdaveh, Amin Banitalebi-Dehkordi, Zirui Zhou, et al. Nl4opt competition: Formulating optimization problems based on their natural language descriptions. In NeurIPS 2022 competition track, pages 189–203. PMLR, 2023. Bernardino Romera-Paredes, Mohammadamin Barekatain, Alexander Novikov, Matej Balog, M Pawan Kumar, Emilien Dupont, Francisco JR Ruiz, Jordan S Ellenberg, Pengming Wang, Omar Fawzi, et al. Mathematical discoveries from program search with large language models. Nature, 625(7995):468–475, 2024. Parshin Shojaee, Iman Mirzadeh, Keivan Alizadeh, Maxwell Horton, Samy Bengio, and Mehrdad Farajtabar. The illusion of thinking: Understanding the strengths and limitations of reasoning models via the lens of problem complexity. arXiv preprint arXiv:2506.06941, 2025. Yuliang Song and Eldan Cohen. Do llms understand constraint programming? zero-shot constraint programming model generation using llms. In International Conference on Learning and Intelligent Optimization, pages 16–31. Springer, 2025. Yuliang Song and Eldan Cohen. Cp-sync: Multi-agent zero-shot constraint modeling in minizinc with synthesized checkers, 2026. URL https://arxiv.org/abs/2605.01675. Sumanth Varambally, Thomas Voice, Yanchao Sun, Zhifeng Chen, Rose Yu, and Ke Ye. Hilbert: Recursively building formal proofs with informal reasoning. In ICLR, NeurIPS Workshop, 2025. URL https://arxiv.org/abs/2509.22819. Haoyu Wang and Dan Roth. LLMs as translators, not thinkers: Structured output enables stronger NP-hard problem solving, 2025. URL https://openreview.net/forum?id=LiSRvegl7Z. Haoyu Wang, Tao Li, Zhiwei Deng, Yaqing Wang, Xinyi Wu, Deepak Ramachandran, and Dan Roth. Polynomial-time reasoning at the edge of NP, 2025. URL https://openreview.net/forum? id=2yhCEYmeiP. Wujiang Xu, Zujie Liang, Kai Mei, Hang Gao, Juntao Tan, and Yongfeng Zhang. A-mem: Agentic memory for llm agents. arXiv preprint arXiv:2502.12110, 2025. Chengrun Yang, Xuezhi Wang, Yifeng Lu, Hanxiao Liu, Quoc V Le, Denny Zhou, and Xinyun Chen. Large language models as optimizers. In The Twelfth International Conference on Learning Representations, 2024. URL https://openreview.net/forum?id=Bb4VGOWELI. 11
Xi Ye, Qiaochu Chen, Isil Dillig, and Greg Durrett. Satlm: Satisfiability-aided language models using declarative prompting. Advances in Neural Information Processing Systems, 36:45548–45580, 2023. Yuchen Zhuang, Xiang Chen, Tong Yu, Saayan Mitra, Victor Bursztyn, Ryan A Rossi, Somdeb Sarkhel, and Chao Zhang. Toolchain*: Efficient action space navigation in large language models with a* search. arXiv preprint arXiv:2310.13227, 2023.
A
Limitations
Three controls bound the external validity of our findings. (i) We evaluate three frontier LLMs from a late-2025 snapshot; future or smaller models may exhibit different paradigm preferences, and absolute fidelity numbers should be read as a snapshot rather than an upper bound. (ii) We fix OR-Tools as the back-end across both solver-backed paradigms, so the representational-divergence finding should be read as evidence for this CP-SAT-backed API/declarative pairing rather than as a claim about all MIP-, SAT-, or CP-modeling pipelines. (iii) We operate in the single-shot synthesis regime with ≤ 4 refinement rounds and a 256 s solver budget per instance; the heuristic-trap claims therefore concern bounded-refinement deployment settings rather than the population-and-selection regimes used by FunSearch-style algorithm-synthesis loops. We do not study finetuning, tool-augmented agents, or multi-instance amortised solving, all of which lie outside the scope of this paper.
B
Prompt details and refinement templates
We list, verbatim, the prompts and refinement templates used by the three paradigms of Sec. 3.1. Each preset ships exactly the text below; placeholders {err_msg}, {previous_code}, and {refinement_feedback_message} are substituted from the evaluation framework’s state at refinement time. Sampling is greedy (T = 0, top-p = 1); for models that expose a reasoning budget we fix the budget at the medium tier across all generators. LLM calls are made through the OpenRouter chat-completions endpoint https://openrouter.ai/api/v1/chat/completions. The three model identifiers used in the experiments are openai/gpt-5.3-codex, google/gemini-3.1-pro-preview, and deepseek/deepseek-v3.2. Each request uses a system message and user/refinement messages, forwards max_tokens=128000, temperature=0, top_p=1, and, when supported by the provider, reasoning.effort=medium; the request timeout is 300 s and transient HTTP/network failures are retried with exponential backoff. The run configuration persisted with every generated artefact records the exact model id, prompt/backend preset, refinement budget, sampling parameters, package versions, and the repository commit. B.1
Python-Based Pipelines (Python and Python + OR-Tools)
System prompt. You are an expert constraint programming and algorithm design assistant. You will be given: - A problem name and full description (and optionally input/output specs). - How the inputs are structured: parameters arrive as a Python dict `data_dict`. The prompt may describe keys by type/schema (not fixed concrete values) because the same code must solve many instances of this problem. Your task is to write Python code that **defines** a function: def solve_instance(data_dict) -> dict: ... return hypothesis_solution Requirements: - Do NOT read or write files, do NOT use the network. - Read all problem data from `data_dict` at runtime (do not assume one fixed instance).
12
- Do not print anything or execute the solver; just define the function. - At the bottom of your code, do NOT call `solve_instance`; we will call it. Output ONLY valid Python code. Do not include explanations or comments outside code.
User prompt template. The user prompt concatenates the natural-language problem description, an inferred schema for the parameter dictionary, the list of required output keys, and the two toggle blocks below. The full schema and required-output blocks are synthesized from the released benchmark and are omitted here for brevity. Algorithmic guidance — baseline preset. Algorithmic guidance: produce a correct solver.
Algorithmic guidance — heuristic preset. Algorithmic guidance: - Use heuristics whenever possible to improve search efficiency. - Avoid naive exhaustive DFS/backtracking as the primary approach. - Design for scalability: strong variable/value ordering, pruning, symmetry breaking, feasibility prechecks, decomposition, and restart/randomized multi-start when useful. - For optimization problems, propagate tight objective bounds and use incumbent-based pruning (valid dominance / bound reasoning), not wall-clock or arbitrary time budgets. - Include concise internal helper structure that makes pruning logic explicit.
Backend constraints — Python + OR-Tools. Backend preference: - Use OR-Tools CP-SAT (`ortools.sat.python.cp_model`) for modeling. - Do NOT configure CP-SAT wall-clock or step limits that stop search early. Forbidden examples (non-exhaustive): assigning to `CpSolver().parameters.max_time_in_seconds`, `solver.parameters.max_time_in_seconds`, or similar time/step caps; time-based callbacks whose purpose is early stopping. Let the outer evaluation framework control runtime. - STRICT requirement: You must solve using OR-Tools CP-SAT only. - Do NOT use gurobipy and do NOT use a pure-Python fallback solver. - If OR-Tools is unavailable, raise a clear RuntimeError immediately. - Keep the public entrypoint unchanged: `solve_instance(data_dict) -> dict`.
Backend constraints — native paradigm. Backend preference: - Use Python standard library only. - Do not rely on third-party optimization libraries. - Do NOT set any explicit time limit inside generated code (e.g., no solver-style TimeLimit and no custom early-stop wall-clock cutoff logic).
Refinement template. Whenever a generated solver fails either the seed-instance check or the 30 s gate check, the LLM is re-prompted with the template below; the algorithmic-guidance and backend blocks are appended unchanged.
13
The following Python solver code needs refinement based on runtime/validation feedback. Fix the code and output ONLY the corrected Python code (no explanation). Define exactly one function: `solve_instance(data_dict) -> dict`. Feedback: ``` {refinement_feedback_message} ``` Previous code: ```python {previous_code} ``` Keep the same function signature and continue following these strategy requirements: {algorithmic guidance for the active preset} {backend block for the active paradigm} Provide the corrected code in a single markdown code block. Do not call `solve_instance` at the bottom; we will call it.
B.2
Declarative Pipeline
System prompt — baseline-MiniZinc. You are an expert in modeling constraint programming tasks with MiniZinc. Read the problem description in markdown, then model this problem and provide MiniZinc code for your model.
System prompt — heuristic-MiniZinc. ing sentence:
The baseline system prompt is augmented with the follow-
Prioritize model efficiency as well as correctness. Prefer formulations that solve efficiently, using tighter bounds, redundant constraints, symmetry breaking, implied constraints, search guidance, or similar techniques when helpful.
User prompt for stage 1. The user prompt concatenates the problem description, the data-file schema, and a format directive declaring the required output variables. The latter follows the “twostage with format constraints” template of Song and Cohen [2025]; we leave its phrasing unchanged for comparability with that pipeline. The full rendered prompts, including the problem-specific schema and required-output block, are saved in the released run logs together with the generated MiniZinc model and output formatter. Stage-3 user prompt — output formatter. The model has been successfully executed, and the decision variable values have been stored. Briefly explain the task and write a Python function named `transform_n_display` that processes these solutions, stores them in a dictionary in the specified format, and then returns this dictionary. The function should take two dictionaries as parameters: (1) `data_dict`, which contains all the input parameter values, and (2) `decision_var_dict`, which contains exactly the decision variable values as used in the MiniZinc model you generated. [...] Ensure your Python script handles these transformations accurately and returns the dictionary with variables in the following format: {required output spec}.
Refinement template — syntax / runtime error. 14
I have executed the code you just generated and it caused an error message from the IDE: ``` {err_msg} ``` Please review the error message and the code, explain why this error occurred in one sentence, then fix the error and provide the correct code in a markdown code block.
Refinement template — efficiency-gate failure (heuristic-MiniZinc only). I ran the model on another benchmark instance with a 30-second time limit and it did not meet the required solving target: ``` {err_msg} ``` Please improve the model efficiency and provide the full corrected code in a markdown code block. Keep the model syntax-correct. You can add redundant constraints, symmetry breaking, tighter bounds, implied constraints, search guidance, or any other tricks that narrow the search space.
Refinement template — evaluation feedback. The code you just provided has been executed, and the generated solution was checked by the CPMP evaluation script. It returned the following result or error: ``` {err_msg} ``` Please review the evaluation feedback, explain the cause in one sentence, and then fix the code and provide the correct code in a markdown code block.
Computing infrastructure. All experiments were executed on a Linux compute pool of dual-socket x86_64 servers running openSUSE Leap 16.0 with kernel 6.12. Each node is equipped with two Intel Xeon Gold processors from the Xeon Scalable family (16 cores per socket, 2.1–2.3 GHz base / 3.7–3.9 GHz turbo, 22 MiB L3 cache per socket), exposing 64 hardware threads (2×16 physical cores with 2-way simultaneous multithreading) distributed over two NUMA domains. Each node is provisioned with at least 345 GiB of ECC DDR4 main memory, comfortably above the resident-set requirement of any constraint-programming subprocess we spawn. The CPU frequency governor was pinned to performance on every node to eliminate dynamic frequency scaling as a confounder for runtime measurements. The constraint-programming back-end is MiniZinc 2.9.6 driving Google OR-Tools CP-SAT 9.15, invoked from Python 3.11.15 through the official minizinc-python bindings. Each generated model is replayed against every parameter instance under a strict 256-second per-instance solver budget, matching the generation-time budget used by the LLM code-refinement loop; instance verification against the reference checker operates under a tighter 128-second budget. To bound resource contention, every node executes at most 100 concurrent solver subprocesses, with the driver enforcing both a per-task estimated memory reservation and a global guard that refuses to launch a new worker if free system memory would fall below 10% of total RAM. We pin every (LLM, generation-strategy) experiment to a single physical node, so per-instance runtimes reported within an experiment are mutually consistent and free of cross-machine drift. All scripts, raw per-instance solver logs, generated solution pickles, and evaluation transcripts are released alongside the paper to permit byte-level reproduction. 15
B.3
Experimental details
Instance filtering. Due to time and compute constraints, we impose a 256 s runtime limit when validating each candidate instance with the reference solver. Candidate instances whose reference validation does not complete within this limit, including those marked as UNKNOWN or ending in timeout, are excluded from the reported comparisons. This filtering leaves 2,565 instances in the final evaluation set reported in the figures and tables.
B.4
Backend-Specific Construct Families and How Often They Appear
We extracted, from every LLM-generated solver in the heuristic preset, the set of constructs the heuristic prompt could plausibly elicit. Table 3 reports the percentage of problems (N ≈ 99 per pair) whose heuristic-prompt solver contains each construct, for every (LLM, backend) pair. The construct families are very different across backends—search hooks dominate Python + OR-Tools, search annotations and globals dominate MiniZinc + OR-Tools, and algorithmic substitutions dominate Python—which is itself a finding: when the same prompt is delivered, the same LLM chooses different syntactic surfaces depending on the language it is instructed to emit. Two patterns in Tab. 3 are worth flagging. First, GPT-5.3-C ODEX reaches for native CP-SAT search hooks under the heuristic prompt (71.7% AddDecisionStrategy on Python + OR-Tools, 70.4% first_fail on MiniZinc + OR-Tools), which the next subsection shows are largely safe. Second, D EEP S EEK -V3.2 reaches for higher-risk devices at much higher rates—randomised choice (37.4% vs. 0.0%), multi-restart (18.2% vs. 5.1%), and iteration caps (12.1% vs. 7.1%) on Python; 64.6% num_search_workers and 63.6% symmetry-breaking constraints on Python + OR-Tools (vs. GPT-5.3-C ODEX’s 20.2% and 32.3%). These same construct families are over-represented among its within-pattern regressions.
B.5
The Trap’s Signature: Per-Pattern Outcome Breakdown
A construct’s frequency alone tells us nothing about its effect. To isolate effect we condition on the construct: for every problem in which the heuristic-prompt solver contains construct C, we record the paired correctness change ∆acc = accH − accB relative to the baseline-prompt solver and, on common-correct instances, the per-instance speed ratio tB /tH . We aggregate within (LLM, backend, C). Table 4 reports the constructs whose effect was most informative; we focus on constructs with ≥ 5 supporting problems and on the correctness-regression rate (within-pattern). 16
Table 3: Frequency (%) with which each heuristic construct appears in the LLM’s heuristic-prompt solver, across 99 problems per (LLM, backend) pair. Bold values flag the dominant construct(s) per backend per LLM. Three sub-tables, one per backend. Pure Python (Native Algorithmic Search) Construct
GPT-5.3-C ODEX
G EMINI 3.1 P RO
D EEP S EEK -V3.2
45.5 3.0 7.1 2.0 3.0 6.1 5.1 0.0 7.1 13.1 8.1
51.5 4.0 3.0 8.1 5.1 0.0 6.1 13.1 2.0 14.1 17.2
44.4 2.0 7.1 9.1 2.0 4.0 18.2 37.4 12.1 20.2 30.3
5.1 5.1 11.1 0.0 40.4 9.1 6.1 27.3 1.0 43.4 12.1 0.0
20.2 21.2 64.6 17.2 52.5 4.0 7.1 26.3 7.1 63.6 10.1 0.0
22.7 14.4 3.1 9.3 12.4 32.0 6.2 7.2 3.1 11.3 3.1 46.4 37.1 2.1 75.3
48.7 25.0 3.7 18.8 17.5 42.5 0.0 1.3 2.5 16.3 1.3 62.5 58.8 0.0 61.3
DFS / backtracking Memoisation (lru_cache/@cache) DP table Branch & bound Beam / A⋆ Local search (SA / 2-opt / hill-climb) Multi-start / random restart Randomised choice (random.*) Iteration-cap truncation Symmetry breaking Dominance / bound (in comments)
OR-Tools CP-SAT (Python + OR-Tools) AddDecisionStrategy (var/val ord.) AddHint (warm start) num_search_workers random_seed Custom objective bound (Add( obj ≤ k)) AddCircuit AddMultiplicationEquality OnlyEnforceIf (reified) Big-M / MTZ encoding Symmetry-breaking constraints Variable fixing / hard equalities Pre-step Python heuristic fed to CP-SAT
71.7 22.2 20.2 3.0 58.6 6.1 7.1 19.2 0.0 32.3 20.2 2.0
MiniZinc (Declarative Modeling) 89.8 70.4 20.4 27.6 8.2 33.7 7.1 5.1 4.1 21.4 4.1 76.5 60.2 7.1 75.5
Custom search annotation first_fail dom_w_deg input_order smallest/largest all_different global_cardinality circuit/subcircuit cumulative/disjunctive lex_lesseq/value_precede table/regular Redundant / implied constraint (in comments) Symmetry-breaking constraint (lex / value-prec.) Prefix-/running-sum auxiliary Tighter explicit variable bounds
Table 4: Per-pattern outcome breakdown. “Coverage” is the fraction of N ≈ 99 problems whose heuristic-prompt solver contains the construct (same as Table 3). “% regress”, “% improve” are the within-pattern fractions of problems with ∆acc ≤ −5 pp resp. ≥ +5 pp. “Med. sp.” is the median per-problem tB /tH on common-correct instances; “% faster”, “% slower” are the within-pattern fractions of common-correct instances (not problems) with ratio ≥ 1.2 resp. ≤ 0.8. Bold rows: regression-rate ≥ 25% or mean ∆acc ≤ −5 pp. LLM
Backend
Construct
∆acc % reg. % impr. Med. sp. % faster % slower
Cov.
(a) Mostly safe constructs (within-pattern regression < 15%) GPT-5.3-C ODEX GPT-5.3-C ODEX GPT-5.3-C ODEX GPT-5.3-C ODEX GPT-5.3-C ODEX GPT-5.3-C ODEX G EMINI 3.1 P RO G EMINI 3.1 P RO GPT-5.3-C ODEX
OR-Tools OR-Tools OR-Tools MiniZinc MiniZinc MiniZinc MiniZinc Python MiniZinc
AddDecisionStrategy OnlyEnforceIf symmetry break (lex / sort) circuit/subcircuit all_different first_fail circuit/subcircuit DFS / backtracking redundant/implied constraint
71.7 19.2 32.3 5.1 33.7 70.4 7.2 51.5 76.5
+0.013 +0.109 +0.063 +0.017 +0.078 +0.011 +0.024 +0.037 +0.030
8.5 5.3 3.1 0.0 9.1 13.0 14.3 13.7 16.0
14.1 31.6 18.8 20.0 27.3 15.9 28.6 27.5 20.0
1.00 1.00 1.00 5.54 1.40 1.21 1.46 1.00 1.18
2.9 3.0 0.2 100.0 53.9 55.5 5.1 6.8 52.3
6.9 1.0 2.4 0.0 10.0 11.0 83.5† 2.9 13.9
62.5 25.0 33.3 33.3 12.5
0.0 0.0 14.3 0.0 25.0
1.42 1.23 1.08 0.97 0.98
48.4 44.0 42.1 0.0 0.0
17.2 6.0 10.7 0.0 12.3
(b) High-risk “trap” constructs (within-pattern regression ≥ 25% or ∆acc ≤ −5 pp)
17
GPT-5.3-C ODEX GPT-5.3-C ODEX GPT-5.3-C ODEX GPT-5.3-C ODEX GPT-5.3-C ODEX
MiniZinc MiniZinc MiniZinc OR-Tools Python
smallest/largest val. sel. global_cumulative global_lex / value_precede random_seed dominance/bound (claimed in comments)
8.2 4.1 21.4 3.0 8.1
−0.225 −0.188 +0.027 −0.315 −0.076
Two patterns emerge from the per-pattern conditioning. Construct families have intrinsic risk profiles, but those profiles interact with model capability. first_fail is a canonical safe heuristic in CP, and indeed for GPT-5.3-C ODEX it regresses on only 13.0% of MiniZinc + OR-Tools problems (mean ∆acc = +0.011); for D EEP S EEK -V3.2 the same construct regresses on 25.0% of problems with mean ∆acc = −0.118 and a median slow-down of 0.88×. The construct is identical—the difference is whether the LLM applies it on a variable scope that admits propagation or on a mis-modelled scope that does not. AddDecisionStrategy, OnlyEnforceIf, and symmetry-breaking constraints exhibit the same pattern in Python + OR-Tools: 5%−10% regression for GPT-5.3-C ODEX and 25%−35% for D EEP S EEK -V3.2 (Table 4, panel b). A subset of constructs is intrinsically dangerous. Three constructs regress at high rates regardless of LLM: • Aggressive value selectors on MiniZinc + OR-Tools (smallest/largest, dom_w_deg): GPT-5.3-C ODEX regresses on 62.5% of smallest/largest problems by −22.5 pp on average—the worst within-pattern regression in our benchmark. The selector imposes a value-ordering decision that, when the variable’s domain ordering does not align with feasibility, forecloses on the satisfying region. • Symmetry / lex-precede chains beyond the trivial scope: on MiniZinc + OR-Tools, value_precede_chain regresses on 33% − 46% of problems for all three LLMs—the constraint is correct only when the values are interchangeable, a property the LLM rarely verifies. • Iteration caps in pure Python (+D EEP S EEK -V3.2 only): max_iter cuts off the search before the search has explored the feasible region; 41.7% of problems regress. These three families are the clearest examples of constructs that violate the problem’s underlying semantics (rather than its search ordering or propagation) and on which the LLM cannot self-verify.
C
Refinement Efficacy Statistics
The pipeline retains both the first-working version of each generated solver—the earliest refinement attempt to pass a seed-instance runtime and format check—and the final-refined version after up to four refinement rounds aimed at clearing a 30 s execution gate. Tab. 5 compares the two artefacts on the shared instance pool. The comparison yields three conclusions. (R1) Refinement does not measurably accelerate solvers: the median speed-up is essentially 1.0× in every (paradigm, prompt) pair, and on the heuristic_ortools setting 51.9% of overlapping instances are slower after refinement. (R2) Refinement is an error-recovery loop: the modest correctness gains (+1.4 to +3.5 pp on three of four pairs) are driven almost entirely by “final-only” instances—cases that crashed or violated the format check on the first round—rather than by speed-ups on already-correct instances. (R3) Refinement under the heuristic prompt is partially counterproductive: the heuristic_py setting shows ∆acc = −0.2 pp (99 instances become first-only and only 89 become final-only), and heuristic_ortools shows the worst % slow rate of any setting (51.9%). When the prompt encourages additional efficiency-oriented machinery, refinement helps least, and on Python it slightly hurts: each refinement round tends to preserve the already-injected heuristic rather than remove it. The same trend manifests in MiniZinc + OR-Tools through Modes E and F (App. G), where the LLM keeps strengthening an already-broken model in successive rounds. Table 5: Refinement effect: first-working artefact versus the final artefact, on a shared instance pool (N ≈4,500). “Speed-up (first/final)” is the per-instance ratio over instances where both artefacts are correct; values > 1 mean the final solver is faster. Preset baseline_py heuristic_py baseline_ortools heuristic_ortools
N accfirst accfinal 4517 4517 4457 4517
0.403 0.431 0.435 0.454
∆acc
e sp
sp % slow
0.418 +1.5 pp 1.03× 0.429 −0.2 pp 1.01× 0.471 +3.5 pp 1.01× 0.468 +1.4 pp 0.99×
1.05× 37.8% 1.33× 45.2% 1.02× 42.9% 0.98× 51.9%
18
D
Correctness at Canonical Time Budgets
Fig. 4 provides a discrete-budget complement to the cumulative runtime curves of Fig. 1: for each LLM and each canonical budget {1, 4, 16, 64, 256} s, it reports the correct ratio across the six (paradigm, prompt) settings. The pattern at every budget mirrors the cumulative curves: Python + OR-Tools dominates, MiniZinc + OR-Tools lags, and the heuristic–baseline relation flips across LLMs. The figure is most useful for cross-referencing the construct- and mode-level discussion of Sec. 5: most per-mode regressions appear in the 4 – 64 s window, where simple solvers have already terminated and harder ones have not yet timed out, and the mid-budget bars surface those regressions more legibly than the tail of the cumulative curve.
Figure 4: Correct ratio at canonical time budgets {1, 4, 16, 64, 256} s, for each LLM (panels) and each (paradigm, prompt) setting (six bars per budget). The pattern at every budget mirrors the cumulative runtime curves of Fig. 1: Python + OR-Tools dominates, MiniZinc + OR-Tools lags, and the heuristic–baseline relation flips across LLMs.
E
Per-Problem Cumulative Runtime Curves
Figs. 5, 6, and 7 report the per-problem cumulative runtime curves for each LLM, with one subplot per benchmark problem and six curves per subplot (3 paradigms × 2 prompts, correct ratio only). The small-multiples view exposes the heterogeneity that the macro cumulative curves of Fig. 1 average over: a non-trivial fraction of problems are solved at correct ratio 1.0 under every setting, while a complementary fraction are solved at correct ratio 0 under every setting; the settings whose macro behaviour we discuss in Sec. 5 therefore differ on the intermediate-difficulty band visible in these per-problem plots. The construct- and mode-conditioning of Sec. B.5 identifies the specific subset of problems on which each (LLM, paradigm) pair regresses; we recommend the per-problem plots primarily as a visual aid when reading those tables. 19
Figure 5: Per-problem cumulative runtime curves (correct ratio) for GPT-5.3-C ODEX, with one subplot per problem and six curves per subplot (3 paradigms × 2 prompts).
20
Figure 6: Per-problem cumulative runtime curves (correct ratio) for D EEP S EEK -V3.2.
21
Figure 7: Per-problem cumulative runtime curves (correct ratio) for G EMINI 3.1 P RO.
F
Anatomy of Baseline Silent Failures: The NL-to-Formal-Language Gap
Sec. 5 explains the differential between heuristic and baseline prompts. It does not explain the silentfailure ranking already visible on the baseline prompt itself: even with no heuristic instruction, every (paradigm, LLM) pair has a non-trivial provided–correct gap, and that gap concentrates differently across paradigms. This appendix dissects the baseline gap mechanistically. The framing is that “provided but wrong” on the baseline prompt is, in essentially every case, a failure at the naturallanguage-to-formal-language boundary rather than a failure of the underlying solver—CP-SAT and the MiniZinc flattener are sound, so any verifier-rejected solution traces to the encoding step. Five mechanisms account for nearly all of the baseline silent failures: four (M1–M4) appear on every paradigm, and a fifth (M5) is unique to Python, where the LLM additionally writes the search procedure. F.1
From Symptom to Cause: Encoding Non-Equivalence
Let Fref (x) denote the reference verifier’s feasible set for an instance x, and Fllm (x) the feasible set of the LLM-generated formal model. The verdict the evaluation pipeline records is determined by the relation between the two sets together with the solver’s choice within Fllm (x). When Fllm (x) ⊊ Fref (x) (over-constraint), the LLM’s optimum is feasible in the reference and the verdict is correct on a CSP, or suboptimal on a COP whenever the over-constraint forecloses the true optimum; if the LLM’s feasible set is empty, the verdict is no solution. When Fllm (x) ̸⊆ Fref (x) (under-constraint or 22
Table 6: Baseline wrong-mass split for the Python + OR-Tools setting, per LLM, on the shared N = 2,565 pool. UNSAT: verifier pins the LLM’s assignment into the reference and the model becomes infeasible. suboptimal: COP solution is feasible in the reference but worse than the optimum. invalid: residual cases. LLM D EEP S EEK -V3.2 GPT-5.3-C ODEX G EMINI 3.1 P RO
Total wrong (frac.)
UNSAT
suboptimal
invalid
469 (18.3%) 214 ( 8.3%) 256 (10.0%)
393 (83.8%) 188 (87.9%) 256 (100.0%)
68 (14.5%) 19 ( 8.9%) 0 ( 0.0%)
8 (1.7%) 7 (3.3%) 0 (0.0%)
mis-encoding), CP-SAT picks an assignment that the verifier rejects when it pins the assignment into the reference model, and the verdict is UNSAT. The empirical signature of the baseline gap is therefore diagnostic: UNSAT dominates whenever encoding is non-equivalent in a direction that lets the LLM’s solver leave the reference’s feasible region; suboptimal dominates whenever encoding is over-constrained but still inside the reference region. For the Python + OR-Tools baseline setting, Tab. 6 reports the wrong-mass split across the three LLMs on the shared N = 2,565 pool: across all three LLMs, ≥ 83.8% of the wrong mass is UNSAT, and the small suboptimal share is essentially all on COPs where the encoding tightens but does not exit the feasible region. The same diagnosis holds on the MiniZinc + OR-Tools baseline setting; only the absolute provided mass differs because the MiniZinc surface causes many instances to drop into no solution before the encoding ever reaches the verifier. F.2
Mechanism Inventory (M1–M4)
The four mechanisms below cover ≈ 90% of the audited UNSAT mass on the Python + OR-Tools baseline setting (top-12 problems, Sec. F.3); they are NL-to-formal-language mechanisms and apply identically on MiniZinc + OR-Tools. M1. Associative recall: the LLM names the problem before it reads it. Frontier LLMs index problems by type before they finish reading the constraint list. “Travelling Purchaser” invokes a TSP template; “Kidney Exchange” invokes max-weight matching; “Mario fuel-bounded path” invokes shortest-path-with-budget. Each retrieval is approximately right but carries idiomatic side-effects (Hamiltonian over all cities, single canonical successor, MTZ ordering) that the actual problem does not require. On problem 63 (TPP), GPT-5.3-C ODEX and D EEP S EEK -V3.2 both reflexively impose a Hamiltonian circuit over every city—two independent LLMs converging on the same template: # GPT -5.3 - Codex , problem 63 ( TPP ) arcs = [( i , j , x [( i , j ) ]) for (i , j ) in x ] model . AddCircuit ( arcs )
The TPP description allows the tour to skip non-purchase locations; the template forecloses that, so any instance whose true optimum visits fewer cities than the cheapest full Hamiltonian becomes infeasible in Fllm . M2. Long-spec attention drift: the LLM encodes most of the constraints, just not all. CP-SynCXL problem descriptions list 4–10 textual constraints, some inline in prose, some in the input/output schema. Faithful encoding requires an explicit clause for each. If the LLM transcribes seven of nine and silently skips two, CP-SAT solves the seven-constraint model to optimality, the verifier checks all nine, and rejects. This structural under-constraint is the single biggest source of UNSAT on problems whose specification runs across multiple paragraphs (Rehearsal, Coin Grid, TSP_TW, Nonogram). The pipeline cannot recover from M2: the LLM’s model is internally consistent, CP-SAT reports OPTIMAL, and there is no failure signal to feed back. M3. Output-schema ambiguity between LLM and verifier. The verifier’s evaluation step pins the LLM’s claimed values into a reference model whose decision-variable schema the LLM has to match exactly. The natural-language description constrains the output schema (keys, types, sizes), but it rarely specifies how those keys are wired into the reference’s variables. The LLM has to guess: should tour include the depot once or twice? Is successors[i]=i the convention for “unmatched”, or a 23
Table 7: Per-problem audit of Python + OR-Tools baseline UNSAT mass. “DS / Cd / Gm” is the per-instance count of UNSAT verdicts on D EEP S EEK -V3.2, GPT-5.3-C ODEX, and G EMINI 3.1 P RO. “Mech.” is the dominant assigned mechanism from Sec. F.2; problem 63 splits 50%/50% between M1 (Hamiltonian template) and M2 (purchase-coupling under-constraint). pid Problem
DS Cd
Gm Mech.
63 60 34 20 66 79 98 72 81 61 97 8
55 37 25 14 56 0 14 44 40 28 0 26
37 36 25 14 0 29 15 0 0 0 0 0
60 35 25 44 13 22 15 0 0 0 27 0
–
– mixed
TPP (Travelling Purchaser) KidneyExchange (max-weight cycles) Coin Grid Rehearsal Problem Amaze (line-pair routing) Mario (fuel-bounded path) Rack Configuration CalvinPuzzle PerfectSquare TSP_TW Blackhole Nonogram
Other 13 small-count problems –
M1+M2 M3 M2 M2 M3 M4 M3 M1 M3 M2 M4 M2
forbidden self-loop? Is model_of_rack[i]=-1 the sentinel for “unused”, or does the verifier expect a missing key? Each plausible-looking guess can either match the reference (correct) or not (UNSAT). Problem 60 (KidneyExchange) is the cleanest example: all three LLMs return successors[v] = v for unmatched pairs, but the reference verifier rejects self-loops as the encoding of “no exchange”. M3 concentrates in problems with explicit “unused / unmatched / placeholder” output semantics. M4. Sentinel-value misreading. Benchmark inputs use sentinel values for “no edge”, “incompatible”, or “infinite cost”—typically −1, 0, or a large positive number. The natural-language description rarely names the convention explicitly, and a wrong reading drops or keeps edges against the spec. GPT-5.3-C ODEX’s baseline Mario solver: # GPT -5.3 - Codex , problem 79 ( Mario ) for i in range ( n ) : for j in range ( n ) : if i != j and fuels [ i ][ j ] > 0: arcs . append (( i , j ) )
# reads 0 as " no edge "
treats fuels[i][j] = 0 as “no edge”, whereas the dataset uses 0 as “edge present, free move”. The LLM has unilaterally banned every free arc; UNSAT on every instance whose true optimum needs one. F.3
Per-Problem Audit and Mechanism Distribution
We manually audited the top twelve problems by aggregated UNSAT mass on the Python + OR-Tools baseline setting—these account for 750 of 837 instances (89.6%) of the wrong mass across all three LLMs (Tab. 7). Aggregating dominant mechanism across the audited 750 instances yields M1 120 (16%), M2 282 (38%), M3 270 (36%), M4 78 (10%); see also the discussion in Sec. 4.4. The audit yields three structural readings. (B1) M2 and M3 jointly account for ∼ 74% of the silent-failure mass, in roughly equal measure; pure problem-template substitution (M1) is real but smaller in isolation (16%), and sentinel misreading (M4) is the smallest (10%). (B2) The same problems fail across all three LLMs: problems 63, 60, 34, 98 fail on every LLM and contribute ≥ 100 wrong instances each. This shared failure pattern is strong evidence that the baseline gap reflects a problem-statement property—ambiguous output schema, long constraint list, an associative-recall trigger—rather than a per-LLM bug. (B3) Refinement cannot fix M2: the LLM’s model is internally consistent, CP-SAT reports OPTIMAL, and no signal flags the missing clause. Sec. C documents that refinement is an error-recovery loop rather than a performance loop; M2 is the formal reason that loop has a hard ceiling on baseline correctness. 24
Table 8: Python baseline wrong-mass split per LLM, on the shared N = 2,565 pool. The UNSAT bucket dominates exactly as on Python + OR-Tools (Tab. 6); the bucket distribution is therefore paradigm-agnostic, and the difference between Python and Python + OR-Tools is the absolute size of the UNSAT bucket. LLM D EEP S EEK -V3.2 GPT-5.3-C ODEX G EMINI 3.1 P RO
F.4
Total wrong (frac.)
UNSAT
suboptimal
invalid
739 (28.8%) 377 (14.7%) 262 (10.2%)
631 (85.4%) 311 (82.5%) 226 (86.3%)
87 (11.8%) 55 (14.6%) 28 (10.7%)
21 (2.8%) 11 (2.9%) 8 (3.1%)
Cross-Paradigm Reading and the Python-Specific Mechanism (M5)
All four mechanisms (M1–M4) are intrinsic to the NL-to-formal-language step, which is paradigmagnostic. MiniZinc + OR-Tools’s declarative semantics catch syntactic and type errors at flatten time, but they do not catch (i) the wrong template applied to the right variables (M1), (ii) a forgotten constraint clause (M2), (iii) an output-schema mismatch between the LLM’s emitted Python output formatter and the verifier’s expected schema (M3), or (iv) the LLM’s reading of an input sentinel (M4). Empirically, MiniZinc + OR-Tools’s conditional wrong rate (wrong|provided) is approximately equal to Python + OR-Tools’s on the strongest LLMs (GPT-5.3-C ODEX baseline: 12.5% MiniZinc vs. 10.6% OR-Tools); the absolute difference is overwhelmingly a translation-fluency effect on MiniZinc + OR-Tools’s no solution bin, not a property of the declarative surface. M5. Search-procedure bugs (Python-only). Python carries M1–M4 plus a fifth mechanism: the LLM writes both the constraint encoding and the search procedure, so wrong mass also includes (i) unsound pruning rules, (ii) off-by-one base cases in DP / DFS, (iii) premature termination of incomplete searches, and (iv) tie-breakers that drop optimal extensions. M5 takes two shapes: M5a (COP local-optimum settle), where an incomplete search returns a feasible but non-optimal assignment that the verifier rejects on optimality (suboptimal); and M5b (junk fallback), where on hitting an internal node / iteration / time budget, the artefact returns a schema-conformant but trivially infeasible assignment (e.g. all squares stacked at the corner) that the verifier rejects on feasibility (UNSAT). Both shapes therefore land in the dominant UNSAT or suboptimal bins of Fig. 3, not in invalid: the verdict bucket alone is not sufficient to separate M5 from M1–M4, and the separation has to be done at the problem and code level. F.5
Python Baseline Audit: How M1–M4 Propagate and Where M5 Dominates
Python’s baseline wrong-mass split per LLM (Tab. 8) shows that UNSAT dominates the wrong mass exactly as on Python + OR-Tools —between 82% and 86% on every LLM. The contrast with Python + OR-Tools is therefore not the bucket distribution but the absolute size of the UNSAT bucket: Python carries 24.6% UNSAT for D EEP S EEK -V3.2 vs. 15.3% on Python + OR-Tools, and the gap shrinks to roughly zero on G EMINI 3.1 P RO (which abstains rather than guesses). To separate the two failure mechanisms, we cross-reference the top Python-baseline failures against the Python + OR-Tools-baseline failures on the same problems. A problem that fails on both paradigms is diagnostic of M1–M4 (the LLM made the same NL-to-formal mistake on both surfaces); a problem that fails only on Python is diagnostic of M5 (the encoding is paradigm-agnostically right, but the hand-rolled algorithm is buggy). Tab. 9 reports the top problems by aggregated wrong mass across all three LLMs. The audit yields two readings. (B4) M1–M4 propagate. The top Python + OR-Tools baseline failures (Tab. 7)—p63, p60, p79, p20, p34—all reappear among the top Python failures with comparable per-LLM counts: the TPP / Hamiltonian template, the KidneyExchange self-loop sentinel, the Mario zero-fuel sentinel, and the Rehearsal long-spec attention drift are paradigm-agnostic. Approximately 170–190 instances of Python wrong mass per LLM are accounted for by these shared problems; the rest is M5. (B5) M5b dominates the Python-only mass. The Python-only failures (problems where Python is wrong but Python + OR-Tools is correct) concentrate on packing / matching / cycle-finding problems whose NL specification is short and unambiguous (so neither M2 nor M3 applies) but whose intrinsic difficulty exceeds the LLM’s hand-rolled search budget. On these problems the LLM consistently emits a node- or iteration-bounded greedy / DFS / DP and falls back to a junk 25
Table 9: Per-problem audit of Python baseline wrong mass. “DS / Cd / Gm” is the per-instance wrong count on D EEP S EEK -V3.2, GPT-5.3-C ODEX, and G EMINI 3.1 P RO. “ORT?” marks problems that also appear in the Python + OR-Tools baseline audit (Tab. 7); these inherit the M1–M4 mechanism. “Mech.” is the dominant assigned mechanism for the Python row: M1–M4 if the same problem fails on Python + OR-Tools (the encoding bug propagates), M5a / M5b if Python-specific. pid Problem
DS Cd Gm ORT?
63 81 60 65 79 20 25 68 82 49 77 98 8
60 60 36 36 10 14 45 26 58 52 48 3 26
TPP PerfectSquare KidneyExchange CyclicBandwidth (COP) Mario Rehearsal Graceful Graphs AntiMagicSquare RoomMate QueensKnights Kakuro Rack Configuration Nonogram
60 60 35 32 40 14 0 38 0 0 0 15 0
54 0 32 15 21 44 19 0 0 0 0 14 5
Mech.
yes (top) M1+M2 no M5b yes (top) M3 partial (DS only) M5a yes M4 yes M2 partial (DS, Gm) M5b partial (Cd) M5b no M5b no M5b no M5b yes M3 yes M2
schema-conformant assignment when the budget runs out (p81 PerfectSquare, p82 RoomMate, p49 QueensKnights, p3 Quasigroup Existence, p77 Kakuro—collectively ∼ 330 M5b instances). M5a (suboptimal) is small in absolute terms (170 total instances) but concentrated on a handful of COPs where the LLM’s incomplete search settles on the first feasible solution, most prominently p65 CyclicBandwidth. Two M5b code patterns typify the failure shape. GPT-5.3-C ODEX’s baseline on p81 (PerfectSquare) caps DFS at a node budget and fabricates a placement when the budget runs out: # GPT -5.3 - Codex , problem 81 ( PerfectSquare , CSP ) -- M5b if n > 34 or size > 90: return { " placements " : [[0 , 0] for _ in range ( n ) ]} node_budget = 200000 if n <= 26 else 90000 # DFS that returns a schema - conformant but infeasible # placement when budget is exhausted .
D EEP S EEK -V3.2’s baseline on p49 (QueensKnights) caps DFS at 100,000 nodes, tries 20 random starts, and on failure literally falls back to a row-major enumeration with the explicit comment “hope for the best”: # DeepSeek - V3 .2 , problem 49 ( QueensKnights , CSP ) -- M5b def dfs ( start , current , visited , path ) : counter [0] += 1 if counter [0] > 100000: return None # ... # After 20 random starts fail : # Create a simple path and hope for the best path = [( i // n , i % n ) for i in range ( min (m , n * n ) ) ]
The pipeline records UNSAT on every instance whose true cycle is not on the row-major path. F.6
Estimated Mechanism Share on the Python Baseline Setting
Combining Tabs. 8 and 9 via cross-paradigm overlap (problems that fail on both Python + OR-Tools and Python attribute their Python wrong mass to M1–M4; problems that fail only on Python attribute their wrong mass to M5) gives the approximate decomposition in Tab. 10. The decomposition refines the design implication: M5 is not a side-channel. On GPT-5.3-C ODEX it accounts for the majority of the Python baseline wrong mass; on D EEP S EEK -V3.2 M1–M4 and M5 are roughly equal contributors; and on G EMINI 3.1 P RO M1–M4 dominate (G EMINI 3.1 P RO is unusually willing to abstain rather than fabricate, which suppresses M5b but not M1–M4). 26
Table 10: Approximate decomposition of Python baseline wrong mass per LLM into M1–M4 (NLto-formal mistakes that also fail on Python + OR-Tools) and M5 (Python-only search-procedure bugs). The M1–M4 share is estimated by intersecting the Python-failing problems with the Python + OR-Tools-failing problems on the same LLM; the residual is treated as M5. LLM D EEP S EEK -V3.2 GPT-5.3-C ODEX G EMINI 3.1 P RO
Python wrong
M1–M4 share
M5 share
739 377 262
∼ 360 (∼ 49%) ∼ 140 (∼ 37%) ∼ 187 (∼ 71%)
∼ 379 (∼ 51%) ∼ 237 (∼ 63%) ∼ 75 (∼ 29%)
The cross-LLM divergence is the same divergence visible in Sec. H: the LLM’s algorithmic taste— specifically, its willingness to defer to verified machinery rather than substitute its own—is the dominant determinant of both the heuristic-prompt safety profile and the baseline silent-failure profile on Python.
G
Heuristic Trap: Detailed Mode Mechanisms and Code Audits
This appendix expands the brief discussion of the six failure modes in Sec. 5.2. The per-(mode, LLM) outcome split is reported as Tab. 2 in Sec. 5.2; here we give one source-level code extract per mode. Each mode is associated with an operational detector—a code-level signature that lets us mark every (LLM, problem) pair as exhibiting the mode or not (full detector definitions in App. G). These detectors are reproducible proxies for recurring code patterns, not formal proofs that the pattern caused every downstream failure. We therefore use them for incidence and conditioning, and validate the mechanistic interpretation through the paired baseline/heuristic diffs and representative manual code audits below. The detectors are intentionally conservative (false-negatives preferred to false-positives), so the incidence numbers should be read as lower bounds on the corresponding pattern families. Mode A (Python + OR-Tools): “tight” bounds the LLM never proves [13.5% overall; D EEP S EEK V3.2 −6.7 pp]. The heuristic prompt explicitly invites the model to “propagate tight objective bounds”. In practice the LLM invents bounds that look plausible but are not theorems. The detector flags any heuristic-prompt Python + OR-Tools solver that introduces a binary-search wrapper on the objective, declares an auxiliary multiplicative variable with a hand-derived domain, or inserts a comment asserting a “dominance” / “valid inequality” / “tight bound” (Tab. 2, row A). In problem 2 (multi-template pressing, COP) under GPT-5.3-C ODEX, the baseline keeps optimisation native; the heuristic version replaces Minimize with a binary search over total pressings P and at each step rebuilds a feasibility model whose auxiliary product variables zk,i = xk,i ·pk are constrained by a hand-derived per-element upper bound: excess = S * P - D zub = max (0 , min ( S * P , d [ i ] + excess ) ) # claimed dominance bound zik = model . NewIntVar (0 , zub , f " z_ { k } _ { i } " ) model . A d d M u l t i p l i c a t i o n E q u a l i t y ( zik , [ x [ k ][ i ] , p [ k ]])
The bound depends on a distributional argument the LLM never states—that no optimal solution over-covers any single variation by more than the global slack—which fails on instances where one variation must absorb most of the slack to keep other rows feasible. The feasibility model becomes infeasible at the true optimum, the binary search overshoots, and correctness drops from 1.00 to 0.43. Mode B (Python + OR-Tools): semantics-preserving rewrites with weaker propagation [4.0% overall; 33% within-mode regression rate]. A second class of regressions arises from rewrites that are mathematically equivalent to the baseline but cripple CP-SAT propagation. The detector triggers when the heuristic-prompt solver newly introduces AddCircuit or a big-M / MTZ encoding that the baseline did not contain. The mode is rare but high-risk: 33.3% of within-mode problems regress and 21.0% of common-correct instances are slower than baseline (Tab. 2, row B). In problem 49 (queens + knight cycle, CSP) the heuristic solver replaces baseline cycle-position variables with a directed circuit over all n2 board cells with self-loops on unselected cells: self_loop = [ k_model . NewBoolVar ( f " self_ { i } " ) for i in range ( N ) ]
27
# N = n*n
arcs = [( i , i , self_loop [ i ]) for i in range ( N ) ] + edge_arcs k_model . Add ( sum ( self_loop ) == N - m ) k_model . AddCircuit ( arcs )
Valid, but with Θ(n2 ) Boolean variables and a global circuit over them: the heuristic version exhausts the 256 s budget at instance 38 where the baseline solves up to 52 in ≤ 14 s. The same pattern appears in problem 79 (Mario fuel-bounded path), where the LLM swaps the idiomatic reified MTZ model.Add(u[j]>=u[i]+1).OnlyEnforceIf(x) for a textbook big-M encoding u[j] ≥ u[i]+1−M (1−x) that is strictly weaker for CP-SAT. Mode C (Python + OR-Tools): hand-computed seeding under the heuristic prompt [19.5% overall; 9–26% per LLM]. The third Python + OR-Tools pattern adds a CP-SAT hand-computed candidate before invoking the solver. The safe version is advisory warm-starting (AddHint); the risky version turns the same candidate into hard equalities (model.Add(... == k)). We group them because both originate from the same LLM behavior—constructing a separate greedy or domainspecific candidate and feeding it to CP-SAT—but we separate their implications in the interpretation: hints can slow search but do not change the feasible set, while hard fixes can remove feasible or optimal assignments if the candidate is wrong. The candidate may be produced by a named helper (def warnsdorff / def greedy / def construct_*) or by an inlined “initial_*” computation inside solve_instance. We flag the mode whenever such a seeding mechanism appears in the heuristic preset and is absent from the baseline. Under this behavioural detector the mode is the most popular Python + OR-Tools heuristic intervention in our audit (26.3% of GPT-5.3-C ODEX, 9.1% of G EMINI 3.1 P RO, 23.2% of D EEP S EEK -V3.2; Tab. 2, row C); the within-mode mean correctness change is mildly positive on every LLM (+0.009 to +0.061) and the median per-problem speed-up sits at 0.96–1.02×. This near-neutral aggregate is mostly explained by advisory hints; the correctness risk concentrates in the smaller subset where the seed is enforced as a hard constraint. The two extremes of within-mode behaviour come from whether the hand-coded candidate is sound for the problem class and whether CP-SAT is allowed to ignore it. In problem 40 (closed knight’s tour, CSP) GPT-5.3-C ODEX implements Warnsdorff’s rule with multi-restart, then constrains every CP-SAT arc to follow the discovered cycle: def h eu ri s ti c _c yc l e () : for attempt in range ( max_attempts ) : # ... Warnsdorff : pick next vertex with min remaining degree ... return path # full closed tour cycle_path = h e ur is t ic _ cy cl e () fixed_next = { cycle_path [ i ]: cycle_path [( i +1) % N ] for i in range ( N ) } model . AddCircuit ( arcs ) for u in range ( N ) : # hard equality model . Add ( arc_var [( u , fixed_next [ u ]) ] == 1)
Here the discovered tour is a valid witness, so the hard equality is safe on instances where the helper succeeds and accuracy jumps from 0.067 to 0.567. The opposite case appears when the LLM seeds with a suboptimal greedy guess but uses only a soft hint: the hint can anchor search around a worse region of the polytope, yet correctness survives because CP-SAT continues exploring beyond the seed. This is why the within-mode mean ∆ acc stays near zero even when individual seeds are unhelpful. The D EEP S EEK -V3.2 mode-incidence in particular is dominated by inlined warm-starts (no def factor-out), confirming that the original named-helper signature was Codex-idiomatic rather than mechanism-defining. Mode D (Python): silent loss of completeness [16.2% overall; D EEP S EEK -V3.2 23.2% incidence with −3.7 pp expected]. On Python the LLM is responsible for the entire algorithm, and the heuristic prompt induces it to substitute a complete search procedure for an incomplete one without flagging the loss. The detector triggers on any heuristic-prompt Python solver that introduces local-search / simulated-annealing / multi-restart / iteration-cap machinery while the baseline either contained a complete-search construct (lru_cache / permutations / DP table) that was dropped or did not contain those incomplete constructs in the first place (i.e. they were added by the heuristic prompt). The mode is moderately common (16.2% overall) and exhibits clear LLM-conditioning: 28
GPT-5.3-C ODEX stays mildly positive (+1.8 pp), G EMINI 3.1 P RO positive (+5.5 pp), D EEP S EEK V3.2 regresses by 3.7 pp on average with 21.7% of within-mode problems regressing (Tab. 2, row D). The clearest case is problem 68 (anti-magic square) under GPT-5.3-C ODEX: the baseline keeps an exhaustive permutation branch for the small case alongside a uniform stochastic local search: # baseline ( Python ) if n == 3: for p in permutations ( nums ) : # complete on n <= 3 if is_valid ( compute_sums ( p ) ) : return { " grid " : to_grid ( list ( p ) ) } # else : SA with uniform random swap , return best_arr
The heuristic version drops the exhaustive branch entirely and replaces the uniform random swap with a biased move generator that concentrates 85% of moves on cells participating in “bad” lines— duplicate or extreme line-sums—so as to converge faster: # heuristic ( Python ) bad_lines = [ ln for ln , x in enumerate ( ls ) if freq [ x ] > 1] if mx - mn + 1 > m : bad_lines += [ ln for ln , x in enumerate ( ls ) if x in ( mn , mx ) ] bad_cells = [ p for ln in bad_lines for p in line_cells [ ln ]] # inside the move loop : i = bad_cells [ rng . randrange ( len ( bad_cells ) ) ] if bad_cells and rng . random () < 0.85 \ else rng . randrange ( N )
The biased generator descends to a local optimum faster, but it can also keep the search there: correctness drops from 0.826 to 0.087, the largest single-problem regression in our entire benchmark. Globally, memoisation usage drops from GPT-5.3-C ODEX’s 6 to 2 files under the heuristic prompt and multi-restart usage appears from 0 to 5 files (Tab. 3). The pattern is amplified in D EEP S EEK V3.2: 18.2% of problems use multi-restart and 37.4% use randomised choice—the within-pattern regression rate of iteration-cap truncation reaches 41.7% (Tab. 4). Mode E (MiniZinc + OR-Tools): COP→SAT collapse via assumed optimum [0.7% overall; expected −33.4 pp]. Specific to MiniZinc + OR-Tools, the heuristic prompt occasionally elicits a hidden optimization-to-satisfaction substitution: the LLM assumes the optimum equals a known lower bound supplied as input and removes the objective. The detector triggers when the baseline used solve minimize / maximize but the heuristic version uses solve satisfy, or when the heuristic declares var X..X: v (a single-value domain bound to an input parameter). The mode is rare overall (2 of 98 GPT-5.3-C ODEX problems, none of G EMINI 3.1 P RO’s or D EEP S EEK -V3.2’s match the strict signature) but its expected effect within the mode is −33.4 pp—the largest mean regression of any mode (Tab. 2, row E). Problem 14 (bus-driver shift selection, min #shifts) under GPT-5.3-C ODEX illustrates the failure. The baseline keeps the COP intact: var min_nu m_shif ts .. num_shifts : total_shifts ; constraint total_shifts = sum ( s in SHIFTS ) ( x [ s ]) ; solve minimize total_shifts ;
The heuristic version’s final refinement freezes total_shifts to the data-supplied lower bound and discards the objective: % " Known optimal cardinality : turn optimization into satisfaction " var min_nu m_shif ts .. min_nu m_shif ts : total_shifts ; constraint total_shifts = mi n_num_ shifts ; constraint sum ( s in SHIFTS ) ( x [ s ]) = total_shifts ; solve :: int_search (x , first_fail , indomain_max , complete ) satisfy ;
min_num_shifts is the input’s lower bound, not the proven minimum: when the bound is not tight (most instances) the SAT problem is infeasible and the evaluation pipeline records UNSAT. Accuracy 0.75 → 0.083. Mode E is rare in absolute terms but has the largest within-mode mean regression in our audit; it is concentrated in COPs whose lower bound is a problem parameter the LLM can mistake for an optimum. 29
Mode F (MiniZinc + OR-Tools): redundant-machinery blow-ups [29.1% overall; the empirical kernel of MiniZinc + OR-Tools’s bimodal outcome]. A complementary MiniZinc + OR-Tools failure is symmetric to Python + OR-Tools Mode B but operates at the model level: the LLM augments a clean model with voluminous “stronger” machinery and the resulting model can either help propagation or overwhelm flattening. The detector triggers when (a) the heuristic file is at least 1.5× the baseline file’s line count and introduces direction-tagged auxiliary arrays (pred_up/down/left/right), distance fields, or “redundant”/“implied” commentary, or (b) when two of those auxiliary signatures co-occur. Mode F is by far the most common mode in our benchmark—incidence 29.1% overall, 39.8% for GPT-5.3-C ODEX, 37.5% for D EEP S EEK -V3.2 (Tab. 2, row F) —and it is the empirical kernel of MiniZinc + OR-Tools’s bimodal outcome: median speed-up 1.08–1.17×, 25% of within-mode problems improve by ≥ 5 pp, and 22.5% regress by ≥ 5 pp. The mode therefore accounts for both the genuine MiniZinc + OR-Tools speed-ups and the heaviest tail of MiniZinc + OR-Tools regressions. Problem 66 (Numberlink, CSP) under GPT-5.3-C ODEX grows from a 40-line baseline to a 156-line heuristic version. The injected machinery is a per-path distance field plus four direction-specific predecessor booleans plus a checkerboard parity invariant: % added by the array [P , R , C ] path array [P , R , C ] array [P , R , C ] array [P , R , C ] array [P , R , C ]
heuristic prompt : O (| P |. R . C ) auxiliaries of var 0.. N : d ; % distance from source per of of of of
var var var var
bool : bool : bool : bool :
pred_up ; pred_down ; pred_left ; pred_right ;
% " Useful implied constraints " -- in fact a Manhattan - distance lower bound constraint forall ( p in P ) ( d [p , tr [ p ] , tc [ p ]] >= abs ( tr [ p ] - sr [ p ]) + abs ( tc [ p ] - sc [ p ]) + 1 ); % Checkerboard parity ( claimed redundant , actually heavy to flatten ) constraint forall ( p in P , r in R , c in C ) ( x [p ,r , c ] -> ( d [p ,r , c ] mod 2 = parity [p ,r , c ]) );
Each comment annotates the construction as “useful implied constraint” or “stronger propagation”, but the flattened model is too large for CP-SAT to load within the 256 s budget on 4 of 6 instances. Accuracy drops 1.00 → 0.00, the worst MiniZinc + OR-Tools regression for GPT-5.3-C ODEX. The same syntactic pattern—adding direction-tagged auxiliary arrays and “parity” constraints to a working channelling model—also drives the regressions on problems 44 and 62. Mode-detector definitions (operational, reproducible). For completeness we record the exact signatures used to classify each heuristic-prompt solver into the modes of Tab. 2. A solver is flagged for a mode if any disjunct in the corresponding clause is satisfied. The signatures are designed for reproducibility and high precision, not exhaustive recall: they identify visible instances of each pattern family, after which the regression analysis compares the marked heuristic solver to its paired baseline on the same problem and LLM. The code examples above illustrate the manual audit used to interpret the flagged families; unflagged solvers may still contain related mistakes in forms the detectors do not cover. • Mode A (Python + OR-Tools): heuristic source contains any of (i) a # comment matching the regex (dominance|tight_bound|tightening|valid_inequality |upper_bound|lower_bound|implied_bound), (ii) a binary-search-on-objective wrapper of the form lo, hi = ...; while lo < hi: ..., or (iii) a newly introduced AddMultiplicationEquality (absent in the baseline). • Mode B (Python + OR-Tools): heuristic source newly contains AddCircuit or a big-M pattern (regex −M\s∗\∗\s∗\(\s∗1\s∗− or the keyword MTZ) absent from the baseline. • Mode C (Python + OR-Tools): heuristic source contains an AddHint or a hard equality of a CP-SAT variable to a constant that is tied to a hand-computed candidate, AND either (i) a Python helper named greedy, warnsdorff, nearest_neighbour, construct_*, heuristic_*, etc., or (ii) the same seeding mechanism is absent from the baseline. We record whether the seed is advisory (AddHint) or enforced (hard equality) for interpretation; the table groups them because both are generated by the same candidate-construction 30
behavior. Clause (ii) captures inlined warm-starts where the LLM emits the heuristic directly inside solve_instance rather than factoring it into a separately named helper. • Mode D (Python): heuristic source contains a local-search / SA / multi-restart / iteration-cap construct, AND either the baseline contained a complete-search construct (lru_cache / permutations / DP table) that has been dropped, OR the baseline did not contain those incomplete-search constructs in the first place. • Mode E (MiniZinc + OR-Tools): the baseline used solve minimize or solve maximize but the heuristic uses solve satisfy, OR the heuristic declares var X..X: v (singlevalue domain bound to a parameter). • Mode F (MiniZinc + OR-Tools): heuristic file is at least 1.5× the baseline file’s line count AND introduces a direction-tagged auxiliary array (pred_up/down/left/right or similar), or a distance field, or a comment marked “redundant” / “implied” / “stronger propagation” / “channelling” / “prefix sum”; OR two of those auxiliary signatures co-occur regardless of size. The full detector script is released with the benchmark (analyze_failure_modes.py); the perproblem mode labels are in per_problem_modes.csv alongside every accuracy and runtime measurement.
H
Model-Specific Heuristic Choices and Safety
The aggregate picture of Sec. 5.1 shows D EEP S EEK -V3.2 as the clearest victim of the heuristic trap; the per-pattern data of Tab. 4 explain which mistakes drive its loss. On Python + OR-Tools every one of D EEP S EEK -V3.2’s heavily-used constructs has a within-pattern regression rate between 26% and 35%: AddDecisionStrategy (35%), OnlyEnforceIf (31%), num_search_workers (27%), symmetry-breaking (27%), variable-fixing (30%). The constructs themselves are correct; D EEP S EEK V3.2’s choice of scope for them is not—it pins variables to incorrect values, asserts symmetries that break the constraint structure, and imposes value orderings that foreclose feasibility. On MiniZinc + OR-Tools the same diagnosis holds: first_fail regresses on 25% of D EEP S EEK -V3.2’s solvers because the chosen variable scope contains channelling auxiliaries whose first_fail ordering forecloses the model. Crucially, 32.0% of redundant constraints in D EEP S EEK -V3.2’s MiniZinc + OR-Tools heuristic preset are themselves correctness-breaking (Tab. 4): the LLM fails to verify that “redundant” is, in fact, an implication. G EMINI 3.1 P RO sits at the threshold. Its Python heuristics gain +2.2 pp—driven mostly by stronger DFS skeletons and randomised restarts that happen to suit the problems for which G EMINI 3.1 P RO has weaker default code paths—while its Python + OR-Tools and MiniZinc + OR-Tools heuristics lose 0.6–1.1 pp through localised over-specification (e.g. global_lex regresses on 36% of the problems where it is used). GPT-5.3-C ODEX is the only LLM whose heuristic prompt is net positive on every paradigm, and its safety profile is largely explained by one behavioral tendency: when in doubt, GPT-5.3-C ODEX prefers a native solver hook (AddDecisionStrategy, first_fail, all_different, circuit) over a hand-rolled algorithmic substitution. On MiniZinc + OR-Tools circuit alone delivers a 5.54× median speed-up with zero regressions; all_different delivers 1.40× with +7.8 pp. The trap is therefore not explained by model strength alone: in this benchmark, an important determinant of whether the heuristic prompt is safe is whether the model expresses the optimization request through verified solver machinery or through an unverified algorithmic substitution.
31