Peel, Guess, and Backtrack: Stopping Sets as a Model of Masked-Diffusion Latency

A masked diffusion model generates text or other discrete data by starting from a sequence of blanks and filling in many positions per step. It is fast only when many positions can be filled at once. Filling them at once is safe only when each position is already pinned down by what has been revealed. Coding theory has a precise account of when this kind of parallel filling-in must stop. A "peeling decoder" for erased bits recovers any bit that is the only unknown in some parity equation. It stalls exactly when the remaining unknowns form a stopping set: a group of positions in which every constraint touching the group touches it at least twice, so no single position is determined. We propose to treat masked-diffusion sampling on structured problems as peeling plus occasional forced guesses. The key consequence is that errors in a well-trained model originate almost entirely at the guesses, so repair should undo the guesses and everything that followed from them, not random regions or the places where a contradiction happens to show up.

The practical payoff concerns iterative refinement latency. Current samplers either spend many small sequential steps to avoid errors from filling dependent positions together, or they correct errors after the fact by re-noising random regions many times. The best verifier-free version of the latter costs about 13 times a single generation. A sampler that knows when it is peeling and when it is guessing can take large parallel steps through the peelable stretches, commit single guesses at stalls, and on failure re-open only the "decision cone" of a bad guess. That is cheaper than blanket re-noising and more targeted than repairing the visible symptom.

Core Claim

On data whose structure is a sparse set of constraints (codewords of a sparse code, Sudoku, satisfiability, arithmetic puzzles), the number of sequential model calls a masked-diffusion sampler needs is governed by two quantities. The first is $R$, the number of peeling rounds: steps in which at least one masked position has a near-deterministic conditional given the revealed context. The second is $D$, the number of decimations: forced commitments made when the masked set contains a stopping set and no position is determined. Writing $N$ for the number of denoiser forward passes,

$$N \approx R + D \ll L,$$

where $L$ is sequence length. The form follows because each peeling round can commit all determined positions together at no sampling-error cost, and each stall needs at least one commitment before peeling can resume. We further claim that sampling errors concentrate at the $D$ decimation points. When a later contradiction appears, the cheapest effective repair is to re-mask a wrong decimation together with the positions peeled after it. We call that set its decision cone.

The claim borrows its vocabulary from coding theory, but it can be checked: on synthetic sparse-code data, $R$, $D$, stopping sets and cones are exactly computable and can be compared against what a learned denoiser actually does.

Relation to Prior Work

The coding-theory side motivates the model. Tree-Structure Expectation Propagation for LDPC Decoding over the BEC characterises the peeling stall as a complete halt even when the equations are globally solvable. Good Concatenated Code Ensembles for the Binary Erasure Channel and Stopping set analysis of repeat multiple-accumulate codes establish that the size of the smallest stopping set, not minimum distance, limits iterative decoding. The latter also warns that locally sensible structural choices can create more small stopping sets. We read this warning as a constraint on design: a greedy "easiest token first" order will tend to steer the sampler into a dense core where every remaining position is doubly constrained.

The method we reuse for leaving a stall is decimation. Learned Decimation for Neural Belief Propagation Decoders pins the least reliable bit, branching over both values or predicting one, and recovers 0.3 to 0.7 dB on a (128, 64) code. Its list version branches as $2^{n_D}$. We keep the single-path commitment but replace branching with deferred, targeted backtracking: we only revisit a guess if a contradiction later implicates it. The boosting work of Boosting Learning for LDPC Codes to Improve the Error-Floor Performance and Boosted Neural Decoders supplies a second idea we test: train specifically on failure states. Our version trains a small repair head only on stalled or contradicted sampler states.

Three diffusion papers define the territory we enter, and each leaves the specific gap we target.

Adaptation to Intrinsic Dependence in Diffusion Language Models proves randomized batch-size schedules achieve error $\tilde{O}(\mathrm{TC}/K)$ or $\tilde{O}(\mathrm{DTC}/K)$ and tests on Reed–Solomon codes. It chooses positions uniformly at random and asks the user to choose between two schedules in advance. Our sampler instead chooses batch size online from whether the state is peelable. We note that Reed–Solomon data is a degenerate case for our model: any $d$ positions are jointly independent and the rest are then determined, so $D=0$ and $N=2$. This is exactly why we add sparse-code data, where stopping sets are nontrivial.

Adaptive Order Policies for Masked Diffusion learns a per-token unmasking policy. It reports that scaling the policy to a transformer did not help and that the policy cannot re-mask. Our reading is that the missing information is not more per-token capacity but whether a stall has been reached and which earlier commitments a conflict depends on.

Inference-Time Scaling in Diffusion Models through Iterative Partial Refinement shows random re-noising lifts MNIST Sudoku HARD from 55.8% to 75.0%. It does so at roughly 13 times the compute, is sensitive to the re-noised fraction, and its authors flag informed selection as open. Decision-cone re-masking is a specific answer to that open question.

Beyond Autoregression uses a fixed easy-first top-k schedule and supplies benchmarks. We treat it as the naive structured reference.

Research Program

The work has three parts.

The first part is a measurement study on data where ground truth is exact. We train masked-diffusion denoisers on the uniform distribution over codewords of sparse parity-check codes of increasing length, including codes structured like the CCSDS (128, 64) code. For each sampling trajectory we compute exactly:

  • whether the masked set contains a stopping set,
  • the realised $R$ and $D$,
  • which committed positions were determined versus guessed,
  • how sampling error (KL to the uniform-over-code distribution, and the rate of emitting non-codewords) is distributed across peeling commitments versus guesses.

The prediction is falsifiable. If a large share of errors come from peeled positions, the "errors originate at guesses" premise fails and the decision-cone repair loses its rationale.

The second part builds the sampler, which needs no constraint graph at inference. A position counts as determined when the denoiser's top-class probability exceeds a threshold $\tau$. A stall is declared when no masked position passes. At a stall the sampler commits one guess, the lowest-entropy masked position, and logs it as a decision. It tags every position committed in subsequent peeling rounds with that decision, which yields an over-approximate decision cone from the step history alone.

Repair is triggered in one of two ways. The first trigger uses no verifier: the denoiser, re-queried on a committed position with that position masked, disagrees with it. The second trigger is a cheap task checker (a Sudoku or clause checker). When repair fires, the sampler re-masks the most recent decision implicated in the conflict together with its cone, flips or resamples the guess, and resumes peeling. On tasks with a known constraint graph we also compute the exact cone (positions whose peeling depended on the decision) as an oracle ablation.

The third part is a boosted repair head, used only if the second part leaves headroom. We collect sampler states that stalled or contradicted, the analogue of uncorrected vectors. On these alone we train a lightweight head that predicts which logged decision to undo. This replaces the "most recent decision" rule, in the spirit of the boosting papers.

Baselines

The naive reference is fixed-step easy-first top-k unmasking as in Beyond Autoregression. We run it at several step counts $K$ with the same denoiser, which traces an accuracy-versus-forward-passes curve. Beating it means a strictly better curve: higher accuracy at equal passes, or equal accuracy at fewer.

The strongest ordering baseline is the learned policy of Adaptive Order Policies for Masked Diffusion. That paper reports 90.9% on 3-SAT with joint policy–denoiser training, against 76.0% for the margin heuristic and 88.8% for the baseline denoiser. On 9×9 Sudoku it reports 92.87% for joint training and 88.67% for the margin heuristic. It is the strongest competitor because it is the only method in the file that adapts ordering to the instance. We reimplement it on our denoisers with the same training budget and report its accuracy at matched forward passes. Our sampler uses a frozen denoiser, so the fair primary comparison is against the policy-only variant, with joint training reported separately. Beating it means exceeding policy-only accuracy at equal passes on 3-SAT and Sudoku, and approaching the joint-training numbers without retraining the denoiser.

The strongest refinement baseline is random partial refinement from Inference-Time Scaling in Diffusion Models through Iterative Partial Refinement, which reports a 75.0% valid-solution rate on MNIST Sudoku HARD after 50 iterations, from a 55.8% start. We run it with its re-noised fraction swept, select that fraction on a validation split, and give it exactly the forward-pass budget our repair loop consumes. Beating it means reaching 75.0% on that benchmark with substantially fewer than its roughly 13× passes, or exceeding it at equal passes.

Three ablations isolate the key ingredient:

  • The sampler without repair, i.e. threshold peeling with a single-guess fallback.
  • Repair that re-masks a random set of the same size as the decision cone.
  • Repair that re-masks the cells of violated constraints, the obvious syndrome-guided alternative.

The oracle exact cone gives an upper bound. A classical symbolic solver is reported for Sudoku and 3-SAT only as a ceiling, not a competitor, because the scientific question is how a learned generator should spend its passes.

Why not just…?

Why not just use more, smaller steps? Setting $K$ close to $L$ removes most parallel-unmasking error, but it throws away the latency advantage that motivates diffusion samplers. That loss is what Adaptation to Intrinsic Dependence in Diffusion Language Models identifies as the problem. The accuracy-versus-passes curve of the naive baseline directly measures this trade-off, and our claim is that a curve following $R + D$ dominates it.

Why not just commit everything above a confidence threshold and fall back to the top token when nothing qualifies? This is a genuine threat: it is essentially the first two-thirds of our sampler. We therefore treat it as an ablation, not a rival. If it matches the full method, the contribution shrinks to the measurement study plus the explanation of why it works. Novelty in the method then rests on decision-cone repair, and the no-repair ablation settles how much repair adds.

Why not just re-mask the cells in violated constraints? Violated constraints show where a contradiction surfaced, not where it began. Under the peeling model, a wrong guess propagates through determined commitments and can produce a violation far from its origin. The constraint-cell ablation tests this directly against cone repair at matched re-masked set size and passes. If the two tie, the decision-cone story is unnecessary for these tasks, and we would report that.

Why not just tune the random re-noising fraction? Random partial refinement is already tuned in our comparison. The concern its authors raise is that any fixed fraction either destroys useful context or misses the error. The same-size random re-masking ablation separates "re-mask fewer positions" from "re-mask the right positions."

Proposed Experiments

The decisive check is on synthetic sparse-code data. Measured forward passes should track the exactly computed $R + D$ across code lengths and denoiser qualities. Most invalid outputs should trace back to a decimation step. Exact-cone repair should restore validity at a cost close to the cone size.

We then move to:

  • 3-SAT and 9×9 Sudoku, compared against the adaptive-order numbers above;
  • MNIST Sudoku HARD, compared against the 75.0% partial-refinement result at matched compute;
  • 4-digit Countdown, where Beyond Autoregression reports 91.5%, as a case where constraints are implicit and only the verifier-free trigger applies.

Across all tasks we report three things: accuracy versus denoiser forward passes, the fraction of passes spent on repair, and how the logged-cone heuristic compares with the oracle cone.

The proposal fails cleanly in two ways. Either errors do not concentrate at guesses, or cone repair does no better than random or constraint-cell re-masking of the same size. Either outcome would itself tell us how far the stopping-set picture describes learned samplers.