Blame for README.md

---
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%.