- 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
- 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.
- 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.
- 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
- The main novelty lies in the Snakepit search space, while the other components are largely based on existing optimization and search-based learning methods.
- Beam Anchor is presented as a major contribution, but the best results are achieved without learning, making its practical benefit less convincing.
- 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
- What are the main differences between Snakepit Surgery and existing local search or reconstruction methods? Could the authors further clarify the key methodological novelty?
- 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?
- 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
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).
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 β 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:
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 Q9.
Q2. What are the practical advantages of introducing learning?
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.