acceptodds
Under review as a conference paper at ICLR 2027

New Snake-in-the-Box Records via Snakepit Surgery and Learned Construction

Abstract

The snake-in-the-box problem asks for a longest induced path in the hypercube graph Q_n. We find a length-191 snake in dimension n=9—the lowest dimension where the maximum is unknown—improving the previous record of 190 that had stood for 14 years. We also establish new lower bounds in dimensions 10–13. To find these records, we introduce snakepits, collections of disjoint snakes, to expand the search space and open new routes between snakes. This motivates our new Snakepit-in-the-Box benchmark, which seeks maximal edge counts when allowing multiple components. Finally, we introduce Beam Anchor, a search-supervised learned constructor algorithm that finds 100 inequivalent length-190 snakes in dimension 9.

Primary area:
optimization
Keywords:
Combinatorial optimization, heuristic search, learning-guided search, simulated annealing, beam search, snake-in-the-box, hypercube graphs

Reviews

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

This paper studies the Snake-in-the-Box problem, which aims to find the longest induced path in a hypercube graph. The authors introduce Snakepit Surgery, which allows multiple disconnected paths during search and uses local reconstruction with simulated annealing to find longer snakes. They also propose Beam Anchor, a learning-based construction method that combines beam search with a learned policy. The proposed methods break the 14-year record in dimension 9, improving the known longest path from 190 to 191, and establish new lower bounds in higher dimensions. The paper also introduces the Snakepit-in-the-Box benchmark and provides additional theoretical results.

Critical strengths
  1. The paper breaks the 14-year record for the Snake-in-the-Box problem in dimension 9 and improves several higher-dimensional bounds, representing a meaningful achievement.
  2. The Snakepit search space is a well-motivated design that allows more flexible modifications of long paths. The idea is intuitive and shows clear benefits in practice.
  3. The paper is well organized, with clear method descriptions and figures. The experimental results and theoretical analysis also provide good support for the main findings.
Critical weaknesses
  1. The main novelty lies in the Snakepit search space, while the other components are largely based on existing optimization and search-based learning methods.
  2. Beam Anchor is presented as a major contribution, but the best results are achieved without learning, making its practical benefit less convincing.
  3. More targeted ablation studies are needed to better understand the key innovations, especially the individual contributions of the Snakepit representation and Cube Surgery.
Questions for authors
  1. What are the main differences between Snakepit Surgery and existing local search or reconstruction methods? Could the authors further clarify the key methodological novelty?
  2. Beam Anchor does not achieve the best results and requires substantial computational resources. What are the main practical advantages of introducing learning into this task?
  3. Could the authors further clarify the individual contributions of the Snakepit representation and Cube Surgery? The current ablation mainly demonstrates the effectiveness of Cube Surgery, while the benefit of the Snakepit representation itself remains less clear.
3 comments

Thank you for a careful and constructive review. We appreciate the value of the ablation request you asked for. We ran it; results are described below and it will become the main experiment of §4 and Appendix B in the revised paper.

W1. "The main novelty lies in the Snakepit search space." We agree that the snakepit relaxation is one of the central ideas. We don't believe it is a weakness. The general lesson that relaxing a constraint in the search space, and penalizing rather than forbidding its violation can be decisive to make progress on a hard search problem, is highly generalizable and is interesting for the AI community. The other novelty is Beam Anchor, the algorithm that we devised to address the issue of credit assignment in problems where the consequences of a move become apparent only much later in the episode.

W2. "Beam Anchor is less convincing." We'd like to stress that Beam Anchor is the best performing snake construction based algorithm at present. It outperforms all previous literature by finding 100 distinct snakes of length 190, whereas previous to our work only a single such snake was known to exist. In this sense, the Beam Anchor method is a record-breaking method as well. We did learn that changing the search space in the environment simplifies the problem, but as far as learning to plan paths to construct long snakes, Beam Anchor is the state of the art.

W3. Targeted ablations of the snakepit representation and cube surgery. We agree that our ablation study did not include changing the snakepit representation. We ran a new ablation study, changing the move set as well as introducing a hard enforcement of connectivity. The move sets we tried are to add and remove a vertex alone, or add and remove plus surgery. The strict enforcement of connectivity was achieved by increasing β\beta to 10^6, so that any proposal leaving more than one component would be rejected.

Each combination of move set with hard enforcement connectivity for one hour on one CPU core with ten different seeds. This is the same budget as the ablation in the paper.

In both cases, we found that enforcing connectivity would cause the search to severely underperform. Specifically, add/remove only with connectivity enforced reached an average of 128.5 (vs 149), spanning 126 and 132 (vs 147 and 155) maximum length reached. When surgery was allowed, the connectivity-enforced average rose to 180 (vs 188), spanning 179 and 182 (vs 186 and 191) maximum length reached. We will add this to the revised paper.

Q1. What is new relative to existing local search and reconstruction methods? Cube surgery is a ruin-and-recreate move, as mentioned in the Related Work. It departs from the usual pattern, which destroys part of a feasible solution and repairs it to another feasible one, in two ways:

  • The repair need not restore feasibility. We search through infeasible states. A refill may leave several components, which the energy penalises rather than forbid explicitly.
  • The ruined region is a small subcube, and a local subcube may include vertices from different parts on the snake.

Earlier record searches for this problem kept a single path at all times. They either extended a primer from the dimension below or re-solved a window of the path exactly, and both had stopped at 190 in Q9Q_9.

Q2. What are the practical advantages of introducing learning?

  • Learning is what makes the search work. As mentioned above, Beam Anchor is the state of the art constructor method for this problem. It beats all the previous baselines as well as off-the-shelf RL algorithms.

Q3. Individual contributions of the Snakepit representation and Cube Surgery. See W3.

Thank you again; the ablation has made the paper's central claim more precise.

Dear Reviewer i2uF18,

Thank you again for your valuable and constructive feedback. Following your suggestion, our response reports a 2×2 ablation that separates the snakepit relaxation from cube surgery, with ten independent seeds per arm. With identical moves, allowing the snake to fragment raises the median best length from 180 to 189.5, and every run with the relaxation beat every run without it. We would like to follow up on our rebuttal and check whether our responses have addressed your concerns, or if there are any additional questions that would need further clarification.

Thank you for the additional ablation, which shows that relaxing connectivity yields longer paths both with and without Cube Surgery. I still find it unclear when Beam Anchor’s benefits justify its computational cost, so I am keeping my original rating of 3 (weak acceptance).

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

The paper presents a novel approach in finding the longest induced path in the hypercube graph (the snake-in-the-box problem). The main contribution is finding of the previously unknown maximum length for dimension n=9 -- according to the paper it is 191; additional contributions mention finding lower bounds for dimensions 10-13. To this end, the method of finding based on simulated annealing is introduced.

Critical strengths
  • Authors push the frontier in one of the niche/highly specialized problems from combinatorics
Critical weaknesses
  • Low fit for the conference -- I do not understand why this paper was submitted to ICLR instead of a community of algorithmics, e.g., Alenex. While we definitely have "something from machine learning" here, the main contribution is about solving the highly specialized combinatorial problem.

  • It is unclear, why this paper should be of interest of ICLR community. Most of the paper is about the algorithm to solve a problem that by itself has little to do with the machine learning theory. The main contributions are about finding the lengths of the snakes. In what way that is useful to researchers working in general machine learning?

  • Even if we treat the paper as an "application" of ML methods, I doubt if this is the contribution that is sufficient for ICLR. The result is incremental and seems a better fit for a mathematical journal specialized in combinatorics.

Questions for authors

No questions, I believe this paper should be submitted to a venue specialized in algorithms or experimental algorithmics (SEA, Alenex, maybe ICALP?) or a mathematics journal.

2 comments

Thank you for the review and for recognizing that the paper pushes a long-standing frontier. We are glad to address the weaknesses that you have pointed out.

W1. Fit with ICLR The official ICLR 2027 Call for Papers, under Subject Areas, explicitly lists four topics to which this submission contributes:

  • “reinforcement learning.” The snake-in-the-box problem presents a common credit-assignment challenge: the consequences of a move may become apparent only much later in the episode. This feature is extremely common to many other RL problems. We develop a novel RL model, Beam Anchor, targeting this challenge which could be successfully applicable to other problems as well.
  • “optimization.” The snakepit formulation tests how the choice of search space affects constrained optimization: relaxing a constraint in the search space, and penalizing rather than forbidding its violation, can be decisive to make progress on a hard search problem.
  • “learning on graphs and other geometries & topologies.” The RL agents we train and develop learn a policy for constructing induced paths in the hypercube graph.
  • “datasets and benchmarks.” We established snake-in-the-box as a concrete benchmark for the deep RL comunity. Similarly, we defined the new problem snakepit-in-the-box that can be equally used as a new benchmark. ML venues have repeatedly published papers that introduce such problems and use them to show what learned search can and cannot do:
    • routing (Kool et al., ICLR 2019);
    • graph optimisation (Dai et al., NeurIPS 2017);
    • the Rubik's cube (DeepCubeA, Nature);
    • matrix multiplication (AlphaTensor, Nature);
    • cap sets and kissing numbers (FunSearch, AlphaEvolve).
  • “Application of Machine Learning to Math.” Furthermore, as explicitly mentioned in the official about page applications to any fields are accepted. Our application is to mathematics, which follows a well established practice and has become extremely popular. Far from being niche, this problem has a long history rooted in classical error correcting codes and coding theory, in addition to appearing at several AI venues: Monte-Carlo search (ECAI 2012) and nested rollout policy adaptation (AAAI 2023), which set records in Q10Q_{10}–Q13Q_{13} but reached only 188 in Q9Q_9.

W2. Interest to general machine learning Our two methods carry two lessons that apply well beyond snakes.

  • Relaxing the state space. In many constrained problems the natural search space is the feasible set: valid schedules, legal molecules, connected paths. Our results show that searching a larger space that violates one constraint can be decisive, provided the violation is penalised rather than forbidden.

  • Reward only at the end. Beam Anchor targets long episodes in which intermediate reward says nothing about the final outcome, a common situation in RL. Examples include program synthesis, molecule and circuit design, theorem proving and planning.

W3. "The result is incremental." We respectfully disagree, for three reasons.

  1. Each extra edge is far rarer than the last. Near the optimum, the number of distinct snakes drops roughly by an order of magnitude.
    • in Q8Q_8, where 98 is proven optimal, there are 26 known classes at length 97 and one at 98;
    • in Q9Q_9, our searches found 1,042 classes at 190 and only 131 at 191.

Each step up is a step into a set about an order of magnitude smaller. That is why the 190 record resisted improvement for 14 years and a testament to the strength of our search.

  1. Gains propagate upward. Long snakes in one dimension can be used as starting points for the next. Lifting our 191s gave length-379 snakes in Q10Q_{10} (still the best known), and the same cascade carried improvements to Q11Q_{11}–Q13Q_{13} (+9+9, +11+11, +24+24).

  2. It is the normal measure of progress. Unit improvements in extremal problems in long-standing cases demonstrate significant advances (e.g. AlphaEvolve's headline geometric result raised the 11-dimensional kissing number from 592 to 593).

We believe we have addressed each of the weaknesses that you have identified, and we would be glad to clarify anything else you might bring up.

Reviewer_AG7wOpenReview ↗

Response

Thank you for the detailed response, but I keep my score.

  1. The presence of the suitable keywords in the Aims and scope does not equal that a paper is of a good fit there. Moreover, we should care that the paper gets published in a venue where it gets the usual attention. Given the way your paper is written and the scope of your contributions, the right place seems to be the algorithmic community. In any conference you will find papers that "went in" but were of little interest. Later those Authors stand by their posters alone, because they entered and nearly nobody cares. It is a very sad sight. If your contribution is as significant as you claim, you should definitely go to a venue that would be carried away with that.

  2. The lessons you provided could be provided by nearly any optimization problem (and are rather well-known).

  3. I understand that the assessment of "being incremental or not" is subjective (even if I asked a few of my colleagues in algorithmic community in general what would qualify to them as non-incremental in their community/research to somehow judge and weight my feeling about this paper). However, more reviewers were also unsure about it, what might suggest that indeed this is not the right venue (the reviewers are unable to recognize an important result).

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

This paper introduces snakepits, which are collections of disjoint snakes, to the snake-in-the-box problem. With these additions, the authors improved the previous record from 190 to 191 in dimension n=9 and established new lower bounds for dimensions 10–13. They also introduced a new approach called Beam Anchor, which utilizes a learned policy to find 100 inequivalent snakes of length 190.

Critical strengths

Please refer to the weaknesses section.

Critical weaknesses
  1. The paper mentions a record that had stood for 14 years, but there is no citation for the previous work. Also, there is no explanation of how the previous result was achieved.

  2. The paper states that a learned policy was used for the construction phase, but there is no explanation of how this policy was learned. Which algorithm was used to train the policy? How did the training progress? Can we see how the policy's performance changed during training?

  3. The paper claims to have achieved a new record, but this record was achieved by introducing snakepits into the environment. Therefore, this appears to be a modification of the environment rather than a new approach.

  4. The references for previous works in Table 1 are not even research papers but blog posts that do not appear to be cited in other papers. Furthermore, these blog posts do not explain how their reported results were achieved.

  5. The proposed method focuses only on achieving a new record for the snake-in-the-box problem, and no other applications of the method are discussed. This raises concerns about the generalizability of the proposed approach.

  6. There is no figure showing the training progress of the PPO algorithm used as a baseline. The paper only reports the best snake found by this algorithm.

  7. The paper discusses continents and islands, but these terms are not clearly defined.

  8. The lessons learned from this work, as mentioned in the conclusion, seem rather obvious. For example, it is expected that a learned policy could help guide the search. Also, I still do not understand the first lesson.

  9. The literature review is also very limited, and I cannot find a clear connection between this work and previous research on the same problem. It is difficult to understand what the proposed method improves upon compared to previous approaches and what limitations of those approaches it aims to address.

  10. I am not sure how significant it is to improve the previous record by just one, which the paper presents as its main contribution. This does not seem to be a substantial improvement over the previous record.

  11. The authors claim that Beam Anchor found 100 inequivalent snakes of length 190 in dimension 9. However, they also state that the new record is 191. Why, then, was Beam Anchor unable to find any snakes of length 191?

Questions for authors

Please refer to the weaknesses section.

4 comments

Thank you for the detailed list. Several points in your list seem to come from places where the paper was too terse. We will revise them accordingly. From your reply we could identify three most critical points which we will address immediately, before answering each weakness in order.

The record is an ordinary snake. The length-191 snakes are connected, induced paths in Q9Q_9. They are the same objects as every other previous record. One such snake is printed in Appendix E and is now listed as the n=9n=9 record on the community record list (T. Ace, minortriad.com/snake).

The +1 is a large step. Near the optimum, each extra edge is roughly an order of magnitude rarer than the last. In 8 dimensions, where the complete spectrum of snakes has been enumerated, there is a single snake of maximum length, 98, and 27 snakes of length 97. Consequently, under comparable computational budgets, even a single-edge improvement represents a meaningful indicator of algorithmic progress, demonstrating the ability to discover solutions that are approximately an order of magnitude rarer. In addition, a +1 improvement in 9 dimensions is meaningful because this gain propagates to higher dimensions (W10).

Our methods are generalizable. There are two lessons from our work which we believe are generalizable and are of interest to the AI community: (i) Relaxing a constraint in the search space, and penalizing rather than forbidding its violation, can be decisive in making progress on a hard search problem. (ii) Snake construction presents a common credit-assignment challenge: the consequences of a move may become apparent only much later in the episode. Beam Anchor addresses this by using search rollouts to compare possible moves and train a policy for long-horizon construction (W5, W8). We believe this algorithm could be fruitful in many other similar problems.

W1. Citation and method for the previous record. The length-190 snake is due to Wynn (2012, arXiv:1201.1647). It was cited in the original submission in Table 1, in Related Work and in §5.2. The revised Related Work will mention how each line of earlier records was obtained.

W2. How the policy is learned, and how training progressed. This is the subject of the Beam Anchor section (§5.2). Beam Anchor follows the expert-iteration paradigm (Anthony et al., 2017):

  • At each step of a construction, a beam search is run, guided by the policy in training, from each possible child of the current prefix, with an equal share of beams. For each child, the length of the longest snake reached is recorded.
  • These lengths are used both to choose the next move and to train the policy.
  • Training is supervised cross-entropy toward a softmax of those lengths (Eq. 3). Algorithm 1 and Table 5 (Appendix A) give the loop and settings, and there is no reward-based policy gradient.

We will add a figure with training curves.

W3. "The record was achieved by introducing snakepits into the environment." Snakepits change the intermediate search states, while the objective and validity requirements remain unchanged: every reported record is a single induced path. As mentioned above, this is an application of the generalizable lesson that relaxing a constraint in the search space can be decisive in making progress on a problem.

W4. Blog posts in Table 1. Only the Q10Q_{10}–Q13Q_{13} baselines come from non-archival sources. That is where those records were originally published.

Since 2025 the records have moved quickly through results posted on the community record list, on Zenodo and in technical notes. We note there is no correctness concern: snakes contributed to the record list are easy to verify as correct with a few lines of code. The Q9Q_9 baseline is Wynn's paper, and other records have appeared at ECAI, IEA/AIE and AAAI venues.

W5. Generality. Our two methods carry two lessons that apply well beyond snakes.

  • Relaxing the state space. In many constrained problems the natural search space is the feasible set: valid schedules, legal molecules, connected paths. Our results show that searching a larger space that violates one constraint can be decisive, provided the violation is penalised rather than forbidden.

  • Reward only at the end. Beam Anchor targets long episodes in which intermediate reward says nothing about the final outcome, a common situation in RL. Examples include program synthesis, molecule and circuit design, theorem proving and planning.

W6. PPO training progress. We had reported the training budget and the best snake PPO found. The main outcome is that PPO, with the same network, came nowhere near Beam Anchor (184 vs. 190). The revision will add its training curves.

W7. Continents and islands. The continent and the island are the sets of known length-191 classes with dmax⁡≤44d_{\max}\le 44 and dmax⁡=52d_{\max}=52, where dmax⁡d_{\max} is the number of times the most-used coordinate is flipped. Their relevance is that searches that start from a snake in the island are not able to find snakes in the continent and vice versa. We will add formal definitions of continent and island in the revised draft.

W8. The lessons in the conclusion. We will revise the language for the lessons in the conclusion.

  • The first lesson is that reformulating the search environment can make a problem tractable where better learners do not. A search in our relaxed environment was able to find 191-snakes, whereas no method before has been able to go past 190 in an environment enforcing strict adherence to valid snakes.
  • Regarding the second lesson, we will expand on this point in the revised paper: even though it seems trivial that learning can help, our point is that this is a very challenging environment for RL. PPO with a GNN is not able to outperform classical methods like beam search with handcrafted heuristics, which were able to find 190 in previous literature. Our new algorithm, Beam Search, is able to outperform all previous baselines, both learned and classical.

W9. Literature review. We will expand on the literature review in the revised paper.

W10. Is +1 significant? Yes, for three reasons, as already mentioned.

  1. Each extra edge is far rarer than the last. Near the optimum, the number of distinct snakes drops roughly by one order of magnitude.

    • in Q8Q_8, where 98 is proven optimal, there are 26 known classes at length 97 and one at 98;
    • in Q9Q_9, our searches found 1,042 classes at 190 and only 131 at 191.
  2. Gains propagate upward. Long snakes in one dimension can be used as starting points for the next. Lifting our 191s gave length-379 snakes in Q10Q_{10} (still the best known), and the same cascade carried improvements to Q11Q_{11}–Q13Q_{13} (+9+9, +11+11, +24+24).

  3. It is the normal measure of progress. Unit improvements in extremal problems in long-standing cases demonstrate significant advances (e.g. AlphaEvolve's headline geometric result raised the 11-dimensional kissing number from 592 to 593).

W11. Why didn't Beam Anchor find 191? Beam Anchor is, to our knowledge, the strongest method for snake construction. However, there is no guarantee that Beam Anchor will converge to the optimal solution, and the reason why it did not reach any length-191 snake is an open question which may be attributable to Lesson #1.

We believe we have addressed each of the weaknesses that you have identified, and we would be glad to clarify anything else you might bring up.

Dear Reviewer rcJc23,

Thank you again for your detailed feedback. In our response, we clarified that snakepits change only the search space: the length-191 record is an ordinary induced path in Q9Q_9, verifiable in a few lines of code and now listed as the n=9n=9 record on the community record list. We also gave formal definitions of continents, islands and basins, explained how earlier records were obtained, and showed why each extra edge is significant. We would like to follow up on our rebuttal and check whether our responses have addressed your concerns, or if there are any additional questions that would need further clarification.

Reviewer_rcJcOpenReview ↗

Response to Authors Comments

Dear Authors,

Thank you for providing the explanation, as I do not have extensive experience in this topic. My main concern is that you claim your method can generalize, but there are no experiments demonstrating how well it generalizes or how it performs across other domains to support this claim. Therefore, I respectfully maintain my score.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.