跳转至

文章背景与核心概要

组合调度问题对语言模型而言是一大巨大挑战，因为它们需要在处理呈指数级增长的搜索空间的同时，兼顾严格且复杂的约束条件。在资源受限的环境中，部署庞大的前沿模型往往不切实际，而较小的模型在直接根据自然语言文本进行调度时，经常难以保持方案的可行性，这一问题显得尤为突出。

为了克服这些局限性，作者引入了一种新颖的神经符号框架 SDDL。SDDL 没有要求语言模型直接生成解决方案或原始求解器代码，而是将自然语言调度问题转化为任务、资源、约束和目标的紧凑且与求解器对齐的表示形式。随后，它将底层建模和搜索过程委托给确定性编译器和外部求解器。

通过形式化抽象提升资源受限语言模型中的自然语言组合优化准确率

作者： Shrenil Shaun Sharma, Avi Sharma
提交于： 2026年8月19日
主要学科： 人工智能 (cs.AI)
arXiv: 2608.18409 [cs.AI]
DOI: 10.48550/arXiv.2608.18409

Improving Natural-Language Combinatorial-Optimization Accuracy in Resource-Constrained Language Models via Formal Abstractions

Authors: Shrenil Shaun Sharma, Avi Sharma
Submitted on: 19 August 2026
Primary Subject: Artificial Intelligence (cs.AI)
arXiv: 2608.18409 [cs.AI]
DOI: 10.48550/arXiv.2608.18409

摘要

组合调度问题给语言模型带来了巨大的障碍，因为它们需要在遍历指数级巨大搜索空间的同时平衡严格而复杂的约束。这个问题在资源受限的环境中尤为关键，因为部署庞大的前沿模型是不切实际的，并且较小的模型在直接从自然语言文本进行调度时经常难以保持可行性。

为了克服这些局限性，作者引入了 SDDL，这是一个新颖的神经符号框架。SDDL 没有要求语言模型直接生成解决方案或原始求解器代码，而是将自然语言调度问题转化为任务、资源、约束和目标的紧凑且与求解器对齐的表示形式。然后，它将底层建模和搜索过程委托给确定性编译器和外部求解器。

核心结果

  • 提升可行性： 在包含 300 个实例、多系列的挑战性调度问题子集上，SDDL 提高了所测试的每个资源受限模型中经独立验证的可行性。
  • 性能增益： 两个最强的 SDDL 配置实现了 55.3% 和 28.3% 的可行性，相较于直接生成基线（23.7% 和 1.3%）以及求解器代码基线（21.7% 和 7.0%）有了显著的提升。
  • 最优性： 在所有可行调度中，SDDL 实现了 0.0% 的中位数最优性鸿沟 (optimality gap)。
  • 以小博大： 通过专注于问题结构而非直接生成解决方案，SDDL 使较小的模型能够接近甚至偶尔匹敌更大、资源密集得多的前沿模型的性能。

Summary

Combinatorial scheduling problems present significant hurdles for language models, as they require navigating exponentially large search spaces while balancing strict, complex constraints. This issue is particularly critical in resource-constrained environments where deploying massive frontier models is impractical, and smaller models frequently struggle to maintain feasibility when scheduling directly from natural language text.

To overcome these limitations, the authors introduce SDDL, a novel neuro-symbolic framework. Instead of asking language models to generate solutions or raw solver code directly, SDDL translates natural-language scheduling problems into compact, solver-aligned representations of tasks, resources, constraints, and objectives. It then delegates the low-level modeling and search processes to a deterministic compiler and external solver.

Key Results

  • Improved Feasibility: On a challenging 300-instance, multi-family subset of scheduling problems, SDDL improved independently verified feasibility across every resource-constrained model tested.
  • Performance Gains: The two strongest SDDL configurations achieved 55.3% and 28.3% feasibility, a dramatic improvement over direct-generation baselines (23.7% and 1.3%) and solver-code baselines (21.7% and 7.0%).
  • Optimality: SDDL achieved a 0.0% median optimality gap among all feasible schedules.
  • Punching Above Weight Class: By focusing on problem structure rather than direct solution generation, SDDL empowers smaller models to approach—and occasionally rival—the performance of much larger, resource-heavy frontier models.

文档详情

Document Details

外部资源与参考文献

External Resources & References