REVIEW 4 major objections 3 minor 1 cited by
ACCORD: Autoregressive Constraint-satisfying Generation for COmbinatorial Optimization with Routing and Dynamic attention
T0 review · 4 major / 3 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read The paper claims that the output format itself can enforce combinatorial feasibility, letting an 8B LLM beat GPT-4 on six NP-hard problems.
desk verdict Novel output representation for LLM-based combinatorial optimization, but the optimality numbers are measured against the same heuristics the model was trained to imitate. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the ACCORD output representation: instead of emitting a static list of decisions, the model emits transitions of the form [decision -> metric: old_metric + delta = new_metric <= limit], so cumulative sums and capacity constraints are visible at each autoregressive step. This is paired with an attention-based dynamic router, a small classifier over pooled token embeddings, that activates the correct LoRA adapter for the problem named in the instruction, so a single 8B model can route between TSP, VRP, Knapsack, FlowShop, JSSP, and BinPacking branches.
What would settle it
Re-run the same validation instances and compute gaps against exact optimal solutions or much stronger solvers instead of the OR-Tools references; if the gaps rise well above Table 1, the optimality claim is unsupported.
Extended reading notes
Core claim
ACCORD's central discovery is that autoregressive LLMs can be turned into end-to-end combinatorial optimizers by representing each solution as a sequence of state transitions annotated with cumulative feasibility metrics. For example, a knapsack step is written as an item followed by its running value and weight with an explicit capacity check, so every token position carries the constraints that the partial solution satisfies. The paper reports that an 8B Llama fine-tuned on this representation achieves a 0% optimality gap on BinPack and JSSP at size 5, gaps below 3% for TSP and VRP at most tested sizes, and feasibility improvements of 2 to 25 percentage points over the list-of-lists format, while outperforming GPT-4 prompting baselines on all six tasks. An attention-based router selects problem-specific LoRA adapters from the instruction text, letting one model handle all six problem types.
Load-bearing premise
The reported optimality gaps are measured against OR-Tools heuristic solutions, specifically PATH_CHEAPEST_ARC for routing and NEH for flow-shop, so if those references are far from optimal, the near-zero gaps would not reflect true optimality.
Editorial extensions
If this is right
- ACCORD representation yields higher feasibility than list-of-lists across all six problems, with the largest gain about 24.86 percentage points on FlowShop.
- On size-5 instances, ACCORD with Llama 8B reaches a 0% gap on BinPack and JSSP and under 4% on Knapsack, TSP, and VRP, with gaps staying low as instance size grows.
- ACCORD beats GPT-4 prompting baselines including IO, CoT, SR, LtM, and SGE on all evaluated tasks and sizes, without executing solver code.
- Scaling from a 1B to an 8B model reduces the average optimality gap from 6.54% to 4.48%, with the largest relative gains on routing problems.
- The method transfers to standard benchmarks such as Taillard flow-shop and job-shop instances, reporting average gaps between roughly 13.7% and 22.1% against conventional heuristics and a learned scheduler.
Reading between the lines
- If the output format is the constraint-enforcement mechanism, the same stepwise cumulative-metric transcript could be ported to other constrained generation tasks such as production planning or API-constrained code synthesis.
- The reported negative correlation between latent distance and feasibility hints that hidden-state proximity to an ACCORD-style manifold could serve as a cheap pre-decoding feasibility filter; this is an inference, not a paper claim.
- A testable extension of the paper's approach is to combine ACCORD transcripts with beam search or constrained decoding, which could lower the 60-sample budget and extend the method to larger instances.
- The 1B model's failure to find feasible JSSP solutions suggests a scale threshold for this representation; mapping that threshold across problem dimensions would be a natural follow-up.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper introduces ACCORD, an autoregressive output representation and architecture for fine-tuned LLMs that aims to solve six NP-hard combinatorial optimization problems (TSP, VRP, Knapsack, FlowShop, JSSP, BinPacking). The representation interleaves feasibility metrics with incremental solution steps, and an attention-based router selects problem-specific LoRA adapters. The authors train Llama 3.1 8B and Llama 3.2 1B models on a new ACCORD-90k dataset generated with OR-Tools (and NEH for FSSP), and report that ACCORD improves feasibility and optimality gap over list-of-list fine-tuning and over prompting baselines including GPT-4 with code interpreter. The paper also presents ablations on model scale and a latent-space analysis claiming a correlation between representation distance and feasibility.
Significance. The central idea—encoding cumulative feasibility state into the autoregressive output stream—is a plausible and potentially useful contribution for LLM-based combinatorial optimization, and the public release of code and the ACCORD-90k dataset is a concrete asset. If the comparative feasibility results are reproducible, the paper offers a practical improvement over naive list-of-list fine-tuning. However, the headline optimality claims are currently not supported because the reported gaps are computed against the same heuristics used to generate training targets, and the main comparison table omits one of the six claimed tasks and lacks error bars or statistical tests. The significance of the result therefore depends on whether the optimality claims can be re-anchored to stronger reference solutions or appropriately weakened.
major comments (4)
- [Section 4.1, Eq. (3), Table 1] The optimality gap defined in Eq. (3) uses the OR-Tools value as the denominator, and Section 4.1 states that TSP/VRP solutions were produced with PATH_CHEAPEST_ARC and FSSP solutions with the NEH heuristic. Because these same heuristic outputs are used as training targets, a 0% gap in Table 1 means the model exactly reproduced the heuristic solution, not that the solution is optimal or near-optimal. The claim in Section 6.1 that ACCORD 'achieves optimal solutions on smaller instances' is therefore not supported. Please either evaluate against exact or substantially stronger reference solutions (e.g., Concorde or LKH for TSP, exact CP-SAT for small VRP, and optimal flow shop solvers for small instances), or explicitly reframe the numbers as 'gap to the training heuristic'.
- [Table 1, Section 6.1] Table 1 is presented as a comparison across six tasks, but its columns cover only Knapsack, BinPack, TSP, VRP, and JSSP; FlowShop is missing despite being listed in the abstract and Section 7. In addition, the asterisks on the ACCORD entries are never explained. The table also reports no error bars, no number of independent runs, and no seeds, so the reader cannot assess whether the differences between ACCORD and SGE (e.g., 3.9% vs. 8.1% at size 5) are within noise. Please add the missing FlowShop column or justify its absence, explain the asterisks, and provide variance estimates or at least multiple-seed results.
- [Section 6.1, Eq. (3), Figure 1] The inference pipeline selects the 'best' of 60 feasible solutions, and Section 6.1 states that the best solution is chosen as the one with the lowest optimality gap. Because the optimality gap is computed against the OR-Tools reference, this selection uses the label during evaluation. In a real deployment the reference is unavailable, so the reported numbers represent an oracle-selection upper bound. Please clarify this explicitly, or additionally report results where the best solution is selected using only information available to the model (e.g., shortest reported tour length for TSP/VRP, lowest makespan for scheduling, highest value for knapsack).
- [Section 4.1, Appendix A.1, Table 2] The reference solver used for dataset generation differs across problems: CP-SAT for JSSP, branch-and-bound for Knapsack, but PATH_CHEAPEST_ARC for TSP/VRP and NEH for FSSP. Consequently the 'gap' values in Table 2 and Figure 2 are not comparable across problems: for TSP/VRP/FSSP they measure distance to a heuristic, while for JSSP/Knapsack they measure distance to (near-)optimal solutions. This should be stated clearly for each row, and the cross-problem average in Table 2 should either be restricted to problems with comparable references or interpreted with this caveat.
minor comments (3)
- [Throughout, Appendix A] There are several typographical errors, including 'percantage', 'avalable', 'familer', 'deimentionality', and 'Nvdidia' (in Section 6); these should be corrected.
- [Section 6.2] The reported correlation between latent distance and feasibility is r = -0.1082 with p = 0.0155. Although nominally significant, the effect size is very small and explains only about 1% of the variance; the statement that 'LLMs encode constraint satisfaction geometrically' is too strong for this evidence. Please temper the conclusion or provide additional evidence such as stronger effect sizes on more instances.
- [Figure 2 and Appendix A.1] In Figure 2, the 'No Data' label is defined only in the caption as 'failed to generate any feasible solution within a sampling budget of 60', but this is easy to miss; consider adding a legend entry or a note in the main text. Also, the training details in Appendix A.1 list 'Number of epochs: 1' twice while Section 6 states two epochs; please reconcile.
Circularity Check
Table 1's 'optimality gap' is computed against the same OR-Tools/PATH_CHEAPEST_ARC and NEH outputs used as training targets, so 0% gaps show heuristic imitation, not optimality.
-
fitted input called prediction
[Section 4.1 (dataset generation); Section 6.1, Eq. (3); Table 1]
"TSP & VRP: ... OR-Tools solved these using the 'PATH_CHEAPEST_ARC' strategy. ... FSSP: ... Solutions were generated with the NEH heuristic [23]. ... The optimality gap is defined as Gap = (Model Value − OR-Tools Value)/(OR-Tools Value) (3), where a lower gap indicates a better solution. ... ACCORD consistently outperforms prompting strategies across all 6 combinatorial optimization tasks, and achieves optimal solutions on smaller instances."
The 'OR-Tools Value' in Eq. (3) is exactly the solver output used as the supervised training target in Section 4.1: for TSP/VRP this is the PATH_CHEAPEST_ARC construction heuristic and for FSSP the NEH heuristic. Therefore Gap=0 means the fine-tuned model reproduced the training-label generator, not that it found a true optimum; PATH_CHEAPEST_ARC and NEH are known to be suboptimal on many instances. The Table 1 entries '0.0*' and the text 'achieves optimal solutions on smaller instances' thus reduce, by construction, to measuring imitation of the heuristic that produced the labels. The asterisk is never explained. The feasibility comparison (Fig. 3) is independent, but the absolute optimality half of the central claim is not.
full rationale
The paper's core mechanism—ACCORD's cumulative-feasibility output format, dynamic LoRA routing, and the fine-tuning protocol—is not circular: the router is a classifier trained on instruction text, the LoRA adapters are fitted to OR-Tools solutions, and feasibility is measured by constraint checking of parsed outputs. The feasibility ablation (Fig. 3) and the comparison against prompting baselines are legitimate supervised-learning evaluations. The single circular element is the optimality metric. Section 4.1 generates training labels with OR-Tools, using PATH_CHEAPEST_ARC for TSP/VRP and NEH for FSSP; Eq. (3) then defines 'optimality gap' against 'OR-Tools Value.' For those problems the reference value is a heuristic, not an optimum, so 0.0* gaps in Table 1 and the sentence 'achieves optimal solutions on smaller instances' are, by construction, statements about copying the heuristic. The unexplained asterisks compound this. This is a partial circularity: it affects the absolute optimality claims and the interpretability of Table 1, but not the representation/feasibility contribution. Reference [1] is a self-citation by the same authors but is used only as related-work context and is not load-bearing. The unverified sentence about Taillard/TAI/DMU benchmarks points to independent evidence, but no supplementary data is present. Accordingly, score 6.
Assumptions & free parameters
assumptions (4)
- domain assumption OR-Tools PATH_CHEAPEST_ARC (TSP/VRP) and NEH (FSSP) produce valid, sufficiently high-quality solutions to serve as training targets and as the reference for 'optimality gap'.
- domain assumption The generated ACCORD text can be parsed reliably to extract items, cumulative totals, and feasibility status.
- domain assumption The attention-based router classifies each problem instance into the correct task with high accuracy, so the correct LoRA adapter is activated.
- domain assumption The synthetic instance distributions (sizes 5 to 100, random coordinates, demands, and processing times) are representative enough that in-distribution results transfer to the claimed generalization on Taillard and DMU benchmarks.
Cite this review
Pith. "Pith review of ACCORD: Autoregressive Constraint-satisfying Generation for COmbinatorial Optimization with Routing and Dynamic attention." pith.science (2026). https://pith.science/paper/4EITLLIX
@misc{pith2026250611052,
author = {Pith},
title = {Pith review of: ACCORD: Autoregressive Constraint-satisfying Generation for COmbinatorial Optimization with Routing and Dynamic attention},
year = {2026},
howpublished = {\url{https://pith.science/paper/4EITLLIX}},
note = {Machine review of arXiv:2506.11052}
}
read the original abstract
Large Language Models (LLMs) have demonstrated impressive reasoning capabilities, yet their direct application to NP-hard combinatorial problems (CPs) remains underexplored. In this work, we systematically investigate the reasoning abilities of LLMs on a variety of NP-hard combinatorial optimization tasks and introduce ACCORD: Autoregressive Constraint-satisfying generation for COmbinatorial optimization with Routing and Dynamic attention. ACCORD features a novel dataset representation and model architecture that leverage the autoregressive nature of LLMs to dynamically enforce feasibility constraints, coupled with attention-based routing to activate problem-specific LoRA modules. We also present the ACCORD-90k supervised dataset, covering six NP-hard combinatorial problems: TSP, VRP, Knapsack, FlowShop, JSSP, and BinPacking. Extensive experiments demonstrate that our ACCORD model, built on an 8B-parameter Llama backbone, consistently outperforms standard prompting and input-output methods, even when compared to much larger LLMs, such as gpt-4. Ablation studies further show that our output structure enhances solution feasibility. To the best of our knowledge, this is the first large-scale, end-to-end framework for exploring the applications of LLMs to a broad spectrum of combinatorial optimization problems. The codes are publicly available at https://github.com/starjob42/ACCORD
Figures
Figures from the paper (2 more)
Forward citations
Cited by 1 Pith paper
-
Large Language Models for Next-Generation Wireless Network Management: A Survey and Tutorial
A survey and tutorial that organizes LLM-enabled wireless network optimization into formulation, solution, and verification stages, with case studies drawn from the authors' own prior papers.
Reference graph
Works this paper leans on
-
[1]
H. Abgaryan, T. Cazenave, and A. Harutyunyan. Starjob: Dataset for llm-driven job shop scheduling. In ArXiv Preprint arXiv:2503.01877v1, 2024
arXiv 2024
-
[2]
Shifting bottleneck procedures for job shop scheduling
James Adams, Elias Balas, and David Zawack. Shifting bottleneck procedures for job shop scheduling. In Management Science, volume 34, pages 391–401. INFORMS, 1988
work page 1988
- [3]
-
[4]
Unsloth: Accelerated fine-tuning for large language models, 2024
Unsloth AI. Unsloth: Accelerated fine-tuning for large language models, 2024. Accessed: 2024-11-19
work page 2024
-
[5]
Sample-Efficient Optimization over Generative Priors via Coarse Learnability
Pranjal Awasthi, Sreenivas Gollapudi, Ravi Kumar, and Kamesh Munagala. Combinatorial optimization via llm-driven iterated fine-tuning. arXiv preprint arXiv:2503.06917, 2025
work page Pith review arXiv 2025
-
[6]
Language models are few-shot learners
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems , 33:1877–1901, 2020
1901
-
[7]
Palm: Scaling language modeling with pathways
Aakanksha Chowdhery, Sharan Narang, Jacob Devlin, Maarten Bosma, Gaurav Mishra, Adam Roberts, Paul Barham, Hyung Won Chung, Charles Sutton, Sebastian Gehrmann, et al. Palm: Scaling language modeling with pathways. Journal of Machine Learning Research, 24(240):1– 113, 2023
2023
-
[8]
Benchmarks for shop scheduling problems
Ebru Demirkol, Sanjay Mehta, and Reha Uzsoy. Benchmarks for shop scheduling problems. European Journal of Operational Research, 109(1):137–141, 1998
work page 1998
Show all 35 references
-
[9]
Genetic algorithms in scheduling
M Goel et al. Genetic algorithms in scheduling. In International Conference on Genetic Algorithms, 1996
1996
-
[10]
Google’s or-tools
Google. Google’s or-tools. https://developers.google.com/optimization/. Accessed: 2024-05-07
2024
-
[11]
LoRA: Low-rank adaptation of large language models
Edward J Hu, yelong shen, Phillip Wallis, Zeyuan Allen-Zhu, Yuanzhi Li, Shean Wang, Lu Wang, and Weizhu Chen. LoRA: Low-rank adaptation of large language models. In International Conference on Learning Representations , 2022
2022
-
[12]
Huang, P
W. Huang, P. Abbeel, D. Pathak, and I. Mordatch. Improving the reasoning capabilities of large language models in complex tasks. In Proceedings of the International Conference on Machine Learning, 2022
2022
-
[13]
Huang et al
W. Huang et al. Large language models for vehicle routing: A prompting-based approach. In Proceedings of the Conference on Empirical Methods in Natural Language Processing , 2024
2024
-
[14]
Self-guiding exploration for combinatorial problems
Zangir Iklassov, Yali Du, Farkhad Akimov, and Martin Takáˇc. Self-guiding exploration for combinatorial problems. In Advances in Neural Information Processing Systems 37 (NeurIPS 2024), 2024
2024
-
[15]
A rank stabilization scaling factor for fine-tuning with lora, 2023
Damjan Kalajdzievski. A rank stabilization scaling factor for fine-tuning with lora, 2023
2023
-
[16]
Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song
Elias B. Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial optimization algorithms over graphs. In Advances in Neural Information Processing Systems , 2017
2017
-
[17]
Attention, learn to solve routing problems! In International Conference on Learning Representations , 2019
Wouter Kool, Holger van Hoof, and Max Welling. Attention, learn to solve routing problems! In International Conference on Learning Representations , 2019
2019
-
[18]
Complexity of machine scheduling problems
Jan K Lenstra, A Rinnooy Kan, and P Brucker. Complexity of machine scheduling problems. Annals of Discrete Mathematics, 1:343–362, 1979
1979
-
[19]
Large language models as evolutionary optimizers
Shengcai Liu, Caishun Chen, Xinghua Qu, Ke Tang, and Yew-Soon Ong. Large language models as evolutionary optimizers. arXiv preprint arXiv:2310.19046, 2023. 11
2023 arXiv
-
[20]
Self-refine: Iterative refinement with self-feedback
Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, et al. Self-refine: Iterative refinement with self-feedback. Advances in Neural Information Processing Systems , 36:46534–46594, 2023
2023
-
[21]
Exploring combinatorial problem solving with large language models: A case study on the traveling salesman problem using gpt-3.5 turbo
Mahmoud Masoud, Ahmed Abdelhay, and Mohammed Elhenawy. Exploring combinatorial problem solving with large language models: A case study on the traveling salesman problem using gpt-3.5 turbo. arXiv preprint arXiv:2405.01997, 2024
2024 arXiv
-
[22]
Puzzlebench: Can llms solve challenging first-order combinatorial reasoning problems? arXiv preprint arXiv:2402.02611, 2024
Chinmay Mittal, Krishna Kartik, Mausam, and Parag Singla. Puzzlebench: Can llms solve challenging first-order combinatorial reasoning problems? arXiv preprint arXiv:2402.02611, 2024
2024 arXiv
-
[23]
Emory Enscore, and Inyong Ham
Muhammad Nawaz, E. Emory Enscore, and Inyong Ham. A heuristic algorithm for the m- machine, n-job flow-shop sequencing problem. Omega, 11(1):91–95, 1983
1983
-
[24]
Applying deep learning to the newsvendor problem
Afshin Oroojlooyjadid, Lawrence V Snyder, and Martin Taká ˇc. Applying deep learning to the newsvendor problem. Iise Transactions, 52(4):444–463, 2020
2020
-
[25]
Machine scheduling by mathematical programming
R Roy and G Sussmann. Machine scheduling by mathematical programming. In Journal of the Operational Research Society, volume 15, pages 352–362. JORS, 1964
1964
-
[26]
Benchmarks for basic scheduling problems
Eric Taillard. Benchmarks for basic scheduling problems. European Journal of Operational Research, 64(2):278–285, 1993
1993
-
[27]
Lamda: Language models for dialog applications
Romal Thoppilan, Daniel De Freitas, Jamie Hall, Noam Shazeer, Apoorv Kulshreshtha, Heng- Tze Cheng, Alicia Jin, Taylor Bos, Leslie Baker, Yu Du, et al. Lamda: Language models for dialog applications. arXiv preprint arXiv:2201.08239, 2022
2022 arXiv
-
[28]
Valmeekam, A
K. Valmeekam, A. Olmo, S. Sreedharan, and S. Kambhampati. A benchmark for evaluating planning and reasoning in large language models. In NeurIPS F oundation Models for Decision Making Workshop, 2022
2022
-
[29]
Optimizing small- scale surgery scheduling with large language model
Fang Wan, Julien Fondrevelle, Tao Wang, Kezhi Wang, and Antoine Duclos. Optimizing small- scale surgery scheduling with large language model. In Proceedings of the 21st International Conference on Informatics in Control, Automation and Robotics (ICINCO) , pages 223–228, Lisbon...
2024
-
[30]
Emergent abilities of large language models
Jason Wei, Yi Tay, Rishi Bommasani, Colin Raffel, Barret Zoph, Sebastian Borgeaud, Dani Yogatama, Maarten Bosma, Denny Zhou, Donald Metzler, et al. Emergent abilities of large language models. arXiv preprint arXiv:2206.07682, 2022
2022 arXiv
-
[31]
Chain-of-thought prompting elicits reasoning in large language models
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fei Xia, Ed Chi, Quoc V Le, Denny Zhou, et al. Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems , 35:24824–24837, 2022
2022
-
[32]
C. Yang, X. Wang, Y . Lu, H. Liu, Q.V . Le, and X. Chen. Optimization by prompting: Leveraging large language models for combinatorial optimization. arXiv preprint arXiv:2309.03409, 2023
2023 arXiv
-
[33]
Zhang, W
C. Zhang, W. Song, Z. Cao, J. Zhang, P.S. Tan, and C. Xu. Learning to dispatch for job shop scheduling via deep reinforcement learning. In Advances in Neural Information Processing Systems, 2020
2020
-
[34]
Automatic chain of thought prompting in large language models
Zhuosheng Zhang, Aston Zhang, Mu Li, and Alex Smola. Automatic chain of thought prompting in large language models. arXiv preprint arXiv:2210.03493, 2022
2022 arXiv
-
[35]
list of list
Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuurmans, Claire Cui, Olivier Bousquet, Quoc Le, et al. Least-to-most prompting enables complex reasoning in large language models. arXiv preprint arXiv:2205.10625, 2022. 12 A Technical Append...
2022 arXiv
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Sign in to comment.