LangNCO: Compiling Natural-Language Constraints into Inference-Time Interventions for Neural Combinatorial Optimization

Hironori Ohigashi

cs.LGOct 16, 2026

LangNCO: Compiling Natural-Language Constraints into Inference-Time Interventions for Neural Combinatorial Optimization

Authors: Hironori Ohigashi

Organizations: Panasonic Connect Co., Ltd.

Abstract

Neural combinatorial optimization (NCO) rapidly produces high-quality solutions for problem structures encountered during training, but operational requirements may change after deployment and be communicated in natural language. We propose LangNCO, a framework that compiles instance-specific requirements into structured inference-time interventions for a frozen NCO solver, without changing the pretrained policy's architecture, learned input representation, or parameters. A pretrained LLM serves as a replaceable semantic front end, translating each requirement into a schema-validated domain-specific language (DSL) rule set. A deterministic Rule Executor applies the rules as nonexpansive hard action masks. Because local masking prevents immediate violations but does not ensure that a complete feasible continuation remains reachable, Critical-Offset Decoding extracts rule-referenced critical nodes and reallocates part of a fixed rollout budget to multi-strength biased rollouts. Using controlled task-specific language to isolate solver adaptation from open-ended language robustness, we evaluate a CVRP policy on road closures, time windows, vehicle assignments, visit-order requirements, all pairwise combinations, and twelve additional constraint types. LangNCO achieves 100% feasibility on the four primary datasets with mean reference gaps of 1.63--3.26%, 97.33--100% feasibility when separately generated rules are composed for pairwise constraints, and 98.67% feasibility across the additional constraints. These results demonstrate modular post-training adaptation of a frozen NCO solver through inspectable language-derived rules, without retraining.

Figures & tables

Figure 1: Inference-time intervention. A natural-language specification is translated into a DSL rule set that is validated and compiled to drive hard action masking and critical-node-biased rollouts. The pretrained NCO policy’s parameters and learned input representation remain unchanged.

	Road		Time		Vehicle		Order
Method	Feas. $\uparrow$	Gap $\downarrow$	Feas. $\uparrow$	Gap $\downarrow$	Feas. $\uparrow$	Gap $\downarrow$	Feas. $\uparrow$	Gap $\downarrow$
LLMCoSolver	36.33%	5.70%	13.67%	4.42%	2.00%	0.58%	0.00%	–
Direct GPT-5	95.00%	35.02%	79.67%	120.01%	95.33%	40.39%	95.67%	32.04%
NCO w/o intervention	37.33%	2.65%	11.00%	1.63%	1.00%	2.56%	1.33%	1.47%
LangNCO-Gemma4	100.00%	1.63%	100.00%	1.89%	100.00%	2.53%	100.00%	3.26%
LangNCO-GPT-5	100.00%	1.63%	100.00%	1.89%	100.00%	2.68%	100.00%	2.97%

Table 1: End-to-end performance. Gap is computed over feasible outputs only; “–” denotes no feasible output.

	Road		Time		Vehicle		Order
Strategy	Feas. $\uparrow$	Gap $\downarrow$	Feas. $\uparrow$	Gap $\downarrow$	Feas. $\uparrow$	Gap $\downarrow$	Feas. $\uparrow$	Gap $\downarrow$
NCO greedy	100.00%	3.19%	99.67%	4.47%	75.33%	5.64%	75.00%	7.69%
NCO greedy + 1 sample	100.00%	2.28%	99.67%	3.83%	77.33%	5.26%	83.67%	6.56%
Critical-Offset greedy	100.00%	3.15%	100.00%	3.52%	100.00%	4.56%	100.00%	6.81%
NCO sampling	100.00%	1.64%	99.67%	2.19%	87.67%	3.33%	97.00%	3.52%
Critical-Offset sampling	100.00%	1.63%	100.00%	1.89%	100.00%	2.53%	100.00%	2.85%

Table 2: Effect of Critical-Offset Decoding. Gap is computed over each strategy’s feasible outputs only.

Combination	Feasible (Ours / Ref.)	Gap $\downarrow$
Road + Time	300 / 300	2.25%
Road + Vehicle	300 / 300	3.14%
Road + Order	300 / 300	3.94%
Time + Vehicle	300 / 300	4.01%
Time + Order	292 / 289	5.18%
Vehicle + Order	294 / 297	6.77%

Table 3: Pairwise constraint composition for LangNCO-Gemma4. Counts are Ours / Ref. out of 300; gap is computed over jointly feasible instances.

Appendix figures & tables16 assets

Supplementary material from the paper’s appendix.

Appendix

Field	Contents
num_nodes	Number of nodes, including the depot.
vehicle_capacity	Homogeneous vehicle capacity $Q$ .
instruction	Natural-language statement of unique visits, capacity, Euclidean-distance minimization, and output format.
input	Node IDs, coordinates, demands, and the two nearest neighbors and distances used as LLM heuristic features.
output	LKH-3 routes and total distance.

Appendix

Table 4: Principal fields in the public LLMCoSolver CVRP instances.

Component	Abstract role
Target	Selects the candidate actions affected by a constraint.
State guard	Determines whether the constraint is active for a decoder state.
Candidate predicate	Evaluates the constraint separately for each candidate action.
Effect	Removes matched actions or restricts the feasible set to matched actions.

Appendix

Table 5: Semantic components of the guarded-rule representation.

Path	Used	Not used
Learned initial embedding	Depot/customer coordinates and customer demand	Time windows, service time, backhaul demand, open-route flag, distance limit, natural language, or DSL tokens
Learned step context	Current-node embedding and available load	Current time, vehicle index, full visit sequence, or remaining distance
Decoder interface	Combined base/rule mask, critical-node lookup, and $\alpha$	Natural-language or DSL tokens and raw values referenced by guards
Environment and Rule Executor	Visit state, time/travel state, vehicle ID, capacity, and other state needed to evaluate a mask	Any learned-parameter update

Appendix

Table 6: Information-flow audit. Constraint-specific state affects the frozen policy only through the nonexpansive action mask and legal-action offset.

Setting	Gemma4	GPT-5
Identifier	gemma4:31b-it-q8_0	Azure deployment gpt-5
Runtime/API	Ollama	Azure OpenAI API, 2025-01-01-preview
Quantization	8 bit	Managed API (not applicable)
Temperature	0.0	Default
Top- $p$ /top- $k$	Ollama defaults	Defaults
Context length	8,192 tokens ( OLLAMA_CONTEXT_LENGTH=8192 )	Managed by API; not configured

Appendix

Table 7: LLM rule-generation settings. “Default” means the request omitted that option. Context length is shared by prompt and output; maximum completion is the request-level output cap.

Method/component	Model or implementation	Inference setting
LangNCO	Frozen RouteFinder	Critical-Offset Decoding; eight dihedral augmentations; all POMO starts; 100 samples per start and augmentation; decoder temperature 1.0; 90 ordinary and ten offset-guided samples.
Direct GPT-5	Azure OpenAI gpt-5	One-shot prompt; one response per instance; 128,000 maximum completion tokens; medium reasoning; default temperature; no retry; regex and JSON route parsing.
LLMCoSolver	Retrained Qwen2.5-7B-based model	Two-nearest-neighbor augmentation; best of eight; temperature 0.7; top- $p$ 0.9; 3,000 maximum new tokens; selection by base-CVRP reward.
NCO w/o intervention	Same frozen RouteFinder	No rule; augmented multi-start greedy decoding; eight augmentations and all POMO starts.
LKH-3 reference	Road wrapper	RUNS=10 ; seed zero; closed edge cost ten times the maximum instance edge.
OR-Tools reference	Routing Solver	PCI for Time/Vehicle/Order and GCA for Pairwise; guided local search; 600 seconds per instance.

Appendix

Table 8: Methods and inference settings. Every RouteFinder-based row uses the same frozen standard-CVRP policy.

Stage	Seed or selection rule
Primary and Additional generation	1234 for every task.
Pairwise construction	Join the two primary instances by index; no new sampling.
Additional subset	Proportional size strata; first source instances within each stratum.
Gemma4 rule generation	Seed 0 and temperature 0.0.
GPT-5 rule generation / Direct GPT-5	No reproducible fixed seed.
LangNCO NCO sampling	Seed $i$ for instance $i$ .

Appendix

Table 9: Randomness controls and deterministic selection rules.

Item	Configuration
CPU	Intel Xeon w9-3575X, 44 cores / 88 threads
GPU	NVIDIA RTX PRO 6000 Blackwell Max-Q, 96 GB
Memory	512 GiB
OS	Ubuntu 24.04
Python	3.12
Ollama	0.30.8

Appendix

Table 10: Local execution environment.

Method	Feasible	Gap [%]	Objective
LLMCoSolver	300/300 (100.00%)	$4.91\pm 3.37$	$10{,}227.09\pm 5{,}208.21$
Direct GPT-5	277/300 (92.33%)	$48.76\pm 82.40$	$15{,}326.47\pm 12{,}776.96$
NCO w/o intervention	300/300 (100.00%)	$2.83\pm 2.32$	$9{,}885.24\pm 4{,}750.93$
LangNCO (empty rule)	300/300 (100.00%)	$2.83\pm 2.32$	$9{,}885.24\pm 4{,}750.93$

Appendix

Table 11: Unconstrained CVRP sanity check. The empty-rule result exactly matches the frozen RouteFinder baseline.

Dataset	Method	Feasible	Gap [%]	Objective
Road	LLMCoSolver	109/300 (36.33%)	$5.70\pm 3.34$	$11{,}811.25\pm 5{,}577.29$
Road	Direct GPT-5	285/300 (95.00%)	$35.02\pm 64.20$	$13{,}281.54\pm 9{,}665.37$
Road	NCO w/o intervention	112/300 (37.33%)	$2.65\pm 2.02$	$10{,}865.53\pm 5{,}121.04$
Road	LangNCO-Gemma4	300/300 (100.00%)	$1.63\pm 1.65$	$9{,}828.66\pm 4{,}719.14$
Road	LangNCO-GPT-5	300/300 (100.00%)	$1.63\pm 1.65$	$9{,}828.66\pm 4{,}719.14$
Time	LLMCoSolver	41/300 (13.67%)	$4.42\pm 2.46$	$11{,}325.59\pm 5{,}269.24$

Appendix

Table 12: Full primary-task end-to-end results. Gaps and objectives summarize only feasible outputs; each dataset has 300 instances.

Dataset	Generator	End-to-end [ms]	Rule generation [ms]	Validate + compile [ms]	NCO solve [ms]
Road	Gemma4	$16{,}398.08\pm 4{,}678.31$	$16{,}113.54\pm 4{,}682.77$	$2.84\pm 0.72$	$281.69\pm 153.71$
Road	GPT-5	$10{,}714.05\pm 3{,}681.74$	$10{,}457.49\pm 3{,}683.47$	$0.65\pm 0.24$	$255.91\pm 137.14$
Time	Gemma4	$44{,}983.17\pm 6{,}997.72$	$44{,}691.05\pm 6{,}962.60$	$2.81\pm 0.79$	$289.32\pm 175.59$
Time	GPT-5	$39{,}842.02\pm 22{,}012.27$	$39{,}495.22\pm 21{,}987.02$	$0.74\pm 0.26$	$346.05\pm 205.16$
Vehicle	Gemma4	$15{,}023.30\pm 2{,}863.01$	$14{,}743.96\pm 2{,}829.72$	$2.77\pm 0.77$	$276.57\pm 156.65$
Vehicle	GPT-5	$36{,}637.52\pm 22{,}892.23$	$36{,}323.33\pm 22{,}883.83$	$0.64\pm 0.21$	$313.55\pm 186.47$

Appendix

Table 13: Per-instance LangNCO wall-clock latency (mean

\pm

standard deviation). End-to-end time is the sum of the three measured stages.

Dataset	Strategy	Feasible	Gap [%]	Objective	Time [ms]
Road	NCO greedy (noaug + single start)	300/300 (100.00%)	$9.47\pm 11.49$	$10{,}424.60\pm 4{,}756.40$	$99.20\pm 53.19$
Road	NCO greedy (noaug)	300/300 (100.00%)	$5.23\pm 5.84$	$10{,}107.41\pm 4{,}734.66$	$113.87\pm 50.90$
Road	NCO greedy	300/300 (100.00%)	$3.19\pm 3.04$	$9{,}950.00\pm 4{,}728.90$	$117.36\pm 56.35$
Road	NCO greedy + 1 sample	300/300 (100.00%)	$2.28\pm 2.38$	$9{,}920.20\pm 4{,}728.38$	$239.61\pm 106.60$
Road	NCO sampling	300/300 (100.00%)	$1.64\pm 1.68$	$9{,}830.36\pm 4{,}723.48$	$167.88\pm 99.84$
Road	Critical-Offset greedy	300/300 (100.00%)	$3.15\pm 3.03$	$9{,}946.12\pm 4{,}727.31$	$140.88\pm 65.04$

Appendix

Table 14: Full decoding ablation across all four primary datasets. Time is per-instance NCO decoding time in milliseconds; language generation and compilation are excluded.

Dataset	$\rho$	Reference gap [%] at offset-strength spacing $\Delta\alpha$
		0.05	0.10	0.20	0.50
Road	0.05	–	–	$1.63\pm 1.66$	$1.63\pm 1.66$
	0.10	–	$1.63\pm 1.66$	$1.63\pm 1.65^{\dagger}$	$1.64\pm 1.67$
	0.20	$1.64\pm 1.65$	$\mathbf{1.62}\pm 1.62$	$1.65\pm 1.67$	$1.65\pm 1.67$
	0.50	$1.66\pm 1.62$	$1.66\pm 1.63$	$1.65\pm 1.59$	$1.68\pm 1.66$
Time	0.05	–	–	$1.94\pm 3.02$	$1.94\pm 3.03$

Appendix

Table 15: Critical-Offset sensitivity at a fixed budget of 100 rollouts per POMO start and augmentation, with rollout ratio

\rho

by row and strength spacing

\Delta\alpha

by column. Entries are mean reference gap

\pm

standard deviation over feasible solutions; every filled cell attained 300/300 feasible solutions. Dashes mark combinations that cannot cover every strength at least once. Bold denotes the lowest gap for each dataset, and

\dagger

marks the setting used in the main paper.

Dataset	Generator	Representation	Feasible	Failure	Gap [%]
Road	Gemma4	DSL	300/300 (100.00%)	0	1.63
Road	Gemma4	Python	300/300 (100.00%)	0	1.63
Road	GPT-5	DSL	300/300 (100.00%)	0	1.63
Road	GPT-5	Python	300/300 (100.00%)	0	1.63
Time	Gemma4	DSL	300/300 (100.00%)	0	1.89
Time	Gemma4	Python	289/300 (96.33%)	11	1.89

Appendix

Table 16: Schema-validated DSL versus free-form Python rule generation. Each row contains 300 instances.

Combination	Method	Feasible	Gap vs. GCA [%]	Objective
Road + Time	OR-Tools (GCA)	300/300 (100.00%)	–	$9{,}875.92\pm 4{,}773.63$
Road + Time	Separate	300/300 (100.00%)	$2.25\pm 3.45$	$10{,}016.40\pm 4{,}679.15$
Road + Time	Joint	297/300 (99.00%)	$2.27\pm 3.46$	$9{,}996.15\pm 4{,}696.13$
Road + Vehicle	OR-Tools (GCA)	300/300 (100.00%)	–	$9{,}998.89\pm 4{,}844.93$
Road + Vehicle	Separate	300/300 (100.00%)	$3.14\pm 2.82$	$10{,}253.60\pm 4{,}813.32$
Road + Vehicle	Joint	300/300 (100.00%)	$3.14\pm 2.82$	$10{,}253.60\pm 4{,}813.32$

Appendix

Table 17: All pairwise constraint results. Gap is relative to the OR-Tools GCA reference on the jointly feasible subset.

Combination	Feasibility [%]
	PCI	LCI	PMCA	GCA	SV	AT
Road + Time	100.00	100.00	100.00	100.00	100.00	100.00
Road + Vehicle	100.00	100.00	100.00	100.00	24.67	73.67
Road + Order	98.67	98.67	8.33	100.00	9.33	11.67
Time + Vehicle	99.00	96.33	99.67	100.00	22.33	73.33
Time + Order	90.00	86.67	7.33	96.33	6.67	13.00

Appendix

Table 18: OR-Tools pairwise feasibility by first-solution strategy. PCI: parallel cheapest insertion; LCI: local cheapest insertion; PMCA: path most constrained arc; GCA: global cheapest arc; SV: savings; AT: automatic.

Constraint type	NCO w/o intervention	LangNCO-Gemma4
First delivery	0/50 (0.00%)	50/50 (100.00%)
Visit position	4/50 (8.00%)	50/50 (100.00%)
Arrival capacity reserve	33/50 (66.00%)	50/50 (100.00%)
Heavy-delivery limit	5/50 (10.00%)	50/50 (100.00%)
Minimum service interval	1/50 (2.00%)	50/50 (100.00%)
Depot closure	17/50 (34.00%)	50/50 (100.00%)

Appendix

Table 19: Feasibility on twelve additional constraint types, 50 instances each. No constrained objective reference is available for these datasets.

Neural Combinatorial Optimization

Neural combinatorial optimization uses neural networks to find high-quality solutions to discrete problems such as routing, scheduling, and graph partitioning.

See all 137 papers

Interpreting Neural Combinatorial Optimization via Evolving Programmatic Bottlenecks
Jun 18, 2026Haocheng Duan, Yuxin Guo, Jieyi Bi +4Neural Network Interpretability Neural Combinatorial Optimization
1Carnegie Mellon University · 2Nanyang Technological University · 3Microsoft Research +1
Understanding Decision-Making Mechanisms in Neural Routing Solvers
Sep 28, 2026Fatemeh Askari, Mazdak Teymourian, Mohammad Izadi +1Mechanistic Interpretability Neural Network Interpretability
Department of Computer EngineeringSharif University of Technology
Improving Natural-Language Combinatorial-Optimization Accuracy in Resource-Constrained Language Models via Formal Abstractions
Aug 19, 2026Shrenil Shaun Sharma, Avi SharmaLarge Language Model-Guided Optimization Combinatorial Optimization
Independent Researcher San Francisco, CA, USA · Department of Electrical Engineering and Computer Sciences University of California, Berkeley

Jun 18, 2026J/K move · Enter open · S save

Interpreting Neural Combinatorial Optimization via Evolving Programmatic Bottlenecks

Haocheng Duan, Yuxin Guo, Jieyi Bi, Anqi Xie+3

1Carnegie Mellon University · 2Nanyang Technological University · 3Microsoft Research+1

Neural Network Interpretability Neural Combinatorial Optimization

Open paper AskPDF arXiv

Neural Combinatorial Optimization (NCO) achieves strong performance, yet its black-box nature remains a key roadblock to deployment and scientific diagnosis. Standard interpretability tools, such as Concept Bottleneck Models (CBMs), are ill-equipped for NCO, whose decisions are dynamic, state-dependent, and lack proper concept vocabulary definition. To close this gap, we introduce Evolving Programmatic Bottlenecks (EPB), to our knowledge, the first framework for interpreting NCO policies by distilling black-box NCO models into human-readable program portfolios. EPB employs an LLM to autonomously evolve a bank of programs, where each program's per-step action distribution serves as the bottleneck. EPB works through an iterative framework: Block I fixes program bank capacity and introduces a hybrid textual-numerical gradient descent scheme that couples numerical gradients for student router updates and textual gradients for LLM-based program revision; Block II dynamically adapts bank capacity via fault-targeted expansion and redundancy pruning. Extensive experiments demonstrate EPB's effectiveness and broad applicability, where the distilled program portfolios largely match original performance. EPB also reveals that NCO behavior shifts across optimization stages and can be approximated as a composition of classic heuristic variants. Our work advances interpretable NCO and establishes EPB as a promising tool for interpreting sequential decision-making models.

Abstract

Neural Combinatorial Optimization

Explore similar work

Interpreting Neural Combinatorial Optimization via Evolving Programmatic Bottlenecks

Understanding Decision-Making Mechanisms in Neural Routing Solvers

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