Parallel Causal Denoising: From Exactness to Batch Selection

Parallel generation reduces waiting in sequence models, but denoisers restricted to current and earlier positions can distort relationships when dependent positions are generated together. For Gaussian data and a fixed optimal denoiser, we establish a necessary and sufficient condition for exact generation when noise levels decrease continuously. We also quantify the final generation error, revealing why correlation alone can select the wrong grouping: it ignores how much variation remains after using earlier context. We use this analysis to develop a batching method with a near-optimality guarantee. For a specified Gaussian family with weak correlations only between adjacent positions, its final distributional error (KL divergence) is at most 1% above the optimum at the same batch count. We extend selection to trained linear denoisers using their actual sampling updates at the chosen computational budget. Gaussian experiments support the selection guarantee and show a median 5.07-fold speedup in evaluating and selecting complete groupings over a baseline using numerical integration.