A machine learning approach that beats Rubik's cubes
Authors: Alexander Chervov
Kirill Khoruzhii
Nikita Bukhal
Jalal Naghiyev
Vladislav Zamkovoy
Ivan Koltsov
Lyudmila Cheldieva
Arsenii Sychev
Arsenii Lenin
Mark Obozov
Egor Urvanov
Alexey M. Romanov
Venue: NeurIPS 2025 spotlight ()
Keywords: pathfinding
multi-agent
ML
machine learning
Cayley graph
Rubik
cube
MLP
Primary area: machine_learning_for_sciences
TL;DR: The paper proposes a novel machine learning–based approach that can solve different puzzles and demonstrate unprecedentedly short results when solving Rubik's cubes up to 5x5x5.

Abstract: The paper proposes a novel machine learning-based approach to the pathfinding problem on extremely large graphs. This method leverages diffusion distance estimation via a neural network and uses beam search for pathfinding. We demonstrate its efficiency by finding solutions for 4x4x4 and 5x5x5 Rubik's cubes with unprecedentedly short solution lengths, outperforming all available solvers and introducing the first machine learning solver beyond the 3x3x3 case. In particular, it surpasses every single case of the combined best results in the Kaggle Santa 2023 challenge, which involved over 1,000 teams. For the 3x3x3 Rubik's cube, our approach achieves an optimality rate exceeding 98%, matching the performance of task-specific solvers and significantly outperforming prior solutions such as DeepCubeA (60.3%) and EfficientCube (69.6%). Our solution in its current implementation is approximately 25.6 times faster in solving 3x3x3 Rubik's cubes while requiring up to 8.5 times less model training time than the most efficient state-of-the-art competitor. Finally, it is demonstrated that even a single agent trained using a relatively small number of examples can robustly solve a broad range of puzzles represented by Cayley graphs of size up to $10^{145}$, confirming the generality of the proposed method.

A machine learning approach that beats Rubik's cubes
Alexander Chervov" Institut Curie, Universite PSL Paris, F-75005, France
Kirill Khoruzhii*
Technical University of Munich Garching, 85748, Germany
Nikita Bukhal Novosibirsk State University Novosibirsk, 630090, Russia
Jalal Naghiyev
Vladislav Zamkovoy Independent Researcher Moscow, 119454, Russia
Technical University of Munich Garching, 85748, Germany
Ivan Koltsov RTU MIREA Moscow, 119454, Russia
Lyudmila Cheldieva
Arsenii Sychev RTU MIREA Moscow, 119454, Russia
RTU MIREA Moscow, 119454, Russia
Arsenii Lenin RTU MIREA Moscow, 119454, Russia
Mark Obozov Innopolis University Innopolis, 420500, Russia
Egor Urvanov RTU MIREA
Moscow, 119454, Russia
Alexey M. Romanoy RTU MIREA Moscow, 119454, Russia romamov@mires ru
Abstract
The paper proposes a novel machine learning-based approach to the pathfinding problem on extremely large graphs. This method leverages diffusion distance estimation via neural network and uses beam search for pathfinding. We demon- strate its efficiency by finding solutions for 4x4x4 and 5x5x5 Rubik's cubes with unprecedentedly short solution lengths, outperforming introducing the first machine learning solver beyond the 3x3x3 case. In particular, it surpasses every single case of the combined best results in the Kaggle Santa 2023 challenge, which involved over 1,000 teams. For the 3x3x3 Rubik's cube, our approach achieves an optimality rate exceeding 98%, matching the performance of task-specific solvers and significantly outperforming prior solutions such DeepCubeA (60.3%) and EffficientCube (69.6%)) Our solution its current im- plementation is approximately 25.6 times faster in solving 3x3x3 Rubik's ss cubes while requiring up to 8.5 times less model training time than the most efficient state-of-the-arr competitor. Finally, it is demonstrated that even a single agent trained using a relatively small number of examples can robustly solve broad range of puzzles represented by Cayley graphs of size up to 10 1455 confirming the generality of the proposed method.
available solvers and
AAlexander Chervov and Kirill Khoruzhii contributed equally this work. Corresponding author
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Introduction
Rubik's cube is one of the most famous puzzles, which believed to be played by more than a billion
people in the world [ According to (2). it was included in the 100 most influential inventions of
the 20th century. Even decades after its first introduction, it is still used as a benchmark and model
task in various fields: artificial intelligence [3] robotics 44, graphs algorithms [5], [6], cryptography
77]. image encryption abilities [13.
[ statistical physics
group theory (11. [12] for human cognitive
From a broader perspective, solving the Rubik's Cube is specific instance of planning problem. One must plan actions to transition between the initial and solved states. The mathematical framework for such problems is pathfinding on graphs (state transition graphs); all possible states are represented as nodes, and edges correspond to transitions between states based on actions (moves). The planning task thus reduces to finding a path from a given initial node to one or more desired nodes. A specific class of graphs represents the Rubik's s Cube and similar puzzles-Caylly-eeeeee Cayley-type graphs of the puzzle's s symmetry group. These are highly symmetric state transition graphs where the symmetry group can transform any node into another. Cayley graphs are of fundamental importance in modern mathematics [14, [5] and have numerous applications: in bioinformatics for estimating evolutionary distances [6
17 18 19: in processor interconnection networks (20 21 22) in coding theory for the
construction of expander graphs and related codes [23]: in cryptography for constructing specific hash
functions (4 77: in machine learning (ML) [8]; and in quantum computing [25] 26 27 28 29]
Finding the shortest paths on generic finite Cayley graphs is an NP-hard problem 30, as it for many
particular groups: the Rubik's 's Cube group B and some others B2, 18]. Brute force breadth-firs search, Dijkstra's, ss and related methods can find the shortest paths on graphs with billions of nodes, the bidirectional trick squares feasible sizes, but these methods require extremely large computational resources and are not practical for much larger sizes, which are of our interest. Moreover, no effective tools are currently available to find any (not just the shortest) paths on Cayley graphs of large finite groups. For example, modern computer algebra systems like GAP fail on any sufficiently large group, such the 4x4x4 Rubik's s Cube.
This research aims to overcome the abovementioned limits in solving large Rubik's cubes and similar large-scale pathfinding problems with a high level of optimality using machine learning. The main contributions to the state of the art are the following:
1. We propose novel multi-agent, machine learning- based approach to find paths on Cayley graphs of finite groups. groups. is the first machine learning approach capable of handling groups as large as 10"4. It achieves over 98% optimality on the DeepCubeA dataset of 3x3x3 cubes, reaching the level of task-oriented solvers based on pattern databases. It produces better results (shorter solution paths) than any known competitor for 4x4x4 and 5x5x5 Rubik's Cubes, including the aggregated best results from the 2023 Kaggle Santa Challenge, representing the current state of the art.
2.
We demonstrate that increasing the size of the set used to train multilayer perceptrons with residual blocks has a limited impact on the pathfinder's performance. At the same time, increasing the beam width and number of agents robustly improves the average solution length and optimality. This surprising finding helped choose the size of the train data for each agent and achieve best-in-class performance without wasting computational resources on additional training.
3. The training time and computational resources required for our approach are significantly the- art approaches. Our solution, tested on the same hardware and beam width providing solution length similar to the EfficientCube (the previous leading ML solution) solving the task approximately 25.6 faster and requiring up to 8.5 times less model training time than the competitor.
smaller than those for state-of- state-of-the-art
4. We demonstrate that even a single agent trained using a relatively small number of examples can robustly solve a broad range of puzzles represented by Cayley graphs with sizes up to 10 confirming the generality of the proposed method.
In recent years, machine learning has been emerging as "a tool in theoretical science"
34 leading
to several noteworthy applications to mathematical problems 35 36
37
38
This
research is part of the larger project, which aims to create an open-source machine learning Python

---

framework for analyzing Cayley graphs and contribute to the fascinating, emerging area of machine learning applications in theoretical sciences.
2 Proposed Machine Learning Approach
This paper presents a unified approach for finding paths on large class of graphs, focusing on demonstrating its efficiency for Rubik's cube graphs. It does not rely on any prior knowledge or human expertise about the graphs. The approach has two main components: a neural network model and a graph search algorithm - similar to previous works such as AlphaGo/AlphaZero [K] [4) DeepCube [4). [. and EfficientCube [46), among others. The model is trained to guide what moves should be done to get closer to the destination node (" ("solved state" for puzzles). The graph search algorithm starts from a given node and moves to nodes closer to the destination, based on the neural network's 's predictions, until the destination node is found.
The basic assumption on a graph is that there is vector associated with each node (feature vector). These vectors serve as an input for the neural network. The precise quantification of requirements for feature vectors that would ensure the successful operation of the proposed method is challenging. We aim to demonstrate its efficiency the context of Rubik's group cases. On one extreme, even random vectors suffice if the training data covers all nodes an idea employed in well-known approaches such as DeepWalk [47] and Node2vec [48]. However, our focus is different: only a small subset of nodes will be covered by the training data (random walks). The key point is the ability of the neural network to generalize from that small subset to the entire graph - something that is impossible with random features. Worse, the feature vectors are related to the distance between nodes on graph more training data is required, and more advanced parameters and resources should be used at all steps of the proposed method. The role of the neural network is to transform the initial feature vectors into a latent representation, where nodes that are closer on the graph are also closer in the latent space. For puzzles or permutation groups the feature vector is just the vector describing the permutation of I-symbols. i.e. vector of numbers p(1), we assume that specific node on the graph, such as the 'solved state" for puzzles, is selected. The task is to find a path from any given node to this selected node. Since the graph sizes may exceed 1040, standard pathfinding methods are not applicable.
- 2), p(l - 1)). Additionally,
The key steps of the proposed method are illustrated in the figure T and described below:
Creating the training set via random walks. (Diffusion distance.) Generate N random walk trajectories starting from a selected node. (The generation of a random walk is a simple process: select random neighbor of the current node and repeat this process iteratively for multiple steps.) Each random walk trajectory consists of up to Kmax steps, where N and Kmmx are integer parameters of the method. For some nodes encountered during the random walks, we store a set of pairs (v,, k), where u represents the vector corresponding to the node and is the number of steps required to reach it via the random walk. This set will serve the training data. For the Rubik's Cube, random walks correspond to random scrambling: starting from the "solved state." we perform a scries of random scrambles and record the resulting positions and the number of scrambles performed. Conceptually, in the limit as N - oc, the average value of & measures the "diffusion distance" - roughly speaking, estimate of how quickly diffusion reaches given node. In
the length of the random path contrast to the DAVI approach used in [3. random walk generation is very computationally cheap, making it possible to generate them directly during the training procedure.
Training the neural network. The generated set of pairs (v. k) serves as the training set for the neural network. Specifically, v serves as the 'feature vector' (the input for the neural network), and & represents the 'target' (the output the network needs to predict). Thus, the neural network's predictions for given node estimate the diffussin distance from to the selected destination node (solved state of the puzzle). We utilize a multilayer perceptron (MLP) architecture with several residual blocks and batch normalization, shown in Figure Lp, which will be further called ResMLP. is a general form of the MLPs used in 3 46 All the models are trained in advance before the solving phase.
Graph search guided by a neural network. Beam search. This step finds a path from given node to the destination node. The neural network provides heuristics on where to make the next steps, while the graph pathfinding technique compensates for any possible incorrectness in the neural network predictions. The beam search pathfinding method is quite simple but has proven to be the
3

---

Training phase
(b) Model architocture
Generating training set (For a single epoch)
Update model parameters
Lincor
Linear
One Hot
Agx.M BatchNorz
Encoding
BatchhNorm
ReLu
Linear
Linear Mix.N BatchNorm
ResBlock Ngx N2
ResBBlock Nox Ni
Linenr My1
6rtx
NormhNoom
ReLU
ReLU
Loss
A
(c) Beam search example
Agent weights
Solving phuse
Agents
ULB L...
Beam search pathfiuder
Shortest path selection block
Scramble
Solution move sequence
Model
Model distance estimation
20
Figure I: Proposed ML solution for Rubik's cube solving: (a) proposed multi-agent solver's process flow; (b) ResMLP neural network architecture; (c) an example of beam search pathfinding on 3x3x3 cube's graph using W = 40.
most effective for us and works as follows. Fix positive integer W parameter known the "beam width" (or "beam size"). Starting from a given node, we take all its neighboring nodes and compute the neural network predictions for all of them. We then select the W nodes closest the destination according to the neural network (i.e., the predictions have smaller values). We take these selected W nodes' neighbors, drop duplicates, and again compute the neural network predictions, choosing the top W nodes with the best (i.e., minimal) predictions. The search iterations are repeated until the destination node is found (or the limit of steps is exceeded). The whole process is illustrated in Figure
Multi-agency. The method described in the steps above relies random walks for train set creation, and thus, due to that randomness, each new launch will create new train set, and thus, each new neural network approximates the distance differently. This diversity is large enough to yield new solution path for each launch typically. And hence, typically, several repetitions allow for the discovery of shorter path than single run. We call each trained neural network agent. To solve any given state we solve it with all the agents and then choose the best result (the shortest solution path among all the agents) illustrated in Figure I.).
3 Optimality vs the Proposed Approach Parameters
The proposed solver has the following main parameters A the number of agents, W beam width used by each agent during pathfinding and ResMLP model general parameters: Ni the size of the first layer, N2 the size of the second layer and residual blocks' layers, N,- - the number of residual blocks and T the trainset size. For easier comparison, N1, N2, and N, are also summarized by model size P - the total number of ResMLP parameters (weights and biases). In this section, we analyze the influence of these parameters the solver's 's average solution length and optimality.
Train set size. First, the example of 3x3x3 and 4x4x4 Rubik's cubes, we analyzed how the model and trainset sizes, well as model depth, influence the average solution length using single agent with fixed beam width (W 215). The experiment details are provided in Appendix B.6] while the results are presented in Figure 2 It is seen from Figure 2 that from certain point, the raise of

---

(a)
Ruchik'ss Cubbe 3x3xx
Rubik's Cubee 4xc4xc
(b)
Rubiik's Cube 3x3x3
Ruihi''s 's Cube 4xcxi4
23.0
Towase sin 1.
22.00
Jeg estetin lengh
-2>
22.5
27:75
23.50
22.0
70
23.25
00
21.5
20.00
4005
05
21.9
53
20.75
Drrae 234
24
20h
2
50
1it R7
214
212
20.50
2
214
2H:
2
2
2
200
Trainset
BOME sice
Beam
W
Figure 2: Influence of model parameters solution length for 3x3x3 and 4x4x4 cubes Gjitter plot): (a) influence of the model size, trainset sizes, and model depth on average solution length; (h) influence of the beam width on average solution length.
T does not lead to any significant reduction of average solution length, especially considering the fact that the trainset size is demonstrated in logarithmic scale. Even more surprising, the T value corresponding to this point is very similar for 3x3x3 and 4x4x4 cubes and neural networks of different sizes and depths. Thus, the experiments above reveal rather unexpected effect- performance stagnation with respect to the train size.
Additional tests were performed to check if the proposed neural network faces grokking when being trained on huge amounts of data. For this purpose, we spent more than 7 days fully utilizing two NVIDIA H100 GPUs to train two neural networks on 524B examples of 4x4x4 Rubik's 's cube states. In both cases, the loss was continuously decreasing from se 26.4 on 8B examples down to 23.8 at the end of training. There was no sign of delayed generalization. At the same time, the loss was notably decreasing, which led us to further analysis of the stagnation effect.
Then, we used both of these networks to solve the complete set of Santa Challenge scrambles for the 4x4x4 cube. For fair comparison, also used snapshots of both networks made after training on 8B examples to solve the same scrambles.
First, we faced the fact that, using half- peffirrcciion during inference, the solvers based on networks trained on 524B examples were unable to solve any of the scrambles. On the contrary, the versions trained on 8B examples were fully compatible with half-precision inference. Thus, faced the first drawback of using huge trainsets - the longer inference time.
The comparison of the solutions found using single- precision during inference shows that networks trained on 524B examples achieved average solution rates of 48.56 56 and 49.46, finding solutions for 43/43 and 41/43 scrambles, respectively. As seen from Figure 3, these results are comparable with the ones achieved by the solvers with neural networks trained on 8B of examples. The solvers equipped with snapshots of the tested networks, stored after training on 8B examples, achieved average solution rates of 49.3 and 49.74, finding solutions for 43/43 and 42/43 scrambles, respectively, From one point of view, the results provided by networks trained on 524B examples are generally better (even though one of the networks "forgot" how to solve one of the scrambles). From another point of view, during the computation time spent such long training, up to 63 networks can be trained on 8B examples. At the same time, as it will be shown further (Figure B3,, even ten solvers equipped with networks trained on 8B examples provide average solution length far below 47. The detailed solution analysis for the experiment is provided in Appendix B.7
The example described above illustrates our interpretation of the observed stagnation effect. It does not mean that further training will not provide a better average solution rate. However, at some point, the computational effort for further training exceeds that required to achieve the same or better results using multiple agents, which are based on networks trained on fewer examples. Moreover, multiple agents can be easily accelerated using distributed computing, whereas boosting the training and inference of a single-agent approach generally requires more advanced GPU hardware.
MLP layers and sizes. As expected, larger and deeper networks trained on train sets of the same size generally provide shorter solutions than smaller models. What less expected is that the higher number of layers (higher NI, N2. and N,) is more significant than larger number of parameters P. More surprising is that even small models with 1M of parameters can reach the average solution length comparable to DeepCubeA and EfficientCube using neural networks with ss 14. 7M parameters.
5

---

Based on these observations for further consideration, we used a deep neural network having the same number of layers (ten) as 3 and 44). but with the smaller model size of 4M parameters.
Beam width. It is the most important parameter. We performed multiple tests on a single agent equipped with this model, changing W from 21 to 2 The results of these tests are presented in Figure 2b (the exact model parameters and details of the tests are provided in Appendix (B.)). From Figure 2p. is clear that increasing W effectively reduces the average solution length. Moreover, the solution length decreases approximately linearly with the logarithm of the beam width W. On the 3x3x3 cube, increasing W up to 2 allows us to get close to the optimal solution, while for 4x4x4, the same beam width results in a better average solution length than the best ones submitted to the 2023 Santa Challenge.
Agents number. In the third part of the experimental studies, we investigated the influence of the number of agents A on the solver's efficiency. These experiments were performed on 3x3x3, 4x4x4, and 5x5x5 Rubik's Cube. We used 10-layer Res.LLP models with 4M parameters trained on 8B states in all the cases. The beam width was chosen W 224 so each agent could fit into the memory of single GPU regardless of the solved cube size. The details of the performed experiments are available in Appendix [B6]] while their results are provided in Figure For ease of analysis, Figures Ba 3 demonstrate lengths only for those agents whose solutions at least once were used as the solver's ' output. The shaded area in Figure 3l representing the standard error of the mean (the standard deviation divided by the square root of the number of samples), calculated as the standard deviation divided by the square root of the number of scrambles used to compute each average, which allows comparison of solver performance.
(a) Rubik's Cube 3x3x3
(b) Rubik's Cube 4x4x4
(0) Rubik's Cube 5x5x5
21.0
107.5
Aorg solution length
50-
Aug solution Bungeth
105.0
20.8
49-
102.5
sobtton
100.0
20.6
20.4
47
95.0
92.5
10
Number of agents
Number of agents
Number agents
18
19
30
21
(d) Rubik's Cube 3x3x3
20.38
5/26 agrens
Agunts
20,00
20.92
Scramble ID)
Rubik's Cube 4x4xd
(f) Rubik's Cube 3x5x5
60
46.51
100
125
150
92,16
10/ / 20 apents
48.00 (t.
2001
Agents
49. 61
40.07
Agonts
103.2
102.8
40.86
164.1
50.10
104.6
50.00
106-4
51 26
108.7
50.03
109.9
Scramble ID
Seramble ID
Average solution length of the proposed multi-agent approach depending on the number of agents composing its output for (a) 3x3x3, (b) 4x4x4, and (c) 5x5x5 Rubik's cubes. Solid line - random set of the agents, dashed line - best set. Shaded area indicates +1 standard error around the mean solution length. Distribution of solution lengths for (d) 3x3x3, (e) 4x4x4, and (f) 5x5x5 Rubik's 's cubes for the best ensemble.
Figure 3:
Figure cleerrl shows that the average solution rate of multi-agent is always higher than the one achieved by the best single agent (up to 8 moves for the 5x5x5 cube). Solid lines on Figures 3bg show how the size the ensemble influences the average solution length for the random set of the agents. As seen in all three cases of 3x3x3, 4x4x4, and 5x5x5 Rubik's 's cubes, the larger number of agents robustly provided more optimal pathfinding. The dashed line demonstrates the same dependency but for the set of agents jointly providing the best overall solution. Figures 3

---

demonstrate in color code how each agent from this set participates in the final solution for every scramble from the dataset. The scrambles which were not solved in less than 200 moves are marked with crosses.
As seen from Figures 3e 3. the worst agents in the ensemble not only provide much longer results than the final solution but also include multiple scrambles that were unsolved. In the case of using the single-model approach, these agents would be considered unsatisfactorily trained. Nevertheless, they are included in the best ensemble because they provided the shortest solution on one or two scrambles. Moreover, our approach achieved an efficiency that was previously unreachable for other ML solutions, largely due to the specialized agents.
Even though the results presented in Figure Jon 3x3x3, 4x4x4, and 5x5x5 cubes can be achieved using 5, 10, and 10 agents, respectively, the probability of training all these agents in a row is very low. For example, heat all the 5x5x5 scrambles from the 2023 Santa Challenge dataset, we trained 69 different agents, while further analysis showed that only 10 of them composed all the output results. At the same time, the first agent trained to solve 4x4x4 cubes beat all the respective scrambles from the mentioned dataset but did not even get in the final ensemble because multiple other agents jointly surpassed it. Thus, achieving high level of optimality requires many agents, as seen from the logarithmic nature of the plots demonstrated in Figure 3 Nevertheless, due to the high scalability of the proposed approach and the ability to run on distributed hardware using dozens of independent agents, it is not an issue using modern computational hardware.
4 Results Summary and Comparison with Prior Art
4.1 Comparison with the other solutions for Rubik's 's cube solving
Table summarizes the main results achieved by the proposed solver, highlighting its superiority over the prior state of the art. Notably, it surpasses the 2023 Kaggle Santa Challenge results, where over a thousand teams competed in virtual puzzle solutions, representing the best available methods and results. It should be mentioned that we were limited in computation resources during our research. Thus, our results can be improved even more by using more advanced hardware, which will allow for an increase in beam width and the number of agents.
Table I contains the following abbreviations: HTM half-turn metric, QTM - quarter-turn metric. The 2023 Kaggle Santa Challenge dataset uses modified QTM with unfixed corners and centers of the cube, which is marked UQTM. Optimal PDB+ solver is a solver used determine the God's number for the 3x3x3 Rubik's s Cube"] The results presented in [49 were evaluated using a single cube scrambled with 100 random moves. For these results, column "Avg. solution len" contains the minimal length achieved by the most suitable genetic algorithm configuration. The optimality was not evaluated for these results and the results from the 2023 Kaggle Santa Challenge dataset. The values provided in parentheses in Table [ iiniicate the standard error of the mean. From the perspective of sampling random states of a given group, this allows statistically significant comparisons between the performance of different solvers.
A single agent with single-layer MLP can solve all the DeepCubeA dataset with 90.4% of optimality, significantly enhancing results of the most advanced state-of-the-art ML solutions: DeepCube and EfficientCube. 26 agents equipped with 10-layer ResMLP models managed to solve all 1000 scrambles from DeepCubeA dataset with 97.6% optimality, which is the best result ever achieved by any ML solution (significantly surpassing 60.3%, 69.8% results from DeepCubeA and EfficientCubbe. A single-agent solution implemented using our approach and 10-layer ResMLP managed to beat each best result corresponding to 3x3x3 and 4x4x4 Rubik's cubes submitted on the 2023 Kaggle Santa Challenge (averages: 48.98 vs 53.49). At the same time, 29 agents managed to solve all the 4x4x4 cube's 's scrambles from the 2023 Kaggle Santa Challenge dataset with an average solution length of 46.51 which is below 48 (a conjectured 4x4x4 Rubik's 's cube diameter (51). Finally, an ensemble of 69 agents beat each best solutions for the 5x5x5 Rubik's cube submitted to the 2023 Kaggle Santa Challenge, shortening the average solution rate among all the datasets on more than 4.4 units in QTM metrics (ours: 92. 16. Santa: 96.58). It is worth emphasizing that the solutions that were obtained outperformed the Santa results on average and in every single case.
3 All the solvers presented in the Table managed to solve all the scrambles from the listed datasets. httpa//wwwaaoooooeote/e/ooeeeea.
7

---

Table 1: The most notable results achieved by the proposed solution and comparison with competitors.
No. Solver
Metric,
Size,
Solver parameters
Average solution length
Optimality
Dataset
T
2x2x2 Rubik's cube
Genetic 49
HTM, 1, 49
n/a
n/a
n/a
n/a
30
n/a 100%
2 Breadth First
QTM, 100, Ours
n/a
n/a
n/a
n/a
10.7(1)
Search
3 Ours, I-layer MLP Ours, 10-layer
QTM, 100, Ours
218
0.15M
8B
10.7(1)
100%
QTM, 100, Ours
218
0.92M
8B
10.7(1)
100%
ResMLP
3x3x3 Rubik's cube
Genetic Optimal PDB+ solver
HTM, 49
n/a
n/a
n/a
n/a
238
n/a 100%
6
QTM, 1000,
3
n/a
n/a
n/a
n/a
20.64(3)
7
DeepCubeA
3
QTM, 1000,
3
n/a
14.7M
10B
21.50(3)
60.3%
EfficientCube
46
QTM, 1000,
3
2
14.7M
52B
21.26(3)
69.6%
9
EfficientCube
46
QTM, 1000,
218
14.7M
52B
21.26(3)
69.8%
(reproduced)
10
Ours, 10-layer
QTM, 1000,
218
4M
8B
21.14(3)
75.4%
ResMLP
11
Ours, I-layer MLP Ours, 10-layer
QTM, 1000,
3
221
0.34M
8B
20.83(3)
90.4%
12
QTM, 1000,
224
4M
8B
20.69(3)
97.3%
ResMLP
13
Ours, multi-agent
QTM, 1000,
26
224
4M
8B
20.67(3)
98.4%
10-layer ResMLP
14
Santa
UQTM, 82,
50
n/a
n/a
n/a
n/a
21.8(1)
n/a
Challenge
(50
15
Ours, 10-layer ResMLP
UQTM, 82, 50
224
4M
8B
19.5(1)
n/a
4x4x4 Rubik's 's cube
16
Genetic
49
HTM, 1, 49
n/a
n/a
n/a
n/a
737
n/a
17
Santa
UQTM, 43, (50]
n/a
n/a
n/a
53.5(2)
n/a
Challenge
50
18
Ours, 10-layer ResMLP
UQTM, 43, 50
221
4M
8B
49.0(4)
n/a
19
Ours, multi-agent 10-layer ResMIP
UQTM, 43, 50
29
221
4M
8B
46.5(3)
n/a
5x5x5 Rubik's cube
20
Genetic
49
HTM, 1, 49
n/a n/a
n/a
n/a
1761
n/a
21
Santa
UQTM, 19, 150
n/a n/a
n/a
n/a
96.6(8)
n/a
Challenge
50
22
Ours, multi-agent 10-layer ResMLP
UQTM, 19, 50
69 224 4M
8B
92.2(7)
n/a

---

Analyzing comparison results in Table should be noticed, that A agent equipped with model of P size are equivalent to single agent with model having A parameters (e.g.. 26 agent with 4M models are computationally comparable to agent with 104M model). At the same time, from hardware point proposed multi-agent solution is much easier to scale using distributed computing than approaches based on large single model.
4.2 Comparison with the previous art in terms of computation time
The efficiency of our approach is driven not only by the large number of agents but also by the efficiency and simplicity of each single node. is difficult to fairly compare computation time between different solutions, because experimental studies published in research papers were performed using different hardware. Moreover, ins such direct comparison disadvantages of algorithm can be hidden by performance boost driven by more modern GPU family. Thus, we performed an additional test and compared it with EfficentCube, which is claimed to be more efficient than DeepCubeA [46] in terms of average computation time while running on the same hardware. The training procedure for EfficentCube took 25 hours 50 minutes 45 seconds, while the model for our solution was trained in 3 hours minutes 36 seconds. In both cases training was performed using 32-bit floats. Then, both solutions were used to solve all the scrambles from the DeepCubeA dataset (see results No.9 and 10 in Table Dp. For both solutions we used the same beam width of 2 which provided very close average solution length. The similarity in solution length makes this comparison fair even both algorithms rely on different models and beam search implementations. Finally, EfficientCube required 237.9 s on average to solve a single scramble, while our solution required 9.16 s, which is 2 25.6 times faster.
is worth mentioning that comparison is fair not because used the same beam width, but because in both cases solvers were running on the same hardware and provided very close average solution length. Multiple factors cause the demonstrated performance boost. First, we used model containing 3.675 times fewer parameters and only one output (instead of the 12 outputs used in Efficien(Cube). This model generally requires less computational resources for both training and inference. Moreover, the training duration was shortened by 6.5 times less trainset size. Second, we used 16-bit half-precision floating point variables instead of 32-bit wide during inference. EfficientCube was configured with the same option, but due to inefficient software implementation it gives only 10% performance gain, while our case the computation speed was approximately doubled. Third, our implementation is much more optimized for running on GPU, which provides the rest of the performance boost. Finally, our approach is much more scalable because agents are independent and can be executed on different processors and GPUs.
4.3 Analysis of efficiency for solving other puzzles
To demonstrate the generality of our approach beyond Rubik's s cube groups we conducted experiments across diverse range of permutation groups with sizes up to 10-45 elements. The details of this experiment and its results are presented in the Section B.8 [B8 and Table In short, we fixed the neural network architecture parameters (N1 1024, N2 epochs on various groups, using beam width W = 22 for all experiments. This experiment design reveals both the strengths and limitations of our approach-whil some extremely large groups remain unsolvable with these fixed parameters, the method successfully solves most tested groups with remarkable efficiency- achievinnnnng short training times (typically under 2 minutes using), fast inference (under minute for most groups), and producing solution paths of practical length
256, N,
and trained models for 128
For groups not included in the Santa Challenge, we tested performance on 10 states obtained through 10,000 random moves from the solved state. Our approach successfully solved 100% of test cases for 28 out of 39 tested groups, including challenging domains like Pancake sorting [52 (known as NP-hard), LRX (53) and the 15-puzzle with periodic boundary conditions [54].
Our method consistently solved the 10 non-Rubik groups. and the average solution lengths were better than the top solutions in the Santa Challenge. This evaluation provides strong evidence that our approach generalizes effectively across various permutation groups, demonstrating robustness and computational efficiency regardless of group structure or size.
Mentioned above times achieved using NVIDIA H100 GPU.
9

---

4.4 Limitations
This paper reports on purely empirical research. Our results demonstrate that the proposed method is effective for multiple groups and outperforms all previously published machine learning solutions for solving Rubik's 's cuhes up to 5x5x5. However, direct application of our results to other tasks requires additional theoretical analysis, which is beyond the scope of this paper.
To the best of our knowledge, there is no optimal solver for 4x4x4 and 5x5x5 Rubik's cubes. Furthermore, the diameter of the corresponding graphs has not yet been precisely defined. Thus, we were limited to the available reference datasets in order to provide results that are comparable to those of the state of the art. It should be noted that the Kaggle Santa 2023 Challenge Dataset includes only a small number of examples for large groups (e.g., it includes only 19 scrambles of the 5x5x5 Rubik's 's Cube). Considering this, broader generalization of the results requires additional research.
5
Conclusion
The paper proposes a machine learning-based approach to the pathfinding problem on large graphs. Experimental studies demonstrate that it more efficient than state-of-the-an solutions terms of average solution length, optimality, and computational performance.
The key parts of the approach are multi-agency, neural networks predicting diffusion distance and beam search. Deeper neural networks better approximate the graph of the large Rubik's cubes, though, for the 3x3x3 case, even single-layer network provides excellent results. At the same time, the effect of enlarging the training set is limited: the trainset above 8196M examples for the tested models has no practical reason, which allowed us avoid additional time spent during the training. Conversely, raising the beam width effectively lowers the solution length and increases optimality.
The complete set of the proposed solutions allowed the creation of the multi-agent pathfinder, which managed to beat all the ML-based competitors: an agent equipped with single-layer MLP solved all the DeepCubeA dataset with 90.4% of optimality significantly enhancing results of the most advanced state of the art solutions: DeepCube and EfficientCube. 26 agents equipped with 10-layer ResMLP models managed to solve all scrambles from DeepCubeA dataset with 97.6% optimality, which is the best result ever achieved by any ML. solution. Single-agent solutions implemented using our approach and 10-layer ResMLP beat all the best results corresponding to 3x3x3 and 4x4x4 Rubik's s cubes submitted on the 2023 Santa Challenge. At the same time, six agents managed to solve all the 4x4x4 cube's scrambles from the 2023 Santa Challenge dataset with an average solution length below 48 (a 4x4x4 Rubik's s cube diameter predicted in [5I]). Finally, a composition of 69 agents beat all the best solutions for the 5x5x5 Rubik's 's cube submitted to the 2023 Santa Challenge, shortening the average solution rate among all the datasets on more than 4.4 units in QTM metrics.
Finally, our experimental studies demonstrated that even single agent trained using relatively small number of examples can robustly solve a broad range of puzzles represented by Cayley graphs of size up to 10445, confirming the generality of the proposed method.
6 Acknowledgments
We express our gratitude to Graviton for providing servers for research in the field of Al.
We are deeply grateful to the many colleagues who expressed their interest, participated in fruitful discussions and have contributed to the CayleyPy project at various stages of its development, including: M. Douglas, M. Gromov, S. Nechaev, V. Rubtsov, Mitchell, M. Kontsevich, Y. Soibelman, A. Soibelman, S. Gukov, A. Hayat, T. Smirnova-Nagibedda D. Osin, V. Kleptsyn, G. Olshanskii, A. Ershler, J. Ellenberg, G. Williamson, A. Sutherland, Y. Fregier, P.A. Melies, I. Vlassopoulos, F. Khafizov, A. Zinovyev, H. Isambert, T. Ruzaikin, A. Fokin, M. Goloshchapov, S. Fironov, A. Lukyanenko, A. Abramov, A. Ogurtsov, A. Trepetsky, A. Dolgorukova,
Lytkin, S. Ermilov, Grunvald, A. Eliseev, G. Annikov, M. Evseev, F. Petrov, N. Narynbaev, S. Nikolenko, S. Krymskii, R. Turtayev, S. Kovalev, N. Rokotyan, G. Verbyi, L. Shishina, A. Korolkova, D. Mamaeva, M. Urakov, A. Kuchin, V. Nelin, B. Bulatov, F. Faizullin, A. Aparnev, O. Nikitina, A. Titarenko, U. Kniaziuk, D. Naumov, A. Krasnyi, S. Botman, R. Vinogradov, D. Gorodkov, I. Gaiur, I. Kiselev, A. Rozanov, K. Yakovley, V. Shitov, E. Durymanov, A. Kostin, R. Magdiev, M. Krinitskiy and P. Snopov.
10

---

References
[1] E. Rubik, Cubed: The Puzzle of Us All. Hachette, UK: Orion Publishing Co, 2020.
[2] S. Van Dulken, Inventing the 20th Century: 100 Inventions that Shaped the World from the Airplane to the Zipper. New York, USA: NYU Press, 2002.
[3] F. Agostinelli, S. McAleer, A. Shmakov, and P. Baldi, "Solving the Rubik's 's cube with deep reinforcement learning and search," Nature Machine Intelligence, vol. 1, no. pp. 356-363, 2019.
[4] OpenAI, I. Akkaya, M. Andrychowicz. M. Chociej, M. Litwin, B. McGrew, A. Petron, A. Paino, M. Plappert, G. Powell, Ribas, J. Schneider, N. Tezak, J. Tworek, P. Welinder, L. Weng, Q. Yuan, W. Zaremba, and I.. Zhang, "Solving rubik's cube with a robot hand," arXiv preprint arXiv: 1910.07113 10,, 2019.
[5] R. E. Korf, "Linear-time disk-based implicit graph search," Journal of the ACM (JACM), vol. 55,
no. 6, pp. 1 1-40, 2008.
[6] N. R. Sturtevant and J. Rutherford, "Minimizing writes in parallel external memory search," Proceedings of the Twenty-Thire International Joint Conference on Artificial Intelligence, p. 666-673, 2013. [Online]. Available:
2540225
[7] C. Petit and J. Quisquater, "Rubik's for cryptographers," Notices of the American Mathemati- cal Society, vol. 60, no. 6, pp. 733-740, 2013.
[8] K. Loukhaoukha, J.-Y. Chouinard, and A. Berdai, "A secure image encryption algorithm based on rubik's cube principle," Journal of Electrical and Computer Engineering, vol. 2012, no. 1, p.
173931, 2012.
[9] Y.-R. Chen and C.-L. Lee, "Rubik's cube: An energy perspective." " Physical Review E, vol. 89, no. 1, 012815, 2014.
[10] A. Gower, O. Hart, and C. Castelnovo, "Saddles-to-minina topological crossover and glassiness in the rubik's cube," arXiv preprint arXiv:2410. /4552, 2024.
[11] D. Joyner, "Adventures in group theory: Rubik's cube, merlin's 'ss machine, and other mathematical toys," 2008.
[12] C. Cornock, "Teaching group theory using rubik's 's cubes," International Journal of Mathematical Education in Science and Technology, vol. 46, no. 7, pp. 957-967, 2015.
[13] E. J. Meinz, D. Hambrick, J. J. Leach, and P. J. Boschulte, "Ability and Nonability Predictors of Real-World World Skill Acquisition: The Case of Rubik's Cube Solving," Journal of Intelligence, vol. 11, no. 1, p. 18, 2023.
[14] M. Gromov, "Geometric group theory: Asymptotic invariants of infinite groups." 1993.
[15] Tao, "Expansion in finite simple groups of lie type," 2015.
[16] S. Hannenhalli and P. A. Pevzner, "Transforming men into mice (polynomial algorithm for genomic distance problem)," Proceedings of IEEE 36th annual foundations of computer science, pp. 581-592, 1995.
[17] "Transforming cabbage into turnip: polynomial algorithm for sorting signed permutations by reversals," Journal of the ACM (JACM), vol. 46, no. 1, pp. 1-27, 1999.
[18] J. Wilson, M. Bechler-Speicher, and P. Veličković, "Cayley graph propagation." arXiv preprint arXiv:2410.0344 0444444, 2024.
[19] L. Bulteau and M. Weller, "Parameterized algorithms in bioinformatics: an overview," Algo- rithms, vol. 12, no. 12, 256, 2019.
[20] S. B. Akers and B. Krishnamurthy, "A group-theoreti model for symmetric interconnection networks," IEEE transactions on Computers, vol. 38, no. 4, pp. 555-566, 1989.
[21] G. Cooperman, L. Finkelstein, and N. Sarawagi, "Applications of cayley graphs," Applied Algebru, Algebraic Algorithms and Error-Correctin Codes: 8th International Conference, AAECC-8 Tokyo, Japan, August 20-24, 1990 Proceedings 8, pp. 367-378, 1991.
[22] M.-C. Heydemann, "Cayley graphs and interconnection networks," Gruph symmetry: algebraic methods and applications, pp. 167-224, 1997.

---

[23] S. Hoory, N. Linial, and A. Wigderson, "Expander graphs and their applications," " Bulletin of the American Mathematical Sociery, vol. 43, no. pp. 439-561, 2006.
[24] G. Zémor, "Hash functions and cayley graphs." Designs, Codes and Cryptography, vol. 4, no. 3,
pp. 381-394, 1994.
[25] F. J. Ruiz, T. Laakkonen, J. Bausch, M. Balog, M. Barekatain, F. J. Heras, A. Novikov, N. Fitzpatrick, B. Pareee-, van de Wetering et al., "Quantum circuit optimization with alphatensor," arXiv preprint arXiv:2402. 14396, 2024.
[26] R. S. Sarkar and B. Adhikari, "Quantum circuit model for discrete-time three-state quantum walks on cayley graphs," Physical Review A, vol. 110, no. I. p. 012617, 2024.
[27] I. Dinur, M.-H. Hsich, T.-C. Lin, and T. Vidick, "Good quantum Idpe codes with linear time decoders," " Proceedings of the 55th annual ACM symposium on theory of computing, pp. 905- 918, 2023.
[28] O. L. Acevedo, J. Roland, and N. J. Cerf, "Exploring scalar quantum walks on cayley graphs." arXiv preprint guant-ph/060924,, 2006.
[29] D. Gromada, "Some examples of quantum graphs." Letters in Mathematical Physics, vol. 112, no. 6, p. 122, 2022.
[30] S. Even and O. Goldreich, "The minimum-length generator sequence problem is np-hard," Journal of Algorithms, vol. 2, no. 3. pp. 311-313, 1981.
[31] E. D. Demaine, S. Eisenstat, and M. Rudoy, "Solving the rubik's cube optimally is np-complete," arXiv preprini arXiv: 06708, 2017.
[32] L. Bulteau, G. Fertin, and I. Rusu, "Pancake flipping is hard," Journal of Computer and System Sciences, vol. 81, no. 8, pp. 1556-1574, 2015.
[33] S. Linton, "Gap: groups, algorithms, programming," ACM Communications in Computer Algebra, vol. 41, no. 3. pp. 108-109, 2007.
[34] M. R. Douglas, "Machine learning tool in theoretical science," Nature Reviews Physics, vol. 4, no. 3, pp. 145-146, 2022.
[35] G. Lample and F. Charton, "Deep learning for symbolic mathematics," " arXiv preprint arXiv:1912.01412. 2019.
[36] A. Davies, P. Veličković, L. Buesing, S. Blackwell, D. Zheng. N. Tomašev, R. Tanburn, P. Battaglia, C. Blundell, A. Juhász et al., "Advancing mathematics by guiding human in- tuition with ai." Nature, vol. 600, no. 7887, pp. 70-74, 2021.
[37] J. Bao, Y.-H. He, E. Hirst, J. Hofscheier, A. Kasprzyk, and S. Majumder, "Polytopes and machine learning," " arXiv preprint wrXiv:2109.0960) 2021.
[38] B. Romera- Romera-Paredes, M. Barekatain, A. Novikov, M. Balog, M. P. Kumar, E. Dupont, F. J. Ruiz, S. Ellenberg, P. Wang, O. Fawzi et al., "Mathematical discoveries from program search with large language models," Nature, vol. 625, no. 7995, pp. 468-475, 2024.
[39] T. Coates, A. Kasprzyk, and S. Veneziale, "Machine learning detects terminal singularities." Advances in Neural Information Processing Systems, vol. 36, 2024.
[40] A. Alfarano, F. Charton, and A. Hayat, "Global Цуарunov functions: a long-standing open problem in mathematics, with symbolic transformers." " arXiv preprint arXiv:2410.08304, 2024.
[41] F. Charton, S. Ellenberg, A. Z. Wagner, and G. Williamson, "Patterboost:: Constructions in mathematics with a little help from ai," arXiv preprint arXiv:2411.0056,, 2024.
[42] A. Shehper, A. M. Medina-Mardones, B. Lewandowski, A. Gruen, P. Kucharski, and S. Gukov, "What makes math problems hard for reinforcement learning: a case study," arXiv preprint arXiv:2408. 15332, 2024.
[43] D. Silver, A. Huang, J. Maddison, A. Guez, L. Sifre, G. Van Den Driessche, J. Schrittwieser, Antonoglou, V. Panneershelvam, M. Lanctot et al., "Mastering the game of go with deep neural networks and tree search," nature, vol. 529, no. 7587, pp. 484-489, 2016.
[44] D. Silver, J. Schrittwieser, K. Simonyan, I. Antonoglou, A. Huang, A. Guez, T. Hubert, I.. Baker, M. Lai, A. Bolton et al., "Mastering the game of Go without human knowledge," " Nature, vol. 550, no. 7676, pp. 354-359, 2017.
12

---

[45] S. McAleer, F. Agostinelli, A. Shmakov, and P. Baldi, "Solving the rubik's cube with approximate policy iteration," International Conference on Learning Representations, 2019. [Online]. Available:
[46] K. Takano, "Self-Supervision All You Need for Solving Rubik's Cube," Transactions on Machine Learning Research, 2023.
[47] B. Perozzi, R. Al-Rfou, and S. Skiena, "Deepwalk: Online learning of social representations," Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining, pp. 701-710, 2014.
[48] A. Grover and J. Leskovee, "node2vec: Scalable feature learning for networks." Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining, pp-
855-864, 2016.
[49] R. Swita and Z. Suszyáski. "Solving Full Nx N Rubik's ' Supercube Using Genetic Algo- rithm," International Journal of Computer Games Technology, vol. 2023, no. 1, p. 2445335, 2023.
[50] R. Holbrook, W. Reade, and A. Howard, "Santa 2023 the polytope permutation puzzle," http:///ggg...ommoommpottonaaaaa 2023 2023, kaggle.
[51] S. Hirata, "Probabilistic estimates of the diameters of the Rubik's Cube groups." arXiv preprint arXiv:2404.07337, 2024.
[52] L. Bulteau, G. Fertin, and Rusu. "Pancake flipping is hard," Journal of Computer and System Sciences, vol. 81, no. 8, pp. 1556-1574, 2015. [Online]. Available:
[53] S. S. Kuppili and B. Chitturi, "An upper bound for sorting in with LRE," CoRR, vol. abs/2002.07344 2020. [Online]. Available: https://arxiv..or//////000222220
[54] Y. Chu and R. Hough, "Solution of the 15 puzzle problem." " 2019. [Online]. Available: https://arxiv.or//abee wttp.o////bbb//000000000000 1908.07106
[55] J. Mulholland, "Permutation puzzles: a mathematical perspective," Departement Of mathematics Simon fraser University, 2016.
[56] N. Alon, I. Benjamini, E. Lubetzky, and S. Sodin, "Non-backtrackingg random walks mix faster," Communications in Contemporary Mathematics, vol. 9, no. 04, pp. 585-603, 2007.
[57] J. Hale, C. Dyer, A. Kuncoro, and J. Brennan, "Finding syntax in human encephalography with beam search," Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers), pp. 2727-2736, 2018
[58] L. Huang, H. Zhang, D. Deng, Zhao, K. Liu, D. A. Hendrix, and D. H. Mathews, "Linear- fold: linear-time approximate rna folding by 5' 1o-3'dynamic programming and beam search," Bioinformatics, vol. 35, no. 14, pp. 1295-1304, 2019.
[59] H. Scheidl, S. Fiel, and R. Sablatnig, "Word beam search: A connectionist temporal classification decoding algorithm," 2018 16th International conference on frontiiers in handwriting recognition (ICFHR), pp. 253-258, 2018.
[60] M. Freitag and Y. Al-Onaizan, "Beam search strategies for neural machine translation," Pro- ceedings of the First Workshop on Neural Machine Translation, pp. 56-60, Aug. 2017.
[61] R. Pryzant, Iter, Li, T. Lee, C. Zhu, and M. Zeng. "Automatic prompt optimization with" gradient descent" and beam search," arXiv preprint arXiv:2305.0334: 2023.
[62] M. Musolesi, "Creative beam search: Lim-as-a-judge for improving response generation," Proc. of the 15th International Conference on Computational Creativity (ICCC'24), 2024.
[63] T. Rokicki, H. Kociemba, M. Davidson, and J. Dethridge, "The diameter of the rubik's cube group is twenty." siam REVIEW, vol. 56, no. 4, pp. 645-670, 2014.
13

---

A NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: The abstract reflects the scope and all the main contributions of the paper, which are then directly listed in the introduction.
2. Limitations
Question: Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification: The limitations of the proposed approach are discussed in Section 4.4
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
Answer: [NA]
Justification: The paper reports research based on empirical experimental studies. It does not include any theoretical result.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: The paper provides all the details required to reproduce the reported results, including the developed software's 's source code and the used verification datasets.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: The developed software's source code and the used verification datasets are provided.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The experimental details are provided in the form of source code, verification datasets, neural networks weights and thechnical appendix.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Most of the experiments were performed using the same standardized reference datasets as previous researchers, making our results directly comparable to the current state the art. Figure directly demonstrates the error bars, while Figure 2 omits them to enhance readability of the small details.
8. Experiments compute resources
14

---

Question: For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed reproduce the experiments?
Answer: [Yes]
Justification: The paper includes all the information on computer resources required to reproduce the experiments.
9. Code of ethics
Question: Does the research conducted the paper conform, in every respect, with the NeurlPS Code of Ethics stttps://eeurips: httpa//www.....caaaaa////cssssaa
Answer: [Yes]
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [NA]
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: The authors of the original models and datasets used the research are correctly cited.
13. New assets
Question: Are new assets introduced in the paper well documented and the documentation provided alongside the assets?
Answer: [Yes]
Justification: The provided code and datasets are accompanied by sufficient documentation.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is important, original, or non-standard component of the core methods this research? Note that the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality the research, declaration is not required.
Answer: [NA]
15

---

B Appendix: Methods
B.1
Source code
The original source code is attached the paper as Supplementary Material, The last version can be found on GitHub: httpat/tt.trreee//to...oooooooaa
B.2 Cayley graphs and Rubik's cubes
Moves of Rubik's cube can be described by permutations (e.g., Chapter 5 55 or Kaggle notebook "Visualize allowed moves Taking all the positions nodes and connecting them by edges, which differ by single moves, one obtains a Cayley-type graph for Rubik's 's cube. Solving the puzzle is equivalent to finding a path the graph between nodes representing the Rubik's cube's scramble initial and solved state.
B.3 Random walks and train set generation
The training set generated by scrambling (i.e., applying random moves) the selected solved state and creating set of pairs (v, k), where k is number of scrambles, and is vector describing the node obtained after lo steps. In other words, we consider random walks on the graph. The main parameters are Kaax and K, where Kmar is maximal number of scrambles (length of random walk trajectory), while K Kmaz a number of nodes to generate.
In the current research, we used so-called non-backtracking random walks [56] that forbid scrambling the state the previous step. A found in trainer.py in the code attached to this paper.
implementation of train set generation can be
Current research does not investigate the influence of Kmar on the solver's performance. We used K mazz= 26 for solvers targeted on 3x3x3 cubes, Kmaz 45 for 4x4x4 cubes, and Kmar 65
for 5x5x5 cubes.
B.4 Neural Network and Training procedure
In this study, we used ResMLP, generalized form of multilayer perceptrons as described in 3 46 Details of the architecture can be found in Figure The PyTorch implementation ResMLP is available in model.py in the code attached to this paper.
The training procedure was performed using the Adam optimizer with fixed learning rate of 0.001 and mean squared еттоr as the loss function. A new dataset of 1M examples was generated before each training epoch. All models were pre- pre-trained and remained unchanged during puzzle-solving. Training was conducted using 32-bit floating point precision, while inference used 16-bit floating point numbers to enhance computational efficiency. The PyTorch implementation of the training procedure is available in Irainer.py in the code attached to this paper.
B.5
Beam-search
Beam search is a simple but effective search procedure used for various optimization tasks [57.
well improve outputs of the modern transformer-based language It has been used in EfficientCube [46) and by many participants the Kaggle We implemented a modified version of traditional beam search, which uses hash functions to remove duplicates, reducing the computation complexity of the pathfinder. Finally, in all the experiments, the scramble was considered unsolved if the path the solved state was not found in 200 beam search steps. Additionally, the algorithm stops if the beam vector contains only already visited graph nodes. Py ToToooo-optimizee implementation of the beam search can be found in searcherpy in the code attached to this paper.
58
59
models 60
Challenge (5)
16

---

B.6 Experiments design
All the experiments were conducted using software attached to this paper. The experiments targeting analysis of trainset size's influence the solver's performance included solving 20 scrambles of both 3x3x3 and 4x4x4 Rubik's cubes using different models as beam search heuristics, For this experiment, we prepared 20 models, whose parameters demonstrated in the first 20 rows of Table 2 Each model was trained during 16384 epochs. The snapshots of the model parameters were saved after 16, 64, 256, 1024, 4096, and 16384 epochs. Then, each model snapshot was integrated as a heuristic into beam search with W 2 which was used to solve the first 20 scrambles from the dataset. DeepCubeA dataset was used for 3x3x3 Rubik's cube, and the 2023 Kaggle Santa Challenge [50] dataset was used for 4x4x4 puzzle. The results achieved by each solver configuration on the corresponding dataset were averaged and analyzed as experimental results. Scrambles unresolved due to low beam width were excluded from the demonstration in Figure 2 to simplify the overall plot analysis.
Table 2: The parameters of neural networks used in current research
No.
Cube
Metric
Layers
N1
N₂
N,
P
Result No.
3x3x3
QTM
3050
0
0
1M
3x3x3
QTM
850
850
IM
3
3x3x3
QTM
800
340
IM
3x3x3
QTM
10
430
300
IM
5
3x3x3
QTM
12196
0
0
4M
3x3x3
QTM
1841
1841
4M
7 3x3x3
QTM
2000
697
4M
8
3x3x3
QTM
700
643
4M
10, 12,
9
4x4x4
UQTM
750
750
1M
10
4x4x4
UQTM
4
530
470
IM
11
4x4x4
UQTM
720
300
IM
12
4x4x4
UQTM
10
500
266
1M
13
4x4x4
UQTM
1730
1730
4M
14
4x4x4
UQTM
1180
1024
4M
15
4x4x4
UQTM
2000
628
4M
16
4x4x4
UQTM
10
1010
592
4M
18, 19
17
4x4x4
UQTM
2000
1126
8M
18
4x4x4
UQTM
10
1540
850
8M
19
4x4x4
UQTM
5000
1369
16M
20
4x4x4
UQTM
10
5000
1062
16M
2x2x2
QTM
1024
0.15M
22
2x2x2
QTM
10
430
300
0.92M
23
3x3x3
QTM
1024
0.34M
24
3x3x3
UQTM
10
700
643
4M
15
25
5x5x5
UQTM
10
1008
560
4M
The first experiment's results are demonstrated in Figure 2h. Single layer MI.Ps for 4x4x4 Rubik's cube are not presented Table as during preliminary research solvers equipped with this type of model did not manage to solve any scramble before reaching the 200 steps limit.
During the second experiment, we used only 10 layer models with size 4M (models No.8 and 16 from Table 2g The first experiment's results did not show significant effect of increasing T (train size) from 4B to 16B. Thus, the second experiment used finer granularity with 4B, 8B, and 16B train sizes to select the appropriate size more precisely. Each snapshot of the models trained with the mentioned above train sets was integrated into solvers with W of 212 224 216 218 220 222 and 224 Then, these solvers were used to unscramble the first 20 puzzles from the same dataset used in the first experiment. The results achieved by each solver configuration on the corresponding dataset were averaged. Unsolved scrambles were excluded from consideration in this experiment.
17

---

Table 3: Average solution length depending from trainset size T and beam width W for tested with puzzle win probability above 0.5.
4B
8B
16B
Win prob.
Avg. sol.
Win prob.
Avg. sol.
Win prob.
Avg. sol.
3x3x3 Rubik's solver results with win probability above 0.5
2
1.00
22.15
1.00
22.05
1.00
22.3
214
1.00
21.55
1.00
21.55
1.00
21.6
216
1.00
21.25
1.00
21.15
1.00
21.2
2
1.00
21.15
1.00
20.95
1.00
21
220
1.00
20.75
1.00
20.85
1.00
20.9
222
1.00
20.65
1.00
20.65
1.00
20.7
221
1.00
20.65
1.00
20.65
1.00
20.65
Average solution
21.16
21.12
21.19
4x4x4 Rubik's solver results with win probability above 0.5
2
0.80
61.88
0.55
60.18
0,85
64.12
218
1.00
58.1
0.85
56.7
0.95
58.47
220
1.00
54.7
1.00
55.3
1.00
54.7
222
1.00
51.9
1.00
52.8
1.00
52.3
221
1.00
50.4
1.00
50.6
1.00
49.6
Average solution
55.4
55.11
55.84
The results of the second experiment are demonstrated in Figure 2p. A deeper analysis of the experimental results shows that we consider only values that give puzzle winning probability above 50%, the agent with the model trained on 8B states has slightly better average solution length than the competitors (Table Thus, for the rest the experiments, we used the 8B train set as a compromise between solver performance and training time.
The third experiment analyzed the influence of the number of agents A the solver's efficiency, We used models No.8, 16, and 25 for this experiment from Table We trained each of these models multiple times during 8192 epochs. Then, each model was integrated into a dedicated agent. Due to computation limitations, we run only two agents in parallel at the same time, assuming that with more available GPU instances, will be possible to compute all of them simultaneously. Finally, total number of pretrained agents for 3x3x3 was 26, 4x4x4 - 29, and 5x5x5 - 69. As in previous experiments, the agents aimed solve 3x3x3 cubes were tested on the scrambles DeepCube dataset, while the rest were verified using the 2023 Kaggle Santa Challenge dataset. Due to the large size of the DeepCubeA dataset, in the third experiment, we used a subset of 69 3x3x3 scrambles, which were considered most difficult during preliminary research. The results of the experiment shown in Figure
Due to historical reasons, scramble order and corresponding IDs demonstrated on Figures and are different from the original ones in the 2023 Kaggle Santa Challenge dataset. This difference does not affect research results in any way, but may be confusing, e.g., in case one compares our best results with their own. Thus, for reproducibility reasons, we added paper/solver--eee puper/solver-scrumblee and rmper/figure-scrmbble folders to the Supplementary Materials, which contain generators and scrambles used in each specific experiment and the corresponding README file.
The authors of [3] along with the well-known DeepCubeA dataset, were using DeepCubeA, set containing the scrambles that are furthest away from the goal state, assuming these scrambles are more challenging to solve. At the same time, original DeepCubeA solutions were robustly and optimally solving them. During the current research, we found another subset of the DeepCubeA dataset containing 16 scrambles, which were not solved optimally during the experimental studies. believe that a significantly rising number of agents will lead to finding solutions to them. However, the first element of this subset (scramble No. from original DeepCubeA) was never optimally solved in any of our attempts, even during preliminary research and experiments not covered by this paper. We believe that analyzing the scrambles in this subset will help understand
18

---

why they are so hard to solve compared to the rest of the DeepCubeA data. Finally, this understanding will lead the development of new, more efficient ML methods [ Thus, we decided to publish these 16 scrambles as a self-contained dataset accompanied by this paper.
The experimental results listed in Table T were achieved by solving all the scrambles from the corresponding dataset defined in the third column of Table uusing the proposed solver. The key solver parameters are listed in the fourth column. The last column of demonstratts for which results from Table Mach model was used.
The next experiment conducted in the current research aimed to compare computational efficiency with the EfficientCube [46] (a state-of-the art solution claimed by its author to have better efficiency than DeepCubeA). For the fairness of comparison, we used a dedicated server equipped with two Intel Xeon Gold 6442Y 24-core processors running at 2600 Mhz, 256 GB DDR5 RAM, 512 GB SSD, and GPUs NVIDIA H100 80GB. The server was running Ubuntu Linux 24.04.2 LTS, CUDA 12.4. The latest version (March 10th, 2024) of the EfficientCube was downloaded from the official GitHub repository E
and configured according to the author's instructions to reproduce the results from [46]. Our solution was installed on the same server and configured with the beam width providing similar solution length (see results No.9 and 10 in Table D.. First, we sequentially trained a model for each solution and measured the time required for these procedures. Then, we tested both solvers on all the scrambles from the DeepCubeA dataset. Both solutions were configured to use 32-bit single-precision floats for training and 16- half-precision floats for inference. We recorded the solving time for each scramble and then averaged among the whole dataset. Finally, we compared training time and average solving time between EfficientCube and our solution. During this experiment, only one solution was running on the server at the same time.
B.7 Analysis of the solutions provided by neural networks trained on 524B examples
The experiment aimed to analyze the benefits and drawbacks of using extremely large trainsets generated by random walks in solving Rubik's ' Cube. Two 10-layer neural networks were trained for this purpose. The parameters of these neural networks training procedure was equal to the one described in Section B..4 The training was performed during 524288 epochs, resulting in 524B examples. The training was performed on a server equipped with two NVIDIA H100 GPUs Each GPU was used to train only one network. The overall training procedure took approximately 7 days and 17.5 hours. Then each network was used to solve 43 4x4x4 scrambles from the 2023 Santa Challenge Dataset using a single agent with a beam width of 224 Additionally, two solvers were equipped with snapshots of the trained networks stored after 8192
provided in line 16 of Table 2 The
training epochs. The detailed comparison of the experimental results is provided in Figure 4 Figure 4 uses the following color code. Blue color solution lengths of the best results, which were provided for the corresponding scramble by one of the neural networks during the experiment. The green color indicates that at least one of the neural networks trained with 524B examples produced shorter results than both versions trained with 8B examples. The red color indicates a scramble for which at least one of the neural networks trained with 8B examples produced shorter results than both versions trained with 524B examples. Yellow color scrambles for which the shortest solutions provided by neural networks trained with 8B and 524B were the same.
Scramble ID 21
25 26 27
40
Neural metwoork (upper line Mitlowwr line 524H)
49
49
47
45
46
48 55 50 50 (5114) 149 48 49 H8 48
55
52
49
50
43
47
45
47
46
50
50
48
40
53
(4
[22 48 48) (50 48 (49 [47 [50 [49 448 54 44
48
49
49
50
50
49
49
Neural netwookk fupyer line
lower
51
49
47
45
50
43
51
46
51
49
48
45
50
54
52
47
47 46 48 52 46 50 53 47 48 47 50 50 54 52
49
49 52
52
49
46
58
52
53
13
15
18 50 (5] 50 48
49 55 50 [17 550 18 50
13
16
13
Hear resucts over wither exeperimennt (newaal wetworke traiind wirh 888 essoppres)
4
47
43
45
46
46
44 H8 45 H6 46 46 48 49
47
50 17 47
Figure 4: The solution lengths found by the solvers equipped with neural networks trained using 8B examples and their versions extensively trained with 524B examples compared to the best solutions found using networks trained with 8B examples (in all other experiments performed during research).
A possible explanation that the number of optimal solution paths for such cubes is lower than average or equal to one, making these paths more difficult to find.
https: /gi thub. com/kyyotakaaoo///ooooooaoaoaoao httpaa///effffifffeefeaeeee
19

---

The first of two networks managed to solve all the scrambles, both trained using 8B and 524B samples. Sixteen scrambles were solved with the same length. In nine cases, network snapshot captured after 8B samples provided shorter solutions, and in 18 cases, the network trained on 524B samples provided shorter solutions. As result, the average solution length decreased from 49.3 to 48.56 as a result of very long training.
The results demonstrated by the solvers based on the second neural network are more controversial. The version trained using 8B samples managed to solve scrambles No. 10, and No. 29, but failed to solve the scramble No. Conversely, the version trained using 524B samples solved the scramble 37.37, but failed to solve scrambles No. 10 and No. 29, providing worse win probability rate. The solver, equipped with the network trained on 524B samples, provided better average solution length, but only if unsolved scrambles are entirely omitted. Moreover, the difference between versions trained using 8B and 524B samples much less than the one observed with the first network. Direct comparisons of different scrambles show that in 9 cases, network snapshots captured after 8B samples provided shorter solutions. 16 cases, networks trained on 524B samples provided shorter solutions, and in the remaining 18 cases, the solution length was the same.
The comparison with the shortest solutions found during the rest of the research showed that networks trained with 524B samples did not outperform the best results demonstrated by the networks trained using 8B samples (Figure 4 for any of the scrambles. In 22 out of 43 cases, one of the solvers equipped with networks trained during the discussed experiment provided solutions with the same length as the shortest ones previously found for the corresponding scrambles. In 8 of these cases, the shortest solution was provided by both versions trained with 8B and 524B samples, and in 4 more cases, the 8B version provided the shortest solution, while the further trained neural network failed (Figure
Thus, even long training with 524B samples slightly improved average solution length, but the advances achieved are incomparable to the additional computational resources required. Another experiment provided in this paper demonstrates that 5-10 agents trained using 8B samples (40-80B in total) achieve a smaller average solution length than any of the two networks we trained on 524B samples. Moreover, comparing these networks with their snapshots captured after 8192 training epochs demonstrated that they not only provide new, shorter solutions but also degrade for other scrambles and even fully "forget" how to solve some of them.
was also revealed that extensive training on a large number of examples leads to more computation- ally extensive inference. The solvers equipped with networks trained with 524B samples were not able to solve any scrambles if half-precision inference was used. Thus, we were forced to compute the inference for these networks with single precision, which required more time on the same hardware. Contrarily, the versions trained with 8B samples were fully compatible with the "half precision" trick, which is used to boost the solver's performance.
B.8 Method generalization
To demonstrate the generality of the proposed method beyond Rubik's cubes, we tested it on a diverse set of permutation groups from the 2023 Kaggle Santa Challenge (excluding cubes larger than 6x6x6), as well as additional groups such as Pancake sorting (52), LRX (53), and the 15-puzzle with periodic boundaries [54]. Each model was trained with fixed neural network parameters (N, 1024, N₂ = 256, N, = 1) for 16 and 128 epochs. The solver used beam width of W = 22 The results of this experiment
summarized in Table The values provided in parentheses in Table 4 indicate the standard error of the mean. From the perspective of sampling random states of a given group, this allows statistically significant comparisons between the performance of different solvers.
The only varying parameter was Kmax selected based on known 633 or estimated [51] graph diameters. In general practice, K can be chosen automatically by scanning several candidate values. We performed four independent training and inference runs for each group, confirming robustness for groups consistently solved in all runs (marked as 100% in Table 4)
Initial states for additional groups were generated by performing 10,000 random moves from the solved state, followed by an optional random move with 50% probability to ensure parity variability. The total test set included 296 puzzles from the Santa challenge groups and 200 puzzles from additional groups (10 per group).
20

---

The comparison of the results achieved using model trained for 16 and 128 epochs (marked in Table with their trainset size T 16M and 128M, respectively) shows that in most of the cases, larger I 128M trainset provides shorter solution length and as consequence faster scramble solving time. At the same time, is surprising that models trained using only 16M examples robustly solve all the test cases for 28 of 39 investigated groups. Moreover, the Globe 6x8 puzzle model trained for 16 epochs was more successful than the one trained for 128.
We evaluated the method by comparing the average solution length to the best Kaggle Santa solutions. The proposed approach provided shorter average solutions for 12 out of 14 non-cube 2023 Kaggle Santa Challenge groups, indicating strong generalization. Failures occurred when the beam search stagnated, detected by repeating vertex sets across consecutive search steps. Such stagnation occurred for some extremely large groups, indicating that while the method is scalable, each group's ' practical solvability limit varies, as evident from Table 4 It is also seen that large Rubik's 's cubes are harder than many other puzzles represented with groups of comparable or larger size. A model trained with 16M examples did not solve any of the scrambles used during the experimental studies, while the model trained for 128 epochs solved only 22% of them. The previous experiments demonstrated that a larger model trained with 8192M examples can robustly solve 100% of scramble, At the same time, the found solution won't won't be the shortest one. Using up 69 agents was required to beat all the best 2023 Kaggle Santa Challenge. Thus, the fact that in the last experiment, our method did not solve any scrambles of 6x6x6 Rubik's ' cube does not mean that it is not suitable for this task. It just may require a larger size of the model and beam width. For example, in one of our preliminary experiments, a single agent equipped with neural network trained on 8 million parameters, billion examples, and a beam width of 16 million managed to solve out of 6 6x6x6 Rubik's Cube scrambles from the Santa Challenge dataset. The solution lengths were more than 200, but they were found using a smaller trainset, the same beam width, and only twice the size of the models used to achieve the result demonstrated in Table I for the 5x5x5 Rubik's cube.
The scripts for reproducing the results presented in Table 4 along with the exact values of the parameter Kmax used for each group, are provided in the supplementary materials (Iraintest-tab4- rnd.sh and traintest traintest-tab4-see shnta.......
Additionally, by suggestion of one of the reviewers on the rebuttal stage, we extended our experiments to include classical 15-puzzle instances (in addition to the periodic boundary version reported in Table in the originally submitted version of the paper). We tested our method on standard 4x4 (15- puzzle) and 5x5 (24-puzzle) sliding puzzles, comparing against both classical PDB-based solvers and learning-based approaches.
For the 4x4 puzzle, our method achieves 100% optimality with an average solution length of 52.02 moves, matching the performance of PDB-based optimal solvers and slightly outperforming DeepCubeA (99% optimality). Our solving time of 3.5 seconds is faster than DeepCubeA's 10.3 seconds, though naturally slower than PDB's ' near-instantancous 0.002 seconds. Crucially, our training time is only 40 seconds compared DeepCubeA's 36 hours a dramatic reduction in computational requirements.
For the more challenging 5x5 puzzle, our approach solves instances in 11 seconds with 88% optimality, compared to DeepCubeA's 19.3 seconds with 97% optimality. Interestingly, while PDB guarantees optimal solutions, it requires 4239 seconds (over an hour) solve 5x5 our learned heuristic provides a practical speed-optimality tradeoff for larger instances. EfficientCube was unable solve the 5x5 puzzle in our tests. The original paper also does not report that this solution can solve the 24-puzzle.
that
These results demonstrate that method offers a compelling balance: training times measured in seconds rather than days, competitive solution quality, and practical solving speeds that scale better than exact algorithms for larger puzzles. While domain-specific solvers like PDB excel in minor instances where precomputation is feasible, our approach offers a more general and scalable alternative that requires minimal domain knowledge.
21

---

Table 4: Generalization performance across different puzzles.
Group
Size
Training, min
Solving, min
Avg. solition len.
Solved, %
16M
128M
16M
128M
16M
128M
16M
128M
Cube 2x2x2
106
0.1
0.5
0.01
0.02
10.5(3)
10.5(3)
100
100
Cube 3x3x3
4 X 10
0.1
0.8
0.18
0.17
21.5(1)
20.5(1)
100
100
Cube 4x4x4
7 x 104s
0.2
1.5
1.44
1.24
77(2)
65(1)
90
94
Cube 5x5x5
3 1074
0.2
1.5
7.14
126(2)
22
Cube 6x6x6
2 x 10116
0.4
2.8
0
Wreath 6x6
x 106
0.1
0.4
0.00
0.00
8.5(4)
8.5(4)
100
100
Wreath 7x7
10
0.1
0.4
0.00
0.00
9.2(3)
9.2(3)
100
100
Wreath 12x12
1 X 1021
0.1
0.5
0.01
0.01
18.3(7)
18.3(7)
100
100
Wreath 21x21
4 X 1047
0.1
0.5
0.05
0.05
35(2)
35(2)
100
100
Wreath 33x33
6 1088
0.1
0.6
0.10
0.11
61(1)
61.5(5)
100
100
Globe 1x8
2 1035
0.1
0.8
0.46
0.43
43(2)
44(2)
100
100
Globe 1x16
1 X 1089
0.1
1.1
2.09
1.98
83.3(7)
81(3)
100
100
Globe 2x6
7 X 1021
0.1
0.6
0.13
0.12
21(1)
21(1)
100
100
Globe 3x4
4 X 1026
0.1
0.7
0.20
0.18
29(2)
27(1)
100
100
Globe 6x4
7 X 1040
0.1
0.7
0.48
0.43
44.0(7)
42(1)
100
100
Globe 6x8
X 10107
0.2
1.8
6.58
7.02
183(16)
173(15)
100
75
Globe 60
1 X 10
0.2
1.8
6.94
143
100
Globe 3x33
X 10448
0.8
6.6
0
Globe 8x25
x 10633
Puzzle 8
2 105
0.1
0.5
0.00
0.00
12.8(5)
12.8(5)
100
100
Puzzle
1 x 10
0.1
0.6
0.05
0.05
31.0(6)
31.0(6)
100
100
Puzzle 24
8 1024
0.1
0.9
0.17
0.17
64.6(8)
64.2(8)
100
100
Puzzle 35
2 X 1041
0.2
1.2
0.56
0.45
115(2)
113(2)
70
100
Puzzle 48
3 X 1082
0.2
1.8
1.79
2.07
181
181
10
Puzzle 63
9 1088
0.3
2.5
0
LRX 10
4 x 106
0.1
0.5
0.01
0.01
28(1)
28(1)
100
100
LRX 15
1 1 12
0.1
0.6
0.07
0.07
66(3)
66(3)
100
100
LRX 20
2 1018
0.1
0.8
0.18
0.19
135(3)
135(3)
100
100
LRX 25
2 x 1025
0.1
1.0
0.42
0.42
216(7)
217(7)
100
100
LRX 30
3 x 1032
0.1
1.1
0.52
0.52
386(16)
329(15)
50
50
Pancake 10
4 x 106
0.1
0.5
0.01
0.01
8.6(3)
8.6(3)
100
100
Pancake 15
1 10
0.1
0.5
0.06
0.06
13.9(3)
13,9()
100
100
Pancake 20
2 x 10
0.1
0.6
0.14
0.14
18.8(3)
18.8(3)
100
100
Pancake 25
2 1025
0.1
0.7
0.38
0.38
24.0(3)
24.0(3)
100
100
Pancake 30
3 x 1032
0.1
0.8
0.58
0.58
28.4(8)
28.2(7)
100
100
Pancake 35
1 x 1040
0.1
1.0
1.26
1.24
34.5(3)
34.2(2)
100
100
Pancake 40
8 1047
0.1
1.1
1.22
1.20
39.4(4)
38.9(3)
100
100
Pancake 45
3 x 1036
0.2
1.2
3.25
2.99
48(1)
44.1(4)
100
100
Pancake 55
3 x 73
0.2
1.4
6.70
3.49
57.2(8)
50.0(3)
50
100
22

---

B.9 Computational resources
All of the experiments reported in the paper were performed on dedicated server manufactured by Graviton. This server is equipped with two Intel Xeon Gold 6442Y 24-core processors running at 2600 Mhz, 256 GB DDR5 RAM, 512 GB SSD, and two GPUs NVIDIA H100 80GB. The server was running Ubuntu Linux 24.04.2 LTS, CUDA 12.4. None of the other applications except the ones used for this research were executed during experimental studies. The server was simultaneously running two agents, each using dedicated GPU. In cases when more agents were needed, they were executed sequentially by pairs. The total computation time used to perform the research, including all the published experiments, took approximately two months of continuous computing with 100% GPU usage, During our preliminary research, we also used several virtual machines provided by Kaggle g
"ntpss/wwww.kagle.com
23


Reviews:
[{"review_id": "NvIznYfZCR", "reviewer": "Reviewer_D1fw", "summary": "This paper shows that coupling multi-agent neural heuristics trained on random-walk data with beam search can solve the Rubik’s Cube and related combinatorial puzzles efficiently. The experimental evaluation is extensive and comprehensive, offering a valuable case study on how an ensemble of learned heuristics can be integrated with a classical graph-search procedure. The results markedly outperform recent baselines—most notably DeepCubeA and EfficientCube—in both solution quality and speed, underscoring the strength of the proposed approach.", "questions": "I believe I now have a solid grasp of the manuscript and therefore have no substantive questions. Nevertheless, I noticed several places that appear to contain typographical or labeling errors. Please verify the items below.\n\n- Lines 217–218.\nOriginal text: “The values provided in parentheses in Table 1 indicate the standard error of the mean.”\nThe figures in parentheses do not look like standard errors.\n\n- Figure 1 caption.\nPanels (b) and (c) appear to be swapped.\n\n- Line 122. Figure 1c → Figure 1.\n\n- Line 187. If it is seen … → As is seen …\n\n- Line 205. \n“Superiority → superiority.”", "limitations": "Section 4.4 provides an adequate explanation.", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n- Straightforward yet powerful approach.\nThe method is conceptually simple—train multiple lightweight MLP heuristics on random-walk data and fuse them via beam search—yet it proves highly effective in practice.\n\n- Extensive, comprehensive experiments.\n  The authors run a broad battery of tests across the standard 3×3×3 Rubik’s Cube and several harder combinatorial puzzles, making the paper a valuable case study for researchers exploring hybrid machine-learning + graph-search techniques.\n\n- Impressive empirical performance.\n  Compared with recent baselines such as DeepCubeA and EfficientCube, the proposed system uses a smaller network, requires less training time, searches faster, and still finds higher-quality solutions, albeit at the cost of running a multi-agent (parallel) beam search.\n\nWeaknesses\n- Limited novelty in ensemble idea.\nIt is not surprising that ensembling several independently trained random-walk models improves accuracy; this strategy is well-known in the literature. Nonetheless, the authors’ quantitative analysis of ensemble size vs solution quality offers useful insight, so the lack of conceptual novelty is a relatively minor drawback.\n\n- Page 2 footnote is quite long; consider integrating its content into the main text to improve readability.", "was_revised": true, "final_justification": "The authors have addressed my concerns. The first weakness I noted was minor, and their rebuttal is convincing. The second was a formatting issue that they have agreed to fix.\n\nMy other comments are limited to typos, which I trust will be corrected.\n\nTherefore, I will maintain my original rating.", "rebuttal": "1. Limited novelty in ensemble idea. It is not surprising that ensembling several independently trained random-walk models improves accuracy; this strategy is well-known in the literature. Nonetheless, the authors’ quantitative analysis of ensemble size vs solution quality offers useful insight, so the lack of conceptual novelty is a relatively minor drawback.\n\n**Reply:** We agree with the reviewer that the ensemble concept is well-known. At the same time, in the discussed task, it was one of the key solutions that significantly improved the solver's results and surpassed all previous art ML solutions in terms of their length on Rubik's cube problems up to 5x5x5. Thus, we decided to stress the reader's attention on that fact. An interesting observation was also made that the ensembles that achieved the shortest results on the whole dataset included specialized agents, whose average solution length was not the best. At the same time, their combination resulted in solving each of the 5x5x5 scrambles in the competition dataset better than the best results achieved during the Kaggle Challenge. Finally, it is worth noting that the ensemble idea is often implemented as an ensemble of neural networks. We attempted this approach to predict the distance to the goal more accurately, but did not achieve any superior results. At the same time, an ensemble of solvers enabled us to outperform our competitors. Thus, we believe that the details of the ensemble idea implementation applied to our puzzle-solving problem are a valuable contribution that will help other researchers.\n\n2. Page 2 footnote is quite long; consider integrating its content into the main text to improve readability.\n\n**Reply**: We thank the reviewer for the valuable suggestions. We will integrate the footnote into the main text in the camera-ready version of the paper.\n\n3. Lines 217–218. Original text: “The values provided in parentheses in Table 1 indicate the standard error of the mean.” The figures in parentheses do not look like standard errors.\n    Figure 1 caption. Panels (b) and (c) appear to be swapped.\n    Line 122. Figure 1c → Figure 1.\n    Line 187. If it is seen … → As is seen\n    Line 205. “Superiority → superiority.”\n\n**Reply**:  We thank the reviewer for their assistance in helping us improve our paper. We will fix the listed typos and formatting issues in the camera-ready version of the paper."}, {"review_id": "N9FqyumVK5", "reviewer": "Reviewer_yeSg", "summary": "This paper proposes a novel ML-based approach for solving pathfinding problems on large Cayley graphs, with a focus on Rubik’s Cubes up to 5x5x5. It uses a ResMLP network trained to estimate “diffusion distance” from the solved state via random walks. This heuristic guides a beam search algorithm. A multi-agent system of independently trained models is used, with the best solution among them selected. The method achieves state-of-the-art results on 3x3x3–5x5x5 cubes and shows generality across other permutation puzzles.", "questions": "1. What is the root cause of this counterintuitive behavior, \"performance stagnation\" anomaly, where more training data leads to worse solver performance? Does this imply that for a certain scale, the \"diffusion distance\" estimation, based on random walks, becomes a less effective or even misleading heuristic for finding shortest paths, perhaps due to increasing noise or a fundamental disconnect from God's number in denser parts of the state space? Instead of random walks, it may be worth exploring alternative problem generators that more closely approximate optimal paths, as used in prior work [1, 2], to see if they provide better training signals and improve solver performance.\n\n\n**References:**\n\n[1] Büchner, C., Ferber, P., Seipp, J., & Helmert, M. (2022). *A Comparison of Abstraction Heuristics for Rubik's Cube*. ICAPS Workshop.\n\n[2] Muppasani, B., Pallagani, V., Srivastava, B., & Agostinelli, F. (2024). *Comparing Rubik’s Cube Solvability in Domain-Independent Planners*.", "limitations": "1. The authors explicitly state that their paper reports on \"purely empirical research\" . This means their findings are based on experimental observations rather than formal mathematical proofs or theoretical derivations.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "**Strengths:**\n1. The proposed solution shows state-of-the-art results and surpasses the aggregated best results from the Kaggle Santa 2023 challenge for 4x4x4 and 5x5x5 Rubik’s Cubes. For the 3x3x3 cube, it achieves an optimality rate exceeding 98%, matching task-specific solvers and significantly outperforming previous ML solutions like DeepCubeA (60.3%) and EfficientCube (69.6%).\n2. The solution is approximately 25.6 times faster in solving 3x3x3 Rubik’s Cubes and requires up to 8.5 times less model training time than the most efficient state-of-the-art competitor like EfficientCube.\n3. The use of multiple agents improves the average solution length. Each agent, trained on a different random walk-generated dataset, approximates the distance differently, and combining their results by selecting the shortest path found provides a more robust solution.\n\n**Weakness/Suggestions:**\n1. The paper reports a surprising result where models trained on a massive dataset (524B examples) failed to solve any 4x4x4 scrambles from the Kaggle Santa 2023 Challenge, while the same models trained on a much smaller dataset (8B examples) performed significantly better. This counter-intuitive performance stagnation is acknowledged but not explained, as the study remains largely empirical. The lack of theoretical analysis leaves open questions about whether overfitting to diffusion distance, noise accumulation, or other factors are responsible. Understanding why more data leads to worse performance is crucial, especially for scaling the method to larger problems.\n2. The neural network is trained to predict \"diffusion distance,\" an estimate based on random walks. While empirically effective, the theoretical connection between this \"diffusion distance\" and the true shortest path length (God's number) is not fully elaborated. The paper notes that beam search \"compensates for any possible incorrectness in the neural network predictions\", but a deeper understanding of why this specific heuristic guides optimal pathfinding so effectively, or why it fails at larger data scales, is not provided.\n3. For large groups, such as the 5x5x5 Rubik's Cube, the Kaggle Santa 2023 Challenge Dataset only includes a small number of examples (e.g., 19 scrambles), which limits the broader generalization of the results.\n4. The use of random walks to generate training data can introduce noisy or suboptimal learning signals, making the diffusion distance heuristic less reliable, especially at greater search depths. This may explain why the method requires a large number of agents to achieve high optimality. The paper itself notes that even the \"worst agents\" contribute uniquely, implying that diversity across independently trained models compensates for weaknesses in individual heuristics. However, with a more efficient problem generator—one that better aligns scramble depth with optimal solution length—fewer agents might be sufficient, potentially improving both training efficiency and convergence.", "was_revised": true, "final_justification": "I will stick to my score. The author's explanation of my concerns regarding the unexplained anomaly (performance stagnation, diffusion distance estimation) is convincing.", "rebuttal": "1. The paper reports a surprising result where models trained on a massive dataset (524B examples) failed to solve any 4x4x4 scrambles from the Kaggle Santa 2023 Challenge, while the same models trained on a much smaller dataset (8B examples) performed significantly better…\n\n**Reply:** We agree with the reviewer that the lack of theoretical proofs and analysis is a key limitation of our paper (we directly state this in Section 4.4 of our paper). The reported example, where models trained on a massive dataset fail to solve any of the scrambles, is explained by the fact that models trained with extremely large training sets start forgetting states around the goal, shifting their distance-to-goal predictions closer to the average distance among all states. Thus, the solver has no chance to find the target value based on such a heuristic. Corresponding clarifications will be added to the camera-ready version of the paper. At the same time, due to the empirical nature of our study, it cannot be guaranteed that this explanation covers all similar cases. It is worth noting that in the submitted paper, this example was used to illustrate the fact that a monotonically decreasing loss function during the training does not guarantee shorter solutions. Nevertheless, we recognize the importance of theoretical statements that accurately explain the observations reported in this paper, and we are currently working on developing them. At the same time, currently they are out of the scope of this research, which was aimed at significantly enhancing results achieved in prior art and demonstrating that ML-based solutions not relying on human knowledge in group theory can successfully solve a large-scale puzzle (e.g., 5x5x5 Rubik's cube) at a high level of optimality.\n\n2. The neural network is trained to predict \"diffusion distance,\" an estimate based on random walks. While empirically effective, the theoretical connection between this \"diffusion distance\" and the true shortest path length (God's number) is not fully elaborated…\n\n**Reply:** We agree with the reviewer that a deeper theoretical connection between \"diffusion distance\" and the true shortest path length (God's number) will help to understand how our solution can be improved or why it fails at larger data scales. The answer to the last reviewer’s comment contains additional clarification on this topic. Also submitting our paper to NeurIPS 2025, we performed several additional experiments on solving a 6x6x6 Rubik's Cube with our approach. A single agent equipped with a neural network trained on 8 million parameters, 1 billion examples, and a beam width of 16 million managed to solve 2 out of 6 scrambles from the Santa Challenge dataset. The solution lengths were more than 200, but they were found using the same beam-width, only twice the size of the models used to solve 5x5x5. Moreover, the amount of training data was even smaller than that used in the experimental studies reported in our paper. Figure 2 and Table 3 demonstrate that for the 4x4x4 cube, the results obtained using the 1B-16B trainset are comparable, which suggests that extremely large trainsets are not required to solve large puzzles. Interestingly, our new result on 6x6x6 does not contradict this assumption. As we have already addressed the previous comment, we are currently actively searching for a solid theoretical basis that will explain our observations and enable us to analytically predict the neural network parameters, training set size, and beam width required to solve large puzzles with an average solution length close to optimal. Meanwhile, this work is far from finished. Still, we believe that our observations, reported in our paper, will be of interest to many researchers working in the field of AI/ML applications in mathematics. We hope that this interest will convert into finding the discussed theoretical basis in a shorter time.\n\n**PS:** While answering this comment, we found a typo in Table 3. $T$ should be 4B, 8B, and 16B instead of 4M, 8M, and 16M. We will fix it in the camera-ready version of the paper.\n\n3. For large groups, such as the 5x5x5 Rubik's Cube, the Kaggle Santa 2023 Challenge Dataset only includes a small number of examples (e.g., 19 scrambles), which limits the broader generalization of the results.\n\n**Reply:** We thank the reviewer for pointing out this concern. We specifically highlighted it in Section 4.4. For the smaller puzzles, such as the 3x3x3 Rubik's Cube, there are optimal algorithmic solvers (like PDB-based), which makes it easy to generate datasets containing optimal ground truth solution lengths of any size. Unfortunately, to the best of our knowledge, there are no optimal solvers available for 4x4x4 and larger cubes. As demonstrated in Table 4 (Appendix A.6), our solution can solve 5x5x5 cubes in a matter of minutes. However, the length of these solutions is far from the shortest one presented in Table 1. As the paper concludes, achieving shorter solutions generally requires increasing model depth, beam width, and the number of agents. The absence of optimal solvers significantly challenges the fair analysis of the proposed method's efficiency. Moreover, most of the published ML solutions were never implemented for the Rubik's Cube larger than 3x3x3. Thus, the 2023 Santa Challenge Dataset was the only one we found, which contained some sort of ground truth (the best solutions among over a thousand teams of ML developers competed to find the shortest puzzle solutions), which was possible to use for a fair assessment of our solution's efficiency.\n\n4. The use of random walks to generate training data can introduce noisy or suboptimal learning signals, making the diffusion distance heuristic less reliable, especially at greater search depths. This may explain why the method requires a large number of agents to achieve high optimality. The paper itself notes that even the \"worst agents\" contribute uniquely, implying that diversity across independently trained models compensates for weaknesses in individual heuristics. However, with a more efficient problem generator—one that better aligns scramble depth with optimal solution length—fewer agents might be sufficient, potentially improving both training efficiency and convergence.\n\n**Reply:** We thank the reviewer for the valuable suggestion. Our team is currently investigating various approaches to trainset generation, aiming to make our random walks \"smarter\" and more efficient for the specific problem. We hope to present a dedicated paper on this topic shortly. At the same time, many possible random walk modifications that improve solver results rely on different human knowledge of the puzzle. At the same time, this paper aims to develop an ML solution that learns to solve specific puzzles based on demonstrated examples, without prior knowledge of the graph representing the puzzles or the laws describing their interconnections. Thus, in this research, we used the simplest version of random walks and demonstrated that, even with relatively small noisy trainsets, it is possible to \"teach\" our solution how to solve puzzles represented by very large graphs.\n\n5. What is the root cause of this counterintuitive behavior, \"performance stagnation\" anomaly, where more training data leads to worse solver performance? Does this imply that for a certain scale, the \"diffusion distance\" estimation, based on random walks, becomes a less effective or even misleading heuristic for finding shortest paths, perhaps due to increasing noise or a fundamental disconnect from God's number in denser parts of the state space? Instead of random walks, it may be worth exploring alternative problem generators that more closely approximate optimal paths, as used in prior work [1, 2], to see if they provide better training signals and improve solver performance.\n\n**Reply:** We acknowledge that the root cause of this performance stagnation anomaly remains an open question that we are actively investigating. Regarding the effectiveness of diffusion distance as a heuristic, our preliminary investigations suggest that while the analytical diffusion distance can exhibit non-monotonic behavior with respect to the true distance, these non-monotonicities do not manifest as deep local minima that would fundamentally impair the solver's performance. It is also important to note that our approach does not simply converge to the raw diffusion distance; instead, it combines diffusion distance with a neural network model trained to approximate it. The interplay between these components, along with hyperparameters such as learning rate and regularization, can significantly influence the algorithm's behavior. It is a topic that warrants careful investigation in future work. We agree that denser parts of the state space pose the most significant challenge for our method, which may contribute to the performance stagnation at larger training scales. Regarding alternative problem generators, we concur that exploring more sophisticated random walk strategies could yield better training signals. We are actively developing approaches that could sample states more efficiently while maintaining good coverage of the state space. One promising direction involves biasing the random walks using easily computable heuristics (such as Manhattan or Hamming distance) to preferentially sample states that increase the heuristic value, controlled by a temperature parameter. However, for this initial study, we deliberately chose the simplest approach to isolate and demonstrate the effectiveness of the diffusion distance concept and multi-agent ensemble strategy in their pure form, allowing us to establish a clear baseline for future improvements."}, {"review_id": "9z5sLp6imY", "reviewer": "Reviewer_Zg9J", "summary": "This paper introduces a machine learning approach for solving large Rubik’s cubes by combining diffusion-distance learning via ResMLP networks with beam search. The method uses a multi-agent setup, where each agent is trained with a different randomized dataset generated through random walks on Cayley graphs. The proposed solver significantly outperforms prior machine learning methods on 3x3x3 cubes and is the first to generalize effectively to 4x4x4 and 5x5x5 puzzles, surpassing results from the 2023 Kaggle Santa Challenge. The method is computationally efficient and demonstrates robustness across a broad range of permutation group puzzles.", "questions": "1. Could you clarify why you do not compare against heuristic search baselines, such as IDA*, A*, or PDB-guided search, which are more appropriate comparisons for a beam search-based method? \n2. Can your random-walk-based diffusion distance training approach be used to enhance other search heuristics e.g., A*, IDA*, or greedy best-first search, rather than just beam search? If not, what specific aspects of beam search make it uniquely compatible?\n3. You include results on several classical combinatorial problems (e.g., 15-puzzle, 24-puzzle,...), could you clarify how your method compares, in terms of accuracy, solution quality (e.g., move count), and runtime, with classical solvers such as PDB-based IDA*, or learning-based solvers like DeepCubeA, on these domains?", "limitations": "N/A", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n1. Well-structured combination of random walk-based diffusion distance learning and beam search.\n2. Efficient multi-agent strategy, reducing training time and enabling parallelization.\n3. Good performance across sizes.\n4. The method is significantly faster.\n\nWeaknesses:\n1. No Comparison with Classical Heuristic Search (e.g., IDA*), while the method uses beam search as a core component, the evaluation omits comparisons with other heuristic search algorithms like IDA*, A*, or PDB-guided search. For a fair assessment, the proposed beam search + learned heuristic should be compared with classical search baselines that also use heuristics, not only RL agents.\n\n2. The proposed approach relies on search to correct for errors in the learned distance function, whereas DeepCubeA and similar models are pure RL policies that do not search during inference. Comparing these directly can be misleading, search-based solvers should be evaluated against other search-based solvers, not pure policy networks.", "was_revised": true, "final_justification": "As discussed, I’m most concerned about the importance of solving the large Rubik’s over the regular 3×3×3, so I’ll keep my score.", "rebuttal": "1.1. No Comparison with Classical Heuristic Search (e.g., IDA*), while the method uses beam search as a core component, the evaluation omits comparisons with other heuristic search algorithms like IDA*, A*, or PDB-guided search For a fair assessment, the proposed beam search + learned heuristic should be compared with classical search baselines that also use heuristics, not only RL agents. \n\n1.2. Could you clarify why you do not compare against heuristic search baselines, such as IDA*, A*, or PDB-guided search, which are more appropriate comparisons for a beam search-based method? \n\n1.3. No Comparison with Classical Heuristic Search (e.g., IDA*), while the method uses beam search as a core component, the evaluation omits comparisons with other heuristic search algorithms like IDA*, A*, or PDB-guided search. For a fair assessment, the proposed beam search + learned heuristic should be compared with classical search baselines that also use heuristics, not only RL agents.\n\n**Reply:** We thank the reviewer for pointing out these concerns. We compared our result for 2x2x2 and 3x3x3 Rubik's Cubes with Breadth-first search and PDB+ search-based solver, respectively. Our solution demonstrated the best efficiency compared to other methods based on neural network heuristics. The comparison with PDB+ or other search-based solvers on larger puzzles was limited by computational resources. For example, following the suggestion of another reviewer, we added a new experiment directly comparing our solver with DeepCubeA and PDB-based solver on 15- and 24-puzzles. Our method solved the 15-puzzle in 3.5 seconds, DeepCubeA in 10.3 seconds, and the PDB-based solver in 0.002 seconds. At the same time, for the 24-puzzle, our approach solves instances in 11 seconds, DeepCubeA in 19.3 seconds, and PDB requires 4239 seconds for the same task. As seen from the example above, the PDB-solver's computational resource usage grows dramatically with the size of the puzzle. To the best of our knowledge, no PDB-based solutions for 4x4x4 or larger cubes were reported yet.  Thus, to fit into the limitation on available computation resources, we used the Santa Challenge dataset as a reference dataset for the cubes larger than 3x3x3.\n  \n2. The proposed approach relies on search to correct for errors in the learned distance function, whereas DeepCubeA and similar models are pure RL policies that do not search during inference. Comparing these directly can be misleading, search-based solvers should be evaluated against other search-based solvers, not pure policy networks.\n\n**Reply:** DeepCubeA and similar models are indeed RL-based in their concepts. At the same time, \"under the hood,\" they also use different search methods based on heuristics. E.g., DeepCubeA uses batch weighted A* search, which directly follows from their paper (Agostinelli, Forest, et al. \"Solving the Rubik’s cube with deep reinforcement learning and search.\" Nature Machine Intelligence 1.8 (2019): 356-363., page 357, column 1, paragraph 4) and their source code. Similarly, EfficientCube relies on beam search as the backbone of the proposed algorithms. We compared our results with multiple methods, including genetic and search-based algorithms. E.g., we compared our result for 2x2x2 and 3x3x3 Rubik's Cubes with Breadth-first search and PDB+ search-based solver, respectively. Our solution demonstrated the best efficiency compared to other methods based on neural network heuristics. The comparison with PDB+ or other search-based solvers on larger puzzles was limited by our computational resources. To the best of our knowledge, no PDB solutions for 4x4x4 or larger cubes were reported yet. Thus, we used the Santa Challenge dataset as a reference dataset.\n\n3. Can your random-walk-based diffusion distance training approach be used to enhance other search heuristics e.g., A*, IDA*, or greedy best-first search, rather than just beam search? If not, what specific aspects of beam search make it uniquely compatible?\n\n**Reply:** We thank the reviewer for highlighting this interesting question for discussion. We have developed a highly efficient GPU-based implementation of beam search, the source code of which is provided along with our paper. Thanks to its performance, we have managed to complete a large number of computation experiments using, in most cases, a single server with only two GPU accelerators. Since our research is purely empirical (which we directly state in our limitations, Section 4.4), it was crucial to provide comparability between all the experimental results. Therefore, we employed the same search method for all experiments. During the preliminary phase of our research, we performed several experiments on combining our approach with the implementation of the A* algorithm but did not achieve the desired performance. Then, when our method surpassed the results of DeepCubeA, which internally uses batch weighted A* search, we decided to focus our efforts on analyzing other factors affecting solution length using beam search for all the remaining experiments.\n\n4. You include results on several classical combinatorial problems (e.g., 15-puzzle, 24-puzzle,...), could you clarify how your method compares, in terms of accuracy, solution quality (e.g., move count), and runtime, with classical solvers such as PDB-based IDA*, or learning-based solvers like DeepCubeA, on these domains?\n\n**Reply:** We thank the reviewer for raising this important question. Following your suggestion, we extended our experiments to include classical 15-puzzle instances (in addition to the periodic boundary version reported in Table 4). We tested our method on standard 4×4 (15-puzzle) and 5×5 (24-puzzle) sliding puzzles, comparing against both classical PDB-based solvers and learning-based approaches.\n\nFor the 4×4 puzzle, our method achieves 100\\% optimality with an average solution length of 52.02 moves, matching the performance of PDB-based optimal solvers and slightly outperforming DeepCubeA (99\\% optimality). Our solving time of 3.5 seconds is faster than DeepCubeA's 10.3 seconds, though naturally slower than PDB's near-instantaneous 0.002 seconds. Crucially, our training time is only 40 seconds compared to DeepCubeA's 36 hours—a dramatic reduction in computational requirements.\n\nFor the more challenging 5×5 puzzle, our approach solves instances in 11 seconds with 88\\% optimality, compared to DeepCubeA's 19.3 seconds with 97\\% optimality. Interestingly, while PDB guarantees optimal solutions, it requires 4239 seconds (over an hour) to solve 5×5 puzzles—demonstrating that our learned heuristic provides a practical speed-optimality tradeoff for larger instances. EfficientCube was unable to solve the 5×5 puzzle in our tests, the original paper also does not report the this solution is able to solve 24-puzzle.\n\nThese results demonstrate that our method offers a compelling balance: training times measured in seconds rather than days, competitive solution quality, and practical solving speeds that scale better than exact algorithms for larger puzzles. While domain-specific solvers like PDB excel on smaller instances where precomputation is feasible, our approach provides a more general and scalable alternative that requires minimal domain knowledge.\n\nWe will include these clarification in the Appendix of our camera ready version and incorporated classical puzzle results in Table 4 to provide a more comprehensive evaluation across different puzzle domains."}]

Author rebuttal:

Meta-review: The paper presents a machine learning-based approach to the pathfinding problem by leveraging diffusion distance estimation and using beam search for pathfinding. Experiments show that the method's efficiency solves 4x4x4 and 5x5x5 Rubik's cubes with short solution lengths, outperforming existing solvers. On the 3x3x3 Rubik's cube, it achieves an optimality rate exceeding 98%, matching task-specific solvers and outperforming previous solutions like DeepCubeA (60.3%) and EfficientCube (69.6%).

Overall, the results are significant, and all reviewers recognized that this work provides strong empirical contributions. One issue raised was the lack of comparison with classical heuristic solvers such as IDA* and PDB. The authors acknowledged that such solvers are effective on smaller problems but become computationally infeasible for larger cubes. Still, it would have been better to provide some direct comparisons. I also agree with reviewer Zg9J that the use of "large Rubik's cubes" in the title is imprecise. While I understand that the authors explained "large" to refer to the complexity of the Cayley graphs, using the term in the title without additional context can be misleading. The authors should revise the title in the final version by either replacing or removing the word "large".

Nevertheless, the empirical results are really impressive. Hence, I am happy to recommend acceptance with a spotlight.
Decision: Accept (spotlight)