pith. sign in

arxiv: 2606.21611 · v1 · pith:ZZHS6EFRnew · submitted 2026-06-19 · 💻 cs.LG · cs.AI· math.GR· math.GT

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

Lucas Fagan , Michele Tarquini , Ali Shehper , Maksymilian Manko , Angus Gruen , Coco Huang , Giorgi Butbaia , Davide Passaro
show 1 more author
Sergei Gukov
This is my paper

Pith reviewed 2026-06-26 14:44 UTC · model grok-4.3

classification 💻 cs.LG cs.AImath.GRmath.GT
keywords reinforcement learningAndrews-Curtis conjecturemathematical searchdifficulty distributiondata generationtransformer modelscombinatorial optimization
0
0 comments X

The pith

A two-hump difficulty distribution creates a barrier to reinforcement learning in mathematical search problems.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Mathematical search problems like those arising from the Andrews-Curtis conjecture have search spaces that are either too easy or too hard for reinforcement learning agents to improve on. The paper identifies this as a two-hump distribution in problem difficulty, with few instances that are hard but still solvable. This scarcity prevents the gradual learning that RL requires. The authors respond by inventing new data generation methods to create more intermediate instances and by upgrading the algorithms with supermoves and transformer models. These steps produce measurable gains in performance and yield large new datasets for the community.

Core claim

The paper establishes that the Andrews-Curtis problem instances follow a two-hump distribution in solvability, with most presentations being either trivially solvable or effectively impossible within computational limits. This leaves a gap in hard-but-solvable cases that blocks effective reinforcement learning. By introducing novel data generation techniques to populate this gap and algorithmic enhancements such as supermoves and Transformer architectures, the work achieves substantial performance improvements over prior baselines.

What carries the argument

The two-hump distribution of problem difficulty in the Andrews-Curtis landscape, which the authors identify as the structural barrier separating trivial from impossible instances.

If this is right

  • New datasets AC-19 and AC-1M supply large collections of AC-trivial presentations for training and testing.
  • The combination of data generation and algorithmic changes allows RL agents to solve more difficult instances.
  • Supermoves and Transformer architectures provide concrete tools for navigating vast search spaces with sparse rewards.
  • Performance gains demonstrate that bridging the difficulty gap is key to applying RL to such mathematical problems.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Similar two-hump patterns may exist in other mathematical search domains, suggesting the data generation approach could transfer.
  • Successful bridging might accelerate progress toward resolving the Andrews-Curtis conjecture itself through automated methods.
  • The released benchmarks could standardize evaluation for future RL methods in combinatorial search.
  • Extending the length limits in datasets might reveal whether the two-hump persists at larger scales.

Load-bearing premise

That the new data generation techniques produce instances in the intermediate difficulty range rather than simply increasing the number of trivial or impossible cases.

What would settle it

A direct measurement showing that the generated instances in the new datasets remain clustered at the easy and hard extremes, with no increase in the middle difficulty band, would indicate the gap has not been populated.

Figures

Figures reproduced from arXiv: 2606.21611 by Ali Shehper, Angus Gruen, Coco Huang, Davide Passaro, Giorgi Butbaia, Lucas Fagan, Maksymilian Manko, Michele Tarquini, Sergei Gukov.

Figure 1
Figure 1. Figure 1: The “Two-Hump” Distribution is a general phenomenon: most presentations are either trivial or practically impossible for current agents. The scarcity of data in the middle region hinders learning. 1.1. Contributions Our specific contributions are: 1 arXiv:2606.21611v1 [cs.LG] 19 Jun 2026 [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Substitution move visualization. Both relators are viewed as cyclic sequences (rings). A substitution selects insertion points in each relator where one can be inserted into the other with at least one element canceling, combining many AC1, AC2, and AC3 moves into a single action. functions, operating on elementary AC-moves. 2.3. Substitutions While the conjecture is defined in terms of elementary AC-moves… view at source ↗
Figure 4
Figure 4. Figure 4: AC-19 Dataset Difficulty Distribution. Node counts required to solve the 125,192 verified trivial group presentations using greedy search with substitutions, displayed with logarithmic scales on both axes. Although AC-19 is a much larger dataset with many more hard presentations than the Miller–Schupp benchmark, the two-hump phenomenon persists: strong concentration in the easy regime (median: 51 nodes) wi… view at source ↗
Figure 5
Figure 5. Figure 5: Automorphisms transform easy presentations into hard ones. While a greedy heuristic can easily find a trivialization path for AK(2), it struggles on automorphisms of AK(2) whose short trivialization paths (shown in red) involve length-increasing steps. sentations with dramatically different path characteristics. While short paths exist for all three presentations, if we do not use our knowledge of the auto… view at source ↗
Figure 7
Figure 7. Figure 7 [PITH_FULL_IMAGE:figures/full_fig_p008_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Comparison of solution path lengths for hard presen￾tations solved by both greedy search and PPO (restricted to pre￾sentations where both methods required ≥50 steps). PPO consis￾tently discovers substantially shorter solution paths than greedy search, with GS finding a shorter path on only 2 instances. This demonstrates that PPO’s learned value function successfully iden￾tifies length-increasing detours th… view at source ↗
Figure 9
Figure 9. Figure 9: compares the number of search nodes required by length-based versus automorphic greedy search for presen￾tations solved by both methods [PITH_FULL_IMAGE:figures/full_fig_p015_9.png] view at source ↗
read the original abstract

Mathematical search problems present a unique challenge for Reinforcement Learning (RL) due to vast search spaces and sparse rewards. In previous works, the Andrews-Curtis (AC) conjecture was established as an illustrative example of such problems. In this work, we identify a critical structural barrier in the AC landscape: a "Two-Hump" distribution, where problem instances are either trivially solvable or effectively impossible, with a scarcity of intermediate "hard-but-solvable" instances required for effective learning. We tackle this challenge through two primary avenues: novel data generation techniques to populate the difficulty gap, and significant algorithmic enhancements including the introduction of supermoves and Transformer-based architectures. We demonstrate substantial performance improvements over previous baselines, and release new comprehensive benchmark datasets including AC-19 (125,192 AC-trivial presentations of varying difficulty with length at most 19) and AC-1M (1,136,154 hard AC-trivial presentations of length at most 30), the first large-scale, publicly available datasets of this kind.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The paper identifies a 'Two-Hump' distribution in the Andrews-Curtis (AC) conjecture problem landscape for RL, where instances are either trivially solvable or effectively impossible with few intermediate hard-but-solvable cases. It introduces novel data generation techniques to populate the difficulty gap, algorithmic enhancements including supermoves and Transformer-based architectures, and releases benchmark datasets AC-19 (125,192 AC-trivial presentations of length at most 19) and AC-1M (1,136,154 hard AC-trivial presentations of length at most 30), claiming substantial performance improvements over baselines.

Significance. If the two-hump phenomenon holds and the data-generation methods reliably produce hard-but-solvable instances that drive learning gains, the work could advance RL applications to mathematical search problems with sparse rewards. The public release of large-scale, labeled datasets is a clear positive contribution for reproducibility and community benchmarking.

major comments (2)
  1. [Abstract] Abstract: the central claim of 'substantial performance improvements' over previous baselines cannot be evaluated because the abstract (and provided summary) contains no quantitative results, ablation studies, or verification that generated instances are genuinely hard-but-solvable rather than scaled trivial cases.
  2. [Abstract] Abstract: the operational definition of the 'Two-Hump' distribution and the metric used to identify the scarcity of 'hard-but-solvable' instances is not stated; without this, it is unclear whether the new data-generation techniques actually populate the claimed intermediate band or merely increase the number of trivial instances.
minor comments (1)
  1. [Abstract] Abstract: the dataset sizes are given with precise counts (125,192 and 1,136,154), but the paper should specify in the methods how difficulty is quantified and how AC-trivial status is verified for the released instances.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their constructive comments on the abstract. We address each major comment below and agree that the abstract can be improved for clarity and completeness. Revisions will be made in the next version.

read point-by-point responses

  1. Referee: [Abstract] Abstract: the central claim of 'substantial performance improvements' over previous baselines cannot be evaluated because the abstract (and provided summary) contains no quantitative results, ablation studies, or verification that generated instances are genuinely hard-but-solvable rather than scaled trivial cases.

    Authors: We agree the abstract lacks specific quantitative results and ablations, which are present in the experimental sections of the full manuscript (including success rates on AC-19 and AC-1M versus baselines, plus ablation on supermoves and architecture). The manuscript also details the data generation process and validation that instances are AC-trivial yet require non-trivial search effort. To address the concern directly, we will revise the abstract to include key quantitative metrics and a brief note on instance verification. revision: yes

  2. Referee: [Abstract] Abstract: the operational definition of the 'Two-Hump' distribution and the metric used to identify the scarcity of 'hard-but-solvable' instances is not stated; without this, it is unclear whether the new data-generation techniques actually populate the claimed intermediate band or merely increase the number of trivial instances.

    Authors: The full manuscript defines the Two-Hump distribution in Section 3 via the empirical distribution of minimal solution lengths under the AC moveset, with the metric being the relative frequency of instances solvable in 1-5 moves versus those requiring >20 moves or remaining unsolved within computational limits. This shows the gap in intermediate cases. We acknowledge the abstract does not state this definition concisely. We will revise the abstract to include a one-sentence operational definition and note how the generation methods target the intermediate band. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper empirically identifies a two-hump distribution in the AC landscape via new datasets (AC-19, AC-1M) and reports performance gains from data-generation techniques plus algorithmic changes (supermoves, Transformers). No derivation step reduces by construction to a fitted parameter renamed as prediction, a self-definitional loop, or a load-bearing self-citation chain; the central claims rest on externally verifiable benchmark construction and performance deltas rather than internal redefinition of inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

Abstract provides no explicit free parameters, axioms, or invented entities; the work is described as empirical identification plus engineering improvements.

pith-pipeline@v0.9.1-grok · 5743 in / 1222 out tokens · 27056 ms · 2026-06-26T14:44:55.188993+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

13 extracted references · 2 canonical work pages · 1 internal anchor

  1. [1]

    Accessed: 2025-01-30

    URL https://deepmind.google/disc over/blog/ai-solves-imo-problems-at-s ilver-medal-level/. Accessed: 2025-01-30. Ecoffet, A., Huizinga, J., Lehman, J., Stanley, K. O., and Clune, J. First return, then explore.Nature, 590(7847): 580–586, 2021. Freedman, M. H., Gompf, R. E., Morrison, S., and Walker, K. Man and machine thinking about the smooth 4- dimension...

    work page doi:10.1088/2632-215 2025

  2. [2]

    Generative Language Modeling for Automated Theorem Proving

    ISBN 3-540-41158-5. Reprint of the 1977 edition. Miasnikov, A. D. Genetic algorithms and the Andrews– Curtis conjecture.International Journal of Algebra and Computation, 9(6):671–686, 1999. Miller, C. F. and Schupp, P. E. Some presentations of the trivial group. InGroups, Languages and Geometry (South Hadley, MA, 1998), volume 250 ofContemporary Math- ema...

    work page internal anchor Pith review Pith/arXiv arXiv doi:10.1016/s0004-3702(99)00052-1 1977

  3. [3]

    For to- kens at positions i and j in a relator of unpadded length L, the cyclic distance is d(i, j) = (i−j) modL

    Self-Attention with Cyclic Relative Positional En- coding:Each relator attends to itself using 4-head multi-head attention with head dimension 8. For to- kens at positions i and j in a relator of unpadded length L, the cyclic distance is d(i, j) = (i−j) modL . The attention score combines content and relative position: Ah ij = (Q h i ·K h j ) + (Qh i ·E h...

  4. [4]

    This uses standard dot-product attention without relative position bias

    Cross-Attention:The two relators attend to each other via symmetric cross-attention (4 heads, head dimension 8). This uses standard dot-product attention without relative position bias. This allows the network to iden- tify matching substrings between r1 and r2, critical for determining valid substitution moves

  5. [5]

    11 The Two-Hump Problem All sub-layers use pre-normalization (LayerNorm applied before the sub-layer) and residual connections

    Feed-Forward Networks:Standard FFN with GELU activation and hidden dimension 32. 11 The Two-Hump Problem All sub-layers use pre-normalization (LayerNorm applied before the sub-layer) and residual connections. A.4. Policy Head The policy head outputs a distribution over valid substitution moves. For each pair of positions (k1, k2) in relators r1 and r2:

  6. [6]

    Concatenate the embeddings at positions k1 and k2: [h1[k1];h 2[k2]](dimension2D= 64)

  7. [7]

    Pass through a 2-layer MLP with GELU activation: • First layer: Linear(64→128)+ GELU • Output layer: Linear (128→4) producing 4 logits corresponding to: –Which relator to replace:i∈ {1,2} –Whether to invertr 2:j∈ {−1,1}(usingr j 2)

  8. [8]

    This gives a distribution over |r1| × |r2| ×4 possible sub- stitution moves, with invalid moves automatically masked out

    Apply asemantic maskthat sets invalid actions to probability zero: only positions where r1[k1] = ±r2[k2] (enabling cancellation) receive non-zero prob- ability. This gives a distribution over |r1| × |r2| ×4 possible sub- stitution moves, with invalid moves automatically masked out. A.5. Value Head The value head estimates the expected return. It applies m...

    2025

  9. [9]

    hard-but-solvable

    based on the PureJaxRL implementation (Lu et al., 2022). All training is done in JAX (Bradbury et al., 2018). Training hyperparameters: • Total training steps: 250M environment interactions • Horizon length (rollout length per update): 96 steps • Number of parallel environments: 2,380 (640 fixed + 1,740 sampling) • Learning rate:2.5×10 −3 (constant, no an...

    2022

  10. [10]

    Canonical form preprocessing (PPO-Sub-Canon): Reduce all presentations to a unique canonical repre- sentative before feeding to a standard Transformer with absolute positional encodings

  11. [11]

    15 The Two-Hump Problem As shown in Table 1, the learned approach (PPO-Sub- DRT) outperforms canonical form preprocessing (PPO-Sub- Canon) by approximately 25 presentations

    Learned symmetry-aware representations (PPO- Sub-DRT):Use cyclic relative positional encodings that allow the network to flexibly attend to cyclically- related positions throughout processing. 15 The Two-Hump Problem As shown in Table 1, the learned approach (PPO-Sub- DRT) outperforms canonical form preprocessing (PPO-Sub- Canon) by approximately 25 prese...

  12. [12]

    Each relator ri is the lexicographically minimal el- ement among all its cyclic rotations and the cyclic rotations of its inverse: ri = min lex rotk(ri),rot k(r−1 i )|k∈Z

  13. [13]

    Substitutions

    The relators are ordered lexicographically:r 1 ≤lex r2 Every presentation can be reduced to a canonical form. Implication for substitutions.Note that the relators r1r−1 2 , r−1 2 r1, r−1 1 r2 and r2r−1 1 all have the same canonical form. This is why, for substitution moves, we only need to in- vert r2 and only append r±1 2 onto r1—the canonical form autom...

    1934