--- license: apache-2.0 tags: - masked-diffusion - discrete-diffusion - constraint-satisfaction - sudoku - recurrent-transformer - from-scratch --- # Recurrent Masked Diffusion for Constraint Satisfaction **Constraint propagation is an iterative algorithm; masked diffusion models are trained as fixed-depth denoisers. Making the denoiser recurrent — one weight-shared block applied many times, supervised at every application — reaches 99.70% on hard Sudoku with 212k parameters, where a 37.9M-parameter feed-forward denoiser reaches 88.90%.** Trained from scratch. No pretrained weights, no pretrained tokenizer. Code: https://github.com/GIND123/MSML612 ## Benchmark 1,000 held-out minimal Sudoku puzzles, 20–30 clues (mean 24.4). Uniqueness verified after **every** cell removal; train/test solutions disjoint even up to digit relabelling. Metric: board accuracy, all 81 cells correct. ## Results | method | params | 1 pass | best | |---|---|---|---| | constraint propagation (no search) | – | – | 3.00% | | greedy MRV | – | – | 5.90% | | autoregressive prefix-LM | 2.4M | – | 0.30% | | direct recurrent classifier* | 212k | 10.5% | 31.00% | | recurrent, no input injection (batch 64) | 212k | – | 94.10% | | feed-forward diffusion, MDLM | 37.9M | 4.40% | 88.15% | | feed-forward diffusion, schedule-matched | 37.9M | 40.10% | 88.90% | | 32 distinct layers, no weight sharing | 6.34M | 70.20% | 94.50% | | recurrent diffusion, MDLM | 212k | 87.35% | 96.55% | | recurrent, no deep supervision | 212k | 93.35% | 97.75% | | **recurrent diffusion, full method** | **212k** | **97.35%** | **99.70%** | | full backtracking search | – | – | 100% (423 nodes) | \* Our reimplementation of the published recurrent classifier reaches 31% against their reported 99.5%. **That is a failed reproduction on our side, not evidence against their method**, and it is not used as a comparison. ## Ablations **Compare only within a batch size.** An earlier version of this card pooled a 32-layer run at batch 256 (94.50%) with one at batch 64 (83.40%) into a single "88.95%", and drew two conclusions from the artefact. Both were wrong and are corrected here. **At batch 256:** | step | params | board | gain | |---|---|---|---| | feed-forward, d=512, 12 layers | 37.9M | 88.90% (n=2) | – | | feed-forward, d=128, 32 layers | 6.34M | 94.50% (n=1) | **+5.60** | | + weight sharing, d=128, 1 layer × 32 | **212k** | **99.70%** (n=2) | **+5.20** | Parameters fall monotonically, accuracy rises monotonically: 37.9M → 6.34M → 212k against 88.90% → 94.50% → 99.70%. **At batch 64, injection off on both sides:** | step | params | board | gain | |---|---|---|---| | feed-forward, d=128, 32 layers | 6.34M | 83.40% (n=1) | – | | + weight sharing | **212k** | **94.10%** (n=2) | **+10.70** | **Corrections.** ~~"Depth alone is worth nothing (+0.05)"~~ — wrong and backwards; at matched batch size the deeper, narrower, 6× smaller model gains **+5.60**. ~~"Input injection is worth +5.60"~~ — **retracted**, see below. Removing either from the full method: deep supervision **−1.95**, schedule matching **−3.15**. ## Recurrence extrapolates past its training depth Trained at R = 32, evaluated elsewhere without retraining: | R | 1 | 4 | 8 | 16 | **32** | **64** | 128 | |---|---|---|---|---|---|---|---| | board | 0.10% | 48.40% | 82.00% | 92.40% | **98.30%** | **99.40%** | 99.10% / 39.70% | 2× extrapolation is reliable; 4× collapses on one seed. ## The instructive failure Both non-diffusion baselines reach **lower training loss** than our method and solve almost nothing — AR at 0.0486 loss gives 0.30% boards, direct all-cell supervision at 0.0722 gives 55%. AR's errors compound unrecoverably; all-cell supervision is dominated by copying the given clues. Low loss, no capability. ## Honest limits - Published comparison is across **different puzzle distributions**: our 20–30 clue range sits inside the Recurrent Transformer's 17–34 but excludes the hardest 17-clue instances, so 99.70% at 212k reads as *competitive with* their 99.5% at 211k, not better. - **Input injection is retracted as a contribution.** In a matched test — identical architecture, batch, and step count, with R-MDM's step embedding on both sides — it is worth **+0.05 points** (96.85% → 96.90%, best decode). The previously claimed +5.60 compared an injection-ON arm at batch 256 against an injection-OFF arm at batch 64; it measured batch size. The single injection-ON seed lands inside the two-seed injection-OFF range at five of six decoding budgets. All three arms stopped at step 80k of 110k on a wall-clock limit, and the ON side is n=1; we could not add seeds, as the allocation had 3,030 billing-minutes left against ~3,600 for one run. - The SATNet split is not used: constraint propagation alone solves 100% of it. ## Negative results, reported - **Any-budget conditioning fails.** Sampling the decoding budget during training is worse than the baseline at every budget on graphs (−4.2 at K=8, −31.7 at K=15) and destroys 20-digit addition outright (0.0% vs 99.9%), because it dilutes `t = 1` training 4.5×. - **The entropy budget is mixed** — competitive on graphs, loses to fixed-`K` on text8. - **Half the QM9 gap was our own representation.** Giving the baseline the atom count that DiGress samples first lifts it from 77.5% to 89.1%; the gap narrows from 22.2 to 10.7 points. - **16-digit addition is unsettled** — a compute-matched baseline reaches 100% on one seed of two. - **Our Sudoku prediction was refuted by our own framework.** We registered that entropy-budgeted decoding would beat fixed-`K` on Sudoku by the largest margin in the project. It loses on every arm by 0.35–1.40 points. The prediction contradicted the bound: Sudoku has a unique answer, so `TC = 0` and there is nothing for a mode-(ii) fix to repair. ## Audit `src/audit.py`: 46 assertions across 11 sections, 0 failures. It caught two live bugs that would each have produced confidently wrong numbers — a sampler emitting the absorbing state so decoding silently stalled, and an aromatic-bond encoding that made round-trip validity on *real* molecules 92.65% instead of 100%.