Resampling Whole Entities: Affinity-Defined Units for Fast Iterative Partial Refinement

Diffusion models generate an image by gradually denoising random noise. They can be made to fix their own mistakes after the fact. The procedure is to take a finished sample, add noise back to a few regions, and regenerate those regions while holding the rest fixed. Repeated many times, this verifier-free loop steadily raises the rate at which samples satisfy hard global constraints, such as valid Sudoku grids or correct polygon counts. The loop is slow, though. Inference-Time Scaling in Diffusion Models through Iterative Partial Refinement (IPR) needs about 50 iterations, roughly 13× the cost of one generation, to move hard Sudoku validity from 55.8% to 75.0%. It also picks the regions to regenerate uniformly at random from a fixed grid.

Our claim is that much of this cost comes from the shape of the regions being redrawn, and less from which regions get chosen. A mistake usually lives in a whole entity: a mis-drawn polygon, a duplicated digit, a patch of the wrong color. A grid patch cuts that entity in half. The frozen half then conditions the regenerated half back toward the same mistake. We propose to build the resampling units from the sample's own affinity structure, meaning groups of tokens that the denoiser's features mark as belonging together, whether they are adjacent or far apart. Each iteration then rewrites an entity consistently instead of nudging a fragment of it. We expect this to reach IPR's 50-iteration accuracy in several times fewer iterations and to remove IPR's collapse at large resampling ratios.

Core Claim and How It Differs

IPR's authors identify random region selection as a limitation and suggest targeting error regions. The obvious follow-up is therefore a better scoring rule: rank grid patches by uncertainty or constraint violation and resample the worst ones. That idea is not what we propose, and we treat it as the main competitor. Our variable is the partition itself. We hold the scoring rule fixed, random by default, and replace grid patches with affinity units. The claim is falsifiable on its own terms. If uncertainty-scored grid patches match affinity units at equal compute, the partition does not matter and our claim fails.

The affinity between tokens $i$ and $j$ of the current clean estimate is computed from the denoiser's intermediate features $f$ and token positions $p$:

$$w_{ij} = \exp\!\left(-\frac{\lVert f_i - f_j\rVert^2}{\sigma_f^2} - \frac{\lVert p_i - p_j\rVert^2}{\sigma_p^2}\right),$$

Here $\sigma_f$ and $\sigma_p$ set how fast affinity falls off with feature distance and with spatial distance. This is the bilateral weighting that Fully Automatic Video Colorization With Self-Regularization and Diversity. uses as a training loss to stop color bleeding across edges. It is also the color-affinity weighting that Edge-Aware Gradient Domain Optimization Framework for Image Filtering by Local Propagation uses to spread edits. Both papers supply the method. We reuse the affinity, not as a loss or a filter, but to decide which tokens are re-noised together.

Setting $\sigma_p$ large gives "non-local" units that group distant tokens with similar features. On Sudoku, such a unit gathers cells drawing the same digit, which is exactly the set that must be rewritten jointly to remove a duplicate. A small $\sigma_p$ gives local, segment-like units. Units come from clustering the k-nearest-neighbour graph of $w$, and the affinity is recomputed every iteration from features already produced by the last denoising pass. The extra cost is a sparse similarity computation and a clustering step, which we will time explicitly.

The design also differs from the other refinement work in the file. OmniRefiner: Reinforcement-Guided Local Diffusion Refinement also confines refinement to a region, but a user supplies that region as a bounding box. Edit-Your-Interest: Efficient Video Editing via Feature Most-Similar Propagation groups tokens by feature similarity, but it propagates edits feedforward and never closes a correction loop. From Prediction to Perfection: Introducing Refinement to Autoregressive Image Generation refines provisional tokens inside a fixed 1D raster window, so tokens that are 2D neighbours cannot inform each other. Our units are automatic, data-dependent, two-dimensional or non-local, and embedded in a closed resampling loop.

Research Program

We will reimplement IPR on its three constrained-generation tasks, using a mixed-noise-conditioned diffusion model and following its protocol: MNIST Sudoku in the HARD setting, Counting Polygons, and Even Pixels. We will confirm that our random-grid IPR reproduces the reported trends before making any comparison.

On top of that baseline we add affinity units in two forms, local bilateral and non-local feature, plus a mixture of the two. The resampling ratio $\alpha$ keeps its IPR meaning as the fraction of tokens re-noised per iteration, so the compute per iteration is matched.

The analysis has three parts. The first is iterations-to-target curves. The second is accuracy as a function of $\alpha$; our hypothesis is that affinity units stay stable at $\alpha = 0.5$, where IPR collapses, because the context destroyed lies inside an entity rather than around it. The third is a diagnostic: we measure how often a regenerated region returns to its pre-noise content, which is the "frozen half re-imposes the error" mechanism we posit. Comparing this re-imposition rate between grid patches and affinity units tests the explanation directly, not just the end metric.

As a stretch goal, we will apply the method to class-conditional ImageNet 256×256 with FID. We found no reported result on Lacuna for IPR on ImageNet, so that experiment is exploratory.

Baselines

The do-nothing reference is a single generation pass. IPR reports 55.8% valid Sudoku solutions (HARD) and 15.4% Number Match Accuracy on Counting Polygons for this setting.

The strongest existing method is random-grid IPR itself, which reports 75.0% Sudoku validity and 27.4% Number Match after 50 iterations at about 13× single-pass cost. We will run it with the same model, the same seeds, and an equal $\alpha$ sweep. Compute is matched in denoiser function evaluations and also reported as wall-clock time including our affinity overhead. Beating it means one of two things: reaching 75.0% Sudoku validity, or the reproduced equivalent, in at most 15 iterations; or exceeding its 50-iteration accuracy at 50 iterations.

The most dangerous competitor is uncertainty-scored grid IPR. It scores each grid patch by the disagreement between two independent denoising predictions and resamples the top patches. Its tuning budget for the score temperature is equal to ours for $\sigma_f$, $\sigma_p$, and the cluster count.

Three ablations isolate the key ingredient. The first uses affinity units with random scoring, which tests the partition alone. The second uses spatial-only units with $\sigma_f$ set to infinity, giving compact blobs that ignore features; this tests whether features matter beyond simply having irregular shapes. The third uses affinity units with uncertainty scoring, which tests whether the two ideas combine. We report best-of-N sampling with an oracle constraint checker at matched compute as an upper reference only, since it uses a verifier that IPR does not.

Why not just…?

Why not just score grid patches by uncertainty, as the IPR authors suggest? This is a real threat and may capture most of the gain. Our ablation grid separates the two factors, partition and score, at matched compute. If affinity units with random scoring do no better than grid patches, and uncertainty-scored grids match the full method, we will report that the scoring rule is what matters and drop the partition claim. The re-imposition diagnostic tells us in advance which outcome to expect. If uncertainty-scored grid patches still show high re-imposition, their gains are capped by the same mechanism.

Why not just run more iterations or tune $\alpha$? IPR already shows that this costs roughly linear compute, about 13× at 50 iterations, and that large $\alpha$ destroys needed context. Our iterations-to-target and $\alpha$-sensitivity curves compare the two methods directly on that axis.

Why not apply a bilateral filter or CRF after one pass? Towards Learning Structure via Consensus for Face Segmentation and Parsing argues that inference-time CRFs are slow. More fundamentally, smoothing can make a region locally coherent, but it cannot change a wrong digit or a missing polygon. We include filtered single-pass outputs to show this on the global-constraint metrics.

Why not use a bigger model or more denoising steps? The file contains no evidence that scale fixes these constraint failures. Idea2Img: Iterative Self-refinement with GPT-4V for Automatic Image Design and Generation finds that the stronger generator in its study (SDXL) gains +26.9% win rate from iteration, so refinement still pays off at that level. We will include a doubled-step single pass at matched compute.

Decisive Checks

The proposal succeeds if three things hold. Affinity units with random scoring must reach random-grid IPR's 50-iteration Sudoku and polygon accuracy in substantially fewer iterations. They must remain stable at $\alpha = 0.5$. And they must show a lower re-imposition rate than grid patches.

The proposal fails if uncertainty-scored grids explain the gain. It also fails if affinity units underperform on Even Pixels or texture-rich ImageNet images. That second failure is a known risk: the Edge-Aware paper reports that color affinity diverges from semantic boundaries, and Edit-Your-Interest reports that feature matching merges identical instances.