Improving Natural-Language Combinatorial-Optimization Accuracy in Resource-Constrained Language Models via Formal Abstractions
작은 AI 모델도 전용 미니 언어를 쓰면 말로 된 스케줄링 문제를 제대로 풀 수 있다
자원이 제한된 소형 언어모델은 자연어로 된 일정 관리 문제를 직접 풀거나 솔버 코드를 짤 때 그럴듯해 보이지만 실제로는 제약을 어기는 답을 자주 낸다. 연구팀은 모델이 과제, 자원, 선후관계 같은 스케줄링 요소만 지정하게 하고 나머지는 결정적 컴파일러가 외부 솔버용 수식으로 바꿔주는 소형 전용 언어 SDDL을 만들었다. 300개 문제로 구성된 벤치마크에서 SDDL을 쓴 모델은 직접 생성이나 일반 솔버 코드 생성보다 훨씬 더 많이 실제로 실행 가능한 일정을 만들어냈다.
METAL MEDIA 해설 도표
작은 AI 모델도 전용 미니 언어를 쓰면 말로 된 스케줄링 문제를 제대로 풀 수 있다
01문제: 자원이 제한된 소형 언어모델은 자연어로 된 일정 문제를 풀 때 기계 겹침이나 작업 순서 같은 필수 제약을 몰래 어기는 그럴듯한 답을 자주 낸다.
02방법: SDDL은 모델이 임의의 솔버 코드를 짜게 하지 않고 과제, 자원, 선후관계, 충돌 등 정해진 7개 구성요소만 쓰게 제한하며, 결정적 컴파일러가 이를 CP-SAT 솔버용 제약식으로 자동 변환해 모델이 변수 정의나 실행 코드 작성을 직접 하지 않아도 된다.
03결과: Qwen3.5-27B는 직접 생성 23.7%, 일반 솔버 코드 21.7%였던 실행 가능 일정 비율이 SDDL 적용 시 55.3%로 올랐고, Devstral-Small-2-24B는 각각 1.3%, 7.0%에서 28.3%로 올랐으며, 실행 가능한 경우 최적해와의 격차도 거의 없었다.
04검증: 모든 결과 일정은 솔버가 성공했다고 주장하는 것을 그대로 믿지 않고 원본 문제의 실제 제약 조건에 대해 독립적으로 재검증했으며, 통계적으로도 유의미한 개선으로 확인됐다.
05적용 범위: 잡숍 스케줄링과 프로젝트 스케줄링 계열 문제에서 검증됐으며, 모델이 표현해야 할 자유도를 줄이고 오류가 나기 쉬운 변수 정의 등의 결정을 컴파일러로 넘긴 것이 핵심이다.
METAL MEDIA이 원문을 바탕으로 재구성한 해설 도표이며, 논문 저자의 원문 figure가 아닙니다.
무엇을 했나
문제: 자원이 제한된 소형 언어모델은 자연어로 된 일정 문제를 풀 때 기계 겹침이나 작업 순서 같은 필수 제약을 몰래 어기는 그럴듯한 답을 자주 낸다.
방법: 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.
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.
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).
직원 근무표, 공장 작업 순서, 프로젝트 일정 같은 실제 스케줄링 요청은 대부분 자연어로 들어오지만, 이런 요청마다 대형 최상위 AI 모델을 쓰는 것은 비용이나 여건상 어려운 경우가 많다. 이 연구는 모델에게 문제 전체를 풀거나 코드로 짜게 하는 대신 문제의 구조만 정해진 형식으로 표현하게 하면, 더 크고 비싼 모델 없이도 소형 모델의 신뢰성을 크게 끌어올릴 수 있음을 보여준다.
이 논문의 용어
CP-SAT · 구글 OR-Tools에 포함된 제약 충족·최적화 문제를 푸는 솔버 엔진
실행 가능성(feasibility) · 생성된 일정이 실제 요구되는 모든 제약 조건을 만족하는지 여부
뉴로심볼릭 프레임워크 · 언어모델과 별도의 규칙 기반·수학적 계산 모듈을 결합해 실제 계산은 후자가 담당하게 하는 방식
전용 언어(DSL) · 특정 분야, 여기서는 스케줄링에만 쓰도록 제한된 소형 언어
최적성 격차(optimality gap) · 찾아낸 해가 이론상 최선의 해와 얼마나 차이 나는지를 나타내는 값
