PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Paul Orland, Lucas Fagan, Michele Tarquini, Davide Passaro, Maksymilian Manko, Elli Heyes, Angus Gruen, Giorgi Butbaia, Justin Tan, Sergei Gukov

arXiv:2607.15270v3cs.DMcs.AIcs.LGmath.CO

TL;DR

Constructing long snakes is a long-horizon decision problem, with poor choices sometimes costly only hundreds of moves later. The paper searches over snakepits with cube surgery and introduces Beam Anchor, a learned constructor. It reports a length-191 snake in Q9 and 100 inequivalent length-190 snakes in Q9 from Beam Anchor.

  • Problem

    Long-snake construction is a long-horizon decision problem in which poor choices may not become costly until hundreds of moves later, making immediate reward uninformative and credit assignment difficult.

    Source: §1 · p. 1

  • Method

    The paper searches over multi-component snakepits using cube surgery and introduces Beam Anchor, which uses policy-guided beam searches to train a constructor from its own comparisons.

    Source: §3 · p. 3, §5.2 · p. 5

  • Results

    The work reports a length-191 snake in Q9, and Beam Anchor finds 100 inequivalent length-190 snakes in Q9.

    Source: §1 · p. 2, §5.2 · p. 5

  • Takeaways & Limitations

    The authors report that cube surgery on snakepits reached 191 from an empty cube in minutes on one CPU core, while anchored-comparison supervision reached 190 from the origin.

    Source: §8 · p. 9

    Whether a length-192 snake exists in Q9 and whether the product snakepits are optimal remain open questions.

    Source: §8 · p. 9

Abstract

from arXiv · show

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.

1 INTRODUCTION

The snake-in-the-box problem seeks a longest induced path in a hypercube, but optimal lengths are known only through dimension 8. This work expands both modification and construction searches and reports new snake records and related contributions.

1 INTRODUCTION

  • Long-horizon construction makes poor choices costly only hundreds of moves later, leaving immediate reward uninformative and credit assignment difficult.Modification is also constrained because vertices in a long snake are often adjacent to other parts of the path.Source: §1 · pp. 1–2
  • Table 1 compares this work’s lower bounds with records preceding its announcement and counts inequivalent snakes found at record length in its final column.The introduction notes that the displayed bank is a discovered bank, not a census.Source: Table 1 · p. 2, §1 · p. 2
  • Snakepit search with cube surgery expands the state from one snake to disjoint snakes, enabling easier routes between components and flexible connectivity changes during subcube refills.The Q9 record search uses simulated annealing with a penalty for larger component counts.Source: §1 · p. 2
  • Beam Anchor combines beam search with a learned policy, comparing continuations from a common prefix and training the policy to favor moves whose continuations reach longer snakes.Each possible next move from a partial snake receives its own share of search.Source: §1 · p. 2
  • A length-191 snake in Q9 breaks the 190 record that had stood for 14 years, alongside new lower bounds in dimensions 10–13 and a bank of 131 inequivalent length-191 snakes.The bank supports an empirical study of family structure and search coverage.Source: §1 · p. 2
  • The paper introduces Snakepit-in-the-Box, a benchmark that maximizes edge counts while allowing multiple components.It also provides lower bounds, exact values through Q7, and a density limit.Source: §1 · p. 2

2 RELATED WORK

Earlier work on long snakes spans exhaustive search, population-based and permutation-based construction, Monte Carlo methods, and newer search strategies. This paper relates cube surgery and Beam Anchor to established optimization and learning approaches.

2 RELATED WORK

  • Exhaustive search established snake optima through Q8, while higher-dimensional records have used population-based search and permutation-based constructions [Wynn, 2012].Monte Carlo search, nested rollout policy adaptation, and beam search with local rerouting [Ace, 2025; 2026a; Echols, 2026d;b] are also reported.Source: §2 · pp. 2–3
  • Cube surgery connects penalty-based annealing with ruin-and-recreate and large-neighborhood search.Collections of separated snakes also occur in coil enumeration, while this work uses them as intermediate states for repeated interior rearrangement.Source: §2 · p. 3
  • Beam Anchor uses policy-only expert iteration, with beam search as teacher and policy distillation guiding later search [Anthony et al., 2017].It shares a search–learning loop with AlphaZero but has no learned value head and supervises only the anchor where alternatives were compared.Source: §2 · p. 3

3 SNAKES AND SNAKEPITS

The section defines snakes and snakepits as induced paths and induced linear forests in hypercubes, then introduces a benchmark for maximizing snakepit edges. Product constructions illustrate how disjoint snakes can yield high-edge, multi-component snakepits.

3 SNAKES AND SNAKEPITS

  • A snakepit is an induced linear forest: a collection of snakes with no cube edge between distinct components, with e(F) = v(F) − c(F).A snake is the one-component case, and intersecting a snake or snakepit with a subcube preserves the snakepit property.Source: §3 · p. 3
  • Snakepit-in-the-Box asks for the maximum edge count of a snakepit in Qn, with L(n, 1) equal to the maximum snake length a(n).L(n, k) gives the maximum edge count when the snakepit has k components.Source: §3 · p. 3
  • A product snakepit places copies of two disjoint snakepits over even- and odd-parity vertices of the higher-dimensional cube’s other factor.The section gives a Q4 illustration of a 7-edge snake and a 6-edge snakepit with two components.Source: §3 · p. 3, Figure 2 · p. 3
  • In Q9, two disjoint length-13 snakes in Q5 yield a product snakepit with 16 components, 208 edges, and 224 vertices; a length-26 and length-24 pair in Q6 yields 8 components and 200 edges.Both pits contain more edges than a length-191 snake, but distribute them across multiple components.Source: §3 · p. 3

4 FINDING RECORD SNAKES: MODIFICATION

Cube-surgery annealing modifies snakepits by rebuilding small subcubes while allowing temporary fragmentation. In Q9, surgery substantially outperformed single-vertex addition and removal, and the annealer reached a validated length-191 snake.

4 FINDING RECORD SNAKES: MODIFICATION

  • Cube surgery clears a 2–4-dimensional subcube and refills it in passes that first prefer connections, then allow new fragments, before accepting or restoring the whole edit.Each selected region contains 4–16 vertices, and the complete edit receives one annealing decision.Source: §4 · p. 4
  • Every legal refill addition starts a component, extends a path at an endpoint, or joins two paths at their endpoints, keeping the result a snakepit.The annealer also proposes single-vertex additions and removals, endpoint wiggles, and deep regrowth.Source: §4 · p. 4
  • The annealer penalizes fragmentation while rewarding occupied vertices, and its cooling and reheating schedule permits temporary fragmentation before favoring consolidation.Because proposals are asymmetric, the method is an optimization heuristic rather than a claim of Boltzmann sampling.Source: §4 · p. 4
  • Product snakepits provide convenient starting states, but they are not required: chains starting from the empty snakepit also reach length 191.The component penalty encourages consolidation of the fragmented starting state.Source: §4 · p. 4
  • 188 median best length (range 186–191) with surgery versus 149 (147–155) with add/remove alone; paired differences favored surgery by 35–41 edges, and one run reached 191 after 158 seconds.The recipes ran for one hour from the empty snakepit over ten paired seeds; the cheaper recipe made about 2.4× more proposals in the same time.Source: §4 · pp. 4–5

5 FINDING RECORD SNAKES: CONSTRUCTION

The paper uses primer-based beam search to extend snakes into larger hypercubes and introduces Beam Anchor, which constructs from the origin without a primer. Beam Anchor searches continuations from each legal move and trains a policy to guide later searches.

5.1 BEAM SEARCH WITH A PRIMER

  • Ordinary beam search ranks extensions by length, reachable available vertices, and Gumbel noise; its faster lifts seed cube-surgery annealing, alternating construction and modification.Observed raw lifts were 379 → 743, 746 → 1470, and 1476 → 2916.Source: §5.1 · p. 5
  • Primer lifting embeds a long Qn−1 snake as a fixed prefix in one half of Qn, then grows a continuation in the other half.This can miss optima: the known length-98 snake in Q8 uses no coordinate exactly once, so extending an optimal length-50 Q7 primer cannot reach it.Source: §5.1 · p. 5

5.2 BEAM ANCHOR

  • Beam Anchor distills search outcomes into a policy over legal moves; it balances training across prefix depths and uses higher target temperature at shallow depths.The policy is the only learned component; the authors argue that ranking moves at one prefix is easier than predicting the best completion length far ahead.Source: §5.2 · pp. 5–6
  • 100 inequivalent length-190 snakes in Q9 were found by Beam Anchor, while the best snake across PPO experiments had length 184.Beam Anchor’s snakes came from training and frozen-policy runs; it was the first learned constructor, to the authors’ knowledge, to reach length 190 in Q9.Source: §5.2 · pp. 5, 7
  • Beam Anchor searches each legal move from a partial snake with its own beam budget, then uses the longest completed snake found as a lower bound on that move’s best completion.The searches do not compete for beams, so each move receives equal effort regardless of the current policy ranking.Source: §5.2 · p. 6

6 RECORDS AND SEARCH LANDSCAPE

The records combine cube-surgery annealing, beam-search lifts, and a Q13 MILP refill. The Q9 class bank reveals separated families of 191-snakes, while adapted searches also establish coil and symmetric-coil records.

6 RECORDS AND SEARCH LANDSCAPE

  • A length-191 snake in Q9 came from cube-surgery annealing alone; lifts and annealing reached 746 in Q11 and 1476 in Q12, while a genetic/MILP-seeded anneal reached 2924 in Q13.Lifting and annealing independently reached 379 in Q10; lifts reached 743, 1470, and 2916 in Q11–Q13, respectively.Source: §6 · p. 7

6.1 WHAT THE Q9 BANK REVEALS ABOUT SEARCH

  • The Q9 bank has 127 length-191 classes with dmax 39–44 and four with dmax 52, with no classes from 45 to 51.These families are separate annealing basins; all 100 Beam Anchor length-190 classes have dmax ≤46, and none of the 131 known 191-snakes admits a one-edge extension, so a 192-snake must lie outside this bank.Source: §6.1 · p. 7, Figure 3 · p. 7

6.2 COILS

  • In Q9, 96 of 1,042 length-190 classes closed into the same 192-coil; no record-length snake closed in Q10–Q12, where shorter harvested snakes yielded coils of 374, 734, and 1466.The search tested 14–24 million shorter snakes per dimension in Q10–Q12.Source: §6.2 · p. 8
  • In Q13, a mixed-integer program refilled a window of a length-2932 snake under a cycle-closing constraint, producing a 2916-coil.Source: §6.2 · p. 8
  • Symmetry-restricted searches adapted surgery to act on vertex pairs and Beam Anchor to build one half-path, setting symmetric-coil records of 370 in Q10 and 734 in Q11.The restriction fixes an involutive cube automorphism; every proven coil optimum in dimensions 2–8 has a representative with this symmetry.Source: §6.2 · p. 8

7 SNAKEPIT-IN-THE-BOX

The Snakepit-in-the-Box benchmark measures the maximum edge count when multiple disjoint snakes are allowed. Snakepits first exceed optimal snakes in dimension 7, while the asymptotic question is how close their edge density can approach one half.

7 SNAKEPIT-IN-THE-BOX

  • 52 edges in Q7 exceed the 50-edge maximum for snakes, and four length-13 paths attain the snakepit maximum.In dimensions 1–6, snakepits cannot exceed an optimal snake; the Q7 maximum is computer-assisted proved.Source: §7 · p. 8
  • Λ(n) ≥ 13 · 2^(n−5) for n ≥ 5, giving 104 edges in Q8 and 208 in Q9; optimality remains open.Across 24 two-hour Q9 runs, a pit-mode annealer never exceeded the construction.Source: §7 · p. 8
  • The ratio Λ(n)/2^n is squeezed by the maximum edge count D(n) of two disjoint snakepits in Q_n and D(n−1), up to a factor 1 − 3/(2n).The proof sketch bounds the ratio above by 1/2 and gives 13/32 from two disjoint length-13 snakes in Q5.Source: §7 · p. 9
  • The benchmark’s central asymptotic question is whether any pair of disjoint snakepits can improve on the Q5 pair’s density.The deficit from density 1/2 equals unused vertices plus components, divided by 2^(n+1).Source: §7 · p. 9

8 CONCLUSION

The conclusion emphasizes the search state and move as key to finding the Q9 record, and reports a benefit from learning with anchored-comparison supervision. Whether longer or structurally different Q9 snakes exist, and whether product snakepits are optimal, remains open.

8 CONCLUSION

  • Cube surgery on snakepits reached 191 from an empty cube in minutes on one CPU core, outperforming single-vertex annealing on the same states and the learned constructor with more compute.The conclusion identifies state-space and move choice as critical.Source: §8 · p. 9
  • Anchored-comparison training reached 190 from the origin, versus 184 for PPO and 178 for the same search with a uniform policy.The conclusion identifies the form of supervision as consequential within construction.Source: §8 · p. 9
  • Open questions include whether Q9 has a length-192 snake or a length-191 snake outside the known bank, and whether Λ(8)=104 and Λ(9)=208 are optimal.Source: §8 · p. 9

ETHICS STATEMENT

The paper reports no living subjects or personal data and anticipates no specific societal harms directly arising from its methods or results.

ETHICS STATEMENT

THE USE OF LARGE LANGUAGE MODELS

The appendices document Beam Anchor’s training and inference procedures, reported-run settings, and the production annealer. They also report baseline outcomes, learned-policy behavior across length-190 classes, and implementation details for cube surgery.

THE USE OF LARGE LANGUAGE MODELS

  • LLMs assisted manuscript drafting, literature discussion, methodological interpretation, and search-code optimization; the authors say they checked outputs and take responsibility for the final artifacts.Source: THE USE OF LARGE LANGUAGE MODELS · p. 10

A BEAM ANCHOR: ALGORITHM DETAILS

A.1 ANCHOR SEARCH

  • Canonical prefixes exclude moves that only relabel coordinates; each anchor’s beam pool is divided across legal moves, and stored outcomes are optimistic attained lengths.Move quotas differ by at most one, and duplicate states retain the higher score.Source: §A.1 · p. 13

A.2 WALKS AND TEMPERATURES

  • Training starts walks from canonical length-10 prefixes, uses hotter exploration at shallow anchors, and decreases exploration as training progresses.Teacher temperature is independent of walk temperature and remains constant over training.Source: §A.2 · p. 13

A.3 DISTILLATION

  • Distillation trains only on prefixes with recorded outcomes for at least two moves, restricting both targets and policy updates to those measured moves.The outcome table is bounded and uses least-recently-used eviction.Source: §A.3 · p. 13

A.4 NETWORK DETAILS

  • Shrinking-ball inference produces identical Q9 logits with 1,792 message-passing rows per state instead of 3,584; the PPO critic requires a full forward pass.The six-layer policy’s computation is restricted to shrinking Hamming balls around the head.Source: §A.4 · p. 14

A.5 SETTINGS OF THE REPORTED RUNS

  • Uniform-policy runs plateaued at 178 and same-network PPO at 184; Beam Anchor’s 100 length-190 classes all lie in the continent mode, not the island modes.Table 4 settings interpolate temperatures by anchor depth, and the walk temperature also declines over training.Source: §A.5 · pp. 14–15, Figure 4 · p. 15, Table 4 · p. 15

B.1 PRODUCTION ALGORITHMS AND SETTINGS

  • Cube surgery clears a random 2-, 3-, or 4-subcube, rebuilds legal occupancy, and restores the prior state if the annealing proposal is rejected.Production chains use compound proposals, save qualifying single snakes with deduplication, and the first successful Q9 chains started from a Q6 product.Source: §B.1 · pp. 15–17

B.2 SURGERY COMPARISON AND ANNEALING TRACE

The section compares cube-surgery annealing with add/remove search, then reports how lifting, window refill, and related searches extend snake and coil records. It also examines snake families and establishes exact small-dimension bounds.

B.2 SURGERY COMPARISON AND ANNEALING TRACE

  • 149 versus 188 edges: after 3,600 seconds, recipe B's median best snake length was 188 (range 186–191), versus 149 (147–155) for A.Every paired difference favored B, with a median of 39 edges; the recipes completed different numbers of temperature cycles, so the comparison does not isolate surgery or establish its necessity. Traced chains recovered 86 known 190 classes and 27 known 191 classes in 120 CPU-hours.Source: §B.2 · pp. 17–18

B.3 BEAM LIFTING

  • Lifting all 131 known 191-snakes recovered the same 12 length-379 classes in Q10; tested Q8 primers did not yield 190 in Q9.Beam lifting scores one-edge extensions using edge length and the count of reachable unvisited vertices, with selection noise distinguishing siblings.Source: §B.3 · p. 18

C.1 SNAKE RECORDS

  • The Q12 route reached 1476, while the Q13 route reached 2924 after refining lifts and annealing; MILP window refill also produced the 2921 Q13 seed.The refill fixes the path outside a window and solves exactly for an induced path joining its endpoints; the reported class counts above Q9 are harvest counts, not completeness results.Source: §C.1 · pp. 18–19

C.2 COILS

  • 374, 734, and 1466 edges: harvested shorter snakes yielded coil records in Q10, Q11, and Q12, respectively; no record-length snake in those dimensions closed.In Q9, 96 of 229 length-190 classes with distance-two endpoints closed, all to the same 192-coil; MILP closure produced a 2916-coil in Q13.Source: §C.2 · p. 19

C.3 SYMMETRIC COILS

  • 96, 192, 372, and 734: symmetric surgery reached these coil lengths in Q8–Q11, matching the optimum or best known in every dimension except Q10.Half-path Beam Anchor reached 48, 92, 176, 370, and 730 in Q7–Q11; a symmetric coil's second half is the image of its first under an involutive cube automorphism.Source: §C.3 · p. 19

C.4 CONTINENT AND ISLAND

  • At length 190, 27% of continent-type snakes and 5% of island-type snakes extend to 191; no measured simple statistic separates extendable 190s from dead ends.Source: §C.4 · p. 20

D.1 BOUNDS AND SMALL VALUES

  • In Q7, every optimum has exactly four components; L(7,k) for k=1–8 is 50, 50, 50, 52, 51, 50, 49, and 48, with 48 persisting through k=16.For n≥5, every set of more than 2n−1 vertices induces a vertex of degree at least √n>2, implying a snakepit uses at most half the cube's vertices.Source: §D.1 · p. 21

D.2 EXACTNESS IN DIMENSION 7

  • The computer-assisted Q7 search excludes snakes of 53 edges, establishing 52 as the maximum; at 52, feasible completions occur only with four components.Those completions yield 63 classes, each comprising four length-13 paths with an edge-free coordinate; the exact values for n≤6 come from exhaustive enumeration.Source: §D.2 · p. 21

D.3 PROOF OF PROPOSITION 1

The proposition bounds normalized snake and snakepit edge counts using products and coordinate splitting. The section calibrates a pit-mode annealer and gives the Q9 record snake's transition-sequence description.

D.3 PROOF OF PROPOSITION 1

  • The bounds dn−1 ≤ un ≤ dn/(1−3/(2n)) imply shared limits ρ = sup da ≤ 1/2, with ρ ≥ 13/32.A disjoint pair in Q5 gives D(5)=26, and its products attain exact D(6)=52 and D(7)=104; the first open base that could improve 13/32 is Q8.Source: §D.3 · p. 21

D.4 BENCHMARK CALIBRATION

  • 98 edges in each of four 40-minute Q8 penalty-ramp runs, versus 95–96 with fixed β=3.2; neither the Q8 nor Q9 runs exceeded product values.The product values were 104 in Q8 and 208 in Q9.Source: §D.4 · p. 22

E RECORD SNAKES

  • 191 edges: the Q9 record snake is given by a transition sequence and has DCV (39, 38, 35, 29, 26, 9, 9, 4, 2).The transition sequence lists the coordinate flipped at each step, starting from the origin.Source: E RECORD SNAKES · p. 23
Loading 2607.15270v3…