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

Motivation

• Known: 이전 연구(Shehper et al., 2025)는 AC conjecture를 RL 환경으로 정식화하여 PPO와 greedy search 베이스라인을 제시했고, Havas & Ramsay 등은 exhaustive enumeration으로 length 13까지의 presentation을 분류했다. Rubik's cube 등 다른 sparse-reward 문제에서는 curriculum learning이나 intrinsic motivation 등이 활용되어 왔다.
• Gap: AC 탐색 공간은 무한하고 scrambling으로는 trivial하거나 이미 알려진 hard instance로만 귀결되어 유용한 curriculum 데이터를 생성하기 어렵다. 기존 접근은 "쉬움-어려움" 사이의 중간 난이도, 즉 학습에 필요한 "hard-but-solvable" instance가 극도로 희박한 Two-Hump 구조 자체를 인식하지 못했고 이를 해결할 방법이 없었다.
• Why: AC conjecture는 4차원 Smooth Poincaré Conjecture 및 Generalized Property R conjecture와 직접 연결된 조합군론의 미해결 난제이며, 이산적이고 효율적으로 검증 가능한 순수 탐색 문제로서 AI 기반 수학적 탐색의 강력한 테스트베드다. Two-Hump 문제의 해결은 sparse-reward 수학 탐색 RL 전반에 적용 가능한 일반적 통찰을 제공한다.
• Approach: substitution 기반 supermove로 액션 공간을 재구성하고, 이를 처리하기 위한 Dual-Ring Transformer 아키텍처를 도입했으며, exhaustive enumeration과 automorphism 기반 생성-해결기 게임을 통해 난이도 valley를 채우는 데이터를 생성했다.

Achievement

Figure 6. Comparison of difficulty distributions for 200 AC-trivial

1. Two-Hump 분포 규명: AC 문제의 난이도 분포가 greedy reduction으로 풀리는 쉬운 mass, 어떤 알고리즘도 진전 못하는 unsolvable mass, 그리고 희소한 중간 valley로 구성됨을 실증적으로 규명했다(Figure 1, 3).
2. Substitution supermove 도입: 여러 primitive AC-move를 하나의 move로 결합하는 substitution을 올바른 action space로 식별하여 state space를 크게 축소하고 더 큰 step을 가능하게 했다.
3. Dual-Ring Transformer 아키텍처: 두 relator를 cyclic sequence로 처리하며 cross-attention으로 최적 substitution move를 식별하는 특화 아키텍처를 개발하여, 확장된 action space에도 불구하고 PPO agent가 기존 baseline 대비 상당한 성능 향상과 더 짧은 solution path를 달성했다.
4. AC-19, AC-1M 벤치마크 데이터셋 공개: exhaustive enumeration으로 length ≤19의 125,192개 presentation(AC-19)과, automorphism 및 ML 기반 generator-solver game으로 생성한 length ≤30의 1,136,154개 hard AC-trivial presentation(AC-1M)을 최초로 대규모 공개했다.
5. AC conjecture 자체에 대한 실질적 진전: Miller-Schupp family 벤치마크에서 기존 미해결이던 100개 이상의 presentation을 trivialize했고, 남은 550개 미해결 예제를 261개 동치류로 축소하며 각 class의 minimal representative를 결정했다.

How

Figure 5. Automorphisms transform easy presentations into hard

• AC-move(AC1, AC2, AC3)를 조합한 substitution을 단일 supermove로 정의하여 action space를 확장하되 state space를 축소
• 두 relator를 cyclic sequence로 취급하고 explicit cross-attention을 적용하는 Dual-Ring Transformer를 설계, PPO 알고리즘으로 학습
• exhaustive enumeration을 통해 length ≤19의 모든 AC-trivial presentation을 열거하여 AC-19 구축, 개선된 substitution 기반 classical search로 검증
• automorphism을 이용해 쉬운 presentation을 hard-but-solvable presentation으로 변환하는 기법과 ML 기반 generator-solver game을 결합해 AC-1M 구축
• Miller-Schupp family 벤치마크에 적용하여 신규 trivialization과 AC-equivalence 발견을 통한 미해결 클래스 축소 수행

Originality

• 기존에는 암묵적으로 다뤄지던 AC 탐색의 난이도 구조를 "Two-Hump"라는 명시적 현상으로 정식화하고 실증적으로 검증한 최초의 시도
• 여러 primitive move를 압축한 substitution을 RL의 action space로 재정의하는 아이디어와, 이를 처리하기 위한 도메인 특화 Dual-Ring Transformer(cyclic sequence + cross-attention) 설계
• automorphism 기반 변환과 generator-solver self-play를 결합해 "hard-but-solvable" 데이터를 인위적으로 생성하는 novel data augmentation 전략
• AC-19, AC-1M이라는 최초의 대규모 공개 벤치마크 데이터셋 제공으로 후속 연구의 재현성과 비교 가능성 확보

Limitation & Further Study

• 발췌된 본문에서는 실험 세부 결과(정량적 성능 수치, 비교 baseline과의 정확한 gap)가 충분히 제시되지 않아 성능 향상의 규모를 정확히 판단하기 어려움
• Two-Hump 현상이 AC 문제 외 다른 수학적 탐색 문제(예: unknotting problem)에도 일반적으로 적용되는지는 추가 검증이 필요
• 550개 중 261개 동치류로 축소했다는 것은 여전히 다수의 미해결 사례가 남아있음을 의미하며, AC conjecture 자체의 완전한 해결과는 거리가 있음
• Dual-Ring Transformer의 확장성(더 긴 presentation, 더 큰 action space)에 대한 계산 비용 및 scalability 분석이 본문 발�취에서 명확히 드러나지 않음
• 후속 연구로 Two-Hump 현상의 이론적 원인 규명, 다른 조합적 탐색 문제로의 일반화, generator-solver game의 self-play 안정성 분석 등이 필요

Evaluation

총평: 난제인 AC conjecture에 대해 RL 기반 접근의 근본적 병목을 명확히 규명하고 이를 해결하는 알고리즘적·데이터적 혁신을 결합해 실질적인 수학적 진전과 유용한 공개 벤치마크를 함께 제공한 견고한 연구다. 다만 세부 실험 결과와 일반화 가능성에 대한 추가 검증이 뒷받침되면 더욱 설득력 있는 기여가 될 것이다.