🤖 machine learning

CayleyPy RL: Pathfinding and Reinforcement Learning on Cayley Graphs

This paper presents the CayleyPy project, which combines reinforcement learning with diffusion distance methods to efficiently solve pathfinding on massive Cayley graphs, successfully overcoming classical tools like GAP, providing strong evidence for the OEIS-A186783 conjecture regarding the symmetric group's diameter, and establishing new theoretical bounds while inviting community participation through Kaggle challenges.

Original authors: A. Chervov, M. Obozov, A. Soibelman, S. Lytkin, I. Kiselev, S. Fironov, A. Lukyanenko, A. Dolgorukova, A. Ogurtsov, F. Petrov, S. Krymskii, M. Evseev, L. Grunvald, D. Gorodkov, G. Antiufeev, G. Verbii

Published 2026-05-19

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: A. Chervov, M. Obozov, A. Soibelman, S. Lytkin, I. Kiselev, S. Fironov, A. Lukyanenko, A. Dolgorukova, A. Ogurtsov, F. Petrov, S. Krymskii, M. Evseev, L. Grunvald, D. Gorodkov, G. Antiufeev, G. Verbii, V. Zamkovoy, L. Cheldieva, I. Koltsov, A. Sychev, A. Eliseev, S. Nikolenko, N. Narynbaev, R. Turtayev, N. Rokotyan, S. Kovalev, A. Rozanov, V. Nelin, S. Ermilov, L. Shishina, D. Mamayeva, A. Korolkova, K. Khoruzhii, A. Romanov

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The Big Picture: Finding the Shortest Way Home in a Maze of Mirrors

Imagine you are in a giant, infinite maze. But this isn't a normal maze with walls; it's a maze made of rules. Every time you take a step, you follow a specific rule that changes your position. In math, this is called a Cayley graph.

The goal of this paper is to solve a specific type of maze: the LRX maze. This maze is built using the rules of shuffling a deck of cards (or a permutation of numbers).

Rule L: Shift everything one spot to the left.
Rule R: Shift everything one spot to the right.
Rule X: Swap the first two items.

The challenge is: If you start with a deck of cards in a messy order, what is the shortest sequence of Left, Right, and Swap moves to get them back to perfect order?

The Problem: The Maze is Too Big for Humans (and Old Computers)

For a small deck of cards, a human or a standard computer program (like the famous math software GAP) can figure out the solution. But as the number of cards ( $n$ ) grows, the number of possible arrangements explodes.

For $n=20$ , the maze is huge.
For $n=100$ , the maze is so big it has more paths than there are atoms in the universe.

Old computer programs get stuck. They try to map every single path, run out of memory, and give up. The authors wanted to see if Artificial Intelligence (AI) could act like a smart explorer to find the way through these massive mazes without mapping every single inch.

The Solution: Teaching an AI to "Guess" the Way

The authors built a system called CayleyPy RL. Think of it as training a robot to navigate the maze. They used a method called Reinforcement Learning (RL).

Here is how they trained the robot, using a simple analogy:

1. The "Warm-Up" (Diffusion Distance)
Imagine you drop a drop of ink in a glass of water. The ink spreads out randomly. If you want to know how far a specific spot is from the center, you can see how long it takes the ink to reach it.

The AI first learned by watching millions of "random walks" (like the ink spreading). It didn't know the shortest path, but it learned a "feeling" of distance. It knew, "If I'm here, it usually takes about 50 random steps to get home."
This gave the AI a rough map, but it wasn't perfect.

2. The "Smart Training" (Reinforcement Learning)
Next, they taught the AI to be smarter. Instead of just guessing based on random walks, they used a technique called Deep Q-Learning.

Imagine the AI is playing a game where it gets a "penalty" for every step it takes. It wants to reach the finish line with the fewest penalties.
The AI tried different moves, saw which ones got it closer, and adjusted its brain (neural network) to make better guesses.
The Innovation: They combined the "ink spreading" intuition with the "game playing" logic. This helped the AI avoid getting stuck in dead ends (local minima) that usually trap simpler algorithms.

3. The "Beam Search" (The Team of Explorers)
This is the most critical part. Imagine you are sending one explorer into the maze. If they take a wrong turn, you lose.

Instead, the authors sent out a team of explorers (a "beam").
At every intersection, the team splits. They keep the top 10,000 most promising paths and throw away the bad ones.
By keeping a huge team (millions of paths in some cases), the AI ensures that even if most explorers get lost, at least one of them finds the perfect shortest path.

The "Magic Trick" (The X-Trick)

The authors discovered a funny little shortcut. In their code, they added a single line of logic:

If the first two cards are already in the right order, don't swap them.

It sounds obvious to a human, but for a computer, it was a game-changer. This tiny rule, which they called the "X-trick," allowed their AI to solve mazes with 100 cards ( $n=100$ ).

Without the trick: The AI could only handle about 40 cards.
With the trick: It handled 100+ cards, beating the old computer software (GAP) which crashed around 20 cards.

What Did They Prove? (The Math Part)

Beyond just building a fast solver, they used their AI to make discoveries about the math of these mazes:

The "God's Number" Conjecture: There is a famous guess in math that the hardest possible shuffle of $n$ cards requires exactly $n(n-1)/2$ moves. The AI tested this for huge numbers and never found a shuffle that was harder than this. It strongly supports the idea that this formula is the absolute limit.
The "Longest" Shuffle: They identified the single most chaotic shuffle possible (the "longest element") and proved exactly how to break it down into moves.
New Bounds: They proved mathematically that the maze cannot be smaller than a certain size and cannot be larger than another size, narrowing down the answer significantly.
The Shape of the Maze: They found that if you count how many shuffles exist at each distance from the start, the numbers don't follow a perfect bell curve (like a normal distribution). Instead, they follow a weird, lopsided shape called a Gumbel distribution.

The Results: AI vs. The Old Guard

The paper compares their new AI method against the standard computer algebra system GAP:

GAP: Can solve up to ~20 cards. It takes hours or days. The paths it finds are often long and inefficient.
CayleyPy RL (AI): Can solve up to ~100 cards. It is much faster. It finds paths that are very close to the theoretical shortest possible path.

Summary

The authors created a smart AI system that treats complex math problems like a giant maze. By combining random guessing with smart learning and sending out a massive "team" of virtual explorers, they can navigate mazes that are too big for traditional computers. They even found a tiny "cheat code" (the X-trick) that lets them solve problems 5 times larger than before, while simultaneously proving new mathematical facts about how these mazes are structured.

They have also put their code and challenges on a platform called Kaggle, inviting other people to try to beat their records and help solve even harder versions of these puzzles.

Technical Summary: CayleyPy RL: Pathfinding and Reinforcement Learning on Cayley Graphs

Problem Statement
The paper addresses the problem of pathfinding on extremely large finite Cayley graphs, specifically focusing on the symmetric group $S_n$ generated by left cyclic shifts ( $L$ ), right cyclic shifts ( $R$ ), and a transposition of the first two elements ( $X$ ). This configuration, known as the LRX Cayley graph, corresponds to the OEIS sequence A186783. The core mathematical challenge is decomposing a group element into the shortest possible product of generators (finding the shortest path in the graph). This problem is NP-hard for generic finite Cayley graphs. Classical computer algebra systems, such as GAP, rely on the Schreier-Sims algorithm, which often produces exponentially long paths and fails to handle groups with sizes beyond $10^{30}$ (roughly $n \approx 20$ for $S_n$ ). The authors aim to develop efficient artificial intelligence-based approaches capable of handling graphs with sizes up to $10^{70}$ (e.g., $n \approx 40$ to $100$) while producing near-optimal or optimal paths.

Methodology
The authors propose a hybrid methodology combining Reinforcement Learning (RL), specifically Deep Q-Learning (DQN), with a pre-training strategy based on diffusion distances.

Reinforcement Learning Framework: The pathfinding problem is framed as finding the shortest path from a state $s$ to the identity element $e$ . This is modeled using the Bellman equation, where the distance function $d(s)$ satisfies $d(s) = 1 + \min_{t \in N(s)} d(t)$ . Standard DQN is adapted to approximate this value function using neural networks.
Diffusion Distance Pre-training: To address the "sparse reward" problem and the noise inherent in standard DQN initialization, the authors introduce a "warm-up" phase. They generate training data via random walks (diffusion) starting from the target. A neural network is first trained to predict the number of steps in these random walks (diffusion distance).
Modified DQN: The pre-trained network is then fine-tuned using a modified DQN algorithm. Crucially, the Bellman update targets are clipped based on the time step $k$ at which a state was first visited during the random walk generation. This prevents the network from overestimating distances and stabilizes training.
Guided Beam Search: Once the neural network is trained to estimate distances, it serves as a heuristic function for a beam search algorithm. The beam search maintains a fixed number ( $W$ ) of the most promising states at each step, expanding their neighbors and selecting the top $W$ based on the network's predictions. This avoids getting stuck in local minima, a common failure mode for greedy search.
The "X-trick": A specific heuristic modification for the LRX generators is introduced. If the first two elements of a permutation are already sorted, the generator $X$ (which swaps them) is excluded from the neighbor set. This single-line modification drastically reduces the search space and improves mixing times.
Non-backtracking: The authors incorporate non-backtracking constraints in both the random walk generation and the beam search to reduce variance in the distance estimates and prevent stagnation in local minima.

Key Contributions

Algorithmic Advancements: The paper presents a novel combination of diffusion distance pre-training and modified DQN. This approach overcomes the limitations of standard DQN (sparse rewards, noisy targets) and outperforms classical methods.
Performance Benchmarks: The proposed methods successfully find paths for LRX Cayley graphs up to $n \approx 44$ with zero prior knowledge and up to $n \approx 100$ when utilizing the "X-trick." This significantly exceeds the capabilities of GAP, which is limited to $n \approx 20$ . The AI methods produce shorter paths and run faster than GAP for comparable $n$ .
Mathematical Results and Conjectures:
- Diameter Conjecture: The authors strongly support the OEIS-A186783 conjecture that the diameter of the LRX Cayley graph is $n(n-1)/2$ . They verified this via brute-force BFS for $n \le 15$ and via AI decomposition for $n$ up to 200 (via Kaggle challenges), finding no decomposition shorter than the conjectured length.
- Longest Element: They identify a unique "longest element" $\ell_n = (1, 0, n-1, n-2, \dots, 3, 2)$ and provide an explicit decomposition of length $n(n-1)/2$ .
- Bounds: The paper proves a lower bound for the diameter of $n(n-1)/2 - n/2 - 1$ and an upper bound of $n(n-1)/2 + 3n$ via a constructive algorithm. An empirical algorithm suggests a tighter bound of $n(n-1)/2 + n/2$ .
- Growth Distribution: Numerical experiments suggest the growth function of the LRX graph follows a left-skewed Gumbel distribution for large $n$ , contrasting with the Gaussian distribution observed in neighbor transposition graphs.
- Mixing Time: While standard random walks have mixing times between $O(n^3)$ and $O(n^3 \log n)$ , the authors conjecture that random walks modified with the "X-trick" mix faster, with a time complexity of $O(n^2)$ .
- Spectrum: The spectrum of the LRX graph appears to follow a uniform distribution.
Open Source and Crowdsourcing: The authors released the "CayleyPy" project and created Kaggle challenges to crowdsource solutions for decomposing the longest element and finding optimal algorithms, fostering collaboration between AI and mathematical communities.

Results

Efficiency: For $n=20$ , GAP requires over 41 minutes to find a path of length 217,944, whereas the diffusion distance method finds the optimal path of length 190 in under 4 minutes.
Scalability: With the "X-trick," the system solved instances for $n=100$ (graph size $\approx 10^{157}$ ) in roughly 8.5 hours on a single GPU, finding a path of length 16,632 (compared to the conjectured diameter of 4,950).
Model Performance: Simple models like Multi-Layer Perceptrons (MLP) and Gradient Boosting (CatBoost/XGBoost) often outperformed complex architectures like Transformers and CNNs for this specific task.
Beam Search: The success rate of finding a path is highly dependent on beam width, showing a super-linear improvement as the beam size increases, analogous to the "exchange of ideas" in a research community.

Significance
The paper claims that computational experiments, particularly those leveraging AI, can significantly advance mathematical research on Cayley graphs. It demonstrates that AI methods can "overcome" classical computer algebra systems in both scalability (handling much larger $n$ ) and solution quality (finding shorter, near-optimal paths). The work bridges the gap between theoretical group theory and practical AI, providing rigorous bounds, new conjectures on growth and mixing times, and a framework for solving pathfinding problems in extremely large state spaces that were previously intractable. The authors position this as a step toward applying AI to other complex planning problems in theoretical science.