Error Analysis of Discrete Flow with Generator Matching
This work provides foundational theoretical insights for researchers in generative modeling, addressing a gap in error analysis for discrete flow models, though it is incremental as it builds on existing concepts like generator matching.
The authors tackled the lack of theoretical understanding of discrete flow models by developing a unified stochastic calculus framework to analyze their convergence and error properties, deriving non-asymptotic error bounds for distribution estimation and showing that discrete flow avoids truncation errors present in discrete diffusion models.
Discrete flow models offer a powerful framework for learning distributions over discrete state spaces and have demonstrated superior performance compared to the discrete diffusion model. 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. Specifically, we derive the KL divergence of two path measures regarding two continuous-time Markov chains (CTMCs) with different transition rates by developing a novel Girsanov-type theorem, and provide a comprehensive analysis that encompasses the error arising from transition rate estimation and early stopping, where the first type of error has rarely been analyzed by existing works. Unlike discrete diffusion models, discrete flow incurs no truncation 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. Our results provide the first error analysis for discrete flow models.