Skip to content

Schedule optimization for tau-leaping in masked discrete diffusion

Sep 2026 · arXiv.org · Vol abs/2609.21960 · 1 citation · 29 references
Mathematics Computer Science

TL;DR

This work establishes an exact integral representation of $\varepsilon_\text{fact}$ separating the schedule from the target's dependence structure, summarized by a dependence density $\rho$, which yields recursive stationarity equations for optimal schedules and allows us to quantify how estimation errors in $\rho$ affect schedule selection.

Abstract

Masked diffusions are popular generative models for discrete distributions. Unlike standard autoregressive sampling, they reveal several coordinates in parallel, approximating each block's joint conditional law by a product of one-coordinate conditionals. The resulting procedure, usually called tau-leaping, reduces computational cost but introduces a factorization error ($\varepsilon_\text{fact}$), even with perfectly learned predictors. We study the resulting tradeoff between generative accuracy and computational cost, focusing on how to choose a denoising schedule to minimize $\varepsilon_\text{fact}$ for a fixed sampling budget. To do so, we establish an exact integral representation of $\varepsilon_\text{fact}$ separating the schedule from the target's dependence structure, summarized by a dependence density $\rho$. This representation yields recursive stationarity equations for optimal schedules and allows us to quantify how estimation errors in $\rho$ affect schedule selection. As the dimension $N$ and sampling budget grow, we characterize the optimal schedule and quantify the cost of random block sizes relative to a deterministic planner. We highlight a fundamental dichotomy: if $\rho$ converges uniformly to a strictly positive continuous profile as $N\to\infty$, schedule optimization can only improve the leading constant of $\varepsilon_\text{fact}$, while if $\rho$ degenerates, schedule optimization can improve the asymptotic order. Examples based on stationary processes and exchangeable mixtures illustrate these regimes.

View source

Similar papers

#machine learning Preprint Oct 2026

Diffusion Removes Langevin's Conditioning Dependence: A Sharp Gaussian Analysis

Despite their empirical success, why diffusion models overcome the bottlenecks of classical score-based samplers remains unclear. In this work, we leverage Gaussian distributions to isolate this phenomenon. We establish 2-Wasserstein convergence bounds for optimized hyperparameters, showing that diffusion processes ach...

Adam Perbost, F. Bach, Pierre Marion · 0 citations
#machine learning Preprint Oct 2026

Transformer-Based Masked Diffusion Models Provably Learn Distributions with Latent Structure

This work establishes end-to-end statistical guarantees showing that transformer-based MDMs learn structured distributions with a sample complexity governed by their latent structure through mixtures of hidden Markov trees, which capture latent dependencies within components and heterogeneity across components.

Jing-Da Wu, Chang-Xiao Cai · 1 citation
#machine learning Preprint Oct 2026

Finite-Sample Guarantees for Fully Discrete Conditional Diffusion Models

The approach aligns the score-training objective with the sampling grid, allowing statistical estimation and numerical discretization errors to be analyzed together, and establishes finite-sample guarantees for conditional diffusion models learned from data and implemented with finitely many denoising steps.

Qiu-Yun Zhu · 0 citations
#machine learning Preprint Oct 2026

Sample complexity bounds for categorical Markov random fields via Discrete Diffusions

This work studies the score learning error from finite data and derive optimal sampling guarantees with explicit dependence on the vocabulary size, the interaction order of the MRF, and the sample size, and trains a single score network across uniform noise levels while leaving the sampling discretization to be chosen...

Shivam Kumar, Nabarun Deb · 0 citations
#machine learning Preprint Oct 2026

IDRF: Inverse-Distilled Reward Fine-tuning of Masked Discrete Diffusion Models

IDRF, a framework for reward fine-tuning of few-step masked discrete diffusion generators, view few-step generation as a finite-horizon Markov decision process and optimize reward with a clipped policy-gradient objective over the student's trajectories.

V. Gromadskii, David Li, Samson Gourevitch et al. · 1 citation

Related blog posts

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.