Improving Natural-Language Combinatorial-Optimization Accuracy in Resource-Constrained Language Models via Formal Abstractions
arXiv:2608.184092026-08-20
작은 AI 모델도 전용 미니 언어를 쓰면 말로 된 스케줄링 문제를 제대로 풀 수 있다
자원이 제한된 소형 언어모델은 자연어로 된 일정 관리 문제를 직접 풀거나 솔버 코드를 짤 때 그럴듯해 보이지만 실제로는 제약을 어기는 답을 자주 낸다. 연구팀은 모델이 과제, 자원, 선후관계 같은 스케줄링 요소만 지정하게 하고 나머지는 결정적 컴파일러가 외부 솔버용 수식으로 바꿔주는 소형 전용 언어 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%로 올랐으며, 실행 가능한 경우 최적해와의 격차도 거의 없었다.
- 검증: 모든 결과 일정은 솔버가 성공했다고 주장하는 것을 그대로 믿지 않고 원본 문제의 실제 제약 조건에 대해 독립적으로 재검증했으며, 통계적으로도 유의미한 개선으로 확인됐다.
- 적용 범위: 잡숍 스케줄링과 프로젝트 스케줄링 계열 문제에서 검증됐으며, 모델이 표현해야 할 자유도를 줄이고 오류가 나기 쉬운 변수 정의 등의 결정을 컴파일러로 넘긴 것이 핵심이다.
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에서 원문 보기
