acceptodds
Under review as a conference paper at ICLR 2027

Scone: Symmetry-aware Neural Combinatorial Optimization for Graph Coloring

Abstract

Graph coloring, which entails assigning colors to nodes such that no adjacent nodes have the same color, is a fundamental combinatorial optimization problem. In general, however, finding a node coloring with no monochromatic edges given a fixed palette is NP-hard. This motivates learning-based methods that can learn to exploit recurring structure across instances to efficiently produce high-quality colorings. Crucially, the validity of a coloring is invariant to permutations of the colors, and we show that exploiting this symmetry reduces the size of the effective state space over which the model has to learn its policy. At the same time, the coloring algorithm must be able to break some symmetries, for example to assign different colors to two adjacent nodes belonging to the same automorphism orbit. In this paper, we introduce Scone, a model that uses a color-equivariant graph neural network to construct colorings sequentially, allowing information from previous assignments to propagate and break node symmetries. Scone achieves perfect solution quality with low inference times across several graph coloring tasks, including on sudoku_extreme and register allocations, and showcases generalization to graph families not encountered during training.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
graph neural networks, neural combinatorial optimization, graph coloring

Reviews

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

The paper aims to develop a neural framework to solve graph coloring problem. The main theme of the paper is studying the symmetries involved while solving the coloring problem. It can be observed that a valid coloring is invariant to permutations of the colors. Also, some nodes may appear symmetrical and solver may assign a similar color but one has to make sure that no adjacent nodes are labelled the same color. The paper targets these symmetries by proposing SCONE , a framework that combines color-permutation equivariance with sequential decoding. The solver uses a message-passing GNN that maintains separate, shared-parameter embeddings for each color, ensuring that its predictions transform consistently under color relabeling. To avoid color conflicts between adjacent nodes, SCONE assigns colors sequentially, one node at a time, allowing previous assignments to break node symmetries and distinguish nodes that are otherwise indistinguishable to an equivariant predictor. Theoretically, the authors characterize the reduction in the effective state space induced by color equivariance and establish expressivity results for sequential coloring on specific graph families. Experimentally, SCONE is evaluated on Sudoku, register-allocation, and examination-timetabling instances as well as on synthetic graph families. The results demonstrate strong solution quality, fast inference and good generalization to graph families not encountered during training. Ablation studies also suggest that architectural color equivariance improves performance especially for graphs with large chromatic number.

Critical strengths
  1. The symmetry-aware approach taken is well motivated as one usually observes that using plain GNN does not target these symmetries and often lead to poor coloring solutions. Rather than predicting colors simultaneously for all nodes, the sequential decoding approach helps to distinguish nodes properly as coloring progresses.

  2. The proposed color-equivariant message-passing GNN respects color-label permutations by construction, exploiting the inherent symmetries of graph coloring rather than relying solely on data augmentation.

  3. The paper’s theoretical approach distinguishes it from other works on neural solvers. From the start, the authors explain graph symmetries using the concepts of automorphisms and orbits. Further, in theoretical analysis, it is discussed how effective state space reduces due to color equivariance. Also the paper establishes expressivity results for sequential coloring on specific graph families.

  4. For experimental evaluation, the method is evaluated across diverse graph-coloring applications, including Sudoku, register allocation, examination timetabling and synthetic graph families. The reported results demonstrate strong solution quality and competitive inference times.

Critical weaknesses
  1. SCONE requires up to O(n) forward passes to color a graph with n nodes. This sequential dependence may limit its applicability to large-scale graph-coloring instances and the experiments do not fully establish how the method scales with graph size.

  2. The model takes number of colors to be used for coloring (k) as input and in cases when one has to particularly find the chromatic number, we need to solve multiple times for different values of k.

  3. The method acts as a heuristic and does not provide solution guarantees. It always returns a complete coloring but it does not guarantee that the coloring is proper or certify infeasibility for a given palette.

  4. The model is not tested properly against state of the art methods. Comparisons are drawn with heuristics such as greedy and Dsatur. Although we have much stronger heuristics such as Recursive Largest First (RLF) and also a lot of metaheuristics that have demonstrated good performance. Few of these methods should also be considered for comparison.

  5. Although it is a positive aspect of the paper that the authors evaluate SCONE on instances drawn from practical applications, it would also be valuable to include standard DIMACS benchmark instances which are widely used in the graph coloring literature. This would facilitate a more direct comparison with existing methods and provide a better assessment of the proposed approach on established benchmarks.

Questions for authors
  1. As pointed out in the weaknesses , it would be useful to provide a more detailed scalability analysis. How does the inference time grow with increasing graph size, particularly for graphs containing thousands of vertices? Including experiments on larger instances would help establish the practical scalability of the proposed approach.

  2. The experimental evaluation should include state of the art metaheuristics like HEAD or swarm optimization based algorithms and heuristics like Recursive Largest First (RLF) for a fair comparison. Furthermore, for comparison with neural solvers, one can also include the neural solver based on sequential coloring discussed in the paper “graph coloring via metric guided independent set extraction”. How does SCONE perform against these approaches in terms of solution quality and computational time under comparable computational budgets ?

  3. The evaluation must be extended to standard DIMACS graph coloring benchmarks. These instances are widely used in the graph coloring literature and would allow a more direct comparison with existing state-of-the-art methods. Evaluating SCONE on these benchmarks would also help assess its effectiveness in dealing with color symmetries on graphs with diverse structural properties and varying levels of difficulty.

  4. As a suggestion, the presentation could be made more accessible to a broader audience by simplifying the explanations of technical concepts such as automorphisms, orbits, and stabilizers and providing more intuitive explanations or examples to help readers understand their role in the proposed approach.

4 comments

Thank you for your insightful review and for your positive remarks, especially on our theoretical approach distinguishing the paper from other works on neural solvers, and on the strong solution quality and competitive inference times. We address your comments one by one below.

W1/Q1 SCONE requires up to O(n) forward passes to color a graph with n nodes.

As discussed in Appendix A, requiring up to O(n)O(n) forward passes to color a graph with nn nodes is indeed one of the limitations of Scone, as it can limit scaling inference efficiently to graphs with several thousand nodes. However, this additional computational cost comes with the benefit of allowing sequential decoding to fully exploit information from previous color assignments. Therefore, on graphs with up to several hundred nodes, it is arguably a worthy trade-off. Following your suggestion, we have now added Figure 12, which plots the runtimes of Scone on synthetic graphs with up to 10k nodes, using both greedy decoding and beam search with width 16. As shown by the plot, greedy inference is below one second even for graphs with a thousand nodes.

W2 The model takes number of colors to be used for coloring (k) as input and in cases when one has to particularly find the chromatic number, we need to solve multiple times for different values of k.

Your observation is indeed correct, to search for smaller upper bounds on the chromatic number one has to run Scone multiple times for different values of k. This fixed-palette setting is also considered by AnyCSP and ConsFormer, and is standard in CSP and ILP formulations of graph coloring.

Scone can efficiently obtain good upper bounds on the chromatic number. We have added Figure 10 to evaluate this scenario. Starting from a Dsatur coloring, we repeatedly attempt a proper coloring with one fewer color, stopping at the first failure and retaining the best proper coloring found. Across 20 independent searches, Scone reaches the best-known color counts on all three tested hard instances, faster than AnyCSP.

W3 The method acts as a heuristic and does not provide solution guarantees.

As noted also in the answer above and in Appendix A (Limitations), the comment is correct. Scone, like any other heuristic method, cannot guarantee that it will return a proper coloring given a palette size kk, nor certify that no proper coloring exists. Note that since kk-coloring is NP-complete for n≥3n\geq3, no algorithm can decide feasibility correctly on all graphs in polynomial time unless P=NP. However, given a complete coloring returned by Scone, it is easy to certify that it is proper (by checking that there are no monochromatic edges). Moreover, even in scenarios where exact solutions are required, good-quality heuristics are nonetheless important for screening. For example, if we are given a large number of kk-coloring problems, a heuristic like Scone can be used to solve cheaply a large fraction of them, and only the unsolved instances can be passed to the expensive complete solvers (e.g., ILP or CSP) to find a solution or certify impossibility.

W4/Q2 The model is not tested properly against state of the art methods.

We would argue that ACE, Gurobi and AnyCSP cover different classes of state-of-the-art solvers. However, we agree that adding more baselines would further strengthen the evaluation. Following your suggestion, we have now added RLF and CSO, a recent swarm optimization algorithm, as classical baselines, and GBS as a learning-based baseline. We have also added two more neural baselines based on another reviewer's comment. As reported in Tables 1,3,4 and Tables 10,11 in the appendix, the most competitive baselines remain ACE and AnyCSP.

W5/Q3 It would also be valuable to include standard DIMACS benchmark instances which are widely used in the graph coloring literature

Datasets drawn from practical applications are indeed a focus of our evaluation. However, we agree that comparing on well-established benchmarks can help compare to related work. We have now added three more families of graphs from the DIMACS collection (besides the already-present Queens and Mycielski graphs), see Tables 12,13,14,15. In particular, books are graphs where nodes are connected by an edge if the corresponding characters encounter each other in the book, DSJC are Erdos-Renyi graphs and le450 are random graphs with guaranteed coloring size. Results on these graphs confirm the Scone generalizes to unseen instances, often being on par or better than state-of-the-art solvers like ACE and AnyCSP.

Q4 Tthe presentation could be made more accessible to a broader audience by simplifying the explanations of technical concepts such as automorphisms, orbits, and stabilizers

Thanks for the suggestion, we have added a few more intuitive explanations for automorphisms and orbits (line 101) and for stabilizer groups (line 297).

Dear Reviewer iJhw,

Thanks for your insightful review. We hope that our response has adequately addressed all your comments, particularly with regard to the new scalability experiments and the addition of new datasets and baselines. As the discussion period will end in less than 2 days, we would appreciate it if you could take a look at our rebuttal and let us know if you have any further or follow-up questions so that we can address them in time.

I thank the authors for their response and for addressing the concerns raised in my initial review. From figure 12 included, it is good to observe that the method is scaling well for large graphs. Also I appreciate the inclusion of additional baselines such as RLF,GBS,CSO etc and DIMACS instances in the experimental evaluation. The additional experimental results included helps in better comparison and understanding the novelty of the proposed approach. I will maintain my rating of 3.

Thank you for your reply. We are glad that our responses and additional experiments have addressed your concerns.

Reviewer_aKcHOpenReview ↗
Rating
4(+1)
Confidence
2
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper introduces SCONE (Symmetry-aware COloring via Neural Equivariance), a neural approach to graph coloring that combines sequential coloring with a graph neural network (GNN) equivariant to both node and color permutations. Sequential coloring allows the model to break node symmetries that would otherwise prevent an equivariant GNN from distinguishing certain neighboring nodes. Color equivariance is achieved through color-specific embeddings and permutation-equivariant message passing, while symmetry-aware training treats unused colors as interchangeable. During inference, learned color scores are combined with deterministic node ordering and forced-assignment propagation.

The authors provide theoretical results on state-space reduction and model expressivity, together with empirical evaluations on Sudoku, register allocation, exam timetabling, and synthetic graph families.

I recommend weak acceptance. The work is technically coherent and well motivated, with strong empirical results, controlled color-equivariance ablations, and evidence of transfer across graph families supporting its contributions.

My main concern is that the reported improvements are not sufficiently attributed to learned guidance independently of the surrounding constraint-solving components. An additional baseline using heuristic color scores within the same decoding procedure would substantially strengthen this aspect of the evaluation.

The reliance on predefined feasible palettes and the limited characterization of inference-time variability also deserve further discussion in the paper.

Critical strengths
  1. Well-motivated architectural design.

The paper clearly explains how the proposed approach exploits color symmetries while breaking node symmetries when necessary. Sequential construction addresses the limitations of simultaneous node predictions, while the color-equivariant architecture incorporates an appropriate inductive bias by construction. Symmetry-aware training further complements this design by avoiding arbitrary distinctions between colors that have not yet been used.

  1. Strong empirical results supported by informative ablations.

SCONE achieves a 100% solve rate across the main benchmarks, including Sudoku, Sudoku Extreme, register allocation, and timetabling. In comparison, several state-of-the-art neural and classical methods do not consistently achieve perfect solve rates and often require substantially longer inference times.

Furthermore, Figure 3 demonstrates the advantages of color equivariance in low-data regimes and settings with larger color palettes. These experiments use greedy decoding without forced-assignment propagation, helping to isolate the architectural contribution from additional search mechanisms.

  1. Theoretical motivation and evidence of transfer.

Theorem 1 formalizes the reduction in effective state space, providing strong theoretical motivation for the architectural design. Furthermore, a single trained model transfers to Toronto timetabling problems without fine-tuning, suggesting that the learned coloring strategies generalize across graph families. These results provide encouraging evidence of generalization, even though decoding configurations are selected through deterministic validation on the target graph families.

Critical weaknesses
  1. The contribution of learned color selection is not sufficiently isolated from the decoding procedure.

SCONE combines learned color scores with classical constraint-solving techniques, including most-constrained-first node ordering, forced-assignment propagation, and adaptive search. Although the paper compares against classical solvers and provides ablations of node ordering and search width, the contribution of learned color scores within the same decoding procedure is not fully isolated. In particular, DSATUR follows a single constructive trajectory, whereas SCONE can explore alternative trajectories through search.

A more informative control experiment would replace the neural color scores with a simple heuristic while keeping the remaining decoder components unchanged, including node ordering, propagation, and search budget. Reporting solve rates under greedy decoding, forced-assignment propagation, and increasing search widths would also help clarify the contribution of each component.

  1. Evaluations rely on simplified problem formulations and predefined feasible palettes.

For register allocation, the evaluation omits the implicit clique of precolored register nodes and move preferences, while using each graph's chromatic number as the palette size instead of the original budget of 21 registers. For timetabling, the evaluation does not account for room capacities or proximity costs, applies k-core preprocessing, and uses best-known feasible palette sizes that are not necessarily optimal.

While these assumptions are reasonable for evaluating fixed-palette graph coloring, they do not fully capture the complexity of the original application problems. In particular, providing a feasible palette removes the challenge of determining the required number of colors, which may not be known in practical settings. Evaluating SCONE with different palette sizes, including infeasible ones, would help assess its robustness and practical applicability.

Furthermore, the transfer experiments involve relatively few distinct test graphs, particularly nine Toronto instances and three queen-graph sizes. Evaluating a broader range of graph structures and palette constraints would provide stronger evidence of generalization.

  1. Inference-time comparisons require further characterization.

Appendix D.4 states that the experiments were conducted on a cluster equipped with AMD EPYC 9374F CPUs and NVIDIA H200 GPUs. However, it does not explicitly distinguish which hardware (CPU or GPU) was used for each evaluated method. Clarifying this distinction would help readers interpret the reported runtime comparisons.

Moreover, average inference times may obscure runtime variability associated with adaptive search widths of up to 512. Reporting batch latencies, runtime percentiles, and the distribution of search widths would provide a more complete characterization of inference efficiency.

Questions for authors
  1. How does SCONE perform when neural color scores are replaced by simple heuristic scores, keeping the decoder and computational budgets comparable? How many tasks can be solved using greedy natural decoding without propagation?

  2. Changing the color palettes making them larger or smaller than the actual chromatic number affect performance? When taking into consideration impossible color palettes, how much SCONE minimize monochromatic edges, and would it be able to search for the smallest possible palette without knowing one?

  3. Could the authors clarify the hardware and batching used for each method, along with batch-one latency and runtime percentiles? How often are width searches required?

3 comments

Thank you for your review and for your positive remarks on the strong empirical results and the well-motivated architectural design. We address your comments one by one below.

W1/Q1 Contribution of learned color selection is not sufficiently isolated from the decoding procedure

Thank you for raising this point. We believe that the combination of learning with classical components is one of the strengths of our approach. That said, we agree that it is important to quantify the contribution of the learned component to the solution quality of Scone.

We have added Fig.4 in the main paper, where we compare the full Scone with a version that ablates forced-assignments and a version that replaces the neural scorer with a minimum-conflict heuristic. Each configuration is evaluated using greedy decoding, and decoding widths of 4 and 16. As shown by the figure, the color-equivariant neural scorer is the most important component of Scone, as solution quality without it drops significantly even at width 16, validating the importance of the learned component. We also observe that forced assignments have a relatively small impact on solution quality (they are mostly meant to give a small speedup).

For an additional breakdown of how much search contributes to solution quality, see also Fig.3 on sudoku_extreme. Here, greedy decoding already solves 40% of instances, and going to width 32 solves 98%.

We believe that the assessment of the importance of the learned component further strengthens the paper, thank you for pointing this out.

W2/Q2 Evaluations rely on simplified problem formulations

We acknowledge that, despite putting a focus on real-world data from practical applications, some evaluations use simplified formulations. However, fixed-palette graph coloring exactly models Sudoku, and is a standard formulation of uncapacitated timetabling. Moreover, establishing a solid foundation on solving the standard graph k-coloring problem is important before extending to richer scenarios (e.g. adding move preferences in register allocations or room capacities in timetabling). In fact, this is an interesting direction for future work, as move preferences in register allocation could be incorporated through additional attributed edges. We have added a remark about this in the conclusions.

The transfer experiments involve relatively few distinct test graphs

We agree that more datasets would provide stronger evidence of generalization. We have added three more classes of graphs from the well-established DIMACS collection. Books are graphs where nodes are connected by an edge if the corresponding characters encounter each other in the book, DSJC are Erdos-Renyi graphs and le450 are random graphs with guaranteed coloring size. Results on these graphs confirm that Scone generalizes to unseen instances, often being on par or better than state-of-the-art solvers like ACE and AnyCSP.

Evaluating SCONE with different palette sizes, including infeasible ones, would help assess its robustness

Fixed-palette coloring is an important problem in its own right, particularly in applications with a fixed resource budget. That said, we agree that evaluating Scone with different palette sizes provides a more complete assessment of robustness. We have therefore added two complementary experiments.

Fig.10 examines whether Scone can find a small feasible palette without being given its size. Starting from a Dsatur coloring, we repeatedly attempt a proper coloring with one fewer color, stopping at the first failure and retaining the best proper coloring found. Across 20 repeats, Scone reaches the best-known color counts on all three tested hard instances, faster than AnyCSP.

Moreover, Table 16 evaluates infeasible palettes on register-interference graphs, simulating insufficient registers that necessitate spilling. Scone achieves better conflict rates than AnyCSP. Compared to ILP, it produces comparable solution quality on the least constrained setting and better solutions on the most constrained one.

W3/Q3 Inference-time comparisons require further characterization

All methods were run on the best hardware and settings they support. The classical baselines are run on CPU. All neural baselines are run on the same NVIDIA H200 GPUs, except for the new VColRL baseline, which does not support GPU inference. For Scone, Sudokus and registers are batched (batch-one latency: 0.35s and 0.09s respectively), while isolated instances are not.

We agree that a breakdown of the average runtimes can provide further insights into the method. We added Fig.3, which reports the cumulative runtime (together with the cumulative solved) as the adaptive search increases the beam width on sudoku_extreme. In particular, percentiles of solution times per puzzle are: median 5.7 ms, 90th perc. 49 ms, 99th perc. 0.20 s, max 0.8 s. Please also check Figure 8 for the difference in runtime between greedy decoding and higher decoding widths.

Dear Reviewer aKcH,

Thanks for your insightful review. We hope that our response has adequately addressed all your comments, particularly with regard to the importance of the learned component, the addition of new datasets and palette sizes, and runtime comparisons. As the discussion period will end in less than 2 days, we would appreciate it if you could take a look at our rebuttal and let us know if you have any further or follow-up questions so that we can address them in time.

Dear Reviewer aKcH,

With discussion closing in less than 12 hours, we would be grateful if you could let us know whether our response and manuscript updates have addressed your concerns.

Reviewer_YG5pOpenReview ↗
Rating
3(+1)
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

This paper proposes SCONE, a graph coloring method combining a color-equivariant graph neural network with sequential construction and symmetry-aware supervision. The authors provide theoretical analysis supporting the design and evaluate solution quality, inference efficiency, and generalization on Sudoku, register allocation, exam timetabling, and synthetic graphs. Ablation studies examine the role of color equivariance.

Critical strengths
  1. The design reflects the structure of graph coloring. Color equivariance, sequential coloring, and supervision work together coherently. Comparisons with non-equivariant models and color-permutation augmentation also support the effectiveness of the architectural design.
  2. The experiments report solved-instance rates, conflict rates, and inference times across several applications. Transfer from synthetic training graphs to timetabling and queen graphs is particularly useful evidence that the model learns transferable strategies.
Critical weaknesses
  1. The differences and advantages over closely related work need further clarification. GDN already studies color-equivariant graph neural networks, while ReLCol and other methods use sequential construction. Although the experiments include several baselines, the absence of direct comparisons with these methods limits the assessment of the new designs and their improvements.
  2. The complete method combines a learned model, node-selection rules, forced-assignment propagation, and beam search. The main-text ablations support the role of color equivariance, but the main results do not clearly distinguish the contributions of model predictions and additional search to the solved-instance rate. This makes it harder to assess the main contribution of the method.
Questions for authors
  1. Could you clarify the new designs relative to GDN and ReLCol, and compare closely related methods on the same test graphs with matched color and inference-time budgets? Would the recent VColRL also be a suitable baseline?
  2. Could you present the solved-instance rates and runtimes on the main application benchmarks for a single greedy decoding run, adding forced-assignment propagation, and then adding beam search, to clarify the contribution of each component?
  3. The main text mentions that a few Sudoku instances require 256 beams. Could you report their proportion and runtimes to clarify the computational cost of harder instances?
4 comments

Thank you for the insightful review, and for acknowledging that the theoretical analysis supports the design and that the experiments provide useful evidence that the model learns transferable strategies. We think your comments allowed us to further strengthen the paper, and we address them one-by-one below.

W1/Q1 The differences and advantages over closely related work need further clarification. GDN already studies color-equivariant graph neural networks, while ReLCol and other methods use sequential construction. Although the experiments include several baselines, the absence of direct comparisons with these methods limits the assessment of the new designs and their improvements. Could you clarify the new designs relative to GDN and ReLCol, and compare closely related methods on the same test graphs with matched color and inference-time budgets? Would the recent VColRL also be a suitable baseline?

It is true that GDN also features a color-equivariant predictor, as discussed in Appendix B. However, their design uses linear equivariant updates, which have limited expressivity compared to our DeepSet-based ones, and uses simultaneous color predictions, which do not explicitly condition each assignment on previous ones, unlike sequential decoding. We could not compare to GDN, as they do not have any public implementation. Moreover, ReLCol is indeed sequential, but only learns a vertex-selection policy, while assigning colors through a fixed first-fit rule. On the other hand, Scone learns how to assign colors.

In summary, the novelty of Scone lies in the effective integration of a novel expressive color-equivariant scorer, sequential color prediction, and classical search techniques (e.g. beam search). We have clarified these points and the differences with previous work in the introduction.

After your suggestion, we have added ReLCol and VColRL as baselines. They both produce significantly worse solutions compared to Scone, even when given a larger compute budget, see the updated Tables 1,3,4. Some baselines are deferred to Tables 10-11 in the appendix due to space constraints.

W2/Q2 The complete method combines a learned model, node-selection rules, forced-assignment propagation, and beam search. The main-text ablations support the role of color equivariance, but the main results do not clearly distinguish the contributions of model predictions and additional search to the solved-instance rate. This makes it harder to assess the main contribution of the method. Could you present the solved-instance rates and runtimes on the main application benchmarks for a single greedy decoding run, adding forced-assignment propagation, and then adding beam search, to clarify the contribution of each component?

Thank you for raising this point. We believe that the combination of learning with classical components is one of the strengths of our approach. That said, we agree that it is important to quantify the contribution of the learned component to the solution quality of Scone.

We have added Figure 4 in the main paper, where we compare the full Scone with a version that ablates forced-assignment propagation and a version that replaces the neural scorer with a minimum-conflict heuristic. Each configuration is evaluated using a single greedy decoding run and decoding widths of 4 and 16. As shown by the figure, the color-equivariant neural scorer is by far the most important component of Scone, as solution quality without it drops significantly even at width 16, validating the importance of the learned component. We can also observe that forced assignments have a relatively small impact on solution quality (they are mostly meant to give a small speedup). Please also check Figure 8 for the difference in runtime between greedy decoding and higher decoding widths.

We believe that the assessment of the importance of the learned component further strengthens the paper, thank you for pointing this out.

Q3 The main text mentions that a few Sudoku instances require 256 beams. Could you report their proportion and runtimes to clarify the computational cost of harder instances?

We have now added Figure 3, which reports the cumulative percentage of solved instances and the respective runtime under adaptive beam search. Greedy decoding already solves more than 40% of instances, and going to width 32 solves 98.5%. The remaining hard instances can require more beams (0.04% require up to width 256, which takes 0.8 s), but since they are so few, widening beyond 32 accounts for only an extra 15% of total runtime.

Dear Reviewer YG5p,

Thanks for your insightful review. We hope that our response has adequately addressed all your comments, particularly with regard to differences with related work and the importance of the learned component. As the discussion period will end in less than 2 days, we would appreciate it if you could take a look at our rebuttal and let us know if you have any further or follow-up questions so that we can address them in time.

Dear Reviewer YG5p,

With discussion closing in less than 12 hours, we would be grateful if you could let us know whether our response and manuscript updates have addressed your concerns.

Thank you for the response and the additional experiments. The new results have substantially alleviated my main concerns about the contribution of the learned component and the comparisons with related methods. After considering the additional evidence, I have decided to raise my rating from 2 to 3.

Comments on the paper

1 comment
AuthorsOpenReview ↗

General response

Dear reviewers, we would like to express our appreciation for the constructive reviews and for the several positive comments on our paper, particularly regarding the alignment between the architecture and the task (YG5p, aKcH, iJhw), the valid theoretical motivation (aKcH, iJhw) and the strong empirical results (YG5p, aKcH, iJhw).

We have carefully considered all of your feedback and we have made revisions to the paper accordingly (highlighted in blue), which we believe have considerably strengthened our contribution. In particular, based on your feedback, we have added

  • A new ablation study that clearly shows that learned color selection is central to the solution quality of Scone;
  • Comparisons with 5 new competitive baselines, spanning classical heuristics, recent swarm-based metaheuristics, and neural methods;
  • Experimental results on additional datasets, confirming the strong performance observed in our original evaluation.

Please find detailed answers to all comments in the individual replies below.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.