Error Analysis of Discrete Flow with Generator Matching

Discrete flow models offer a powerful framework for learning distributions over discrete state spaces and have demonstrated superior performance compared to the discrete diffusion models. However, their convergence properties and error analysis remain largely unexplored. In this work, we develop a unified framework grounded in stochastic calculus theory to systematically investigate the theoretical properties of discrete flow models. Specifically, by leveraging a Girsanov-type theorem for the path measures of two continuous-time Markov chains (CTMCs), we present a comprehensive error analysis that accounts for both transition rate estimation error and early stopping error. In fact, the estimation error of transition rates has received little attention in existing works. Unlike discrete diffusion models, discrete flow incurs no initialization error caused by truncating the time horizon in the noising process. Building on generator matching and uniformization, we establish non-asymptotic error bounds for distribution estimation without the boundedness condition on oracle transition rates. Furthermore, we derive a faster rate of total variation convergence for the estimated distribution with the boundedness condition, yielding a nearly optimal rate in terms of sample size. Our results provide the first error analysis for discrete flow models. We also investigate model performance under different settings based on simulation results.

Discrete flow models provide a flexible framework for learning distributions over discrete data, but their theoretical guarantees are still limited. In particular, it remains unclear how accurately these models learn the target distribution and how their performance improves as more data become available. This work studies the error analysis and statistical convergence of discrete flow models. Under different assumptions, we establish slow and fast statistical convergence rates for the error of the learned distribution. These results help explain when discrete flow models can be expected to work reliably. Overall, our work provides a theoretical foundation for discrete flow models and supports their broader use in discrete generative modeling.