Scramble Inversion as Discrete Denoising Diffusion: A Matched-Compute Study on the Rubik's Cube Group
Aamer Khani · Zenodo (CERN European Organization for Nuclear Research) · 2026
Solving the Rubik's Cube with learned heuristics is conventionally framed as reinforcement learning: deep approximate value iteration (DAVI) learns a cost-to-go function that guides search, as in DeepCubeA. We study an alternative framing in which cube solving is discrete denoising diffusion on a Cayley graph: the forward (noising) process scrambles the solved state with random generator moves under a linear depth schedule, and a denoiser is trained by cross-entropy to predict the inverse of the last scramble move -- the exact analogue of epsilon-prediction. Solving is reverse-process sampling, optionally sharpened by beam search. The training objective coincides with the self-supervised scramble-inversion objective of Takano (2023); our contributions are the diffusion-process formalization, a controlled matched-architecture, matched-hardware comparison against DAVI, and an evaluation protocol with unusually strong guarantees: an exact breadth-first-search oracle over the entire 2x2x2 group (3,674,160 states) and mechanical replay verification of every claimed solution. On a single consumer GPU, the denoising objective is 5x cheaper per iteration than DAVI, reaches 99.989% greedy (search-free) solve rate over the full 2x2x2 state space where DAVI reaches 77.7%, and solves 1000/1000 fully scrambled 3x3x3 cubes after 4.9 hours of training versus 13.9 hours for DAVI at the same solve rate. Exact-oracle diagnostics reveal complementary error structure: the value function degrades monotonically with distance-to-goal, while the denoiser's per-move accuracy dips precisely where the scramble-length posterior is most ambiguous. Ablations over the noise schedule and timestep conditioning support the diffusion interpretation: a linear (uniform) schedule suffices, and conditioning on the timestep is unnecessary because the group state determines its own noise level. Code and full logs are released for reproducibility.