🤖 machine learning

The Two-Hump Problem: Bridging the Difficulty Gap in Mathematical Reinforcement Learning

This paper addresses the "Two-Hump" difficulty distribution in mathematical reinforcement learning by introducing novel data generation techniques and algorithmic enhancements to bridge the gap between trivial and impossible problem instances, resulting in substantial performance improvements and the release of large-scale benchmark datasets (AC-19 and AC-1M) for the Andrews-Curtis conjecture.

Original authors: Lucas Fagan, Michele Tarquini, Ali Shehper, Maksymilian Manko, Angus Gruen, Coco Huang, Giorgi Butbaia, Davide Passaro, Sergei Gukov

Published 2026-06-23

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Lucas Fagan, Michele Tarquini, Ali Shehper, Maksymilian Manko, Angus Gruen, Coco Huang, Giorgi Butbaia, Davide Passaro, Sergei Gukov

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: A Mathematical Maze

Imagine you are trying to solve a giant, infinite maze. The goal is to take a complex, tangled knot of string (a mathematical "presentation") and untangle it until it becomes a simple, straight line (the "trivial" solution).

For decades, mathematicians have been trying to figure out if every possible knot can be untangled this way. This is called the Andrews-Curtis Conjecture.

Recently, scientists tried to use Artificial Intelligence (specifically Reinforcement Learning, or RL) to solve this. Think of the AI as a robot explorer trying to find the exit. But the robot kept getting stuck. It could easily solve the easy knots, but it hit a wall when it encountered the hard ones. It didn't know how to get from "easy" to "hard."

This paper explains why the robot was stuck and how they fixed it.

The Problem: The "Two-Hump" Landscape

The authors discovered that the difficulty of these math problems isn't spread out evenly. Instead, it looks like a landscape with two giant hills and a deep, empty valley in between.

The Easy Hill (Left): These are the knots that are easy to untangle. The robot can solve these quickly by just making them shorter step-by-step.
The Impossible Hill (Right): These are the knots that are so complex that current computers and robots simply cannot solve them. They get stuck in a loop.
The Empty Valley (Middle): This is the problem. There are almost no "medium-difficulty" knots.

Why is this bad for AI?
Imagine you are teaching a child to climb a mountain. If you only show them a tiny hill (too easy) and a vertical cliff (too hard), they will never learn how to climb a steep slope. They need "stepping stones" in the middle. Because the math problems lacked these stepping stones, the AI couldn't learn the general skills needed to tackle the really hard knots.

The Solution: Three New Tools

To bridge this gap, the team built three new tools to help the AI climb the mountain.

1. The "Super-Move" (Substitutions)

In the old way, the robot could only make tiny, single steps (like moving one piece of string). This was too slow.
The authors realized the robot could make "Super-Moves." Instead of moving one piece, the robot learned to grab a whole chunk of the knot, rotate it, and snap it into a different spot all at once.

Analogy: Imagine trying to organize a messy room. The old way was moving one sock at a time. The new way is picking up a whole pile of clothes, folding them, and placing them in the closet in one giant, efficient motion. This lets the robot take giant leaps through the maze instead of tiny shuffles.

2. The "Dual-Ring" Brain (New Architecture)

The math problems have a special property: they are cyclic. If you have a necklace of beads, it doesn't matter where you start counting; the pattern is the same.
The old AI brains (neural networks) treated the string like a straight line, which confused them. The authors built a new brain called the Dual-Ring Transformer.

Analogy: Imagine looking at a clock. A normal brain sees the numbers 1 through 12 in a straight line. The new brain sees them as a circle. It understands that 12 is right next to 1. This helps the AI see the "big picture" of the knot and find shortcuts that the old brain missed.

3. The "Generator-Solver" Game (Filling the Valley)

Since the "valley" of medium-difficulty problems was empty, the team had to create their own. They set up a game between two AIs:

The Generator: Its job is to take an easy knot and twist it just enough to make it harder, but not impossible. It's like a puzzle master who creates a puzzle that is challenging but solvable.
The Solver: Its job is to try and untangle the new, harder knot.
The Result: By playing this game millions of times, they created a massive library of "Goldilocks" problems—not too easy, not too hard. This filled the valley with stepping stones, allowing the AI to learn how to climb the steep parts of the mountain.

The Results

With these three tools, the AI made huge progress:

More Solved: The new AI solved 153 more difficult knots than the previous best method.
Smarter Paths: Even when the old methods could solve a knot, the new AI found a much shorter, more efficient path to the solution. It learned to take "detours" that temporarily made the knot look bigger, just to untangle it faster later on.
New Datasets: They released two massive new libraries of math problems (AC-19 and AC-1M) containing over a million examples, which other scientists can now use to keep training better AIs.

The Bottom Line

The paper proves that the reason AI struggled with this math problem wasn't because the AI was "dumb," but because the problem landscape was broken (the Two-Hump). By fixing the landscape (creating stepping stones) and giving the AI better tools (Super-Moves and a Ring-Brain), they were able to solve hundreds of previously unsolved mathematical puzzles.

They didn't prove the whole conjecture yet (the mountain is still huge), but they built a much better ladder to climb it.

Technical Summary: The Two-Hump Problem in Mathematical Reinforcement Learning

Problem Definition

The paper addresses the challenge of applying Reinforcement Learning (RL) to the Andrews–Curtis (AC) conjecture, a prominent open problem in combinatorial group theory. The conjecture posits that any balanced presentation of the trivial group can be transformed into the trivial presentation $\langle x, y \mid x, y \rangle$ via a finite sequence of specific moves (AC1: inversion, AC2: conjugation/concatenation, AC3: cyclic permutation).

The core difficulty lies in the nature of the search space:

Vast Search Spaces: The graph of possible presentations is infinite.
Sparse Rewards: An agent receives a reward only upon complete trivialization; there are no intermediate "early failure" signals or partial progress indicators.
The "Two-Hump" Phenomenon: The authors identify a critical structural barrier where problem instances are bimodally distributed. Most presentations are either trivially solvable (via simple greedy length reduction) or effectively impossible (requiring paths that temporarily increase length, which standard heuristics reject). Crucially, there is a scarcity of intermediate "hard-but-solvable" instances, creating a "valley" of data that prevents effective curriculum learning.

Methodology

To bridge the difficulty gap and overcome the Two-Hump distribution, the authors propose a three-pronged approach combining algorithmic innovations, architectural design, and targeted data generation.

1. Action Space: Substitution Supermoves

Instead of operating on primitive AC-moves, the authors introduce substitution moves as the primary action space.

Mechanism: A substitution treats relators as cyclic sequences and inserts one into the other at a point where cancellation occurs. This combines multiple primitive moves (AC1, AC2, AC3) into a single action.
Benefit: This allows the agent to take larger, more meaningful steps through the AC graph and significantly reduces the effective state space by ignoring cyclic permutations.
Theoretical Basis: Ivanov (2018) proved that if the AC conjecture is true, substitutions suffice to realize all AC-transformations.

2. Architecture: The Dual-Ring Transformer

To handle the large, structured action space of substitutions while respecting the mathematical symmetries of the problem, the authors developed the Dual-Ring Transformer.

Cyclic Symmetry: Unlike standard Transformers that use absolute positional encoding, this architecture treats relators as cyclic rings. It employs cyclic relative positional encodings where the attention score depends on the cyclic distance $d(i, j) = (i - j) \mod L$ .
Cross-Attention: The network processes both relators in parallel, using cross-attention to identify matching substrings between $r_1$ and $r_2$ , which is critical for determining valid substitution moves.
Policy Head: The output is a distribution over valid substitution moves, masked to ensure only actions leading to cancellation (where $r_1[i] = \pm r_2[j]$ ) receive non-zero probability.

3. Data Generation: Populating the Valley

Recognizing that standard "scrambling" strategies fail to generate hard-but-solvable instances, the authors employ two novel data generation techniques:

Automorphism Perturbation: Applying automorphisms to known trivial presentations (e.g., $AK(2)$) transforms them into presentations with drastically different path characteristics. While the original may be easy, its automorphic image may require length-increasing steps, effectively moving it from the "easy" hump to the "valley."
Generator-Solver Game: An asymmetric two-player game is formulated where a Generator (a PPO agent) applies sequences of automorphisms to increase presentation difficulty, while a Solver (greedy search) attempts to trivialize them. The Generator is rewarded for creating instances that challenge the Solver, specifically targeting the intermediate difficulty region.
Resulting Datasets: This process yields AC-19 (125,192 short AC-trivial presentations, length $\le 19$ ) and AC-1M (1,136,154 hard AC-trivial presentations, length $\le 30$ ), the first large-scale public datasets of this kind.

Key Results

The authors evaluate their methods on the 1,190-presentation Miller–Schupp benchmark dataset.

Performance Improvement: The combination of substitution supermoves and the Dual-Ring Transformer (PPO-Sub-DRT) solves 610 presentations (mean over 5 seeds), a significant increase from the previous best RL baseline of 457 (PPO-AC-ResNet).
Data Impact: Incorporating the generated AC-1M dataset further improves performance, demonstrating that targeted data generation successfully helps agents learn general strategies for hard presentations.
Path Efficiency: While Greedy Search (GS) with substitutions solves more instances (640) due to exhaustive exploration, the PPO agent discovers substantially shorter solution paths, particularly on harder presentations. PPO identifies length-increasing detours that greedy heuristics reject, proving the agent learns non-obvious mathematical structures.
Architectural Superiority: The Dual-Ring Transformer (using cyclic relative encodings) outperforms a variant using canonical form preprocessing with absolute encodings by approximately 25 solved presentations, highlighting the importance of learning symmetry-aware representations.
Mathematical Progress: The authors successfully trivialized over 100 previously unsolved presentations from the Miller–Schupp family. They reduced the remaining 550 unsolved examples to 261 distinct AC-equivalence classes, providing a concrete checklist for future research.

Significance and Claims

The paper claims that progress on the Andrews–Curtis conjecture requires understanding the problem's inherent difficulty structure rather than just scaling compute.

The Two-Hump Insight: The identification of the bimodal difficulty distribution explains why previous approaches struggled and motivates the necessity of combining algorithmic improvements with targeted data generation.
RL in Sparse Reward Environments: The work demonstrates that RL can succeed in extremely sparse reward environments where solutions require hundreds of precise sequential decisions, offering insights transferable to robotics, theorem proving, and program synthesis.
Mathematical Utility: Regardless of whether the AC conjecture is ultimately true or false, the work makes concrete progress. If true, every new trivialization contributes to a proof; if false, trivializing apparent counterexamples narrows the search for genuine ones.
Transferability: The "Two-Hump" structure and the techniques developed (substitutions, cyclic architectures, generator-solver games) are presented as generalizable to other mathematical search problems where bimodal difficulty distributions and progress-violating moves occur.

The authors conclude that further progress will not come from marginal improvements in classical search but will require learning-based methods capable of exploiting structure beyond what fixed heuristics can capture.