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

cs.DMJul 16, 2026

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

Authors: Paul Orland, Lucas Fagan, Michele Tarquini, Davide Passaro, Maksymilian Manko, Elli Heyes, Angus Gruen, Giorgi Butbaia, +2 more

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.

Figures & tables

Figure 1: From a snakepit to a snake. Two vertex-disjoint length- $13$ snakes in $Q_{5}$ can be combined to form a $16$ -snake snakepit with $208$ edges in $Q_{9}$ . Cube-surgery annealing can rearrange such a starting state into a length- $191$ snake.

dimension $n$	our bound $a(n)\geq$	previous record	$\Delta$	# classes at record
$9$	$\mathbf{191}$	$190$ ( Wynn, 2012 )	$\mathbf{+1}$	$131^{*}$
$10$	$\mathbf{379}$	$376$ ( Ace, 2025 )	$\mathbf{+3}$	$\geq 12$
$11$	$\mathbf{746}$ †	$737$ ( Ace, 2026a )	$\mathbf{+9}$	$\geq 72$
$12$	$\mathbf{1476}$ †	$1465$ ( Ace, 2026a )	$\mathbf{+11}$	$\geq 34{,}688$
$13$	$\mathbf{2924}$ †	$2900$ ( Echols, 2026b )	$\mathbf{+24}$	$\geq 30$

Table 1: Lower bounds established by this work relative to the records preceding our announcement. The final column counts inequivalent snakes found at the record length, up to the symmetries of

Q_{n}

and reversal.

Panel of Figure 2 — Figure 2: A snake with $7$ edges (left) and a snakepit with $6$ edges in two components (right), both in $Q_{4}$ .

Panel of Figure 3 — Figure 3: Distribution of $d_{\max}$ over the known $Q_{9}$ classes at length $191$ (top) and $190$ (bottom). At length $191$ the continent ( $d_{\max}\leq 44$ ) and the island ( $d_{\max}=52$ ) are separated by an empty gap; the length- $190$ stratum shows the same two modes.

$n$	our bound	previous	$\Delta$	# classes at record
Coils
$9$	$\mathbf{192}$	$188$ ( Wynn, 2012 )	$+4$	$1$
$10$	$\mathbf{374}$	$370$ ( Echols, 2026d )	$+4$	$12$
$11$	$\mathbf{734}$ †	$728$ ( Ace, 2026a )	$+6$	$9$
$12$	$\mathbf{1466}$ †	$1442$ ( Ace, 2026a )	$+24$	$5$
$13$	$\mathbf{2916}^{\dagger\ddagger}$	$2840$ ( Echols, 2026b )	$+76$	$13$

Table 2: Coil and symmetric-coil bounds established by this work. Class counts are up to the symmetries of

Q_{n}

, reversal and rotation. The separate symmetric-coil rows refer to translation symmetry.

$n$	$k=1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$\Lambda(n)$
$3$	$4$	$2$	$0$	$0$	—	—	—	—	$4$
$4$	$7$	$6$	$5$	$4$	$2$	$0$	$0$	$0$	$7$
$5$	$13$	$12$	$12$	$12$	$10$	$10$	$8$	$8$	$13$
$6$	$26$	$26$	$25$	$24$	$24$	$24$	$24$	$24$	$26$
$7$	$50$	$50$	$50$	$52$	$51$	$50$	$49$	$48$	$52$
$8$	$98$	$\geq 98$	$\geq 100$	$\geq 100$	$\geq 100$	$\geq 101$	$\geq 102$	$\geq 104$	$\geq 104$

Table 3: The head of the Snakepit-in-the-Box table

L(n,k)

. Dashes are infeasible;

\Lambda(n)

maximizes over all

k

. Unqualified entries are exact (Appendix D );

\geq

entries are achieved lower bounds.

Appendix figures & tables5 assets

Supplementary material from the paper’s appendix.

Appendix

	Parameter	Setting
Search	width per move $b$ ; beams per anchor $B=nb$	$192$ ; $1{,}728$
	search noise $T_{\mathrm{BA}}$	$0.25$ , constant
	action-sequence capacity $H$	$192$ (never binding)
Walks	walks per cycle $P$	$16$
	training start prefix length $\ell_{0}$	$10$
	shallow / deep thresholds $\ell_{\mathrm{a}}$ , $\ell_{\mathrm{b}}$	$10$ , $20$ moves

Appendix

Table 4: Beam Anchor production settings in

Q_{9}

. Length-dependent temperatures interpolate linearly between the shallow and deep thresholds; the walk temperature also decreases linearly over training (Eq. 4 ).

Panel of Figure 4 — Figure 4: Distribution of $d_{\max}$ over the $100$ length- $190$ classes found by Beam Anchor in $Q_{9}$ . All lie in the continent’s mode of the length- $190$ bank (Figure 3 ); none reaches the island’s modes at $d_{\max}=52$ and $54$ .

Parameter	Nominal production setting
Peak / minimum temperature	$2.0$ / $10^{-4}$
Fragmentation penalty	$\beta=3.2$ , per-chain jitter $\pm 0.30$
Surgery probability / dimension	$0.35$ / uniform $d\in\{2,3,4\}$
Reheating periods	$M\in\{64,128,256\}\times 10^{6}$ moves
Chains / device; moves / launch	$131{,}072$ ; $2{,}000{,}000$
Stall threshold; bank reseeding	$30$ launches; probability $0.5$

Appendix

Table 5: Nominal forest-annealer settings; run-specific overrides are recorded in the release manifests. The minimal mixture splits nonsurgery proposals equally between addition and removal; production endpoint-move probabilities depend on the recipe.

Seed	A	B	B $-$ A	A	B	A	B
	Best snake edges			Proposals ( $10^{9}$ )		Full cycles
$0$	$152$	$188$	$36$	$16.015$	$6.686$	$250$	$104$
$1$	$147$	$186$	$39$	$15.300$	$6.384$	$239$	$99$
$2$	$149$	$187$	$38$	$16.151$	$6.735$	$252$	$105$
$3$	$148$	$188$	$40$	$16.194$	$6.753$	$253$	$105$
$4$	$155$	$191$	$36$	$16.145$	$6.733$	$252$	$105$

Appendix

Table 6: All ten paired outcomes after

3{,}600

seconds per recipe and seed in

Q_{9}

. A: add/remove; B: surgery/add/remove. Proposals count every attempt, including illegal and no-op proposals; full cycles count completed

64

-million-proposal periods.

Elapsed checkpoint (s)	A median [range]	B median [range]
$90$	$143\ [143,147]$	$181\ [175,184]$
$240$	$146\ [143,147]$	$182.5\ [181,191]$
$900$	$147\ [144,155]$	$185.5\ [184,191]$
$3{,}600$	$149\ [147,155]$	$188\ [186,191]$

Appendix

Table 7: Best-so-far validated single-snake edge lengths at the four prespecified checkpoints, across ten runs per recipe. Each checkpoint is recorded at the first completed proposal after its deadline.

Explore similar work

Improved Upper Bounds for Slicing the Hypercube
Feb 6, 2026Duncan Soiffer, Nathaniel Itty, Christopher D. Rosin +5Slices Upper Bounds
Carnegie Mellon University · Work done while at Worcester Polytechnic Institute · Constructive Codes +1
Improved lower bounds for the Shannon capacity of odd cycles
Jul 23, 2026Nathaniel Itty, Christopher D. Rosin, Chase Carstensen +1Maximum Independent Set Lower Bounds
Worcester Polytechnic Institute · Constructive Codes
Neurosymbolic Discovery of Algebraic Graph Constructions
Aug 8, 2026David Seka, Stefan SzeiderAcyclic Graphs Algebraic Structures
Algorithms and Complexity Group TU Wien, Vienna, Austria

Feb 6, 2026, cs.AIJ/K move · Enter open · S save

Improved Upper Bounds for Slicing the Hypercube

Duncan Soiffer, Nathaniel Itty, Christopher D. Rosin, Blake Bruell+4

Carnegie Mellon University · Work done while at Worcester Polytechnic Institute · Constructive Codes+1

Slices Upper Bounds Lower Bounds Polytopes Maximum Independent Set

Open paper AskPDF arXiv

A collection of hyperplanes

\mathcal{H}

slices all edges of the

n

-dimensional hypercube

Q_n

with vertex set

\{-1,1\}^n

if, for every edge

e

in the hypercube, there exists a hyperplane in

\mathcal{H}

intersecting

e

in its interior. Let

S(n)

be the minimum number of hyperplanes needed to slice

Q_n

. We prove that

S(n) \leq \lceil \frac{4n}{5} \rceil

, except when

n

is an odd multiple of

5

, in which case

S(n) \leq \frac{4n}{5} +1

. This improves upon the previously known upper bound of

S(n) \leq \lceil\frac{5n}{6} \rceil

due to Paterson reported in 1971. We also obtain new lower bounds on the maximum number of edges in

Q_n

that can be sliced using

k<n

hyperplanes. We prove the improved upper bound on

S(n)

by constructing

8

hyperplanes slicing

Q_{10}

aided by the recently introduced CPro1: an automatic tool that uses reasoning LLMs coupled with automated hyperparameter tuning to create search algorithms for the discovery of mathematical constructions.

Abstract

Explore similar work

Improved Upper Bounds for Slicing the Hypercube

Improved lower bounds for the Shannon capacity of odd cycles

Neurosymbolic Discovery of Algebraic Graph Constructions