LLM生成组合求解器时，优化搜索反而降低正确率，应优先形式化约束而非优化策略。
Formalize, Don't Optimize: The Heuristic Trap in LLM-Generated Combinatorial Solvers
- 用声明式建模让LLM专注形式化变量与约束，避免自行设计搜索算法。
- 提示优化搜索仅带来1.03-1.12倍加速，但多数问题变慢且正确率骤降。
- 适合需要高可靠性的自动化求解场景，如工业调度或验证系统。
大型语言模型（LLMs）在直接推理复杂组合问题上表现不佳，因此近年神经符号系统越来越多地利用它们生成可执行的求解器。核心设计问题是：如何表示求解器，以及是否应让模型同时优化搜索过程。本文提出CP-SynC-XL基准，包含100个组合问题（共4,577个实例），评估三种构建范式：原生算法搜索（Python）、通过Python求解器接口的约束建模（Python + OR-Tools），以及声明式约束建模（MiniZinc + OR-Tools）。结果发现显著的表示差异：Python + OR-Tools在各类LLM中达到最高正确率，而尽管使用相同OR-Tools后端，MiniZinc + OR-Tools的绝对覆盖率较低。原生Python最易生成语法合法但验证失败的解，而基于求解器的路径保持更高条件保真度。在启发式优化方面，提示优化搜索仅带来1.03–1.12倍的中位加速，且效果呈强双峰分布：大量实例变慢，长尾问题的正确率大幅下降。代码级审计揭示了反复出现的启发式陷阱——在效率导向提示下，LLM可能以局部近似替代完整搜索（Python），注入未经验证的界值（Python + OR-Tools），或添加冗余的声明式结构，过度约束或压垮模型。这些发现支持一种保守设计原则：将LLM主要用于为可信求解器形式化变量、约束和目标，任何由LLM编写的搜索优化必须单独验证后方可使用。
原文摘要 · Abstract (English)
Large Language Models (LLMs) struggle to solve complex combinatorial problems through direct reasoning, so recent neuro-symbolic systems increasingly use them to synthesize executable solvers. A central design question is how the LLM should represent the solver, and whether it should also attempt to optimize search. We introduce CP-SynC-XL, a benchmark of 100 combinatorial problems (4,577 instances), and evaluate three solver-construction paradigms: native algorithmic search (Python), constraint modeling through a Python solver API (Python + OR-Tools), and declarative constraint modeling (MiniZinc + OR-Tools). We find a consistent representational divergence: Python + OR-Tools attains the highest correctness across LLMs, while MiniZinc + OR-Tools has lower absolute coverage despite using the same OR-Tools back-end. Native Python is the most likely to return a schema-valid solution that fails verification, whereas solver-backed paths preserve higher conditional fidelity. On the heuristic axis, prompting for search optimization yields only small median speed-ups (1.03-1.12x) and a strongly bimodal effect: many instances slow down, and correctness drops sharply on a long tail of problems. A paired code-level audit traces these regressions to a recurring heuristic trap. Under an efficiency-oriented prompt, the LLM may replace complete search with local approximations (Python), inject unverified bounds (Python + OR-Tools), or add redundant declarative machinery that overwhelms or over-constrains the model (MiniZinc + OR-Tools). These findings support a conservative design principle for LLM-generated combinatorial solvers: use the LLM primarily to formalize variables, constraints, and objectives for verified solvers, and separately check any LLM-authored search optimization before use.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。