Multi-Action Self-Improvement For Neural Combinatorial Optimization
Authors: Laurin Luttmann
Lin Xie
Venue: ICLR 2026 Poster (2026)
Keywords: Neural Combinatorial Optimization
Self-improvement learning
Multi-agent Combinatorial Optimization
Multi-agent coordination
Bipartite matching
Primary area: reinforcement learning
TL;DR: MACSIM introduces a multi-action self-improvement framework for neural combinatorial optimization that jointly predicts multi-agent actions and exploits permutation symmetries, achieving faster generation and better solutions on several benchmarks

Abstract: Self-improvement has emerged as a state-of-the-art paradigm in Neural Combinatorial Optimization (NCO), where models iteratively refine their policies by generating and imitating high-quality solutions. Despite strong empirical performance, existing methods face key limitations. Training is computationally expensive, as policy updates require sampling numerous candidate solutions per instance to extract a single expert trajectory. More fundamentally, these approaches fail to exploit the structure of combinatorial problems involving the coordination of multiple agents, such as vehicles in min-max routing or machines in scheduling. By supervising on single-action trajectories,  they fail to exploit agent-permutation symmetries, where distinct sequences of actions yield identical solutions, hindering generalization and the ability to learn coordinated behavior.

We address these challenges by extending self-improvement to operate over joint multi-agent actions. Our model architecture predicts complete agent-task assignments jointly at each decision step. To explicitly leverage symmetries, we employ a set-prediction loss, which supervises the policy on multiple expert assignments for any given state. This approach enhances sample efficiency and the model's ability to learn coordinated behavior. Furthermore, by generating multi-agent actions in parallel, it drastically accelerates the solution generation phase of the self-improvement loop. Empirically, we validate our method on several combinatorial problems, demonstrating consistent improvements in the quality of the final solution and a reduced generation latency compared to standard self-improvement.

Published as a conference paper at ICLR 2026
MULTI-ACTION SELF-IMPROVEMENT FOR NEURAL COMBINATORIAL OPTIMIZATION
Laurin Luttmann
Lin Xie
Leuphana University Lüneburg
Brandenburg University of Technology
laurin. 1uttmannn wwpphana de
1 in. x xieeb-tu..de
ABSTRACT
Self-improvement has emerged as a state-of-the -orte-- paradigm in Neural Combina- torial Optimization (NCO), where models iteratively refine their policies by gener- ating and imitating high-quality solutions. Despite strong empirical performance, existing methods face key limitations. Training is computationally expensive, policy updates require sampling numerous candidate solutions per instance to ex- tract single expert trajectory. More fundamentally, these approaches fail ex- ploit the structure of combinatorial problems involving the coordination of mul- tiple agents, such as vehicles in min-max routing or machines in scheduling. By supervising single-action trajectories, they fail to exploit agent-permutation symmetries, where distinct sequences of actions yield identical solutions, hinder- ing generalization and the ability to learn coordinated behavior.
We address these challenges by extending self- improvement to operate over joint multi-agent actions. Our model architecture predicts complete agent-task assign- ments jointly at each decision step. To explicitly leverage symmetries, employ a set-prediction loss, which supervises the policy on multiple expert assignments for any given state. This approach enhances sample efficiency and the model's ability to learn coordinated behavior. Furthermore, by generating multi-agent ac- tions in parallel, drastically accelerates the solution generation phase of the self- improvement loop. Empirically, we validate our method on several combinatorial problems, demonstrating consistent improvements in the quality of the final solu- tion and a reduced generation latency compared to standard self-improvement.
INTRODUCTION
End-to-end constructive Neural Combinatorial Optimization (NCO) has emerged as a powerful framework for solving combinatorial optimization (CO) problems by casting them as sequential Markov Decision Processes (MDPs), where a neural policy constructs solutions step by step (Ben- gio et al., 2021). Reinforcement Learning (RL)-based methods have proven especially effeettve in this setting, enabling models to learn solution strategies through interaction rather than relying on pre-existing expert data (Bello al., 2017; Kool et al., 2019; K Kwon al., 2020; Kim et al., 2022).
Despite their flexibility, traditional RL. approaches in NCO face significant challenges. The sparse reward signals inherent to combinatorial optimization where meaningful objective is avail- able only upon solution completion - have largely limited training to the REINFORCE algorithm (Williams, 1992) and variants (Kool al., 2019; Kim al., 2022: Kwon al., 2020). Since these methods require backpropagation through the entire solution trajectory, the resulting high memory requirements and risk of gradient instability have encouraged a "heavy-encoder, light-decoder" ar- chitectural paradigm. In this setup, a static representation of the initial problem is generated once and used for all subsequent decisions. This becomes a critical bottleneck, as fails to reflect the evolving problem state, often resulting in suboptimal decisions in the later stages of solution con- struction (Drakulic et al., 2023; Luo et al., 2024). Recently, self-improvement methods have of- fered a compelling solution to these issues (Pimna & Grimm, 2024: Corsini et al., 2024). During training, these algorithms generate numerous solutions for a given problem instance, identify the best- performiffggggg trajectory, and use it the policy is trained on individual statc-action pairs along this expert trajectory, it enables the use of more powerful, decoder-only architectures that can dynamically re-encode the state at each step.
eseudo-expert example for imitation learning. Because

---

Published as a conference paper at ICLR 2026
However, this next-token prediction approach of self-improvement faces fundamental limi- tation in multi-agent CO problems, where mul- tiple decision entities (agents) must plan and co- ordinate their actions achieve shared ob- jective. These problems often exhibit agent- permutation symmetries, meaning that differ- ent permutations of agent-task assignments can yield identical solutions. For example, in ve- hicle routing, assigning driver I to location A and then driver to location B leads to the same overall route as the reverse assignment or- der (Figure 1). However, by supervising the policy on single "best" next action per state, self-improvement implicitly enforces an arbi- trary agent order and treats the remaining symmetric choices errors. This reduces sample ef- ficiency and limits the model's ability to learn coordination in multi-agent settings, thus limiting generalization performance.
Agest
Agent
Agent
Agent
Agent
Agmmt
Agent
Figure 1: Example for agent-permutation sym- metry. Both trajectories have the same solution.
To address these limitations, this paper introduces MACSIM -a Multi-ACtion Self- Seff-Improvement Method. MACSIM extends the self-improvement paradigm by incorporating a multi-agent policy that predicts joint assignments for all agents in parallel at each decision step. To explicitly lever- age problem symmetries, we employ a set-prediction loss, which allows the policy learn from multiple equivalent expert assignments for a given state. This design promotes agent coordination, improves sample efficiency, and significantly accelerates solution generation. We demonstrate the effectiveness of MACSIM several challenging combinatorial optimization tasks spanning both routing and scheduling domains. Our key contributions are as follows:
We propose MACSIM, novel learning paradigm for cooperative multi aageit combinato- rial optimization problems that achieves better empirical results with lower solution gener- ation latency compared to standard self-improvement methods.
We develop new solution generation scheme that models the entire joint-agent action space in a single forward pass thus fostering coordination and avoids conflicts between agents through an autoregressive sampling algorithm.
We introduce a permutation-invartie surrogate loss function for imitation learning on ex- pert multi-action trajectories, which stabilizes and accelerates the training process.
2 RELATED WORKS
The application of deep learning to CO problems pioneered by the Pointer Network (Vinyals et al., 2015), which was trained via supervised learning to autoregressively construct solutions for the Traveling Salesman Problem (TSP). This paradigm was quickly adapted to RL, removing the dependency on optimal solutions as training data and thus improving scalability (Bello et al., 2017; Nazari et al., 2018). A major architectural advance came with transformer-basee policies leveraging self-attention (Vaswani et al., 2017), leading to substantial performance gains (Kool et al., 2019).
A common strategy in these REINFORCE- putationally expensive encoder once per problem instance and use the resulting embeddings in lightweight, iterative decoder. While efficient, this "encode-once" approach has been shown gen- eralize poorly to have explored alternative strategies, such as re-encoding the state at each decoding step (Drakulic et al., 2023; Luo et al., 2024), learning diverse set of policies improve performance at test time (Grinsztajn et al., 2023; Hottung et al., 2025), or abandoning autoregressive decoding entirely in favor of heatmap-based (Joshi et al., 2019; Fu al., 2021; Qiu et al., 2022; Ye al., 2023) or diffusion-based methods (Sun& & Yang. 2023; Li et al., 2023; 2024).
methods (Williams, 1992) is to apply com-
instances (Manchanda et al., 2022). In response, recent works
Self Self-improvement learning has recently emerged need for expert solutions (Corsini et al., 2024; Pirnay & Grimm, 2024). Inspired by elite sampling from cross-entropy methods (Boer al., 2005), these approaches sample multiple solution trajec-
powerful training paradigm that bypasses the
2

---

Published as a conference paper at ICLR 2026
tories, identify the best-perforinng one "pseudo-expert" and train the policy to imitate this target via next-token prediction. However, this approach assumes a unique optimal action per step, which is often violated in CO problems that exhibit symmetries (Cappart et al., 2023). In such cases, foreing the model to follow a single sequence reduces solution diversity and impairs generalization.
Several lines of research have focused explicitly exploiting symmetries. POMO (Kwon al., 2020) and Sym-NCO (Kim et al., 2022) leverage the cyclic symmetry of the TSP by training on rollouts from all possible starting nodes and using their averaged returns compute a low-variance baseline. More recently, DPN (Zheng et al., 2024) generalized this concept to multi-agent problems like the min-max VRP, where the order of agent routes is commutaatio-invariinn DPN samples multiple agent orderings and computes an tettt--eeton-mymmnaaaaae gradient variance and accelerates convergence by avoiding redundant learning.
baseline, which reduces
We extend self-improvement to explicitly leverage these structural symmetries in multi-agent CO problems. In contrast to PARCO, which resolves conflicts post-hoc, and DPN, which reduces vari- ance through permutation-invarian baselines, MACSIM generates coordinated and conflict-free as- signments directly and learns with set-based loss, leading to more robust symmetry-aware policies.
3 PRELIMINARIES
NCO typically involves a reformulation of the respective CO problem into Markov Decision Process (MDP), where solution т to a problem instance x is constructed over a finite horizon t == I...., The current configuration of the problem at time step t is encoded in the state 81 E S, which typically represents all information in a graph G = {V, E,E,w), w). with N nodes V. edges & C V V/ and edge weights w & R (Khalil et al., 2017). At each step, policy wæ with learnable weights I selects an action a E V based on 8t, and the transition function yl updates the state to S(+1 (Khalil et al., 2017). Due to the sequential structure of MDPs, NCO commonly adopts autoregressive (AR) policies that generate actions step by step, conditioned on prior deci- sions. Classical approaches trained via REINFORCE typically encode only the initial state so using a graph neural network, while the policy operates autoregressively from this encoding. In contrast, self- seff-improvement methods enable training at the action level, allowing the policy to encode inter- mediate states 8, and use decoder-only architectures defined as P(T xs; 0) = I'= no(a; 8t).
In this work, we specifically target CO problems that can be framed as a cooperative multi-agent MDP (MMDP or Markov Game) with M agents sharing a common reward (Boutilier, 1996). Agents correspond to decision entities executing tasks, such as machines in scheduling problems or vehicles in routing. The state 5t of the problem can be defined by a bipartite graph G = M, E, w). where V is the set of nodes (tasks), M is the set of agents, and edges & S . x V denote feasible agent- task assignments, each associated with a cost w : E + RR
At each step t, the policy To maps the state s, to bipartite matching a, {at Je= between agent and tasks. Each element at (m², 2k) denotes the assignment of task U2 to agent mg. where no two agents can be assigned to the same task. Given a matching a, E ., with A the space of valid matchings, the problem transitions from 8 to 8t+1 according to transition function ei SS A + S, until a complete solution T is obtained. The transition function is assumed order-invariant, meaning it depends only on the final matching a,, receive a shared reward observed only at terminal states, where the return R(T, x) equals the negative value of the CO objective for the complete solution.
the order in which assignments are produced. Agents
4 MULTI-ACTION SELF-IMPROVEMENT
4.1 MULTI-AGENT POLICY
The permutation invariance of the transition function with respect to joint agent-task assignments induces symmetries over agent orderings. Standard self-improvementt typically ignores this structure by assuming a single best action per time-step. In contrast, our approach leverages these agent- permutation symmetries by learning policy that generates complete joint agent-task assignments a, instead of single next actions a, = (m, v). To this end, MACSIM utilizes a multi-agent policy that directly maps the current state 8, to a joint agent-action assignment a, This policy first encodes
3

---

Published as a conference paper at ICLR 2026
Generation
Decode solutions with current best policyy x;
Instance
Current Best
Policy
Joint Logits
Autoregressive Sampling
State Update
Update improved
Validation
Target
P(a: ags 0)
Update set-bosod
Sample
Select best solution and add stato-action pairs {st, 1E,,, to dataset
Dataser
Policy
VC
loss Cox
(+,,
Figure 2: Overview of MACSIM. It generates joint acctinn logits in parallel through a multi- agent policy and autoregressively samples from them to generate complete agent-task assignments. The policy is used to sample & solutions, where the best serves as training example. A set-based loss function is used to train the policy on pseudo-expert multi-agent actions for a given state.
the bipartite input graph 9 into agent embeddings HM E R Mxd and task embeddings Hy E Nxd Based on these embeddings, it computes matrix of unnormalized logits L E IR BNN,,, where each entry I. represents the compatibility score for assigning task e to agent m. For full architectural details of the policy network, we refer the reader to Appendix B.
While the idea of multi-agent policies NCO not novel, existing approaches either sample only once from the resulting joint-distribution (Liu al., 2024), thus discarding learned inter-agent cor- relations as well as potential efficiency gains through multi-step prediction. Or, they assume inde- pendence across agents by normalizing L per agent and sampling independently from the resulting marginal distributions. However, this independence assumption does not hold, leading to subop- timal coordination and conflicts, where agents happen select the same action. PARCO (Berto et al., 2024) resolves conflicts by post-hoc resolution mechanism, prioritizing agents with larger log- oog-robabbilities while leaving others idle. Yet, since agents are modeled independently through different marginal distributions, effective coordination does not take place.
4.2 MULTI-ACTION GENERATION
To address this, we introduce an autoregressive sampling procedure, that utilizes the joint-logits L from the neural policy to sequentially sample agent-action pairs from their joint distribution without replacement. To this end, the probability of generating a specific sequence a is factorized using the chain rule of probability:
M
P(a L) II P P(mek, Ve.k a L)
(1)
k=
where a 1 vt.1)..... (7,,6-1,V denotes the sequence of previous assignments in the construction of a,. This formulation casts the selection of each agent-task pair as a step in sequence, where the choice at step conditioned on all prior assignments. Specifically, let MA and V% be the sets of agents and tasks, respectively, available at step k, with Mj M and V== V. At each step E (l....,M, M). the policy samples a feasible and available agent-task pair, (ma, vx. E & C E, where & = & (M& x Vx), from categorical distribution with probabilities proportional to their scores Lmc.ve:
exp(Lmme.v
P(a (mz, Uk) a <k L)
Emm a/ exp(Lmm',,')
After sampling of (m&. Uk). the sets for the next step updated via M M {m&} and Vs+1 = 1/2 \ { and the process continues until all agents are assigned to task. We summarize this sampling process, which guarantees the generation of valid matching a,, in Algorithm 1. The validity of the resulting distribution is formally stated as follows:
Proposition 1.
The function P(a, L) defined by the autoregressive process in Equations 1 and a valid probability distribution over the space of all possible ordered agent-task task matchings.
proof for Proposition can be found in Appendix A.
4

---

Published as a conference paper at ICLR 2026
The injectivity constraint implies that earlier as- sigmments reduce the set available actions for subsequent agents, making the generation process order-sensitive, even though the final solution is sermutaaion-invariinn. Our autore- gressive approach explicitly models this depen- dency: the joint softmax normalization dynami- cally integrates coordination, since the denomi- nator depends on all remaining agent-task task pairs.
Algorithm Joint Action Sampling from L
Require: Score matrix L
RMxx feasible pairs & Ensure: a= [(mi, 01) vi),,........................v.. (m., ewr)
1:
Initialize empty sequence
2:
for l: = 1 M do
3:
P(m, v)
softmax(Lm.x (m.u)EE
Normalize
4:
(ma, Uk) ~
D Sample from joint dist.
5:
a + all (mx, v6)
D Append Mask
High logits for pair (m", v²) implicitly reduce
6: Ling: f -00;
L, + -00
the probability the same task, allowing the policy to prioritize favorable assignments and avoid conflicts with-
competing agents choosing
7:
end for
8: return
out relying on heuristics or post hoc conflict resolution, PARCO does.
Substituting the definition of P(a, L) from Equation (I) into the decoder-only policy of Section yields the following definition of our MACSIM policy:
T
M
P(T 8c: = II (L 8x) II P(a a <k
LL)
In this formulation, the joint logits L are computed only once by the computationally expensive neu- ral policy me, after which M actions are generated using fast autoregressive sampling procedure. As result, MACSIM can construct solutions significantly faster than fully autoregressive models, as we demonstrate in the experimental section of this paper.
4.3
SKIP TOKEN
The generative model defined by Equation (3) requires each agent to select action at every de- cision step. However, enforcing task assignments for all agents at every step can suboptimal, particularly in problems with strong inter-agent dependencies. In job-shop scheduling, for instance, the set of available jobs for a machine likely changes as other machines schedule operations. In such cases, it may be beneficial for an agent to wait until more favorable task becomes available.
Therefore, we introduce a dummy action, referred to as the skip token. The skip token is a transient action that can be chosen by any agent any time, allowing them to wait until the next decision step without modifying the current solution. To encourage efficient solution construction, each use of the skip token incurs small penalty added to the objective value. Empirically, this penalty toward zero during training yields the best performance. This strategy encourages the policy increasingly prioritize generating high-quality solutions as training progresses. We exam- ine the effect of the skip token in Table 3 and provide more details and analyses in Appendix D.3.
find that annealing
Technically, the skip token is implemented as a learnable embedding h RRd which is added to the set of all task embeddings Hy. Unlike other actions, the skip token can be selected by multiple agents, with the only restriction that least one agent selects an actual task.
4.4 POLICY LEARNING
We train MACSIM with two-stage self- self-improvement framework, similar to Pirnay & Grimm (2024) and Corsini et al. (2024). In the first stage, the current best policy zø generates > solutions for each problem instance æ. We select the best solution with respect to the objective value plus the penalty term for skip token usage, and add the state-action pairs (($1, af)..... (#T: a7)) corresponding to the solution 7* to the training dataset. In the second stage, the policy network updated via imitation learning on these pseudo-expert trajectories.
Unlike prior work that predicts single "token" from partial solution, we aim maximize the likelihood of the policy producing the entire expert multi-agent action at given the state 8t The corresponding negative logllikelihood (NLL) under our generative process of Equation (1) is:
M
M
exp( (m)
PML = log P(mx, U/ a =
Σ log k=
(4)
E(m w' v'EE exp(Lme..))
5

---

Published as a conference paper at ICLR 2026
However, direct optimization with LML is problematic. As detailed in Appendix E, its primary flaw is conflicting gradient signals: each term in the sum assumes one assignment is correct at a given step and consequently penalizes all others, including those that occur later in the expert assignments.
A first step to mitigate this issue is to utilize the agent order from the expert assignment. By assuming fixed agent order m" (ma1.... mass the choice of agent at step & becomes deterministic. Thus, P(m+ a */²²) 1 and the probability P(Uk. my a, a²*)) can be factorized as P(uk mg, *
transforming the generative process into a Plackett-Luce (PL) model (Volkovs & Zemel, 2012). 2). Its
NLL computes the loss over the marginal distributions for each agent, preventing gradient conflicts:
M
Σ log exp(Lmm..z) k=1
M
Cp1. Σ
log P(uk Tig a 2
(5)
Ev'En exp( (1)((n),.)))
While this improves gradient stability, the loss remains sensitive to the permutation of the expert sequence. However, every permutation of the assignments in a" yields the same solution, which should be reflected in the loss function. Ideally, this would be achieved by averaging the Plackett- Luce loss over all possible M! agent orderings, which computationally intractable. Therefore, we employ a surrogate loss by relaxing the sequential dependence assumption for the loss calculation and treating each agent-task pair in an expert matching as independent supervised instance with conditional probability P I m). This is justified because the expert data consist only of valid matchings, making unnecessary to enforce the injectivity constraint within the loss itself. This is analogous to bipartite matching in object detection (Carion et al., 2020), where the assignment between predictions and ground-truth objects first established algorithmically, and losses are then computed independently for each matched pair. The resulting surrogate is defined as the cross- entropy (CE) loss summed over all agents:
expl (LMg,EE)
LCE Σ log P( m4) =
Σ log Ever exp (xp((L)gerr)
This surrogate is inntitatiioninviianntn computationally efficient, and provides a more robust train- ing signal as we will validate empirically the experimental section. Moreover, we provide a thorough analysis of Ler in Appendices E and F.
5 EXPERIMENTS
We assess the effectiveness of MACSIM on representative multi-agent CO problems, spanning rout- ing and scheduling domains. Specifically, we evaluate MACSIM two challenging scheduling problems- the flexible job shop scheduling problem (FJSP) and the flexible flow shop problem (FFSP) as well as common routing problem, the heterogeneous capacitated vehicle routing prob- lem (HCVRP). We compare MACSIM with common and SOTA solvers for the respective CO prob- lems and the self-improvement method (SLIM) of Corsini et al. (2024); Pirna & Grimm (2024).
5.1 PROBLEMS
Flexible Job Shop Scheduling Problem. The FJSP is concerned with scheduling N jobs on M machines (agents). Fach job consists of sequence of operations that must be executed in fixed order. Unlike the classical job shop problem, each operation in FISP can be processed by a subset of eligible machines M₁ C M,, with machine-dependent processing times, resulting in a combined routing (assigning operations to machines) and sequencing problem (ordering operations on each machine). The common objective to minimize the makespan of the resulting schedule. The formal mathematical model and the MMDP formulation of the FJSP are presented in Appendix C.1.
To evaluate the performance on the FJSP, we compare MACSIM against several baselines. First, we include OR-Tools, a state-of-the-art CP-SAT solver widely applied in scheduling (Col & Tep- pan, 2019). We also benchmark against classical priority dispatching rules FIFO (Firt In First Out), MOR (Most Operations Remaining), and MWKR (Most Work Remaining) commonly used in manufacturing scheduling (Montazeri & Wassenhove, 1990). Lastly, we consider learning-based approaches, including graph neural network trained via Proximal Policy Optimization (PPO) pro- posed by Song et al. (2022), and the dual attention model DANIEL (Wang et al., 2023).
"Source code available https: // thwb, com www.t/tttttttttmm....mm

---

Published as a conference paper at ICLR 2026
Flexible Flow Shop Scheduling Problem. The FFSP involves scheduling N jobs that must pass through S sequential processing stages. The key challenge lies in the flexibility at each stage. which contains M parallel machines; a job can be processed by any available machine within a stage. The objective is to determine the assignment and sequence of jobs on machines to minimize the makespan. A detailed problem formulation for the FFSP is provided in Appendix C.2.
We compare MACSIM against traditional baselines - Gurobi (Gurobi Optimization, LLC, 2025), Genetic Algorithm (Hejazi & Saghafian, 2005), and Particle Swarm Optimization (Singh & Ma- hapatra, 2012) - as well as neural baselines: MatNet (Kwon et al., 2021), PolyNet (Hottung et al., 2025), and PARCO (Berto al., 2024).
Min-Max Heterogeneous Capacitated Vehicle Routing Problem. The HCVRP is a challenging extension of the classical CVRP, designed to capture more realistic logistics and transportation sce- narios. In HCVRP, fleet of heterogeneous vehicles, each with distinct capacities and travel costs, is responsible for serving a set of customer demands. The objective differs from standard CVRP: in- stead of minimizing the total cost or distance, the goal is to minimize the maximum route length (or workload) among all vehicles, ensuring a balanced distribution of effort across the fleet. A detailed mathematical formulation for the min-max HCVRP is provided in Appendix C.3.
For the HCVRP, we employ two well-known heuristic baselines: Simulated Annealing (ilhan, 2021) and SISR (Christiaens & Berghe, 2020), a state-of-the-ar heuristic for solving the CVRP and vari- ants. Neural baselines involve 2D-Ptr (Liu et al., 2024), and DPN (Zheng et al., 2024).
(ET) (Son et al., 2024), DRL, (Li et al., 2022),
5.2 EXPERIMENTAL RESULTS
We present the main empirical results in Table 1, which reports test-set performance of the eval- uated methods in terms of average objective values (Obj.), gaps to the best-known solutions, and average inference latency for a single instance. For neural baselines, we report performance under both greedy (g.) and sampling (s.) decoding, with the latter evaluated using 1,280 sampled solutions (more details on the experimental setup can be found in Appendix H). MACSIM consistently out- performs neural baselines across all problem types and sizes, surpasses all methods on FFSP, and substantially reduces the gap to OR-Tools on FJSP, even outperforming it on 20 x 5 instances.
Compared to SLIM, the advantage of MACSIM increases with the number of agents, as shown in Figure 3b for the HCVRP and FFSP. In addition, MACSIM significantly reduces inference time compared to SLIM. For FFSP 30 4 instances, SLIM requires nearly ten times longer than MACSIM to generate a solution. This difference grows with the number of agents, shown in Figure 3c, which illustrates the number of forward passes needed by each policy to construct a solution and the resulting inference times. MACSIM requires only fraction of the construction steps used by SLIM, and this advantage further increases with the number of agents due to its multi-agent policy.
While MACSIM is not necessarily the fastest among the neural solvers evaluated here, slower in- ference times compared to other methods can be attributed to the fact that, like SLIM, MACSIM performs step-wise re-encoding of the problem state. As discussed in previous work, this enables better generalization to -fito--distribution instances (e.g., Luo et al. (2024)). Table 2 validates this by evaluating models trained on the small FJSP instances of Table on larger instances, where MACSIM outperforms all neural baselines and even OR- Tools on two out of three instance types.
We also conduct an ablation study assess the impact of MACSIM's components. First, Figure 3a evaluates MACSIM with different sequence generation modes. While "MACSIM-flI" refers to the generative model defined by Equation (3) with the sequential sampling algorithm described in Al- gorithm 1, in random or fixed order, respectively, given logits L. The results in Figure 3a and table 3 highlight the effectiveness of the proposed sampling procedure, particularly on instances with many agents. Moreover, Table 3 confirms the importance of the skip token, which proves especially beneficial in larger instances where coordination among agents is more challenging. Although the skip token increases generation latency, it substantially improves solution quality. A more detailed analysis of the skip token and its penalty is provided in Appendix D where provide more experiments.
and "MACSSM-fieed-rdde"" denote variants where agents act
7

---

Published as a conference paper at ICLR 2026
Table I: Test set performance of MACSIM and baselines on FISP, FFSP, and HCVRP. Best obj.
values found by any solver are shown in bold; grey backgrounds indicate the best neural solver.
EJSP
N x M
10 x
20 x
15 x 10
Metric
Obj.
Gap
Time (s.)
Obj.
Gap
Time (8.)
Obj.
Gap
Time (8.)
OR-Tools
96.32
0.00%
1597
188.15
0.03%
1800
143.53
0.00%
1724
119.4
23.96%
14.88%
0.32
184.55
MOR
115.38
19.79%
0.16
214.16
13.85%
0.32
173.15
20.64%
0.51
MWKR
113.23
17.56%
0.16
209.78
11.53%
0.32
171.25
19.31%
0.50
PPO (g.)
111.67
15.94%
0.45
211.22
12.29%
1.43
166.92
16.30%
1.35
DANIEL (g.)
106.71
10,79%
0.45
197.56
5.03%
0.94
161,28
12.37%
1.43
SLIM (g.)
103.85
7.82%
0.91
194.37
3.33%
1.18
154.32
7.62%
MACSIM (g.)
102.21
6.12%
0.44
191.08
1.58%
0.76
149.84
4.40%
1.32
PPO
105.59
9.62%
1.11
207.53
10.33%
2.36
160.86
12.07%
6.42
DANIEL (5.)
101.67
5.55%
0.74
192.78
2.49%
1.87
153.22
6.75%
6.10
SLIM (s.)
98.74
2.51%
2.32
189.08
0.52%
6.91
149.02
3.82%
20.08
MACSIM (x.)
97.64
1.37%
0.86
188.10
0.00%
2.28
145.95
1.69%
6.19
FFSP
N
20 x 4 x
50 4 x
100 x 4
Metric
Obj.
Gap
Time (s.)
Obj.
Gap
Time (s.)
Ohj.
Gap
Time (8.)
Gurobi (600s)
31.61
31.93%
600
600
600
Genetic Algorithm
31.15
30.01%
21.05
56.92
19.23%
44.82
99.25
13.79%
89.20
Particle
21.45%
46.17
15.42%
82.46
97.30
11.56%
MatNet (g.)
27.26
13.77%
1.22
51.52
7.92%
2.17
91.58
5.00%
4.97
PolyNet (g.)
26.71
11.48%
1.69
51.01
6.85%
2.45
91.22
4.59%
5.21
PARCO (g.)
26.31
9.81%
0.26
51.19
7.23%
0.52
91.29
4.67%
0.89
SLIM (g-)
26.18
9.27%
0.86
50.01
4.75%
3.36
91.97
5.45%
5.14
MACSIM (g.)
25.75
0:28
3.39%
89.88
1.86%
MaiNet
25.43
6.14%
3.88
4.06%
89.72
2.87%
PolyNet (s.)
24.98
4.26%
5.04
49.23
3.12%
9.24
89.21
2.28%
19.29
PARCO (6.)
24.78
3.42%
0.99
49.27
3.20%
1.97
89.46
2.57%
4.04
SLIM (s.)
24.19
0.96%
1.55
48.13
0.82%
10.21
89.50
2.61%
19.01
MACSIM (x.)
23.96
0.00%
0.49
47.74
0.00%
0.91
87.22
0.00%
3.60
HCVRP
N M
60 x
80 3
100 x
Metrie
Obj.
Gap
Time (S.)
Obj.
Gap
Time (s.)
Obj.
Gap
Time (8.)
SISRs
6.57
0.00%
478
8.52
0.00%
750
10.29
0.00%
1084
Simulated Annealing
7.04
7.15%
382
7.63%
561
11.13
8.16%
(g.)
7,58
15.37%
0.28
14.55%
14.09%
DPN
7.46
13.54%
0.28
9.66
13.38%
0.40
11.48
11.56%
0.46
DRLA (g.)
7.43
13.09%
0.34
9.64
13.15%
0.46
11.44
11.18%
0.58
2D-Ptr (g.)
7.20
9.59%
0.20
9.24
8.45%
0.27
11.12
8.07%
0.31
SLIM (x.)
7.19
9.44%
0.63
9.25
8.57%
0.87
11.10
7.87%
MACSIM (g))
7.39%
7.09%
(6.)
7.14
8.68%
0.52
7.86%
0.66
11.20
8.84%
1.02
DPN (6.)
7.03
7.00%
0.55
9.16
7.51%
0.71
11.03
7.19%
1.08
DRL (5.)
6.97
6.09%
0.73
9.10
6.81%
1.10
10.90
5.93%
1.48
2D-Ptr (s)
6.82
3.81%
0.32
8.85
3.87%
0.44
10.71
4.08%
0.55
SLIM (x.)
4.75%
2.40
4.69%
3.31
10.81
5.05%
MACSIM (x.)
2.89%
1.65
3.05%
3.69%
SLIM
MACSISS-Eu1
Jog, (90) 5E.33 idatre 1080
HCVRP 00)
33.0 Bkge
SUM
SUM (m
</6 peanty
5/h peatts
Roquted constmmch (0nc3)
Infereuce tine in scc (bac)
155
120
110
Number Agests
30x
FRAF N
(a)
(b)
(c)
Figure 3: Left: Validation performance (makespan) on FISP 10 x 5 instances during training under different sequence generation strategies. Middle: Average performance gap of SLIM relative to MACSIM across varying numbers of agents. Right: Inference efficiency comparison, reporting construction steps (lines, right axis) and inference time to generate a solution (bars, left axis).
8

---

Published as a conference paper at ICLR 2026
Table 2: Generalization performance of MACSIM and baseline solvers on larger FJSP instance distributions not seen during training.
FJSP
M
20 x 10
30 10
40 x 10
Metric
Obj.
Gap
Time (s.)
Obj.
Gap
Time (s.)
Obj.
Gap
Time (s.)
Oo-Tools
195,98
3.14%
1800
274.67
0.00%
1800
365. 666.9
0.08%
1800
(g.)
215.78
13.56%
1.91
312.59
13.81%
416.18
13.81
3.82
DANIEL (g.)
198.50
4.46%
1.85
281.49
2.48%
2.76
371.45
1.58%
3.81
SLIM (g.)
195.89
3.09%
3.11
281.87
2.62%
4.57
374.13
2.31%
6.03
MACSIM (g.)
192.15
1.12%
1.19
276.01
0.49%
1.71
365.87
0.05%
2.27
PPO (x.)
214.81
13.05%
6.23
308.55
12.33%
12.79
410.76
12.33%
24.54
DANIEL (s.)
193.91
2.05%
6.35
279.20
1.65%
12.37
370.08
1.21%
21.09
SLIM (s.)
194.19
2.19%
28.15
281.42
2.46%
69.97
373.70
2.20%
139.30
MACSIM (x.)
190.02
0.00%
6.79
275.48
0.29%
14.12
365.67
0.00%
27.13
Table 3: Ablation study on MACSIM components
Table 4: Comparison of Loss Functions
FJSP
FJSP
FFSP
N X M
10 x
15
10
N M
10 5
20 x
20 x 12
50 x 12
Metric
Obj.
Time
Obj.
Time
Metric
Obj.
Obj.
Obj.
Obj.
MACSIM-full (s.)
97.64
0.86
145.95
6.19
CSA (s.)
98.81
189.18
24.29
49.58
w/o AR AR- AR-sampling Bixed
98.97
0.76
155.13
3.97
LML (s.)
98.13
188.97
24.15
49.02
random (s.)
98.66
0,78
150.72
CPL (s.)
97.99
188.81
24.08
47.90
w/o skip-token (s.)
98.69
0.75
159.65
3.89
LCE (s.)
97.64
188.10
23.96
47.74
Finally, Table 4 compares the loss functions from Section 4.4, along with the single-agent cross- entropy loss LSA defined in Appendix E. Our surrogate set-based cross-entropy loss consistently achieves the best performance on both FJSP and FFSP.
6 CONCLUSION
We presented MACSIM, a novel self-improvement framework tailored for multi-agent CO prob- lems. Instead of predicting single next token, MACSIM learns multi-agent policy that emits joint agent-task logits in one forward pass and then samples a valid matching autoregressively without replacement. This design captures inter-agent dependencies, prevents conflicts by construction, and amortizes policy computation over multiple assignments, drastically accelerating solution genera- tion. second key ingredient a permutation permutationninvaaiinn,, invariant, set-based learning objective. By supervis- ing on the set of expert agent-tast pairs rather than a single agent's 's next step. MACSIM explicitly exploits peeettpermutttion symmetries, avoids gradient conflicts inherent single-action imitation, and promotes coordinated behaviors. A skip token combined with an annealed penalty further en- ables agents to defer actions when beneficial while keeping construction efficient.
Empirically, MACSIM achieves state-of-the-art results challenging scheduling and routing benchmarks, consistently improving solution quality. By leveraging the structural symmetries of multi-agent problems, approach enhances both the performance and scalability of neural solvers, making self-improvement practical for complex, real-world optimization tasks. Overall, MACSIM advances self- self-improvement for multi-agent CO by unifying joint-action modeling and symmetry- aware learning, yielding a more coordinated, generalizable, and practical solver.
Limitations and Future Work. Although MACSIM substantially improves inference and training time (see Figure 6 for training times) compared to standard self-improvement, its reliance step- wise encoding results in slower generation than some lightweight neural solvers, which may hinder applicability in latency-critical settings. Future work will therefore focus on further reducing gen- eration latency through more efficient policy architectures. A promising direction is to encode and cache the initial problem state once, and then incrementally update embeddings the state evolves, rather than re-encoding the entire graph at each step. This strategy could retain MACSIM's ability to leverage multi-agent symmetries while reducing both memory and computational overhead.

---

Published as a conference paper at ICLR 2026
REPRODUCIBILITY STATEMENT
To facilitate reproducibility of our results, we provide complete access to our implementa- tion, model weights, and training configurations. The source code is available at https: //github. Sttm/LLuttmatnnmmmeete
and the trained model weights along with all con- figuration files used in our experiments can be found at https::/tet //off 1o/5z2aj/ [o2aj/?viex ?view_ only=783b0bb> e8e 64444444 64434446660 fe21fdd3352ea72 O. Detailed descriptions of model architec- tures, training procedures, and experimental setups are provided in the main paper and appendix. These resources together ensure that our experiments can be independently reproduced.
REFERENCES
Irwan Bello, Hieu Pham, Quoe V. Le, Mohammad Norouzi, and Samy Bengio. Neural combinatorial optimization with reinforcement learning. arXiv preprint 1rX19:1611.09940 2017.
Yoshua Bengio, Andrea Lodi, and Antoine Prouvost. Machine learning for combinatorial opti- mization: methodological tour d d'horizon. European Journal of Operational Research, 290(2): 405 2021.
Federico Berto, Chuanbo Hua, Laurin Luttmann, Jiwoo Son, Junyoung Park, Kyuree Ahn, Changhyun Kwon, Lin Xie, and Jinkyoo Park. Parco: Learning parallel autoregressive policies for efficient multi-agent combinatorial optimization. arXiv preprint arXiv:2409 03811, 2024.
Federico Berto, Chuanbo Hua, Junyoung Park, Laurin Luttmann, Yining Ma, Fanchen Bu, Jiarui Wang, Haoran Ye, Minsu Kim, Sanghyeok Choi, et al. RLACO: an extensive reinforcement learning for combinatorial optimization benchmark. Proceedings of the 31st ACM SIGKDD Conference Knowledge Discovery and Data Mining V. 2, pp. 5278-5289, 2025.
Pieter-Tjerk De Boer, Dirk P. Kroese, Shie Mannor, and Reuven Y. Rubinstein. A tutorial on the cross-entropy method. Annals of Operations Research, 134:19-67, 2005.
Craig Boutilier. Planning, learning and coordination in multiagent decision processes. TARK, volume 96, pp. 195-210, 1996.
Paolo Brandimarte. Routing and scheduling in a flexible job shop by tabu search. Annals of Opera- tions Research, 4173)1157-183 1993.
Quentin Cappart, Didier Chételat, Elias B. Khalil, Andrea Lodi, Christopher Morris, and Petar Veličković. Combinatorial optimization and reasoning with graph neural networks. Journal of Machine Learning Research, 24(130):1-61, 2023.
Nicolas Carion, Francisco Massa, Gabriel Synnaeve, Nicolas Usunier, Alexander Kirillov, and Sergey Zagoruyko. End-to-end object detection with transformers. In European Conference on Computer Vision, pp. 213-229. Springer, 2020.
Jan Christiaens and Greet Vanden Berghe. Slack induction by string removals for vehicle routing problems. Transportation Science, 54(2)4417433, 2020.
Giacomo Da Col and Erich C. Teppan. Industrial size job shop scheduling tackled by present day CP solvers. Principles and Practice of Constraint Programming: 25th International Confer- ence, CP 2019, Stamford, CT, USA, September 30 October 4, 2019, Proceedings, pp. 144-160. Springer- Verlag, 2019. doi: 10.1007/978-3-00 5--030-30048-15
Andrea Corsini, Angelo Porrello, Simone Calderara, and Mauro Dell' Amico. Self-labeling the job shop scheduling problem. In Advances in Neural Information Processing Systems, volume 37,
pp. 105528- 105551, 2024.
Darko Drakulic, Sofia Michel, Florian Mai, Arnaud Sors, and Jean-Mare Andrcoli. Bq-nco: Bisim- ulation quotienting for efficient neural combinatorial optimization. In Advances in Neural Infor- mation Processing Systems, volume 36, pp. 77416-77429, 2023.
William Falcon and The PyTorch Lightning team. PyTorch Lightning, 2019. URL https:
//gi thub. wwt.m//..ghnnnnnAAa.....
10

---

Published as a conference paper at ICLR 2026
Zhang-Hiu Hua Fu, Kai-Bin Qiu, and Hongyuan Zha. Generalize small pre- mre-trained model arbitrarily large TSP instances. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35 No. 8, pp. 7474-7482, 2021.
Nathan Grinsztajn. Daniel Furelos-Blanco, Shikha Surana, Clément Bonnet, and Tom Barrett, Win- takes it all: Training performant RL populations for combinatorial optimization, In Advances in Neural Information Processing Systems, volume 36, pp. 48485-48509, 2023.
Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2025. URL https://www
gurobi com.
Seyed Reza Hejazi and S. Saghafian. Flowshop-schedulling problems with makespan criterion: review. International Journal of Production Research, 43(14):2895-2929 2005.
Dan Hendrycks and Kevin Gimpel. Gaussian error linear units (gelus). arXiv preprint
arXiv:1606.084 08415, 2016.
André Hottung, Mridul Mahajan, and Kevin Tiemey. Polynet: Learning diverse solution strategies for neural combinatorial optimization. In Y. Yue, A. Garg, N. Peng, E. Sha, and R. Yu (eds.), International Conference on Representation Learning, volume 2025, pp. 80417-80435, 2025.
Johann Hurink, Bernd Jurisch, and Monika Thole. Tabu search for the job-shop scheduling problem with multi-purpose machines. Operations Research Spektrum, 15(4):205-211 1994.
ilhan Ilhan. An improved simulated annealing algorithm with crossover operator for capacitated vehicle routing problem. Swarm and Evolutionary Computation, 64:100911, 2021.
Chaitanya K. Joshi, Thomas Laurent, and Xavier Bresson. An efficient graph convolutional network technique for the travelling salesman problem. arXiv preprint arXiv: 1906.01227 2019.
Elias Khalil, Hanjun Dai, Yuyu Zhang, Bistra Dilkina, and Le Song. Learning combinatorial op- timization algorithms over graphs. In Advances in Neural Information Processing Systems, vol- ume 30, 2017.
Minsu Kim, Junyoung Park, and Jinkyoo Park. Sym-nco: Leveraging symmetricity for neural com- binatorial optimization. In Advances in Neural Information Processing Systems, volume 35, 2022.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv:1412.69888 69880 2015.
Wouter Kool, Herke van Hoof, and Max Welling. Attention, Learn to Solve Routing Problems! In International Conference on Learning Representations, 2019.
Ycong-Dae Kwon, Jinho Choo, Byoungjip Kim, Iljoo Yoon, Youngjune Gwon, and Seungjai Min. Pomo: Policy optimization with multiple optima for reinforcement learning. In Advances in Neural Information Processing Systems, volume 33, pp. 21188-21198, 2020.
Yeong-Dat Dae Kwon, Jinho Choo, Iljoo Yoon, Minah Park, Duwon Park, and Youngjune Gwon. Matrix encoding networks for neural combinatorial optimization. In Advances in Neural Information Processing Systems, volume 34, pp. 5138-5149, 2021.
Jingwen Li, Yining Ma, Ruize Gao, Zhiguang Cao, Andrew Lim, Wen Song, and Jie Zhang. Deep reinforcement learning for solving the heterogeneous capacitated vehicle routing problem. IEEE Transactions Cybernetics,
2022. doi: 10. 1..1109/TCYB.20211 2.221..11.11111111 111111111822
Yang Li, Jinpei Guo, Runzhong Wang, and Junchi Yan. T2T: From distribution learning in training to gradient search in testing for combinatorial optimization. In Advances in Neural Information Processing Systems, volume 36, pp.
2023.
Yang Li, Jinpei Guo, Runzhong Wang, Hongyuan Zha. and Junchi Yan. Fast T2T: Optimization consistency speeds up diffusion-basee training-to-testing to-testing solving for combinatorial optimization. In Advances Neural Information Processing Systems, volume 37, pp. 30179-30206, 2024.
11

---

Published as a conference paper at ICLR 2026
Qidong Liu, Chaoyue Liu, Shaoyao Niu, Cheng Long, Jie Zhang, and Mingliang Xu. 2D-Ptr: 2D array pointer network for solving the heterogeneous capacitated vehicle routing problem. In the Proceedings the 23rd International Conference on Autonomous Agents and Multiagent Systems,
pp. 1238-1246 2024.
Fu Luo, Xi Lin, Fei Liu, Qingfu Zhang, and Zhenkun Wang. Neural combinatorial optimization with heavy decoder: Toward large scale generalization. In Advances Neural Information Processing Systems, volume 36, 2024.
Laurin Luttmann and Lin Xie. Neural combinatorial optimization heterogeneous graphs: An application to the picker routing problem in mixed-shelves warehouses. In Proceedings of the International Conference on Automated Planning and Scheduling, volume 34, pp. 351-359, 2024.
Laurin Luttmann and Lin Xie. Learning to solve the min-max mixed-shelves picker-routing problem via hierarchical and parallel decoding. arXiv preprint arXiv:2502. 10233, 2025.
Sahil Manchanda, Sofia Michel, Darko Drakulic, and Jean-Mare Andreoli. On the generalization of neural combinatorial optimization heuristics. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pp. 426-442. Springer, 2022.
Mr Montazeri and L. N. Van Wassenhove. Analysis of scheduling rules for an FMS. The Interna- tional Journal of Production Research, 28(4):785-80) 802, 1990.
Mohammadreza Nazari, Afshin Oroojlooy, Lawrence Snyder, and Martin Takáe. Reinforcement learning for solving the vehicle routing problem. In Advances in Neural Information Processing Systems, volume 31, 2018.
Cemal Özgüven, Lale Özbakır, and Yasemin Yavuz. Mathematical models for job-shop scheduling problems with routing and process plan flexibility. Applied Mathematical Modelling, 34(6): 1539- 1548, 2010.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, al. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems, volume 32, 2019.
Jonathan Pimmy and Dominik G. Grimm. Self-improvement for neural combinatorial optimization: Sample without replacement, but improvement. Transactions Machine Learning Research, 2024. ISSN 2835-8856.
Ruizhong Qiu, Zhiqing Sun, and Yiming Yang. Dimes: A differentiable meta solver for combinato- rial optimization problems. In Advances Neural Information Processing Systems, volume 35, pp. 25531-25546, 2022.
Manas Ranjan Singh and S. S. Mahapatra. A swarm optimization approach for flexible flow shop scheduling with multiprocessor tasks. The International Journal of Advanced Manufacturing Techhology, 62:267-2777 2012.
Jiwoo Son, Minsu Kim. Sanghyeok Choi, Hyeonah Kim, and Jinkyoo Park. Equity-Transforme Solving NP-Hard Min-Max Routing Problems as Sequential Generation with Equity Context. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38 No. 18, pp. 20265- 20273, 2024.
Wen Song, Xinyang Chen, Qiqiang Li, and Zhiguang Cao. Flexible job-shop scheduling via graph neural network and deep reinforcement learning. IEEE Transactions on Industrial Informatics, 1902):600-11100, 2022.
Zhiqing Sun and Yiming Yang. Difusco: Graph- diffusion solvers for combinatorial optimiza- tion. In Advances in Neural Information Processing Systems, volume 36, pp. 3706-3731, 2023.
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N. Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. In Advances Neural Infor- mation Processing Systems, volume 30, 2017.
12

---

Published as a conference paper at ICLR 2026
Oriol Vinyals, Meire Fortunato, and Navdeep Jaitly, Pointer networks. In Advances in Neural Information Processing Systems, volume 28, 2015.
Maksims Volkovs and Richard Zemel. Efficient sampling for bipartite matching problems. In Ad- vances in Neural Information Processing Systems, volume 25, 2012.
Runqing Wang, Gang Wang, Jian Sun, Fang Deng, and Jie Chen. Flexible job shop scheduling via dual attention baaee reinforcement learning, IEEE Transactions on Neural Networks and Learning Systems, 35(3):3091-3102 2023.
Ronald Williams. Simple statistical crudient-followiig algorithms for connectionist reinforcement learning. Machine Learning, 8:229-256, 1992.
Haoran Ye, Jiarui Wang. Zhiguang Cao, Helan Liang, and Yong Li. DeepACO: Neural-enhanced ant systems for combinatorial optimization. In Advances in Neural Information Processing Systems, volume 36, pp. 43706 43716844772, 2023.
Zhi Zheng, Shunyu Yao, Zhenkun Wang, Xialiang Tong, Mingxuan Yuan, and Ke Tang. DPN: decoupling partition and navigation for neural solvers of min-max vehicle routing problems. In Proceedings of the 41st International Conference on Machine Learning, ICML'24, JMLR.org. 2024.
13

---

Published as a conference paper at ICLR 2026
A PROOF OF PROPOSITION 1
Proposition
The probability P(a:
L) of generating a specific sequence of agent-task assign-
ments defined by
M
exp(Lmm,.i vve)
P(a:
L)
II
E(m' (m,,, (EEE)) exp (xp(Lmm).e)
a valid probability distribution over the space of all possible ordered agent-task matchings.
Proof. To establish that P(a L) is valid probability distribution over the space Aseq of all dered sequences M agent-task assignments, we demonstrate that satisfies two axioms: (i) non-negativity and (ii) normalization.
Non-negativity. Each term in Equation (7) is mapped into the probability simplex via the softmax function f E - A(E&x) applied to the of available agent-tast pairs & (M V&). By definition of the probability simplex, the softmax yields non-negative values that sum to one. Thus, each conditional probability P(as <k L) is non-negative, and the total probability P(a L), as product of non-negative terms, is also non-negative for any Asey satisfying the non-negativity axiom.
Normalization. To verify normalization, demonstrate that the sum of probabilities over the entire sample space is unity. We expand this sum by expressing it as nested sum over all possible choices at each step of the sequence generation. Using the notation E(a <*) for the set of available choices at step & given the history a <k
we have:
Σ L) REeA.
Σ
II
P(a:
a ck L)
aE k=1
M
Σ
Σ
II
P(as
<k L)
A1EE agEE(an)
(M
k=1
Σ P(a1 L)
Σ a2EE(a1)
P(a2
L)
Σ
Plam <M L)
A1Eg
AMES(aSM)
Consider the sum over all possible assignments for any given history a <k By substituting the definition from Equation 2, have:
exp(Ima.ve)
P(a: (mx, uk) a <* L)= ())
Σ
(mx:R)EE(as)) Eim (*)a((as)) exp(Lm',w)
Σ Emma.w)6E(aact expl Leme
Enme w/) exp( (e))
=
Since Eese Play ca () for any < M, the marginalized sum collapses:
Σ
P(a L) 1x 1
aEAAngg
Thus, the normalization property is satisfied. Since both axioms hold, P(a L) is a valid probability distribution.
14

---

Published as a conference paper at ICLR 2026
B MACSIM POLICY
As defined in Section 3, the problems tackled by MACSIM can be formulated MMDPs, whose states are bipartite graphs consisting of agent and task nodes. MACSIM therefore re- quires an architectural policy backbone, that is capable of encoding such graph structure effec- tively. Our policy is strongly motivated by re- lated works of Kwon et al. (2021); Luttmann & Xie (2024: 2025), who define such architec- tures in the realm of NCO.
Agent
Agent 2
heeriivly Sampling Agent Actions: a {(mp otherrs (mar, sg]}
Lu
by
Lag-1
First, the policy employed in our paper projects the different node-types (agents and tasks) from their distinct feature spaces into mutual em- bedding space of dimensionality d using type- specific transformations W e; for node i of type eG. The features used to represent agents and tasks for the respective problems can be found in Appendix C.
Igg
Igs
Lz
FAN-
Lyg
1xg3
R
xxx
Agent Fmrhedkiigg bus 34
Action Fimbolding by R
Given the initial embeddings H and Hy for agents and tasks, respectively, we use sev- eral layers of self- and cross-attention able message passing between all nodes in the graph. While self-attention is applied indepen- dently to agent and task embeddings follow- ing the Transformer architecture Vaswani et al. (2017), rross-attention allows message passing between agent and task nodes.
Transfomer Encoder Layer
Transdommer Encoder Layer
en-
Add LaverNonu
Add & LayerNom
Cuss-MHA
Chos-MHAA
Q.K.V
Q.K.
LayerNom
LoyerNoon
Formally, to perform cross-attention we com- pute matrix of attention scores A using agent embeddings as queries Q and task embeddings as keys K:
Agest Projections H M
Action Projections HY; N
A QKT
lddee Weights R aa
Agent
Agent 2 O
Lidg Weights
B e 2
vd
where
= Q M
K= K=
Figure 4: MACSIM Policy
and Wº and WK E Rddx are weight matrices learned per attention head and dy is the per- head embedding dimension. The resulting attention scores A IR M can be interpreted as the (learned) compatibility of an agent m and task v. Similar to MatNet Kwon et al. (2021), we fuse these learned attention scores with the edge weights w + R. In FFSP, for instance, the weight w of an edge connecting an agent and task node corresponds to the duration of the respective job on that specific machine. Formally, we concatenate the attention score and the matrix of edge weights E and feed the resulting score vector through multi-layer perceptron MLP: R MxX2 + M with a single hidden layer comprising of units and GELU activation function Hendrycks & Gimpel (2016). Further, we pass the transpose of the attention scores and of the supply matrix A E R XMM through a second MLP to obtain the reverse compatibility Ay-M of tasks u on agents m:
AM- = MLP M [[A]
Ap-M = MLP, ([A |E I),
(8)
The resulting attention scores are then used to compute the embeddings for the nodes of the respec- tive type:
H' softmax MaatmaxxAAM-ia) (AM- Vy = w
(9)
H softmax (AyimnxXAM)MMMMM
VM= W
(10)
For succinetness, we omit the layer and head enumeration
15

---

Published as a conference paper at ICLR 2026
As in Vaswani al. (2017), H'M and H', then augmented through skip connections and layer normalization, before being passed to the self-attention layer, yielding the agent and task embed- dings H'M and Hyy respectively, of the current layer 1.
Given the final agent and task embeddings HM and Hy, respectively, the policy utilized in MAC- SIM uses multiple-pointe mechanism similar to Berto et al. (2024):
QK vd
c tanh
Q = W H.:
K
w (Hy) (kip))
(11)
Dec
with learnable parameters Wios Dec and Wike E Raxd and c is scale parameter, set to 10 following
Bello al. (2017) to enhance exploration.
C PROBLEM DEFINITIONS
C.I FLEXIBLE JOB SHOP SCHEDULING PROBLEM
The Flexible Job Shop Scheduling Problem (FJSP) is a highly complex, NP-hard optimization prob- lem and a generalization of the classical Job Shop Scheduling Problem (ISP). The problem concerns scheduling a set of N jobs on M machines. Each job consists of sequence of operations that must be processed in specific order. The critical distinction from the classical JSP is the "flexibility": each operation can be processed by any machine from a given subset capable machines. This introduces two interdependent decision layers: routing problem (assigning each operation suitable machine) and a sequencing problem (determining the order of operations on each machine). agent
The FJSP can be modeled as a multi-agent CO problem, where each machine acts sponsible for building its own schedule. In an autoregressive framework, a decision is made at each step assign and schedule the next operation, considering machine availability and job precedence constraints. The ultimate goal is typically to find schedule that minimizes the makespan, i.e., the time required complete all operations for all jobs.
C.I.1 MATHEMATICAL MODEL
We present common mixed-integer linear programming (MILP) model for the FJSP, based on the formulation described by Özgüven et al. (2010):
Indices
j,
Job index
i
Operation index
k
Machine index
Parameters
N
Number of jobs
M
Number of machines
O
Set of operations for job j
Mij
Set of machines capable of processing operation of job j
Piyk
Processing time of operation of job j on machine &
B
A very large positive number (for big-M constraints)
Decision variables
Oman
The makespan (maximum completion time) Completion time of operation of job j
Cij
{ 1 if operation i of job is assigned machine k
Tijk
0 otherwise
1 if op (j.t) precedes h) on machine k otherwise
Ujakk
16

---

Published as a conference paper at ICLR 2026
Objective:
min Cmaz
(12)
Subject to:
Cmax 2 Cij
Vj. ViE
(13)
Σ M
Tisk
Vj. ViE
(14)
Cij Σ
PijkTajk 2 ((i-)}
Vj. VA E 03,i>1
(15)
Cjj 4th + (1 - yjakk) 2 Piyk - B Tijk Tink)
Vj, h s.t. <1
(16)
Cij + B Ujilkh 2 Pink B Tijk TINK)
yj,l,i,h,kstt
(17)
Ci 2
Σ
PijkTiih
Vj. V V
(18)
KEMs
The objective function in equation 12 minimizes the makespan. The makespan itself is defined by constraint set equation 13 as being greater than or equal to the completion time of every operation. Constraint set equation 14 is the assignment constraint, ensuring that each operation is assigned to exactly one machine from its set of eligible machines. The chronological sequence of operations within the same job is enforced by constraint set equation 15, which states that operation (j, i) cannot be completed before the completion of its predecessor (j. - 1) plus its own processing time. For the first operation of a job, constraint set equation 18 ensures its completion time is at least its processing time. Constraint sets equation 16 and equation 17 are the core disjunctive constraints that prevent machine from processing more than operation at time. For any operations (j, i) and (z, h) assigned to the same machine k, these "big-M" constraints ensure that one must finish before the other begins. The binary variable yjuzh determines their relative order.
C.1.2 MULTI-AGENT MDP
To solve the FJSP with MACSIM, cast it multi-agent Markov decision process (MDP) as defined in Section 3. In this formulation, we define the state the FISP at construction step f as bipartite graph, where machines correspond the of agents M and jobs/operations to the set of tasks V. An edge (m, v) E exists if machine m can process the next operation of job v, with processing time wmm, v). At each step, each agent m chooses an action a" v from the set of admissible edges (m, v) (or the skip token), which assigns job e's next operation to machine m. The joint action a, {a." MEE induces deterministic transition to 8t+1, which updates the schedule, the job progress, and machine queues. The reward is () for all intermediate steps, with final terminal reward of the negative makespan (-Cmaz) shared between all agents.
C.2 FLEXIBLE FLOW SHOP PROBLEM
The flexible flow shop problem (FFSP) is challenging and extensively studied optimization prob- lem in production scheduling, involving N jobs that must be processed by a total of M machines divided into quence through these stages, but within each stage, any available machine can process the job, with the key constraint that no machine can handle more than one job simultaneously. The FFSP can naturally be viewed as multi-agent CO problem by considering each machine an agent that con- structs its own schedule. Adhering to autoregressive CO, agents construct the schedule sequentially, selecting one job (or no job) at time. The job selected by machine (agent) at a specific stage in the decoding process is scheduled at the earliest possible time, that is, the maximum of the time the job becomes available in the respective stage (i.e., the time the job finished on prior stages) and the machine becoming idle. The process repeats until all jobs for each stage have been scheduled, and the ultimate goal is to minimize the makespan, i.e., the total time required complete all jobs.
S stages, each with multiple machines (M; > 1). Jobs follow a specified se-
17

---

Published as a conference paper at ICLR 2026
C.2.1
MATHEMATICAL MODEL
We the model outlined in Kwon al. (2021) to define the FFSP:
Indices
i
Stage index
j.
Job index
Machine index in each stage
Parameters
N
Number of jobs
S
Number of stages
M;
Number of machines in stage
B
A very large number
Pisk
Processing time of job j stage on machine
Decision variables
Czj
Completion time of job j in stage i
1
if job is assigned to machine k in stage i
Eijk
0 otherwise
1 if job is processed earlier than job j in stage i otherwise
yul
0
Objective:
min
max {ess} f=1..n
(19)
Subject to:
M;
Tiyk
1,....;;;1 = Iy...,A. N (20)
k=1
Yiij
=
0
1,...,,;; = 1,...,N N (21)
N
N
Ms
Σ
Mitj
max Σ (1.gk) 1,0
I.....S s
(22)
1=1
1=1
k=1
Vily S max
max frisk + make 1,0 k=
i= 1=
S; j, 1=..,,,;;;
I....,N N (23)
Σ Vily 1
i= 1= = =1, 1....,N (24)
Vily S 1
I...., 1= 1,...,NN ,, (25)
mi
Pijk Tijk
I,..., N
(26)
M
Gÿ 2 C--1 +
Pijk Tisk
1 2,3 S..,,,S.::
S: j =
I....,N (27)
M;
Gj + B(1 2n1) > cu +
Pijk Tigh
= L, j, 1...,,N N (28)
1=1
18

---

Published as a conference paper at ICLR 2026
Here, the objective function equation 19 minimizes the makespan of the resulting schedule, that is, the completion time of the job that finishes last. The schedule has to adhere to several constraints: First, constraint set equation 20 ensures that each job is assigned to exactly one machine at each stage. Constraint sets equation 21 through equation 25 define the precedence relationships between jobs within a stage. Specifically, constraint relationship with itself. Constraint set equation 22 ensures that the total number of precedence rela- tionships in stage equals N M; minus the number of machines with no jobs assigned. Constraint set equation 23 dictates that precedence relationships can only exist among, jobs assigned to the same machine. Additionally, constraint sets equation 24 and equation 25 restrict a job to having at most one preceding job and one following.jo job.
equation 21 ensures that job has precedence
Moving on, constraint set equation 26 specifies that the completion time of job the first stage must be at least as long as its processing time in that stage. The relationship between the completion times of job in consecutive stages described by constraint set equation 27. Finally, constraint set equation 28 ensures that no more than one job can be processed on the same machine at the same time.
C.2.2 MULTI-AGEN MDP
We formulate the FFSP as a multi-agent MDP. At construction step the state is represented by a bipartite graph: jobs form the task set V, and machines grouped by production stages form the agent set M. Within each stage, an edge (m, v) exists if machine m at that stage eligible to process the next pending operation of job with processing time wm,, v). At each step, each agent m .M selects an action am job operation to that machine. The joint action a, induces deterministic transition to 81+1 by updating the partial schedule, machine queues, and job progression across stages. Intermediate steps yield zero reward, while the terminal state provides reward equal to the negative makespan shared between all agents.
from its admissible edges (m, v), assigning the corresponding
C.3 MIN-MAX HETEROGENEOUS CAPACITATED VEHICLE ROUTING PROBLEM
The min-max heterogencous capacitated vehicle routing problem (HCVRP) is NP-hard combina- torial optimization problem, representing significant extension of the classic Capacitated Vehicle Routing Problem (CVRP). The problem involves designing set of optimal routes for hetero- geneous fleet of vehicles, stationed at a central depot, to serve geographically dispersed set of customers, each with specific demand. The heterogeneity implies that vehicles may differ in their capacities and costs. The primary objective of the HCVRP is to minimize the length (or cost, or duration) of the longest single route the solution, rather than the total length of all routes. This "Min-Max" criterion is crucial for applications where the balance of workload between drivers is priority.
C.3.1 MATHEMATICAL MODEL
We present threc-index vehicle flow formulation for the HCVRP, adapted from standard VRP models as described works such as Li et al. (2022):
Indices
i,j
Node indices (customers and depot) Vehicle index
Sets
L
Set of N customers. indexed 1,..., N
V
Set of all nodes, V L, (0), where is the depot Set of vehicles
K
Parameters
d,
Demand of customer E L
Q
Capacity of vehicle & K
Cijk
Cost (c.g. travel time) for vehicle & to travel between nodes and
19

---

Published as a conference paper at ICLR 2026
Decision variables
Cmax
The maximum route length (the objective)
1 if vehicle i travels directly from node to node j
Tisk
0 otherwise
Continuous variable representing the load of vehicle is after visiting node
Objective:
min Cmaz
(29)
Subject
Cmaax 2 Σ
Σ
Gikhiijk
Wk E K
(30)
iEV JEVANS
Σ Σ
Tijk
VjeL L
(31)
KEK iEV,
E Tihk =
Σ
Thikk
wh E L, AA E K
(32)
jEV
Σ Tojk 1
VKE
(33)
JEL
Usk Uyk + TITH S Qk -dj
Vi,J L, * j. Ak
(34)
d; Σ
Ijth S Uik Qk
Σ TEV
Djsk
L Wk K
(35)
jEV
The objective function eq. (29) minimizes the maximum route cost Cmaz. Cman is defined by constraint set equation 30, which ensures it is greater than or equal to the calculated cost of every individual route, using the vehicle-specific cost parameter Ciyk-
Constraint set equation 31 guarantees that each customer is visited exactly once by one vehicle. The vehicle flow conservation is handled by two sets of constraints. First, constraint set equation 32 ensures that if vehicle enters customer node, it must also depart from it. Second, constraint set equation 33 ensures that each vehicle can leave the depot at most once; combined with constraint set equation 32, this also implies that any vehicle that serves eustomers must return the depot.
Finally, constraint sets equation 34 and equation 35 are the Miller-Tuuker-ZZemlll constraints, which simultaneously prevent subtours and enforce vehicle capacity limits. The continuous variable us tracks the cumulative load of vehicle k. Constraint set equation 34 establishes a valid sequence for load accumulation, while constraint set equation 35 binds the load variable for each customer visit, ensuring it is positive only if the customer is on vehicle k's route and that it never exceeds the vehicle's 's capacity Qk-
C.3.2 MULTI-AGENT MDP
We formulate the HCVRP as a multi-agent MDP where each vehicle is modeled as an agent. The state at construction step consists of a graph with eustomer nodes and vehicles M, where each customer E V has a remaining demand dr... and each vehicle m E M has residual capacity Ct.m and current position on the graph. At each step, each vehicle m selects an action a" corresponding to the next customer to visit, a return to the depot, or stay at the current location, subject to feasibility given its residual capacity and route status. The joint action a, determines the transition to 8t41 by updating vehicle positions, capacities, and customer demands. The shared reward is sparse: intermediate steps yield zero reward, while the final reward defined as the negative of the maximum travel cost among all agents -Ciaar-
20

---

Published as a conference paper at ICLR 2026
Table Generalization performance on public FJSP benchmark instances.
FJSP
Brandimarte
Hurink (rdata)
Hurink (edata)
Hurink (vdata)
Metrie
Obj.
Gap
Time (x.)
Obj.
Gap
Time (s.)
Obj.
Gap
Time (x.)
Obj.
Gap
Time (x.)
OR-
174.20
0.99%
1447
935,80
0.16%
1397
1028,93
0.00%
899
919.60
0.00%
6,39
MWKR
201.70
16.52%
0.49
1053,10
12.72%
0.52
1219.01
18.47%
0.52
952.01
3.52%
0.52
PPO (g.)
198.50
15.07%
1.25
1030.83
10.33%
1182.08
14.88%
1.4
954.33
3.78%
1.37
DANIEL (g-)
184.40
6.90%
1.3
1031.63
10.42%
1.37
1175.53
14.25%
1.37
944.85
2.75%
1.36
SLIM (s.
195.12
13.11%
2.16
1011.15
8.23%
2.28
1170.45
13.75%
2.29
937,04
1.90%
2.28
MACSIM (g.)
185.80
7.71%
1.12
992.10
6. 6.9%
0.87
1168,97
13.61%
0.85
937.07
1.90%
1.04
PEO (.)
190.30
10.32%
4.13
983.33
5.46%
4,81
1116.68
8,53%
4.87
930.80
1.22%
4.72
DANIEL((s) (s.)
180.80
4.81%
4.12
978.28
4.71%
4,73
1119.73
8.82%
4.73
925.40
0.63%
4.77
SLIM
191.20
10.84%
30.75
963.55
3.13%
30.81
1117.50
8.61%
30.82
924.07
0.49%
33.12
MACSIM (x.)
177.30
2.78%
9.78
957.92
2.53%
6.84
1094.85
6.41%
7.05
923.17
0.39%
8.83
D MORE EXPERIMENTS
D.1 PUBLIC BENCHMARK DATASET FOR FJSP
In addition to the synthetic FJSP instances used in Tables and 2, we analyze the generalization capabilities MACSIM on two well-known FJSP benchmarks. First, the Brandimarte benchmark comprises 10 benchmark cases ranging from 10-20 jobs with 3-15 operations each, processed on 4-15 machines with varying machine ficxibility (Brandimarte, 1993). Second, the benchmark from Hurink et al. (1994) contains 120 instances ranging from 6-30 jobs and 6-15 machines, with the number of operations per job matching the machine count. These are categorized into three groups based machine flexibility:
edata: Few operations may be assigned to more than one machine.
rdata: Most of the operations may be assigned to some machines.
vdata: All operations may be assigned to several machines.
The aggregated results for these 4 benchmarks are presented in Table 5. For each instance type, we report results for the best-performing model selected from the models trained on the instance sizes reported in Table 1. MACSIM consistently outperforms all other neural baselines and substantially narrows the gap to the saateoof-the-ar CP-SAT solver, OR-Tools.
D.2 INCREASING THE NUMBER OF AGENTS IN FFSP
We further evaluate all solvers for the FFSP on instances with an increasing number of agents while keeping the number of jobs fixed. Specifically, we consider instances with N = 50 jobs processed across S 3 stages, each containing M; 4. 6, and 8 machines, for total of M 12, 18, and 24 machines, respectively. The results in Table 6 reveal a widening performance gap between standard self- self-improvement (SLIM) and MACSIM. highlighting the importance of exploiting agent symmetries during training. These symmetries become more pronounced in problems with more agents, making coordination increasingly challenging. MACSIM consistently produces policies that achieve superior coordination as the number of agents grows
D.3 ANALYSIS OF THE SKIP TOKEN
In Figure 5a, we evaluate the effect of the skip token and its associated penalty on solution qual- ity. The skip token proves essential for achieving high-quality solutions. However, introducing penalty on its usage initially skews training towards solutions with fewer skip tokens, which results in slightly worse performance compared to MACSIM without the penalty. By annealing the penalty towards zero via an exponential decay, the model ultimately reaches solutions of equal quality while requiring significantly fewer construction steps (forward passes through no), as confirmed in Fig- ure 5b. The different penalty schedules reported in Figure 5b are visualized in Figure Sc.
Although found that the policy is largely insensitive to the specific form of penalty decay, adopt an exponential decay because it naturally prevents the penalty from reaching exactly zero. If the penalty were to reach zero, the model would immediately resume increasing its of the skip
21

---

Published as a conference paper at ICLR 2026
Table 6: Test set performance on FFSP instances with varying number of agents.
FESP
x M, x
x 4
x
x
Metric
Obj.
Gap
Time (s.)
Obj.
Gap
Time (s.)
Obj
Gap
Time (s.)
Shortest Job First
56.94
19.27%
0.37
38.01
23.65%
0.25
29.39
27.45%
0.25
Genetic Algorithm
56.92
19.23%
44.33
38.26
24.46%
47.12
29.05
25.98%
50.95
Particle Swarm Opt.
55.1
15.42%
82.74
36.83
19.81
85.43
28.06
21.68%
89.01
MatNet (g.)
51.52
7,92%
2.17
34,82
13.27%
2.42
27.52
19.34%
2.65
PARCO (g.)
51.19
7.23%
0.52
32.88
6.96%
0.50
24.89
7.94%
0.44
SLIM (g.)
50.01
4.75%
2.28
32.99
7.32%
3.01
25.04
8.59%
3.87
MACSIM (g.)
49.36
3.39%
0.43
32.23
4.85%
0.59
24.45
6.03%
0.61
MatNet (c.)
49.68
4.06%
8.91
33.45
8.82%
9.23
26.00
12.75%
9.81
PARCO (x.)
49.27
3,20%
1.97
31.60
2.80%
1.89
23.59
2.30%
1.68
SLIM (s.)
48.13
0.82%
8.87
31.65
2.96%
24.41
5.85%
10.6
MACSIM (s.)
47.74
0.00%
0.91
30.74
0.00%
1.65
23,06
0.00%
1.78
Expocunttal docay
Fiand pastally
Litsuu deeay
114
penulky
0.22
Fbood, panalty
112
Penely Cpilleee
0,30
No pansally
0.28
No pamiity
104
Fiudl pazally
112
Expermilaal
Linort docap
0022
0.30
10
13 31
10
100
50
100
Epoch
Epocl
Epoch
(1) FJSP 10
(b) FFSP 50 x
(c) FFSP 50 x
Figure 5: Left: Training curves for MACSIM with and without skip token as well as different penalties. Middle: Effect of different penalty strategies on the number of skip tokens used. Right: Skip token penalty coefficient for different strategies over the course of training.
token as shown in Figure 5b. Maintaining a penalty slightly above zero ensures that, when multiple solutions have equal objective values during training data generation, the skip token usage serves as meaningful tie-breaking criterion for the expert data selection. As such, very small penalty still serves as an effective regularizer during the later stages of training.
Moreover, Figure 5b illustrates how the model learns to regulate skip token usage. At the start of training. the model employs the skip token at a relatively low rate. It then rapidly increases its usage, recognizing that deferring decision in FFSP for machines. As training progresses, the model reduces unnecessary skips to avoid the penalty, returning nearly the same skip frequency as the beginning. Crucially, however, the model has now learned to distinguish when deferring an assignment is beneficial and when it is not.
unlock better scheduling opportunities
D.4 TRAINING DYNAMICS ANALYSIS
Figure 6 offers additional insight into the training behavior of MACSIM relative to SLIM across FFSP instances of increasing size. Beyond final performance metrics, these curves highlight funda- mental differences in stability and efficiency. As the problem size grows from N 20 to N 100 jobs, SLIM exhibits increasingly unstable training dynamies, with pronounced oscillations in val- idation performance. In contrast, MACSIM maintains smooth and monotonic convergence. This contrast suggests that SLIM's single-action supervision becomes insufficient for complex coordina- tion tasks, while MACSIM's set-based loss provides more reliable and stable gradient signals.
The comparison of wall-clock training times (right y-axis) further demonstrates that MACSIM's efficiency advantages extend the training process itself. MACSIM trains nearly order of mag- nitude faster per epoch while still achieving superior final performance. This consistent efficiency gain across problem sizes, coupled with its robustness on larger instances where SLIM becomes unstable, provides strong empirical evidence that the joint-action framework effectively overcomes scalability limitations in self-improvemmntt for multi-agent combinatorial optimization.
22

---

Published as a conference paper at ICLR 2026
500
100
SLIBE Xinkspia MACSIIKI Malorgen
35
250
-500
180
Ars. Nikopan
2X0
350
1.00
100
16
120
Tainng
-00
25
20
601
100
300000
SLM
25
50
100
100
MAUSIN
100
150
20
MATSIM
Eperis
FFSP 20
(b) FESP
FESP
Figure 6: Wall-clock training time per epoch (right axis) and evolution of the average makespan the validation set FFSP instances with = 20, 50, and 100 jobs (left axis). As the problem size increases, SLIM's training becomes progressively unstable, whereas MACSIM maintains stability and converges while being nearly an order of magnitude faster to train.
D.5 SCALABILITY ANALYSIS
A key concern in neural combinatorial optimization is scalability to large problem instances. In this section, we provide a comprehensive analysis demonstrating that MACSIM's 's design choices training single state-action pairs and amortizing re-encoding costs over multiple actions yield substantial scalability advantages over both traditional RL-based NCO methods and standard self- improvement approaches.
Comparison with RL-based NCO. Traditional RL-based NCO methods like MatNet (Kwon et al., 2021) train via REINFORCE, which requires backpropagation through entire solution trajec- tories. This necessitates storing activations for all decoding steps, leading memory consumption that scales linearly with solution length. contrast, MACSIM's self-improvement paradigm trains on individual fate-action pairs, requiring only single-step gradients.
We empirically validate this advantage by comparing memory consumption and training efficiency between MACSIM and MatNet FFSP instances of increasing size. For memory analysis, a batch size of for both methods and record peak GPU memory consumption during training. For training time analysis, use the maximum feasible batch size for each method on single NVIDIA A A100 GPU with 40GB VRAM and measure wall-clock time per epoch (1,000 instances).
Results presented in Table For N 100 jobs, MatNet consumes approximately GB of memory, which increases to roughly 13 GB for N = 500, corresponding to 13x increase. In contrast, MACSIM increases from only 702 MB to just under GB less than 3x increase. This dramatic difference in memory scaling enables MACSIM to use significantly larger batch sizes (64 vs. for N 500), directly translating to faster training: MatNet's training time grows from 6.4 minutes per epoch at N = 100 to 264 minutes at N 500, while MACSIM only increases from 5.1 minutes 63 minutes.
These results demonstrate that MACSIM's state-action pair training paradigm provides a fundamen- tal scalability advantage over trajectory-based RI. methods, enabling efficient training on problem sizes where traditional approaches become prohibitively expensive.
Table 7: Memory consumption and training time comparison between MatNet (RL-based) and MACSIM on FESP instances of increasing size. Fraction columns show MACSIM's cost relative to MatNet.
FFSP
Peak Memory (GB)
Training Time (min/epoch)
N x M: S
MatNet
MACSIM
Fraction
MatNet
MACSIM
Fraction
100 x 4 x 3
1.47
0.71
0.48
6.43
5.12
0.79
x x
4.12
1.24
0.30
31.12
15.60
0.50
500 x 4
12.87
1.95
0.15
264.41
63.62
0,24
23

---

Published as a conference paper at ICLR 2026
Comparison with Standard Self-Improvement. While standard self-improvement methods like SLIM share MACSIM's 's advantage of state-action pair training, they employ step-wise re-encoding with fully autoregressive decoding, thus computing embeddings for every single action. MAC- SIM amortizes this computational cost by generating M agent actions from a single encoding step.
Figure 3c in the main paper demonstrates this advantage across FFSP instances of varying size. For N = 50 jobs with M = 24 agents, MACSIM requires approximately 10 construction steps to generate a complete solution, while SLIM requires 150 steps. This translates directly wall-clock time as shown in Figure 6: MACSIM trains in approximately 400 seconds per epoch compared to almost an order of magnitude faster.
SLIM's 3,000 seconds
Combined Advantage: Scaling large multi-agent Problems.
The combination of (1) state- action pair training and (2) multi-action generation creates powerful synergy for scaling to large multi-agent problems:
Memory efficiency from state-action pair training enables large batch sizes during training
Computational efficiency from amortized re-encoding significantly reduces training time by a factor proportional the number of agents
Training stability from the permutation -iviriiannn loss ensures reliable convergence even as coordination complexity increases
Together, these properties position MACSIM as a highly scalable approach for large-scale multi- agent combinatorial optimization.
D.6 RUNTIME PROFILING AND EFFICIENCY ANALYSIS
To isolate the source of MACSIM's computational efficiency, we perform a decomposition of infer- ence latency into two distinct components: (i) policy evaluation, which encompasses the forward pass the neural network (L st) to generate logits, and (ii) sampling, which refers to the discrete selection of actions from the distribution P(L).
We compare the baseline SLIM against MACSIM on the Flexible Flow Shop Problem (FFSP). We fix the problem size to N 50 jobs across 5 = 3 stages and vary the number of parallel machines per stage, denoted as M, E 83. This results total agent counts of M = 12, 18, and 24, respectively.
Table 8: Inference time decomposition. Times are reported as milliseconds for a single solution construction, averaged over 100 instances. The Policy column measures the cumulative time spent in neural network forward passes, while Sampling measures the time spent selecting discrete actions. Percentages indicate the relative contribution total latency.
FFSP
MACSIM
SLIM
N X M,
Policy
Sampling
Policy
Sampling
50 X 4 X 3
234.44 (65%)
125.02 (35%)
3119.36 (96%)
120.12 (4%)
50 x 6 x
319.73 (71%)
133.45 (29%)
3966. 12 (97%)
120.40 (3%)
50 8 x
568.44 (79%)
155.64 (21%)
8844.75 (99%)
121.01 (1%)
Policy. As shown in Table 8, inference in SLIM is overwhelmingly dominated by policy evalua- tion, which accounts for over 96% of total runtime. This bottleneck arises because SL.M operates as a single-action sequential predictor: for problem requiring N total assignments, SLIM must exccute the encoder-decoder stack N times.
In contrast, MACSIM reduces the policy evaluation time by factor of 12 to 16. This speedup is a direct consequence of the multi-agent architecture defined in Equation (3), where the joint logit matrix L is computed once construct M actions. By enabling all M agents act based on single forward pass, MACSIM effectively amortizes the expensive neural computation over M decisions. Consequently, the end-to-end speedup ranges from approximately 9 to 11 across these settings.
24

---

Published as a conference paper at ICLR 2026
Sampling. Notably, the absolute time spent sampling remains comparable between the two methods (e.g., R 125 ms vs. ~ 120 ms for the 50 x 3 x instance), though MACSIM exhibits a slight increase agent count grows. It is important to note that the total count of sampled actions in MACSIM is slightly higher than in SLIM, due to the incorporation of the skip token. While this mechanism increases the total volume of discrete samples required to complete solution, the sampling cost remains negligible relative to the massive reduction in policy evaluation steps.
E Loss FUNCTION GRADIENT ANALYSIS
Here, we provide a detailed analysis of the gradients for the four loss functions discussed and evalu- ated in the main text: the single-agent cross-entropy loss (evaluating only single action aj a a time) akin to SLIM, the multi-agent cross-entropy loss (CCE), the loss derived from the Plackett- Luce formulation (Crt), and the loss corresponding to the Maximum Likelihood Estimation (MLE) of the generative model of Equation (3), denoted LML. This analysis highlights the sources of insta- bility and bias in CSA, LMLL and CrL. justifying
of Lcs as permutation-ineee iiviroinniiaaiatttt surrogate.
E. SINGLE-AGENT CROSS-ENTROPY Loss
This loss mimics standard self-improvement methods which are trained in "next-token prediction" fashion described by Pimaa & Grimm (2024). Given state st and any pseudo-expert action (m", o*) E a/, the model's 's task under this loss is to predict this single pair from the entire, static pool of all possible agent-task assignments, &. The loss is the negative log-likelihood of selecting the single expert pair (m" , u²) from the set of all pairs E:
exp( exp(Im=.,n
CSA - llg
(36)
E(m,e)ee exp()
and the gradient for any logit Ligj in the logits matrix is given by:
OLSA
exp(Lia)
Σ (m, exp( (Tp()))))) I[ii = m²"j m= = v*)
(37)
Thi
where I(.) is the indicator function.
Conflicting and Spurious Gradients. The core problem arises from the global softmax normal- ization. At each step, the gradient update for the target pair (mī. vf) is defined in competition with all other available pairs in &. This setup effectively designates a single pair as positive while treat- ing the remaining M correct assignments as negatives. Consequently, the model is explicitly penalized for predicting other parts of the ground-truth -ruth solution: for every correct pair not chosen as the target, the gradient contributes a positive update that suppresses its logit. The resulting signal is inherently contradictory, preventing the model from converging toward consistent joint policy.
This flaw is particularly evident forced-choice scenarios. When an agent m has only one valid task v" at step k, no genuine decision is required. Nevertheless, CML still yields non-zero loss, producing spurious gradients that penalize unrelated logits I,,, with i * m. Such unnecessary updates destabilize optimization by introducing noise unrelated to the actual decision process.
Vanishing Gradients. The softmax denominator is calculated
the entire set E, which can contain thousands possible actions. This makes the probability of the single target action infinites- imally small, leading to a vanishing gradient problem even more severe than that of the sequential MLE loss (CMI). This effectively makes training infeasible for large problem sizes.
E.2
MLE LOSS
Unlike the single-agent formulation, the MLE loss computes softmax over the remaining feasible pairs at each step k; with E denoting the available pairs. The gradient for Li,j aggregates contribu- tions across agents:
25

---

Published as a conference paper at ICLR 2026
0LML abi
exp(Li.) Lla,ieee exp(La,b)
11(i m - v1.)
(38)
Similar to LSA, the global softmax normalization in LML leads to conflicting and spurious gra- dient signals. Since the loss is sum over all agents, the final gradient for any correct assignment becomes an inefficient and contradictory sum of one large negative update and many small positive updates (penalties). Also, similar to LSA, this loss formulation suffers from vanishing gradients, especially for decisions made early in the sequence when the action space is at its largest. This effec- tively stalls the learning process, making it very difficult for the model learn meaningful policies for large problems.
E.3 PLACKETT-LUCE LOSS
The Plackett-Luce model addresses the global competition issue by conditioning the choice of a task on specific agent at each step. If agent mæ is assigned at step k, the softmax is computed only over the set of available tasks V4= = V (ui...., 1 The gradient for agent i's logit Lig is:
0Crl tLis Eyev, exp(Li.")
exp(Li.))
II(j 2kk)
(39)
Permutation-Indue Induucd Bias. While LPt. resolves the confticting gradient issue of LAIL. it remains sensitive to the arbitrary order of the expert permutation. This bias arises directly from the structure of the gradient. For an agent acting early in sequence, the set of available actions V2 is large, leading to a large normalization term in its softmax calculation. At the beginning of training, this large denominator yields very small initial probability P(vglo) for the expert action. Since smaller probability results in gradient with a larger magnitude, the optimization process is forced to drive the corresponding logit to significantly higher magnitude. In contrast, late-sequence agent starts with higher probability and thus smaller gradient magnitude, requiring a less substantial increase in its logit value. Consequently, the model dedicates capacity to learning an artificial, agent- specific confidence level, where the scale of the output logits becomes entangled with the agent's position in the training sequence.
E.4 SET CROSS-ENTROOE Loss
To avoid the issues of sequential modeling, the multi-agent cross-entropy loss (LCr) treats each agent's assignment as an independent classification problem. Each agent predicts its task o (i) from the complete set of tasks V. The gradient for agent i's logit Li depends only on its own
logits:
dccE exp(Ir.) aLا Eyev exp(L..)) I(j 00 (1))
(40)
where (1) is the expert-assigned task for agent i.
This decoupled formulation provides stable and robust learning signal. Every correct pair (i, uf) reinforced individually, without interference or competition from the assignments of other agents. This elegant structure entirely circumvents the confticting gradients of LML and the permutation bias of LpT, making it a superior objective for learning multi-agent assignment policies. Figure validates the superiority of MACSIM trained with LCE over SLIM that uses single-agent loss LSA. especially for larger instances.
F THEORETICAL JUSTIFICATION FOR SET-BASED LOss IN MACSIM
F. TRAINING-INFERENCE MISMATCH
The surrogate loss in equation 6 offers tractable and stable method for training. While the gen- erative model in equation 3 couples assignments through one-to-one matching constraint, the set- based cross-entropy loss simplifies this by treating each expert agent-task pair as an independent
26

---

Published as a conference paper at ICLR 2026
classification problem. This is justified because the training process only observes valid matchings, allowing for clean, per-agent supervision. The result a permutation invarriann learning signal that provides stable gradients, avoiding the conflicts and biases inherent in more complex objectives like direct Maximum Likelihood Estimation (MLF) as shown in Appendix E.
This independent loss signal does not prevent the model from learning coordination. Inter-agent dependencies are captured implicitly by the policy's architecture, where self- and cross-attention mechanisms compute the joint logit matrix with full context. At inference, the autoregressive sampling algorithm then acts as hard constraint enforcer, translating these context-aware logits into valid, conflict-free assignment. This combination of a stable surrogate for training and structurally- aware process for inference proves highly effective. Empirically. this approach sig- nificantly outperforms training with an exact MLE or Plackett-Luue loss (Table 4), confirming its practical advantages.
In the following, we provide formal justification for using the set-based cross-entropy loss, LCE- We prove that it is sound proxy for the ideal (but intractable) permutation--nvariian objective.
F.2 FORMAL JUSTIFICATION FOR THE SURROGATE LOSS
Setup. We introduce shorthand notation for softmax normalization and marginals. For agent m and its expert-assigned task v" (m), use:
Pm( exp(Lm.e)
Zm Σ exp(Lmm.)) VEV
Pm.
(v" (m)).
Zm
During generation, the policy samples agents in some order (a permutation of {1,...; M)) with prior w(r), where E. w(o) = 1. At step k, agent my (kk) selects a task from the remaining set (x( V. The normalizer for the softmax function given as:
Sa
Σ
exp(Lo(k)).).
wEV.
The probability of producing the unordered matching a* is
exp( (x)(Lo(K) Sx(o)
Pperm (a
Σ w(a) II
The ideal loss Lideal log Permm (a*), while the surrogate loss is the set cross-entropy LCE
-MM
logpm- Pm-
Theorem (Upper Bound and Tightness). For any permutation prior w(a):
1. (Upper Bound) The surrogate loss upper- the ideal loss:
LCe Lideal.
2. (Gap Bound) With Tm (1
M Σ m=1
0 < Lee Lideal S
log(1 + rm))
Pm Pm 2 1 for all m, then
LCB Lideal S M log [ r-m s Me
Part 1: Proof of the Upper Bound.
Proof. Fix a permutation and denote P(a" ()) its sequence probability. At each step k.
Sa(a)=
Σ exp(Too()).) S Σ exp(TTo(A),.) = =Zo(k)
vEVA(G)
NE
27

---

Published as a conference paper at ICLR 2026
since (o) C.. Thus
exp(Io(()) expl ((()))))))))
Sx(0)
Zo(k)
Po(M)-
Hence
M
P(a" σ) 2 Pm.
m=1
Taking the expectation over a preserves this bound:
Perm (a") = Σ w(lo) (0)
II Pm.
Applying log(-) yields
Lideal S LCE.
Part 2: Proof of the Gap Bound.
Proof. To bound the gap, establish an upper bound on Pperm (a*). We start by rewriting the probability of single sequence by multiplying and dividing each factor by Za())
P(a"
())
II
M
exp (a()
Zo(k) (x(o)
M II Po(k) A=1
(
II k=1
Zacks (.
Zo(k)
1=1
Since v"(o(k)) E Va(a), it must hold that Sx(a) 2 cxp(Lo(s) and thus:
Za(k)
Zo(k)
= 1 + To(k)
(x)
exp(Lo(()))r((c))
Po(k)
Thus
M
M (Ma+)))
P(a" 1
II Ps
Averaging over a preserves the bound, so
M
Pperm (a)) s
II Pm
II m=1
rm)
Taking log gives
M
Lideal 2 Lce
log(1 1 + rm).
m=1
or equivalently
Loe Lideal S
log(1 rm).
If Pm - then I -
M Σ m=1
log(1 + +rm) S M Mlog 1 T
Ms I-e-
Implication for Optimization. Theorem establishes that Lcs is a tractable upper bound on the true symmetric objective. Moreover, the bound tightens the policy becomes confident, ensuring that optimization with LeE smoothly transitions from providing stable gradients early to closely approximating the ideal objective in later training.
28

---

Published as a conference paper at ICLR 2026
G DISCUSSING THE INDEPENDENCE ASSUMPTION IN THE SET-BASED LOSS
This section analyzes the efficacy of the agent-independent loss function (Cer) for solving coupled multi-agent combinatorial problems. The proposed loss function LCE treats the assignment of each agent m to a task & as an independent classification problem. Letting the total loss be the sum of individual agent losses, LCE = Im= Cm(Lm.:) direct analysis of the gradients (Appendix E.4) shows that the loss for a specific agent m yields no direct gradient signal with respect to the logits of any other agent:
8Lm
0
Vk #
(41)
aLE
Consequently, at the output layer, the optimization objective for Agent m is independent of the de- cisions of Agent k. Despite this independence at the loss level, MACSIM achieves coordinated solutions through the synergy of three distinet mechanisms: Architectural Coupling, Implicit Constraint Learning, and Inference- Constraints enforced via our autoregressive sampling approach.
G.1 MECHANISM 1: ARCHITECTURAL COUPLING
While the gradients are independent with respect to the logits L, the agents are coupled via the shared model parameters 0. The policy architecture processes the state through deep encoder utilizing multiple layers of self-attention and cross-attention. In this shared latent space, the embedding of Agent m, denoted as hym, is computed by aggregating information from all other agents and tasks. As result, the gradient of Agent m's loss with respect to the shared parameters affects the representations of all agents:
dL
+ 0
(42)
00
This implies updates to features utilized by Agent kt To minimize LCE, the encoder learns to produce disentangled representations where the features for Agent m align with Task Un. while the features for Agent align with Task Uj-
G.2 MECHANISM 2: IMPLICIT CONSTRAINT LEARNING VIA GRADIENT DYNAMICS
The second coordination mechanism emerges from the specific gradient dynamics of the set- based loss. As detailed in our gradient analysis in Appendix E, single-action supervision (e.g., SLIM) inherently suffers from gradient interfer- ence. Because it utilizes global Softmax over all possible agent-task pairs, reinforcing a sin- gle target action explicitly degrades the proba- bility of valid future actions for other agents. This creates confficting signals that hinder the learning of a consistent joint policy. In contrast, MACSIM avoids this interference by optimizing M independent local losses. For any specific agent m, the objective maximizes the logit for the assigned task of, while suppressing the log- its for all other tasks. Crucially, this set of sup- pressed tasks includes all tasks og assigned to other agents l: + m.
0.6
Conticct
0.4
MACSIM
0.0
20
30
50
Epoch
Figure 7: Evolution of the raw conflict rate (per- centage of agents that share the same argmax ac- tion) during training on FISP 10 x 5 instances.
Since the expert targets conffict-free, exactly one agent receives positive update for any given task v, while all M 1 other agents receive negative updates for that same task, actively reducing contention. The policy internalizes global coordination constraints purely through this independent contrast.
We visualize this effect in Figure 8 and quantify it in Figure 7. Figure 8 compares the logit heatmaps of MACSIM against an Attention Model (AM) trained via standard SLIM. After train- ing, MACSIM's logits exhibit clear "permutation matrix" structure-hige values are sparse and
29

---

Published as a conference paper at ICLR 2026
non-overlapping across agents. Conversely, the AM baseline fails to coordinate, frequently assign- ing the highest logit value for a single task to multiple agents simultancously.
Furthermore, analyse the percentage of agents that share the same argmax action of the logits during training. As shown in Figure 7, this conflict rate drops precipitously during training for MACSIM while staying consistently validates that the independent loss, when combined with conflict-free expert labels, successfully teaches the network to respect injectivity constraints.
high level for the AM trained via SLIM. This empirically
(8) Initial Logits
(b) MACSIM After Training
(e) SLIM AM After Training
XI
XII
MI
Agantt (Mochiuu)) 333
M22
ME
M2
MB3
MB
All agests compete
MB
Apeiie Choerianle Actione
MS
5.lp 11
32
30 Thake (Jole)
26
17
38
Skip 22
13
19 110
9kp
15 16 (Job))
Taako (Jklm)
Takk
Figure 8: Comparison of joint logits L computed on an FISP 10 problem instance by (a) an un- trained MACSIM policy, (b) MACSIM after training, and (c) an Attention Model trained by SLIM.
G.3 MECHANISM 3: INFERENCE-TIME CONSTRAINTS
The third layer of coordination occurs during the solution generation phase. Although the loss is calculated independently, the inference process defined in Algorithm explicitly couples the agents autoregressive sampling from the flattened joint logits. Because we sample without replacement, an agent that is highly confident (possessing high logit value) exerts "soft" suppression other agents. Specifically, Agent mn has a high probability for Task v, it is statistically likely to be sampled early in the sequence. Once (m, v) is added the solution, task is masked. This mechanism effectively converts confidence into priority. An agent that was reinforced multiple times during training to take specific action will exhibit sharp probability peak. In our AR-sampling algorithm, this confident agent will take precedence, thereby preventing other agents from making a conflicting choice.
all
The ablation study in Table 3 validates that the policy implicitly learns to rank agents: replacing our logit-dependent sampling order with fixed random order significantly degrades performance, particularly for instances with larger number of agents, proving that the learned confidence hierar- chy is essential for resolving complex inter-agent conflicts.
H EXPERIMENTAL DETAILS AND RESOURCES
H.1
FISP
H.1.1 HYPERPARAMETERS
We train MACSIM on the FJSP for 50 epochs using 4,000 randomly generated instances per epoch. For each training instance æ the current best policy ιq is used to sample 3 128 solutions, where the best serves as training example. Within the training loop, we sample pseudo expert state- assignment pairs in batches of size 2,000 from the generated training dataset and use the Adam optimizer Kingma & Ba (2015) with a learning rate of 10-4, which we alter during training using cosine annealing scheme. The embedding dimension is set to 256, transformer layers use heads and we set the number of encoder layers P to 4. Also, we use dropout rate of 10%.
H.1.2 DATASETS
Train data generation. We train MACSIM on FJSP instances of size 10 x 5, 20 5, and 15 x 10, following the generation scheme and parameters described in Song al. (2022).
30

---

Published as a conference paper at ICLR 2026
Testing. Testing on the instance-tyye sepnnneeettppsseceee rep in Tables 1 and is performed 1000 separate test instances provided by Song et al. (2022). Further, we test MACSIM on public benchmark datasets (see Appendix D.1 for details).
H.2 FFSP
H.2.1
HYPERPARAMETERS
In each epoch, we train the models using 1,000 randomly generated instances for which sample = 128 solutions and put the best into the training dataset. During training, we sample pseudo expert astignassinmentt pairs in batches of size 1,000 from the generated training dataset and use the Adam optimizer Kingma & Ba (2015) with a learning rate 10-1, which we alter during training using cosine annealing scheme. Same for the FISP, the embedding dimension is set to 256 and we set the number of encoder layers P to 4. Also, we use the same dropout rate of 10%. However, following Kwon al. (2021) we use 16 heads in the attention layers. We train models corresponding to environments with 20 jobs for 100, with 50 jobs for 150 and with 100 jobs for 200 epochs.
H.2.2 DATASETS
Train data generation. We follow the instance generation scheme outlined in Kwon et al. (2021) and sample processing times for job-machine pairs independently from uniform distribution within the bounds| 22 10). For the FFSP instance types shown in Table 1 we also use the same instance sizes as Kwon al. (2021) with N = 20, 50 and 100 jobs and M
machines which are spread evenly over S 3 stages. To test for agent sensitivity in the FFSP, we fix the number of jobs to N = 50 but alter the number agents for the last three instance types shown Table 1. Still, we use for this experiment, but alter the number of machines per stage to M; 6, 8 and 10, yielding total of 18, 24 and 30 agents, respectively.
Testing.
Testing on the instance- types reported in Table is performed on 1000 separate test in- stances provided by Kwon et al. (2021). For the instance types reported in Table 6, test instances are generated randomly according to the above generation scheme.
H.3 HCVRP
H.3.1 HYPERPARAMETERS
We train MACSIM on the HCVRP for 200 epochs. In each epoch, we train the models using 1,000 randomly generated instances for which we sample 3 200 solutions. Within the training loop we sample pseudo expert state-assignment pairs in batches of size 1,000 from generated training alter during training using cosine
dataset and use Adam with learning rate of 10-4, which annealing scheme. The embedding dimension is set to 256, dropout rate is 10%, transformer layers 16 heads and we the number of encoder layers P to
H.3.2 DATASETS
Train data generation. We apply the instance generation scheme and seed used by Liu et al. (2024). The authors follow the standard procedure in NCO literature and sample coordinates for the N customer locations and the depot from the unit square. The demand of customer locations is sampled i.idd from U(1, 10) and the capacity for each vehicle from ((20,, 41). The speed of each vehicle uniformly distributed within the range (0.5,, 1.0).
Testing. Testing is performed on the 1280 instances per N M test setting from Liu et al. (2024). Neural baselines in Table were trained with the specific number nodes and number of agents M they were tested
31

---

Published as a conference paper at ICLR 2026
H.4 HARDWARE AND SOFTWARE
H.4.1 HARDWARE
We experiment on workstation equipped with 2 INTEL(R) XEON(R) GOLD 6338 CPUs and 8 NVIDIA A100 graphic cards with 80 GB of VRAM each. Each training run uses a single A100.
H.4.2 SOFTWARE
Our code base is implemented in Python 3.10. Neural policies implemented in PyTorch 2.8 (Paszke et al., 2019) and training algorithms are defined as PyTorch Lightning Modules (Falcon & The PyTorch Lightning team, 2019). Environment implementations are based on or inspired by the RLACO library (Berto et al., 2025). The operating system is Ubuntu 24.04 L.TS.
H.5 USE OF LARGE LANGUAGE MODELS
Large language models (LLMs) were used in this work solely as a general- purpose writing assistant. Their role limited to polishing phrasing, improving clarity, and correcting grammar in drafts of the manuscript. All research ideas, analyses, results, and interpretations were generated and verified by the authors. The content produced by LLMs carefully reviewed, edited, and integrated by the authors to ensure accuracy and adherence to academic standards.
32


Reviews:
[{"review_id": "cSPeJqyEmc", "reviewer": "Reviewer_Q1dc", "summary": "This paper presents a multi-agent extension of the self-improvement paradigm for neural combinatorial optimization (NCO). Instead of predicting one action per step, the proposed method jointly samples actions for all agents from the full joint-agent action space. By incorporating agent-permutation symmetry into both the policy design and training objective, the approach improves coordination among agents and produces higher-quality solutions compared to existing self-improvement baselines.", "questions": "None", "limitations": "", "rating": 6, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The paper effectively integrates ideas from reinforcement learning–based NCO and self-improvement learning. It makes good use of the MatNet architecture, originally developed for RL, and adapts it to the self-improvement setting. The main idea is simple yet powerful—using the joint action score matrix to derive agent–task matchings, which is both logical and effective. In addition, the paper is very well written, with rigorous equations and precise mathematical definitions.", "weaknesses": "While the paper presents a clear and elegant formulation, the novelty appears somewhat incremental, as it mainly builds upon existing self-improvement methods by reformulating them for multi-agent joint-action modeling. \n\nThe method relies on full re-encoding of the problem state at each step, which may hinder scalability to larger instances. Moreover, since each re-encoding operates only on the updated state—without explicitly retaining information about past actions or the original problem context—the approach may have limited applicability to problems with temporal dependencies or long-horizon constraints.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "a09HvSuPms", "reviewer": "Reviewer_t8zx", "summary": "This paper identifies a critical limitation in existing self-improvement (SI) methods, such as those proposed by Corsini et al. (2024) and Pirnay & Grimm (2024). The authors argue that the standard \"next-token\" prediction paradigm, which learns from a single expert trajectory, fails to account for agent-permutation symmetries in multi-agent problems. This forces the model to learn an arbitrary agent order, hindering coordination and sample efficiency. To solve this, the paper proposes MACSIM (Multi-ACtion Self-Improvement). The core contribution is a framework that: 1) Uses a policy to predict a single, joint logit matrix ($M \\times N$, a \"$heatmap$\" for all agents and tasks in one forward pass. 2) Employs a set-prediction loss ($\\mathcal{L}_{CE}$) to supervise this heatmap on the set of expert assignments, making the training signal invariant to agent permutation. The authors claim MACSIM achieves higher solution quality, better sample efficiency, and \"drastically accelerated\" solution generation on multi-agent scheduling and routing problems.", "questions": "1. Your paper cites DPN (Zheng et al., 2024) and notes that it also addresses agent-permutation symmetries. Given that both your method and DPN are evaluated on min-max routing problems (HCVRP), why was DPN not included as a direct experimental baseline in your empirical comparison (Table 1)?\n2. Could you provide a computational profile of your model at inference? Specifically, what percentage of the wall-clock time is spent on the $T$-step policy re-encodings versus the $M \\times T$-step autoregressive sampling (Algorithm 1)? This would clarify if the accelerated part is a meaningful portion of the total inference time.\n3. You train with the $\\mathcal{L}_{CE}$ loss, which treats all $M$ agent assignments as independent classification problems. However, you infer using a sequential, dependent sampling algorithm (Algorithm 1). Why is this independent loss sufficient for learning a policy that must produce coordinated, dependent assignments?", "limitations": "", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. The paper’s primary strength is its clear identification of the \"agent-permutation symmetry\" problem. The diagnosis that standard SI's next-token supervision (SLIM) implicitly punishes valid, symmetric solutions as \"errors\" is a significant contribution.\n2. The decoupling of the (expensive) one-shot policy evaluation to get the joint logits from the (fast) $M$-step autoregressive sampling (Algorithm 1) is a clever way to amortize computation while guaranteeing a conflict-free joint action.\n3. The experimental results show that MACSIM consistently outperforms its baseline (SLIM).", "weaknesses": "1. The paper's core claim is that it better handles multi-agent symmetries. The authors cite DPN (Zheng et al., 2024) in their related work, noting it also targets multi-agent permutation symmetries, albeit using a different method (symmetric baselines). However, despite both MACSIM and DPN being applied to min-max routing problems (HCVRP), DPN is completely absent from the experimental comparisons in Table 1. DPN is a state-of-the-art method that directly addresses the same core problem (multi-agent symmetry). Failing to compare against it empirically, while instead comparing against a re-implemented SLIM baseline, significantly weakens the paper's claims of superiority in this domain.\n2. The paper positions itself as an improvement over standard self-improvement (SI) but only provides a direct experimental comparison against a re-implemented \"SLIM\" (Corsini et al., 2024). It fails to provide a direct experimental comparison to other significant and recent work in SI, notably Pirnay & Grimm (2024), which it cites alongside SLIM as the methods it aims to improve upon. While the authors group these methods together conceptually, they are not identical. A direct comparison against Pirnay & Grimm (2024) would be necessary to fully substantiate the claim of superiority over the class of standard SI methods.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Jlt0yUTSc6", "reviewer": "Reviewer_tkUT", "summary": "The paper proposes MACSIM, a method to solve multi-agent CO problems, inspired by recent self-improvement methods for neural CO. More concretely, MACSIM learns a multi-agent policy for joint agent-task assignments, where the policy is learned via self-improvement: the policy is trained to imitate previously found good solutions. Through experiments on the FJSP, FFSP, and HCVRP problems, the authors show the efficacy of their method against relevant baselines.", "questions": "See weaknesses.", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is mostly well-written.\n- The problem studied in this paper (multi agent CO) is of interest to the neural CO community and the proposed method (self-improvement with a joint policy) is novel.\n- The empirical results are good.", "weaknesses": "- The authors claim that prior self-improvement methods assume a unique optimal action per step, which limits their applicability to multi-agent settings with symmetric solutions. However, since the policy here is stochastic, it’s unclear to me why it couldn’t naturally capture multiple optimal actions if the imitation data already reflects these symmetries. Could the authors clarify this?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "WDa3beeyUH", "reviewer": "Reviewer_z3tB", "summary": "This paper presents a novel approach to solving combinatorial optimization problems that require simultaneous assignment between multiple agents and multiple tasks over time. Such assignment problems can generally be formulated as bipartite matching problems.\nThe authors propose a method that jointly embeds multi-agent and multi-task information to generate joint logits, performs assignment based on these logits, and trains a neural network for joint logit embedding using a self-improvement learning framework.\nExperiments are conducted on FJSP, FFSP, and HCVRP combinatorial optimization problems, showing faster inference and higher solution quality compared to previous studies.", "questions": "None", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The strategy of assigning all agents and tasks simultaneously through a single joint logit output is efficient and demonstrates strong performance.\n\n- The proposed approach is expected to be useful for solving other similar types of combinatorial optimization problems or for inspiring further research in this area.\n\n- The training procedure for producing joint logits is logically well-structured.\n\n- The paper is overall well-organized and highly readable.", "weaknesses": "- The overall model structure based on joint logits is similar to prior works (e.g., Kwon et al., 2021), and its novelty is mainly limited to the use of joint logits for agent–task assignment and the application of self-improvement for model training.\n\n- The application of self-improvement does not introduce substantial new ideas or enhancements, and it appears to largely adopt existing approaches without major modifications.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)