acceptodds
Under review as a conference paper at ICLR 2027

Towards Generic and Efficient Architectures for Graph Neural Combinatorial Optimization

Abstract

Constructive neural solvers have become a leading paradigm for combinatorial optimization (CO). However, building an architectural framework that is both generic enough across diverse problems without per-problem component redesign and efficient enough for step-wise inference remains an open challenge. To reduce this gap, we propose GECO, a generic and efficient architecture for edge-aware graph neural CO. To reduce computational cost, GECO introduces ScoreMixer-in-Attention (SMA), which follows a head-coupled attention-logit modeling principle: it treats the pre-softmax multi-head logits as a compact node–edge compatibility representation and refines it through a light-weight sub-network, avoiding expensive high-dimensional pairwise feature transformations. To enable generic instantiation, GECO further introduces a learnable warm-up attention layer that initializes node embeddings by aggregating edge information in a task-agnostic manner, together with an instance-preserving normalization framework that provides a principled feature-scaling normalization recipe for CO problems. Experiments on five representative routing and scheduling tasks show that GECO achieves strong solution quality while substantially reducing computational cost compared with state-of-the-art edge-aware architectures. Overall, GECO offers a concrete step toward systematically instantiable architectures for efficient edge-aware graph-based CO.

Primary area:
optimization
Keywords:
Combinatorial Optimization

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_yNN8OpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper introduces the ScoreMixer-in-Attention mechanism, which can successfully encode CO instances with relations between items. Together with the proposed warm-up layer and instance-preserving normalizer, the proposed model outperforms existing NCO methods in terms of generalization and complexity. Although the work has an important practical gain, questions about its originality and methodology remain.

Critical strengths

(S1) The practical gain is clear: the proposed method is faster, requires less memory and generalizes better to larger instances.

(S2) Detailed evaluation metrics: wall-clock time, memory, FLOPs and training cost are the right metrics for this study.

Critical weaknesses

This paper has three stated contributions: ScoreMixer-in-Attention (SMA), the warm-up layer, and the instance-preserving normalizer.

(W1) SMA is claimed as the main architectural contribution, but it combines known components: an additive edge bias on the attention logits is presented in [1], refinement of a pairwise representation through an MLP in [2], and mixing of logits across the head dimension in [3]. Admittedly, these works are not from the NCO field, but they are established and well known in the graph transformer community and cannot be ignored. The related work covers only edge-aware attention mechanisms in NCO (GOAL and MatNet) and ignores many important works on graph transformers in general.

(W2) The second contribution, the warm-up layer, is not convincing. There is a clear gain on OP but only a small gain on large-size ATSP, while the warm-up layer performs worse on small-size ATSP. This raises the question of whether there is a real gain from introducing the warm-up layer.

[1] Ying et al., Do Transformers Really Perform Badly for Graph Representation?, NeurIPS 2021

[2] Ma et al., Graph Inductive Biases in Transformers without Message Passing, ICML 2023

[3] Shazeer et al. Talking-heads attention. arXiv:2003.02436, 2020

Questions for authors

Q1. Could you explicitly explain the novelty of your SMA mechanism compared with the methods presented in [1], [2] and [3]?

Q2. Table 5 provides the node initialization ablation only for ATSP and OP. I would like to see the same for the other problems as well.

Q3. As mentioned above, the warm-up layer does not bring much on ATSP, and it even degrades performance at problem sizes closer to the training size. Since ATSP is the only problem in this work without any node features, could this gap come from that property? That could be a major limitation for a model that claims to be a generic model for CO, since many CO problems have that property.

Q4. I do not understand the ablation presented in Table 1. It measures the impact of input normalization on MatNet, and I cannot see how the conclusion can be generalized to other models, including yours. How can we conclude that, because z-norm helps MatNet generalize, it will also help other models, including GECO, generalize?

Q5. Table 11 could answer the question about the usefulness of the normalization choices, but only OP has results without normalization (“None”). I would like to see the same for all problems, i.e. how the model performs without any normalization.

Q6. At present, this work addresses four routing problems and one scheduling problem. This may not be enough to claim a general model for graph combinatorial optimization. Did you try to apply your model to another problem family? It would be nice to see whether this method works when the input graph is sparse and defined by adjacency, as for example in the Maximal Independent Set problem.

Bonus question (not related to assessing the quality of this work): Just out of curiosity, did you try to train one model for all problems in a multi-task setting, like GOAL? I know this is outside the scope of this paper, but it seems to me that there is no (structural) limitation preventing this paradigm. Is that correct?

5 comments
AuthorsOpenReview ↗

Response (1 / 4)

We sincerely thank the reviewer for the careful review, for the positive assessment of the practical gain and of the evaluation metrics, and for the pointers to the graph-transformer literature. Below we address the novelty of SMA, the warm-up layer, the normalizer, and the problem coverage.

W1 / Q1: SMA combines known components: an additive edge bias on the attention logits [1], an MLP refinement of a pairwise representation [2], and mixing of logits across heads [3]. Please explain the novelty of SMA compared with these works.

We thank the reviewer for pointing us to these works, we admitted that we did not have a thorough search on the existing literature. We agree that they are closely related, and will add a paragraph on graph transformers (Graphormer [1], GRIT [2] and talking-heads [3], and also SAN [4], EGT [5] and GraphGPS [6]).

We agree that each ingredient has a precedent, and SMA differs from the three works in its nonlinear mixer on edge-fused logits, its budget of 12 numbers per pair, and its calibration of the logits:

  • Graphormer [1] adds a per-head edge bias to the attention logits. This is the first operator of SMA (Eq. 2), and we do not claim it as new.
  • Talking-heads [3] mixes the logits of different heads with a linear map and has no edge input. The mixer of SMA is nonlinear and residual, and it acts on edge-fused logits. With a linear mixing, the score of a head is still a single bilinear form of query and key plus an edge term. Prop. C.3 shows that SMA represents scorers that are not of this form.
  • GRIT [2] keeps a width-dd representation for every node pair and updates it with an MLP in every layer, at O(N2d)O(N^2 d) memory. This is the cost regime of GOAL and MatNet. SMA keeps C(1+r)C(1 + r) = 12 numbers per pair.
  • None of the three calibrates the logits before the softmax. The third operator of SMA does: a query-axis shift, which is our design, combined with the support-size factor of SSMax [7], which we adopt and cite. In a constructive solver trained at NN = 100 and applied at NN = 1000, this stage carries the generalization across sizes.

Our contribution is therefore the combination that makes score-space edge fusion work for step-wise construction, where the cost recurs at every step. It joins a nonlinear residual mixer across heads, a calibration stage on the logits and an explicit per-pair budget, with the analysis of what this design can and cannot represent (Appendix C).

To test whether the earlier designs would suffice, we built them inside GECO with everything else unchanged, and both are far behind SMA (gap in %, NN = 100 / 200 / 500 / 1000, SMA as in Table 2, other rows with one seed):

Attention scorerATSPCVRPTW
additive edge bias only (as in [1])1.38 / 1.60 / 1.65 / 2.34–
+ ScoreNorm1.05 / 1.33 / 1.31 / 1.265.03 / 6.23 / 6.87 / 3.27
+ linear mixing across heads (as in [3])1.16 / 1.33 / 1.36 / 1.404.88 / 6.42 / 6.88 / 3.54
+ nonlinear residual mixer: SMA0.31 / 0.55 / 0.81 / 0.874.21 / 5.37 / 5.55 / 2.26

Wider pair states, the direction of [2], cost 1.8–2.1× the time and 2.9–4.2× the memory in GECO and are not more accurate on ATSP, CVRP or CVRPTW. They are represented by GECO-MatNet, which keeps a hidden activation per pair and head (Tables 3 and 6, and 4.88 / 6.12 / 6.57 / 3.22 on CVRPTW). The additive bias and the linear head mixing are far behind the nonlinear residual mixer on both tasks with intrinsic edge attributes.

We will add this discussion and the table to the revised paper.

References

  • [1] Ying et al., Do Transformers Really Perform Badly for Graph Representation?, NeurIPS 2021
  • [2] Ma et al., Graph Inductive Biases in Transformers without Message Passing, ICML 2023
  • [3] Shazeer et al., Talking-heads attention, arXiv:2003.02436, 2020
  • [4] Kreuzer et al., Rethinking Graph Transformers with Spectral Attention, NeurIPS 2021
  • [5] Hussain et al., Global Self-Attention as a Replacement for Graph Convolution, KDD 2022
  • [6] Rampášek et al., Recipe for a General, Powerful, Scalable Graph Transformer, NeurIPS 2022
  • [7] Nakanishi, Scalable-Softmax Is Superior for Attention, arXiv:2501.19399, 2025
AuthorsOpenReview ↗

Response (2 / 4)

W2 / Q3: The warm-up layer gives a clear gain on OP but only a small gain on large ATSP instances, and it is worse on small ATSP instances. Could this come from ATSP having no node features, and is that a limitation for a generic model?

We thank the reviewer for this careful reading of Table 5. We agree that on ATSP the gain of the warm-up is small, and that random identifiers are slightly better at the training size. We would like to add three observations.

First, the difference at small ATSP sizes is of the size of the variation between training runs, and at NN ≥ 500 the warm-up is ahead. The difference at ATSP100 (0.31 against 0.23) is close to the standard deviation between runs (0.06, measured over three further seeds).

Second, on ATSP the warm-up already contains what identifiers provide: adding random IDs on top of it brings nothing. The combined variant gives 0.35 / 0.61 / 0.85 / 1.02. The warm-up is also deterministic, with no artificial randomness at inference.

Third, on node features (Q3), we agree with the reviewer's observation: without node features, random identifiers have an edge near the training size, while the warm-up is ahead at the largest sizes. We tested this directly on a new problem, minimum vertex cover (MVC), which has no node features and no edge weights (set-up under Q6). All models are trained at NN = 100 (gap in %):

ModelNN = 1002005001000
GOAL (official released checkpoint)0.270.7515.9615.87
GECO, random-ID initialization0.140.372.186.44
GECO, warm-up0.330.702.223.34

Where the GOAL row is the checkpoint released by the GOAL authors for this problem, run with their official code. At NN = 100 the test set is GOAL's own, with 10,000 graphs. For the larger sizes we generated graphs of the same kind: 128 per size, and 64 at NN = 1000. The gap is measured against the optimal cover at NN ≤ 200, and against the best cover found by a local-search solver at NN ≥ 500.

As on ATSP, random identifiers are more accurate at the training size, and the order reverses at NN = 1000, where the warm-up reaches 3.34 against 6.44. So the benefit of the warm-up is in size generalization, which is the purpose we claim for it. We will state this explicitly in the paper.

Q2: Table 5 gives the node-initialization ablation only for ATSP and OP. I would like to see the same for the other problems.

We thank the reviewer for this suggestion. Following it, we added CVRPTW and a combined variant, and the warm-up is ahead of random identifiers at NN ≥ 500 on all three tasks (gap in %, NN = 100 / 200 / 500 / 1000). Entries already in the paper (Tables 2 and 5) are repeated from it, and all other entries use one seed:

InitializationATSPCVRPTWOP
random IDs0.23 / 0.52 / 0.89 / 0.984.04 / 5.60 / 6.48 / 3.10-0.16 / 0.65 / 4.96 / 10.58
warm-up + random IDs0.35 / 0.61 / 0.85 / 1.024.10 / 5.94 / 6.16 / 3.21-0.18 / 0.30 / 3.98 / 6.02
warm-up: GECO0.31 / 0.55 / 0.81 / 0.874.21 / 5.37 / 5.55 / 2.26-0.34 / 0.27 / 2.98 / 5.11

On CVRPTW, the new task, the two are close at NN ≤ 200, and the warm-up is ahead by 0.9 points at NN = 500 and 0.8 at NN = 1000. This is the pattern of OP in Table 5. On CVRP at NN = 1000, random identifiers give 6.51 against 4.79 in Table 2.

Overall, on these routing problems the warm-up gives its gain in size generalization, without any random input. We will add these results to Table 5.

AuthorsOpenReview ↗

Response (3 / 4)

Q4: Table 1 measures input normalization on MatNet. How can its conclusion be generalized to other models, including GECO?

We would like to clarify that Table 1 is only a motivating observation on MatNet, and it does not show by itself that normalization helps GECO. We apologize for the confusion. The direct evidence is now on GECO itself (next answer): without input scaling, GECO fails beyond the training size on ATSP, CVRP and CVRPTW.

Q5: Only OP has results without normalization ("None"). I would like to see the same for all problems.

We thank the reviewer for this suggestion. Following it, we ran GECO without any input scaling on the other routing problems, and also with GOAL's hand-designed scaling (gap in %, NN = 100 / 200 / 500 / 1000). Entries already in the paper (Tables 2 and 11) are repeated from it, and all other entries use one seed:

VariantATSPCVRPTWOP
GOAL's input scaling instead of our normalizer0.62 / 0.80 / 0.85 / 1.093.93 / 5.50 / 6.27 / 3.38GOAL applies none (next row)
no input scaling at all0.39 / 0.91 / 3.96 / 104.2854.91 / 64.50 / 72.51 / 70.24-0.19 / 1.43 / 3.90 / 10.37
our normalizer: GECO0.31 / 0.55 / 0.81 / 0.874.21 / 5.37 / 5.55 / 2.26-0.34 / 0.27 / 2.98 / 5.11

Without any scaling, the model fails beyond the training size: the gap reaches 104% on ATSP1000, 61% on CVRP1000 and 55–73% on CVRPTW at every size. On CVRP the full row is 3.27 / 14.36 / 21.25 / 61.37, against 2.37 / 2.37 / 3.36 / 4.79 in Table 11. With GOAL's hand-designed scaling, accuracy drops on ATSP at small sizes and on CVRPTW at large sizes. We will add these rows to Table 11.

Reviewer_ByvmOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
1
Soundness
1
Read review
Paper summary

This paper proposes GECO, a neural architecture for combinatorial optimization that aims to be both general and efficient. The main idea is to reduce the computational cost of handling edge information while using the same architecture across different problems. The method has three main components. SMA processes edge information in the attention scores to reduce computation and memory usage. The warm-up layer uses edge information to initialize node embeddings, while the feature normalizer provides a common way to scale features based on the problem formulation. The authors test GECO on five combinatorial optimization problems, including ATSP, CVRP, CVRPTW, OP, and JSSP. The results show that GECO achieves good solution quality with lower computational cost than existing edge-aware methods. The paper also includes ablation studies and efficiency comparisons to evaluate the proposed design.

Critical strengths
  1. Methodological Novelty: The paper addresses the challenge of balancing efficiency and generality in neural combinatorial optimization architectures. The proposed SMA improves computational efficiency, while the warm-up layer and feature normalizer enhance architectural generality, offering interesting and innovative design ideas.
  2. Comprehensive Experiments: The paper presents extensive experiments across five combinatorial optimization problems, including baseline comparisons, ablation studies, and computational efficiency evaluations, providing empirical support for the effectiveness of the proposed method.
Critical weaknesses
  1. Although the paper provides several ablation studies, GECO makes multiple changes compared with GOAL, including SMA, the warm-up layer, and the feature normalizer. These changes are evaluated on different subsets of tasks, so their individual contributions to the overall improvement remain unclear. It is also unclear how these components interact with each other. For example, Table 10 shows that applying log-scaling to GOAL reduces the CVRPTW1000 gap from 26.34% to 10.37%, suggesting that score calibration may account for part of the improvement over GOAL rather than SMA alone. While the efficiency gains are convincing, the contribution of SMA to the improvements in solution quality is not fully clear.
  2. The paper proposes a general feature normalization method, but it does not clearly show how the features are grouped for each of the five tasks. Also, Table 11 shows that different normalization choices can lead to large differences in performance, even when they follow the same instance-preserving principle. This raises some questions about how easily the proposed method can be applied to new problems and how its normalization settings should be chosen.
Questions for authors

1.Although the paper includes several ablation studies, the components are evaluated on different subsets of tasks. How do the authors distinguish their individual contributions of these components and their interactions, particularly the role of SMA in improving solution quality? 2. In Section 3.3, how are the features grouped for each of the five CO problems? What needs to be specified or adapted when applying the proposed framework to a new problem? 3. Are the reported results based on single runs or multiple training seeds? Could the authors also clarify the number of test instances used for each problem size and the batch size used for inference? 4. Although the methodology is described in detail, Figure 1 does not clearly distinguish the proposed components. Could the authors clarify their distinctions and connections in the figure? 5. In Section 3.2, the warm-up layer uses scalar edge projections instead of vector-valued projections. Could the authors briefly discuss the trade-off between computational efficiency and expressiveness in this design? 6. What is the size of the test dataset? How are Gap and Time calculated in the result table? 7. What is the reasons for setting the scaling factor r=0.5r=0.5 in Equation (3)? Has it been verified by experiments? 8. Descriptions for some symbols are unclear, such as symbol C below Equation (2) and b_{ij}^v in Equation (7).

6 comments
AuthorsOpenReview ↗

Response (1 / 4)

We sincerely thank the reviewer for the detailed and constructive review, and for recognising the novelty of the method and the breadth of the experiments. Below we address the concerns on the contribution of each component, on the feature normalizer, and on clarity.

W1 / Q1: The components are evaluated on different subsets of tasks, so their individual contributions and interactions remain unclear, in particular the role of SMA in solution quality.

We sincerely thank the reviewer for this careful comment, and we fully agree with it. In the submission each component was ablated on two tasks, and not the same two (Tables 3, 4, 5 and 11), which made the individual contributions hard to read.

Following the reviewer's suggestion, every component is now ablated on the same three tasks under one protocol, and each one contributes (gap in %, NN = 100 / 200 / 500 / 1000). Entries already in the paper (Tables 2, 4, 5 and 11) are repeated from it, and all other entries use one seed:

VariantATSPCVRPTWOP
GECO0.31 / 0.55 / 0.81 / 0.874.21 / 5.37 / 5.55 / 2.26-0.34 / 0.27 / 2.98 / 5.11
w/o ScoreNorm (shift and log NkN_k)0.56 / 0.74 / 1.04 / 1.464.05 / 5.56 / 8.38 / 6.58-0.19 / 0.11 / 3.69 / 5.23
w/o log NkN_k only0.42 / 0.66 / 0.97 / 1.124.08 / 5.63 / 7.87 / 6.58-0.29 / 0.48 / 5.65 / 6.84
w/o query-axis shift only0.47 / 0.70 / 1.03 / 1.094.15 / 5.86 / 6.75 / 3.50-0.30 / -0.03 / 4.45 / 9.85
w/o ChannelMixer1.05 / 1.33 / 1.31 / 1.265.03 / 6.23 / 6.87 / 3.270.02 / 0.11 / 3.01 / 5.86
random IDs instead of warm-up0.23 / 0.52 / 0.89 / 0.984.04 / 5.60 / 6.48 / 3.10-0.16 / 0.65 / 4.96 / 10.58
warm-up + random IDs0.35 / 0.61 / 0.85 / 1.024.10 / 5.94 / 6.16 / 3.21-0.18 / 0.30 / 3.98 / 6.02
GOAL's input scaling instead of our normalizer0.62 / 0.80 / 0.85 / 1.093.93 / 5.50 / 6.27 / 3.38GOAL applies none (next row)
no input scaling at all0.39 / 0.91 / 3.96 / 104.2854.91 / 64.50 / 72.51 / 70.24-0.19 / 1.43 / 3.90 / 10.37

What the table shows for each component:

  • ScoreNorm matters most at large sizes: removing both of its parts hurts accuracy in most settings.
  • ChannelMixer matters at every size on ATSP and CVRPTW, the two tasks whose pairwise attributes are intrinsic (ATSP100: 0.31 to 1.05). On Euclidean OP its effect is smaller.
  • The warm-up is ahead of random identifiers at NN ≥ 500 on all three tasks, by 0.9 and 0.8 points on CVRPTW at NN = 500 and 1000. Random IDs on top of the warm-up add nothing.
  • Normalizer: without any input scaling, the model fails beyond the training size on ATSP and CVRPTW. With GOAL's hand-designed scaling, accuracy drops on ATSP at small sizes and on CVRPTW at large sizes.

On task coverage, the three tasks together cover all input types of our routing problems, and on CVRP at NN = 1000 removing each component also raises the gap. The input types are asymmetric edge costs without node features (ATSP), capacity and time-window constraints (CVRPTW, which extends CVRP), and prizes under a budget (OP). On CVRP at NN = 1000, the same ablations give 6.98 (w/o ScoreNorm), 5.05 (w/o ChannelMixer), 6.51 (random IDs), 7.87 (GOAL's scaling) and 6.29 (ReZero only), against 4.79 in Table 2. The JSSP ablations take 3–5 GPU-days each and could not be finished within the rebuttal period. We will add them to the final version.

AuthorsOpenReview ↗

Response (2 / 4)

W1 / Q1 (continued): Table 10 shows that log-scaling reduces GOAL's CVRPTW1000 gap from 26.34% to 10.37%, so score calibration may account for part of the improvement rather than SMA alone. How do the components interact?

We agree that calibration does account for part of the improvement over GOAL. We thank the reviewer for pointing it out, and we would like to make precise which part, and what SMA adds on top.

First, ScoreNorm has two parts, the log NkN_k factor of Table 10 that we adopt from SSMax [1] and a query-axis shift of our own design, and the adopted factor explains only part of the gain. The factor is cited as such in Sec. 3.1, and the shift is ablated in Table 9.

  • With the factor, GOAL reaches 1.19 / 1.70 on ATSP and 10.07 / 10.37 on CVRPTW at NN = 500 / 1000 (Table 10), where GECO has 0.81 / 0.87 and 5.55 / 2.26. So the factor explains part of the gain on CVRPTW and almost none on ATSP.
  • Conversely, GECO without the factor (Table 4: 0.97 / 1.12 and 7.87 / 6.58) is still ahead of GOAL with it.
  • Removing only our shift costs 0.15–0.22 points on ATSP at NN ≤ 500 and 1.2 points on CVRPTW at NN = 500 and 1000 (new row in the table of part 1).

Second, to separate SMA from calibration, we trained two new GOAL variants on CVRPTW, the reviewer's example: with the same calibration and the same backbone, SMA is better than GOAL's attention at every size, at a fraction of the inference time (rows 3 and 4 are new, and everything not named in a row is GOAL's):

Model on CVRPTWGap (%)Inference time relative to GECO
GOAL4.66 / 7.19 / 18.48 / 26.34
GOAL + log NkN_k only, at inference– / – / 10.07 / 10.37
GOAL + ScoreNorm in its own attention, trained4.92 / 6.17 / 7.28 / 4.303.6× / 6.1× / 9.2× / 9.1×
GOAL-SMA: GOAL's attention replaced by SMA4.44 / 5.93 / 6.22 / 2.781.5× / 1.3× / 1.5× / 1.6×
GECO4.21 / 5.37 / 5.55 / 2.261×

At NN = 1000 the gap goes from 26.34 (GOAL) to 10.37 (adopted factor), 4.30 (full ScoreNorm, trained), 2.78 (SMA in place of GOAL's attention) and 2.26 (GECO). So at equal calibration, SMA's score-space fusion and mixer are better than GOAL's pairwise feature fusion at every CVRPTW size. (Times are for the 128 test instances, each model against GECO on the same GPU type. At NN ≥ 500 the two GOAL variants need smaller batches to fit in memory, and GOAL + ScoreNorm is trained on four GPUs at the same effective batch size.)

Third, the same holds against a MatNet-style scorer: with the same calibration it is behind SMA at every CVRPTW size and at three of the four OP sizes, at 1.8–2.1× the time and 2.9–4.2× the memory. GECO-MatNet changes only the scorer and keeps ScoreNorm, and its cost is in Table 6. Beyond Table 3, it gives 4.88 / 6.12 / 6.57 / 3.22 on CVRPTW and -0.09 / 0.17 / 3.18 / 8.57 on OP.

Overall, we agree with the reviewer that calibration is an important part of the gain, and SMA adds to it through its mixer and, at equal calibration, through better quality than GOAL's attention on CVRPTW at a fraction of the time. The mixer alone takes ATSP100 from 1.05 to 0.31. We will state this decomposition explicitly in the revised paper, together with the unified ablation table.

References

  • [1] Nakanishi, Scalable-Softmax Is Superior for Attention, arXiv:2501.19399, 2025
AuthorsOpenReview ↗

Response (3 / 4)

W2 / Q2: How are the features grouped for each of the five problems, and what needs to be specified for a new problem? Table 11 shows that different normalization choices can lead to large differences.

We thank the reviewer for this helpful comment. We agree that the paper should have listed the feature groups explicitly, and we apologize for the omission.

Each problem has one or two feature groups, listed below, and each group is divided by one shared factor that is recomputed at every construction step.

ProblemGroups
ATSP{distance}
CVRP{distances} and {demands, remaining capacity, vehicle capacity}
CVRPTW{demands, remaining capacity, vehicle capacity} and {travel times, service times, window starts, window ends, departure time}
OP{distances, travel budget} and {prizes}
JSSP{processing times, job availability times, machine availability times}, with the 0/1 precedence and machine edges left unscaled

For a new problem, the features and their grouping follow from its MILP formulation. The features are the instance data that enter the formulation as coefficients, right-hand sides or bounds, together with the running quantities of the partial solution, such as the remaining capacity. For the grouping (Step 1 of Sec. 3.3), two features are linked if their entries appear additively in the same objective or constraint expression, and the groups are the transitive closure of this relation. They are the connected components of a graph over the features, so they can be extracted automatically from the formulation (for the five problems we derived them by hand). In CVRP, the capacity constraint links demands and capacity, and the objective contains only distances, which gives the two groups above. The same statistic (RMS), aggregation (mean) and step-wise schedule serve all five problems. Minimum vertex cover, our new problem family, has only 0/1 coefficients and needs no group at all.

On Table 11, we agree that the choices matter: the large differences are between one-shot and step-wise normalization, and the step-wise variants are much closer to each other. Among the three step-wise CVRP rows the differences are at most 0.25 points, except at NN = 500, where the difference (1.0) is of the size of the variation between training runs: two runs of the same step-wise Max–Max configuration differ by 0.75 there. So we fix one setting, RMS with mean aggregation recomputed at every step, and use it unchanged for all five problems.

We will add the group table and the recipe to Sec. 3.3.

Q3 / Q6: Are the results based on single runs or multiple seeds? What are the number of test instances and the inference batch size, and how are Gap and Time calculated?

We thank the reviewer for these questions. This information should have been in the paper.

Seeds: on the four routing problems, GECO's entries in Table 2 are means of three training runs, while JSSP is a single run because of its training cost. The revision will add standard deviations to Table 2 and multiple JSSP runs. The gaps of Table 2, with ± the standard deviation between runs measured on three re-trained seeds, are (NN = 100 / 200 / 500 / 1000):

TaskGap ± standard deviation
ATSP0.31 ± 0.06 / 0.55 ± 0.02 / 0.81 ± 0.10 / 0.87 ± 0.07
CVRP2.37 ± 0.03 / 2.37 ± 0.22 / 3.36 ± 0.25 / 4.79 ± 0.34
CVRPTW4.21 ± 0.15 / 5.37 ± 0.33 / 5.55 ± 0.40 / 2.26 ± 0.32
OP-0.34 ± 0.11 / 0.27 ± 0.06 / 2.98 ± 0.38 / 5.11 ± 0.39

Test sets: we use GOAL's test sets for the routing problems and the 100 instances per size of L2D for JSSP. ATSP has 10,000 / 128 / 50 / 33 instances at NN = 100 / 200 / 500 / 1000. CVRP, CVRPTW and OP have 128 instances at every size.

Batch size: inference uses batches of 10,000 / 1,000 / 128 / 32 instances at NN = 100 / 200 / 500 / 1000, capped at the number of test instances. As stated in Sec. 4, the same batch size is used for all neural solvers when time is measured.

Gap is the mean over the test instances of 100 × (cost − reference) / reference, and Time is the wall-clock time to solve the whole test set of that size with greedy decoding on one RTX 3090. The reference comes from LKH (ATSP, CVRP), HGS (CVRPTW), EA4OP (OP) and OR-Tools (JSSP). For OP, where the prize is maximized, the sign is flipped.

We will add this protocol paragraph to Sec. 4.

Reviewer_iaUJOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes GECO, a constructive neural solver architecture for edge-aware graph combinatorial optimization. Building on GOAL's layout, it introduces four changes: ScoreMixer-in-Attention (SMA), which fuses edge features additively into attention logits and refines them across heads with a small residual MLP; ScoreNorm, which counters attention dilution when generalizing to larger sizes; a warm-up attention layer that gives nodes distinguishable embeddings from edge information; and an instance-preserving normalizer applied at every construction step. Models are trained separately by supervised learning on ATSP, CVRP, CVRPTW, OP and JSSP at small sizes and tested up to N=1000. The paper reports solution quality close to or better than GOAL, with large efficiency gains

Critical strengths
  1. Efficiency gains are large and well supported. Time, peak memory, FLOPs and training cost are all reported against GOAL and a controlled GECO-MatNet variant. GECO-MatNet keeps all other components, so the comparison isolates the attention design. Because these are architectural properties, they are fairly robust to the training protocol, and they matter for step-wise inference, where the cost recurs at every step.

  2. Candid and diagnostic analysis. The paper states what SMA gives up and shows that a wide-mixer concatenation variant would contain MatNet. The ScoreNorm and normalization design choices are tied to concrete diagnostics. This makes the contribution more than a collection of tricks.

Critical weaknesses
  1. GOAL is retrained in a single-task setting for each problem, and GOAL's original paper positions it as a generalist. If its architecture is designed for multi-task training, the single-task numbers may understate its performance.

  2. Absolute performance is not convincing against single-task SOTA. In the single-task setting, task-specific SOTA methods are generally much stronger than multi-task ones. Without stronger task-specific baselines, the quality claim is hard to assess outside the multi-task scenario.

  3. No evidence that the design transfers to stronger backbones. SMA, ScoreNorm, the warm-up layer, and the normalizer are only tested on the GOAL-style backbone. It is unclear whether they help on other strong constructive solvers, which is the key test of the "generic" claim.

Questions for authors
  1. Can SMA, ScoreNorm, the warm-up layer, and the instance-preserving normalizer be plugged into existing SOTA constructive solvers and still improve quality or efficiency?

  2. Why does explicit-edge input help at N=100/200 on CVRP but not at 500/1000, and what explains GECO's faster runtime growth versus BQ-NCO?

  3. Can you report GOAL-SMA on CVRP and other tasks, and an ablation of ReZero+RMSNorm vs. ReZero, to separate the contribution of each component?

3 comments
AuthorsOpenReview ↗

Response (1 / 3)

We sincerely thank the reviewer for the careful evaluation of our work, and for the encouraging comments on the efficiency analysis and on the discussion of what SMA gives up. Below we address the concerns about the GOAL baseline, the comparison with task-specific solvers, and the transfer of our components to other solvers.

W1: GOAL is retrained in a single-task setting, although it is positioned as a generalist. The single-task numbers may understate its performance.

We thank the reviewer for raising this important point. We fully agree that a generalist model should be compared in the setting that suits it best, and we apologize that the paper did not describe the GOAL baseline clearly enough.

The GOAL's results of Table 2 are from the official single-task checkpoints released by the GOAL authors, evaluated with their official code, and not from a weaker re-training.

Following the reviewer's suggestion, we also evaluated GOAL's officially released multi-task checkpoint, and it is generally behind its respective single-task checkpoint (gap is reported, NN = 100 / 200 / 500 / 1000):

ModelATSPCVRP
GOAL, multi-task1.61 / 1.69 / 1.67 / 2.313.62 / 4.07 / 5.36 / 9.45
GOAL, single-task0.56 / 0.88 / 1.25 / 1.672.41 / 2.86 / 4.27 / 7.27
GECO0.31 / 0.55 / 0.81 / 0.872.37 / 2.37 / 3.36 / 4.79

Single-task GOAL is the stronger of the two GOAL models on all the datasets, which suggests that the single-task setting does not understate GOAL. This agrees with the main table of GOAL paper itself [1]. We will state clearly how each GOAL number was obtained in our revision.

References

  • [1] Drakulic et al., GOAL: A Generalist Combinatorial Optimization Agent Learner, ICLR 2025
AuthorsOpenReview ↗

Response (2 / 3)

W2: Absolute performance is not convincing against single-task SOTA. Task-specific SOTA methods are generally much stronger than multi-task ones, and stronger task-specific baselines are needed.

We thank the reviewer for this constructive comment. We agree that a comparison with strong task-specific solvers is essential for judging solution quality, and we address it from three angles.

First, the comparison in Table 2 is already a single-task one. We should have stated this more prominently. Every model in Table 2 is trained separately for each problem (Sec. 4), including GOAL and GECO itself. The baselines include solvers developed for routing problems (POMO, Sym-NCO, BQ-NCO, LEHD and ICAM), for matrix-encoded problems such as ATSP (MatNet), and for job-shop scheduling (L2D).

Second, following the reviewer's suggestion, we added RADAR [2], the most recent solver designed for asymmetric routing: GECO is ahead of it at NN ≥ 200, and at every size when both decode a single trajectory. We evaluated its released checkpoint on our ATSP test sets with the scoring of Table 2 (gap in %, NN = 100 / 200 / 500 / 1000, GECO as in Table 2):

ModelATSP
RADAR, best of NN trajectories0.12 / 0.78 / 1.84 / 3.69
RADAR, one greedy trajectory1.25 / 2.63 / 4.33 / 6.83
GECO, one greedy trajectory0.31 / 0.55 / 0.81 / 0.87

With a single greedy trajectory, which is GECO's decoding budget, GECO is ahead of RADAR at every size. With its own inference, which keeps the best of NN trajectories per instance, RADAR is ahead at the training size NN = 100, and GECO is ahead from NN = 200 onward.

Third, we agree with the reviewer that specialised solvers remain very strong on Euclidean routing: we do not claim the state of the art there, and a wider mixer (rr = 1, one seed) still brings GECO ahead of BQ-NCO, LEHD and GOAL on CVRP at NN = 100, 200 and 1000. Our claim is a generic architecture for problems whose pairwise attributes are intrinsic. With rr = 1 instead of 0.5, GECO reaches 2.08 / 2.53 / 3.05 / 4.65 on CVRP, level with LEHD at NN = 500.

Overall, we agree that more task-specific baselines would further strengthen the paper, and we will gladly include any further solver the reviewer recommends. Training more of them under a matched protocol did not fit into the rebuttal period. We will make the single-task setting and the scope of our claim explicit in the revised paper.

References

  • [2] Yi et al., RADAR: Learning to Route with Asymmetry-aware Distance Representations, ICLR 2026
AuthorsOpenReview ↗

Response (3 / 3)

W3 / Q1: Can SMA, ScoreNorm, the warm-up layer and the normalizer be plugged into existing SOTA constructive solvers and still improve quality or efficiency?

We thank the reviewer for this insightful question. We agree that transfer to other backbones is a key test of the "generic" claim. Within the rebuttal period we tested it inside GOAL, the strongest existing edge-aware solver, in both directions.

First, SMA improves GOAL when it replaces GOAL's attention: the gap falls at every CVRPTW size (26.34 to 2.78 at NN = 1000) and on CVRP at NN ≥ 500. This also answers the first part of Q3. ATSP is in Table 3, and on CVRP and CVRPTW we obtain (gap in %, NN = 100 / 200 / 500 / 1000, GOAL as in Table 2):

ModelCVRPCVRPTW
GOAL2.41 / 2.86 / 4.27 / 7.274.66 / 7.19 / 18.48 / 26.34
GOAL-SMA2.49 / 2.83 / 2.79 / 4.834.44 / 5.93 / 6.22 / 2.78

On CVRPTW1000, the inference time is then 1.6× that of GECO, against 9.1× with GOAL's own attention.

Second, ScoreNorm improves GOAL's own attention on large CVRPTW instances: trained into GOAL, it lowers the gap at NN = 1000 from 26.34 to 4.30. The adopted log NkN_k factor alone, applied at inference (Table 10), gives 10.37, so the gain does not come from that factor alone.

Third, in the opposite direction, MatNet's scorer in place of SMA makes GECO worse at every CVRPTW size and at three of the four OP sizes. Beyond Table 3, this variant gives 4.88 / 6.12 / 6.57 / 3.22 on CVRPTW and -0.09 / 0.17 / 3.18 / 8.57 on OP.

We acknowledge that we have not yet integrated the components into solvers outside the GOAL family, and we will state this as a limitation. This requires re-implementing and retraining each solver and did not fit into the rebuttal period. The normalizer acts on the inputs and the warm-up is the first layer, so neither depends on the rest of the backbone.

On genericity across problems, we also added a new problem family, minimum vertex cover: with random identifiers GECO is ahead of GOAL's official released checkpoint at every size, and with the warm-up it is the most accurate of the three at NN = 1000 (trained at NN = 100, gap in %, one checkpoint per row, details in our reply to Reviewer yNN8):

ModelNN = 1002005001000
GOAL (official released checkpoint)0.270.7515.9615.87
GECO, random-ID initialization0.140.372.186.44
GECO, warm-up0.330.702.223.34

Q2: Why does explicit-edge input help at NN = 100 / 200 on CVRP but not at 500 / 1000, and what explains GECO's faster runtime growth versus BQ-NCO?

We thank the reviewer for these two thoughtful questions.

On accuracy, we attribute the pattern to two regimes: near the training size the edge input gives every attention head the exact distances, and far beyond it both variants are limited by the same size extrapolation. Near the training size, the coordinate variant has to compute the distances inside the network, which is where the edge interface gains (3.22 to 2.37 at NN = 100). The input interface does not change the size extrapolation, so the two variants meet at large NN (Table 14).

On runtime, the reviewer is right that GECO grows faster than BQ-NCO on CVRP, and the reason is the edge input rather than SMA: on ATSP, where BQ-NCO also processes edges, its time matches GECO's. On CVRP, BQ-NCO is a node-only model: it embeds NN coordinate vectors and never processes an NN × NN edge input. On ATSP (Table 2) it needs 2m / 10s / 1m / 6m, against 2m / 9s / 59s / 5m for GECO. We will add this remark to Sec. 4.2.

Q3: Can you report GOAL-SMA on CVRP and other tasks, and an ablation of ReZero + RMSNorm vs. ReZero?

We thank the reviewer for these suggestions, and we ran both.

GOAL-SMA on CVRP and CVRPTW is in the table above: SMA lowers GOAL's gap on CVRP at NN = 500 (4.27 to 2.79) and NN = 1000 (7.27 to 4.83), and on CVRPTW at every size.

For ReZero + RMSNorm against ReZero alone, we ran the ablation on three tasks, and RMSNorm lowers the gap on all three (gap in %, NN = 100 / 200 / 500 / 1000, GECO as in Table 2, ReZero only with one seed):

VariantATSPCVRPTWOP
ReZero only0.56 / 0.71 / 1.00 / 1.014.24 / 5.59 / 6.23 / 3.26-0.27 / 0.63 / 3.48 / 5.07
ReZero + RMSNorm: GECO0.31 / 0.55 / 0.81 / 0.874.21 / 5.37 / 5.55 / 2.26-0.34 / 0.27 / 2.98 / 5.11

We hope these clarifications and additional results address the reviewer's concerns, and we are happy to provide any further detail.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.