小模型也能精准解复杂调度问题,靠的是把自然语言转成机器可解的结构化任务。
Improving Natural-Language Combinatorial-Optimization Accuracy in Resource-Constrained Language Models via Formal Abstractions
- 将自然语言调度问题转化为紧凑的符号化表示,交由外部求解器处理。
- 在300个实例上,小模型可行性提升至55.3%(原仅23.7%),最优性差距为0%。
- 适合资源受限场景,让小型模型逼近大模型和专业求解器表现。
组合调度对语言模型构成重大挑战,需在指数级搜索空间中找到满足复杂约束的可行解。这一挑战在资源受限环境下尤为突出,因大模型不可用,小模型直接从自然语言生成方案常丧失可行性。为此,我们提出SDDL——一种神经符号框架,将自然语言调度问题转换为紧凑、与求解器对齐的任务、资源、约束和目标表示,并将低层建模与搜索交给确定性编译器与外部求解器。在包含300个实例的多族调度子集上,SDDL显著提升所有资源受限模型的独立验证可行性。两种最优SDDL配置分别达到55.3%和28.3%的可行性,远超直接生成基线(23.7%和1.3%)与求解器代码基线(21.7%和7.0%),且可行解的中位最优性差距为0%。通过表达问题结构而非生成解或求解器代码,SDDL使小模型接近最强评估的直接生成与求解器代码配置,包括显著更大的前沿模型。
原文摘要 · Abstract (English)
Combinatorial scheduling poses a significant challenge for language models, requiring them to identify feasible solutions within exponentially large search spaces while satisfying complex constraints. This challenge is especially pronounced in resource-constrained settings, where larger language models are impractical and selection is limited to smaller models which often fail to preserve feasibility when scheduling directly from natural language. To address these limitations, we introduce SDDL, a neuro-symbolic framework that translates natural-language scheduling problems into compact, solver-aligned representations of tasks, resources, constraints, and objectives, while delegating low-level modeling and search to a deterministic compiler and external solver. On a 300-instance, multi-family subset of scheduling problems, SDDL improves independently verified feasibility for every resource-constrained model tested. The two strongest SDDL configurations reach 55.3% and 28.3%, up from direct-generation baselines of 23.7% and 1.3% and solver-code baselines of 21.7% and 7.0%, with a 0.0% median optimality gap among feasible schedules. By expressing problem structure rather than generating solutions or solver code, SDDL enables smaller models to approach the strongest evaluated direct- and solver-code configurations, including substantially larger frontier models.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。