通过形式化抽象改进资源受限语言模型中的自然语言组合优化精度

# 通过形式化抽象提升资源受限语言模型的自然语言组合优化精度  
来源：https://arxiv.org/html/2608.18409  
Shrenil Shaun Sharma  
所属机构：独立研究员  
所属机构：美国加利福尼亚州旧金山  
邮箱：[[email protected]](mailto:[email protected])  

Avi Sharma  
所属机构：电气工程与计算机科学系  
所属机构：加州大学伯克利分校  
邮箱：[email protected]  

###### 摘要  
组合调度对语言模型提出了重大挑战，要求其在指数级搜索空间中识别可行解，同时满足复杂约束。这一挑战在资源受限环境中尤为突出，因为较大的语言模型不切实际，只能选择较小的模型，而这些模型在直接从自然语言进行调度时往往无法保证可行性。为解决这些局限性，我们引入SDDL——一种神经符号框架，可将自然语言调度问题转化为任务、资源、约束和目标的紧凑、求解器对齐的表示，同时将底层建模和搜索委托给确定性编译器及外部求解器。在包含300个实例的多族调度问题子集上，SDDL提升了所有测试的资源受限模型的独立验证可行性。两个最强的SDDL配置分别达到55.3%和28.3%的可行性，相较于直接生成基线（23.7%和1.3%）和求解器代码基线（21.7%和7.0%）显著提升，且可行调度的中位最优性差距为0.0%。通过表达问题结构而非生成解或求解器代码，SDDL使较小模型能够接近评估中最强的直接生成和求解器代码配置，包括规模大得多的前沿模型。  

## 1 引言  
许多对现代语言模型的请求以自然语言提出，包括解决方案依赖于底层数学结构的问题。在此类情况下，约束、目标和过程可能仅隐式指定，要求模型推断所描述的数学问题。对于体现优化问题的任务，这种推断不仅是语义的：模型必须将口头描述转化为可能解的潜在搜索空间，并根据隐式的可行性和最优性标准评估候选解。这一挑战在资源受限环境中尤为突出，因为模型选择仅限于参数远少于大型可用替代方案的语言模型。生成解需要解析任务描述、跟踪交互约束、推理目标，并在单次自回归过程中隐式搜索替代方案。对于较小模型，此过程通常产生流畅但不可行的解。神经符号分解可能通过将语言理解与下游计算分离来缓解此局限性：语言模型生成可执行或形式表示，而外部运行时或求解器执行相应计算（5（https://arxiv.org/html/2608.18409#bib.bib1）；13（https://arxiv.org/html/2608.18409#bib.bib4））。在优化专用系统中，这种形式化可能包括决策变量、约束和目标（14（https://arxiv.org/html/2608.18409#bib.bib5）；3（https://arxiv.org/html/2608.18409#bib.bib6）；16（https://arxiv.org/html/2608.18409#bib.bib8））。然而，这种方法将瓶颈转移到了翻译保真度上。求解器仅优化接收到的形式化，因此遗漏的约束、错误定义的变量或扭曲的目标直接破坏最终解。组合优化问题尤其凸显了这一弱点，与小型决策问题或线索式逻辑谜题不同，实例必须大规模表示目标、资源容量、时间关系、优先级约束和析取替代方案。我们发现，资源受限模型直接生成求解器代码通常作为形式化策略失败，产生可能可执行且求解器可行但不符合预期问题的程序。为弥合这一差距，我们引入了SDDL（调度领域定义语言），这是一种领域特定语言，将翻译目标从开放式的求解器代码缩小到一组求解器对齐的调度原语。SDDL不要求模型生成底层求解器代码，而是为任务、资源、约束、替代方案和目标提供调度原生抽象，其中SDDL程序被确定性编译为求解器模型以供外部求解器执行。在13个模型中，我们比较了直接和通用求解器代码生成，并在多个资源受限模型上评估了SDDL。SDDL提升了所有测试模型的独立验证可行性，同时降低了可行调度的中位最优性差距。其最强结果在整体评估中排名靠前，而其他结果则提升至基线的数倍，证明了SDDL相对于直接和通用求解器代码生成的有效性，并使较小模型能够匹配更强配置。我们的贡献包括：1. SDDL（调度领域定义语言）一种用于可执行、承载目标的组合调度公式的领域特定语言，相对于直接求解器代码生成，提升了资源受限LLM形式化的保真度。2. 对SDDL在概念范围和求解器目标匹配的生成策略上进行独立验证评估。3. 评估显示SDDL使规模小得多的模型能够匹配或紧密接近评估中最强的直接生成和求解器代码配置的性能，包括使用规模大得多的前沿模型的配置。  

## 2 相关工作  
### 2.1 结构化形式推理  
诸如PlanBench之类的实证评估记录了系统化多步规划中的显著弱点（18（https://arxiv.org/html/2608.18409#bib.bib17）），而9（https://arxiv.org/html/2608.18409#bib.bib18）认为LLMs最好被整合到将规划委托给外部模块的框架中。在受限生成任务上的性能在不同模型规模之间差异显著，较小的资源受限模型比包括零样本提示下的大型模型实现更低的约束满足率（19（https://arxiv.org/html/2608.18409#bib.bib19））。这种差距可能因严格的输出格式要求而加剧，这已被证明会降低推理密集型任务的性能（17（https://arxiv.org/html/2608.18409#bib.bib16））。这种形式化之一出现在组合调度问题中，模型必须同时恢复问题语义、尊重表示约定，并在相互依赖的决策和时间关系中保持约束保真度。这些发现共同表明，保留推理能力可能取决于减少模型必须形式化和计算的内容，从而推动将执行委托给外部工具的方法。  

### 2.2 求解器委托约束推理  
神经符号框架利用LLMs将非结构化文本解析为可执行表示，将计算委托给外部运行时以绕过内部算术和逻辑错误（5（https://arxiv.org/html/2608.18409#bib.bib1）；4（https://arxiv.org/html/2608.18409#bib.bib3））。Logic-LM将此方法扩展到符号推理，将自然语言问题转化为形式逻辑，并使用求解器反馈迭代修复无效表示（13（https://arxiv.org/html/2608.18409#bib.bib4））。这些结果表明，LLMs可以通过构建可执行或符号表示，同时将确定性计算和推理委托给外部工具而受益。NL4Opt（14（https://arxiv.org/html/2608.18409#bib.bib5））、OptiMUS（3（https://arxiv.org/html/2608.18409#bib.bib6））和ConstraintLLM（16（https://arxiv.org/html/2608.18409#bib.bib8））在不同抽象层次上将此范式应用于优化和约束规划。然而，OptiMUS和ConstraintLLM针对高度表达的通用编程环境，其中形式化可能需要冗长的变量声明、底层求解器API调用，以及在翻译底层问题语义之上的显式控制流；这种通用性可能以可靠的生成为代价。  

### 2.3 无求解器生成和解码  
替代方法将LLMs评估为直接端到端组合求解器（8（https://arxiv.org/html/2608.18409#bib.bib9））。在此类端到端生成上下文中，评估显示解的质量和可行性随实例规模和结构复杂度增加而降低（8（https://arxiv.org/html/2608.18409#bib.bib9））。另外，结构化解码方法约束了生成过程本身：语法感知解析（20（https://arxiv.org/html/2608.18409#bib.bib10））和语法约束解码（6（https://arxiv.org/html/2608.18409#bib.bib11））在令牌级别强制结构有效性。然而，硬格式约束可能降低底层推理性能（17（https://arxiv.org/html/2608.18409#bib.bib16）），且语法有效的表示仍可能遗漏关键约束或传递错误值。因此，SDDL在解析时拒绝格式错误的程序，并对照源实例验证发出的调度，确保不将句法有效性单独视为正确性的证据。  

### 2.4 LLMs用于组合调度  
虽然上述范式解决了通用约束满足，但针对调度原生问题结构的文献仍然有限且分散。现有调度应用通过作业车间领域的监督微调模仿无求解器范式（2（https://arxiv.org/html/2608.18409#bib.bib12））。此类方法将问题解释和组合搜索折叠到单个生成步骤中，使得难以将不可行调度中的错误归因于约束翻译错误而非搜索失败。相反，与调度相关的通用CP系统（12（https://arxiv.org/html/2608.18409#bib.bib7）；16（https://arxiv.org/html/2608.18409#bib.bib8））继承了通用求解器API的重形式化开销，并非旨在利用跨越调度族的重复结构模式（优先级、资源容量、覆盖要求、惩罚软约束）。最接近我们情况的是Logic.py（10（https://arxiv.org/html/2608.18409#bib.bib20）），它通过用于约束求解的DSL形式化基于搜索的问题，主要在逻辑网格谜题上进行评估。其评估系统专注于寻找满足赋值，而非在可行调度上优化目标。  

### 2.5 自然语言调度基准  
特定于调度的自然语言基准仍然有限。Starjob（1（https://arxiv.org/html/2608.18409#bib.bib13））提供了用于端到端JSSP调度的大型监督语料库，但通过固定模板将其实例语言化。R-ConstraintBench（7（https://arxiv.org/html/2608.18409#bib.bib15））使用类似结构化的字段式描述，在系统化变化的约束下评估RCPSP可行性。NL⇒Schedule（11（https://arxiv.org/html/2608.18409#bib.bib14））通过跨四个领域的真实材料构建的半合成实例提供更完整的自然语言描述。NLCO（8（https://arxiv.org/html/2608.18409#bib.bib9））涵盖了调度之外更广泛的组合优化族，并仅提供最小语言化的实例。由于我们的评估强调形式化，我们优先使用具有明确描述和规范源实例的基准，使生成的调度能够直接对照形式化真实值进行验证。SCHEDBench（15（https://arxiv.org/html/2608.18409#bib.bib2））通过构造为此要求提供了最佳保证，其中每个描述都是对来自已建立调度文献的规范源实例进行的受控、约束保留的语言化；提供明确的形式化真实值和最佳已知目标以验证生成的调度。  

## 3 方法与DSL创建  
SDDL的设计基于一个观察：自动化形式化不仅容易在理解问题时崩溃，而且在实现该理解所需的有效决策上也容易失败（16（https://arxiv.org/html/2608.18409#bib.bib8））。SDDL通过仅命名模型需要识别的重复调度结构，移除了本应由模型承担的、易于出错的建模决策，同时确定性编译器处理其下游编码。我们首先阐述这一立场的基本原理，然后开发实现这些原理的接口及其提供的编译保证。  
JSSP实例，10作业×5机器规则（节选）。项目内的步骤遵循给定顺序；一个位置一次最多处理一个步骤；不可抢占。设置。5个机组站上的10个场景。每个场景是一个有序步骤序列；每个步骤命名一个站点和持续时间。场景Franklin有一个5步序列。步骤1在North Sound Stage进行12小时；步骤2在Second Unit Screening Room进行94小时... [+ 9个其他场景]响应格式：步骤k: start=，每行一个。  
图1：以自然语言呈现的示例调度问题；模型必须恢复底层结构并为每个步骤发出开始时间。  
### 3.1 调度问题  
调度问题要求将活动分配到特定时间和资源分配，以产生满足一组约束并优化目标的可行调度。尽管形式多样，其约束结构来源于几个重复关系：活动间的优先级、一次处理一个活动的析取资源、允许容量内并发的累积资源，以及每个活动的多种可能执行模式。不同问题族以不同方式组合这些：作业车间调度（JSSP）通过优先级将操作链接在析取机器上，而资源受限项目调度（RCPSP）用累积资源替代机器，其多模式扩展在不可再生预算下添加了模式选择；所有都是NP难问题，以完工时间作为标准目标。实例是约束密集的（例如图1（https://arxiv.org/html/2608.18409#S3.F1）），因此单个遗漏或误读的关系会静默改变可行区域，使得调度成为研究自然语言问题陈述忠实形式化的自然且苛刻的目标。  

### 3.2 设计原则  
我们针对三种特性优化该语言：鲁棒性，确保建模表面产生少量格式错误的程序；简洁性，允许约束在无需特定求解器机制的情况下表达；以及对目标问题族的足够表达力。我们进一步要求有界表达力：SDDL不暴露可能让模型引入任意变量或谓词的通用语言，而是固定了重复调度构造的词汇表——优先级、析取和累积资源、可选执行模式，以及支持的目标。这有助于减少形式化错误的机会。