Improving Natural-Language Combinatorial-Optimization Accuracy in Resource-Constrained Language Models via Formal Abstractions
arXiv:2608.184092026-08-20
给小模型一门专用的排程小语言,就能让它写出真正可行的日程安排
资源受限的小型语言模型在用自然语言直接解决排程问题或编写求解器代码时,常常给出看似合理却违反实际约束的排程结果。研究者开发了SDDL,一种只允许模型指定任务、资源、先后顺序等排程要素的专用小语言,再由确定性编译器将其转换成外部求解器可用的数学模型。在一个包含300个实例的基准测试中,使用SDDL的模型生成可行排程的比例远高于直接生成或编写通用求解器代码的情况。
他们做了什么
- 问题：资源受限的小型语言模型在处理自然语言描述的排程任务时，经常生成表面流畅却违反机器占用冲突、任务先后顺序等硬性约束的排程方案。
- 方法：SDDL不让模型自由编写求解器代码，而是只提供任务、资源、先后关系、冲突等7种固定的基本构件；确定性编译器再把这些构件转换成CP-SAT求解器所需的约束，模型无需自己定义变量或编写可执行代码。
- 结果：Qwen3.5-27B的可行排程比例从直接生成的23.7%、通用求解器代码的21.7%提升到使用SDDL后的55.3%；Devstral-Small-2-24B则从1.3%和7.0%分别提升到28.3%，且在可行方案中与最优解的差距也很小。
- 验证：所有排程结果都用独立验证器对照原始问题的真实约束重新核查，而不是仅凭求解器自称成功，改进效果也经过统计显著性检验确认。
- 适用范围：该方法在job-shop排程和项目排程这类问题族上得到验证，其核心在于压缩模型需要表达的自由度，把易出错的变量定义等决策转交给编译器完成。
Table 1: Per-model results on SCHEDBench subset, ‡ marks new results. Brackets list 95% Wilson CIs on feasibility. Bold figures follow model feasibility through all three conditions, direct → solver-mediated → SDDL, with blue for qwen3.5-27b, orange for devstral-small-2-24b. †Evaluated with SDDL, not a new model. | Solver-Mediated Generation | Direct Generation | |
|---|
| Model | N | Feas. (%) | 95% CI (%) | R. fail (%) | Med. gap (%) | N | Feas. (%) | 95% CI (%) | Med. gap (%) | Δ Feas. |
| claude-opus-4-6 | 300 | 56.7‡ | [51.0, 62.2] | 21.0 | 0.0 | 300 | 4.7 | [2.8, 7.7] | 18.3 | +52.0 |
| qwen3.5-27b + SDDL† | 300 | 55.3‡ | [49.7, 60.9] | 16.0 | 0.0 | 300 | 23.7 | [19.2, 28.8] | 395.8 | +31.7 |
| gpt-5.5 (2026-04-23) | 300 | 53.3‡ | [47.7, 58.9] | 5.0 | 0.0 | 300 | 57.0 | [51.3, 62.5] | 36.7 | −3.7 |
| gpt-5.4 (2026-03-05) | 300 | 51.7 | [46.0, 57.3] | 18.3 | 0.0 | 300 | 0.3 | [0.1, 1.9] | 16.7 | +51.3 |
| gpt-5.4-mini (2026-03-17) | 300 | 36.7 | [31.4, 42.3] | 32.3 | 7.5 | 300 | 0.7 | [0.2, 2.4] | 131.8 | +36.0 |
| claude-sonnet-4-6 | 300 | 35.0‡ | [29.8, 40.6] | 24.3 | 0.0 | 300 | 8.3 | [5.7, 12.0] | 19.5 | +26.7 |
| qwen/qwen3.5-397b (2026-02-16) | 300 | 33.3 | [28.2, 38.8] | 12.3 | 0.0 | 300 | 19.3 | [15.3, 24.2] | 14.6 | +14.0 |
| devstral-small-2-24b + SDDL† | 300 | 28.3‡ | [23.5, 33.7] | 30.0 | 0.0 | 300 | 1.3‡ | [0.5, 3.4] | 111.2 | +27.0 |
| qwen/qwen3.5-122b (2026-02-24) | 300 | 23.3 | [18.9, 28.4] | 56.0 | 0.6 | 300 | 7.0 | [4.6, 10.5] | 7.1 | +16.3 |
| qwen/qwen3.5-27b (2026-02-24) | 300 | 21.7 | [17.4, 26.7] | 62.7 | 2.6 | 300 | 23.7 | [19.2, 28.8] | 395.8 | −2.0 |
| gemini-3.1-flash-lite | 300 | 17.0 | [13.2, 21.7] | 56.7 | 0.0 | 300 | 0.3 | [0.1, 1.9] | 107.1 | +16.7 |
| gemini-3-flash-preview | 300 | 12.0‡ | [8.8, 16.2] | 74.3 | 0.0 | 300 | 22.0 | [17.7, 27.0] | 24.5 | −10.0 |
| devstral-small-2-24b (2025-12-09) | 300 | 7.0‡ | [4.6, 10.5] | 66.7 | 0.0 | 300 | 1.3‡ | [0.5, 3.4] | 111.2 | +5.7 |
| claude-haiku-4-5 (2025-10-01) | 300 | 2.0 | [0.9, 4.3] | 37.0 | 0.0 | 300 | 1.0 | [0.3, 2.9] | 135.3 | +1.0 |
| meta-llama-4-maverick-17bX123e | 300 | 1.0 | [0.3, 2.9] | 92.0 | 0.0 | 300 | 0.3 | [0.1, 1.9] | 150.0 | +0.7 |
Table 2: The five registered penalty measures. Each is implemented once in the compiler and reused across programs; makespan is the only measure exercised by the evaluated families.| Measure | Archetype | Definition (minimized) |
|---|
| makespan | continuous | maxiendi over all scheduled tasks |
| capacity | discrete | total enrolment exceeding room capacity, summed over assignments |
| spread | discrete | shortfall below each task’s min_days distinct meeting days |
| isolated | discrete | count of meetings with no adjacent same-group meeting |
| room_stability | discrete | number of distinct rooms used by a task beyond the first |
Table 3: Evaluation-subset composition.| Family | Source suites | N |
|---|
| JSSP | Taillard, DMU, LA, ORB, ABZ, SWV | 100 |
| SM-RCPSP | PSPLIB J30–J120 | 100 |
| MM-RCPSP | PSPLIB MM J10–J30 | 100 |
Table 4: Inference, sandbox, and solver configuration.| Setting | Value |
|---|
| Resource-Constrained models | qwen3.5-27b (2026-02-24), devstral-small-2-24b (2025-12-09), qwen3-coder-30b-a3b (2025-07-31), magistral-small-24b (2025-09-17) |
| Reproduced | pinned versions of Table 1 (SCHEDBench) |
| Decoding | greedy (temperature 0), zero-shot, single pass, no tools |
| Max output tokens | 96,000 default; provider ceilings; token-terminated responses retained and scored |
| Sandbox | no network, fresh directory, 4 GB memory, 300 s wall-clock limit; CP-SAT budget fixed at 240 s in both solver-mediated conditions |
| Software | Python 3.11.2; OR-Tools 9.15.6755 (CP-SAT, default parameters except max_time_in_seconds) |
Table 5: Complete primitive and property reference. A well-formed task satisfies exactly one archetype rule: it is continuous iff it specifies duration or modes and no count, and discrete iff it specifies count; archetype assignment is therefore deterministic and complete, and a task specifying both (or neither) is rejected as malformed.| Primitive | Property | Value | Meaning / well-formedness |
|---|
| task(id, ...) | duration | int ≥0 | processing time; declares a continuous task |
| modes | list of maps | alternative execution modes, each a map with duration and optional demands/consumes; declares a continuous multi-mode task; mutually exclusive with a top-level duration |
| demands | map {rid: int} | renewable units held while active; keys must name declared resource() ids with capacity |
| consumes | map {rid: int} | nonrenewable units expended once; keys must name resources with total |
| machine | string rid | fixed disjunctive-resource assignment; pair with no_overlap(rid) |
| job, position | int, int | job index and 0-based operation index (job-shop bookkeeping used by the renderer) |
| label | string | verbatim display name from the problem text; consumed by the renderer/verifier, not the solver |
| count | int ≥1 | number of meetings; declares a discrete (timetabling) task |
| min_days, students | int | discrete-archetype spread/enrolment attributes |
| demand | int ≥1 | units required while assigned (discrete archetype: enrolment, checked against room capacity and scored by the capacity measure) |
| resource(id, ...) | capacity | int ≥1 | renewable per-time capacity ⇒ cumulative semantics; for the discrete archetype, a room’s seat capacity |
| total | int ≥1 | nonrenewable project-wide budget ⇒ linear budget semantics |
| (neither) | — | strictly disjunctive resource; meaningful with no_overlap |
| before(a, b) | — | task ids | hard finish-to-start precedence: enda≤startb; both ids must be declared |
| no_overlap(r) | — | resource id | at most one assigned task active on r at any time |
| conflict(...) | group | string (opt.) | listed tasks may not occupy the same time slot; group label also keys group-level objective terms (discrete archetype) |
| not_at(id, ...) | day, period | int | forbids execution at the given absolute time; on continuous tasks the forbidden times enter the horizon offset T (§3.7) |
| penalize(m, ...) | weight | int ≥1 | soft objective term; m must be a registered measure name (Table 2) |
Table 6: Statement-by-statement lowering into CP-SAT. Discrete-archetype tasks lower to day, period, and room integer variables with a channelled slot variable slot=day⋅NP+period.| SDDL construct | CP-SAT lowering |
|---|
| continuous task (fixed duration d) | si,ei∈[0,H] (NewIntVar); interval NewIntervalVar(si,d,ei) |
| continuous task with modes Mi | mode Booleans bim (NewBoolVar) with AddExactlyOne; duration variable di∈[minmdim,maxmdim] channelled by bim⇒di=dim (OnlyEnforceIf); a master interval on (si,di,ei) plus one NewOptionalFixedSizeIntervalVar(si,dim,bim) per mode |
| before(a, b) | model.Add(sb≥ea) |
| no_overlap(r) | AddNoOverlap over the intervals of tasks with machine =r |
| renewable resource (capacity=k) | AddCumulative(intervals, demands, k); multi-mode tasks contribute their per-mode optional intervals with mode-specific demands |
| nonrenewable resource (total=B) | linear budget ∑i∑mcimbim≤B (fixed-mode consumption enters as constants) |
| conflict(...) | AddAllDifferent over the members’ slot variables (discrete archetype) |
| discrete task (count c) | c meetings, each with day, period, and room integer variables and channelled slot =day⋅NP+period; room assignment respects seat capacity |
| not_at(id, day, period) | continuous tasks: reified exclusion ei≤t∨si>t per forbidden time t; discrete tasks: slot-exclusion constraints on the day/period variables, reified per meeting |
| penalize("makespan", w) | 𝑚𝑠∈[0,H] with AddMaxEquality(𝑚𝑠,{ei}); contributes w⋅𝑚𝑠 |
| objective | Minimize(∑penalty terms) |
Table 7: McNemar discordant counts (b: SDDL-only feasible; c: comparison-only feasible) and two-sided p-values for the within-model contrasts; all remain significant after Holm correction (padj<10−6).| Model | Contrast | b | c | p |
|---|
| qwen3.5-27b | SDDL vs. Direct | 100 | 5 | 5.0×10−24 |
| SDDL vs. Solver | 107 | 6 | 5.2×10−25 |
| devstral-small-2-24b | SDDL vs. Direct | 82 | 1 | 1.7×10−23 |
| SDDL vs. Solver | 67 | 3 | 9.7×10−17 |
| qwen3-coder-30b-a3b | SDDL vs. Direct | 70 | 1 | 6.1×10−20 |
| SDDL vs. Solver | 61 | 2 | 4.4×10−16 |
| magistral-small-24b | SDDL vs. Direct | 41 | 0 | 9.1×10−13 |
| SDDL vs. Solver | 42 | 5 | 2.5×10−8 |
Table 8: Resource-constrained models across all three conditions, direct → solver-mediated → SDDL, in the format of Table 1. Brackets list 95% Wilson CIs on feasibility. Color follows one model across rows, with blue for qwen3.5-27b, orange for devstral-small-2-24b, green for qwen3-coder-30b-a3b, purple for magistral-small-24b. | Solver-Mediated Generation | Direct Generation | |
|---|
| Model | N | Feas. (%) | 95% CI (%) | R. fail (%) | Med. gap (%) | N | Feas. (%) | 95% CI (%) | Med. gap (%) | Δ Feas. |
| qwen3.5-27b + SDDL | 300 | 55.3 | [49.7, 60.9] | 16.0 | 0.0 | 300 | 23.7 | [19.2, 28.8] | 395.8 | +31.7 |
| devstral-small-2-24b + SDDL | 300 | 28.3 | [23.5, 33.7] | 30.0 | 0.0 | 300 | 1.3 | [0.5, 3.4] | 111.2 | +27.0 |
| qwen3-coder-30b-a3b + SDDL | 300 | 23.3 | [18.9, 28.4] | 28.7 | 0.0 | 300 | 0.3 | [0.1, 1.9] | 357.1 | +23.0 |
| qwen/qwen3.5-27b (2026-02-24) | 300 | 21.7 | [17.4, 26.7] | 62.7 | 2.6 | 300 | 23.7 | [19.2, 28.8] | 395.8 | −2.0 |
| magistral-small-24b + SDDL | 300 | 15.0 | [11.4, 19.5] | 47.3 | 0.0 | 300 | 1.3 | [0.5, 3.4] | 159.9 | +13.7 |
| devstral-small-2-24b (2025-12-09) | 300 | 7.0 | [4.6, 10.5] | 66.7 | 0.0 | 300 | 1.3 | [0.5, 3.4] | 111.2 | +5.7 |
| qwen3-coder-30b-a3b (2025-07-31) | 300 | 3.7 | [2.1, 6.4] | 74.3 | 0.0 | 300 | 0.3 | [0.1, 1.9] | 357.1 | +3.3 |
| magistral-small-24b (2025-09-17) | 300 | 2.7 | [1.4, 5.2] | 88.0 | 0.0 | 300 | 1.3 | [0.5, 3.4] | 159.9 | +1.3 |
Table 9: qwen3.5-27b by family and condition (N=300 convention; run-fail includes instances without a completed generation).| Cond. | Family | N | Feas. (%) | R. fail (%) | Med. gap (%) |
|---|
| SDDL | JSSP | 100 | 96.0 | 3.0 | 0.0 |
| SDDL | SM-RCPSP | 100 | 17.0 | 44.0 | 0.0 |
| SDDL | MM-RCPSP | 100 | 53.0 | 1.0 | 0.0 |
| Solver | JSSP | 100 | 53.0 | 40.0 | 5.4 |
| Solver | SM-RCPSP | 100 | 7.0 | 68.0 | 0.0 |
| Solver | MM-RCPSP | 100 | 5.0 | 80.0 | 0.0 |
| Direct | JSSP | 100 | 52.0 | 0.0 | 697.4 |
| Direct | SM-RCPSP | 100 | 4.0 | 0.0 | 0.0 |
| Direct | MM-RCPSP | 100 | 15.0 | 0.0 | 0.0 |
Table 10: Hand-coded causes over a stratified sample of SDDL failures (one primary code per instance).| Failure code | qwen3.5 | devstral | q3-coder | magistral | Total |
|---|
| Dropped / garbled precedence edges (tasks complete) | 6 | 4 | 4 | 5 | 19 |
| Referenced-but-undeclared real activity | 1 | 2 | 0 | 3 | 6 |
| Phantom identifier (no problem counterpart) | 1 | 1 | 0 | 0 | 2 |
| Duplicate task declarations | 0 | 1 | 1 | 0 | 2 |
| Coverage collapse / label mismatch | 0 | 1 | 2 | 0 | 3 |
| Primitive-argument misuse | 0 | 0 | 1 | 0 | 1 |
| Emission derailment (prose drift, repetition, syntax slip) | 2 | 0 | 0 | 1 | 3 |
| Coded / sampled | 10/10 | 9/10 | 8/10 | 9/10 | 36/40 |
为什么重要
员工排班、工厂作业顺序、项目计划等现实中的排程需求大多以自然语言提出，但为每个这类请求都调用大型顶尖AI模型往往成本过高或不现实。这项工作表明，与其让模型自己解决或编写整个求解代码，不如给它一个专门设计的狭窄格式来表达问题结构，这样即使不用更大的模型，也能大幅提升小模型的可靠性。
本文术语
- CP-SAT · 谷歌OR-Tools中的一款约束求解引擎，用于寻找组合优化问题的可行解或最优解
- 可行性(feasibility) · 生成的排程是否真正满足所有实际要求的约束条件
- 神经符号框架 · 将语言模型与独立的规则或数学计算模块结合，由后者完成真正计算的系统
- 领域专用语言(DSL) · 仅限于特定领域使用的小型专用语言，此处仅限排程领域
- 最优性差距(optimality gap) · 所得解与理论最优解之间的差距大小
论文原文摘要（英文）
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.
作者 · Shrenil Shaun Sharma, Avi Sharma
在 arXiv 阅读
