ACCORD: Autoregressive Constraint-satisfying Generation for COmbinatorial Optimization with Routing and Dynamic attention

Henrik AbgaryanLAMSADE, Université Paris Dauphine-PSLParis, France [email protected], Tristan CazenaveLAMSADE, Université Paris Dauphine-PSLParis, France [email protected], Ararat HarutyunyanLAMSADE, Université Paris Dauphine-PSLParis, France [email protected] · 2025

Read ACCORD: Autoregressive Constraint-satisfying Generation for COmbinatorial Optimization with Routing and Dynamic attention by Henrik AbgaryanLAMSADE, Université Paris Dauphine-PSLParis, France [email protected], Tristan CazenaveLAMSADE, Université Paris Dauphine-PSLParis, France [email protected], Ararat HarutyunyanLAMSADE, Université Paris Dauphine-PSLParis, France [email protected] (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-11052.txt.

Introduction

Henrik Abgaryan, Tristan Cazenave, and Ararat Harutyunyan teach a language model to solve hard packing and routing tasks, in work from 2025. Such tasks, called combinatorial problems, ask for the best plan among a vast set of options. Language models can reason in words, but no one had pressed them far on this class.

Their model, ACCORD, builds an answer step by step and blocks any step that breaks the rules. A routing trick wakes a small tuned module that fits the task at hand. The team trained it on 90,000 worked cases across six tasks, from travel routes to bin packing. The 8-billion-part model beat plain prompts and even much larger models. Checks showed the step form is what keeps answers valid.

Catalog record

CREATORHenrik AbgaryanLAMSADE, Université Paris Dauphine-PSLParis, France [email protected], Tristan CazenaveLAMSADE, Université Paris Dauphine-PSLParis, France [email protected], Ararat HarutyunyanLAMSADE, Université Paris Dauphine-PSLParis, France [email protected]
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE42 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2506-11052

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

ACCORD: Autoregressive Constraint-satisfying Generation for COmbinatorial Optimization with Routing and Dynamic attention Henrik AbgaryanLAMSADE, Université Paris Dauphine-PSLParis, France [email protected], Tristan CazenaveLAMSADE, Université Paris Dauphine-PSLParis, France [email protected], Ararat HarutyunyanLAMSADE, Université Paris Dauphine-PSLParis, France [email protected] 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 : A utoregressive C onstraint-satisfying generation for CO mbinatorial optimization with R outing and D ynamic 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 1 1 footnotetext: Equal contribution. 1 Introduction Large Language Models (LLMs) have rapidly established themselves as versatile engines for reasoning across a broad spectrum of tasks, encompassing arithmetic, commonsense logic , thoppilan2022lamda , chowdhery2023palm , brown2020language . Among the prominent strategies enabling such capabilities is the Chain-of-Thought approach, which allows these models to decompose complex problems into sequential, interpretable steps wei2022chain . Recent efforts have sought to adapt these reasoning techniques to address more advanced optimization tasks. Combinatorial optimization problems (CPs) are decision-making challenges where the goal is to select an optimal arrangement or subset from a large, discrete set of possibilities. Classic examples include the Traveling Salesman Problem (TSP), Vehicle Routing Problem (VRP), and Job Shop Scheduling Problem (JSSP), which have widespread applications in logistics, manufacturing, and artificial intelligence lenstra1979complexity . Due to their NP-hard nature, even moderately sized instances possess a combinatorial explosion of potential solutions, rendering brute-force approaches infeasible. As a result, practical methods typically rely on heuristics or approximation algorithms to provide near-optimal solutions within reasonable time frames. As NP-hard problems, CPs present huge obstacles in practical settings oroojlooyjadid2020applying . Presently, the predominant paradigm in industry relies on metaheuristic algorithms—sophisticated combinations of simple, efficient heuristics—for solving CPs under various constraints. However, the success of these heuristics is often highly sensitive to the specific structure and requirements of each problem, necessitating tailored approaches for optimal results. Figure 1 : Overview of the ACCORD inference pipeline. As an example, a knapsack problem described in natural language is provided as input, then Attention based Dynamic router 5 activates the corresponding LoRA layer specialized for knapsack tasks. Multiple candidate solutions are generated via sampling, each checked for feasibility. The best feasible solution is returned as the final output. Note that the pipeline generalizes to other combinatorial problems in the same manner; knapsack is shown here for illustration. At the same time, investigations into leveraging LLMs for combinatorial problem solving have revealed significant research gaps. While the latest breakthroughs highlight the promise of LLMs in diverse reasoning scenarios abgaryan2024starjob , SGE , wei2022emergent , zhang2022automatic , their full potential in the context of combinatorial optimization remains largely untapped. Applying LLMs directly to these problems presents unique challenges: LLMs are trained primarily for natural language generation, not for enforcing strict combinatorial constraints, leading to issues such as hallucinations (plausible but infeasible solutions) huang2022improving , lack of optimality, and limited interpretability valmeekam2022benchmark . Furthermore, the absence of systematic search or explicit constraint mechanisms means LLM outputs can violate feasibility or fail to improve upon prior attempts. Recent advances have begun to explore the application of large language models (LLMs) to combinatorial optimization (CO). Numerous prompting-based approaches have been tested on CO tasks yang2023optimization ; huang2024large ; Mittal2024 ; wei2022chain ; zhou2022least ; madaan2023self ; SGE , demonstrating progress in solution quality and constraint handling. However, to date, there has been no comprehensive study evaluating a unified fine-tuned LLM-based framework for NP-hard CO problems across multiple domains. In this work, we address this gap by introducing ACCORD ( A utoregressive C onstraint-satisfying generation for CO mbinatorial optimization with R outing and D ynamic attention), a novel framework for testing the reasoning capabilities of LLMs on combinatorial optimization problems. Our main contributions are as follows: (i) We propose the ACCORD-90k supervised dataset for TSP, VRP, Knapsack, FlowShop, JSSP, and BinPacking, employing an ACCORD representation that explicitly encodes problem constraints by leveraging the autoregressive nature of LLMs;(ii) we develop a model architecture that leverages attention-based dynamic routing and specialized Low-Rank Adaptation (LoRA) modules for different CO tasks; (iii) extensive ablation studies demonstrate that our method achieves lower optimality gaps and higher solution feasibility than both the traditional list-of-lists representation and state-of-the-art prompting techniques (including GPT-4 with the Code Interpreter enabled). Notably, it achieves substantial improvement percantage difference in feasibility over the list-of-list representation, with gains of 24.86% in FlowShop, 7% in JSSP, 4% in Knapsack, and 2% in BinPacking, 10% in VRP and TSP, problems. To the best of our knowledge, this is the first work to demonstrate large-scale, end-to-end combinatorial problem solving with LLMs, offering new directions for testing symbolic reasoning and optimization within language models. 2 Related Work 2.1 Heuristic and Machine Learning Approaches on CO problems Combinatorial optimization has been tackled with both heuristic and exact methods. Simple priority dispatching rules (PDRs), such as shortest processing time or earliest due date, are computationally efficient but often yield suboptimal solutions due to their greedy nature lenstra1979complexity . Metaheuristics (e.g., simulated annealing, tabu search, genetic algorithms) offer improved solution quality, and exact approaches like the shifting bottleneck procedure adams1988shifting , mixed-integer programming, and constraint programming can find optimal solutions for small instances, though at high computational cost roy1964machine ; goel1996genetic . Recently, machine learning, particularly deep reinforcement learning (RL) and graph neural networks (GNNs) have advanced combinatorial optimization zhang2020learning ; khalil2017learning ; kool2019attention . RL methods treat scheduling as sequential decision making, learning dispatching policies via environment interaction zhang2020learning . GNNs encode jobs and machines as nodes, enabling permutation-invariant representations and, when combined with RL, can model complex dependencies khalil2017learning . Attention-based and sequence-to-sequence models further enhance performance on tasks like TSP and VRP, often utilizing iterative refinement kool2019attention . 2.2 Large Language Models in Combinatorial Optimization The advent of LLMs has introduced new paradigms for CO. Early work explored whether LLMs could generate solutions through prompting yang2023optimization , huang2024large , Mittal2024 , wei2022chain zhou2022least , madaan2023self , SGE . Prompting-based strategies, such as OPRO, involve iterative refinement based on feedback, while methods for VRP employ self-debugging and verification to enhance feasibility huang2024large . However, scalability remains a challenge, as even strong prompting techniques struggle on larger or more complex instances Mittal2024 . Recent research has explored a variety of prompting strategies to leverage LLMs for solving combinatorial optimization (CO) problems. The Input-Output (IO) method presents the LLM with multiple examples of input and corresponding

Read the complete text