A Theoretical Analysis of Discrete Flow Matching Generative Models

Title: 1 Introduction
ArXiv: 2509.22623v1
Version: v1
Sections: 160
Estimated tokens: 81.4k

## Contents
- 1 Introduction
  - Organization.
  - Notation.
- 2 Preliminaries
- 3 Error Bounds for Discrete Flow Matching
  - Theorem 3.1 (Error Bound for Discrete Flow Matching) .
  - Proof.
  - Remark 3.1 (Comparison with Flow Matching Error Bounds) .
  - Roadmap of Our Theoretical Results.
- 4 Approximation Error for Discrete Flow Matching
  - 4.1 Extending the Velocity Field
    - Definition 4.1 (Hölder Class) .
    - Assumption 4.1 .
    - Remark 4.1 .
    - Lemma 4.1 (Discrete-to-Continuous Functional Extension) .
    - Proof.
    - Remark 4.2 .
  - 4.2 Discrete Flow Matching Approximation
    - Theorem 4.1 (Approximation Theorem for Discrete Flow Matching) .
    - Proof.
- 5 Velocity and Distribution Estimations
  - 5.1 Velocity Estimation
    - Theorem 5.1 (Velocity Estimation with Discrete Flow Matching Transformer) .
    - Proof.
  - 5.2 Distribution Estimation
    - Theorem 5.2 (Discrete Flow Matching Velocity Estimation with Transformer) .
    - Proof.
- 6 Discussion and Conclusion
- 7 Conclusion
  - Related Work: Statistical Rates for Generative Models.
- Acknowledgments
- Appendix
  - Appendix A Related Work
    - Discrete Generative Models and Discrete Flow Matching.
    - Transformer Universal Approximation.
  - Appendix B Supplementary Background: Transformer Block
    - B.1 Transformers
      - Definition B.1 (Transformer Block) .
      - Definition B.2 (Transformer Network Function Class) .
      - Definition B.3 (Reshape Layer) .
      - Definition B.4 (Transformer Function Class With Reshape Layer and Parameter Bound) .
    - B.2 Lipschitzness of Transformer Network
      - Preparations of Lemma ˜ B.7 .
        - Lemma B.1 .
        - Proof.
        - Lemma B.2 (Lipschitzness of 𝖱𝖾𝖫𝖴 ( ⋅ ) \mathop{\mathsf{ReLU}}(\cdot) ) .
        - Proof.
        - Lemma B.3 (Lipschitzness of FFN) .
        - Proof.
        - Lemma B.4 (Lipschitzness of Functions with Bounded Jacobian; Modified from Lemma A.6 of (Edelman et al., 2022 ) ) .
        - Proof.
        - Lemma B.5 (Lipschitzness of Softmax ( ⋅ ) \mathop{{\rm Softmax}}(\cdot) ; Modified from Corollary A.7 of (Edelman et al., 2022 ) ) .
        - Proof.
        - Lemma B.6 (Lipschitzness of Multi-Head Self-Attention) .
        - Proof.
      - Lipschitzness of Transformer.
        - Lemma B.7 (Lipschitzness of Transformer Block) .
        - Proof.
        - Remark B.1 (Near-Optimality of the Lipschitz Bound) .
    - B.3 Universal Approximation of Transformers
      - Background: Contextual Mapping.
        - Definition B.5 (Vocabulary) .
        - Definition B.6 (Tokenwise Separateness) .
        - Definition B.7 (Contextual Mapping) .
        - Lemma B.8 (Any-Rank Attention is ( γ , δ ) (\gamma,\delta) -Contextual Mapping, Lemma 2.2 of (Hu et al., 2024a ) ) .
        - Proof.
      - Universal Approximation of Transformer.
        - Theorem B.1 (Transformer Universal Approximation, Theorem H.2 of (Su et al., 2025 ) ) .
        - Proof.
      - Parameter Norm Bounds of Transformer Approximator.
        - Theorem B.2 (Parameter Norm Bound for Approximator Transformer, Modified from Lemma H.4 of (Su et al., 2025 ) ) .
        - Proof.
  - Appendix C Proof of Theorem ˜ 3.1
    - C.1 Preliminaries
      - Definition C.1 (Total Variation Distance) .
      - Lemma C.1 (Grönwall’s Inequality, (Gronwall, 1919 ) ) .
      - Lemma C.2 (Variation of Constants Formula for Error) .
      - Proof.
    - C.2 Main Proof of Theorem ˜ 3.1
      - Theorem C.1 (Error Bounds for Discrete Flow Matching) .
      - Proof.
      - Theorem C.2 (Error Bounds for Discrete Flow Matching with Factorized Velocity, Theorem ˜ 3.1 Restate) .
      - Proof.
  - Appendix D Proof of Lemma ˜ 4.1
    - D.1 Preliminaries
      - Lemma D.1 .
      - Proof.
    - D.2 Main Proof of Lemma ˜ 4.1
      - Lemma D.2 ( Lemma ˜ 4.1 Restate) .
      - Proof.
  - Appendix E Proof of Theorem ˜ 4.1
    - E.1 Preliminaries
      - Remark E.1 .
    - E.2 Auxiliary Lemmas
      - Lemma E.1 (Discrete-to-Continuous Functional Extension of Velocity under Mixture Path Setting, Modified from Lemma ˜ 4.1 ) .
      - Proof.
      - Lemma E.2 (Lipschitzness of Extension) .
      - Proof.
      - Lemma E.3 (Lipschitzness of Extension under Mixture Path Setting, Modified from Lemma ˜ E.2 ) .
      - Proof.
      - Lemma E.4 (Integral Lower Bound via Point-wise Magnitude) .
      - Proof.
      - Lemma E.5 (Point-wise Upper Bound via Integral Constraint) .
      - Proof.
    - E.3 Main Proof of Theorem ˜ 4.1
      - Theorem E.1 (
Approximation Theorem for Mixture Path Discrete Flow Matching, Theorem ˜ 4.1 Restate) .
      - Proof.
  - Appendix F Proof of Theorem ˜ 5.1
    - F.1 Preliminaries
      - Lemma F.1 (Modified from Remark E.2 of (Su et al., 2025 ) ) .
      - Proof.
    - F.2 Auxiliary Lemmas
      - Definition F.1 (Covering Number) .
      - Lemma F.2 (Lemma J.2 of (Hu et al., 2024b ) , Modified from Theorem A.17 of (Edelman et al., 2022 ) ) .
      - Proof.
      - Lemma F.3 (Covering Number Bound for Transformer Class, Modified from Lemma J.3 of (Hu et al., 2024b ) ) .
      - Proof.
      - Lemma F.4 (Covering Number Bound for Loss Function Class, Modified from Lemma L.3 of (Su et al., 2025 ) ) .
      - Proof.
      - Lemma F.5 (Generalization Bound, Modified from Lemma L.5 of (Su et al., 2025 ) ) .
      - Proof.
      - Lemma F.6 (Empirical Risk Bound, Modified from Theorem L.1 of (Su et al., 2025 ) ) .
      - Proof.
    - F.3 Main Proof of Theorem ˜ 5.1
      - Theorem F.1 (Mixture Path Discrete Flow Matching Velocity Estimation with Transformer, Theorem ˜ 5.1 Restate) .
      - Proof.
  - Appendix G Proof of Theorem ˜ 5.2
    - Theorem G.1 (Discrete Flow Matching Distribution Estimation with Transformer, Theorem ˜ 5.2 Restate) .
    - Proof.
  - Appendix H Approximation Theory for Discrete Flow Matching: General Case
    - H.1 Auxiliary Lemmas
      - Lemma H.1 (Lipschitzness of Extension, Lemma ˜ E.2 Restate) .
      - Proof.
      - Lemma H.2 (Point-wise Upper Bound via Integral Constraint, Lemma ˜ E.5 Restate) .
      - Proof.
    - H.2 Approximation Theory for Discrete Flow Matching
      - Theorem H.1 (Approximation Theorem for Discrete Flow Matching) .
      - Proof.
  - Appendix I Estimation theory for Discrete Flow Matching: General Case
    - I.1 Preliminaries
      - Lemma I.1 (Modified from Lemma ˜ F.1 ) .
      - Proof.
    - I.2 Auxiliary Lemmas
      - Lemma I.2 ( Lemma ˜ F.2 Restate, Lemma J.2 of (Hu et al., 2024b ) , Modified from Theorem A.17 of (Edelman et al., 2022 ) ) .
      - Proof.
      - Lemma I.3 (Covering Number Bound for Transformer Class, Modified from Lemma ˜ F.3 ) .
      - Proof.
      - Lemma I.4 (Covering Number Bound for Loss Function Class, Modified from Lemma ˜ F.4 ) .
      - Proof.
      - Lemma I.5 (Generalization Bound, Modified from Lemma ˜ F.5 ) .
      - Proof.
      - Lemma I.6 (Empirical Risk Bound, Modified from Lemma ˜ F.6 ) .
      - Proof.
    - I.3 Estimation Rates for Discrete Flow Matching
      - Theorem I.1 (Discrete Flow Matching Velocity Estimation with Transformer) .
      - Proof.
    - I.4 Discrete Flow Matching Distribution Estimation
      - Theorem I.2 (Discrete Flow Matching Distribution Estimation Rates) .
      - Proof.
  - References

### 1 Introduction

We provide a comprehensive theoretical analysis of Discrete Flow Matching (DFM), establishing rigorous error bounds and statistical convergence rates for training this emerging class of models.
Generative models for discrete data, such as text, proteins, and molecules, are central to modern machine learning.
Recently, discrete flow matching (Campbell et al., 2024; Gat et al., 2024) emerges as a powerful and flexible paradigm in these domains.
It learns a transformation from a simple prior distribution to a complex data distribution by parameterizing the dynamics of a Continuous-Time Markov Chain (CTMC).
A key advantage of this approach is its simulation-free training objective.
Instead of solving complex differential equations, discrete flow matching models learn the underlying velocity field that governs the probability path, leading to efficient and stable training.
This framework has achieved promising results in various applications, including video generation (Fuest et al., 2025), inverse protein folding (Yi et al., 2025), and graph generation (Qin et al., 2024).

Despite its rapid adoption and strong empirical performance, the theoretical foundations of discrete flow matching remain unexplored.
This creates a critical gap between practice and theory: How does the error in the learned velocity field translate to error in the final generated distribution? What are the expressive limits of the neural networks, like Transformers, used to parameterize these velocities? And how does the quality of the generated samples depend on the amount of training data? Without answers to these questions, it is difficult to understand the discrete flow matching method’s behavior, its fundamental limitations, or how to guide future improvements in a principled manner.

This paper addresses these gaps by providing the comprehensive theoretical analysis of end-to-end training for Discrete Flow Matching.
We focus on the popular setting of factorized velocities (Lipman et al., 2024) parameterized by the Transformer architecture (Vaswani et al., 2017; Gat et al., 2024), the major workhorse of modern generative AI.
Our analysis establishes a clear chain of guarantees connecting model design and data size to the quality of the resulting distribution.

Contributions. Our contributions are three-fold:

- •
Intrinsic Error Bounds for Discrete Flow Matching.
We establish a fundamental error bound intrinsic to the Discrete Flow Matching (DFM) framework.
Our analysis begins with the Kolmogorov equation ([2.3](https://arxiv.org/html/2509.22623v1#S2.E3)), which governs the relationship between a probability distribution and its underlying velocity field in a Continues Time Markov Chain [Section˜2](https://arxiv.org/html/2509.22623v1#S2).
We frame the problem as analyzing the discrepancy between the solutions to two systems of Kolmogorov ODEs ([Lemma˜C.2](https://arxiv.org/html/2509.22623v1#A3.Thmlemma2)): one for the true data distribution $p_{t}$ and its velocity field $u_{t}$, and the other for the estimated distribution $p_{t}^{\theta}$ driven by our learned velocity field $u_{t}^{\theta}$.
By applying Grönwall’s Inequality ([Lemma˜C.1](https://arxiv.org/html/2509.22623v1#A3.Thmlemma1)), we derive an explicit upper bound on the total variation distance between the true distribution $p_{t}$ and the estimated distribution $p_{t}^{\theta}$ in ([Theorem˜3.1](https://arxiv.org/html/2509.22623v1#S3.Thmtheorem1)).
This bound is intrinsic because it originates from the core discrete flow matching paradigm of modeling the velocity field rather than the distribution—an inherent source of error that exists irrespective of model architecture or data volume.
This result validates the intuition that a more accurate velocity field approximation yields a higher-fidelity generative model.
It provides a distribution convergence guarantee for any discrete flow matching implementation, including empirical works that do not use Transformers (Campbell et al., 2024; Gat et al., 2024; Lipman et al., 2024).
- •
Approximation Error Analysis.
We analyze the approximation error, proving that Transformer networks possess sufficient expressive power to approximate the ground-truth velocity fields with a controlled error rate.
A key challenge is that the existing universal approximation results for Transformers ([Appendix˜B](https://arxiv.org/html/2509.22623v1#A2)) limits to continuous functions, whereas our velocity field $u(x,t)$ is defined over a discrete space $x\in\mathcal{S}$.
We bridge this theoretical gap in [Lemma˜4.1](https://arxiv.org/html/2509.22623v1#S4.Thmlemma1) by first constructing a continuous extension, $\tilde{u}(x,t)$, that preserves the temporal smoothness of the discrete velocity function.
Building on this, we then derive an upper bound on the approximation error when using a Transformer estimator $u_{\theta}(x,t)$ to model the ground-truth velocity $u(x,t)$ ([Theorem˜4.1](https://arxiv.org/html/2509.22623v1#S4.Thmtheorem1)).
This result provides a formal justification for using Transformers to model discrete flows.
- •
Estimation Error Analysis.
We derive statistical convergence rates for the estimation error, which arises from learning the velocity field from a finite dataset.
Our analysis proceeds in two stages. First, leveraging our approximation error bounds from [Theorem˜4.1](https://arxiv.org/html/2509.22623v1#S4.Thmtheorem1), we analyze the velocity estimation error in [Theorem˜5.1](https://arxiv.org/html/2509.22623v1#S5.Thmtheorem1).
This result establishes a rate at which the Transformer-based velocity estimator converges to the true field as the number of training samples increases.
Second, we combine this velocity estimation error with the intrinsic error bound for discrete flow matching ([Theorem˜3.1](https://arxiv.org/html/2509.22623v1#S3.Thmtheorem1)) to derive a final upper bound on the distribution estimation error in [Theorem˜5.2](https://arxiv.org/html/2509.22623v1#S5.Thmtheorem2).
Together, these theorems provide a solid theoretical guarantee for discrete flow matching models implemented with Transformers, grounding existing empirical applications (Fuest et al., 2025; Qin et al., 2024; Yi et al., 2025) in a rigorous framework.

##### Organization.

[Section˜2](https://arxiv.org/html/2509.22623v1#S2) reviews the core concepts of discrete flow matching and the Transformer architecture.
[Section˜3](https://arxiv.org/html/2509.22623v1#S3) establishes our intrinsic error bound for the Discrete Flow Matching framework.
[Section˜4](https://arxiv.org/html/2509.22623v1#S4) provides an approximation error analysis for discrete flow matching implemented with Transformers.
[Section˜5](https://arxiv.org/html/2509.22623v1#S5) derives statistical convergence rates for both velocity and distribution estimation errors.
[Section˜7](https://arxiv.org/html/2509.22623v1#S7) summarizes our contributions and discusses their implications.
The appendix provides supplementary material and proofs.
[Appendix˜B](https://arxiv.org/html/2509.22623v1#A2) details the theoretical background on the expressive power of Transformers.
[Appendices˜C](https://arxiv.org/html/2509.22623v1#A3), [E](https://arxiv.org/html/2509.22623v1#A5), [F](https://arxiv.org/html/2509.22623v1#A6) and [G](https://arxiv.org/html/2509.22623v1#A7) contain detailed proofs of our main theorems.
[Appendices˜H](https://arxiv.org/html/2509.22623v1#A8) and [I](https://arxiv.org/html/2509.22623v1#A9) study approximation and estimation rates for generic DFM without the factorized velocity technique.

##### Notation.

We denote the index set $\{1,\ldots,I\}$ by $[I]$.
Let $x[i]$ denote the $i$-th component of a vector $x$.
Let $\mathbb{Z}$ denote integers and $\mathbb{Z}_{+}$ denote positive integers.
Given discrete probability distribution $P$ and $Q$, we denote the total variation distance between $P$ and $Q$ by $\text{TV}(P,Q)$.
Given a matrix $Z\in\mathbb{R}^{d\times L}$, $\|Z\|_{1}$ and $\|Z\|_{\rm F}$ denote the induced $1$-norm and the Frobenius norm.
For vectors $u,v\in\mathbb{R}^{d}$, the Bregman divergence induced by a strictly convex function $\Phi:\mathbb{R}^{d}\rightarrow\mathbb{R}$ is
$D(u,v):=\Phi(u)-\Phi(v)-(u-v)^{\top}\nabla\Phi(v).$
Let $\|\cdot\|_{1}$ and $\|\cdot\|_{2}$ be the $\ell_{1}$ and $\ell_{2}$ vector norms.
Let $\mathcal{S}=\{s_{1},\ldots,s_{N}\}$ be a finite state space. For each $t\in[0,1]$, let $f_{t}:\mathcal{S}\times\mathcal{S}\rightarrow\mathbb{R}$ be a scalar-valued function.
Then we define a vector-valued function $f_{t}(\cdot,x):\mathcal{S}\times[0,1]\rightarrow\mathbb{R}^{N}$, as
$f_{t}(\cdot,x):=[f_{t}(s_{1},x),\ldots,f_{t}(s_{N},x)]^{\top}.$

### 2 Preliminaries

In this section, we provide an high level review of discrete flow matching following (Lipman et al., 2024), and the transformer architecture (Vaswani et al., 2017).

Continues Time Markov Chain.
Consider the discrete data $x$ from state space $\mathcal{S}=\mathcal{V}^{d}$ where vocabulary $\mathcal{V}=\{1,\ldots,M\}$.
In this paper, we utilize a natural embedding $E:\mathcal{S}\hookrightarrow\mathbb{R}^{d}$ that maps each discrete token $j\in\mathcal{V}$ to its corresponding integer value as a real number..
For convenience, we view $\mathcal{V}=[M]$ as a subspace of $\mathbb{R}$.
The Continues Time Markov Chain (CTMC) (Norris, 1998) is a continuous stochastic process $(X_{t})_{t\geq 0}$ that models systems evolving over continuous time.
A defining characteristic of a Continues Time Markov Chain is the Markov property, meaning the system’s future state only depends on its current state, not on its past history.
Let $p_{t}$ denote the probability mass function (PMF) of $X_{t}$.
Then we define an unique Continues Time Markov Chain by specifying an initial distribution $p_{0}$
and rates function (velocity field) $u_{t}(y,x):\mathcal{S}\times\mathcal{S}\to\mathbb{R}$.
This function induces the probability transition kernel
$p_{t+h|t}$ as

$$ $\displaystyle p_{t+h|t}(y|x):=P(X_{t+h}=y|X_{t}=x)=\delta(x,y)+u_{t}(y,x)h+o(h),$ (2.1) $$

where $\delta(x,y)$ is the Kronecker delta function, equal to $1$ when $x=y$ and 0 otherwise.
The values $u_{t}(y,x)$, called rates or velocities, represent the instantaneous rate of transition from state $x$ to state $y$ at time $t$.
We define $u_{t}$ generates $p_{t}$ if there exists $p_{t+h|t}$ satisfying ([2.1](https://arxiv.org/html/2509.22623v1#S2.E1)) with probability path $(p_{t})_{t\geq 0}$.
For the total probability to sum to one, i.e., $\sum_{y}p_{t+h|t}(y|x)=1$, the rates function $u_{t}$ must satisfy the following conditions (rates conditions),

$$ $\displaystyle u_{t}(y,x)\geq 0\quad\text{for all}\quad y\neq x,\quad\text{and}\quad\sum_{y}u_{t}(y,x)=0.$ (2.2) $$

By the definition of transition kernel ([2.1](https://arxiv.org/html/2509.22623v1#S2.E1)), a rates function $u_{t}$ and an initial distribution $p_{0}$ define a unique probability path $p_{t}$ via the Kolmogorov Equation (Lipman et al., 2024, Theorem 12),

$$ $\displaystyle\derivative{p_{t}(y)}{t}=\sum_{x\in S}u_{t}(y,x)p_{t}(x).$ (2.3) $$

Finally, we simulate a sample trajectory $(x_{t})_{t\geq 1}$ with Euler method

$$ $\displaystyle P(X_{t+h}=y|X_{t}=x)=\delta(x,y)+u_{t}(y,x)h,\quad\text{with}\quad P(X_{0})=p_{0}(x).$ $$

Discrete Flow Matching.
Discrete Flow Matching (DFM) is a generative modeling framework that learns a transformation from a source distribution $p_{0}$ to a target distribution $p_{1}$ (Campbell et al., 2024; Gat et al., 2024; Lipman et al., 2024). The core principle is to first define a probability path $(p_{t})_{t\in[0,1]}$ that interpolates between $p_{0}$ and $p_{1}$. This path is induced by a Continuous-Time Markov Chain (CTMC) characterized by a velocity field $u_{t}$. The learning objective is to train a neural network $u_{t}^{\theta}$ to approximate this ground-truth velocity.
We train the model by minimizing the discrete flow matching loss, which measures the discrepancy between the ground-truth velocity $u_{t}$ and predicted velocities $u_{t}^{\theta}$ using a Bregman divergence $D(\cdot,\cdot)$ (see [Section˜1](https://arxiv.org/html/2509.22623v1#S1) for definition)

$$ $\displaystyle\mathcal{L}_{\text{DFM}}=\mathbb{E}_{t,X_{t}\sim p_{t}}\left[D(u_{t}(\cdot,X_{t}),u_{t}^{\theta}(\cdot,X_{t}))\right],$ $$

where the ground-truth velocity $u(\cdot,X_{t})$ (notation follows [Section˜1](https://arxiv.org/html/2509.22623v1#S1.SS0.SSS0.Px2)) satisfies the rate conditions in ([2.2](https://arxiv.org/html/2509.22623v1#S2.E2)).
A tractable method for constructing these paths and velocities is Conditional Discrete Flow Matching (CDFM) (Campbell et al., 2024; Gat et al., 2024), which introduces an auxiliary discrete random variable $Z$ over a space $\mathcal{Z}$ with PMF $p_{Z}(z)$.
The marginal probability path is defined as

$$ $\displaystyle p_{t}(x)=\sum_{z\in\mathcal{Z}}p_{t|Z}(x|z)p_{Z}(z).$ $$

As shown by (Lipman et al., 2024), if each conditional path $p_{t}(x|z)$ is generated by a velocity $u_{t}(y,x|z)$, the corresponding marginal velocity $u_{t}(x)$ is given by

$$ $\displaystyle u_{t}(x)=\sum_{z\in\mathcal{Z}}u_{t}(y,x|z)p_{Z|t}(z|x),\quad\text{where}\quad p_{Z|t}(z|x)=\frac{p_{t}(x|z)p_{Z}(z)}{p_{t}(x)}.$ $$

This leads to the CDFM loss, an objective based on the conditional velocity fields

$$ $\displaystyle\mathcal{L}_{\text{CDFM}}=\mathbb{E}_{t,Z\sim p_{Z},X_{t}\sim p_{t|Z}}\left[D(u_{t}(\cdot,X_{t}|Z),u_{t}^{\theta}(\cdot,X_{t}))\right].$ $$

Crucially, the CDFM and DFM objectives yield identical learning gradients (Lipman et al., 2024, Theorem 15), i.e., $\nabla_{\theta}\mathcal{L}_{\text{CDFM}}(\theta)=\nabla_{\theta}\mathcal{L}_{\text{DFM}}(\theta)$. This equivalence makes CDFM a powerful and efficient training strategy. In this paper, we instantiate the Bregman divergence as the squared $\ell_{2}$ distance.
Then the conditional flow matching loss takes the form

$$ $\displaystyle\mathcal{L}_{\text{CDFM}}=\mathbb{E}_{t,Z,X_{t}\sim p_{t|Z}}\left[\|u_{t}(\cdot,X_{t}|Z)-u_{t}^{\theta}(\cdot,X_{t})\|_{2}^{2}\right].$ (2.4) $$

Factorized Paths and Velocities.
For sequences of length $d$ over a vocabulary of size $M$, the velocity field $u_{t}(\cdot,x)$ must specify a transition rate to all $M^{d}$ possible states.
The model’s output is therefore a vector in $\mathbb{R}^{M^{d}}$.
This exponential scaling with sequence length makes the direct modeling of the velocity field intractable.
To overcome this challenge, we employ factorized velocities (Campbell et al., 2022, 2024; Gat et al., 2024), which decompose the velocity field as

$$ $\displaystyle u_{t}(y,x)=\sum_{i}\delta(y^{\macc@depth\@ne\macc@set@skewchar\macc@nested@a 111{i}},x^{\macc@depth\@ne\macc@set@skewchar\macc@nested@a 111{i}})u^{i}_{t}(y^{i},x),$ (2.5) $$

where $\delta(\cdot,\cdot)$ is the Kronecker delta and $\macc@depth\@ne\macc@set@skewchar\macc@nested@a 111{i}:=(1,...,i-1,i+1,...,d)$ denotes all indices except $i$. We then model each component $u^{i}_{t}(y^{i},x)$ with a neural network $u^{\theta,i}_{t}(y^{i},x)$, which outputs a vector in $\mathbb{R}^{M}$. This reduces the total output dimension to a tractable $d\cdot M$. Substituting the factorized velocity ([2.5](https://arxiv.org/html/2509.22623v1#S2.E5)) into the CDFM objective ([2.4](https://arxiv.org/html/2509.22623v1#S2.E4)) yields the following loss function

$$ $\displaystyle\mathcal{L}_{\text{CDFM}}=$ $\displaystyle\penalty 10000\ \mathbb{E}_{t,Z,X_{t}\sim p_{t|Z}}\left[\|u_{t}(\cdot,X_{t}|Z)-u_{t}^{\theta}(\cdot,X_{t})\|_{2}^{2}\right],$ ( By the definition of CDFM ( 2.4 ) ) $\displaystyle=$ $\displaystyle\penalty 10000\ \mathbb{E}_{t,Z,X_{t}\sim p_{t|Z}}\left[\sum_{y\in V^{d}}\sum_{i\in[d]}\delta^{2}(y^{\macc@depth\@ne\macc@set@skewchar\macc@nested@a 111{i}},X_{t}^{\macc@depth\@ne\macc@set@skewchar\macc@nested@a 111{i}})\left(u^{i}_{t}(y^{i},X_{t}|Z)-u^{\theta,i}_{t}(y^{i},X_{t})\right)^{2}\right],$ ( By ( 2.5 ) ) $\displaystyle=$ $\displaystyle\penalty 10000\ \mathbb{E}_{t,Z,X_{t}\sim p_{t|Z}}\left[\sum_{i\in[d]}\|u_{t}^{i}(\cdot,X_{t}|Z)-u_{t}^{\theta,i}(\cdot,X_{t})\|_{2}^{2}\right].$ (2.6) $$

To generate samples from the trained model (Campbell et al., 2024; Gat et al., 2024), we simulate the CTMC by applying coordinate-wise updates for each $i\in[d]$ using a discrete time step $h$

$$ $\displaystyle P(X_{t+h}^{i}=y^{i}|X_{t}=x)=\delta(x^{i},y^{i})+hu_{t}^{\theta,i}(y^{i},x).$ (2.7) $$

Mixture Paths.
Following (Gat et al., 2024; Lipman et al., 2024), we adopt mixture paths for our strategy for conditional generation.
By conditioning on the source-target pair $Z=(X_{0},X_{1})$, we construct a factorized conditional probability path $p_{t|0,1}(x|x_{0},x_{1})=\prod_{i}p^{i}_{t|0,1}(x^{i}|x_{0},x_{1})$, where each per-coordinate path interpolates between the source and target tokens

$$ $\displaystyle p^{i}_{t|0,1}(x^{i}|x_{0},x_{1})=\kappa_{t}\delta(x^{i},x_{1}^{i})+(1-\kappa_{t})\delta(x^{i},x_{0}^{i}).$ $$

Here, $\delta(\cdot,\cdot)$ is the Kronecker delta and $\kappa_{t}$ is a monotonically increasing smooth function that satisfies the boundary conditions

$$ $\displaystyle\kappa_{0}=0,\quad\kappa_{1}=1,\quad\text{and}\quad\derivative{\kappa_{t}}{t}>0\quad\text{for}\quad t\in(0,1).$ $$

The conditional factorized velocity field that generates this per-coordinate path takes the form

$$ $\displaystyle u_{t}^{i}(y^{i},x^{i}|x_{0}^{i},x_{1}^{i})=\frac{\dot{\kappa_{t}}}{1-\kappa_{t}}[\delta(y^{i},x_{1}^{i})-\delta(y^{i},x^{i})].$ (2.8) $$

We parameterize the velocity $u^{i}_{t}$ with a model $u_{t}^{\theta,i}$.
The model is trained to match the ground-truth velocity for each coordinate $u^{i}_{t}$, resulting in the following CDFM loss objective

$$ $\displaystyle\mathcal{L}_{\text{CDFM}}=\mathbb{E}_{t,X_{0},X_{1},X_{t}\sim p_{t|X_{0},X_{1}}}\left[\sum_{i\in[d]}\|\frac{\dot{\kappa_{t}}}{1-\kappa_{t}}[\delta(\cdot,X_{1}^{i})-\delta(\cdot,X_{t}^{i})]-u_{t}^{\theta,i}(\cdot,X_{t})\|_{2}^{2}\right],$ (2.9) $$

where $\delta(\cdot,z)$ denotes a one-hot vector in $\mathbb{R}^{M}$ corresponding to a token $z\in\mathcal{V}$.
For notational simplicity, we define $u(x,t):=u_{t}(\cdot,x)$ as the vector-value function representing the full velocity field for a state $x$ at time $t$.
This function maps the state-time space $S\times[0,1]$ to the velocity space $\mathbb{R}^{M^{d}}$.
Similarly, we apply this convention to the learnable model and their factorized counterparts: $u_{\theta}(x,t):=u_{t}^{\theta}(\cdot,x)$, $u^{i}(x,t):=u_{t}^{i}(\cdot,x)$, and $u^{i}_{\theta}(x,t):=u_{t}^{\theta,i}(\cdot,x)$.

This paper focuses on discrete flow matching (DFM) using factorized velocities and the mixture path construction, as these are most common choices in practice (Campbell et al., 2024; Gat et al., 2024; Lipman et al., 2024).
Given $n$ i.i.d training $\{x_{i}\}_{i=1}^{n}$ , the factorized empirical loss used to train the velocity model for coordinate $i_{0}$ is defined as:

$$ $\displaystyle\widehat{\mathcal{L}}^{i_{0}}_{\rm CDFM}:=\frac{1}{n}\sum_{i=1}^{n}\int_{t_{0}}^{T}\underset{X_{0}\sim p_{0},X_{t}\sim p_{t|x_{0}=X_{0},x_{1}=x_{i}}}{\mathbb{E}}\|\frac{\dot{\kappa_{t}}}{1-\kappa_{t}}[\delta(\cdot,x_{i}^{i_{0}})-\delta(\cdot,X_{t}^{i_{0}})]-u^{i_{0}}_{\theta}(X_{t},t)\|_{2}^{2}\differential t.$ (2.10) $$

Discrete Flow Matching Transformers.
We parameterize the velocity model $u^{\theta}_{t}$ using a Transformer architecture (Vaswani et al., 2017).
Due to space limits, we defer a detailed definition of the Transformer block and its theoretical properties to [Appendix˜B](https://arxiv.org/html/2509.22623v1#A2), including Lipschitzness and universal approximation.
We also illustrate the specific architecture used in our paper in [Figure˜1](https://arxiv.org/html/2509.22623v1#S3.F1).

### 3 Error Bounds for Discrete Flow Matching

Figure: Figure 1: Discrete Flow Matching (with Factorized Velocity) Network Architecture. Our model processes a discrete input $x\in\mathcal{S}$ and a continuous time $t\in[0,1]$ as input. Initially, embedding layer $E$ maps discrete tokens to continuous embeddings ([Section˜2](https://arxiv.org/html/2509.22623v1#S2)). Sequentially, the model concat the continues embeddings with the time variable. A reshape layer then structures this combined representation into a sequence format with a hidden dimension of $d_{0}$, making it compatible with the Transformer network. This Transformer block processes the sequence to learn the complex temporal dynamics of the discrete flow. Finally, a reverse reshape layer flattens the output for a linear projection that predicts the underlying velocity field over the vocabulary space.

Instead of estimating the distribution paths $p_{t}$, the Discrete Flow Matching (DFM) framework (Campbell et al., 2024; Gat et al., 2024) learns the underlying dynamics by estimating the velocity field $u_{t}$.
This section provides the first theoretical verification for this approach by establishing rigorous error bounds for the discrete flow matching (with factorized velocity).
We prove that the quality of the generated distribution is controlled by the accuracy of the learned velocity field.
We formalize this relationship by presenting an upper bound on the total variation distance between the estimated distribution $\widehat{P}$ and target distributions $P$, in terms of the risk of the velocity estimator.

###### Theorem 3.1 (Error Bound for Discrete Flow Matching) .

Consider the discrete state space $\mathcal{S}=\mathcal{V}^{d}$ with vocabulary $\mathcal{V}=\{1,\ldots,M\}$.
Let $P$ be the true data distribution and let $\widehat{P}$ be the distribution generated by a DFM model using factorized velocity estimators $\widehat{u}_{\theta}^{1},\ldots,\widehat{u}_{\theta}^{d}$.
For each coordinate $i_{0}\in[d]$, define the factorized risk as the mean squared error of its velocity estimator:

$$ $\displaystyle\mathcal{R}^{i_{0}}(\widehat{\Theta}):=\int_{t_{0}}^{T}\underset{X_{t}\sim p_{t}(x)}{\mathbb{E}}\|u^{i_{0}}(X_{t},t)-\widehat{u}^{i_{0}}_{\theta}(X_{t},t)\|_{2}^{2}\differential t,$ $$

where the time interval is clipped to $[t_{0},T]$ to ensure numerical stability and $p_{t}(x)$ is true probability path generated by factorized velocities $u^{1},\ldots,u^{d}$. Then, the total variation distance between the true and generated distributions is bounded by the sum of the risks from each factorized component:

$$ $\displaystyle{\rm TV}(P,\widehat{P})\lesssim\sqrt{M}\exp(M_{u})\sum_{i_{0}\in[d]}\sqrt{\mathcal{R}^{i_{0}}(\widehat{\Theta})},$ $$

where $M_{u}$ is the upper bound of estimated velocity such that $\absolutevalue{u_{t}^{\theta,i_{0}}(y,x)}\leq M_{u}$ for all $y,x\in\mathcal{S}$.

###### Proof.

Please see [Appendix˜C](https://arxiv.org/html/2509.22623v1#A3) for a detailed proof.
∎

###### Remark 3.1 (Comparison with Flow Matching Error Bounds) .

Our error bounds [Theorem˜3.1](https://arxiv.org/html/2509.22623v1#S3.Thmtheorem1) provides an analogue to flow matching bounds (in $2$-Wasserstein distance) like (Benton et al., 2023), with foundational differences in technique.
We bound the solution error of the Kolmogorov forward equation governing the probability distribution.
In contrast, their approach uses the Alekseev-Gröbner formula to control the trajectory-wise error of the underlying flow ODE.
This technical distinction leads to different complexity sources: total variation distance bound scales exponentially with vocabulary size $M$ (a combinatorial challenge), whereas their $2$-Wasserstein bound scales with the velocity field’s Lipschitz constant $L$ (an analytic challenge).

[Theorem˜3.1](https://arxiv.org/html/2509.22623v1#S3.Thmtheorem1) confirms that the central challenge in discrete flow matching is to learn factorized velocity estimators $\widehat{u}_{\theta}^{i_{0}}$ with low risk $\mathcal{R}^{i_{0}}(\widehat{\Theta})$.
Therefore, the subsequent sections analyzes the two primary sources of this risk: (i) [Section˜4](https://arxiv.org/html/2509.22623v1#S4): the approximation error (the error arising from learning velocity estimators with neural networks, which is the inherent limitation of model class) and (ii) [Section˜5](https://arxiv.org/html/2509.22623v1#S5): the estimation error (the error arising from training on a finite dataset).

###### Theorem 3.1 (Error Bound for Discrete Flow Matching) .

###### Proof.

###### Remark 3.1 (Comparison with Flow Matching Error Bounds) .

##### Roadmap of Our Theoretical Results.

For the convenience of readers,
we provide the logical structure of our theoretical results in [Figure˜2](https://arxiv.org/html/2509.22623v1#S3.F2) below.
It illustrates the progression from supporting lemmas to intermediate error bounds.
Altogether, these bounds culminate in our four main results (error bounds for discrete flow matching): intrinsic ([Theorem˜3.1](https://arxiv.org/html/2509.22623v1#S3.Thmtheorem1)), approximation ([Theorem˜4.1](https://arxiv.org/html/2509.22623v1#S4.Thmtheorem1)), velocity estimation ([Theorem˜5.1](https://arxiv.org/html/2509.22623v1#S5.Thmtheorem1)), and distribution estimation ([Theorem˜5.2](https://arxiv.org/html/2509.22623v1#S5.Thmtheorem2)).

Figure: Figure 2: Roadmap of Our Theoretical Results.

### 4 Approximation Error for Discrete Flow Matching

This section addresses the first component of the learning error: the approximation error of discrete flow matching with transformers.
We focus on the transformers since the transformers are the foundational architecture in many of today’s most powerful generative models based on discrete flows, such as (Fuest et al., 2025), inverse protein folding (Yi et al., 2025), and graph generation (Qin et al., 2024).
[Section˜4.1](https://arxiv.org/html/2509.22623v1#S4.SS1) embeds the discrete ground-truth velocity field $u(x,t)$ into a continuous space $\mathbb{R}^{M^{d}}$.
[Section˜4.2](https://arxiv.org/html/2509.22623v1#S4.SS2) presents the approximation error bounds for discrete flow matching.

#### 4.1 Extending the Velocity Field

To analyze our model’s approximation error, which operates on the discrete domain $S=\mathcal{V}^{d}$, we require a continuous extension of the ground-truth velocity field.
Therefore, we first embed the discrete input space $S$ into the continuous Euclidean space $\mathbb{R}^{d}$, following [Section˜2](https://arxiv.org/html/2509.22623v1#S2).

Applying this embedding, we then extend the velocity function $u(x,t)$ to a continuous function $\widetilde{u}(z,t)$ defined over $z\in\mathbb{R}^{d}$. The goal is to construct this extension $\widetilde{u}$ such that it preserves the smoothness of the original function. We quantify this smoothness using the Hölder space.

###### Definition 4.1 (Hölder Class) .

Let $d,d^{\prime}\in\operatorname*{\mathbb{Z}}^{+}$, $\Omega\subset\mathbb{R}^{d}$, and let $\beta=k+\gamma$ be the smoothness parameter with $k=\lfloor\beta\rfloor\in\operatorname*{\mathbb{Z}}_{\geq 0}$ and $\gamma\in[0,1)$.
For a $k$-times differentiable function $f:\Omega\to\mathbb{R}$, the Hölder norm is defined as

$$ $\displaystyle\|f\|_{\mathcal{H}^{\beta}(\Omega)}:=\sum_{\|\alpha\|_{1}\leq k}\|\partial^{\alpha}f\|_{L^{\infty}(\Omega)}+\sum_{\|\alpha\|_{1}=k}\sup_{\begin{subarray}{c}x,y\in\Omega\\ x\neq y\end{subarray}}\frac{|\partial^{\alpha}f(x)-\partial^{\alpha}f(y)|}{\|x-y\|^{\gamma}}.$ $$

The Hölder class with smoothness $\beta$ and radius $K>0$ is then

$$ $\displaystyle\mathcal{H}^{\beta}_{d,d^{\prime}}(\Omega,K):=\{f=(f_{1},\dots,f_{d^{\prime}})^{\top}:\Omega\to\mathbb{R}^{d^{\prime}}\mid\sup_{i\in[d^{\prime}]}\|f_{i}\|_{\mathcal{H}^{\beta}(\Omega)}\leq K\}.$ $$

Our analysis requires the ground-truth velocity field $u(x,t)$ to be smooth in time.
We assume that for any fixed state $x\in\mathcal{S}$, the velocity function $t\mapsto u(x,t)$ is Hölder continuous, as stated below.

###### Assumption 4.1 .

For each state $x\in\mathcal{S}$, the true velocity function $t\mapsto u(x,t)$ lies in the Hölder space $\mathcal{H}^{\beta}_{1,|S|}([0,1],K)$ for some smoothness parameter $\beta\geq 1$.

###### Remark 4.1 .

This is a standard assumption in the analysis of differential equations, ensuring the velocity field changes smoothly over time.
[Assumption˜4.1](https://arxiv.org/html/2509.22623v1#S4.Thmassumption1) is not restrictive and holds for many common probability path constructions.
A prominent example is the mixture path.
The velocity that generates the mixture path ([2.8](https://arxiv.org/html/2509.22623v1#S2.E8)) is smooth with respect to time $t$.
This ensures that for any smoothness level $\beta\geq 1$, the condition in [Assumption˜4.1](https://arxiv.org/html/2509.22623v1#S4.Thmassumption1) is satisfied.

Then the following lemma demonstrates that a smooth extension $\widetilde{u}(z,t)$ exists that interpolates the original function while preserving its smoothness.

###### Lemma 4.1 (Discrete-to-Continuous Functional Extension) .

Let $\mathcal{S}\subset\mathbb{R}^{d}$ be the discrete state space.
For each $x\in\mathcal{S}$,
let $t\mapsto u(x,t)\in\mathcal{H}^{\beta}_{1,M^{d}}([0,1],K)$ with $\beta=k_{1}+\gamma\geq 1$, where $k=\lfloor\beta\rfloor$ and $\gamma\in[0,1)$.
Then there exists an continuous extension $\widetilde{u}\in\mathcal{H}^{\beta}_{d+1,M^{d}}(\mathbb{R}^{d}\times[0,1],C)$ such that

$$ $\displaystyle\widetilde{u}(s,t)=u(s,t)\penalty 10000\ \penalty 10000\ \penalty 10000\ \penalty 10000\ \text{for all}\penalty 10000\ s\in\mathcal{S},t\in[0,1],$ $$

where the Hölder norm $C=e\cdot(k_{1}+2)(2k_{1})^{2k_{1}}KM^{d}$.

###### Proof.

Please see [Appendix˜D](https://arxiv.org/html/2509.22623v1#A4) for a detailed proof.
∎

###### Remark 4.2 .

This lemma shows that it is possible to extend a family of smooth functions indexed by discrete points to a smooth function on the whole domain with controlled Hölder norm.

###### Definition 4.1 (Hölder Class) .

###### Assumption 4.1 .

###### Remark 4.1 .

###### Lemma 4.1 (Discrete-to-Continuous Functional Extension) .

###### Proof.

###### Remark 4.2 .

#### 4.2 Discrete Flow Matching Approximation

Building on the continuous extension of the velocity field from [Section˜4.1](https://arxiv.org/html/2509.22623v1#S4.SS1), we now derive a specific approximation rate for the discrete flow matching model.
Following practical implementation (Campbell et al., 2024; Gat et al., 2024; Lipman et al., 2024), our analysis in this section focuses on the setting that combines factorized velocities with the mixture path construction ([Section˜2](https://arxiv.org/html/2509.22623v1#S2)).

###### Theorem 4.1 (Approximation Theorem for Discrete Flow Matching) .

Suppose $u^{i}(x,t)$ be the factorized velocity field for coordinate $i\in[d]$ under mixture path setting.
Assume [Assumption˜4.1](https://arxiv.org/html/2509.22623v1#S4.Thmassumption1) holds,
then for any $\epsilon\in(0,1)$, there exists a transformer network $u^{i}_{\theta}(x,t)\in\mathcal{T}^{h,s,r}_{R}(C_{\mathcal{T}},C^{2,\infty}_{KQ},C_{KQ},C^{2,\infty}_{OV},C_{OV},C_{E},C^{2,\infty}_{F},C_{F})$ satisfying that for any $t\in[t_{0},T]$:

$$ $\displaystyle\sum_{x\in\mathcal{S}}\|u^{i}_{\theta}(x,t)-u^{i}(x,t)\|^{2}_{2}\cdot p_{t}(x)\lesssim\epsilon^{\frac{2}{M}}M^{13},$ $$

where $d_{0}$ is the transformer feature dimension.
The parameters of the approximating Transformer (see [Appendix˜B](https://arxiv.org/html/2509.22623v1#A2) for a detailed definition) are bounded as follows:

$$ $\displaystyle\penalty 10000\ C_{KQ},C^{2,\infty}_{KQ}=\widetilde{O}(M^{7d_{0}}\epsilon^{-5d_{0}});\quad C_{OV},C^{2,\infty}_{OV}=O(M^{-\frac{1}{2}}\epsilon)$ $\displaystyle\penalty 10000\ C_{F},C^{2,\infty}_{F}=O(M^{2}\epsilon^{-1});\quad C_{E}=O(M),$ $$

where $d$ is the sequence length, $d_{0}$ is the transformer feature dimension, $O(\cdot)$ hides polynomial factors depending on $d,d_{0}$, $\widetilde{O}(\cdot)$ hides polynomial factors depending on $d,d_{0}$ and logarithmic factors depending on vocabulary size $M$.
Here we set transformer feature dimension $d_{0}>25$ for simplicity.

###### Proof.

Please see [Appendix˜E](https://arxiv.org/html/2509.22623v1#A5) for a detailed proof.
∎

###### Theorem 4.1 (Approximation Theorem for Discrete Flow Matching) .

###### Proof.

### 5 Velocity and Distribution Estimations

While [Section˜4](https://arxiv.org/html/2509.22623v1#S4) confirms that Transformers are powerful enough to approximate true velocity field with any precision, this section addresses the practical challenge of learning from data.
We analyze the estimation error—the error that arises from having access only to a finite set of $n$ training samples rather than the true underlying data distribution.
Specifically, [Section˜5.1](https://arxiv.org/html/2509.22623v1#S5.SS1) derives convergence rates for the velocity estimator, showing how its error decreases as the number of training samples $n$ increases.
Then, by applying the error bounds for discrete flow matching [Theorem˜3.1](https://arxiv.org/html/2509.22623v1#S3.Thmtheorem1),
[Section˜5.2](https://arxiv.org/html/2509.22623v1#S5.SS2)
translates this velocity error into a bound on the final distribution error under total variation distance.

#### 5.1 Velocity Estimation

We begin by establishing the estimation error bounds of training the factorized velocity estimator.

###### Theorem 5.1 (Velocity Estimation with Discrete Flow Matching Transformer) .

Let $\widehat{u}^{i_{0}}_{\theta}\in\mathcal{T}^{h,s,r}_{R}$ with parameter $\widehat{\Theta}^{i_{0}}$ be the factorized velocity estimator for coordinate $i_{0}\in[d]$ under mixture path setting.
Given $n$ i.i.d training samples $\{x_{i}\}_{i=1}^{n}$ from state space $\mathcal{S}=[M]^{d}$, we train the model by minimizing empirical loss $\widehat{\mathcal{L}}^{i_{0}}_{\rm CDFM}$ following ([2.10](https://arxiv.org/html/2509.22623v1#S2.E10)).
Then for large enough $n$ we have:

$$ $\displaystyle\underset{\{x_{i}\}_{i=1}^{n}}{\mathbb{E}}[\mathcal{R}^{i_{0}}(\widehat{\Theta}^{i_{0}})]\lesssim M^{13d_{0}}n^{-\frac{1}{5Md_{0}}}(\log n)^{\frac{1}{5Md_{0}}},$ $$

Here we set transformer feature dimension $d_{0}>25$ for simplicity.

###### Proof.

Please see [Appendix˜F](https://arxiv.org/html/2509.22623v1#A6) for a detailed proof.
∎

###### Theorem 5.1 (Velocity Estimation with Discrete Flow Matching Transformer) .

###### Proof.

#### 5.2 Distribution Estimation

The velocity estimation rate is a critical intermediate step.
We now leverage this result to derive the main statistical guarantee of our work: an end-to-end bound on the final distribution generated by the discrete flow matching process.
By combining the velocity estimation error bound from [Theorem˜5.1](https://arxiv.org/html/2509.22623v1#S5.Thmtheorem1) with the internal error analysis for the discrete flow matching ([Theorem˜3.1](https://arxiv.org/html/2509.22623v1#S3.Thmtheorem1)), we establish the convergence rates for discrete flow matching distribution estimation error.

###### Theorem 5.2 (Discrete Flow Matching Velocity Estimation with Transformer) .

For any coordinate $i_{0}\in[d]$, let $\widehat{u}^{i_{0}}_{\theta}$ be the $i$-th velocity estimator trained by minimizing empirical loss $\widehat{\mathcal{L}}^{i_{0}}_{\rm CDFM}$ following ([2.10](https://arxiv.org/html/2509.22623v1#S2.E10)).
Let $P$ denote the true distribution and $\widehat{P}$ the distribution generated by the discrete flow matching framework with factorized velocity estimators $\widehat{u}^{1}_{\theta},\widehat{u}^{2}_{\theta},\ldots,\widehat{u}^{d}_{\theta}$.
Then for a vocabulary size $M$, the expected total variation distance $\text{TV}(P,\widehat{P})$ over training data $\{x_{i}\}_{i=1}^{n}$ is bounded by:

$$ $\displaystyle\underset{\{x_{i}\}_{i=1}^{n}}{\mathbb{E}}[\text{TV}(P,\widehat{P})]\lesssim M^{7d_{0}}n^{-\frac{1}{9Md_{0}}}(\log n)^{\frac{1}{9Md_{0}}}.$ $$

Here we set transformer feature dimension $d_{0}>25$ for simplicity.

###### Proof.

Please see [Appendix˜G](https://arxiv.org/html/2509.22623v1#A7) for a detailed proof.
∎

[Theorem˜5.2](https://arxiv.org/html/2509.22623v1#S5.Thmtheorem2) establishes a concrete convergence rate, confirming that the model’s generated distribution provably converges to the true data distribution as the size of the training set increases.

###### Theorem 5.2 (Discrete Flow Matching Velocity Estimation with Transformer) .

###### Proof.

### 6 Discussion and Conclusion

Our analysis also provides a strong theoretical justification for employing factorized velocities, a common practical choice.
A comparison between the statistical rates for the factorized setting ([Sections˜4](https://arxiv.org/html/2509.22623v1#S4) and [5](https://arxiv.org/html/2509.22623v1#S5)) and the general, non-factorized setting ([Appendices˜H](https://arxiv.org/html/2509.22623v1#A8) and [I](https://arxiv.org/html/2509.22623v1#A9)) reveals a critical insight.
The intrinsic error bound for the general case scales with a term of $M^{d/2}$ ([Theorem˜C.1](https://arxiv.org/html/2509.22623v1#A3.Thmtheorem1)), where $M$ is the vocabulary size and $d$ is the sequence length.
In contrast, the intrinsic error bound for the factorized velocity discrete flow matching depends only on $\sqrt{M}$ ([Theorem˜3.1](https://arxiv.org/html/2509.22623v1#S3.Thmtheorem1)), mitigating this severe curse of dimensionality.
Because this error is model-agnostic and intrinsic to the discrete flow matching framework itself, the $\sqrt{M}$ term represents a fundamental barrier, not an artifact of a specific network architecture.
This intrinsic weakness propagates to the final learning guarantees, resulting in looser estimation error bounds for the non-factorized approach ([Theorem˜I.1](https://arxiv.org/html/2509.22623v1#A9.Thmtheorem1) and [Theorem˜I.2](https://arxiv.org/html/2509.22623v1#A9.Thmtheorem2)).
This finding demonstrates that factorization is not only a computational convenience but is also crucial for statistical efficiency.

While our work provide solid statistical foundation for discrete flow matching, we highlight limitations and opens avenues for future research.
A key limitation revealed by our analysis is the polynomial dependence of the error bounds on the vocabulary size $M$.
As shown in our main theorems [Theorem˜5.2](https://arxiv.org/html/2509.22623v1#S5.Thmtheorem2), the error bounds scale with terms like $M^{7d_{0}}$, and thus do not provide meaningful guarantees for typical large-vocabulary tasks such as text generation.
This provides a critical insight: the discrete flow matching framework may be better suited for applications with small to medium sized vocabularies, such as coding or protein design.
As part of our future work, we plan to investigate whether this polynomial dependence constitutes a fundamental hardness result.

### 7 Conclusion

In this work, we present the first comprehensive theoretical analysis of Discrete Flow Matching (DFM), providing an end-to-end guarantee that the generated distribution provably converges to the true data distribution.
Our key innovation is establishing a model-agnostic, intrinsic error bound for the discrete flow matching ([Theorem˜3.1](https://arxiv.org/html/2509.22623v1#S3.Thmtheorem1)).
This foundational result demonstrates that the final distribution error is controlled by the accuracy of the learned velocity field, a principle that holds true for discrete flow matching with any arbitrary implementation.
Building on this intrinsic bound, we specialized our analysis to the popular case of Transformer-based models, decomposing the velocity risk into its two fundamental components: approximation error, which concerns the expressive power of the model architecture, and estimation error, which results from learning on a finite sample.

To address the approximation error, we first bridge the theoretical gap between the discrete data space $\mathcal{S}$ and our transformer universal approximation theory.
We then construct an embedding that maps the discrete space into Euclidean space
([Section˜2](https://arxiv.org/html/2509.22623v1#S2)).
This embedding allows us to extend the discrete velocity field to a continuous one ([Lemma˜E.1](https://arxiv.org/html/2509.22623v1#A5.Thmlemma1)).
By applying transformer universal approximation theory ([Theorems˜B.1](https://arxiv.org/html/2509.22623v1#A2.Thmtheorem1) and [B.2](https://arxiv.org/html/2509.22623v1#A2.Thmtheorem2)) to the continuous extension of the velocity field, we obtain explicit approximation rates for discrete flow matching with Transformers ([Theorem˜4.1](https://arxiv.org/html/2509.22623v1#S4.Thmtheorem1)).
To bound the estimation error, we analyze the complexity of the function class learned by the Transformer. By applying covering number arguments, we establish a precise rate for the velocity estimation error ([Theorem˜5.1](https://arxiv.org/html/2509.22623v1#S5.Thmtheorem1)).
Finally, by composing these results, we derive the overall distribution estimation error in [Theorem˜5.2](https://arxiv.org/html/2509.22623v1#S5.Thmtheorem2). This final bound characterizes the convergence rate of the learned distribution, providing a complete statistical analysis of the discrete flow matching Transformers pipeline.

In conclusion, this paper establishes a solid theoretical foundation for the discrete flow matching framework, with our intrinsic error bound serving as the cornerstone.
By validating the core principles of discrete flow matching and the practical utility of techniques like velocity factorization, our work moves the understanding of these models from an empirical art to a more rigorous science, paving the way for more principled and robust advancements in discrete generative modeling.

##### Related Work: Statistical Rates for Generative Models.

The theoretical study of generative models involves analyzing their statistical properties, including approximation error, estimation error, convergence rates, and sample complexity.
Recent works make significant progress in this area for continuous data models.
For instance, Fu et al. (2024) establish sharp statistical rates for conditional diffusion models with MLP backbones, while Jiao et al. (2024) derive explicit convergence rates for flow models in a latent space.
In a key development for Flow Matching (FM), Fukumizu et al. (2024) show that Flow Matching achieve nearly minimax optimal convergence rates under the $p$-Wasserstein distance, providing the first theoretical evidence of its competitiveness with diffusion models. This line of studies extend to analyze conditional diffusion transformers (Hu et al., 2024b) and higher-order flow matching methods (Su et al., 2025).

However, these theoretical work only focus on models for continuous data, leaving the discrete setting unexplored.
A fundamental challenge for discrete generative approaches is how to define a tractable denoising process on discrete spaces.
Our key innovation is to overcome this obstacle by constructing an embedding layer that maps discrete data into a continuous space.
This crucial step enables a rigorous statistical analysis of discrete generative models within continuous-time framework.
Building on this, we provide an end-to-end statistical guarantee for discrete flow matching.

We defer an extended discussion on related work to [Appendix˜A](https://arxiv.org/html/2509.22623v1#A1) due to page limits.

### Acknowledgments

JH would like to thank Mimi Gallagher, Sara Sanchez, T.Y. Ball, Dino Feng and Andrew Chen for valuable conversations; Yi-Chen Lee and Sophia Pi for collaborations on related topics; and the Red Maple Family for support.
The authors would like to thank the anonymous reviewers and program chairs for constructive comments.

JH is partially supported by Ensemble AI and Northwestern University.
Han Liu is partially supported by NIH R01LM1372201, NSF
AST-2421845, Simons Foundation
MPS-AI-00010513, AbbVie , Dolby and Chan Zuckerberg Biohub Chicago Spoke Award.
This research was supported in part through the computational resources and staff contributions provided for the Quest high performance computing facility at Northwestern University which is jointly supported by the Office of the Provost, the Office for Research, and Northwestern University Information Technology.
The content is solely the responsibility of the authors and does not necessarily represent the official
views of the funding agencies.

Typeset with a modified LaTeX template of 1712.09542 [hep-th] by Yuji Tachikawa (Tachikawa, 2020).

## Appendix

### Appendix A Related Work

In this section, we discuss the recent success of DFM and techniques used in our work.

##### Discrete Generative Models and Discrete Flow Matching.

While autoregressive models remain the predominant paradigm for discrete data generation (Achiam et al., 2023; Liu et al., 2024; Ingraham et al., 2019), recent diffusion and flow-matching alternatives show impressive performance across many domains, including sound generation (Yang et al., 2023), graph generation (Vignac et al., 2022), and protein design (Campbell et al., 2024).
Progress in adapting these continuous-time models to discrete settings follows two strategies.
The first involves designing diffusion processes over discrete state spaces (Sohl-Dickstein et al., 2015; Hoogeboom et al., 2021; Austin et al., 2021; Lou et al., 2023; Yang et al., 2023; Vignac et al., 2022).
The second embeds discrete data into a continuous space, where standard diffusion or flow-matching techniques then be applied (Dieleman et al., 2022; Campbell et al., 2022; Davis et al., 2024).

Most recently, Campbell et al. (2024) and (Gat et al., 2024) introduce Discrete Flow Matching (DFM), which emerge as a powerful new paradigm for discrete generative modeling.
DFM offers significant flexibility in the design of the denoising process and the choice of the source distribution.
Consequently, there is a growing interest in exploring the efficiency and application of DFM for various generation tasks.
This interest lead to a rapid expansion of DFM-based models.
For instance, (Hu and Ommer, 2024) validate its efficiency in the image domain.
In graph generation, Qin et al. (2024) introduce DeFoG, a framework that uses DFM to respect the inherent symmetries of graphs and disentangle sampling from training for more efficient optimization.
Fuest et al. (2025) introduce MaskFlow, a unified video generation framework that leverages DFM for efficient, high-quality long video synthesis.
Similarly, in structural biology, Yi et al. (2025) present ADFLIP, a DFM-based model for designing protein sequences conditioned on all-atom structural contexts.
However, the success of these models are driven by empirical validation.
Despite their impressive performance and growing adoption, a rigorous theoretical understanding of DFM is lacking.
Our work fills this critical gap by providing the solid theoretical foundations for Discrete Flow Matching.

##### Transformer Universal Approximation.

Transformers are universal approximators, possessing the capacity to model any arbitrary sequence-to-sequence function with a desired level of precision.
Yun et al. (2019) establish universality for deep stacks of self-attention and feed-forward layers via a contextual mapping method, under the assumption that hidden representations remain sufficiently separated.
Later, (Alberti et al., 2023) broaden the scope of this guarantee to encompass variants using sparse attention mechanisms.
Building on this foundation, more recent findings relax the architectural requirements. Research from Hu et al. (2024a); Kajitsuka and Sato (2023) demonstrate that the powerful approximation capability is not dependent on depth, showing that a single Transformer block with one self-attention layer is itself sufficient to achieve universal approximation.
In our work, we leverage this powerful result to analyze the approximation error of Transformer-based discrete flow matching models.

### Appendix B Supplementary Background: Transformer Block

In this section, we introduce the transformer network structure (Vaswani et al., 2017) and its properties.
Following the notations in (Hu et al., 2024b),
We start with the definition of transformers.

#### B.1 Transformers

Transformer Block.
Let $h$ be the number of heads and $s$ be the hidden dimension of the multi-head attention layer.
The multi-head attention layer $F^{\rm SA}:\mathbb{R}^{d\times L}\to\mathbb{R}^{d\times L}$ is then defined as:

$$ $\displaystyle F^{\rm SA}(Z):=Z+\sum_{i=1}^{h}W_{O}^{i}(W_{V}^{i}Z)\mathop{{\rm Softmax}}((W_{K}^{i}Z)^{\top}(W_{Q}^{i}Z)),$ $$

where $W_{K}^{i},W_{Q}^{i},W_{V}^{i},(W_{O}^{i})^{\top}\in\mathbb{R}^{s\times d}$ are weight matrices for all $i\in[h]$ and $\mathop{{\rm Softmax}}(\cdot)$ is the column-wise softmax function.

Let $r$ be the dimension of hidden of the feed-forward layer.
The feed-forward layer $F^{\rm FF}(Z):\mathbb{R}^{d\times L}\to\mathbb{R}^{d\times L}$ is then defined as:

$$ $\displaystyle F^{\rm FF}(Z):=Z+W_{2}\mathop{\mathsf{ReLU}}(W_{1}Z+b_{1}\mathds{1}_{L}^{\top})+b_{2}\mathds{1}_{L}^{\top},$ $$

where $W_{1},(W_{2})^{\top}\in\mathbb{R}^{r\times d}$ are weight matrices, $b_{1}\in\mathbb{R}^{r},b_{2}\in\mathbb{R}^{d}$ are bias.
Throughout this paper, we treat $\mathop{\mathsf{ReLU}}(\cdot)$ as element-wise operation when applied to vectors or matrices.

We define a transformer block as the composition of a self-attention layer and a feed-forward layer.

###### Definition B.1 (Transformer Block) .

For $h,s,r\in\mathbb{Z}^{+}$, we define a
transformer block $F^{h,s,r}:\mathbb{R}^{d\times L}\to\mathbb{R}^{d\times L}$ as:

$$ $\displaystyle F^{h,s,r}:=F^{\rm FF}\circ F^{\rm SA},$ $$

where $F^{\rm SA}$ has $h$ heads and hidden dimension $s$, $F^{\rm FF}$ has hidden dimension $r$.

Then we define the transformer networks function class as composition of transformer blocks.

###### Definition B.2 (Transformer Network Function Class) .

Let transformer block $F^{h,s,r}$ be as defined in [Definition˜B.1](https://arxiv.org/html/2509.22623v1#A2.Thmdefinition1).
Then we define the transformer network function class $\mathcal{T}^{h,s,r}$ as a function class with each component being the composition of transformer blocks:

$$ $\displaystyle\mathcal{T}^{h,s,r}=\{\tau:\mathbb{R}^{d\times L}\to\mathbb{R}^{d\times L}\mid\tau=F^{h,s,r}\circ\cdots\circ F^{h,s,r}\}.$ $$

Discrete Flow Matching Transformers.
Following the common structure of diffusion transformers (Peebles and Xie, 2023) and flow matching transformers (Su et al., 2025), we introduce the transformer architecture used in this paper.
We start with the definition of a reshape layer that converts a vector input $x\in\mathbb{R}^{d_{x}}$ into a matrix input $Z\in\mathbb{R}^{d\times L}$, where $d_{x}=d\times L$.

###### Definition B.3 (Reshape Layer) .

The reshape layer $R(\cdot):\mathbb{R}^{d_{x}}\to\mathbb{R}^{d\times L}$ is an operator transforming vector input of dimension $d_{x}$ to matrix output of size $d\times L$.
Te reshape layer is frozen when training.
Further, we define the reverse reshape layer as $R^{-1}(\cdot):\mathbb{R}^{d\times L}\to\mathbb{R}^{d_{x}}$.

For instance, the most commonly used reshape layer in diffusion models is the operator turning vector input of dimension $d_{x}$ to matrix input of size $d\times L$ by rearranging entries, where $d_{x}=d\cdot L$.

Finally, we define the following transformer function class with reshape layer.

###### Definition B.4 (Transformer Function Class With Reshape Layer and Parameter Bound) .

Let $F^{\rm E}(Z):=Z+E$ represent the position encoding layer and $R$ represent the reshape layer.
The transformer network class with reshape layer is defined as:

$$ $\displaystyle\mathcal{T}^{h,s,r}_{R}:=\{R^{-1}\circ f_{\mathcal{T}}\circ F^{\rm E}\circ R:\mathbb{R}^{d_{0}}\to\mathbb{R}^{d_{0}}\mid f_{\mathcal{T}}\in\mathcal{T}^{h,s,r}\}.$ $$

We write $W_{KQ}^{i}:=(W_{K}^{i})^{\top}W_{Q}^{i}$ and $W_{OV}^{i}:=W_{O}^{i}W_{V}^{i}$ for simplicity of notations.
Then, a transformer function class with reshape layer and parameter bound is defined as as $\mathcal{T}^{h,s,r}_{R}(C_{\mathcal{T}},C^{2,\infty}_{KQ},C_{KQ},C^{2,\infty}_{OV},C_{OV},C_{E},C^{2,\infty}_{F},C_{F},L_{\mathcal{T}})$, which satisfies:

- •
$h,s,r$ as defined above;
- •
Transformer output bound: $\sup_{Z}\|f_{\mathcal{T}}(Z)\|\leq C_{\mathcal{T}}$;
- •
Parameter bound in $F^{\rm FF}$: $\max\{\|W_{1}\|_{2,\infty},\|W_{2}\|_{2,\infty}\}\leq C^{2,\infty}_{F},\penalty 10000\ \max\{\|W_{1}\|_{2},\|W_{2}\|_{2}\}\leq C^{2}_{F}$;
- •
Parameter bound in $F^{\rm SA}$: $\|W_{KQ}^{i}\|_{2}\leq C_{KQ},\penalty 10000\ \|W_{OV}^{i}\|_{2}\leq C_{OV},\penalty 10000\ \|W_{KQ}^{i}\|_{2,\infty}\leq C^{2,\infty}_{KQ},\penalty 10000\ \|W_{OV}^{i}\|_{2}\leq C^{2,\infty}_{OV}$;
- •
Parameter bound in $F^{\rm E}$: $\|E^{\top}\|_{2,\infty}\leq C_{E}$;
- •
Frobenius Lipschitzness of $f_{\mathcal{T}}\in\mathcal{T}^{h,s,r}$:$\|f_{\mathcal{T}}(Z_{1})-f_{\mathcal{T}}(Z_{2})\|_{F}\leq L_{\mathcal{T}}\|Z_{1}-Z_{2}\|_{F}$.

###### Definition B.1 (Transformer Block) .

###### Definition B.2 (Transformer Network Function Class) .

###### Definition B.3 (Reshape Layer) .

###### Definition B.4 (Transformer Function Class With Reshape Layer and Parameter Bound) .

#### B.2 Lipschitzness of Transformer Network

To prepare our proofs, we first establish a new result on the Lipschitzness of transformer networks (i.e., [Lemma˜B.7](https://arxiv.org/html/2509.22623v1#A2.Thmlemma7)).
It shows that a function composed of Lipschitz functions remains Lipschitz.

##### Preparations of Lemma ˜ B.7 .

We first present some helper lemmas for proving [Lemma˜B.7](https://arxiv.org/html/2509.22623v1#A2.Thmlemma7).

###### Lemma B.1 .

Let $f_{1},f_{2}:\mathbb{R}^{d\times L}\to\mathbb{R}^{d\times L}$ be $L_{1}$- and $L_{2}$-Lipschitz w.r.t. Frobenius norm $\|\cdot\|_{F}$ respectively.
Then $f_{1}\circ f_{2}$ is $(L_{1}L_{2})$-Lipschitz with respect to $\|\cdot\|_{F}$.

###### Proof.

For all $X_{1},X_{2}\in\mathbb{R}^{d\times L}$, it holds:

$$ $\displaystyle\|f_{1}\circ f_{2}(X_{1})-f_{1}\circ f_{2}(X_{2})\|_{F}\leq$ $\displaystyle\penalty 10000\ L_{2}\|f_{1}(X_{1})-f_{1}(X_{2})\|_{F}$ $\displaystyle\leq$ $\displaystyle\penalty 10000\ L_{1}L_{2}\|X_{1}-X_{2}\|_{F},$ $$

where the first line is by $\|f_{2}(X_{1})-f_{2}(X_{2})\|_{F}\leq L_{2}\|X_{1}-X_{2}\|_{F}$ and the second line is by $\|f_{1}(X_{1})-f_{1}(X_{2})\|_{F}\leq L_{1}\|X_{1}-X_{2}\|_{F}$.
This completes the proof.
∎

Next, we analyze the Lipschitzness of RELU function.
Throughout this paper, we treat $\mathop{\mathsf{ReLU}}(\cdot)$ as element-wise operator when applied to vectors or matrices.

###### Lemma B.2 (Lipschitzness of $\mathop{\mathsf{ReLU}}(\cdot)$ ) .

The ReLU function $\mathop{\mathsf{ReLU}}:\mathbb{R}^{d\times L}\to\mathbb{R}^{d\times L}$ is $1$-Lipschitz with respect to the Frobenius norm $\|\cdot\|_{F}$.

###### Proof.

For all $X_{1},X_{2}\in\mathbb{R}^{d\times L}$, it holds:

$$ $\displaystyle\|\mathop{\mathsf{ReLU}}(X_{1})-\mathop{\mathsf{ReLU}}(X_{2})\|_{F}=$ $\displaystyle\penalty 10000\ \sqrt{\sum_{i=1}^{d}\sum_{j=1}^{L}|\mathop{\mathsf{ReLU}}((X_{1})_{i,j})-\mathop{\mathsf{ReLU}}((X_{2})_{i,j})|^{2}}$ ( By the definition of Frobenius Norm ) $\displaystyle\leq$ $\displaystyle\penalty 10000\ \sqrt{\sum_{i=1}^{d}\sum_{j=1}^{L}|(X_{1})_{i,j}-(X_{2})_{i,j}|^{2}}$ $\displaystyle=$ $\displaystyle\penalty 10000\ \|X_{1}-X_{2}\|_{F},$ $$

where the second line is by $|\mathop{\mathsf{ReLU}}(x_{1})-\mathop{\mathsf{ReLU}}(x_{2})|\leq|x_{1}-x_{2}|$ for $x_{1},x_{2}\in\mathbb{R}$.

This completes the proof.
∎

With [Lemma˜B.2](https://arxiv.org/html/2509.22623v1#A2.Thmlemma2), we now prove the Lipschitzness of feed-forward layer.

###### Lemma B.3 (Lipschitzness of FFN) .

Let $Z\in\mathbb{R}^{d\times L}$ and define the feedforward layer as

$$ $\displaystyle F^{\rm FF}(Z):=Z+W_{2}\mathop{\mathsf{ReLU}}(W_{1}Z+b_{1}\mathds{1}_{L}^{\top})+b_{2}\mathds{1}_{L}^{\top}.$ $$

Then $F^{\rm FF}$ is Lipschitz continuous with respect to Frobenius norm, with Lipschitz constant
$\|W_{1}\|_{2}\cdot\|W_{2}\|_{2}+1$.

###### Proof.

For all $X_{1},X_{2}\in\mathbb{R}^{d\times L}$, it holds:

$$ $\displaystyle\penalty 10000\ \|F^{\rm FF}(X_{1})-F^{\rm FF}(X_{2})\|_{F}$ $\displaystyle\leq$ $\displaystyle\penalty 10000\ \|X_{1}-X_{2}\|_{F}+\|(W_{2}\mathop{\mathsf{ReLU}}(W_{1}X_{1}+b_{1}\mathds{1}_{L}^{\top})+b_{2}\mathds{1}_{L}^{\top})-(W_{2}\mathop{\mathsf{ReLU}}(W_{1}X_{2}+b_{1}\mathds{1}_{L}^{\top})+b_{2}\mathds{1}_{L}^{\top})\|_{F}$ ( By triangle inequality ) $\displaystyle\leq$ $\displaystyle\penalty 10000\ \|X_{1}-X_{2}\|_{F}+\|W_{2}\|_{2}\cdot\|\mathop{\mathsf{ReLU}}(W_{1}X_{1}+b_{1}\mathds{1}_{L}^{\top})-\mathop{\mathsf{ReLU}}(W_{1}X_{2}+b_{1}\mathds{1}_{L}^{\top})\|_{F}$ $\displaystyle\leq$ $\displaystyle\penalty 10000\ \|X_{1}-X_{2}\|_{F}+\|W_{2}\|_{2}\cdot\|(W_{1}X_{1}+b_{1}\mathds{1}_{L}^{\top})-(W_{1}X_{2}+b_{1}\mathds{1}_{L}^{\top})\|_{F}$ $\displaystyle\leq$ $\displaystyle\penalty 10000\ \|X_{1}-X_{2}\|_{F}+\|W_{1}\|_{2}\cdot\|W_{2}\|_{2}\cdot\|X_{1}-X_{2}\|_{F}$ $\displaystyle=$ $\displaystyle\penalty 10000\ (\|W_{1}\|_{2}\cdot\|W_{2}\|_{2}+1)\cdot\|X_{1}-X_{2}\|_{F},$ $$

where the third line is by $\|AX\|_{F}\leq\|A\|_{2}\|X\|_{F}$, the fourth line is by [Lemma˜B.2](https://arxiv.org/html/2509.22623v1#A2.Thmlemma2), and the fifth line is by $\|AX\|_{F}\leq\|A\|_{2}\|X\|_{F}$.

This completes the proof.
∎

Next, we establish the Lipschitzness of self-attention.
We remark that Castin et al. (2024) also establish similar results but with a different method not applicable in our setting.
We start with a lemma proving Lipschitzness of any function whose Jacobian norm is uniformly bounded.

###### Lemma B.4 (Lipschitzness of Functions with Bounded Jacobian; Modified from Lemma A.6 of (Edelman et al., 2022 ) ) .

Let $\Delta^{n-1}=\{x\in\mathbb{R}^{n}|x\geq 0,\|x\|_{1}=1\}$ denote the $n$-simplex.
Suppose $f:\mathbb{R}^{d}\to\Delta^{n-1}$ is differentiable and satisfies $\|Jf(x)\|_{2}\leq c_{f}$ for all $x\in\mathbb{R}^{d}$.
Then for all $x_{1},x_{2}\in\mathbb{R}^{d}$, it holds:

$$ $\displaystyle\|f(x_{1})-f(x_{2})\|_{2}\leq c_{f}\|x_{1}-x_{2}\|_{2}.$ $$

###### Proof.

Our proof follows the proof of (Edelman et al., 2022, Lemma A.6).
With Newton-Leibniz formula and change of variables, we have

$$ $\displaystyle\|f(x_{1})-f(x_{2})\|_{2}\leq$ $\displaystyle\penalty 10000\ \|(\int_{0}^{1}J(tx_{1}+(1-t)x_{2})\differential t)(x_{1}-x_{2})\|_{2}$ $\displaystyle\leq$ $\displaystyle\penalty 10000\ \int_{0}^{1}\|J(tx_{1}+(1-t)x_{2})(x_{1}-x_{2})\|_{2}\differential t$ ( By Jensen’s inequality ) $\displaystyle\leq$ $\displaystyle\penalty 10000\ \int_{0}^{1}\|J(tx_{1}+(1-t)x_{2})\|_{2}\cdot\|x_{1}-x_{2}\|_{2}\differential t$ ( $\|Ax\|_{2}\leq\|A\|_{2}\|x\|_{2}$ ) $\displaystyle\leq$ $\displaystyle\penalty 10000\ c_{f}\|x_{1}-x_{2}\|_{2}.$ ( $\|Jf(x)\|_{2}\leq c_{f}$ ) $$

This completes the proof.
∎

With [Lemma˜B.4](https://arxiv.org/html/2509.22623v1#A2.Thmlemma4), we now prove the Lipschitzness of $\mathop{{\rm Softmax}}(\cdot)$.

###### Lemma B.5 (Lipschitzness of $\mathop{{\rm Softmax}}(\cdot)$ ; Modified from Corollary A.7 of (Edelman et al., 2022 ) ) .

Let $\mathop{{\rm Softmax}}(\cdot):\mathbb{R}^{d\times L}\to\mathbb{R}^{d\times L}$ denote the column-wise softmax function.
Then for all $X_{1},X_{2}\in\mathbb{R}^{d\times L}$, it holds:

$$ $\displaystyle\|\mathop{{\rm Softmax}}(X_{1})-\mathop{{\rm Softmax}}(X_{2})\|_{F}\leq\|X_{1}-X_{2}\|_{F}.$ $$

###### Proof.

For the simplicity of presentation, let $s:\mathbb{R}^{d}\to\mathbb{R}^{d}$ denote the (element-wise) softmax function.
Its Jacobian is $J=\operatorname{diag}(s)-ss^{\top}$.
Thus, $J$ is symmetric and positive semi-definite, so its singular values equal its eigenvalues.
Recall that for softmax function, its Jacobian matrix’s eigenvalues are smaller than 1.
Hence,

$$ $\displaystyle\|J\|_{2}\leq 1.$ $$

Combining $\|J\|_{2}\leq 1$ with [Lemma˜B.4](https://arxiv.org/html/2509.22623v1#A2.Thmlemma4), for each column $i\in[L]$ we have

$$ $\displaystyle\|(\mathop{{\rm Softmax}}(X_{1})-\mathop{{\rm Softmax}}(X_{2}))_{\cdot,i}\|_{2}\leq\|(X_{1}-X_{2})_{\cdot,i}\|_{2}.$ $$

Summing over all columns gives

$$ $\displaystyle\|\mathop{{\rm Softmax}}(X_{1})-\mathop{{\rm Softmax}}(X_{2})\|_{F}\leq\|X_{1}-X_{2}\|_{F}.$ $$

This completes the proof.
∎

Finally, we prove the Lipschitzness of self-attention layer.

###### Lemma B.6 (Lipschitzness of Multi-Head Self-Attention) .

Let $X\in\mathbb{R}^{d\times L}$ satisfy $\|X\|_{2}\leq B_{X}$ on a compact domain.
Define $F^{\rm SA}(X):=X+\sum_{i=1}^{h}W_{O}^{i}(W_{V}^{i}X)\mathop{{\rm Softmax}}((W_{K}^{i}X)^{\top}(W_{Q}^{i}X))$.
Then, $F^{\rm SA}$ is Lipschitz continuous w.r.t. the Frobenius norm $\|\cdot\|_{F}$, with Lipschitz constant

$$ $\displaystyle 1+2(B_{X})^{2}\sum_{i=1}^{h}\|W^{i}_{OV}\|_{2}\cdot\|W^{i}_{KQ}\|_{2}+L\sum_{i=1}^{h}\|W^{i}_{OV}\|_{2},$ $$

where $W^{i}_{OV}=W_{O}^{i}W_{V}^{i}$ and $W^{i}_{KQ}=(W_{K}^{i})^{\top}W_{Q}^{i}$ for any $i\in[h]$.

###### Proof.

For every $X_{1},X_{2}\in\mathbb{R}^{d\times L}$ such that $\|X_{1}\|_{2},\|X_{2}\|_{2}\leq B_{X}$, it holds:

$$ $\displaystyle\penalty 10000\ \|F^{\rm SA}(X_{1})-F^{\rm SA}(X_{2})\|_{F}$ $\displaystyle\leq$ $\displaystyle\penalty 10000\ \|X_{1}-X_{2}\|_{F}+\|\sum_{i=1}^{h}W_{OV}^{i}X_{1}\mathop{{\rm Softmax}}(X_{1}^{\top}W_{KQ}^{i}X_{1})-W_{OV}^{i}X_{2}\mathop{{\rm Softmax}}(X_{2}^{\top}W_{KQ}^{i}X_{2})\|_{F}$ $\displaystyle\leq$ $\displaystyle\penalty 10000\ \|X_{1}-X_{2}\|_{F}+\sum_{i=1}^{h}\|W_{OV}^{i}\|_{2}\cdot\|X_{1}\mathop{{\rm Softmax}}(X_{1}^{\top}W_{KQ}^{i}X_{1})-X_{2}\mathop{{\rm Softmax}}(X_{2}^{\top}W_{KQ}^{i}X_{2})\|_{F}$ ( $\|AX\|_{F}\leq\|A\|_{2}\|X\|_{F}$ ) $\displaystyle\leq$ $\displaystyle\penalty 10000\ \|X_{1}-X_{2}\|_{F}+\sum_{i=1}^{h}\|W_{OV}^{i}\|_{2}\cdot\|X_{1}\mathop{{\rm Softmax}}(X_{1}^{\top}W_{KQ}^{i}X_{1})-X_{1}\mathop{{\rm Softmax}}(X_{2}^{\top}W_{KQ}^{i}X_{2})\|_{F}$ $\displaystyle\penalty 10000\ +\sum_{i=1}^{h}\|W_{OV}^{i}\|_{2}\cdot\|X_{1}\mathop{{\rm Softmax}}(X_{2}^{\top}W_{KQ}^{i}X_{2})-X_{2}\mathop{{\rm Softmax}}(X_{2}^{\top}W_{KQ}^{i}X_{2})\|_{F}$ $\displaystyle\leq$ $\displaystyle\penalty 10000\ \|X_{1}-X_{2}\|_{F}+\sum_{i=1}^{h}\|W_{OV}^{i}\|_{2}\cdot B_{X}\cdot\|\mathop{{\rm Softmax}}(X_{1}^{\top}W_{KQ}^{i}X_{1})-\mathop{{\rm Softmax}}(X_{2}^{\top}W_{KQ}^{i}X_{2})\|_{F}$ $\displaystyle\penalty 10000\ +\sum_{i=1}^{h}\|W_{OV}^{i}\|_{2}\cdot\|X_{1}-X_{2}\|_{F}\cdot\|\mathop{{\rm Softmax}}(X_{2}^{\top}W_{KQ}^{i}X_{2})\|_{F}$ ( $\|X_{1}\|_{2}\leq B_{X}$ and $\|AX\|_{F}\leq\|A\|_{F}\cdot\|X\|_{F}$ ) $\displaystyle\leq$ $\displaystyle\penalty 10000\ \|X_{1}-X_{2}\|_{F}+\sum_{i=1}^{h}\|W_{OV}^{i}\|_{2}\cdot B_{X}\cdot\|X_{1}^{\top}W_{KQ}^{i}X_{1}-X_{2}^{\top}W_{KQ}^{i}X_{2}\|_{F}$ $\displaystyle\penalty 10000\ +\sum_{i=1}^{h}\|W_{OV}^{i}\|_{2}\cdot\|X_{1}-X_{2}\|_{F}\cdot L$ ( By Lemma B.5 and $\|\mathop{{\rm Softmax}}(Z)\|_{F}\leq L$ when $Z\in\mathbb{R}^{L\times L}$ ) $\displaystyle\leq$ $\displaystyle\penalty 10000\ \|X_{1}-X_{2}\|_{F}$ $\displaystyle\penalty 10000\ +\sum_{i=1}^{h}\|W_{OV}^{i}\|_{2}\cdot B_{X}\cdot(\|X_{1}^{\top}W_{KQ}^{i}X_{1}-X_{1}^{\top}W_{KQ}^{i}X_{2}\|_{F}+\|X_{1}^{\top}W_{KQ}^{i}X_{2}-X_{2}^{\top}W_{KQ}^{i}X_{2}\|_{F})$ $\displaystyle\penalty 10000\ +\sum_{i=1}^{h}\|W_{OV}^{i}\|_{2}\cdot\|X_{1}-X_{2}\|_{F}\cdot L$ $\displaystyle\leq$ $\displaystyle\penalty 10000\ \|X_{1}-X_{2}\|_{F}$ $\displaystyle\penalty 10000\ +\sum_{i=1}^{h}\|W_{OV}^{i}\|_{2}\cdot B_{X}\cdot(\|X_{1}^{\top}\|_{2}\|W_{KQ}^{i}\|_{2}\|X_{1}-X_{2}\|_{F}+\|X_{2}^{\top}\|_{2}\|(W_{KQ}^{i})^{\top}\|_{2}\|X_{1}-X_{2}\|_{F})$ $\displaystyle\penalty 10000\ +\sum_{i=1}^{h}\|W_{OV}^{i}\|_{2}\cdot\|X_{1}-X_{2}\|_{F}\cdot L$ ( $\|AX\|_{F}\leq\|A\|_{2}\cdot\|X\|_{F}$ ) $\displaystyle=$ $\displaystyle\penalty 10000\ (1+2(B_{X})^{2}\sum_{i=1}^{h}\|W^{i}_{OV}\|_{2}\cdot\|W^{i}_{KQ}\|_{2}+L\sum_{i=1}^{h}\|W^{i}_{OV}\|_{2})\cdot\|X_{1}-X_{2}\|_{F}.$ ( $\|X_{1}\|_{2},\|X_{2}\|_{2}\leq B_{X}$ ) $$

This completes the proof.
∎

###### Lemma B.1 .

###### Proof.

###### Lemma B.2 (Lipschitzness of 𝖱𝖾𝖫𝖴 ( ⋅ ) \mathop{\mathsf{ReLU}}(\cdot) ) .

###### Proof.

###### Lemma B.3 (Lipschitzness of FFN) .

###### Proof.

###### Lemma B.4 (Lipschitzness of Functions with Bounded Jacobian; Modified from Lemma A.6 of (Edelman et al., 2022 ) ) .

###### Proof.

###### Lemma B.5 (Lipschitzness of Softmax ( ⋅ ) \mathop{{\rm Softmax}}(\cdot) ; Modified from Corollary A.7 of (Edelman et al., 2022 ) ) .

###### Proof.

###### Lemma B.6 (Lipschitzness of Multi-Head Self-Attention) .

###### Proof.

##### Lipschitzness of Transformer.

Now we state our result on the Lipschitzness of transformer.

###### Lemma B.7 (Lipschitzness of Transformer Block) .

Let

$$ $\displaystyle f_{\mathcal{T}}:=F^{\rm FF}_{1}\circ F^{\rm SA}\circ F^{\rm FF}_{2},$ $$

be a Transformer block in the class

$$ $\displaystyle\mathcal{T}^{h,s,r}(C_{\mathcal{T}},C^{2,\infty}_{KQ},C_{KQ},C^{2,\infty}_{OV},C_{OV},C_{E},C^{2,\infty}_{F},C_{F}).$ $$

If $X\in\mathbb{R}^{d\times L}$ satisfies $\|X\|\leq B_{X}$, then $f_{\mathcal{T}}$ is Lipschitz continuous w.r.t. the Frobenius norm $\|\cdot\|_{F}$ with Lipschitz constant

$$ $\displaystyle L_{\mathcal{T}}\leq(1+2h(B_{X})^{2}C_{OV}C_{KQ}+hLC_{OV})\cdot(C_{F}^{2}+1)^{2}.$ $$

###### Proof.

This is a direct consequence of combining [Lemma˜B.3](https://arxiv.org/html/2509.22623v1#A2.Thmlemma3) and [Lemma˜B.6](https://arxiv.org/html/2509.22623v1#A2.Thmlemma6) with [Lemma˜B.1](https://arxiv.org/html/2509.22623v1#A2.Thmlemma1).
∎

###### Remark B.1 (Near-Optimality of the Lipschitz Bound) .

We remark that the upper bound on the Lipschitz constant in [Lemma˜B.7](https://arxiv.org/html/2509.22623v1#A2.Thmlemma7) is near-optimal in its dependence on the key parameters.
To illustrate this, we construct a worst-case example as follows.
Let $A\in\mathbb{R}^{d\times L}$ be the diagonal matrix

$$ $\displaystyle A_{ij}=\begin{cases}1,\penalty 10000\ &i=j,\\ 0,\penalty 10000\ &i\neq j.\end{cases}$ $$

Consider the network $f_{\mathcal{T}}$ with parameter

$$ $\displaystyle W^{i}_{OV}=C_{OV}I_{d},\quad W^{i}_{KQ}=C_{KQ}I_{d},\quad W_{1}=W_{2}=C_{F}A,$ $$

where $I_{d}$ is the $d\times d$ identity.

A direct calculation shows that the operator norm of the directional derivative of $f_{\mathcal{T}}$ at an input $Z$ in direction $V$ scales with the same order as the upper bound in [Lemma˜B.7](https://arxiv.org/html/2509.22623v1#A2.Thmlemma7), up to constants and polynomial factors in $d$.
Hence the bound in [Lemma˜B.7](https://arxiv.org/html/2509.22623v1#A2.Thmlemma7) provides a tight estimate by construction.

###### Lemma B.7 (Lipschitzness of Transformer Block) .

###### Proof.

###### Remark B.1 (Near-Optimality of the Lipschitz Bound) .

#### B.3 Universal Approximation of Transformers

Previous works (Hu et al., 2024b; Kajitsuka and Sato, 2023; Yun et al., 2019) study the universal approximation property of Transformers for continuous functions.
In this section, we restate the proofs for completeness and adapt the parameter estimates to the discrete flow-matching framework.
This adaptation highlights the connection between universal approximation and our discrete setting.

##### Background: Contextual Mapping.

Concept of contextual mapping is key to the proof of universal approximation of transformer.
We restate the definition of contextual mapping and related concepts introduced by Kajitsuka and Sato (2023) for completeness.
To start with, we introduce the concept of Vocabulary.
We use $Z_{:,k}$ to denote the $k$-th column of vector $Z$.

###### Definition B.5 (Vocabulary) .

Let $Z\in\mathbb{R}^{d\times L}$ represent input embeddings.
Specifically, given $N$ embeddings $Z^{(1)},\dots,Z^{(N)}\in\mathbb{R}^{d\times L}$, we call $Z^{(i)}$ the $i$-th sequence for $i\in[N]$.
Further, we define the $i$-th vocabulary set as $\mathcal{V}^{(i)}=\cup_{k\in[L]}Z^{(i)}_{:,k}\subset\mathbb{R}^{d}$.
Then the whole vocabulary set $\mathcal{V}$ is defined as $\mathcal{V}=\cup_{i\in[N]}\mathcal{V}^{(i)}\in\mathbb{R}^{d}$.

We assume embeddings are separate.
Specifically, we assume embeddings are $(\gamma_{\rm min},\gamma_{\rm max},\delta)$-separated defined below.

###### Definition B.6 (Tokenwise Separateness) .

Let $Z^{(1)},\dots,Z^{(N)}\in\mathbb{R}^{d\times L}$ be embeddings.
Then $Z^{(1)},\dots,Z^{(N)}$ are called tokenwise $(\gamma_{\rm min},\gamma_{\rm max},\delta)$-separated if the following conditions hold:

- (i)
For any $i\in[N]$ and $k\in[L]$, $\|Z^{(i)}_{:,k}\|>\gamma_{\rm min}$ holds.
- (ii)
For any $i\in[N]$ and $k\in[L]$, $\|Z^{(i)}_{:,k}\|<\gamma_{\rm max}$ holds.
- (iii)
For any $i,j\in[N]$ and $k,m\in[L]$, if $Z^{(i)}_{:,k}\neq Z^{(j)}_{:,m}$, then $\|Z^{(i)}_{:,k}-Z^{(j)}_{:,m}\|>\delta$ holds.

Further, $Z^{(1)},\dots,Z^{(N)}$ are called tokenwise $(\gamma,\delta)$-separated if only (ii) and (iii) hold.
Also, $Z^{(1)},\dots,Z^{(N)}$ are called tokenwise $\delta$-separated if only (iii) holds.

Building on the condition (ii) and (iii) in [Definition˜B.6](https://arxiv.org/html/2509.22623v1#A2.Thmdefinition6), we introduce the concept of contextual mapping.
Contextual mapping describes attention layer’s ability to distinguish difference and relationship between tokens in different input sequences.

###### Definition B.7 (Contextual Mapping) .

Let $Z^{(1)},\dots,Z^{(N)}\in\mathbb{R}^{d\times L}$ be embeddings.
Then, we say a map $f:\mathbb{R}^{d\times L}\to\mathbb{R}^{d\times L}$ is a $(\gamma,\delta)$-contextual mapping if the following conditions hold:

- (i)
For For any $i\in[N]$ and $k\in[L]$, $\|f(Z^{(i)})_{:,k}\|<\gamma$ holds.
- (ii)
For any $i,j\in[N]$ and $k,m\in[L]$, if $\mathcal{V}^{(i)}\neq\mathcal{V}^{(j)}$ or $Z^{(i)}_{:,k}\neq Z^{(j)}_{:,m}$, then $\|f(Z^{(i)})_{:,k}-f(Z^{(j)})_{:,m}\|>\delta$ holds.

Helper Lemma.
We restate a lemma from (Hu et al., 2024a).
This lemma guarantee the existence of 1-layer single head attention that is $(\gamma,\delta)$-contextual mapping.

###### Lemma B.8 (Any-Rank Attention is $(\gamma,\delta)$ -Contextual Mapping, Lemma 2.2 of (Hu et al., 2024a ) ) .

Let $Z^{(1)},\dots,Z^{(N)}\in\mathbb{R}^{d\times L}$ be tokenwise $(\gamma_{\rm min},\gamma_{\rm max},\epsilon)$-separated embeddings with the vocabulary set $\mathcal{V}=\cup_{i\in[N]}\mathcal{V}^{(i)}\subset\mathbb{R}^{d}$.
Assume there are no duplicate token in each sequence; that is, $Z^{(i)}_{:,k}\neq Z^{(i)}_{:,m}$ for $i\in[N]$ and $k,m\in[L]$.
Then there exists a 1-layer single head attention layer that is a $(\gamma,\delta)$-contextual mapping for the embeddings $Z^{(1)},\dots,Z^{(N)}$ with

$$ $\displaystyle\gamma=\gamma_{\rm max}+\frac{\epsilon}{4},\penalty 10000\ \delta=\exp(-\frac{5|\mathcal{V}|^{4}d\kappa\gamma_{\rm max}\log L}{\epsilon}),$ $$

where $\kappa:=\frac{\gamma_{\rm max}}{\gamma_{\rm min}}$.

###### Proof.

See the proof of (Hu et al., 2024a, Lemma 2.2).
∎

###### Definition B.5 (Vocabulary) .

###### Definition B.6 (Tokenwise Separateness) .

###### Definition B.7 (Contextual Mapping) .

###### Lemma B.8 (Any-Rank Attention is ( γ , δ ) (\gamma,\delta) -Contextual Mapping, Lemma 2.2 of (Hu et al., 2024a ) ) .

###### Proof.

##### Universal Approximation of Transformer.

We introduce the universal approximation theory of transformer in (Su et al., 2025) and restate the proof for completeness.

###### Theorem B.1 (Transformer Universal Approximation, Theorem H.2 of (Su et al., 2025 ) ) .

Let $\epsilon\in(0,1)$ and $p\in[1,\infty)$.
Let $Z\in[-I,I]^{d\times L}$ be an input sequence on a bounder domain, where $I>0$.
Let $f(Z):[-I,I]^{d\times L}\to\mathbb{R}^{d\times L}$ be a continuous function on a bounded domain.
Then there exists a $g(Z)=F^{\rm FF}_{1}\circ F^{\rm SA}\circ F^{\rm FF}_{2}\in\mathcal{T}^{h,s,r}$ such that $d_{F}(f(Z),g(Z))<\epsilon$, where $d_{F}:=(\int\|f(Z)-g(Z)\|_{F}^{2}\differential Z)^{\frac{1}{2}}$.

###### Proof.

Here, we restate the proof of (Su et al., 2025, Theorem H.2) for completeness.

The proof proceeds in four parts:

- •
Step 1: Approximation using step function
- •
Step 2: Quantization by the first feed-forward layer
- •
Step 3: Contextual mapping through the self-attention layer
- •
Step 4: Memorization via the second feed-forward layer

Step 1: Approximation using Step Function.
We assume the domain of $f$ is $\Omega=[-I,I]^{d\times L}$.

Then we construct the grid $\mathbb{G}_{D}$ as :

$$ $\displaystyle\mathbb{G}_{D}:=\{C\in\Omega|C_{i,k}=-I+\frac{s_{i,k}}{D},s_{i,k}=1,\dots,2ID,\}$ $$

where $D>0$ is the grid granularity.
Given $Z\in\Omega$, we approximate $f$ via the step function

$$ $\displaystyle g_{1}(Z)=\sum_{C\in\mathbb{G}_{D}}f(C)\mathds{1}\{Z\in C+[-1/D,0)^{d\times L}\}.$ $$

By uniform continuity of $f$ , there exists $D$ such that

$$ $\displaystyle d_{F}(f,g_{1})<\frac{\epsilon}{3}.$ $$

Then we use a transformer to approximate the step function $g_{1}(Z)$.

Step 2: Quantization by the First Feed-forward Layer.
The quantification function we want to approximate consists of two parts, namely, the quantize function and the penalty function.
We approximate two parts separately.

- •
Quantize Function
We define the quantization function ${\rm quant}_{D}:\mathbb{R}\to\mathbb{R}$:
$\displaystyle{\rm quant}_{D}(z):=\begin{cases}-I&\penalty 10000\ z<-I,\\
-I+1/D&\penalty 10000\ -I\leq z<-I+1/D,\\
\vdots&\penalty 10000\ \vdots\\
I&\penalty 10000\ I-1/D\leq z.\end{cases}$
Further, we define the quantize function ${\rm quant}^{d\times L}_{D}(Z):\mathbb{R}^{d\times L}\to\mathbb{R}^{d\times L}$ as the entrywise quantize function, such that $({\rm quant}^{d\times L}_{D}(Z))_{t,k}={\rm quant}_{D}(Z_{t,k})$.
Notice that ${\rm quant}_{D}(z)$ is approximated through the following function by taking sufficiently small $\delta$:
$\displaystyle f_{1}(z):=-I+\sum_{t=-ID}^{I(D-1)}\frac{\rm RELU[z/\delta-t/\delta D]-\mathop{\mathsf{ReLU}}[z/\delta-1-t/\delta D]}{D}.$
(B.1)
That’s to say, there exists RELU feed-forward network approximating ${\rm quant}^{d\times L}_{D}(Z)$.
- •
Penalty Function
We define the penalty function ${\rm penalty}:\mathbb{R}\to\mathbb{R}$:
$\displaystyle{\rm penalty}(z):=\begin{cases}-1&\penalty 10000\ z<-I,\\
0&\penalty 10000\ z\in[-I,I],\\
1&\penalty 10000\ z>I.\end{cases}$
Further, we define the penalty function ${\rm penalty}^{d\times L}(Z):\mathbb{R}^{d\times L}\to\mathbb{R}^{d\times L}$ as the entrywise penalty function, such that $({\rm penalty}^{d\times L}(Z))_{t,k}={\rm quant}_{D}(Z_{t,k})$.
Notice that ${\rm penalty}(z)$ is approximated through the following function by taking sufficiently small $\delta$:
$\displaystyle f_{2}(z)=$
$\displaystyle\penalty 10000\ \mathop{\mathsf{ReLU}}[(z-I)/\delta]-\mathop{\mathsf{ReLU}}[(z-I)/\delta+1]$
$\displaystyle\penalty 10000\ +\mathop{\mathsf{ReLU}}[(-z-I)/\delta]-\mathop{\mathsf{ReLU}}[(-z-I)/\delta+1]$
(B.2)
That’s to say, there exists RELU feed-forward network approximating ${\rm penalty}^{d\times L}(Z)$.

Altogether, we define $g_{2}(Z):\mathbb{R}^{d\times L}\to\mathbb{R}^{d\times L}$ as :

$$ $\displaystyle g_{2}(Z):=\frac{{\rm quant}^{d\times L}_{D}(Z)+I}{2I}+{\rm penalty}^{d\times L}(Z).$ $$

$g_{2}(Z)$ map $[-I,I]^{d\times L}$ into normalized grid $\mathbb{G}_{D}^{\rm norm}\subset[0,1]^{d\times L}$ with gride granularity $2ID$.
At the same time, $g_{2}(Z)$ guarantees non-positive outputs on domain $\mathbb{R}^{d\times L}\backslash[-I,I]^{d\times L}$.
We use $f_{1}(z)$ and $f_{2}(z)$ introduced above to construct the first feed-forward layer $F^{\rm FF}_{1}$.

Step 3: Contextual Mapping through the Self-attention Layer.
Let $\macc@depth\@ne\macc@set@skewchar\macc@nested@a 111{}_{D}$ denote the following sub-grid class on $[0,1]^{d\times L}$:

$$ $\displaystyle\macc@depth\@ne\macc@set@skewchar\macc@nested@a 111{}_{D}:=\{G\in\mathbb{G}_{D}^{\rm norm}\mid{\rm for\penalty 10000\ all\penalty 10000\ }k,m\in[L],G_{:,k}\neq G_{:,m}\}.$ $$

The by definition, $\macc@depth\@ne\macc@set@skewchar\macc@nested@a 111{}_{D}$ is a token class with token-wise $((2ID)^{-1},\sqrt{d},(2ID)^{-1})$-separated sequence.
Following the construction of $F^{\rm SA}$ in proof of (Su et al., 2025, Theorem H.2), for sufficiently large $D$ we have:

$$ $\displaystyle F^{\rm SA}\circ F^{\rm FF}_{1}(Z)_{t,k}<$ $\displaystyle\penalty 10000\ \frac{1}{4D}\quad{\rm for\penalty 10000\ all}\quad Z\in\mathbb{R}^{d\times L}\backslash[-I,I]^{d\times L},\quad t\in[d],k\in[L],$ $\displaystyle F^{\rm SA}\circ F^{\rm FF}_{1}(Z)_{t,k}>$ $\displaystyle\penalty 10000\ \frac{3}{4D}\quad{\rm for\penalty 10000\ all}\quad Z\in[-I,I]^{d\times L},\quad t\in[d],k\in[L].$ $$

Step 4: Memorization via the Second Feed-forward Layer.
Finally, we construct a bump function of scale $R>0$ to map every $c\in\macc@depth\@ne\macc@set@skewchar\macc@nested@a 111{}_{D}$ to its label $f(C)$ and sends any sequence that lies component-wise below the threshold $1/(4D)$ to zero.
Precisely, for each $C\in\mathbb{G}_{D}^{\rm norm}$ we construct a bump function of scale $R$:

$$ $\displaystyle{\rm bump}_{R}(Z)=$ $\displaystyle\penalty 10000\ \frac{f(2C-I)}{dL}\sum_{t=1}^{d}\sum_{k=1}^{L}({\rm RELU[R(Z_{t,k}-C_{t,k})-1]}$ $\displaystyle\penalty 10000\ -\mathop{\mathsf{ReLU}}[R(Z_{t,k}-C_{t,k})]+\mathop{\mathsf{ReLU}}[R(Z_{t,k}-C_{t,k})+1]).$ (B.3) $$

Summing up over $C\in\mathbb{G}_{D}^{\rm norm}$ and we obtain the second feed-forward layer $F_{2}^{\rm FF}$.

We sum up the error bound in four steps.
As discussed in the step approximation using step function, there exists $D$ such that

$$ $\displaystyle d_{F}(f,g_{1})<\frac{\epsilon}{3}.$ $$

By choosing sifficiently quantization step $\delta>0$, we obtain

$$ $\displaystyle d_{F}(F^{\rm FF}_{2}\circ F^{\rm SA}\circ F^{\rm FF}_{1},F^{\rm FF}_{2}\circ F^{\rm SA}\circ g_{2})<\frac{\epsilon}{3}.$ $$

By choosing granularity $D$ large enough, $|\mathbb{G}_{D}\backslash\mathbb{G}_{D}^{\rm norm}|$ is negligible.
Then we have for large enough $D$ and $R$,

$$ $\displaystyle d_{F}(F^{\rm FF}_{2}\circ F^{\rm SA}\circ g_{2},g_{1})<\frac{\epsilon}{3}.$ $$

Altogether, summing up the error we have:

$$ $\displaystyle d_{F}(f(Z),g(Z))<\epsilon.$ $$

This completes the proof.
∎

###### Theorem B.1 (Transformer Universal Approximation, Theorem H.2 of (Su et al., 2025 ) ) .

###### Proof.

##### Parameter Norm Bounds of Transformer Approximator.

Next, we compute the norm bound of the approximator transformer in [Theorem˜B.1](https://arxiv.org/html/2509.22623v1#A2.Thmtheorem1).
This theorem is modified from of (Su et al., 2025, Lemma H.4).
The main difference is that we also take polynomial factor of $L$ into the final result instead of neglecting it, while other parts of computation is similar.

###### Theorem B.2 (Parameter Norm Bound for Approximator Transformer, Modified from Lemma H.4 of (Su et al., 2025 ) ) .

Let $\epsilon\in(0,1)$.
Consider $Z\in[-I,I]^{d\times L}$ be input sequence, where $I>0$ and $L>2$.
Let Let $f(Z):[-I,I]^{d\times L}\to\mathbb{R}^{d\times L}$ be a Lipschitz continuous function with respect to Frobenius norm on a bounded domain.
Then for the approximator $g(Z)=F^{\rm FF}_{1}\circ F^{\rm SA}\circ F^{\rm FF}_{2}\in\mathcal{T}^{h,s,r}$ in [Theorem˜B.1](https://arxiv.org/html/2509.22623v1#A2.Thmtheorem1) within $\epsilon$ precision, i.e., $d_{F}(f,g)<\epsilon$, the parameter bound in the transformer network class follow:

$$ $\displaystyle\penalty 10000\ C_{KQ},C^{2,\infty}_{KQ}=O(I^{4d+2}\epsilon^{-4d-2}L^{2d+1}\log L);C_{OV},C^{2,\infty}_{OV}=O(\epsilon L^{-1/2})$ $\displaystyle\penalty 10000\ C_{F},C^{2,\infty}_{F}=O(I\epsilon^{-1}L\cdot\max\|f(Z)\|_{F});C_{E}=O(L),$ $$

where $O(\cdot)$ hides polynomial factors depending on $d$.

###### Proof.

The proof is modified from proof of (Su et al., 2025, Lemma H.4).

Recall that we take sufficiently large $D,R$ and sufficiently small $\delta$ in proof of [Theorem˜B.1](https://arxiv.org/html/2509.22623v1#A2.Thmtheorem1) to ensure the precision.
We then start with bounding $D,R,\delta$ in terms of $\epsilon$.

- •
Bound on $\delta$.
Recall the approximation in ([B.1](https://arxiv.org/html/2509.22623v1#A2.E1)) and ([• ‣ B.3](https://arxiv.org/html/2509.22623v1#A2.Ex55)).
To guarantee the effect of grid, we hope partition $(i/D,i/D+\delta)$ is a contained in the interval $(i/D,(i+1)/D)$ where $i\in\mathbb{Z}^{+}$.
Then it’s sufficient to take $\delta=o(1/D)$.
- •
Bound on $D$.
For Lipschitz continuous function $f$ with respect to Frobenius norm with Lipschitz constant $L_{f}$, we have
$\displaystyle d_{F}(f(Z),g_{1}(Z))\leq L_{f}\|Z-Z^{*}\|_{F}\leq 2\sqrt{dL}L_{f}/D,$
where $Z^{*}={\rm argmin}_{Z^{\prime}\in\macc@depth\@ne\macc@set@skewchar\macc@nested@a 111{}_{D}}\|Z-Z^{\prime}\|_{F}$.
Then we take $D=O(\epsilon^{-1}\sqrt{L})$.
- •
Bound on $R$.
To obtain the correct labeling in ([B.3](https://arxiv.org/html/2509.22623v1#A2.Ex60)), we need $S_{t,k}:=Z_{t,k}-C_{t,k}\in(0,1/R)$ for all $t\in[d],k\in[L]$.
Then since $C_{t,k}$ is defined on $\mathbb{G}^{\rm norm}_{D}$ with granularity $2DI$ and is chosen close enough to $Z_{t,k}$, it suffices to set $R=O(DI)$.

Next, we get the norm bound of matrices on the basis of computation above.
Since the $F^{\rm SA}$ is a single head self-attention layer, we directly write $W_{K}^{1},W_{Q}^{1},W_{V}^{1},W_{O}^{1}$ as $W_{K},W_{Q},W_{V},W_{O}$ for simplicity of notations.

- •
Bound on Norm of $W_{KQ}$.
Recall that in the proof of Theorem H.1 of (Su et al., 2025), $W_{K}$ and $W_{Q}$ follows the construction of
$\displaystyle W_{K}=\sum_{i=1}^{\rho}p_{i}q_{i}^{\top}\in\mathbb{R}^{s\times d},W_{Q}=\sum_{i=1}^{\rho}p_{i}^{\prime}q_{i}^{\prime\top}\in\mathbb{R}^{s\times d},$
where $p_{i}^{\top}p_{i}^{\prime}=(|\mathcal{V|}+1)^{4}d\log L/(\epsilon_{s}\gamma_{\rm min})$.
Then we have
$\displaystyle\penalty 10000\ \|W_{KQ}\|_{2}\leq\|W_{KQ}\|_{F}=\|W_{K}^{\top}W_{Q}\|_{F}=O(\frac{4\log L|V|^{4}}{\epsilon_{s}\gamma_{\rm min}}),$
$\displaystyle\penalty 10000\ \|W_{KQ}\|_{2,\infty}=\|W_{K}^{\top}W_{Q}\|_{2,\infty}=O(\frac{4\log L|V|^{4}}{\epsilon_{s}\gamma_{\rm min}}).$
Recall that input $\macc@depth\@ne\macc@set@skewchar\macc@nested@a 111{}_{D}$ is a token class with token-wise $((2ID)^{-1},\sqrt{d},(2ID)^{-1})$-separated sequence.
Then $|V|=O((DI)^{d})$ and $\gamma_{\rm min},\epsilon_{s}=(2DI)^{-1}$.
Finally, by $D=O(\epsilon^{-1}\sqrt{L})$, we get
$\displaystyle\|W_{KQ}\|_{2},\|W_{KQ}\|_{2,\infty}=O(\epsilon^{-4d-2}I^{4d+2}L^{2d+1}\log L).$
- •
Bound on Norm of $W_{OV}$.
Recall that in the proof of Theorem H.1 of (Su et al., 2025), $W_{O}$ and $W_{V}$ follows the construction of
$\displaystyle W_{O}=\sum_{i=1}^{\rho}p_{i}^{\prime\prime}q_{i}^{\prime\prime\top}\in\mathbb{R}^{s\times d},W_{V}=\sum_{i=1}^{\rho}p_{i}^{\prime\prime\prime\prime}p_{i}^{\prime\prime\top}\in\mathbb{R}^{d\times s},$
where $\|p_{i}^{\prime\prime\prime}\|\lesssim\epsilon_{s}/(4\rho\gamma_{\rm max}\|p_{i}^{\prime\prime}\|)$ and $p_{i}^{\prime\prime}\in\mathbb{R}^{s}$ is any nonzero vector.
Then with the $(\gamma_{\rm min}=1/D,\gamma_{\rm max}=\sqrt{d},\epsilon_{s}=1/D)$-separateness and $D=O(\epsilon^{-1}\sqrt{L}),\rho<d$, we get:
$\displaystyle\penalty 10000\ \|W_{V}\|_{2}=\sup_{\|x\|_{2}=1}\|W_{V}x\|_{2}\leq O(\sqrt{\rho})\leq O(\sqrt{d}),$
$\displaystyle\penalty 10000\ \|W_{V}\|_{2,\infty}=\max_{1\leq i\leq d}\|(W_{V})_{(i,:)}\|_{2}\leq O(\rho)\leq O(d),$
$\displaystyle\penalty 10000\ \|W_{O}\|_{2}=\sup_{\|x\|_{2}=1}\|W_{O}x\|_{2}\leq O(\sqrt{\rho}\cdot\rho^{-1}\cdot\gamma^{-1}_{\rm max}\cdot\epsilon_{s})=O(d^{-1}\epsilon L^{-1/2}),$
$\displaystyle\penalty 10000\ \|W_{O}\|_{2,\infty}=\max_{1\leq i\leq d}\|(W_{O})_{(i,:)}\|_{2}\leq O(\rho\cdot\rho^{-1}\cdot\gamma^{-1}_{\rm max}\cdot\epsilon_{s})=O(d^{-1/2}\epsilon L^{-1/2}).$
Therefore we get:
$\displaystyle\|W_{OV}\|_{2}=\|W_{O}W_{V}\|_{2}\leq O(\epsilon L^{-1/2}),\|W_{OV}\|_{2,\infty}=\|W_{O}W_{V}\|_{2,\infty}\leq O(\epsilon L^{-1/2}).$
- •
Bound on Norm of $W_{1}^{1}$ and $W_{2}^{1}$ in $F^{\rm FF}_{1}$.
Recall that in the construction of the first feed-forward layer, we have two key approximator:
$\displaystyle f_{1}(z):=-I+\sum_{t=-ID}^{I(D-1)}\frac{\rm RELU[z/\delta-t/\delta D]-\mathop{\mathsf{ReLU}}[z/\delta-1-t/\delta D]}{D},$
and
$\displaystyle f_{2}(z)=$
$\displaystyle\penalty 10000\ \mathop{\mathsf{ReLU}}[(z-I)/\delta]-\mathop{\mathsf{ReLU}}[(z-I)/\delta+1]+$
$\displaystyle\penalty 10000\ \mathop{\mathsf{ReLU}}[(-z-I)/\delta]-\mathop{\mathsf{ReLU}}[(-z-I)/\delta+1].$
Then for $t\in[d],k\in[L]$, we approximate each entry of $g_{1}(Z)$ with
$\displaystyle F^{\rm FF}_{1}(Z)_{t,k}=\frac{f_{1}(Z_{t,k})+I}{2I}+f_{2}(Z_{t,k}).$
That’s to say, each element in $W_{1}$ and $W_{2}$ is bounded by $1/\delta$ and $I$.
Recall that $\delta=o(1/D)$ and $D=O(\epsilon^{-1}\sqrt{L})$, we have
$\displaystyle\max\{\|W_{1}^{1}\|_{2},\|W_{2}^{1}\|_{2}\}\leq O(\epsilon^{-1}L),\max\{\|W_{1}^{1}\|_{2,\infty},\|W_{2}^{1}\|_{2,\infty}\}\leq O(\epsilon^{-1}L).$
- •
Bound on Norm of $W_{1}^{2}$ and $W_{2}^{2}$ in $F^{\rm FF}_{2}$.
Recall that in the construction of the second feed-forward layer, we construct $F^{\rm FF}_{2}$ through bump function:
$\displaystyle{\rm bump}_{R}(Z)=$
$\displaystyle\penalty 10000\ \frac{f(2C-I)}{dL}\sum_{t=1}^{d}\sum_{k=1}^{L}({\rm RELU[R(Z_{t,k}-C_{t,k})-1]}$
$\displaystyle\penalty 10000\ -\mathop{\mathsf{ReLU}}[R(Z_{t,k}-C_{t,k})]+\mathop{\mathsf{ReLU}}[R(Z_{t,k}-C_{t,k})+1]).$
Therefore, the output of $F^{\rm FF}_{2}$ is bounded by $R$ and $\max\|f(Z)\|_{F}$.
Then by $R=O(DI)$ and $D=O(\epsilon^{-1}\sqrt{L})$, we have:
$\displaystyle\penalty 10000\ \max\{\|W_{1}^{2}\|_{2},\|W_{2}^{2}\|_{2}\}\leq O(I\epsilon^{-1}L\cdot\max\|f(Z)\|_{F}),$
$\displaystyle\penalty 10000\ \max\{\|W_{1}^{2}\|_{2,\infty},\|W_{2}^{2}\|_{2,\infty}\}\leq O(I\epsilon^{-1}L\cdot\max\|f(Z)\|_{F}).$
- •
Bound on Norm of Encoding Matrix $E$.
By Corollary 2 of (Kajitsuka and Sato, 2023), it suffices to take the encoding matrix $E$:
$\displaystyle E=\begin{bmatrix}2\gamma_{\rm max}&4\gamma_{\rm max}&\dots&2L\gamma_{\rm max}\\
2\gamma_{\rm max}&4\gamma_{\rm max}&\dots&2L\gamma_{\rm max}\\
\vdots&\vdots&&\vdots\\
2\gamma_{\rm max}&4\gamma_{\rm max}&\dots&2L\gamma_{\rm max}\end{bmatrix}.$
Recall that we have $\gamma_{\rm max}=\sqrt{d}$, then we obtain:
$\displaystyle\|E^{\top}\|_{2,\infty}=\sqrt{4dL^{2}}\gamma_{\rm max}=O(L).$

This complete the proof.
∎

###### Theorem B.2 (Parameter Norm Bound for Approximator Transformer, Modified from Lemma H.4 of (Su et al., 2025 ) ) .

###### Proof.

### Appendix C Proof of Theorem ˜ 3.1

This section provides the proof of [Theorem˜3.1](https://arxiv.org/html/2509.22623v1#S3.Thmtheorem1).

Organization.
Due to the complexity of the proof, our proof proceeds in two steps: (i) First, in [Lemma˜C.2](https://arxiv.org/html/2509.22623v1#A3.Thmlemma2), we establish a key intermediate result by presenting the distribution error in terms of the velocity error.
(ii) Second, building upon this lemma, we present the final proof of [Theorem˜3.1](https://arxiv.org/html/2509.22623v1#S3.Thmtheorem1) in [Theorem˜C.2](https://arxiv.org/html/2509.22623v1#A3.Thmtheorem2) by applying Grönwall’s Inequality.

#### C.1 Preliminaries

Total Variation Distance is a distance function defined between probability distributions.
We start with the definition of total variation distance as below.

###### Definition C.1 (Total Variation Distance) .

Let $P$ and $Q$ be two probability distributions defined on a discrete state space $S$, with corresponding probability mass functions $p(x)$ and $q(x)$.
Then the total variation (TV) distance between them is defined as:

$$ $\displaystyle\text{TV}(P,Q):=\frac{1}{2}\sum_{x\in S}|p(x)-q(x)|.$ $$

Our analysis relies on Grönwall’s Inequality.
It is a fundamental tool for establishing bounds on the solutions of ordinary differential equations (ODEs).

###### Lemma C.1 (Grönwall’s Inequality, (Gronwall, 1919 ) ) .

Let $a,b\in\mathbb{R}$ satisfy $a<b$.
Let $y(t)$ and $f(t)$ be two real value function defined on $[a,b]$.
Suppose that $y(t)$ is differentiable on $[a,b]$ and satisfies:

$$ $\displaystyle\frac{\differential}{\differential t}y(t)\leq y(t)f(t),t\in[a,b].$ $$

Then we have:

$$ $\displaystyle y(b)\leq y(a)\exp(\int_{a}^{b}f(s)\differential s).$ $$

To analyze the distribution error, we first express the DFM framework in the language of linear algebra.
Let the discrete state space be indexed as $S=\{w_{1},\ldots,w_{|S|}\}$.
We represent the ground-truth probability mass function $p_{t}(x)$ and its corresponding estimator $p_{t,\theta}(x)$ as vectors $p_{t},p_{t,\theta}$ in $\mathbb{R}^{|S|}$, where $p_{t}[i]=p_{t}(w_{i})$ and $p_{t,\theta}[i]=p_{t,\theta}(w_{i})$.
Similarly, the velocity fields are represented as rates matrices $U_{t},U_{t,\theta}\in\mathbb{R}^{|S|\times|S|}$, where the entry $[U_{t}]_{ij}=u_{t}(w_{i},w_{j}),[U_{t,\theta}]_{ij}=u_{t,\theta}(w_{i},w_{j})$ is the corresponding rate of transition from state $w_{j}$ to state $w_{i}$.
With these definitions, we rewrite the Kolmogorov Forward Equation ([2.3](https://arxiv.org/html/2509.22623v1#S2.E3)) for both the true and estimated paths into the compact matrix form ([C.1](https://arxiv.org/html/2509.22623v1#A3.E1)).
Then we derive the distribution error bounds in terms of the risk function.

###### Lemma C.2 (Variation of Constants Formula for Error) .

Let the true probability vector $p_{t}$ and the estimated vector $p_{t,\theta}$ be solutions to the linear differential systems

$$ $\displaystyle\begin{cases}\frac{\differential}{\differential t}p_{t}=U_{t}p_{t},\\ \frac{\differential}{\differential t}p_{t,\theta}=U_{t,\theta}p_{t,\theta},\end{cases}$ (C.1) $$

with a shared initial condition $p_{0}=p_{0,\theta}$.
Let the evolution operator for the estimated system be $\mathcal{P}_{s,t,\theta}\in\mathbb{R}^{|S|\times|S|}$, which is the solution to $\frac{\differential}{\differential t}\mathcal{P}_{s,t,\theta}=U_{t,\theta}\mathcal{P}_{s,t,\theta}$ with $\mathcal{P}_{s,s,\theta}=I$.
The difference between the distributions at time $t>0$ is given by

$$ $\displaystyle p_{t,\theta}-p_{t}=\int_{0}^{t}\mathcal{P}_{s,t,\theta}(U_{s,\theta}-U_{s})p_{s}\differential s.$ $$

###### Proof.

We construct the helping function $Z(s)$ as:

$$ $\displaystyle Z(s)=\mathcal{P}_{s,t,\theta}p_{s}.$ (C.2) $$

Then since $\mathcal{P}_{s,t,\theta}$ and $p_{s}$ is differentiable, we have:

$$ $\displaystyle\frac{\differential}{\differential s}Z(s)=$ $\displaystyle\penalty 10000\ (\frac{\differential}{\differential s}\mathcal{P}_{s,t,\theta})p_{s}+\mathcal{P}_{s,t,\theta}(\frac{\differential}{\differential s}p_{s})$ ( By ( C.2 ) ) $\displaystyle=$ $\displaystyle\penalty 10000\ (-\mathcal{P}_{s,t,\theta}U_{s,\theta})p_{s}+\mathcal{P}_{s,t,\theta}(U_{s}p_{s})$ ( By backward Kolmogorov Equation ( 2.3 ) and ( C.1 ) ) $\displaystyle=$ $\displaystyle\penalty 10000\ -\mathcal{P}_{s,t,\theta}(U_{s,\theta}-U_{s})p_{s}.$ (C.3) $$

Integrating ([C.3](https://arxiv.org/html/2509.22623v1#A3.E3)), we obtain:

$$ $\displaystyle-\int_{0}^{t}\mathcal{P}_{s,t,\theta}(U_{s,\theta}-U_{s})p_{s}\differential s=\int_{0}^{t}\frac{\differential}{\differential s}Z(s)\differential s=Z(t)-Z(0)=p_{t}-p_{t,\theta}.$ $$

This completes the proof.
∎

###### Definition C.1 (Total Variation Distance) .

###### Lemma C.1 (Grönwall’s Inequality, (Gronwall, 1919 ) ) .

###### Lemma C.2 (Variation of Constants Formula for Error) .

###### Proof.

#### C.2 Main Proof of Theorem ˜ 3.1

Before studying the tractable factorized velocity ([Section˜2](https://arxiv.org/html/2509.22623v1#S2)) case, we first establish a foundational error bound for the general discrete flow matching framework.
Presenting the universal principle first makes our subsequent, more detailed analysis clearer and more readable.

###### Theorem C.1 (Error Bounds for Discrete Flow Matching) .

Consider the discrete state space $\mathcal{S}=\mathcal{T}^{d}$, where the vocabulary is $\mathcal{T}=\{1,\ldots,M\}$.
Let $P$ be the true data distribution over $\mathcal{S}$.
Let $\widehat{u}_{\theta}$ be the velocity estimator, with parameters $\widehat{\Theta}$ and let $\widehat{P}$ be the distribution generated using this estimator.
Define the risk of the velocity estimator as

$$ $\displaystyle\mathcal{R}(\widehat{\Theta}):=\int_{0}^{1}\underset{X_{t}\sim p_{t}(x)}{\mathbb{E}}\|u(X_{t},t)-u_{\widehat{\theta}}(X_{t},t)\|_{2}^{2}\differential t,$ $$

where $p_{t}(x)$ is the true probability path. Then, the total variation distance between the true and generated distributions is bounded by the risk of this estimator:

$$ $\displaystyle\text{TV}(P,\widehat{P})\lesssim\exp(M_{u})M^{\frac{d}{2}}\sqrt{\mathcal{R}(\widehat{\Theta})},$ $$

where $M_{u}$ is the upper bound of the true velocity field, satisfying $\underset{y,x\in S,t\in[0,1]}{\max}|u_{t}(y,x)|\leq M_{u}$.

###### Proof.

Following the definitions in [Lemma˜C.2](https://arxiv.org/html/2509.22623v1#A3.Thmlemma2),
let $p_{t}\in\mathbb{R}^{M^{d}}$ and $U_{t}\in\mathbb{R}^{M^{d}\times M^{d}}$ be the true probability vector and the true rates matrix.
Let $\widehat{p}_{t,\theta}\in\mathbb{R}^{M^{d}}$ and $\widehat{U}_{t,\theta}\in\mathbb{R}^{M^{d}\times M^{d}}$ be the estimated probability vectors and rates matrix defined by estimated velocity $\widehat{u}_{t,\theta}$.
Then we have:

$$ $\displaystyle\begin{cases}\frac{\differential}{\differential t}p_{t}=U_{t}p_{t},\\ \frac{\differential}{\differential t}\widehat{p}_{t,\theta}=\widehat{U}_{t,\theta}p_{t,\theta},\\ p_{0}=\widehat{p}_{0,\theta}\sim P_{0}.\end{cases}$ $$

Let evolution operator $\mathcal{P}_{s,t,\theta}$ be defined as in [Lemma˜C.2](https://arxiv.org/html/2509.22623v1#A3.Thmlemma2).
Then by definition of total variation distance, we have:

$$ $\displaystyle\text{TV}(P,\widehat{P})=$ $\displaystyle\penalty 10000\ \frac{1}{2}\sum_{x\in S}|p_{1}(x)-p_{1,\theta}(x)|$ $\displaystyle=$ $\displaystyle\penalty 10000\ \frac{1}{2}\|\widehat{p}_{1,\theta}-p_{1}\|_{1}$ $\displaystyle=$ $\displaystyle\penalty 10000\ \frac{1}{2}\|\int_{0}^{1}\mathcal{P}_{s,1,\theta}(U_{s,\theta}-U_{s})p_{s}\differential s\|_{1}$ ( By Lemma C.2 ) $\displaystyle\leq$ $\displaystyle\penalty 10000\ \int_{0}^{1}\|\mathcal{P}_{s,1,\theta}(U_{s,\theta}-U_{s})p_{s}\|_{1}\differential s,$ $\displaystyle\leq$ $\displaystyle\penalty 10000\ \int_{0}^{1}\|\mathcal{P}_{s,1,\theta}\|_{1}\|(U_{s,\theta}-U_{s})p_{s}\|_{1}\differential s$ (C.4) $$

where the last line follows by $\|p_{s}\|_{1}=1$ the sub-multiplicative property of norm $\|\cdot\|_{1}$.
To bound $\|\mathcal{P}_{s,1,\theta}\|_{F}$,
we first bound the derivative of $\|\mathcal{P}_{s,t,\theta}\|_{F}$.
Let $M$ be the vocabulary size and set the transformer estimator $u_{\widehat{\theta}}$ bound by $M_{u}$, then we have

$$ $\displaystyle\frac{\partial}{\partial t}\|\mathcal{P}_{s,t,\theta}\|_{1}\leq$ $\displaystyle\penalty 10000\ \|\frac{\partial}{\partial t}\mathcal{P}_{s,t,\theta}\|_{1}$ $\displaystyle=$ $\displaystyle\penalty 10000\ \|U_{t,\theta}\mathcal{P}_{s,t,\theta}\|_{1}$ ( By Kolmogorov Equation ) $\displaystyle\leq$ $\displaystyle\penalty 10000\ \|U_{t,\theta}\|_{1}\|\mathcal{P}_{s,t,\theta}\|_{1}$ ( By triangle inequality ) $\displaystyle\leq$ $\displaystyle\penalty 10000\ 2M_{u}\|\mathcal{P}_{s,t,\theta}\|_{1},$ (C.5) $$

where the last line follows by the maximum of the sum of absolute value if entry of $U_{t,\theta}$ in each column is less than $M^{d}M_{u}$.
Then by Grönwall’s Inequality [Lemma˜C.1](https://arxiv.org/html/2509.22623v1#A3.Thmlemma1), we have:

$$ $\displaystyle\|\mathcal{P}_{s,1,\theta}\|_{1}\leq\|\mathcal{P}_{s,s,\theta}\|_{1}\exp(\int_{0}^{t}M_{u}\differential s)\leq 2\exp(M_{u}).$ (C.6) $$

Substituting ([C.6](https://arxiv.org/html/2509.22623v1#A3.E6)) into
([C.4](https://arxiv.org/html/2509.22623v1#A3.E4)), we get:

$$ $\displaystyle\text{TV}(P,\widehat{P})\leq$ $\displaystyle\penalty 10000\ \int_{0}^{1}\|\mathcal{P}_{s,1,\theta}\|_{1}\|(U_{s,\theta}-U_{s})p_{s}\|_{1}\differential s$ ( By ( C.4 ) ) $\displaystyle\leq$ $\displaystyle\penalty 10000\ \int_{0}^{1}\exp(M_{u})\|(U_{s,\theta}-U_{s})p_{s}\|_{1}\differential s$ $\displaystyle\lesssim$ $\displaystyle\penalty 10000\ \exp(M_{u})M^{\frac{d}{2}}\sqrt{\mathcal{R}(\widehat{\Theta}))}.$ ( By the definition of risk function $\cal{R}$ ) $$

This completes the proof.
∎

Now we consider the error bounds for discrete flow matching with factorized velocity ([Section˜2](https://arxiv.org/html/2509.22623v1#S2)).

###### Theorem C.2 (Error Bounds for Discrete Flow Matching with Factorized Velocity, Theorem ˜ 3.1 Restate) .

Consider the discrete state space $\mathcal{S}=\mathcal{T}^{d}$ with vocabulary $\mathcal{T}=\{1,\ldots,M\}$.
Let $P$ be the true data distribution and let $\widehat{P}$ be the distribution generated by a DFM model using factorized velocity estimators $\widehat{u}_{\theta}^{1},\ldots,\widehat{u}_{\theta}^{d}$.
For each coordinate $i_{0}\in[d]$, define the factorized risk as the mean squared error of its velocity estimator:

$$ $\displaystyle\mathcal{R}^{i_{0}}(\widehat{\Theta}):=\int_{t_{0}}^{T}\underset{X_{t}\sim p_{t}(x)}{\mathbb{E}}\|u^{i_{0}}(X_{t},t)-\widehat{u}^{i_{0}}_{\theta}(X_{t},t)\|_{2}^{2}\differential t,$ $$

where the time interval is clipped to $[t_{0},T]$ to ensure numerical stability and $p_{t}(x)$ is true probability path generated by $u^{1},\ldots,u^{d}$. Then, the total variation distance between the true and generated distributions is bounded by the sum of the risks from each factorized component:

$$ $\displaystyle\text{TV}(P,\widehat{P})\lesssim\sqrt{M}\exp(M_{u})\sum_{i_{0}\in[d]}\sqrt{\mathcal{R}^{i_{0}}(\widehat{\Theta}))},$ $$

where $M_{u}$ is the upper bound of estimated velocity such that $\absolutevalue{u_{t}^{\theta,i}(y,x)}\leq M_{u}$ for all $y,x\in\mathcal{S}$.

###### Proof.

Following the definitions in [Lemma˜C.2](https://arxiv.org/html/2509.22623v1#A3.Thmlemma2) and [Theorem˜C.1](https://arxiv.org/html/2509.22623v1#A3.Thmtheorem1).
Let evolution operator $\mathcal{P}_{s,t,\theta}^{i_{0}}$ be the transformation operator for coordinate $i_{0}$.
Let $p_{t}^{i_{0}}\in\mathbb{R}^{M}$ and $U_{t}^{i_{0}}\in\mathbb{R}^{M\times M}$ be the true probability vector and the true rates matrix for coordinate $i_{0}$.
Let $\widehat{p}_{t,\theta}^{i_{0}}\in\mathbb{R}^{M}$ and $\widehat{U}_{t,\theta}^{i_{0}}\in\mathbb{R}^{M\times M}$ be the estimated probability vectors and rates matrix defined by estimated velocity $\widehat{u}_{t,\theta}$ for coordinate $i_{0}$.
Then by definition of total variation distance, we have:

$$ $\displaystyle\text{TV}(P,\widehat{P})=$ $\displaystyle\penalty 10000\ \frac{1}{2}\sum_{x\in S}|p_{1}(x)-p_{1,\theta}(x)|$ $\displaystyle\leq$ $\displaystyle\penalty 10000\ \frac{1}{2}\sum_{i_{0}\in[d]}\sum_{x\in S}|p_{1}^{i_{0}}(x)-p^{i_{0}}_{1,\theta}(x)|$ ( By $p_{1}^{i_{0}}=\prod_{i_{0}=1}^{d}p_{1}^{i_{0}}$ and $p_{1,\theta}^{i_{0}}=\prod_{i_{0}=1}^{d}p_{1,\theta}^{i_{0}}$ . ) $\displaystyle\leq$ $\displaystyle\penalty 10000\ \int_{0}^{1}\sum_{i_{0}\in[d]}\|\mathcal{P}_{s,1,\theta}^{i_{0}}\|_{1}\|(U_{s,\theta}^{i_{0}}-U_{s}^{i_{0}})p_{s}^{i_{0}}\|_{1}\differential s,$ (C.7) $$

where the last equation follows from the proof of [Theorem˜C.1](https://arxiv.org/html/2509.22623v1#A3.Thmtheorem1).
As in [Theorem˜C.1](https://arxiv.org/html/2509.22623v1#A3.Thmtheorem1),
we then bound the derivative of $\|\mathcal{P}_{s,t,\theta}^{i_{0}}\|_{F}$.
Let $M$ be the vocabulary size and set the transformer estimator $u_{\widehat{\theta}}^{i_{0}}$ bound by $M_{u}$ for any $i_{0}\in[d]$, then we have

$$ $\displaystyle\frac{\partial}{\partial t}\|\mathcal{P}_{s,t,\theta}^{i_{0}}\|_{1}\leq$ $\displaystyle\penalty 10000\ \|\frac{\partial}{\partial t}\mathcal{P}_{s,t,\theta}^{i_{0}}\|_{1}$ $\displaystyle=$ $\displaystyle\penalty 10000\ \|U_{t,\theta}^{i_{0}}\mathcal{P}_{s,t,\theta}^{i_{0}}\|_{1}$ ( By Kolmogorov Equation ) $\displaystyle\leq$ $\displaystyle\penalty 10000\ \|U_{t,\theta}^{i_{0}}\|_{1}\|\mathcal{P}_{s,t,\theta}^{i_{0}}\|_{1}$ ( By triangle inequality ) $\displaystyle\lesssim$ $\displaystyle\penalty 10000\ M_{u}\|\mathcal{P}^{i_{0}}_{s,t,\theta}\|_{1},$ (C.8) $$

where the last line follows by the maximum of the sum of absolute value of entry of $U_{t,\theta}^{i_{0}}$ in each column is lesssim than $M_{u}$.
Then by Grönwall’s Inequality [Lemma˜C.1](https://arxiv.org/html/2509.22623v1#A3.Thmlemma1), we have:

$$ $\displaystyle\|\mathcal{P}_{s,1,\theta}^{i_{0}}\|_{1}\lesssim\|\mathcal{P}_{s,s,\theta}^{i_{0}}\|_{1}\exp(\int_{0}^{t}M_{u}\differential s)\leq\exp(M_{u}).$ (C.9) $$

Substituting ([C.9](https://arxiv.org/html/2509.22623v1#A3.E9)) into
([C.7](https://arxiv.org/html/2509.22623v1#A3.E7)), we get:

$$ $\displaystyle\text{TV}(P,\widehat{P})\leq$ $\displaystyle\penalty 10000\ \int_{0}^{1}\sum_{i_{0}\in[d]}\|\mathcal{P}_{s,1,\theta}^{i_{0}}\|_{1}\|(U_{s,\theta}^{i_{0}}-U_{s}^{i_{0}})p_{s}^{i_{0}}\|_{1}\differential s$ ( By ( C.7 ) ) $\displaystyle\leq$ $\displaystyle\penalty 10000\ \sum_{i_{0}\in[d]}\int_{0}^{1}\exp(M_{u})\|(U_{s,\theta}^{i_{0}}-U_{s}^{i_{0}})p_{s}^{i_{0}}\|_{1}\differential s$ $\displaystyle\lesssim$ $\displaystyle\penalty 10000\ \sqrt{M}\exp(M_{u})\sum_{i_{0}\in[d]}\sqrt{\mathcal{R}^{i_{0}}(\widehat{\Theta}))}.$ ( By the definition of risk function $\mathcal{R}^{i_{0}}$ ) $$

This completes the proof.
∎

###### Theorem C.1 (Error Bounds for Discrete Flow Matching) .

###### Proof.

###### Theorem C.2 (Error Bounds for Discrete Flow Matching with Factorized Velocity, Theorem ˜ 3.1 Restate) .

###### Proof.

### Appendix D Proof of Lemma ˜ 4.1

This section provides the proof of [Lemma˜4.1](https://arxiv.org/html/2509.22623v1#S4.Thmlemma1).
Note that we view $\mathcal{T}=[M]$ as a subspace of $\mathbb{R}$ in this section.
In other words, we embed $\mathcal{S}=\mathcal{T}^{d}$ into $\mathbb{R}^{d}$ through the inclusion map $E:\mathcal{S}\hookrightarrow\mathbb{R}^{d}$.

Organization.
In [Section˜D.1](https://arxiv.org/html/2509.22623v1#A4.SS1), we define a $C^{\infty}$ function $\eta(x)$ and derive bounds for all its derivatives in [Lemma˜D.1](https://arxiv.org/html/2509.22623v1#A4.Thmlemma1).
Then we present the main proof of [Lemma˜4.1](https://arxiv.org/html/2509.22623v1#S4.Thmlemma1) in [Section˜D.2](https://arxiv.org/html/2509.22623v1#A4.SS2) on the basis of function constructed in [Lemma˜D.1](https://arxiv.org/html/2509.22623v1#A4.Thmlemma1).

#### D.1 Preliminaries

We start with defining a smooth function $\eta(x)$ and bounding its derivatives.

###### Lemma D.1 .

Define $\eta(x):[0,\infty)\to[0,1]$ by

$$ $\displaystyle\eta(x)=\begin{cases}e\cdot\exp(-\frac{1}{1-x}),\penalty 10000\ &x\in[0,1),\\ 0,\penalty 10000\ &x\in[1,\infty).\end{cases}$ $$

Then $\eta(t)\in C^{\infty}$ and $|\frac{\differential^{n}\eta}{\differential x^{n}}(x)|\leq e\cdot(\frac{2n}{e})^{2n}$ for all $x\in[0,1]$.

###### Proof.

Our proof consists of three steps.

Step 1: Smoothness.
First, we show that $\eta(x)\in C^{\infty}$.

For $x>1$, $\eta(x)=0$ so all derivatives vanish (i.e., $\frac{\differential^{n}\eta}{\differential x^{n}}=0$ for any $n\in\operatorname*{\mathbb{Z}}^{+}$).

For $x\in[0,1)$, we have $\frac{\differential\eta}{\differential x}(x)=e\cdot(-\frac{1}{(x-1)^{2}})\cdot\exp(\frac{1}{x-1})$.

We denote, for $x<1$,

$$ $\displaystyle\frac{\differential^{n}\eta}{\differential x^{n}}(x):=e\cdot p_{n}(\frac{1}{x-1})\cdot\exp(\frac{1}{x-1}),\quad\text{for}\quad n\in\mathbb{Z}^{+},$ (D.1) $$

where $p_{n}(x)$ is a function to be determined.
Then $p_{0}(x)=1$ and $p_{1}(x)=-x^{2}$.

For $n\in\operatorname*{\mathbb{Z}}^{+}$, it holds

$$ $\displaystyle\penalty 10000\ \frac{\differential^{n}\eta}{\differential x^{n}}(x)$ $\displaystyle=$ $\displaystyle\penalty 10000\ \frac{\differential}{\differential x}(\frac{\differential^{n-1}\eta}{\differential x^{n-1}})(x)$ $\displaystyle=$ $\displaystyle\penalty 10000\ \frac{\differential}{\differential x}(e\cdot p_{n-1}(\frac{1}{x-1})\cdot\exp(\frac{1}{x-1}))$ $\displaystyle=$ $\displaystyle\penalty 10000\ e\cdot(-\frac{1}{(x-1)^{2}}p^{\prime}_{n-1}(\frac{1}{x-1})+-\frac{1}{(x-1)^{2}}p_{n-1}(\frac{1}{x-1}))\cdot\exp(\frac{1}{x-1}).$ ( By chain rule ) $$

Then we have the recurrence relation $p_{n}(x)=-x^{2}(p_{n-1}(x)+p^{\prime}_{n-1}(x))$ for $n\in\operatorname*{\mathbb{Z}}^{+}$ and $p_{0}(x)=1$.

By induction, $p_{n}$ is a polynomial of degree $2n$.
Then for $n\in\operatorname*{\mathbb{Z}}^{+}$, we have

$$ $\displaystyle\lim_{x\to 1^{-}}\frac{\differential^{n}\eta}{\differential x^{n}}(x)=$ $\displaystyle\penalty 10000\ \lim_{x\to 1^{-}}e\cdot p_{n}(\frac{1}{x-1})\exp(\frac{1}{x-1})$ ( By ( D.1 ) ) $\displaystyle=$ $\displaystyle\penalty 10000\ \lim_{x\to-\infty}e\cdot p_{n}(x)\cdot e^{x}$ ( By setting $z=\frac{1}{x-1}$ ) $\displaystyle=$ $\displaystyle\penalty 10000\ 0$ ( $({\rm polynomial})\cdot e^{z}$ vanishes as $z\to-\infty$ ) $\displaystyle=$ $\displaystyle\penalty 10000\ \lim_{x\to 1^{+}}\frac{\differential^{n}\eta}{\differential x^{n}}(x),$ ( By $\eta(x)=0$ for $x>1$ ) $$

showing that all derivatives match at $x=1$.

Then, since $\eta(x)$ is smooth on $[0,1)$ and $(1,\infty]$, we have $\eta(x)\in C^{\infty}$.

Step 2: Growth Bound.
Next, we bound $|\frac{\differential^{n}\eta}{\differential x^{n}}(x)|$.

Define $q_{n}(x):=|e^{x}\cdot p_{n}(x)|$.
Then $q_{n+1}(x)=x^{2}\cdot q^{\prime}_{n}(x)$, $n\in\operatorname*{\mathbb{Z}}^{+}$.

Introduce the generating function

$$ $\displaystyle G(t,x):=\sum_{n\geq 0}\frac{q_{n}(x)}{n!}t^{n}.$ $$

Then $G(t,x)$ satisfies the partial differential equation

$$ $\displaystyle\partial_{t}G(t,x)=x^{2}\partial_{x}G(t,x),\quad G(0,x)=e^{x}.$ (D.2) $$

One solution to ([D.2](https://arxiv.org/html/2509.22623v1#A4.E2)) is $G(t,x)=\exp(\frac{x}{1-xt})$.
Hence, $\frac{q_{n}(x)}{n!}$ is the $t^{n}$-th coefficient in the Taylor expansion of $G(t,x)=\exp(\frac{x}{1-xt})$ at point $t=0$.

By Cauchy integral formula, for all
$x\leq-1$ and $0<r<1/|x|$, we have

$$ $\displaystyle\frac{q_{n}(x)}{n!}=$ $\displaystyle\penalty 10000\ \frac{1}{2\pi i}\int_{|t|=r,t\in\mathbb{C}}\frac{G(t,x)}{t^{n+1}}\differential t$ $\displaystyle\leq$ $\displaystyle\penalty 10000\ \frac{1}{2\pi}\int_{|t|=r,t\in\mathbb{C}}|\frac{G(t,x)}{t^{n+1}}|\differential t$ ( By $q_{n}(x)\in\mathbb{R}$ and $|\int f\differential x|\leq\int|f|\differential x$ ) $\displaystyle\leq$ $\displaystyle\penalty 10000\ \frac{1}{2\pi}\cdot\frac{\max_{|t|=r,t\in\mathbb{C}}|G(t,x)|}{r^{n+1}}\int_{|t|=r,t\in\mathbb{C}}1\differential x$ ( By $\int|fg|\differential x\leq(\sup|f|)\int|g|\differential x$ ) $\displaystyle=$ $\displaystyle\penalty 10000\ \frac{\max_{|t|=r,t\in\mathbb{C}}|G(t,x)|}{r^{n}}.$ (D.3) $$

Further, for $x\leq-1$ and $0<r<1/|x|$, we set $t=re^{i\theta}\in\mathbb{C}$ and get

$$ $\displaystyle\max_{|t|=r,t\in C}|G(t,x)|=$ $\displaystyle\penalty 10000\ \max_{\theta\in[0,2\pi]}|\exp(\frac{x}{1-xre^{i\theta}})|$ $\displaystyle=$ $\displaystyle\penalty 10000\ \max_{\theta\in[0,2\pi]}\exp(x\cdot{\rm Re}(\frac{1}{1-xre^{i\theta}}))$ $\displaystyle=$ $\displaystyle\penalty 10000\ \exp(\frac{x}{1-xr}),$ (D.4) $$

where the second line is by $|\exp(z)|=\exp({\rm Re}(z))$, and the last line is by $x\leq-1$ and $|xr|<1$.

Substituting ([D.4](https://arxiv.org/html/2509.22623v1#A4.E4)) into ([D.3](https://arxiv.org/html/2509.22623v1#A4.E3)), we get

$$ $\displaystyle\frac{q_{n}(x)}{n!}\leq$ $\displaystyle\penalty 10000\ \inf_{0<r<\frac{1}{|x|}}\frac{1}{r^{n}}\exp(\frac{x}{1-xr})$ $\displaystyle\leq$ $\displaystyle\penalty 10000\ (2|x|)^{n}\cdot\exp(\frac{2}{3}x)$ $\displaystyle\leq$ $\displaystyle\penalty 10000\ (\frac{3n}{e})^{n},$ (D.5) $$

where the second line is by setting $r=\frac{1}{2|x|}$, and the last line follow from $x\leq-1$ and optimizing over $x$.

Step 3: Final Bound.
Finally we bound $|\frac{\differential^{n}\eta}{\differential x^{n}}(x)|$ as

$$ $\displaystyle|\frac{\differential^{n}\eta}{\differential x^{n}}(x)|=$ $\displaystyle\penalty 10000\ e\cdot q_{n}(\frac{1}{x-1})$ $\displaystyle\leq$ $\displaystyle\penalty 10000\ e\cdot n!\cdot(\frac{3n}{e})^{n}$ ( By ( D.5 ) and $\frac{1}{x-1}\leq-1$ when $x\in[0,1)$ ) $\displaystyle\leq$ $\displaystyle\penalty 10000\ e\cdot(\frac{n}{e})^{n}\cdot(\frac{3n}{e})^{n}$ ( By Stirling’s formula ) $\displaystyle\leq$ $\displaystyle\penalty 10000\ e\cdot(\frac{2n}{e})^{2n}.$ $$

This completes the proof.
∎

###### Lemma D.1 .

###### Proof.

#### D.2 Main Proof of Lemma ˜ 4.1

We now establish [Lemma˜4.1](https://arxiv.org/html/2509.22623v1#S4.Thmlemma1) building on [Lemma˜D.1](https://arxiv.org/html/2509.22623v1#A4.Thmlemma1).
This lemma guarantees the existence of a smooth function that interpolates a given discrete function by matching its values at prescribed points.
In this way, it provides a bridge between discrete functions and their continuous counterparts.

###### Lemma D.2 ( Lemma ˜ 4.1 Restate) .

Let $\mathcal{S}\subset\mathbb{R}^{d}$ be the state space of discrete flow matching.
Recall that $\mathcal{S}\subset\mathbb{R}^{d}$ is a $1$-separated finite set with $|\mathcal{S}|=M^{d}$, i.e., $\|s-s^{\prime}\|\geq 1$ for all distinct $s,s^{\prime}\in\mathcal{S}$.
For each $x\in\mathcal{S}$,
let $u(x,\cdot)\in\mathcal{H}^{\beta}_{1,M^{d}}([0,1],K)$ with $\beta=k_{1}+\gamma\geq 1$ and $k_{1}=\lfloor\beta\rfloor$.
Then there exists an extension $\widetilde{u}:\mathbb{R}^{d}\times[0,1]\to\mathbb{R}$ such that

$$ $\displaystyle\widetilde{u}(x,t)\in\mathcal{H}^{\beta}_{d+1,M^{d}}(\mathbb{R}^{d}\times[0,1],e\cdot(k_{1}+2)(2k_{1})^{2k_{1}}KM^{d}),$ $$

and $\widetilde{u}(s,t)=u(s,t)$ for all $s\in\mathcal{S}$ and $t\in[0,1]$.

###### Proof.

Our proof consists of five steps.
We give the construction of $\widetilde{u}(x,t)$ first in Step 1 & 2, and then prove that it has desired properties in Step 3 - 5.

Step 1: Partition of Unity around $\mathcal{S}$.

Let $\eta(t)$ be the bump function from [Lemma˜D.1](https://arxiv.org/html/2509.22623v1#A4.Thmlemma1).

Let $r=1/e<1/2$.
For $s\in\mathcal{S}\subset\mathbb{R}^{d}$, we define $\phi^{r}_{s}(x):\mathbb{R}^{d}\to\mathbb{R}$ as

$$ $\displaystyle\phi^{r}_{s}(x):=\eta(\frac{\|x-s\|^{2}}{r^{2}}).$ $$

Then $\phi^{r}_{s}(x)\in C^{\infty}$, ${\rm supp}\penalty 10000\ \phi^{r}_{s}(x)\subset B(s,r)=\{x\in\mathbb{R}^{d}\mid\|x-s\|<r\}$, and $\phi^{r}_{s}(s)=1$.
Since $\mathcal{S}$ is $1$-separated and $r<1/2$, the supports $\{\operatorname{supp}(\phi_{s})\}_{s\in\mathcal{S}}$ are pairwise disjoint.

Step 2: Extension.
Next, we extend the discrete function $u$ to a continuous function $\widetilde{u}$.

We construct $\widetilde{u}(x,t)$ as:

$$ $\displaystyle\widetilde{u}(x,t)=\sum_{s\in\mathcal{S}}\phi_{s}(x)\cdot u(s,t).$ (D.6) $$

Disjointness implies that for each fixed $x$ at most one term in ([D.6](https://arxiv.org/html/2509.22623v1#A4.E6)) is nonzero.
Hence, $\widetilde{u}(s,t)=u(s,t)$ for all $s\in\mathcal{S}$.

Step 3: Derivative Bounds up to Order $k_{1}$.
We now prove $\widetilde{u}(x,t)\in\mathcal{H}^{\beta^{\prime}}_{d,M^{d}}(\mathbb{R}^{d}\times[0,1],K^{\prime})$.

Let $(\lambda,m)$ be multi‑indices with $\lambda\in\mathbb{N}_{0}^{d}$, $m\in\mathbb{N}_{0}$, and $|\lambda|+m\leq k_{1}$.

Since $\phi_{s}$ is independent of $t$ and $u(s,\cdot)$ is independent of $x$

$$ $\displaystyle\partial_{x}^{\lambda}\partial_{t}^{m}\widetilde{u}(x,t)=\sum_{s\in\mathcal{S}}\partial_{x}^{\lambda}\phi_{s}(x)\partial_{t}^{m}u(s,t),$ $$

or in component-wise form, for every $k\in\mathbb{R}^{d}$, it holds:

$$ $\displaystyle\partial_{x}^{\lambda}\partial_{t}^{m}\widetilde{u}_{k}(x,t)=\sum_{s\in\mathcal{S}}\partial^{\lambda}_{x}\phi_{s}(x)\partial^{m}_{t}u_{k}(s,t).$ $$

Further, for all $s\in\mathcal{S}$, $x\in\mathbb{R}^{d}$ and $j\in[d]$, it holds

$$ $\displaystyle|\frac{\partial}{\partial x[j]}\phi_{s}(x)|=|\frac{2(x[j]-s[j])}{r^{2}}\eta^{\prime}(\frac{\|x-s\|^{2}}{r^{2}})|.$ $$

Then with $|s[j]-x[j]|\leq\frac{1}{e}$ when $x\in{\rm supp}\{\phi_{s}(x)\}$, using mathematical induction we get that for all $s\in\mathcal{S}$, $x\in\mathbb{R}^{d}$ and $m\in\operatorname*{\mathbb{Z}}^{+}$, it holds

$$ $\displaystyle|\partial_{x}^{\lambda}\partial_{t}^{m}\phi_{s}(x)|\leq\frac{1}{r^{2m}}\cdot|\frac{\differential^{m}\eta}{\differential x^{m}}(\frac{\|x-s\|^{2}}{r^{2}})|.$ $$

By [Lemma˜D.1](https://arxiv.org/html/2509.22623v1#A4.Thmlemma1) and $r=1/e$, we have $|\frac{\differential^{m}\eta}{\differential x^{m}}(x)|\leq e\cdot(\frac{2m}{e})^{2m}$ and hence

$$ $\displaystyle\|\partial_{x}^{\alpha}\phi_{s}\|_{L^{\infty}(\mathbb{R}^{d})}\leq e(2|\alpha|)^{2|\alpha|}\quad\text{for all}\quad s\in\mathcal{S}.$ (D.7) $$

Step 4: $\gamma$-Hölder Seminorm for Order $k_{1}$.
Return to the discussion of $\widetilde{u}_{k}$.

Let $|\lambda|+m=k_{1}$.
For $(x,t_{1}),(y,t_{2})\in\mathbb{R}^{d}\times[0,1]$ and for every $k\in[M^{d}]$, we have

$$ $\displaystyle\sum_{\|\lambda\|_{1}+m\leq k_{1}}\|\partial_{x}^{\lambda}\widetilde{u}_{k}(x,t)\|_{L^{\infty}}\leq$ $\displaystyle\penalty 10000\ \sum_{\|\lambda\|_{1}+m\leq k_{1}}\sum_{s\in\mathcal{S}}\|\partial_{x}^{\lambda}\phi_{s}(x)\partial^{m}_{t}u_{k}(s,t)\|_{L^{\infty}}$ ( By ( D.6 ) ) $\displaystyle\leq$ $\displaystyle\penalty 10000\ e\cdot(2k_{1})^{2k_{1}}\sum_{m\leq k_{1}}\sum_{s\in\mathcal{S}}\|\partial^{m}_{t}u_{k}(s,t)\|_{L^{\infty}}$ ( By ( D.7 ) ) $\displaystyle=$ $\displaystyle\penalty 10000\ e\cdot(2k_{1})^{2k_{1}}\sum_{s\in\mathcal{S}}\sum_{m\leq k_{1}}\|\partial^{m}_{t}u_{k}(s,t)\|_{L^{\infty}}$ ( Interchange the order of summations ) $\displaystyle\leq$ $\displaystyle\penalty 10000\ e\cdot(2k_{1})^{2k_{1}}KM^{d},$ (D.8) $$

where the last line follows that $u(s,t)\in\mathcal{H}^{\beta}_{1,M^{d}}([0,1],K)$ with respect to $t$.
Also, we have

$$ $\displaystyle\penalty 10000\ \sum_{\|\lambda\|_{1}+m=k_{1}}\sup_{\begin{subarray}{c}{(x,t_{1}),(y,t_{2})\in\mathbb{R}^{d}\times[0,1]}\\ (x,t_{1})\neq(y,t_{2})\end{subarray}}\frac{|\partial_{x}^{\lambda}\partial_{t}^{m}\widetilde{u}_{k}(x,t_{1})-\partial_{x}^{\lambda}\partial_{t}^{m}\widetilde{u}_{k}(y,t_{2})|}{\|(x,t_{1})-(y,t_{2})\|^{\gamma}}$ $\displaystyle=$ $\displaystyle\penalty 10000\ \sum_{\|\lambda\|_{1}+m=k_{1}}\sup_{\begin{subarray}{c}{(x,t_{1}),(y,t_{2})\in\mathbb{R}^{d}\times[0,1]}\\ (x,t_{1})\neq(y,t_{2})\end{subarray}}\frac{|\sum_{s\in\mathcal{S}}\partial^{\lambda}_{x}\phi_{s}(x)\partial^{m}_{t}u_{k}(s,t_{1})-\partial^{\lambda}_{x}\phi_{s}(y)\partial^{m}_{t}u_{k}(s,t_{2})|}{\|(x,t_{1})-(y,t_{2})\|^{\gamma}}$ ( By ( D.6 ) ) $\displaystyle\leq$ $\displaystyle\penalty 10000\ e\cdot(2k_{1})^{2k_{1}}M^{d}\sum_{n^{\prime}\leq k_{1}}\sup_{t_{1},t_{2}\in[0,1],t_{1}\neq t_{2},s\in\mathcal{S}}\frac{|\partial^{m}_{t}u_{k}(s,t_{1})-\partial^{m}_{t}u_{k}(s,t_{2})|}{|t_{1}-t_{2}|^{\gamma}}$ ( By ( D.7 ) ) $\displaystyle=$ $\displaystyle\penalty 10000\ e\cdot(2k_{1})^{2k_{1}}M^{d}\cdot(\sum_{n^{\prime}=k_{1}}\sup_{t_{1},t_{2}\in[0,1],t_{1}\neq t_{2},s\in\mathcal{S}}\frac{|\partial^{m}_{t}u_{k}(s,t_{1})-\partial^{m}_{t}u_{k}(s,t_{2})|}{|t_{1}-t_{2}|^{\gamma}}$ $\displaystyle\penalty 10000\ \hskip 70.0001pt+\sum_{n^{\prime}<k_{1}}\sup_{t_{1},t_{2}\in[0,1],t_{1}\neq t_{2},s\in\mathcal{S}}\frac{|\partial^{m}_{t}u_{k}(s,t_{1})-\partial^{m}_{t}u_{k}(s,t_{2})|}{|t_{1}-t_{2}|^{\gamma}})$ $\displaystyle\leq$ $\displaystyle\penalty 10000\ e\cdot(2k_{1})^{2k_{1}}M^{d}\cdot(\sum_{n^{\prime}=k_{1}}\sup_{t,t_{1},t_{2}\in[0,1],t_{1}\neq t_{2},s\in\mathcal{S}}\frac{|\partial^{m}_{t}u_{k}(s,t_{1})-\partial^{m}_{t}u_{k}(s,t_{2})|}{|t_{1}-t_{2}|^{\gamma}}$ $\displaystyle\penalty 10000\ \hskip 70.0001pt+\sum_{n^{\prime}<k_{1}}\sup_{t_{1},t_{2}\in[0,1],t_{1}\neq t_{2},s\in\mathcal{S}}\frac{\|\partial^{n^{\prime}+1}u_{k}(s,t)\|_{L^{\infty}}\cdot|t_{1}-t_{2}|}{|t_{1}-t_{2}|^{\gamma}})$ ( By Newton-Leibniz formula ) $\displaystyle\leq$ $\displaystyle\penalty 10000\ e\cdot(2k_{1})^{2k_{1}}M^{d}\cdot(K+\sum_{n^{\prime}<k_{1}}K)$ ( $u(s,t)\in\mathcal{H}^{\beta}_{1,M^{d}}([0,1],K)$ and $|t_{1}-t_{2}|^{1-\gamma}\leq 1$ ) $\displaystyle=$ $\displaystyle\penalty 10000\ e\cdot(k_{1}+1)(2k_{1})^{2k_{1}}KM^{d}.$ (D.9) $$

Step 5: Altogether.
Combing ([D.8](https://arxiv.org/html/2509.22623v1#A4.E8)) and ([D.9](https://arxiv.org/html/2509.22623v1#A4.E9)), we get

$$ $\displaystyle\widetilde{u}(x,t)\in\mathcal{H}^{\beta}_{d+1,M^{d}}(\mathbb{R}^{d}\times[0,1],e\cdot(k_{1}+2)(2k_{1})^{2k_{1}}KM^{d}).$ $$

This completes the proof.
∎

###### Lemma D.2 ( Lemma ˜ 4.1 Restate) .

###### Proof.

### Appendix E Proof of Theorem ˜ 4.1

This section provides the proof of [Theorem˜4.1](https://arxiv.org/html/2509.22623v1#S4.Thmtheorem1).
We first develop auxiliary lemmas characterizing Lipschitz continuity properties and bound point-wise values of Lipschitz continuous functions using integral upper bounds.
Building on these technical tools, we then present the proof of approximation theorem [Theorem˜4.1](https://arxiv.org/html/2509.22623v1#S4.Thmtheorem1), which guarantees the existence of transformer networks that approximate the target function with controlled error and parameter bounds.

Organization.
We recall basic concepts of factorized discrete flow matching and mixture path setting in [Section˜E.1](https://arxiv.org/html/2509.22623v1#A5.SS1).
Then we introduce and prove auxiliary lemmas in [Section˜E.2](https://arxiv.org/html/2509.22623v1#A5.SS2).
Finally, we present the main proof of [Theorem˜4.1](https://arxiv.org/html/2509.22623v1#S4.Thmtheorem1) in [Section˜E.3](https://arxiv.org/html/2509.22623v1#A5.SS3).

#### E.1 Preliminaries

To start with, recall from [Section˜2](https://arxiv.org/html/2509.22623v1#S2) that when constructing a factorized path, the probability path has a factorized generating velocity of the form

$$ $\displaystyle u_{t}(y,x)=\sum_{i}\delta(y^{\macc@depth\@ne\macc@set@skewchar\macc@nested@a 111{i}},x^{\macc@depth\@ne\macc@set@skewchar\macc@nested@a 111{i}}),u_{t}^{i}(y^{i},x),$ (E.1) $$

where $\macc@depth\@ne\macc@set@skewchar\macc@nested@a 111{i}=(1,\dots,i-1,i+1,\dots,d)$ denotes all indices except $i$.
Following notations in [Section˜1](https://arxiv.org/html/2509.22623v1#S1), we write
$u_{t}(\cdot,x)$ and $u^{i}_{t}(\cdot,x)$ as $u(x,t)$ and $u^{i}(x,t)$ respectively.

Next, recall that in [Section˜2](https://arxiv.org/html/2509.22623v1#S2) we construct mixture path $p_{t|0,1}(x|x_{0},x_{1})=\prod_{i}p^{i}_{t|0,1}(x^{i}|x_{0},x_{1})$, where each per-coordinate path interpolates between the source and target tokens:

$$ $\displaystyle p^{i}_{t|0,1}(x^{i}|x_{0},x_{1})=\kappa_{t}\delta(x^{i},x_{1}^{i})+(1-\kappa_{t})\delta(x^{i},x_{0}^{i}).$ $$

Here, $\delta(\cdot,\cdot)$ is the Kronecker delta and $\kappa_{t}$ is a monotonically increasing smooth function that satisfies the boundary conditions:

$$ $\displaystyle\kappa_{0}=0,\quad\kappa_{1}=1,\quad\text{and}\quad\derivative{\kappa_{t}}{t}>0\quad\text{for}\quad t\in(0,1).$ $$

Then the corresponding conditional factorized velocity field that generates this per-coordinate path takes the form:

$$ $\displaystyle u_{t}^{i}(y^{i},x^{i}|x_{0}^{i},x_{1}^{i})=\frac{\dot{\kappa_{t}}}{1-\kappa_{t}}[\delta(y^{i},x_{1}^{i})-\delta(y^{i},x^{i})].$ $$

Taking expectation on $x_{1}$ and we obtain:

$$ $\displaystyle u^{i}_{t}(y,x)=\frac{\dot{\kappa_{t}}}{1-\kappa_{t}}\underset{x_{1}\sim P_{1}}{\mathbb{E}}[\delta(y^{i},x_{1}^{i})-\delta(y^{i},x^{i})].$ (E.2) $$

Further, we clip the time interval for training stability.
Specifically, we focus on the time period $[t_{0},T]$, where $0<t_{0}<T<1$.
This clipping is to prevent $\frac{\dot{\kappa}(t)}{1-\kappa(t)}$ from blowing up at $t=0,1$.
We assume $\frac{\dot{\kappa}(t)}{1-\kappa(t)}=O(1)$ and $(\frac{\dot{\kappa}(t)}{1-\kappa(t)})^{\prime}=O(1)$ in $t\in[t_{0},T]$.

###### Remark E.1 .

We demonstrate that clipping the interval of $t$ is necessary in discrete flow matching, for there doesn’t exist a construction of $\kappa(t)$ that keeps stability of $\frac{\dot{\kappa}(t)}{1-\kappa(t)}$ at both $t=0$ and $t=1$.
To show this, we set $r(t)=\frac{\dot{\kappa}(t)}{1-\kappa(t)}$ and $g(t)=1-\kappa(t)$.
Then we have:

$$ $\displaystyle(-\log(g(t))^{\prime}=\frac{-g^{\prime}(t)}{g(t)}=r(t).$ $$

Since $\kappa(0)=0$ and $\kappa(1)=1$, we have $-\log g(0)=0$ and $-\log g(1)=\infty$.
This means $r(t)=(-\log(g(t))^{\prime}$ is not bounded on [0,1].
Then for $\kappa(t)$ finite on (0,1), it must be instable at
$t=0$ or $t=1$.
Therefore, clipping the interval of $t$ is necessary.

###### Remark E.1 .

#### E.2 Auxiliary Lemmas

In this section, we introduce auxiliary lemmas for the proof of [Theorem˜4.1](https://arxiv.org/html/2509.22623v1#S4.Thmtheorem1).
We adapt [Lemma˜4.1](https://arxiv.org/html/2509.22623v1#S4.Thmlemma1) to the mixture path setting, stated as [Lemma˜E.1](https://arxiv.org/html/2509.22623v1#A5.Thmlemma1).
In [Lemma˜E.2](https://arxiv.org/html/2509.22623v1#A5.Thmlemma2) and [Lemma˜E.3](https://arxiv.org/html/2509.22623v1#A5.Thmlemma3), we compute the Lipschitz constants of the functions constructed in these bridging lemmas.
Finally, we establish connections between local Lipschitz behavior and integral bounds in [Lemma˜E.4](https://arxiv.org/html/2509.22623v1#A5.Thmlemma4) and [Lemma˜E.5](https://arxiv.org/html/2509.22623v1#A5.Thmlemma5).

To begin with, we introduce a lemma parallel to [Lemma˜4.1](https://arxiv.org/html/2509.22623v1#S4.Thmlemma1), guaranteeing the existence of a smooth function taking same value as a given discrete function at certain points.

###### Lemma E.1 (Discrete-to-Continuous Functional Extension of Velocity under Mixture Path Setting, Modified from Lemma ˜ 4.1 ) .

Consider velocity function $u(x,t)$ with the form ([E.2](https://arxiv.org/html/2509.22623v1#A5.E2)) generating mixture path.
For each $x\in\mathcal{S}$ and coordinate $i\in[d]$,
let $t\mapsto u^{i}(x,t)\in\mathcal{H}^{\beta}_{1,M}([t_{0},T],K)$ with $\beta=k_{1}+\gamma\geq 1$, where $k=\lfloor\beta\rfloor$ and $\gamma\in[0,1)$.
Then there exists an continuous extension $\widetilde{u}^{i}\in\mathcal{H}^{\beta}_{d+1,M}(\mathbb{R}^{d}\times[0,1],C)$ such that

$$ $\displaystyle\widetilde{u}(s,t)=u(s,t)\penalty 10000\ \penalty 10000\ \penalty 10000\ \penalty 10000\ \text{for all}\penalty 10000\ s\in\mathcal{S},t\in[t_{0},T],$ $$

where the Hölder norm $C=e\cdot(k_{1}+2)(2k_{1})^{2k_{1}}KM$.

###### Proof.

The construction of $\widetilde{u}(x,t)$ is same as the construction in the proof of [Lemma˜4.1](https://arxiv.org/html/2509.22623v1#S4.Thmlemma1).
We restate it for completeness.
Let $\eta(t)$ be as defined in [Lemma˜D.1](https://arxiv.org/html/2509.22623v1#A4.Thmlemma1).
For $s\in\mathcal{S}$, we define $\phi_{s}(x)$ as:

$$ $\displaystyle\phi_{s}(x)=\eta(e^{2}\|x-E(s)\|^{2}).$ $$

Then we construct $\widetilde{u}(x,t)$ as:

$$ $\displaystyle\widetilde{u}^{i}(x,t)=\sum_{s\in\mathcal{S}}\phi_{s}(x)\cdot u^{i}(s,t).$ (E.3) $$

This construction takes the same form as in ([D.6](https://arxiv.org/html/2509.22623v1#A4.E6)), while $u$ and $\widetilde{u}$ has output dimension of $M$ in mixture path case instead of $M^{d}$.
Then $\widetilde{u}^{i}(s,t)=u^{i}(s,t)$ for every $s\in\mathcal{S}$ given that $\phi_{s}(s)=1$.

The computation of Hölder constant of $\widetilde{u}^{i}(x,t)$ is exactly in the same form to the computation in proof of [Lemma˜4.1](https://arxiv.org/html/2509.22623v1#S4.Thmlemma1), while the only difference is to replace $M^{d}$ with $M$.
∎

Next, we prove that when $u(x,t)$ is Lipschitz continuous with respect to $t$ for fixed $x$, $\widetilde{u}(x,t)$ we construct is Lipschitz continuous.
Further, we give the Lipschitz constant of $\widetilde{u}(x,t)$ under $\ell_{2}$-norm.
We first present the result under general case to increase readability.

###### Lemma E.2 (Lipschitzness of Extension) .

Suppose that for every given $s\in\mathcal{S}$, it holds $\|u(s,t)\|_{2}\leq M_{u}$ and $u(s,t)$ is Lipschitz continuous under $\ell_{2}$-norm with respect to $t$, with Lipschitz constant $L_{u}$.
Then $\widetilde{u}(x,t)$ defined in the proof of [Lemma˜4.1](https://arxiv.org/html/2509.22623v1#S4.Thmlemma1) is Lipschitz continuous under $\ell_{2}$-norm with respect to $(x,t)$, with Lipschitz constant $\max\{L_{u},4e\sqrt{d}M_{u}\}$.

###### Proof.

By letting $n=1$ in ([D.7](https://arxiv.org/html/2509.22623v1#A4.E7)), we get $|\partial\phi_{s}|\leq 4e$.
This indicates $\|\nabla\phi_{s}\|_{2}\leq 4e\sqrt{d}$, meaning that $\phi_{s}$ is is Lipschitz continuous under $\ell_{2}$-norm, with Lipschitz constant $4e\sqrt{d}$.

By definition, for $s_{1}\neq s_{2}\in\mathcal{S}$,
it holds $\|s_{1}-s_{2}\|\geq 1$.
Then $B(s_{1},\frac{1}{e})$ and $B(s_{2},\frac{1}{e})$ does not intersect for distinct $s_{1}.s_{2}$.
Therefore for $x\in[0,M]^{d}$, there is at most one $s\in\mathcal{S}$ such that $x\in B(s,\frac{1}{e})$.
For $(x_{1},t_{1}),(x_{2},t_{2})\in\mathbb{R}^{d}\times\mathbb{R}$, we discuss two possible cases as below.

(1). There exists $s_{0}\in\mathcal{S}$, such that $x_{1},x_{2}\in B(s_{0},\frac{1}{e})$.

Then it holds:

$$ $\displaystyle\|\widetilde{u}(x_{1},t_{1})-\widetilde{u}(x_{2},t_{2})\|_{2}=$ $\displaystyle\penalty 10000\ \|\sum_{s\in\mathcal{S}}\phi_{s}(x_{1})\cdot u(s,t_{1})-\sum_{s\in\mathcal{S}}\phi_{s}(x_{2})\cdot u(s,t_{2})\|_{2}$ $\displaystyle=$ $\displaystyle\penalty 10000\ \|\phi_{s_{0}}(x_{1})\cdot u(s_{0},t_{1})-\phi_{s_{0}}(x_{2})\cdot u(s_{0},t_{2})\|_{2}$ ( $\phi_{s}(x)=0$ for $x\notin B(s,\frac{1}{e})$ ) $\displaystyle\leq$ $\displaystyle\penalty 10000\ \|\phi_{s_{0}}(x_{1})\cdot u(s_{0},t_{1})-\phi_{s_{0}}(x_{1})\cdot u(s_{0},t_{2})\|_{2}$ $\displaystyle\penalty 10000\ +\|\phi_{s_{0}}(x_{1})\cdot u(s_{0},t_{2})-\phi_{s_{0}}(x_{2})\cdot u(s_{0},t_{2})\|_{2}$ $\displaystyle\leq$ $\displaystyle\penalty 10000\ \|u(s_{0},t_{1})-u(s_{0},t_{2})\|_{2}+M_{u}\|\phi_{s_{0}}(x_{1})-\phi_{s_{0}}(x_{2})\|_{2}$ ( $\phi_{s}(x)\leq 1$ , $\|u(s,t)\|_{2}\leq M_{u}$ ) $\displaystyle\leq$ $\displaystyle\penalty 10000\ L_{u}\|t_{1}-t_{2}\|_{2}+4e\sqrt{d}M_{u}\|x_{1}-x_{2}\|_{2}$ $\displaystyle\leq$ $\displaystyle\penalty 10000\ \max\{L_{u},4e\sqrt{d}M_{u}\}\|(x_{1},t_{1})-(x_{2},t_{2})\|_{2}.$ $$

(2). For all $s\in\mathcal{S}$, $x_{1}$ and $x_{2}$ do not both belong to $B(s,\frac{1}{e})$.

Then $\|x_{1}-x_{2}\|\geq 1-\frac{2}{e}$.
Therefore we have:

$$ $\displaystyle\|u(x_{1},t_{1})-u(x_{2},t_{2})\|_{2}\leq 2M_{u}\leq\frac{2e}{e-2}M_{u}\|x_{1}-x_{2}\|_{2}\leq\frac{2e}{e-2}M_{u}\|(x_{1},t_{1})-(x_{2},t_{2})\|_{2}.$ $$

Since $4e\sqrt{d}M_{u}\geq\frac{2e}{e-2}M_{u}$ this completes the proof.
∎

Next, we introduce a lemma modified from [Lemma˜E.2](https://arxiv.org/html/2509.22623v1#A5.Thmlemma2).
This lemma computes the upper bound of $\widetilde{u}^{i}(x,t)$ for $u^{i}(x,t)$ with the form ([E.2](https://arxiv.org/html/2509.22623v1#A5.E2)) generating mixture path.

###### Lemma E.3 (Lipschitzness of Extension under Mixture Path Setting, Modified from Lemma ˜ E.2 ) .

Consider $u^{i}(x,t)$ under mixture path setting with the form ([E.2](https://arxiv.org/html/2509.22623v1#A5.E2)) .
Then $\widetilde{u}^{i}(x,t)$ comstructed in the proof of [Lemma˜E.1](https://arxiv.org/html/2509.22623v1#A5.Thmlemma1) is Lipschitz continuous under $\ell_{2}$-norm with respect to $(x,t)$ when $t\in[t_{0},T]$, with Lipschitz constant $L_{\widetilde{u}}\lesssim 1$.

###### Proof.

Recall that under mixture path setting $M_{u},L_{u}=O(1)$.
Substituting $M_{u}$ and $L_{u}$ with $O(1)$ in conclusion of [Lemma˜E.2](https://arxiv.org/html/2509.22623v1#A5.Thmlemma2) and we get the result for mixture path case.
∎

Observing that for Lipschitz continuous function, its Lipschitz constant gives an upper bound on how fast a function increases or decreases.
This leads to the following lemma, connecting a function’s local value to its integral’s value lower bound.

###### Lemma E.4 (Integral Lower Bound via Point-wise Magnitude) .

Suppose that $f:\mathbb{R}^{d\times L}\to\mathbb{R}^{d\times L}$ is Lipschitz continuous under Frobenius norm, with Lipschitz constant $L_{f}$.
Let $n=dL$.
If there exists $X\in\mathbb{R}^{d\times L}$ such that $\|f(X)\|_{F}\geq a>0$, then it holds:

$$ $\displaystyle(\int\|f(Z)\|_{F}^{2}\differential Z)^{1/2}\geq(\frac{2S_{n}}{n(n+1)(n+2)})^{1/2}\frac{a^{\frac{n+2}{2}}}{L_{f}^{\frac{n}{2}}},$ $$

where $S_{n}$ denote the surface area of the unit sphere in $n$-dimensional Euclidean space.

###### Proof.

For $Z$ such that $\|Z-X\|_{F}\leq\frac{a}{L_{f}}$, it holds:

$$ $\displaystyle\|f(Z)\|_{F}\geq a-L_{f}\|X-Z\|_{F}.$ $$

Let $S_{n}$ denote the surface area of the unit sphere in $n$-dimensional Euclidean space.
We have:

$$ $\displaystyle(\int\|f(Z)\|_{F}^{2}\differential Z)^{1/2}\geq$ $\displaystyle\penalty 10000\ (\int_{\|Z-X\|_{F}\leq\frac{a}{L}}(a-L_{f}\|X-Z\|_{F})^{2}\differential Z)^{1/2}$ $\displaystyle=$ $\displaystyle\penalty 10000\ (\int_{\|Z\|_{F}\leq\frac{a}{L}}(a-L_{f}\|Z\|_{F})^{2}\differential Z)^{1/2}$ ( By change of variable ) $\displaystyle=$ $\displaystyle\penalty 10000\ (\int_{0}^{a/L}(a-L_{f}r)^{2}S_{n}r^{n-1}\differential r)^{1/2}$ $\displaystyle=$ $\displaystyle\penalty 10000\ (\frac{2S_{n}a^{n+2}}{n(n+1)(n+2)L_{f}^{n}})^{1/2}$ ( By integration ) $\displaystyle=$ $\displaystyle\penalty 10000\ (\frac{2S_{n}}{n(n+1)(n+2)})^{1/2}\frac{a^{\frac{n+2}{2}}}{L_{f}^{\frac{n}{2}}}.$ $$

This completes the proof.
∎

With [Lemma˜E.4](https://arxiv.org/html/2509.22623v1#A5.Thmlemma4) we have the following lemma bounding local value with integral value.

###### Lemma E.5 (Point-wise Upper Bound via Integral Constraint) .

Suppose that $f:[-I,I]^{d\times L}\to\mathbb{R}^{d\times L}$ is Lipschitz continuous on a bounded domain under Frobenius norm, with Lipschitz constant $L_{f}$.
Let $n=dL$.
Let $(\int\|f(Z)\|_{F}^{2}\differential Z)^{1/2}\leq b$, then for all $Z\in[-I,I]^{d\times L}$ it holds:

$$ $\displaystyle\|f(Z)\|_{F}\lesssim b^{\frac{2}{n+2}}L_{f}^{\frac{n}{n+2}}.$ $$

###### Proof.

We obtain the conclusion by rearranging the inequality in conclusion of [Lemma˜E.4](https://arxiv.org/html/2509.22623v1#A5.Thmlemma4) and ignoring constants.
∎

###### Lemma E.1 (Discrete-to-Continuous Functional Extension of Velocity under Mixture Path Setting, Modified from Lemma ˜ 4.1 ) .

###### Proof.

###### Lemma E.2 (Lipschitzness of Extension) .

###### Proof.

###### Lemma E.3 (Lipschitzness of Extension under Mixture Path Setting, Modified from Lemma ˜ E.2 ) .

###### Proof.

###### Lemma E.4 (Integral Lower Bound via Point-wise Magnitude) .

###### Proof.

###### Lemma E.5 (Point-wise Upper Bound via Integral Constraint) .

###### Proof.

#### E.3 Main Proof of Theorem ˜ 4.1

In this section, we prove the approximation theorem for discrete flow matching under the mixture path and factorized velocity settings.
Notice that in the proof of this theorem, we treat the upper bound of the Lipschitz constant of the approximator Transformer class as a constant independent of $\epsilon$.
Also, in the main text we present a simplified version [Theorem˜4.1](https://arxiv.org/html/2509.22623v1#S4.Thmtheorem1) in order to keep the exposition concise, while [Theorem˜E.1](https://arxiv.org/html/2509.22623v1#A5.Thmtheorem1) stated below is the explicit form.

###### Theorem E.1 ( Approximation Theorem for Mixture Path Discrete Flow Matching, Theorem ˜ 4.1 Restate) .

Let $u^{i}(x,t)$ be the factorized velocity field for coordinate $i\in[d]$ under mixture path setting.
Assume [Assumption˜4.1](https://arxiv.org/html/2509.22623v1#S4.Thmassumption1) holds,
then for any $\epsilon\in(0,1)$, there exists a transformer network $u^{i}_{\theta}(x,t)\in\mathcal{T}^{h,s,r}_{R}(C_{\mathcal{T}},C^{2,\infty}_{KQ},C_{KQ},C^{2,\infty}_{OV},C_{OV},C_{E},C^{2,\infty}_{F},C_{F})$ satisfying that for any $t\in[t_{0},T]$:

$$ $\displaystyle\sum_{x\in\mathcal{S}}\|u^{i}_{\theta}(x,t)-u^{i}(x,t)\|^{2}_{2}\cdot p_{t}(x)\lesssim\epsilon^{\frac{4}{M+2}}M^{\frac{12Md_{0}+25M}{M+2}},$ $$

where $d_{0}$ is the transformer feature dimension.
The parameter bound of the transformer network class follows:

$$ $\displaystyle\penalty 10000\ C_{KQ},C^{2,\infty}_{KQ}=\widetilde{O}(M^{6d_{0}+3}\epsilon^{-4d_{0}-2});C_{OV},C^{2,\infty}_{OV}=O(M^{-\frac{1}{2}}\epsilon)$ $\displaystyle\penalty 10000\ C_{F},C^{2,\infty}_{F}=O(M^{2}\epsilon^{-1});C_{E}=O(M),$ $$

where $O(\cdot)$ hides polynomial factors depending on $d,d_{0}$, $\widetilde{O}(\cdot)$ hides polynomial factors depending on $d,d_{0}$ and logarithmic factors depending on $M$ .

###### Proof.

To begin with, we introduce reshape layer we use in the proof.

While ordinary transformer network approximates function with same input and output dimension, under factorized path setting we need to approximate function $\widetilde{u}(x,t)$, with input dimension $d+1$ and output dimension $M$.
To accommodate this difference, we introduce two reshape layers: $R_{1}$ and $R_{2}$ to facilitate the transformation of dimensions.
We assume $d+1|M$ for simplicity in discussions below.

- •
$R_{1}:[0,M]^{d}\times[0,1]\to\mathbb{R}^{d_{0}\times\frac{M}{d_{0}}}$ is a reshape function rearranging a vector of dimension $d+1$ into a matrix of size $\mathbb{R}^{d_{0}\times\frac{M}{d_{0}}}$, where transformer feature dimension $d_{0}$ satisfies $d_{0}|d+1$.
We realize $R_{1}$ by first reshaping input vector $(x,t)$ with dimension $d+1$ into a matrix $A\in\mathbb{R}^{d_{0}\times\frac{d+1}{d_{0}}}$, following the standard procedure of rearranging entries.
Then we replicate the matrix $\frac{M}{d+1}$ times along its columns, yielding a matrix of size $d_{0}\times\frac{M}{d_{0}}$.
Altogether, the output of $R_{1}$ is a matrix of size $d_{0}\times\frac{M}{d_{0}}$.
As the reverse of $R_{1}$, $R^{-1}_{1}:\mathbb{R}^{d_{0}\times\frac{M}{d_{0}}}\to[0,M]^{d}\times[0,1]$ is defined by taking first $\frac{d+1}{d_{0}}$ columns of the matrix, and then rearranging it into a vector of dimension $d+1$.
- •
$R_{2}:\mathbb{R}^{d_{0}\times\frac{M}{d_{0}}}\to\mathbb{R}^{M}$ is a reshape function rearranging a matrix of size $\mathbb{R}^{d_{0}\times\frac{M}{d_{0}}}$ into a vector of dimension $M$, where $d_{0}|d+1$.
We realize $R_{2}$ by rearranging the entries of the matrix into a vector preserving the total number of elements, following standard reshape layer construction.
We define $R_{2}^{-1}$ as the reverse map of $R_{2}$.
This is well-defined since $R_{2}$ is bijection between $\mathbb{R}^{d_{0}\times\frac{M}{d_{0}}}$ and $\mathbb{R}^{M}$.

It is important to note that these reshape layers do not participate in the learning process of the Discrete Flow Matching, and therefore, are not the main focus of our discussion.
$R_{1}$ and $R_{2}$ represent a feasible design for the reshape layers, but they are not unique construction to make up for the dimension difference.
We present these particular forms of $R_{1}$ and $R_{2}$ for clarity and completeness, but the core of our discussion does not depend on them, and readers should avoid overemphasizing these details.

We now return to the main proof.
Let $\widetilde{u}(x,t)$ be as defined in [Lemma˜E.1](https://arxiv.org/html/2509.22623v1#A5.Thmlemma1).
For any coordinate $i\in[d]$, let reshaped factorized velocity field $u^{i,\rm reshape}:\mathbb{R}^{d_{0}\times\frac{M}{d_{0}}}\to\mathbb{R}^{d_{0}\times\frac{M}{d_{0}}}$ be:

$$ $\displaystyle u^{i,\rm reshape}=R_{2}^{-1}\circ\widetilde{u}(x,t)\circ R_{1}^{-1}.$ $$

Then $u^{i,\rm reshape}$ is Lipschitz continuous under Frobenius norm, with Lipschitz constant no larger than Lipschitz constant of $\widetilde{u}$.
By [Theorem˜B.1](https://arxiv.org/html/2509.22623v1#A2.Thmtheorem1), for any $\epsilon$ there exists a

$$ $\displaystyle u_{\theta}^{i,\rm reshape}(Z)=F^{\rm FF}_{1}\circ F^{\rm SA}\circ F^{\rm FF}_{2}\circ F^{\rm E}\in\mathcal{T}^{h,s,r}(C_{\mathcal{T}},C^{2,\infty}_{KQ},C_{KQ},C^{2,\infty}_{OV},C_{OV},C_{E},C^{2,\infty}_{F},C_{F}),$ $$

such that $d_{F}(u^{i,\rm reshape}(Z),u_{\theta}^{i,\rm reshape}(Z))<\epsilon$, where $d_{F}(f(Z),g(Z)):=(\int\|f(Z)-g(Z)\|^{2}_{F}\differential Z)^{1/2}$.
By [Theorem˜B.2](https://arxiv.org/html/2509.22623v1#A2.Thmtheorem2), the parameter bound of the transformer network satisfies:

$$ $\displaystyle\penalty 10000\ C_{KQ},C^{2,\infty}_{KQ}=\widetilde{O}(M^{6d_{0}+3}\epsilon^{-4d_{0}-2});C_{OV},C^{2,\infty}_{OV}=O(M^{-\frac{1}{2}}\epsilon)$ $\displaystyle\penalty 10000\ C_{F},C^{2,\infty}_{F}=O(M^{2}\epsilon^{-1});C_{E}=O(M),$ (E.4) $$

where $O(\cdot)$ hides polynomial factors depending on $d,d_{0}$, $\widetilde{O}(\cdot)$ hides polynomial factors depending on $d,d_{0}$ and logarithmic factors depending on $M$.

Let $h=u_{\theta}^{i,\rm reshape}-u^{i,\rm reshape}$.
Then $(\int\|h\|_{F}^{2}\differential Z)^{1/2}<\epsilon$.
By [Lemma˜B.7](https://arxiv.org/html/2509.22623v1#A2.Thmlemma7) and [Lemma˜E.3](https://arxiv.org/html/2509.22623v1#A5.Thmlemma3), $u_{\theta}^{i,\rm reshape},u^{i,\rm reshape}$ are Lipschitz continuous under Frobenius norm, indicating that $h$ is Lipschitz continuous under Frobenius norm.
We denote their Lipschitz constant as $L_{\theta}^{i,\rm reshape},L^{i,\rm reshape}$ and $L_{h}$ respectively.

We first compute $L_{\theta}^{i,\rm reshape}$ according to [Lemma˜B.7](https://arxiv.org/html/2509.22623v1#A2.Thmlemma7):

$$ $\displaystyle L_{\theta}^{i,\rm reshape}\leq$ $\displaystyle\penalty 10000\ (1+2M^{2}C_{OV}C_{KQ}+h\frac{M}{d_{0}}C_{OV})\cdot(C_{F}^{2}+1)^{2}$ $\displaystyle\lesssim$ $\displaystyle\penalty 10000\ (C_{F})^{2}\cdot M^{2}\cdot hC_{KQ}C_{OV}\cdot(C_{F})^{2}$ $\displaystyle\lesssim$ $\displaystyle\penalty 10000\ M^{6d_{0}+\frac{25}{2}}.$ ( By ( E.3 ). Note that we drop terms od $\epsilon$ . ) $$

Then we compute the expression of $L_{h}$:

$$ $\displaystyle L_{h}\leq$ $\displaystyle\penalty 10000\ L_{\theta}^{i,\rm reshape}+L^{i,\rm reshape}$ $\displaystyle\lesssim$ $\displaystyle\penalty 10000\ M^{6d_{0}+\frac{25}{2}}.$ ( By Lemma E.3 ) $$

Let $u_{\theta}:=R_{2}\circ u_{\theta}^{i,\rm reshape}\circ R_{1}$.
For all $(x,t)\in[0,M]^{d}\times[t_{0},T]$, it holds:

$$ $\displaystyle\|u^{i}_{\theta}(x,t)-\widetilde{u}^{i}(x,t)\|^{2}_{2}\leq$ $\displaystyle\penalty 10000\ \|u_{\theta}^{i,\rm reshape}\circ R_{1}(x,t)-u^{i,\rm reshape}\circ R_{1}(x,t)\|^{2}_{F}$ $\displaystyle=$ $\displaystyle\penalty 10000\ \|h(R_{1}(x,t))\|^{2}_{F}$ ( By definition of $h$ ) $\displaystyle\lesssim$ $\displaystyle\penalty 10000\ \epsilon^{\frac{4}{M+2}}M^{\frac{12Md_{0}+25M}{M+2}}.$ ( By Lemma E.5 ) $$

Then for every $t\in[t_{0},T]$, we have:

$$ $\displaystyle\sum_{x\in\mathcal{S}}\|u^{i}_{\theta}(x,t)-u^{i}(x,t)\|^{2}_{2}\cdot p_{t}(x)\lesssim\epsilon^{\frac{4}{M+2}}M^{\frac{12Md_{0}+25M}{M+2}}\sum_{x\in\mathcal{S}}p_{t}(x)=\epsilon^{\frac{4}{M+2}}M^{\frac{12Md_{0}+25M}{M+2}}.$ $$

This completes the proof.
∎

###### Theorem E.1 (
Approximation Theorem for Mixture Path Discrete Flow Matching, Theorem ˜ 4.1 Restate) .

###### Proof.

### Appendix F Proof of Theorem ˜ 5.1

This section provides the proof of [Theorem˜5.1](https://arxiv.org/html/2509.22623v1#S5.Thmtheorem1), deriving velocity estimation rate for factorized discrete flow matching implemented with transformers under mixture path setting.
The analysis adapts and modifies the risk-decomposition plus covering-number technique of (Fu et al., 2024) to our setting and parameter bounds from [Theorem˜4.1](https://arxiv.org/html/2509.22623v1#S4.Thmtheorem1).

Organization.
We derive the estimation rates of discrete flow matching transformers in four steps.

- •
Preliminaries.
In [Section˜F.1](https://arxiv.org/html/2509.22623v1#A6.SS1), we introduce several essential concepts, including factorized empirical loss $\widehat{\mathcal{L}}^{i_{0}}_{\rm CDFM}$, factorized discrete flow matching risk $\mathcal{R}^{i_{0}}(\Theta^{i_{0}})$ and factorized empirical risk $\widehat{\mathcal{R}}^{i_{0}}(\Theta^{i_{0}})$.
- •
Covering Number Upper bound.
We obtain covering-number bounds for the transformer class using the parameter constraints from [Theorem˜4.1](https://arxiv.org/html/2509.22623v1#S4.Thmtheorem1) and for the induced loss class in [Section˜F.2](https://arxiv.org/html/2509.22623v1#A6.SS2), [Lemma˜F.2](https://arxiv.org/html/2509.22623v1#A6.Thmlemma2)-[Lemma˜F.4](https://arxiv.org/html/2509.22623v1#A6.Thmlemma4).
- •
Generalization and Approximation Error Bound.
We apply the covering-number machinery and conclusions from [Theorem˜4.1](https://arxiv.org/html/2509.22623v1#S4.Thmtheorem1) to bound generalization and approximation error in [Section˜F.2](https://arxiv.org/html/2509.22623v1#A6.SS2), [Lemmas˜F.5](https://arxiv.org/html/2509.22623v1#A6.Thmlemma5) and [F.6](https://arxiv.org/html/2509.22623v1#A6.Thmlemma6).
- •
Velocity Estimation rates.
We utilize conclusions from prior three steps to prove [Theorem˜5.1](https://arxiv.org/html/2509.22623v1#S5.Thmtheorem1), the velocity estimation rate.

#### F.1 Preliminaries

In this section, we introduce and discuss basic concepts risk function of factorized flow matching.

In factorized velocity discrete flow matching case, for $i_{0}\in[M]$, $u_{\theta}^{i_{0}}$ is trained to approximate $u^{i_{0}}(x,t)$ solely, independent of the behaviour of velocity field $u(x,t)$ on other $d-1$ dimensions.
In other words, given $i_{0}\in[d]$ and $n$ i.i.d training samples $\{x_{i}\}_{i=1}^{n}$, the transformer network $u^{i_{0}}_{\theta}$ is trained through minimizing the factorized empirical loss:

$$ $\displaystyle\widehat{\mathcal{L}}^{i_{0}}_{\rm CDFM}:=\frac{1}{n}\sum_{i=1}^{n}\int_{t_{0}}^{T}\underset{X_{0}\sim p_{0},X_{t}\sim p_{t|x_{0}=X_{0},x_{1}=x_{i}}}{\mathbb{E}}\|u^{i_{0}}(X_{t},t)-u^{i_{0}}_{\theta}(X_{t},t)\|_{2}^{2}\differential t.$ $$

For simplicity of expression, we define the loss of certain function $f$ with respect to some certain end point $x$ as:

$$ $\displaystyle\ell^{i_{0}}(x;f):=\int_{t_{0}}^{T}\underset{X_{0}\sim p_{0},X_{t}\sim p_{t|x_{0}=X_{0},x_{1}=x}}{\mathbb{E}}\|u^{i_{0}}(X_{t},t)-f(X_{t},t)\|_{2}^{2}\differential t.$ $$

Then we have:

$$ $\displaystyle\widehat{\mathcal{L}}^{i_{0}}_{\rm CDFM}=\frac{1}{n}\sum_{i=1}^{n}\ell^{i_{0}}(x_{i};u^{i_{0}}_{\theta}).$ $$

We use $\widehat{\Theta}^{i_{0}}$ to denote the parameter of network trained by minimizing the factorized empirical loss $\widehat{\mathcal{L}}^{i_{0}}_{\rm CDFM}$ with $n$ i.i.d training samples $\{x_{i}\}_{i=1}^{n}$.
That’s to say, discrete flow matching network $\widehat{u}^{i_{0}}_{\theta}$ with parameter $\widehat{\Theta}^{i_{0}}$ is the factorized empirical risk minimizer, satisfying $\widehat{\Theta}^{i_{0}}\in\underset{\Theta^{i_{0}}}{\rm argmin\penalty 10000\ }\widehat{\mathcal{L}}_{\rm CDFM}(u^{i_{0}}_{\theta})$.

For a factorized discrete flow matching network $u^{i_{0}}_{\theta}$ with parameter $\Theta^{i_{0}}$, its performance in velocity estimation is measured by the factorized discrete flow matching risk, which is defined as:

$$ $\displaystyle\mathcal{R}^{i_{0}}(\Theta):=\int_{t_{0}}^{T}\underset{X_{t}\sim p_{t}}{\mathbb{E}}\|u^{i_{0}}(X_{t},t)-u^{i_{0}}_{\theta}(X_{t},t)\|_{2}^{2}\differential t.$ (F.1) $$

In practice, we evaluate the performance of the factorized network $u^{i_{0}}_{\theta}$ using factorized empirical discrete flow matching risk, which is defined as:

$$ $\displaystyle\widehat{\mathcal{R}}^{i_{0}}(\Theta^{i_{0}}):=\frac{1}{n}\sum_{i=1}^{n}\ell^{i_{0}}(x_{i};u^{i_{0}}_{\theta})-\frac{1}{n}\sum_{i=1}^{n}\ell^{i_{0}}(x_{i};u^{i_{0}}),$ (F.2) $$

where $\{x_{i}\}_{i=1}^{n}$ are n i.i.d samples and $u^{i_{0}}$ is the true velocity.
We have the following lemma showing that factorized discrete flow matching risk is equal to the expectation of factorized empirical discrete flow matching risk.

###### Lemma F.1 (Modified from Remark E.2 of (Su et al., 2025 ) ) .

For a factorized discrete flow matching network $u^{i_{0}}_{\theta}(x,t)$ with parameters noted as $\Theta^{i_{0}}$ and i.i.d samples $\{x_{i}\}_{i=1}^{n}$, it holds:

$$ $\displaystyle\underset{\{x_{i}\}_{i=1}^{n}}{\mathbb{E}}[\widehat{\mathcal{R}}^{i_{0}}(\Theta^{i_{0}})]=\mathcal{R}^{i_{0}}(\Theta^{i_{0}}).$ $$

###### Proof.

The proof is modified from Remark E.2 of (Su et al., 2025).

We use $\Theta^{i_{0},\rm true}$ to denote the true parameter of velocity function.
That’s to say, with parameter $\Theta^{i_{0},\rm true}$ it holds $u^{i_{0}}_{\theta}=u^{i_{0}}$.
Then we have:

$$ $\displaystyle\underset{\{x_{i}\}_{i=1}^{n}}{\mathbb{E}}[\widehat{\mathcal{R}}^{i_{0}}(\Theta^{i_{0}})]=$ $\displaystyle\penalty 10000\ \underset{\{x_{i}\}_{i=1}^{n}}{\mathbb{E}}[\frac{1}{n}\sum_{i=1}^{n}\ell^{i_{0}}(x_{i};u^{i_{0}}_{\theta})]-\underset{\{x_{i}\}_{i=1}^{n}}{\mathbb{E}}[\frac{1}{n}\sum_{i=1}^{n}\ell^{i_{0}}(x_{i};u^{i_{0}})]$ ( By ( F.2 ) ) $\displaystyle=$ $\displaystyle\penalty 10000\ \mathcal{L}^{i_{0}}_{\rm CDFM}(\Theta^{i_{0}})-\mathcal{L}^{i_{0}}_{\rm CDFM}(\Theta^{i_{0},\rm true})$ $\displaystyle=$ $\displaystyle\penalty 10000\ \mathcal{R}^{i_{0}}(\Theta^{i_{0}})-\mathcal{R}^{i_{0}}(\Theta^{i_{0},\rm true})$ ( By gradient equivalence of $\mathcal{L}^{i_{0}}_{\rm DFM}$ and $\mathcal{L}^{i_{0}}_{\rm CDFM}$ ) $\displaystyle=$ $\displaystyle\penalty 10000\ \mathcal{R}^{i_{0}}(\Theta^{i_{0}}).$ ( $\mathcal{R}^{i_{0}}(\Theta^{i_{0},\rm true})=0$ ) $$

This completes the proof.
∎

###### Lemma F.1 (Modified from Remark E.2 of (Su et al., 2025 ) ) .

###### Proof.

#### F.2 Auxiliary Lemmas

To bound $\underset{\{x_{i}\}_{i=1}^{n}}{\mathbb{E}}[\mathcal{R}^{i_{0}}(\widehat{\Theta}^{i_{0}})]$, we modify the risk decomposition approach formulated in (Fu et al., 2024) to discrete flow matching case.
Specifically, we have:

$$ $\displaystyle\underset{\{x_{i}\}_{i=1}^{n}}{\mathbb{E}}[\mathcal{R}^{i_{0}}(\widehat{\Theta}^{i_{0}})]=\underbrace{\underset{\{x_{i}\}_{i=1}^{n}}{\mathbb{E}}[\mathcal{R}^{i_{0}}(\widehat{\Theta}^{i_{0}})-\widehat{\mathcal{R}^{i_{0}}}(\widehat{\Theta}^{i_{0}})]}_{\rm(I)}+\underbrace{\underset{\{x_{i}\}_{i=1}^{n}}{\mathbb{E}}[\widehat{\mathcal{R}}^{i_{0}}(\widehat{\Theta}^{i_{0}})]}_{\rm(II)},$ (F.3) $$

In this section, we introduce auxiliary lemmas helping us prove [Theorem˜5.1](https://arxiv.org/html/2509.22623v1#S5.Thmtheorem1).
Specifically, we compute the covering number bound of transformers in [Lemma˜F.2](https://arxiv.org/html/2509.22623v1#A6.Thmlemma2) and [Lemma˜F.3](https://arxiv.org/html/2509.22623v1#A6.Thmlemma3).
Further, we obtain the covering number of loss function class in [Lemma˜F.4](https://arxiv.org/html/2509.22623v1#A6.Thmlemma4).
Finally, [Lemma˜F.5](https://arxiv.org/html/2509.22623v1#A6.Thmlemma5) and [Lemma˜F.6](https://arxiv.org/html/2509.22623v1#A6.Thmlemma6) bounds (I) and (II) in ([F.3](https://arxiv.org/html/2509.22623v1#A6.E3)) respectively.

To begin with, we introduce the definition of covering number, a concept that plays a fundamental role in establishing bounds on (I), the generalization error.

###### Definition F.1 (Covering Number) .

Consider a vector-valued function class $\mathcal{F}$.
For $\epsilon>0$, a point set $\{z_{i}\}_{i=1}^{n}$ and a norm $\|\cdot\|$ , the quantity $\mathcal{N}_{\infty}(\mathcal{F};\epsilon;\{z_{i}\}_{i=1}^{n};\|\cdot\|)$ denotes the minimal cardinality of a subset (a cover) $\mathcal{C}\subset\mathcal{F}$ such that, for any $f\in\mathcal{F}$, there exists $\widehat{f}\in\mathcal{C}$ such that:

$$ $\displaystyle\max_{1\leq i\leq n}\|f(z_{i})-\widehat{f}(z_{i})\|\leq\epsilon.$ $$

We call $\mathcal{N}_{\infty}(\mathcal{F};\epsilon;\{z_{i}\}_{i=1}^{n};\|\cdot\|)$ the $\epsilon$-covering number of $\mathcal{F}$ with respect to point set $\{z_{i}\}_{i=1}^{n}$.
We further set:

$$ $\displaystyle\mathcal{N}_{\infty}(\mathcal{F};\epsilon;m;\|\cdot\|)=\max_{\{z_{i}\}_{i=1}^{m}}\mathcal{N}_{\infty}(\mathcal{F};\epsilon;\{z_{i}\}_{i=1}^{m};\|\cdot\|).$ $$

Next, we introduce the following lemma that gives an upper bound on the covering number of multiple-layer transformer network.

###### Lemma F.2 (Lemma J.2 of (Hu et al., 2024b ) , Modified from Theorem A.17 of (Edelman et al., 2022 ) ) .

Let $\mathcal{T}^{h,s,r}_{R}(C_{\mathcal{T}},C^{2,\infty}_{KQ},C_{KQ},C^{2,\infty}_{OV},C_{OV},C_{E},C^{2,\infty}_{F},C_{F},L_{\mathcal{T}})$ represent the class of transformer network with parameter bound.
Then for data points $x$ such that $\|x\|_{2}\leq B_{X}$, we have:

$$ $\displaystyle\penalty 10000\ \log\mathcal{N}(\mathcal{T}^{h,s,r}_{R},\epsilon,n,\|\cdot\|_{2})$ $\displaystyle\leq$ $\displaystyle\penalty 10000\ \frac{\log(nL_{\mathcal{T}})}{\epsilon^{2}}\alpha^{2}(d_{0}^{\frac{2}{3}}(C_{F}^{2,\infty})^{\frac{2}{3}}+d_{0}^{\frac{2}{3}}(2(C_{F})^{2}C_{OV}C_{KQ}^{2,\infty})^{\frac{2}{3}}+2((C_{F})^{2}C_{OV}^{2,\infty})^{\frac{2}{3}})^{3},$ $$

where $\alpha=(C_{F})^{2}C_{OV}(1+4C_{KQ})(B_{X}+C_{E})$.

###### Proof.

See Remark J.7 of (Hu et al., 2024b) and proof of Lemma A.17 of (Edelman et al., 2022).
∎

Equipped with [Lemma˜F.2](https://arxiv.org/html/2509.22623v1#A6.Thmlemma2), we compute the covering number of transformer network class with parameter bound given in [Theorem˜4.1](https://arxiv.org/html/2509.22623v1#S4.Thmtheorem1).

###### Lemma F.3 (Covering Number Bound for Transformer Class, Modified from Lemma J.3 of (Hu et al., 2024b ) ) .

Let $\epsilon_{c}>0$.
Consider the transformer class $\mathcal{T}^{h,s,r}_{R}(C_{\mathcal{T}},C^{2,\infty}_{KQ},C_{KQ},C^{2,\infty}_{OV},C_{OV},C_{E},C^{2,\infty}_{F},C_{F})$ with parameter bound given in [Theorem˜E.1](https://arxiv.org/html/2509.22623v1#A5.Thmtheorem1) and $x_{i}$ satisfying $x_{i}\in\mathcal{S}$.
Then the $\epsilon_{c}$-covering number of $\mathcal{T}^{h,s,r}_{R}$ has the following upper bound:

$$ $\displaystyle\log\mathcal{N}(\mathcal{T}^{h,s,r}_{R},\epsilon_{c},n,\|\cdot\|_{2})\lesssim\frac{\log(nM)}{\epsilon_{c}^{2}}M^{24d_{0}+28}\epsilon^{-16d_{0}-12}.$ $$

###### Proof.

The proof is modified from proof of Lemma J.2 of (Hu et al., 2024b).

From [Theorem˜E.1](https://arxiv.org/html/2509.22623v1#A5.Thmtheorem1), we have the bounds on transformer parameters:

$$ $\displaystyle\penalty 10000\ C_{KQ},C^{2,\infty}_{KQ}=\widetilde{O}(M^{6d_{0}+3}\epsilon^{-4d_{0}-2});C_{OV},C^{2,\infty}_{OV}=O(M^{-\frac{1}{2}}\epsilon)$ $\displaystyle\penalty 10000\ C_{F},C^{2,\infty}_{F}=O(M^{2}\epsilon^{-1});C_{E}=O(M);L_{\mathcal{T}}=O(M^{6d_{0}+\frac{25}{2}}).$ (F.4) $$

We first use parameter in ([F.2](https://arxiv.org/html/2509.22623v1#A6.Ex14)) to compute $\alpha$ and get:

$$ $\displaystyle\alpha\lesssim(M^{2}\epsilon^{-1})^{2}\cdot M^{-\frac{1}{2}}\epsilon\cdot M^{6d_{0}+3}\epsilon^{-4d_{0}-2}\cdot M=M^{6d_{0}+\frac{15}{2}}\epsilon^{-4d_{0}-3}.$ $$

Further, by [Lemma˜F.2](https://arxiv.org/html/2509.22623v1#A6.Thmlemma2) we have:

$$ $\displaystyle\penalty 10000\ \log\mathcal{N}(\mathcal{T}^{h,s,r}_{R},\epsilon_{c},n,\|\cdot\|_{2})$ $\displaystyle\lesssim$ $\displaystyle\penalty 10000\ \frac{\log(nL_{\mathcal{T}})}{\epsilon_{c}^{2}}\alpha^{2}(d_{0}^{\frac{2}{3}}(2(C_{F})^{2}C_{OV}C_{KQ}^{2,\infty})^{\frac{2}{3}})^{3}$ $\displaystyle\lesssim$ $\displaystyle\penalty 10000\ \frac{\log(nM)}{\epsilon_{c}^{2}}M^{24d_{0}+28}\epsilon^{-16d_{0}-12}.$ $$

This completes the proof.
∎

Then we compute the covering number bound of loss function class by bounding error of loss function with error of transformer.

###### Lemma F.4 (Covering Number Bound for Loss Function Class, Modified from Lemma L.3 of (Su et al., 2025 ) ) .

Let $\epsilon_{c}>0$ and $i_{0}\in[M]$.
Suppose that for every given $x\in\mathcal{S}$, $u^{i_{0}}(x,t)$ represent the velocity field of $x$ at time $t$ that follows mixture path setting ([E.2](https://arxiv.org/html/2509.22623v1#A5.E2)).
We define the factorized loss function class by

$$ $\displaystyle F^{i_{0}}_{\rm loss}:=\{\ell^{i_{0}}(x;u^{i_{0}}_{\theta})|u^{i_{0}}_{\theta}\in\mathcal{T}^{h,s,r}_{R}\},$ $$

where $\mathcal{T}^{h,s,r}_{R}$ is the transformer class with parameter bound given in [Theorem˜4.1](https://arxiv.org/html/2509.22623v1#S4.Thmtheorem1).

Then we have:

$$ $\displaystyle\log\mathcal{N}(F^{i_{0}}_{\rm loss},\epsilon_{c},\{x_{i}\}_{x_{i}\in\mathcal{S}},|\cdot|)\lesssim\frac{\log(M)-\log(\epsilon_{c})}{\epsilon_{c}^{2}}M^{24d_{0}+28}\epsilon^{-16d_{0}-12}.$ $$

###### Proof.

The proof is modified from the proof of Lemma L.3 of (Su et al., 2025).

Consider $i_{0}\in[d]$and $\{x_{i}\}_{i=1}^{n}\in\mathcal{S}$.
Let $u^{i_{0}}_{1}(x,t),u^{i_{0}}_{2}(x,t)$ be mixture path velocity function satisfying $\|u^{i_{0}}_{1}(x,t)-u^{i_{0}}_{2}(x,t)\|\leq\delta$ for all $x\in\mathcal{S}$ and $t=0,\frac{1}{\lceil\frac{L_{\mathcal{T}}}{\delta}\rceil},\frac{2}{\lceil\frac{L_{\mathcal{T}}}{\delta}\rceil},\dots,1$.
Then since $u^{i_{0}}_{1}$ and $u^{i_{0}}_{2}$ is Lipschitz continuous with Lipschitz constant $L_{\mathcal{T}}$ under $\ell_{2}$-norm, for $x\in\mathcal{S}$ and $t\in[0,1]$ we have $\|u^{i_{0}}_{1}(x,t)-u^{i_{0}}_{2}(x,t)\|\leq 2\delta$.

Further, for $x=x_{i},1\leq i\leq n$ we have:

$$ $\displaystyle\penalty 10000\ |\ell(^{i_{0}}x;u^{i_{0}}_{1})-\ell^{i_{0}}(x;u^{i_{0}}_{2})|$ $\displaystyle=$ $\displaystyle\penalty 10000\ |\int_{t_{0}}^{T}\underset{X_{0}\sim p_{0},X_{t}\sim p_{t|x_{0}=X_{0},x_{1}=x}}{\mathbb{E}}(\|u^{i_{0}}_{1}(X_{t},t)-u^{i_{0}}(X_{t},t)\|_{2}^{2}-\|u^{i_{0}}_{2}(X_{t},t)-u^{i_{0}}(X_{t},t)\|_{2}^{2})\differential t|$ $\displaystyle=$ $\displaystyle\penalty 10000\ |\int_{t_{0}}^{T}\underset{X_{0}\sim p_{0},X_{t}\sim p_{t|x_{0}=X_{0},x_{1}=x}}{\mathbb{E}}(u^{i_{0}}_{1}(X_{t},t)-u^{i_{0}}_{2}(X_{t},t))^{\top}(u^{i_{0}}_{1}(X_{t},t)+u^{i_{0}}_{2}(X_{t},t)-2u^{i_{0}}(X_{t},t)))\differential t|$ $\displaystyle\leq$ $\displaystyle\penalty 10000\ 2\delta\int_{0}^{1}\underset{X_{0}\sim p_{0},X_{t}\sim p_{t|x_{0}=X_{0},x_{1}=x}}{\mathbb{E}}\|u^{i_{0}}_{1}(X_{t},t)+u^{i_{0}}_{2}(X_{t},t)-2u^{i_{0}}(X_{t},t)\|_{2}\differential t$ ( $\|u^{i_{0}}_{1}-u^{i_{0}}_{2}\|_{2}\leq 2\delta$ ) $\displaystyle\leq$ $\displaystyle\penalty 10000\ 8\delta C_{\mathcal{T}},$ $$

where the last line is by assuming $C_{\mathcal{T}}\geq\underset{t\in[t_{0},T]}{\max}\frac{2\dot{\kappa}(t)}{1-\kappa(t)}$ without losing generality.

From computation above, for every function class $\mathcal{U}$ being a $\epsilon_{c}$-covering of $\mathcal{T}^{h,s,r}_{R}$ with respect to point set $S$, function class $\mathcal{L}=\{\ell(x;u)|u\in\mathcal{U}\}$ is a $4\epsilon_{c}C_{\mathcal{T}}$-covering of $F^{i_{0}}_{\rm loss}$.
Recall that we assume $\frac{\dot{\kappa}(t)}{1-\kappa(t)}=O(1)$ when $t\in[t_{0},T]$ in [Section˜E.2](https://arxiv.org/html/2509.22623v1#A5.SS2).
Then, for small enough $\epsilon$ it holds that $C_{\mathcal{T}}=O(1)$.
We further obtain:

$$ $\displaystyle\log\mathcal{N}(F^{i_{0}}_{\rm loss},\epsilon_{c},\{x_{i}\}_{x_{i}\in\mathcal{S}},|\cdot|)\leq$ $\displaystyle\penalty 10000\ \log\mathcal{N}(\mathcal{T}^{h,s,r}_{R},\frac{\epsilon_{c}}{8C_{\mathcal{T}}},M^{d}(\lceil\frac{L_{\mathcal{T}}}{\epsilon_{c}}\rceil+1),|\cdot|)$ $\displaystyle\lesssim$ $\displaystyle\penalty 10000\ \frac{\log(M)-\log(\epsilon_{c})}{\epsilon_{c}^{2}}M^{24d_{0}+28}\epsilon^{-16d_{0}-12}.$ ( By Lemma F.3 ) $$

This completes the proof.
∎

We now bound (I) with covering number of loss function class and (II), the empirical risk.

###### Lemma F.5 (Generalization Bound, Modified from Lemma L.5 of (Su et al., 2025 ) ) .

Let $\widehat{u}^{i_{0}}_{\theta}$ with parameter $\widehat{\Theta}^{i_{0}}$ be the velocity estimator trained by minimizing $\widehat{\mathcal{L}}^{i_{0}}_{\rm CDFM}$ with i.i.d training samples $\{x_{i}\}_{i=1}^{n}$, where $x_{i}\in\mathcal{S}$.
For simplicity, we use $\mathcal{N}$ to denote $\mathcal{N}(F^{i_{0}}_{\rm loss},\epsilon_{c},\{x_{i}\}_{x_{i}\in\mathcal{S}},|\cdot|)$.
Then we bound (I), the generalization bound as:

$$ $\displaystyle\underset{\{x_{i}\}_{i=1}^{n}}{\mathbb{E}}[\mathcal{R}^{i_{0}}(\widehat{\Theta}^{i_{0}})-\widehat{\mathcal{R}}^{i_{0}}(\widehat{\Theta}^{i_{0}})]\lesssim\underset{\{x_{i}\}_{i=1}^{n}}{\mathbb{E}}[\widehat{\mathcal{R}}^{i_{0}}(\widehat{\Theta}^{i_{0}})]+O(\frac{\kappa}{n}\log\mathcal{N}+\epsilon_{c}),$ $$

where $\kappa$ denote the upper bound of $\ell^{i_{0}}(x;u^{i_{0}}_{\theta})$.

###### Proof.

The proof is modified from the proof of Lemma L.5 of (Su et al., 2025).

We use $\widehat{\mathcal{L}}^{*,i_{0}}_{\rm CDFM}$ and $\widehat{\mathcal{R}}^{*,i_{0}}$ to denote the factorize conditional discrete flow matching loss and empirical risk with i.i.d training samples $\{x_{i}^{*}\}$.
Then we have $\underset{\{x_{i}^{*}\}_{i=1}^{n}}{\mathbb{E}}[\widehat{\mathcal{L}}^{*,i_{0}}_{\rm CDFM}(\Theta^{i_{0}})]=\mathcal{L}^{i_{0}}_{\rm CDFM}(\Theta^{i_{0}})$ and $\underset{\{x_{i}^{*}\}_{i=1}^{n}}{\mathbb{E}}[\widehat{\mathcal{R}}^{*,i_{0}}(\Theta^{i_{0}})]=\mathcal{R}^{i_{0}}(\Theta^{i_{0}})$ for all parameter set $\Theta^{i_{0}}$.
We now rewrite (I) as:

$$ $\displaystyle\penalty 10000\ \underset{\{x_{i}\}_{i=1}^{n}}{\mathbb{E}}[\mathcal{R}^{i_{0}}(\widehat{\Theta}^{i_{0}})-\widehat{\mathcal{R}}^{i_{0}}(\widehat{\Theta}^{i_{0}})]$ $\displaystyle=$ $\displaystyle\penalty 10000\ \underset{\{x_{i}\}_{i=1}^{n}}{\mathbb{E}}[\underset{\{x_{i}^{*}\}_{i=1}^{n}}{\mathbb{E}}[\widehat{\mathcal{R}}^{*,i_{0}}(\widehat{\Theta}^{i_{0}})]-\widehat{\mathcal{R}}^{i_{0}}(\widehat{\Theta}^{i_{0}})]$ $\displaystyle=$ $\displaystyle\penalty 10000\ \underset{\{x_{i},x_{i}^{*}\}_{i=1}^{n}}{\mathbb{E}}[\widehat{\mathcal{R}}^{*,i_{0}}(\widehat{\Theta}^{i_{0}})-\widehat{\mathcal{R}}^{i_{0}}(\widehat{\Theta}^{i_{0}})]$ $\displaystyle=$ $\displaystyle\penalty 10000\ \frac{1}{n}\underset{\{x_{i},x_{i}^{*}\}_{i=1}^{n}}{\mathbb{E}}[(\sum_{i=1}^{n}\ell^{i_{0}}(x_{i}^{*};\widehat{u}^{i_{0}}_{\theta})-\sum_{i=1}^{n}\ell^{i_{0}}(x_{i}^{*};u^{i_{0}}))-(\sum_{i=1}^{n}\ell^{i_{0}}(x_{i};\widehat{u}^{i_{0}})-\sum_{i=1}^{n}\ell^{i_{0}}(x_{i};u^{i_{0}}))].$ $$

For $\epsilon_{c}$ to be chosen later, let $\mathcal{L}=\{\ell^{i_{0}}_{1},\ell^{i_{0}}_{2}...\ell^{i_{0}}_{\mathcal{N}}\}$ be a $\epsilon_{c}$-covering of $F^{i_{0}}_{\rm loss}$ with respect to point set $S$.
That’s to say, for every $\widehat{u}^{i_{0}}_{\theta}$, there exists $\ell^{i_{0}}_{j}\in\mathcal{L}$ such that $|\ell^{i_{0}}_{j}-\ell^{i_{0}}(x,\widehat{u}^{i_{0}}_{\theta})|\leq\epsilon_{c}$ for every $x\in\mathcal{S}$.
For simplicity of notations, we have the following definitions:

$$ $\displaystyle\omega(x):=$ $\displaystyle\penalty 10000\ \ell^{i_{0}}(x;\widehat{u}^{i_{0}}_{\theta})-\ell^{i_{0}}(x;u^{i_{0}}),$ $\displaystyle\omega_{j}(x):=$ $\displaystyle\penalty 10000\ \ell^{i_{0}}_{j}(x)-\ell^{i_{0}}(x;u^{i_{0}}),$ $\displaystyle h_{j}:=$ $\displaystyle\penalty 10000\ \max\{A,\sqrt{\underset{z\in\mathcal{S}}{\mathbb{E}}[\ell^{i_{0}}_{j}(z)-\ell^{i_{0}}(z,u^{i_{0}})]}\},$ ( $A$ is a constant to be chosen later ) $\displaystyle\Omega:=$ $\displaystyle\penalty 10000\ \max_{k\in[\mathcal{N}]}|\sum_{i=1}^{n}\frac{\omega_{k}(x_{i})-\omega_{k}(x_{i}^{*})}{h_{k}}|.$ $$

Then we further obtain:

$$ $\displaystyle\penalty 10000\ |\frac{1}{n}\underset{\{x_{i},x_{i}^{*}\}_{i=1}^{n}}{\mathbb{E}}[(\sum_{i=1}^{n}\ell^{i_{0}}(x_{i}^{*};\widehat{u}^{i_{0}}_{\theta})-\sum_{i=1}^{n}\ell^{i_{0}}(x_{i}^{*};u^{i_{0}}))-(\sum_{i=1}^{n}\ell^{i_{0}}(x_{i};\widehat{u}^{i_{0}}_{\theta})-\sum_{i=1}^{n}\ell^{i_{0}}(x_{i};u^{i_{0}}))]|$ (F.5) $\displaystyle\leq$ $\displaystyle\penalty 10000\ \frac{1}{n}\underset{\{x_{i},x_{i}^{*}\}_{i=1}^{n}}{\mathbb{E}}|\omega(x_{i}^{*})-\omega(x_{i})|$ ( By definition of $\omega(x)$ ) $\displaystyle\leq$ $\displaystyle\penalty 10000\ \frac{1}{n}\underset{\{x_{i},x_{i}^{*}\}_{i=1}^{n}}{\mathbb{E}}|\omega_{j}(x_{i}^{*})-\omega_{j}(x_{i})|+2\epsilon_{c}$ ( By $|w_{j}(x)-\omega(x)|\leq\epsilon_{c}$ when $x\in\mathcal{S}$ ) $\displaystyle\leq$ $\displaystyle\penalty 10000\ \frac{1}{n}\underset{\{x_{i},x_{i}^{*}\}_{i=1}^{n}}{\mathbb{E}}[h_{j}\Omega]+2\epsilon_{c}$ ( By definition of $h_{j}$ and $\Omega$ ) $\displaystyle\leq$ $\displaystyle\penalty 10000\ \frac{1}{2}\underset{\{x_{i},x_{i}^{*}\}_{i=1}^{n}}{\mathbb{E}}[h_{j}^{2}]+\frac{1}{2n^{2}}\underset{\{x_{i},x_{i}^{*}\}_{i=1}^{n}}{\mathbb{E}}[\Omega^{2}]+2\epsilon_{c},$ (F.6) $$

where the last line follows AM-GM Inequality.
In the following paragraphs, we bound $\underset{\{x_{i},x_{i}^{*}\}_{i=1}^{n}}{\mathbb{E}}[h_{j}^{2}]$ and $\underset{\{x_{i},x_{i}^{*}\}_{i=1}^{n}}{\mathbb{E}}[\Omega^{2}]$ separately.
We start with bounding $\underset{\{x_{i},x_{i}^{*}\}_{i=1}^{n}}{\mathbb{E}}[h_{j}^{2}]$:

$$ $\displaystyle\underset{\{x_{i},x_{i}^{*}\}_{i=1}^{n}}{\mathbb{E}}[h_{j}^{2}]=$ $\displaystyle\penalty 10000\ \underset{\{x_{i}\}_{i=1}^{n}}{\mathbb{E}}[h_{j}^{2}]$ $\displaystyle\leq$ $\displaystyle\penalty 10000\ A^{2}+\underset{\{x_{i}\}_{i=1}^{n},z\in\mathcal{S}}{\mathbb{E}}[\ell^{i_{0}}_{j}(z)-\ell^{i_{0}}(z,u)]$ $\displaystyle\leq$ $\displaystyle\penalty 10000\ A^{2}+\underset{\{x_{i}\}_{i=1}^{n},z\in\mathcal{S}}{\mathbb{E}}[\ell^{i_{0}}(z;\widehat{u}^{i_{0}}_{\theta})-\ell^{i_{0}}(z;u^{i_{0}})]+\epsilon_{c}$ ( $|\ell^{i_{0}}_{j}(z)-\ell^{i_{0}}(z,\widehat{u}^{i_{0}}_{\theta})|\leq\epsilon_{c}$ when $z\in\mathcal{S}$ ) $\displaystyle=$ $\displaystyle\penalty 10000\ A^{2}+\underset{\{x_{i}\}_{i=1}^{n}}{\mathbb{E}}[\mathcal{R}^{i_{0}}(\widehat{\Theta}^{i_{0}})]+\epsilon_{c}.$ (F.7) $$

where the last line follows [Lemma˜F.1](https://arxiv.org/html/2509.22623v1#A6.Thmlemma1).
Next, we bound $\underset{\{x_{i},x_{i}^{*}\}_{i=1}^{n}}{\mathbb{E}}[\Omega^{2}]$ by using Bernstein’s Inequality to bound $\Pr(\Omega\geq b)$ for given $b>0$.
We define $a_{k,i}$ as $a_{k,i}:=\frac{\omega_{k}(x_{i})-\omega_{k}(x_{i}^{*})}{h_{k}}$.
Then $\Omega=\max_{k\in[\mathcal{N}]}|\sum_{i=1}^{n}a_{k,i}|$.
Also, since $\kappa$ denote the upper bound of $\ell^{i_{0}}(x;u^{i_{0}}_{\theta})$, we have $\ell^{i_{0}}(x;u^{i_{0}}_{\theta})\leq\kappa$.
For $k\in[\mathcal{N}]$ we have:

$$ $\displaystyle|a_{k,i}|\leq|\frac{\ell^{i_{0}}_{k}(x)}{h_{k}}|\leq\frac{\kappa}{A}.$ (F.8) $$

By definition of $\omega_{j}(x)$ and $h_{j}$, for all $k\in[\mathcal{N}]$ we have:

$$ $\displaystyle\underset{x}{\mathbb{E}}[\omega_{k}(x)]=\underset{x}{\mathbb{E}}[\ell^{i_{0}}_{k}(x)-\ell^{i_{0}}(x;u^{i_{0}})]\leq h_{k}^{2}.$ (F.9) $$

By symmetrization, we get:

$$ $\displaystyle\mathbb{E}[a_{k,i}]=\underset{\{x_{i},x_{i}^{*}\}}{\mathbb{E}}[\frac{\omega_{k}(x_{i})-\omega_{k}(x_{i}^{*})}{h_{k}}]=0.$ (F.10) $$

Then we bound the variation of $a_{k,i}$ as:

$$ $\displaystyle\underset{x_{i},x_{i}^{*}}{\rm Var}[a_{k,i}]=$ $\displaystyle\penalty 10000\ \underset{x_{i},x_{i}^{*}}{\mathbb{E}}[(\frac{\omega_{k}(x_{i})-\omega_{k}(x_{i}^{*})}{h_{k}})^{2}]$ $\displaystyle=$ $\displaystyle\penalty 10000\ \underset{x_{i},x_{i}^{*}}{\mathbb{E}}[\frac{\omega_{k}^{2}(x_{i})}{h_{k}^{2}}+\frac{\omega_{k}^{2}(x_{i}^{*})}{h_{k}^{2}}-\frac{2\omega_{k}(x_{i})\omega_{k}(x_{i}^{*})}{h_{k}^{2}}]$ $\displaystyle=$ $\displaystyle\penalty 10000\ 2\underset{x}{\mathbb{E}}[\frac{\omega_{k}^{2}(x)}{h_{k}^{2}}]-2(\underset{x}{\mathbb{E}}[\frac{\omega_{k}(x)}{h_{k}}])^{2}$ ( By symmetrization ) $\displaystyle\leq$ $\displaystyle\penalty 10000\ 2\underset{x}{\mathbb{E}}[\frac{\omega_{k}^{2}(x)}{h_{k}^{2}}]$ $\displaystyle\leq$ $\displaystyle\penalty 10000\ 2\kappa\underset{x}{\mathbb{E}}[\frac{\omega_{k}(x)}{h_{k}^{2}}]$ ( By ( F.8 ) ) $\displaystyle\leq$ $\displaystyle\penalty 10000\ 2\kappa,$ (F.11) $$

where the last line follows ([F.9](https://arxiv.org/html/2509.22623v1#A6.E9)).

Then for $b>0$ we have:

$$ $\displaystyle\Pr[\Omega^{2}\geq b^{2}]=$ $\displaystyle\penalty 10000\ \Pr[\Omega\geq b]$ (F.12) $\displaystyle\leq$ $\displaystyle\penalty 10000\ \mathcal{N}\Pr[|\sum_{i=1}^{k}a_{k,i}|\geq b]$ ( By union bound ) $\displaystyle\leq$ $\displaystyle\penalty 10000\ 2\mathcal{N}\exp(-\frac{\frac{b^{2}}{2}}{\sum_{i=1}^{n}2\kappa+\frac{b\kappa}{3A}})$ ( By ( F.8 ),( F.11 ) and Bernstein’s Inequality ) $\displaystyle=$ $\displaystyle\penalty 10000\ 2\mathcal{N}\exp(-\frac{\frac{b^{2}}{2}}{2n\kappa+\frac{b\kappa}{3A}})$ (F.13) $$

We now bound $\underset{\{x_{i},x_{i}^{*}\}_{i=1}^{n}}{\mathbb{E}}[\Omega^{2}]$ as:

$$ $\displaystyle\underset{\{x_{i},x_{i}^{*}\}_{i=1}^{n}}{\mathbb{E}}[\Omega^{2}]=$ $\displaystyle\penalty 10000\ \int_{0}^{b_{0}^{2}}\Pr[\Omega^{2}<b^{2}]\differential b+\int_{b_{0}^{2}}^{\infty}\Pr[\Omega^{2}\geq b^{2}]\differential b$ ( $b_{0}$ is a constant to be determined ) $\displaystyle\leq$ $\displaystyle\penalty 10000\ b_{0}^{2}+\int_{b_{0}^{2}}^{\infty}2\mathcal{N}\exp(-\frac{\frac{b^{2}}{2}}{2n\kappa+\frac{b\kappa}{3A}})\differential b$ ( By ( F.13 ) ) $\displaystyle\leq$ $\displaystyle\penalty 10000\ b_{0}^{2}+\int_{b_{0}^{2}}^{\infty}2\mathcal{N}\exp(-\frac{Ab}{\kappa})\differential b$ ( Assume $b_{0}\geq 12nA$ ) $\displaystyle=$ $\displaystyle\penalty 10000\ b_{0}^{2}+\frac{2\mathcal{N}\kappa}{A}\exp(-\frac{Ab_{0}^{2}}{\kappa}).$ $$

Let $b_{0}=\sqrt[3]{n\kappa\log\mathcal{N}}$ and $A=\frac{b_{0}}{12n}$, we have:

$$ $\displaystyle\underset{\{x_{i},x_{i}^{*}\}_{i=1}^{n}}{\mathbb{E}}[\Omega^{2}]\lesssim n\kappa\log\mathcal{N}.$ (F.14) $$

Substituting the result of ([F.7](https://arxiv.org/html/2509.22623v1#A6.E7)) and ([F.14](https://arxiv.org/html/2509.22623v1#A6.E14)) into ([F.6](https://arxiv.org/html/2509.22623v1#A6.E6)), we finish the proof.
∎

With [Lemma˜F.5](https://arxiv.org/html/2509.22623v1#A6.Thmlemma5), we reduce bounding (I) to bounding (II).
Finally, we bound (II) with [Theorem˜E.1](https://arxiv.org/html/2509.22623v1#A5.Thmtheorem1).

###### Lemma F.6 (Empirical Risk Bound, Modified from Theorem L.1 of (Su et al., 2025 ) ) .

Consider the transformer class $\mathcal{T}^{h,s,r}_{R}$ with parameter bound given in [Theorem˜E.1](https://arxiv.org/html/2509.22623v1#A5.Thmtheorem1).
Let $\widehat{u}^{i_{0}}_{\theta}\in\mathcal{T}^{h,s,r}_{R}$ with parameter $\widehat{\Theta}^{i_{0}}$ be the factorized velocity estimator under mixture path setting trained by minimizing $\widehat{\mathcal{L}}^{i_{0}}_{\rm CDFM}$ with i.i.d training samples $\{x_{i}\}_{i=1}^{n}$, where $x_{i}\in\mathcal{S}$.
Let factorized empirical risk $\widehat{\mathcal{R}}^{i_{0}}(\widehat{\Theta}^{i_{0}})$ be as defined in ([F.2](https://arxiv.org/html/2509.22623v1#A6.E2)).
Then we have:

$$ $\displaystyle\underset{\{x_{i}\}_{i=1}^{n}}{\mathbb{E}}[\widehat{\mathcal{R}}^{i_{0}}(\widehat{\Theta}^{i_{0}})]\lesssim\epsilon^{\frac{4}{M+2}}M^{\frac{12Md_{0}+25M}{M+2}}.$ $$

###### Proof.

The proof is modified from proof of Theorem L.1 of (Su et al., 2025).

Given that $\widehat{u}_{\theta}$ with parameter $\widehat{\Theta}$ is the minimizer of $\widehat{\mathcal{L}}_{\rm CDFM}$, for all $u_{\theta}$ with parameter $\Theta$ we have:

$$ $\displaystyle\underset{\{x_{i}\}_{i=1}^{n}}{\mathbb{E}}[\widehat{\mathcal{R}}^{i_{0}}(\widehat{\Theta}^{i_{0}})]=$ $\displaystyle\penalty 10000\ \underset{\{x_{i}\}_{i=1}^{n}}{\mathbb{E}}[\widehat{\mathcal{L}}^{i_{0}}_{\rm CDFM}(\widehat{u}^{i_{0}}_{\theta})-\widehat{\mathcal{L}}^{i_{0}}_{\rm CDFM}(u^{i_{0}})]$ $\displaystyle\leq$ $\displaystyle\penalty 10000\ \underset{\{x_{i}\}_{i=1}^{n}}{\mathbb{E}}[\widehat{\mathcal{L}}^{i_{0}}_{\rm CDFM}(u^{i_{0}}_{\theta})-\widehat{\mathcal{L}}^{i_{0}}_{\rm CDFM}(u^{i_{0}})]$ $\displaystyle=$ $\displaystyle\penalty 10000\ \underset{\{x_{i}\}_{i=1}^{n}}{\mathbb{E}}[\widehat{\mathcal{R}}^{i_{0}}(\Theta^{i_{0}})]$ $\displaystyle=$ $\displaystyle\penalty 10000\ \mathcal{R}^{i_{0}}(\Theta^{i_{0}}).$ ( By Lemma F.1 ) $$

Let $u_{\theta}^{i_{0},\rm approx}$ with parameter $\Theta^{i_{0},\rm approx}$ be the approximator network in [Theorem˜E.1](https://arxiv.org/html/2509.22623v1#A5.Thmtheorem1), we obtain:

$$ $\displaystyle\underset{\{x_{i}\}_{i=1}^{n}}{\mathbb{E}}\widehat{\mathcal{R}}^{i_{0}}[(\widehat{\Theta}^{i_{0}})]\leq$ $\displaystyle\penalty 10000\ \mathcal{R}^{i_{0}}(\Theta^{i_{0},\rm approx})$ $\displaystyle=$ $\displaystyle\penalty 10000\ \sum_{x\in\mathcal{S}}\|u_{\theta}^{i_{0},\rm approx}(x,t)-u^{i_{0}}(x,t)\|^{2}_{2}\cdot p_{t}(x)$ $\displaystyle\lesssim$ $\displaystyle\penalty 10000\ \epsilon^{\frac{4}{M+2}}M^{\frac{12Md_{0}+25M}{M+2}}.$ $$

This completes the proof.
∎

###### Definition F.1 (Covering Number) .

###### Lemma F.2 (Lemma J.2 of (Hu et al., 2024b ) , Modified from Theorem A.17 of (Edelman et al., 2022 ) ) .

###### Proof.

###### Lemma F.3 (Covering Number Bound for Transformer Class, Modified from Lemma J.3 of (Hu et al., 2024b ) ) .

###### Proof.

###### Lemma F.4 (Covering Number Bound for Loss Function Class, Modified from Lemma L.3 of (Su et al., 2025 ) ) .

###### Proof.

###### Lemma F.5 (Generalization Bound, Modified from Lemma L.5 of (Su et al., 2025 ) ) .

###### Proof.

###### Lemma F.6 (Empirical Risk Bound, Modified from Theorem L.1 of (Su et al., 2025 ) ) .

###### Proof.

#### F.3 Main Proof of Theorem ˜ 5.1

This section presents the main proof of [Theorem˜5.1](https://arxiv.org/html/2509.22623v1#S5.Thmtheorem1).
In the main text, we give a simplified version of [Theorem˜5.1](https://arxiv.org/html/2509.22623v1#S5.Thmtheorem1) to keep the exposition concise, while [Theorem˜F.1](https://arxiv.org/html/2509.22623v1#A6.Thmtheorem1) provides the explicit form.

###### Theorem F.1 (Mixture Path Discrete Flow Matching Velocity Estimation with Transformer, Theorem ˜ 5.1 Restate) .

Let $\widehat{u}^{i_{0}}_{\theta}\in\mathcal{T}^{h,s,r}_{R}$ with parameter $\widehat{\Theta}^{i_{0}}$ be the factorized velocity estimator under mixture path setting trained by minimizing $\widehat{\mathcal{L}}^{i_{0}}_{\rm CDFM}$ with i.i.d training samples $\{x_{i}\}_{i=1}^{n}$, where $x_{i}\in\mathcal{S}$.
Then for large enough $n$ we have:

$$ $\displaystyle\underset{\{x_{i}\}_{i=1}^{n}}{\mathbb{E}}[\mathcal{R}^{i_{0}}(\widehat{\Theta}^{i_{0}})]\lesssim M^{12d_{0}+25}n^{-\frac{1}{4Md_{0}+3M+8d_{0}+9}}(\log n)^{\frac{1}{4Md_{0}+3M+8d_{0}+9}}$ $$

###### Proof.

Recall the decomposition given in ([F.3](https://arxiv.org/html/2509.22623v1#A6.E3)):

$$ $\displaystyle\underset{\{x_{i}\}_{i=1}^{n}}{\mathbb{E}}[\mathcal{R}^{i_{0}}(\widehat{\Theta}^{i_{0}})]=\underset{\{x_{i}\}_{i=1}^{n}}{\mathbb{E}}[\mathcal{R}^{i_{0}}(\widehat{\Theta}^{i_{0}})-\widehat{\mathcal{R}^{i_{0}}}(\widehat{\Theta}^{i_{0}})]+\underset{\{x_{i}\}_{i=1}^{n}}{\mathbb{E}}[\widehat{\mathcal{R}}^{i_{0}}(\widehat{\Theta}^{i_{0}})].$ $$

Substituting what we get in [Lemma˜F.5](https://arxiv.org/html/2509.22623v1#A6.Thmlemma5) and [Lemma˜F.6](https://arxiv.org/html/2509.22623v1#A6.Thmlemma6) into the decomposition, we get:

$$ $\displaystyle\underset{\{x_{i}\}_{i=1}^{n}}{\mathbb{E}}[\mathcal{R}^{i_{0}}(\widehat{\Theta}^{i_{0}})]\lesssim$ $\displaystyle\penalty 10000\ O(\frac{\kappa}{n}\log\mathcal{N}+\epsilon_{c})+2\underset{\{x_{i}\}_{i=1}^{n}}{\mathbb{E}}[\widehat{\mathcal{R}}^{i_{0}}(\widehat{\Theta}^{i_{0}})]$ ( By Lemma F.5 ) $\displaystyle\lesssim$ $\displaystyle\penalty 10000\ O(\frac{\kappa}{n}\log\mathcal{N}+\epsilon_{c})+\epsilon^{\frac{4}{M+2}}M^{\frac{12Md_{0}+25M}{M+2}}$ ( By Lemma F.6 ) $\displaystyle\lesssim$ $\displaystyle\penalty 10000\ \frac{\log(M)-\log(\epsilon_{c})}{n\epsilon_{c}^{2}}M^{24d_{0}+28}\epsilon^{-16d_{0}-12}+\epsilon_{c}+\epsilon^{\frac{4}{M+2}}M^{\frac{12Md_{0}+25M}{M+2}}.$ ( By Lemma F.4 and $\kappa\lesssim 1$ under mixture path setting ) $$

Next, we choose proper $\epsilon,\epsilon_{c}$ to get a optimal bound for the estimation rates.

First, we let $\epsilon_{c}=(\frac{\log(n\epsilon)M^{24d_{0}+28}\epsilon^{-16d_{0}-12}}{n})^{1/3}$ and get

$$ $\displaystyle\underset{\{x_{i}\}_{i=1}^{n}}{\mathbb{E}}[\mathcal{R}^{i_{0}}(\widehat{\Theta}^{i_{0}})]\lesssim$ $\displaystyle\penalty 10000\ (\log(n\epsilon))^{1/3}M^{\frac{24d_{0}+28}{3}}\epsilon^{-\frac{16d_{0}+12}{3}}n^{-\frac{1}{3}}+\epsilon^{\frac{4}{M+2}}M^{\frac{12Md_{0}+25M}{M+2}}.$ $$

Next, let $\epsilon=M^{-\frac{3}{4}}n^{-\frac{M+2}{16Md_{0}+12M+32d_{0}+36}}(\log n)^{\frac{M+2}{16Md_{0}+12M+32d_{0}+36}}$, then for large enough $n$ we get:

$$ $\displaystyle\underset{\{x_{i}\}_{i=1}^{n}}{\mathbb{E}}[\mathcal{R}^{i_{0}}(\widehat{\Theta}^{i_{0}})]\lesssim M^{12d_{0}+25}n^{-\frac{1}{4Md_{0}+3M+8d_{0}+9}}(\log n)^{\frac{1}{4Md_{0}+3M+8d_{0}+9}}.$ $$

This completes the proof.
∎

###### Theorem F.1 (Mixture Path Discrete Flow Matching Velocity Estimation with Transformer, Theorem ˜ 5.1 Restate) .

###### Proof.

### Appendix G Proof of Theorem ˜ 5.2

This section provides the main proof of [Theorem˜5.2](https://arxiv.org/html/2509.22623v1#S5.Thmtheorem2).
In the main text, we give a simplified version of [Theorem˜5.2](https://arxiv.org/html/2509.22623v1#S5.Thmtheorem2) to keep the exposition concise, while [Theorem˜G.1](https://arxiv.org/html/2509.22623v1#A7.Thmtheorem1) below presents the explicit form.

###### Theorem G.1 (Discrete Flow Matching Distribution Estimation with Transformer, Theorem ˜ 5.2 Restate) .

For any coordinate $i_{0}\in[d]$, let $\widehat{u}^{i_{0}}_{\theta}$ be the $i$-th velocity estimator trained by minimizing empirical conditional discrete flow matching loss $\widehat{\mathcal{L}}^{i_{0}}_{\rm CDFM}$ following ([2.10](https://arxiv.org/html/2509.22623v1#S2.E10)).
Let $P$ denote the true distribution and $\widehat{P}$ the distribution generated by the discrete flow matching framework with factorized velocity estimators $\{\widehat{u}^{i_{0}}_{\theta}\}_{i^{0}=1}^{d}$.
Then for a vocabulary size $M$, the expected total variation distance $\text{TV}(P,\widehat{P})$ over training data $\{x_{i}\}_{i=1}^{n}$ is bounded by:

$$ $\displaystyle\underset{\{x_{i}\}_{i=1}^{n}}{\mathbb{E}}[\text{TV}(P,\widehat{P})]\lesssim M^{6d_{0}+13}\exp(M)n^{-\frac{1}{8Md_{0}+6M+16d_{0}+18}}(\log n)^{\frac{1}{8Md_{0}+6M+16d_{0}+18}}.$ $$

###### Proof.

From [Theorem˜3.1](https://arxiv.org/html/2509.22623v1#S3.Thmtheorem1), we have:

$$ $\displaystyle{\rm TV}(P,\widehat{P})\lesssim\sqrt{M}\exp(M_{u})\sum_{i_{0}\in[d]}\sqrt{\mathcal{R}^{i_{0}}(\widehat{\Theta})}.$ $$

Taking expectation on both sides and recalling that $M_{u}=O(1)$ under mixture setting, we obtain:

$$ $\displaystyle\underset{\{x_{i}\}_{i=1}^{n}}{\mathbb{E}}[\text{TV}(P,\widehat{P})]\lesssim$ $\displaystyle\penalty 10000\ \sqrt{M}\underset{\{x_{i}\}_{i=1}^{n}}{\mathbb{E}}[\sum_{i_{0}\in[d]}\sqrt{\mathcal{R}^{i_{0}}(\widehat{\Theta})}]$ $\displaystyle\lesssim$ $\displaystyle\penalty 10000\ M^{6d_{0}+13}n^{-\frac{1}{8Md_{0}+6M+16d_{0}+18}}(\log n)^{\frac{1}{8Md_{0}+6M+16d_{0}+18}}.$ ( By Theorem F.1 ) $$

This completes the proof.
∎

###### Theorem G.1 (Discrete Flow Matching Distribution Estimation with Transformer, Theorem ˜ 5.2 Restate) .

###### Proof.

### Appendix H Approximation Theory for Discrete Flow Matching: General Case

This section establishes the approximation theory for discrete flow matching in the general case.

Organization.
We recall and restate important lemmas in [Section˜H.1](https://arxiv.org/html/2509.22623v1#A8.SS1).
Then we present the main proof of [Theorem˜H.1](https://arxiv.org/html/2509.22623v1#A8.Thmtheorem1), with same proof strategy in [Theorem˜E.1](https://arxiv.org/html/2509.22623v1#A5.Thmtheorem1).

#### H.1 Auxiliary Lemmas

In this section, we restate auxiliary lemmas for proving the approximation theory [Theorem˜H.1](https://arxiv.org/html/2509.22623v1#A8.Thmtheorem1).
We start with restating [Lemma˜E.2](https://arxiv.org/html/2509.22623v1#A5.Thmlemma2) as [Lemma˜H.1](https://arxiv.org/html/2509.22623v1#A8.Thmlemma1) , computing the Lipschitz constant of $\widetilde{u}(x,t)$ constructed in [Lemma˜4.1](https://arxiv.org/html/2509.22623v1#S4.Thmlemma1).
Then we restate [Lemma˜E.5](https://arxiv.org/html/2509.22623v1#A5.Thmlemma5) as [Lemma˜H.2](https://arxiv.org/html/2509.22623v1#A8.Thmlemma2), a key lemma in proof of [Theorem˜H.1](https://arxiv.org/html/2509.22623v1#A8.Thmtheorem1) bounding function’s local value with its integral’s value lower bound.

To begin with, we restate [Lemma˜E.2](https://arxiv.org/html/2509.22623v1#A5.Thmlemma2) proved in [Section˜E.2](https://arxiv.org/html/2509.22623v1#A5.SS2) as [Lemma˜H.1](https://arxiv.org/html/2509.22623v1#A8.Thmlemma1).
This lemma computes the Lipschitz constant of $\widetilde{u}(x,t)$ in [Lemma˜4.1](https://arxiv.org/html/2509.22623v1#S4.Thmlemma1).

###### Lemma H.1 (Lipschitzness of Extension, Lemma ˜ E.2 Restate) .

Suppose that for every given $s\in\mathcal{S}$, it holds $\|u(s,t)\|_{2}\leq M_{u}$ and $u(s,t)$ is Lipschitz continuous under $\ell_{2}$-norm with respect to $t$, with Lipschitz constant $L_{u}$.
Then $\widetilde{u}(x,t)$ defined in the proof of [Lemma˜4.1](https://arxiv.org/html/2509.22623v1#S4.Thmlemma1) is Lipschitz continuous under $\ell_{2}$-norm with respect to $(x,t)$, with Lipschitz constant $\max\{L_{u},4e\sqrt{d}M_{u}\}$.

###### Proof.

See the proof of [Lemma˜E.2](https://arxiv.org/html/2509.22623v1#A5.Thmlemma2).
∎

Then we restate [Lemma˜E.5](https://arxiv.org/html/2509.22623v1#A5.Thmlemma5) proved in [Section˜E.2](https://arxiv.org/html/2509.22623v1#A5.SS2) as [Lemma˜H.2](https://arxiv.org/html/2509.22623v1#A8.Thmlemma2), bounding local value of Lipschitz continuous function with its integral value.

###### Lemma H.2 (Point-wise Upper Bound via Integral Constraint, Lemma ˜ E.5 Restate) .

Suppose that $f:[-I,I]^{d\times L}\to\mathbb{R}^{d\times L}$ is Lipschitz continuous on a bounded domain under Frobenius norm, with Lipschitz constant $L_{f}$.
Let $n=dL$.
Let $(\int\|f(Z)\|_{F}^{2}\differential Z)^{1/2}\leq b$, then for all $Z\in[-I,I]^{d\times L}$ it holds:

$$ $\displaystyle\|f(Z)\|_{F}\lesssim b^{\frac{2}{n+2}}L_{f}^{\frac{n}{n+2}}.$ $$

###### Proof.

See the proof of [Lemma˜E.5](https://arxiv.org/html/2509.22623v1#A5.Thmlemma5).
∎

###### Lemma H.1 (Lipschitzness of Extension, Lemma ˜ E.2 Restate) .

###### Proof.

###### Lemma H.2 (Point-wise Upper Bound via Integral Constraint, Lemma ˜ E.5 Restate) .

###### Proof.

#### H.2 Approximation Theory for Discrete Flow Matching

In this section, we prove the approximation theorem for discrete flow matching in the general case.
Similar to proof of [Theorem˜E.1](https://arxiv.org/html/2509.22623v1#A5.Thmtheorem1), we treat the upper bound of the Lipschitz constant of the approximator Transformer class as a constant independent of $\epsilon$.

###### Theorem H.1 (Approximation Theorem for Discrete Flow Matching) .

Suppose that for every given $x\in\mathcal{S}$, $u(x,t)$ is bounded and Lipschitz continuous with respect to $t$, such that $\|u(x,t)\|_{2}\leq M_{u}$ and Lipschitz constant is $L_{u}$.
Then for every $\epsilon>0$, there exists a transformer network $u_{\theta}(x,t)\in\mathcal{T}^{h,s,r}_{R}(C_{\mathcal{T}},C^{2,\infty}_{KQ},C_{KQ},C^{2,\infty}_{OV},C_{OV},C_{E},C^{2,\infty}_{F},C_{F})$ satisfying that for every $t\in[0,1]$:

$$ $\displaystyle\sum_{x\in\mathcal{S}}\|u_{\theta}(x,t)-u(x,t)\|^{2}_{2}\cdot p_{t}(x)\lesssim\epsilon^{\frac{4}{M^{d}+2}}M^{\frac{4M^{d}dd_{0}+13M^{d}d+8M^{d}d_{0}+12M^{d}}{M^{d}+2}}M_{u}^{\frac{8M^{d}}{M^{d}+2}},$ $$

where $d_{0}$ is the transformer feature dimension.
The parameter bound of the transformer network class follows:

$$ $\displaystyle\penalty 10000\ C_{KQ},C^{2,\infty}_{KQ}=\widetilde{O}(M^{2dd_{0}+d+4d_{0}+2}\epsilon^{-4d_{0}-2});\quad C_{OV},C^{2,\infty}_{OV}=O(M^{-\frac{1}{2}d}\epsilon)$ $\displaystyle\penalty 10000\ C_{F},C^{2,\infty}_{F}=O(M^{d+1}M_{u}\epsilon^{-1});\quad C_{E}=O(M^{d}),$ $$

where $O(\cdot)$ hides polynomial factors depending on $d,d_{0}$, $\widetilde{O}(\cdot)$ hides polynomial factors depending on $d,d_{0}$ and logarithmic factors depending on $M$.

###### Proof.

Similar to proof of [Theorem˜E.1](https://arxiv.org/html/2509.22623v1#A5.Thmtheorem1), we start with introducing the reshape layer of $u_{\theta}(x,t)$.
In the general case, we need to approximate function $\widetilde{u}^{i}(x,t)$, with input dimension $d+1$ and output dimension $M^{d}$.
To make up for this difference, we introduce two reshape layers: $R_{1}$ and $R_{2}$.
Note that we assume $d+1|M^{d}$ for simplicity in discussions below.

- •
$R_{1}:[0,M]^{d}\times[0,1]\to\mathbb{R}^{d_{0}\times\frac{M^{d}}{d_{0}}}$ is a reshape function rearranging a vector of dimension $d+1$ into a matrix of size $\mathbb{R}^{d_{0}\times\frac{M^{d}}{d_{0}}}$, where transformer feature dimension $d_{0}$ satisfies $d_{0}|d+1$.
We realize $R_{1}$ by first reshaping input vector $(x,t)$ with dimension $d+1$ into a matrix $A\in\mathbb{R}^{d_{0}\times\frac{d+1}{d_{0}}}$, following the standard procedure of rearranging entries.
Then we replicate the matrix $\frac{M^{d}}{d+1}$ times along its columns, yielding a matrix of size $d_{0}\times\frac{M^{d}}{d_{0}}$.
Altogether, the output of $R_{1}$ is a matrix of size $d_{0}\times\frac{M^{d}}{d_{0}}$.
As the reverse of $R_{1}$, $R^{-1}_{1}:\mathbb{R}^{d_{0}\times\frac{M^{d}}{d_{0}}}\to[0,M]^{d}\times[0,1]$ is defined by taking first $\frac{d+1}{d_{0}}$ columns of the matrix, and then rearranging it into a vector of dimension $d+1$.
- •
$R_{2}:\mathbb{R}^{d_{0}\times\frac{M^{d}}{d_{0}}}\to\mathbb{R}^{M^{d}}$ is a reshape function rearranging a matrix of size $\mathbb{R}^{d_{0}\times\frac{M^{d}}{d_{0}}}$ into a vector of dimension $M^{d}$.
We realize $R_{2}$ by rearranging the entries of the matrix into a vector preserving the total number of elements, following standard reshape layer construction.
We define $R_{2}^{-1}$ as the reverse map of $R_{2}$.
This is well-defined since $R_{2}$ is bijection between $\mathbb{R}^{d_{0}\times\frac{M^{d}}{d_{0}}}$ and $\mathbb{R}^{M^{d}}$.

Again, as discussed in proof of [Theorem˜E.1](https://arxiv.org/html/2509.22623v1#A5.Thmtheorem1), we state the construction above for clarity, while the construction of $R_{1}$ and $R_{2}$ is not focus of our discussion.

Now we return to the main proof.
Let $\widetilde{u}(x,t)$ be as defined in [Lemma˜4.1](https://arxiv.org/html/2509.22623v1#S4.Thmlemma1).
Let $u^{\rm reshape}:\mathbb{R}^{d_{0}\times\frac{M^{d}}{d_{0}}}\to\mathbb{R}^{d_{0}\times\frac{M^{d}}{d_{0}}}$ be as:

$$ $\displaystyle u^{\rm reshape}=R_{2}^{-1}\circ\widetilde{u}(x,t)\circ R_{1}^{-1}.$ $$

Then $u^{\rm reshape}$ is Lipschitz continuous under Frobenius norm, with Lipschitz constant no larger than Lipschitz constant of $\widetilde{u}$.
By [Theorem˜B.1](https://arxiv.org/html/2509.22623v1#A2.Thmtheorem1), for any $\epsilon$ there exists a

$$ $\displaystyle u_{\theta}^{\rm reshape}(Z)=F^{\rm FF}_{1}\circ F^{\rm SA}\circ F^{\rm FF}_{2}\circ F^{\rm E}\in\mathcal{T}^{h,s,r}(C_{\mathcal{T}},C^{2,\infty}_{KQ},C_{KQ},C^{2,\infty}_{OV},C_{OV},C_{E},C^{2,\infty}_{F},C_{F}),$ $$

such that $d_{F}(u^{\rm reshape}(Z),u_{\theta}^{\rm reshape}(Z))<\epsilon$, where $d_{F}(f(Z),g(Z)):=(\int\|f(Z)-g(Z)\|^{2}_{F}\differential Z)^{1/2}$.
By [Theorem˜B.2](https://arxiv.org/html/2509.22623v1#A2.Thmtheorem2), the parameter bound of the transformer network satisfies:

$$ $\displaystyle\penalty 10000\ C_{KQ},C^{2,\infty}_{KQ}=\widetilde{O}(M^{2dd_{0}+d+4d_{0}+2}\epsilon^{-4d_{0}-2});C_{OV},C^{2,\infty}_{OV}=O(M^{-\frac{1}{2}d}\epsilon)$ $\displaystyle\penalty 10000\ C_{F},C^{2,\infty}_{F}=O(M^{d+1}M_{u}\epsilon^{-1});C_{E}=O(M^{d}),$ (H.1) $$

where $O(\cdot)$ hides polynomial factors depending on $d,d_{0}$, $\widetilde{O}(\cdot)$ hides polynomial factors depending on $d,d_{0}$ and logarithmic factors depending on $M$.

Let $h=u_{\theta}^{\rm reshape}-u^{\rm reshape}$.
Then $(\int\|h\|_{F}^{2}\differential Z)^{1/2}<\epsilon$.
Further, by [Lemma˜B.7](https://arxiv.org/html/2509.22623v1#A2.Thmlemma7) and [Lemma˜H.1](https://arxiv.org/html/2509.22623v1#A8.Thmlemma1), $u_{\theta}^{\rm reshape},u^{\rm reshape}$ are Lipschitz continuous under Frobenius norm.
Then $h$ is Lipschitz continuous under Frobenius norm.
We denote their Lipschitz constant as $L_{\theta}^{\rm reshape},L^{\rm reshape}$ and $L_{h}$ respectively.

We first compute $L_{\theta}^{\rm reshape}$ according to [Lemma˜B.7](https://arxiv.org/html/2509.22623v1#A2.Thmlemma7).
It holds:

$$ $\displaystyle L_{\theta}^{\rm reshape}\leq$ $\displaystyle\penalty 10000\ (1+2M^{2d}C_{OV}C_{KQ}+h\frac{M^{d}}{d_{0}}C_{OV})\cdot(C_{F}^{2}+1)^{2}$ $\displaystyle\lesssim$ $\displaystyle\penalty 10000\ (C_{F})^{2}\cdot M^{2d}\cdot hC_{KQ}C_{OV}\cdot(C_{F})^{2}$ $\displaystyle\lesssim$ $\displaystyle\penalty 10000\ M^{2dd_{0}+\frac{13}{2}d+4d_{0}+6}M_{u}^{4}.$ ( By ( H.2 ) and dropping terms of $\epsilon$ ) $$

Then we compute $L_{h}$.
We have:

$$ $\displaystyle L_{h}\leq$ $\displaystyle\penalty 10000\ L_{\theta}^{\rm reshape}+L^{\rm reshape}$ $\displaystyle\lesssim$ $\displaystyle\penalty 10000\ M^{2dd_{0}+\frac{13}{2}d+4d_{0}+6}M_{u}^{4}.$ ( By Lemma H.1 ) $$

Let $u_{\theta}:=R_{2}\circ u_{\theta}^{\rm reshape}\circ R_{1}$.
For all $(x,t)\in[0,M]^{d}\times[0,1]$, it holds:

$$ $\displaystyle\|u_{\theta}(x,t)-\widetilde{u}(x,t)\|^{2}_{2}\leq$ $\displaystyle\penalty 10000\ \|u_{\theta}^{\rm reshape}\circ R_{1}(x,t)-u^{\rm reshape}\circ R_{1}(x,t)\|^{2}_{F}$ $\displaystyle=$ $\displaystyle\penalty 10000\ \|h(R_{1}(x,t))\|^{2}_{F}$ ( By definition of $h$ ) $\displaystyle\lesssim$ $\displaystyle\penalty 10000\ \epsilon^{\frac{4}{M^{d}+2}}M^{\frac{4M^{d}dd_{0}+13M^{d}d+8M^{d}d_{0}+12M^{d}}{M^{d}+2}}M_{u}^{\frac{8M^{d}}{M^{d}+2}},$ ( By Lemma H.2 ) $$

where $L_{h}=M^{2dd_{0}+\frac{13}{2}d+4d_{0}+6}M_{u}^{4}$.
Then we have for every $t\in[0,1]$, it holds:

$$ $\displaystyle\sum_{x\in\mathcal{S}}\|u_{\theta}(x,t)-u(x,t)\|^{2}_{2}\cdot p_{t}(x)\lesssim$ $\displaystyle\penalty 10000\ \epsilon^{\frac{4}{M^{d}+2}}M^{\frac{4M^{d}dd_{0}+13M^{d}d+8M^{d}d_{0}+12M^{d}}{M^{d}+2}}M_{u}^{\frac{8M^{d}}{M^{d}+2}}\sum_{x\in\mathcal{S}}p_{t}(x)$ $\displaystyle=$ $\displaystyle\penalty 10000\ \epsilon^{\frac{4}{M^{d}+2}}M^{\frac{4M^{d}dd_{0}+13M^{d}d+8M^{d}d_{0}+12M^{d}}{M^{d}+2}}M_{u}^{\frac{8M^{d}}{M^{d}+2}},$ $$

This completes the proof.
∎

###### Theorem H.1 (Approximation Theorem for Discrete Flow Matching) .

###### Proof.

### Appendix I Estimation theory for Discrete Flow Matching: General Case

This section derives estimation rates for discrete flow matching with transformers in the general case.
The analysis adapts and modifies the risk-decomposition plus covering-number technique of (Fu et al., 2024) to our setting and parameter bounds from [Theorem˜H.1](https://arxiv.org/html/2509.22623v1#A8.Thmtheorem1).

Organization.
This section consists of four steps to obtain the estimation rates of discrete flow matching.
The proof structure follows [Appendix˜F](https://arxiv.org/html/2509.22623v1#A6).

- •
Preliminaries.
In [Section˜I.1](https://arxiv.org/html/2509.22623v1#A9.SS1), we introduce several essential concepts, including empirical loss $\widehat{\mathcal{L}}_{\rm CDFM}$, discrete flow matching risk $\mathcal{R}(\Theta)$ and empirical risk $\widehat{\mathcal{R}}(\Theta)$.
- •
Covering Number Upper bound.
We obtain covering-number bounds for the transformer class using the parameter constraints from [Theorem˜H.1](https://arxiv.org/html/2509.22623v1#A8.Thmtheorem1) and for the induced loss class in [Section˜I.2](https://arxiv.org/html/2509.22623v1#A9.SS2), [Lemma˜I.2](https://arxiv.org/html/2509.22623v1#A9.Thmlemma2)-[Lemma˜I.4](https://arxiv.org/html/2509.22623v1#A9.Thmlemma4).
- •
Generalization and Approximation Error Bound.
We apply the covering-number machinery and conclusions from [Theorem˜H.1](https://arxiv.org/html/2509.22623v1#A8.Thmtheorem1) to bound generalization and approximation error in [Section˜I.2](https://arxiv.org/html/2509.22623v1#A9.SS2), [Lemmas˜I.5](https://arxiv.org/html/2509.22623v1#A9.Thmlemma5) and [I.6](https://arxiv.org/html/2509.22623v1#A9.Thmlemma6).
- •
Estimation rates.
We apply conclusions from prior three steps to prove the velocity estimation rate in [Theorem˜I.1](https://arxiv.org/html/2509.22623v1#A9.Thmtheorem1) and then the distribution estimation rate in [Theorem˜I.2](https://arxiv.org/html/2509.22623v1#A9.Thmtheorem2).

#### I.1 Preliminaries

In practice, given $n$ i.i.d training samples $\{x_{i}\}_{i=1}^{n}$, the transformer network is trained through minimizing the empirical loss:

$$ $\displaystyle\widehat{\mathcal{L}}_{\rm CDFM}:=\frac{1}{n}\sum_{i=1}^{n}\int_{0}^{1}\underset{X_{0}\sim p_{0},X_{t}\sim p_{t|x_{0}=X_{0},x_{1}=x_{i}}}{\mathbb{E}}\|u(X_{t},t)-u_{\theta}(X_{t},t)\|_{2}^{2}\differential t.$ $$

Similar to notations in [Section˜F.1](https://arxiv.org/html/2509.22623v1#A6.SS1), we define the loss of certain function $f$ with respect to some certain point $x$ as:

$$ $\displaystyle\ell(x;f):=\int_{0}^{1}\underset{X_{0}\sim p_{0},X_{t}\sim p_{t|x_{0}=X_{0},x_{1}=x}}{\mathbb{E}}\|u(X_{t},t)-f(X_{t},t)\|_{2}^{2}\differential t.$ $$

Then we have:

$$ $\displaystyle\widehat{\mathcal{L}}_{\rm CDFM}=\frac{1}{n}\sum_{i=1}^{n}\ell(x_{i};u_{\theta}).$ $$

We use $\widehat{\Theta}$ to denote the parameter of network trained by minimizing the empirical loss with $n$ i.i.d training samples $\{x_{i}\}_{i=1}^{n}$.
That’s to say, discrete flow matching network $\widehat{u}_{\theta}$ with parameter $\widehat{\Theta}$ is the empirical risk minimizer, satisfying $\widehat{\Theta}\in\underset{\Theta}{\rm argmin\penalty 10000\ }\widehat{\mathcal{L}}_{\rm CDFM}(u_{\theta})$.

Similar to the factorized case, for a discrete flow matching network $u_{\theta}$ with parameter $\Theta$, its performance in velocity estimation is measured by the discrete flow matching risk, which is defined as:

$$ $\displaystyle\mathcal{R}(\Theta):=\int_{0}^{1}\underset{X_{t}\sim p_{t}}{\mathbb{E}}\|u(X_{t},t)-u_{\theta}(X_{t},t)\|_{2}^{2}\differential t.$ (I.1) $$

In practice, we evaluate the performance of the network $u_{\theta}$ using empirical discrete flow matching risk, which is defined as:

$$ $\displaystyle\widehat{\mathcal{R}}(\Theta):=\frac{1}{n}\sum_{i=1}^{n}\ell(x_{i};u_{\theta})-\frac{1}{n}\sum_{i=1}^{n}\ell(x_{i};u),$ (I.2) $$

where $\{x_{i}\}_{i=1}^{n}$ are n i.i.d samples and $u$ is the true velocity.
We have the following lemma showing that discrete flow matching risk is equal to the expectation of empirical discrete flow matching risk.

###### Lemma I.1 (Modified from Lemma ˜ F.1 ) .

For a discrete flow matching network $u_{\theta}(x,t)$ with parameters noted as $\Theta$ and i.i.d samples $\{x_{i}\}_{i=1}^{n}$, it holds:

$$ $\displaystyle\underset{\{x_{i}\}_{i=1}^{n}}{\mathbb{E}}[\widehat{\mathcal{R}}(\Theta)]=\mathcal{R}(\Theta).$ $$

###### Proof.

See the proof of [Lemma˜F.1](https://arxiv.org/html/2509.22623v1#A6.Thmlemma1).
The only difference is the integration domain in definition of $\ell$ and $\ell^{i^{0}}$, which is modified in the same way on both sides of the equality, from $[t_{0},T]$ to $[0,1]$.
∎

###### Lemma I.1 (Modified from Lemma ˜ F.1 ) .

###### Proof.

#### I.2 Auxiliary Lemmas

To bound $\underset{\{x_{i}\}_{i=1}^{n}}{\mathbb{E}}[\mathcal{R}^{i_{0}}(\widehat{\Theta}^{i_{0}})]$, we take the same decomposition approach introduced in [Section˜F.2](https://arxiv.org/html/2509.22623v1#A6.SS2)
Specifically, we have:

$$ $\displaystyle\underset{\{x_{i}\}_{i=1}^{n}}{\mathbb{E}}[\mathcal{R}(\widehat{\Theta})]=\underbrace{\underset{\{x_{i}\}_{i=1}^{n}}{\mathbb{E}}[\mathcal{R}(\widehat{\Theta})-\widehat{\mathcal{R}}(\widehat{\Theta})]}_{\rm(I)}+\underbrace{\underset{\{x_{i}\}_{i=1}^{n}}{\mathbb{E}}[\widehat{\mathcal{R}}(\widehat{\Theta})]}_{\rm(II)},$ (I.3) $$

In this section, we introduce auxiliary lemmas helping us prove [Theorem˜I.1](https://arxiv.org/html/2509.22623v1#A9.Thmtheorem1).
Specifically, we derive the covering number bound of transformers in [Lemma˜I.2](https://arxiv.org/html/2509.22623v1#A9.Thmlemma2) and [Lemma˜I.3](https://arxiv.org/html/2509.22623v1#A9.Thmlemma3).
Then we get the covering number of loss function class in [Lemma˜I.4](https://arxiv.org/html/2509.22623v1#A9.Thmlemma4).
[Lemma˜I.5](https://arxiv.org/html/2509.22623v1#A9.Thmlemma5) gives an upper bound on (I), the generalization bound.
Finally, [Lemma˜I.6](https://arxiv.org/html/2509.22623v1#A9.Thmlemma6) bound the empirical risk of a trained network.

To start with, we restate [Lemma˜F.2](https://arxiv.org/html/2509.22623v1#A6.Thmlemma2) as [Lemma˜I.2](https://arxiv.org/html/2509.22623v1#A9.Thmlemma2), giving an upper bound on the covering number of multiple-layer transformer network.

###### Lemma I.2 ( Lemma ˜ F.2 Restate, Lemma J.2 of (Hu et al., 2024b ) , Modified from Theorem A.17 of (Edelman et al., 2022 ) ) .

Let $\mathcal{T}^{h,s,r}_{R}(C_{\mathcal{T}},C^{2,\infty}_{KQ},C_{KQ},C^{2,\infty}_{OV},C_{OV},C_{E},C^{2,\infty}_{F},C_{F},L_{\mathcal{T}})$ represent the class of transformer network with parameter bound.
Then for data points $x$ such that $\|x\|_{2}\leq B_{X}$, we have:

$$ $\displaystyle\penalty 10000\ \log\mathcal{N}(\mathcal{T}^{h,s,r}_{R},\epsilon,n,\|\cdot\|_{2})$ $\displaystyle\leq$ $\displaystyle\penalty 10000\ \frac{\log(nL_{\mathcal{T}})}{\epsilon^{2}}\alpha^{2}(d_{0}^{\frac{2}{3}}(C_{F}^{2,\infty})^{\frac{2}{3}}+d_{0}^{\frac{2}{3}}(2(C_{F})^{2}C_{OV}C_{KQ}^{2,\infty})^{\frac{2}{3}}+2((C_{F})^{2}C_{OV}^{2,\infty})^{\frac{2}{3}})^{3},$ $$

where $\alpha=(C_{F})^{2}C_{OV}(1+4C_{KQ})(B_{X}+C_{E})$.

###### Proof.

See the proof of [Lemma˜F.2](https://arxiv.org/html/2509.22623v1#A6.Thmlemma2).
∎

Equipped with [Lemma˜I.2](https://arxiv.org/html/2509.22623v1#A9.Thmlemma2), we now compute the covering number of transformer network class with parameter bound given in [Theorem˜H.1](https://arxiv.org/html/2509.22623v1#A8.Thmtheorem1).

###### Lemma I.3 (Covering Number Bound for Transformer Class, Modified from Lemma ˜ F.3 ) .

Let $\epsilon_{c}>0$.
Consider the transformer class $\mathcal{T}^{h,s,r}_{R}(C_{\mathcal{T}},C^{2,\infty}_{KQ},C_{KQ},C^{2,\infty}_{OV},C_{OV},C_{E},C^{2,\infty}_{F},C_{F})$ with parameter bound given in [Theorem˜H.1](https://arxiv.org/html/2509.22623v1#A8.Thmtheorem1) and $x_{i}$ satisfying $x_{i}\in\mathcal{S}$.
Then the $\epsilon_{c}$-covering number of $\mathcal{T}^{h,s,r}_{R}$ satisfies:

$$ $\displaystyle\log\mathcal{N}(\mathcal{T}^{h,s,r}_{R},\epsilon_{c},n,\|\cdot\|_{2})\lesssim\frac{\log(nMM_{u}\epsilon)}{\epsilon_{c}^{2}}M^{8dd_{0}+12d+16d_{0}+16}M_{u}^{8}\epsilon^{-16d_{0}-12}.$ $$

###### Proof.

The proof is modified from the proof of [Lemma˜F.3](https://arxiv.org/html/2509.22623v1#A6.Thmlemma3).

From [Theorem˜H.1](https://arxiv.org/html/2509.22623v1#A8.Thmtheorem1), we have:

$$ $\displaystyle\penalty 10000\ C_{KQ},C^{2,\infty}_{KQ}=\widetilde{O}(M^{2dd_{0}+d+4d_{0}+2}\epsilon^{-4d_{0}-2});C_{OV},C^{2,\infty}_{OV}=O(M^{-\frac{1}{2}d}\epsilon)$ $\displaystyle\penalty 10000\ C_{F},C^{2,\infty}_{F}=O(M^{d+1}M_{u}\epsilon^{-1});C_{E}=O(M^{d});L_{\mathcal{T}}=O(M^{2dd_{0}+\frac{13}{2}d+4d_{0}+6}M_{u}^{4}).$ (I.4) $$

Then we substitute ([I.2](https://arxiv.org/html/2509.22623v1#A9.Ex8)) into [Lemma˜I.2](https://arxiv.org/html/2509.22623v1#A9.Thmlemma2) and get:

$$ $\displaystyle\alpha\lesssim M^{2d+2}M_{u}^{2}\epsilon^{-2}\cdot M^{-\frac{1}{2}d}\epsilon\cdot M^{2dd_{0}+d+4d_{0}+2}\epsilon^{-4d_{0}-2}\cdot M^{d}=M^{2dd_{0}+\frac{7}{2}d+4d_{0}+4}M_{u}^{2}\epsilon^{-4d_{0}-3}.$ $$

Through further computation, we have

$$ $\displaystyle\penalty 10000\ \log\mathcal{N}(\mathcal{T}^{h,s,r}_{R},\epsilon_{c},n,\|\cdot\|_{2})$ $\displaystyle\lesssim$ $\displaystyle\penalty 10000\ \frac{\log(nL_{\mathcal{T}})}{\epsilon_{c}^{2}}\alpha^{2}(d_{0}^{\frac{2}{3}}(2(C_{F})^{2}C_{OV}C_{KQ}^{2,\infty})^{\frac{2}{3}})^{3}$ $\displaystyle\lesssim$ $\displaystyle\penalty 10000\ \frac{\log(nMM_{u})}{\epsilon_{c}^{2}}M^{8dd_{0}+12d+16d_{0}+16}M_{u}^{8}\epsilon^{-16d_{0}-12}.$ $$

This completes the proof.
∎

Then we compute the covering number of loss function class with [Lemma˜I.3](https://arxiv.org/html/2509.22623v1#A9.Thmlemma3), using the same approach as in [Lemma˜F.4](https://arxiv.org/html/2509.22623v1#A6.Thmlemma4).

###### Lemma I.4 (Covering Number Bound for Loss Function Class, Modified from Lemma ˜ F.4 ) .

Let $\epsilon_{c}>0$.
Suppose that for every given $x\in\mathcal{S}$, $u(x,t)$ is bounded and Lipschitz continuous with respect to $t$, such that $\|u(x,t)\|_{2}\leq M_{u}$ and Lipschitz constant is $L_{u}$.
We define the loss function class by

$$ $\displaystyle F_{\rm loss}:=\{\ell(x;u_{\theta})|u_{\theta}\in\mathcal{T}^{h,s,r}_{R}\},$ $$

where $\mathcal{T}^{h,s,r}_{R}$ is the transformer class with parameter bound given in [Theorem˜H.1](https://arxiv.org/html/2509.22623v1#A8.Thmtheorem1).
Then we have:

$$ $\displaystyle\log\mathcal{N}(F_{\rm loss},\epsilon_{c},\{x_{i}\}_{x_{i}\in\mathcal{S}},|\cdot|)\lesssim\frac{\log(MM_{u})-\log(\epsilon_{c})}{\epsilon_{c}^{2}}M^{8dd_{0}+12d+16d_{0}+16}M_{u}^{10}\epsilon^{-16d_{0}-12}.$ $$

###### Proof.

The proof is modified from the proof of [Lemma˜F.4](https://arxiv.org/html/2509.22623v1#A6.Thmlemma4).

Consider $\{x_{i}\}_{i=1}^{n}\in\mathcal{S}$ and function $u_{1}(x,t),u_{2}(x,t)$ satisfying $\|u_{1}(x,t)-u_{2}(x,t)\|\leq\delta$ for all $x\in\mathcal{S}$ and $t=0,\frac{1}{\lceil\frac{L_{\mathcal{T}}}{\delta}\rceil},\frac{2}{\lceil\frac{L_{\mathcal{T}}}{\delta}\rceil},\dots,1$.
Then since $u_{1}$ and $u_{2}$ is Lipschitz continuous with Lipschitz constant $L_{\mathcal{T}}$ under $\ell_{2}$-norm, for $x\in\mathcal{S}$ and $t\in[0,1]$ we have $\|u_{1}(x,t)-u_{2}(x,t)\|\leq 2\delta$.

Further, for $x=x_{i},1\leq i\leq n$ we have:

$$ $\displaystyle\penalty 10000\ |\ell(x;u_{1})-\ell(x;u_{2})|$ $\displaystyle=$ $\displaystyle\penalty 10000\ |\int_{0}^{1}\underset{X_{0}\sim p_{0},X_{t}\sim p_{t|x_{0}=X_{0},x_{1}=x}}{\mathbb{E}}(\|u_{1}(X_{t},t)-u(X_{t},t)\|_{2}^{2}-\|u_{2}(X_{t},t)-u(X_{t},t)\|_{2}^{2})\differential t|$ ( By definition of $\ell$ ) $\displaystyle=$ $\displaystyle\penalty 10000\ |\int_{0}^{1}\underset{X_{0}\sim p_{0},X_{t}\sim p_{t|x_{0}=X_{0},x_{1}=x}}{\mathbb{E}}(u_{1}(X_{t},t)-u_{2}(X_{t},t))^{\top}(u_{1}(X_{t},t)+u_{2}(X_{t},t)-2u(X_{t},t)))\differential t|$ $\displaystyle\leq$ $\displaystyle\penalty 10000\ 2\delta\int_{0}^{1}\underset{X_{0}\sim p_{0},X_{t}\sim p_{t|x_{0}=X_{0},x_{1}=x}}{\mathbb{E}}\|u_{1}(X_{t},t)+u_{2}(X_{t},t)-2u(X_{t},t)\|_{2}\differential t$ $\displaystyle\leq$ $\displaystyle\penalty 10000\ 8\delta C_{\mathcal{T}},$ $$

where the third line is by $\|u_{1}-u_{2}\|_{2}\leq 2\delta$, and the last line is by assuming $C_{\mathcal{T}}\geq M_{u}$ without losing generality.
Therefore, suppose $\mathcal{U}$ is a $\epsilon_{c}$-covering of $\mathcal{T}^{h,s,r}_{R}$ with respect to point set $S$, function class $\mathcal{L}=\{\ell(x;u)|u\in\mathcal{U}\}$ is a $4\epsilon_{c}C_{\mathcal{T}}$-covering of $F_{\rm loss}$.
Then we get:

$$ $\displaystyle\log\mathcal{N}(F_{\rm loss},\epsilon_{c},\{x_{i}\}_{x_{i}\in\mathcal{S}},|\cdot|)\leq$ $\displaystyle\penalty 10000\ \log\mathcal{N}(\mathcal{T}^{h,s,r}_{R},\frac{\epsilon_{c}}{8C_{\mathcal{T}}},M^{d}(\lceil\frac{L_{\mathcal{T}}}{\epsilon_{c}}\rceil+1),|\cdot|)$ $\displaystyle\lesssim$ $\displaystyle\penalty 10000\ \frac{\log(MM_{u})-\log(\epsilon_{c})}{\epsilon_{c}^{2}}C_{\mathcal{T}}^{2}M^{8dd_{0}+12d+16d_{0}+16}M_{u}^{8}\epsilon^{-16d_{0}-12}$ ( By Lemma I.3 ) $\displaystyle\lesssim$ $\displaystyle\penalty 10000\ \frac{\log(MM_{u})-\log(\epsilon_{c})}{\epsilon_{c}^{2}}M^{8dd_{0}+12d+16d_{0}+16}M_{u}^{10}\epsilon^{-16d_{0}-12}.$ ( $C_{\mathcal{T}}=O(M_{u})$ ) $$

This completes the proof.
∎

We now bound (I) with the concept of covering number.

###### Lemma I.5 (Generalization Bound, Modified from Lemma ˜ F.5 ) .

Let $\widehat{u}_{\theta}$ with parameter $\widehat{\Theta}$ be the velocity estimator trained by minimizing $\widehat{\mathcal{L}}_{\rm CDFM}$ with i.i.d training samples $\{x_{i}\}_{i=1}^{n}$, where $x_{i}\in\mathcal{S}$.
For simplicity, we use $\mathcal{N}$ to denote $\mathcal{N}(F_{\rm loss},\epsilon_{c},\{x_{i}\}_{x_{i}\in\mathcal{S}},|\cdot|)$.
Then we bound (I), the generalization bound as:

$$ $\displaystyle\underset{\{x_{i}\}_{i=1}^{n}}{\mathbb{E}}[\mathcal{R}(\widehat{\Theta})-\widehat{\mathcal{R}}(\widehat{\Theta})]\lesssim\underset{\{x_{i}\}_{i=1}^{n}}{\mathbb{E}}[\widehat{\mathcal{R}}(\widehat{\Theta})]+O(\frac{\kappa}{n}\log\mathcal{N}+\epsilon_{c}),$ $$

where $\kappa$ denote the upper bound of $\ell(x;u_{\theta})$.

###### Proof.

See the proof of [Lemma˜F.5](https://arxiv.org/html/2509.22623v1#A6.Thmlemma5).
Differences in notations do not influence the conclusion.
∎

The next lemma bounds (II) with the approximation theory [Theorem˜H.1](https://arxiv.org/html/2509.22623v1#A8.Thmtheorem1).

###### Lemma I.6 (Empirical Risk Bound, Modified from Lemma ˜ F.6 ) .

Consider the transformer class $\mathcal{T}^{h,s,r}_{R}$ with parameter bound given in [Theorem˜H.1](https://arxiv.org/html/2509.22623v1#A8.Thmtheorem1).
Let $\widehat{u}_{\theta}\in\mathcal{T}^{h,s,r}_{R}$ with parameter $\widehat{\Theta}$ be the velocity estimator trained by minimizing $\widehat{\mathcal{L}}_{\rm CDFM}$ with i.i.d training samples $\{x_{i}\}_{i=1}^{n}$, where $x_{i}\in\mathcal{S}$.
Let empirical risk $\widehat{\mathcal{R}}(\widehat{\Theta})$ be as defined in ([I.2](https://arxiv.org/html/2509.22623v1#A9.E2)).
Then we have:

$$ $\displaystyle\underset{\{x_{i}\}_{i=1}^{n}}{\mathbb{E}}[\widehat{\mathcal{R}}(\widehat{\Theta})]\lesssim\epsilon^{\frac{4}{M^{d}+2}}M^{\frac{4M^{d}dd_{0}+13M^{d}d+8M^{d}d_{0}+12M^{d}}{M^{d}+2}}M_{u}^{\frac{8M^{d}}{M^{d}+2}}.$ $$

###### Proof.

See the proof of [Lemma˜F.6](https://arxiv.org/html/2509.22623v1#A6.Thmlemma6).
The only difference is using the approximation error given in [Theorem˜H.1](https://arxiv.org/html/2509.22623v1#A8.Thmtheorem1) instead of the approximation error given in [Theorem˜4.1](https://arxiv.org/html/2509.22623v1#S4.Thmtheorem1) in proof.
∎

###### Lemma I.2 ( Lemma ˜ F.2 Restate, Lemma J.2 of (Hu et al., 2024b ) , Modified from Theorem A.17 of (Edelman et al., 2022 ) ) .

###### Proof.

###### Lemma I.3 (Covering Number Bound for Transformer Class, Modified from Lemma ˜ F.3 ) .

###### Proof.

###### Lemma I.4 (Covering Number Bound for Loss Function Class, Modified from Lemma ˜ F.4 ) .

###### Proof.

###### Lemma I.5 (Generalization Bound, Modified from Lemma ˜ F.5 ) .

###### Proof.

###### Lemma I.6 (Empirical Risk Bound, Modified from Lemma ˜ F.6 ) .

###### Proof.

#### I.3 Estimation Rates for Discrete Flow Matching

In this section, we derive the estimation error bounds for discrete flow matching in general case.

###### Theorem I.1 (Discrete Flow Matching Velocity Estimation with Transformer) .

Let $\widehat{u}_{\theta}$ with parameter $\widehat{\Theta}$ be the velocity estimator trained by minimizing empirical conditional discrete flow matching loss $\widehat{\mathcal{L}}_{\rm CDFM}$ with i.i.d training samples $\{x_{i}\}_{i=1}^{n}$, where $x_{i}\in\mathcal{S}$.
Suppose that for every given $x_{i}\in\mathcal{S}$, $u(x_{i},t)$ is bounded , such that $\|u(x_{i},t)\|_{2}\leq M_{u}$.
Moreover, for every given $x_{i}\in\mathcal{S}$ $u(x_{i},t)$ is Lipschitz continuous with respect to $t$.
Then for large enough $n$ we have:

$$ $\displaystyle\underset{\{x_{i}\}_{i=1}^{n}}{\mathbb{E}}[\mathcal{R}(\widehat{\Theta})]\lesssim M_{u}^{8}M^{4dd_{0}+12d+8d_{0}+12}n^{-\frac{1}{4M^{d}d_{0}+3M^{d}+8d_{0}+9}}(\log n)^{\frac{1}{4M^{d}d_{0}+3M^{d}+8d_{0}+9}}.$ $$

###### Proof.

Recall the decomposition given in ([I.3](https://arxiv.org/html/2509.22623v1#A9.E3)):

$$ $\displaystyle\underset{\{x_{i}\}_{i=1}^{n}}{\mathbb{E}}[\mathcal{R}(\widehat{\Theta})]=\underset{\{x_{i}\}_{i=1}^{n}}{\mathbb{E}}[\mathcal{R}(\widehat{\Theta})-\widehat{\mathcal{R}}(\widehat{\Theta})]+\underset{\{x_{i}\}_{i=1}^{n}}{\mathbb{E}}[\widehat{\mathcal{R}}(\widehat{\Theta})].$ $$

Substituting the result of [Lemma˜I.5](https://arxiv.org/html/2509.22623v1#A9.Thmlemma5) and [Lemma˜I.6](https://arxiv.org/html/2509.22623v1#A9.Thmlemma6) into the decomposition, we get:

$$ $\displaystyle\underset{\{x_{i}\}_{i=1}^{n}}{\mathbb{E}}[\mathcal{R}(\widehat{\Theta})]\lesssim$ $\displaystyle\penalty 10000\ O(\frac{\kappa}{n}\log\mathcal{N}+\epsilon_{c})+2\underset{\{x_{i}\}_{i=1}^{n}}{\mathbb{E}}[\widehat{\mathcal{R}}(\widehat{\Theta})]$ ( By Lemma I.5 ) $\displaystyle\lesssim$ $\displaystyle\penalty 10000\ O(\frac{\kappa}{n}\log\mathcal{N}+\epsilon_{c})+\epsilon^{\frac{4}{M^{d}+2}}M^{\frac{4M^{d}dd_{0}+13M^{d}d+8M^{d}d_{0}+12M^{d}}{M^{d}+2}}M_{u}^{\frac{8M^{d}}{M^{d}+2}}$ ( By Lemma I.6 ) $\displaystyle\lesssim$ $\displaystyle\penalty 10000\ \frac{\log(MM_{u}\epsilon)-\log(\epsilon_{c})}{n\epsilon_{c}^{2}}M^{8dd_{0}+12d+16d_{0}+16}M_{u}^{12}\epsilon^{-16d_{0}-12}$ $\displaystyle\penalty 10000\ +\epsilon_{c}+\epsilon^{\frac{4}{M^{d}+2}}M^{\frac{4M^{d}dd_{0}+13M^{d}d+8M^{d}d_{0}+12M^{d}}{M^{d}+2}}M_{u}^{\frac{8M^{d}}{M^{d}+2}}.$ ( By Lemma I.4 and $\kappa\lesssim M_{u}^{2}$ ) $$

We then choose $\epsilon$ and $\epsilon_{c}$ to get an optimal estimation.

First, let $\epsilon_{c}=(\frac{\log(n\epsilon)M^{8dd_{0}+12d+16d_{0}+16}M_{u}^{12}\epsilon^{-16d_{0}-12}}{n})^{1/3}$ and we obtain:

$$ $\displaystyle\underset{\{x_{i}\}_{i=1}^{n}}{\mathbb{E}}[\mathcal{R}(\widehat{\Theta})]\lesssim$ $\displaystyle\penalty 10000\ (\log(n\epsilon))^{1/3}M_{u}^{4}M^{\frac{8dd_{0}+12d+16d_{0}+16}{3}}\epsilon^{-\frac{16d_{0}+12}{3}}n^{-\frac{1}{3}}$ $\displaystyle\penalty 10000\ +\epsilon^{\frac{4}{M^{d}+2}}M^{\frac{4M^{d}dd_{0}+13M^{d}d+8M^{d}d_{0}+12M^{d}}{M^{d}+2}}M_{u}^{\frac{8M^{d}}{M^{d}+2}}.$ $$

Next, let $\epsilon=M^{-\frac{1}{4}d+1}n^{-\frac{M^{d}+2}{16M^{d}d_{0}+12M^{d}+32d_{0}+36}}(\log n)^{\frac{M^{d}+2}{16M^{d}d_{0}+12M^{d}+32d_{0}+36}}$, then for large enough $n$ we get:

$$ $\displaystyle\underset{\{x_{i}\}_{i=1}^{n}}{\mathbb{E}}[\mathcal{R}(\widehat{\Theta})]\lesssim M_{u}^{8}M^{4dd_{0}+12d+8d_{0}+12}n^{-\frac{1}{4M^{d}d_{0}+3M^{d}+8d_{0}+9}}(\log n)^{\frac{1}{4M^{d}d_{0}+3M^{d}+8d_{0}+9}}.$ $$

This completes the proof.
∎

###### Theorem I.1 (Discrete Flow Matching Velocity Estimation with Transformer) .

###### Proof.

#### I.4 Discrete Flow Matching Distribution Estimation

Finally, we present the distribution estimation rate for discrete flow matching in general case.

###### Theorem I.2 (Discrete Flow Matching Distribution Estimation Rates) .

Let $\widehat{u}_{\theta}$ with parameter $\widehat{\Theta}$ be the velocity estimator trained by minimizing empirical conditional discrete flow matching loss $\widehat{\mathcal{L}}_{\rm CDFM}$ in [Theorem˜I.1](https://arxiv.org/html/2509.22623v1#A9.Thmtheorem1).
Let $P$ stand for the true distribution and $\widehat{P}$ stand for the generated distribution with discrete flow matching network $\widehat{u}_{\theta}$.
Then we have:

$$ $\displaystyle\underset{\{x_{i}\}_{i=1}^{n}}{\mathbb{E}}[\text{TV}(P,\widehat{P})]\lesssim M_{u}^{4}\exp(M_{u}M^{d})M^{2dd_{0}+\frac{13}{2}d+4d_{0}+6}n^{-\frac{1}{8M^{d}d_{0}+6M^{d}+16d_{0}+18}}(\log n)^{\frac{1}{8M^{d}d_{0}+6M^{d}+16d_{0}+18}}.$ $$

###### Proof.

Following [Theorem˜C.1](https://arxiv.org/html/2509.22623v1#A3.Thmtheorem1), we have:

$$ $\displaystyle\text{TV}(P,\widehat{P})\lesssim\exp(M_{u})M^{\frac{d}{2}}\sqrt{\mathcal{R}(\Theta)}.$ $$

We then take expectations at both sides and apply the velocity estimation rate ([Theorem˜I.1](https://arxiv.org/html/2509.22623v1#A9.Thmtheorem1)),

$$ $\displaystyle\underset{\{x_{i}\}_{i=1}^{n}}{\mathbb{E}}[\text{TV}(P,\widehat{P})]\lesssim$ $\displaystyle\penalty 10000\ \exp(M_{u})M^{\frac{d}{2}}\underset{\{x_{i}\}_{i=1}^{n}}{\mathbb{E}}[\sqrt{\mathcal{R}(\Theta)}]$ $\displaystyle\lesssim$ $\displaystyle\penalty 10000\ M_{u}^{4}\exp(M_{u})M^{2dd_{0}+\frac{13}{2}d+4d_{0}+6}n^{-\frac{1}{8M^{d}d_{0}+6M^{d}+16d_{0}+18}}(\log n)^{\frac{1}{8M^{d}d_{0}+6M^{d}+16d_{0}+18}}.$ ( By Theorem I.1 ) $$

This completes the proof.
∎

###### Theorem I.2 (Discrete Flow Matching Distribution Estimation Rates) .

###### Proof.

### References

- Achiam et al. [2023]
Josh Achiam, Steven Adler, Sandhini Agarwal, Lama Ahmad, Ilge Akkaya, Florencia Leoni Aleman, Diogo Almeida, Janko Altenschmidt, Sam Altman, Shyamal Anadkat, et al.
Gpt-4 technical report.
*arXiv preprint arXiv:2303.08774*, 2023.
- Alberti et al. [2023]
Silas Alberti, Niclas Dern, Laura Thesing, and Gitta Kutyniok.
Sumformer: Universal approximation for efficient transformers.
In *Topological, Algebraic and Geometric Learning Workshops 2023*, pages 72–86. PMLR, 2023.
- Austin et al. [2021]
Jacob Austin, Daniel D Johnson, Jonathan Ho, Daniel Tarlow, and Rianne Van Den Berg.
Structured denoising diffusion models in discrete state-spaces.
*Advances in neural information processing systems*, 34:17981–17993, 2021.
- Benton et al. [2023]
Joe Benton, George Deligiannidis, and Arnaud Doucet.
Error bounds for flow matching methods.
*arXiv preprint arXiv:2305.16860*, 2023.
- Campbell et al. [2022]
Andrew Campbell, Joe Benton, Valentin De Bortoli, Thomas Rainforth, George Deligiannidis, and Arnaud Doucet.
A continuous time framework for discrete denoising models.
*Advances in Neural Information Processing Systems*, 35:28266–28279, 2022.
- Campbell et al. [2024]
Andrew Campbell, Jason Yim, Regina Barzilay, Tom Rainforth, and Tommi Jaakkola.
Generative flows on discrete state-spaces: Enabling multimodal flows with applications to protein co-design.
*arXiv preprint arXiv:2402.04997*, 2024.
- Castin et al. [2024]
Valérie Castin, Pierre Ablin, and Gabriel Peyré.
How smooth is attention?, 2024.
URL [https://arxiv.org/abs/2312.14820](https://arxiv.org/abs/2312.14820).
- Davis et al. [2024]
Oscar Davis, Samuel Kessler, Mircea Petrache, Ismail Ceylan, Michael Bronstein, and Joey Bose.
Fisher flow matching for generative modeling over discrete data.
*Advances in Neural Information Processing Systems*, 37:139054–139084, 2024.
- Dieleman et al. [2022]
Sander Dieleman, Laurent Sartran, Arman Roshannai, Nikolay Savinov, Yaroslav Ganin, Pierre H Richemond, Arnaud Doucet, Robin Strudel, Chris Dyer, Conor Durkan, et al.
Continuous diffusion for categorical data.
*arXiv preprint arXiv:2211.15089*, 2022.
- Edelman et al. [2022]
Benjamin L Edelman, Surbhi Goel, Sham Kakade, and Cyril Zhang.
Inductive biases and variable creation in self-attention mechanisms.
In *International Conference on Machine Learning*, pages 5793–5831. PMLR, 2022.
- Fu et al. [2024]
Hengyu Fu, Zhuoran Yang, Mengdi Wang, and Minshuo Chen.
Unveil conditional diffusion models with classifier-free guidance: A sharp statistical theory.
*arXiv preprint arXiv:2403.11968*, 2024.
- Fuest et al. [2025]
Michael Fuest, Vincent Tao Hu, and Björn Ommer.
Maskflow: Discrete flows for flexible and efficient long video generation.
*arXiv preprint arXiv:2502.11234*, 2025.
- Fukumizu et al. [2024]
Kenji Fukumizu, Taiji Suzuki, Noboru Isobe, Kazusato Oko, and Masanori Koyama.
Flow matching achieves almost minimax optimal convergence.
*arXiv preprint arXiv:2405.20879*, 2024.
- Gat et al. [2024]
Itai Gat, Tal Remez, Neta Shaul, Felix Kreuk, Ricky TQ Chen, Gabriel Synnaeve, Yossi Adi, and Yaron Lipman.
Discrete flow matching.
*Advances in Neural Information Processing Systems*, 37:133345–133385, 2024.
- Gronwall [1919]
Thomas Hakon Gronwall.
Note on the derivatives with respect to a parameter of the solutions of a system of differential equations.
*Annals of Mathematics*, 20(4):292–296, 1919.
- Hoogeboom et al. [2021]
Emiel Hoogeboom, Didrik Nielsen, Priyank Jaini, Patrick Forré, and Max Welling.
Argmax flows and multinomial diffusion: Learning categorical distributions.
*Advances in neural information processing systems*, 34:12454–12465, 2021.
- Hu et al. [2024a]
Jerry Yao-Chieh Hu, Wei-Po Wang, Ammar Gilani, Chenyang Li, Zhao Song, and Han Liu.
Fundamental limits of prompt tuning transformers: Universality, capacity and efficiency.
*arXiv preprint arXiv:2411.16525*, 2024a.
- Hu et al. [2024b]
Jerry Yao-Chieh Hu, Weimin Wu, Yi-Chen Lee, Yu-Chao Huang, Minshuo Chen, and Han Liu.
On statistical rates of conditional diffusion transformers: Approximation, estimation and minimax optimality.
*arXiv preprint arXiv:2411.17522*, 2024b.
- Hu and Ommer [2024]
Vincent Tao Hu and Björn Ommer.
[mask] is all you need.
*arXiv preprint arXiv:2412.06787*, 2024.
- Ingraham et al. [2019]
John Ingraham, Vikas Garg, Regina Barzilay, and Tommi Jaakkola.
Generative models for graph-based protein design.
*Advances in neural information processing systems*, 32, 2019.
- Jiao et al. [2024]
Yuling Jiao, Yanming Lai, Yang Wang, and Bokai Yan.
Convergence analysis of flow matching in latent space with transformers.
*arXiv preprint arXiv:2404.02538*, 2024.
- Kajitsuka and Sato [2023]
Tokio Kajitsuka and Issei Sato.
Are transformers with one layer self-attention using low-rank weight matrices universal approximators?
*arXiv preprint arXiv:2307.14023*, 2023.
- Lipman et al. [2024]
Yaron Lipman, Marton Havasi, Peter Holderrieth, Neta Shaul, Matt Le, Brian Karrer, Ricky TQ Chen, David Lopez-Paz, Heli Ben-Hamu, and Itai Gat.
Flow matching guide and code.
*arXiv preprint arXiv:2412.06264*, 2024.
- Liu et al. [2024]
Aixin Liu, Bei Feng, Bing Xue, Bingxuan Wang, Bochao Wu, Chengda Lu, Chenggang Zhao, Chengqi Deng, Chenyu Zhang, Chong Ruan, et al.
Deepseek-v3 technical report.
*arXiv preprint arXiv:2412.19437*, 2024.
- Lou et al. [2023]
Aaron Lou, Chenlin Meng, and Stefano Ermon.
Discrete diffusion modeling by estimating the ratios of the data distribution.
*arXiv preprint arXiv:2310.16834*, 2023.
- Norris [1998]
James R Norris.
*Markov chains*.
Number 2. Cambridge university press, 1998.
- Peebles and Xie [2023]
William Peebles and Saining Xie.
Scalable diffusion models with transformers.
In *Proceedings of the IEEE/CVF international conference on computer vision*, pages 4195–4205, 2023.
- Qin et al. [2024]
Yiming Qin, Manuel Madeira, Dorina Thanou, and Pascal Frossard.
Defog: Discrete flow matching for graph generation.
*arXiv preprint arXiv:2410.04263*, 2024.
- Sohl-Dickstein et al. [2015]
Jascha Sohl-Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli.
Deep unsupervised learning using nonequilibrium thermodynamics.
In *International conference on machine learning*, pages 2256–2265. pmlr, 2015.
- Su et al. [2025]
Maojiang Su, Jerry Yao-Chieh Hu, Yi-Chen Lee, Ning Zhu, Jui-Hui Chung, Shang Wu, Zhao Song, Minshuo Chen, and Han Liu.
High-order flow matching: Unified framework and sharp statistical rates.
In *Proceedings of the 39th Conference on Neural Information Processing Systems (NeurIPS)*, 2025.
- Tachikawa [2020]
Yuji Tachikawa.
On gauging finite subgroups.
*SciPost Physics*, 8(1):015, 2020.
- Vaswani et al. [2017]
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Łukasz Kaiser, and Illia Polosukhin.
Attention is all you need.
*Advances in neural information processing systems*, 30, 2017.
- Vignac et al. [2022]
Clement Vignac, Igor Krawczuk, Antoine Siraudin, Bohan Wang, Volkan Cevher, and Pascal Frossard.
Digress: Discrete denoising diffusion for graph generation.
*arXiv preprint arXiv:2209.14734*, 2022.
- Yang et al. [2023]
Dongchao Yang, Jianwei Yu, Helin Wang, Wen Wang, Chao Weng, Yuexian Zou, and Dong Yu.
Diffsound: Discrete diffusion model for text-to-sound generation.
*IEEE/ACM Transactions on Audio, Speech, and Language Processing*, 31:1720–1733, 2023.
- Yi et al. [2025]
Kai Yi, Kiarash Jamali, and Sjors HW Scheres.
All-atom inverse protein folding through discrete flow matching.
*arXiv preprint arXiv:2507.14156*, 2025.
- Yun et al. [2019]
Chulhee Yun, Srinadh Bhojanapalli, Ankit Singh Rawat, Sashank J Reddi, and Sanjiv Kumar.
Are transformers universal approximators of sequence-to-sequence functions?
*arXiv preprint arXiv:1912.10077*, 2019.

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 4
presentation: 3
questions: 1. In the original discrete flow matching, the training loss uses cross-entropy terms (see Eq. (28) in Gat et al, 2024). Is it equivalent to the loss term in Eq. (2.10) by using the $\ell_2$-norm in Bregmann divergence? 

2. Does using different form of Bregmann divergence affect the results? 

3. In Theorem 3.1, is $T = 1$? How big is $t_0$? 

4. Is it possible to show some empirical evidence of the scaling behavior (e.g., $M$, $n$, or $d_0$) on some toy data?
soundness: 3
strengths: The paper is well written. To my knowledge this is the first formal proof of convergence for DFM. It provides a valuable theoretical contribution to the growing area of discrete generative modeling and flow‐matching methods. They decompose the errors for learning the probability velocity into the approximation error (due to model architecture) and the estimation error (due to the sample size), assuming that training is done ideally.
summary: This paper provides a theoretical analysis of end‐to‐end training of DFM models. They bound the distance between the generated distribution and the true data distribution by the risk of the learned probability velocity. Then this risk is analyzed through two sources: approximation and estimation errors. The approximation error is determined by the capacity of the transformer, and the estimate error is due to the training on a finite dataset. 

The paper provides theoretical justification (for the first time in discrete flow‐matching) that model error can be controlled and that convergence is guaranteed under ideal conditions.
weaknesses: The analysis is built upon a slightly different version of the loss function from the original discrete flow matching (Gat et al, 2024). Maybe it is better to elaborate a bit more on the connection between those loss functions and justify the use of squared $\ell_2$ as the Bregman divergence. 

There is a connection between discrete diffusion models and discrete flow matching. The original DFM training loss is identical to the masked diffusion training loss. There exists earlier literature on the convergence analysis of the discrete diffusion models. It’s better to include some discussions on the similarity and differences, and novelty compared to earlier works on discrete diffusion.  

In addition, since the paper only provides upper bounds on the TV distance and probability velocity risk, I feel that it needs some empirical evidence to show how tight those bounds are.

---

confidence: 5
contribution: 2
initial_rating: 2
presentation: 3
questions: See Weaknesses.
soundness: 1
strengths: - The main body of the paper is well written.
- The main TV bound is useful
- The Roadmap on page 6 is a nice addition to the paper to help understand how the proof works.
summary: The paper provides a useful bounds for Conditional Discrete Flow Matching (CDFM)  controlling the sampling error in total variation by a so-called riskk directly linked to the training loss. The authors also provide quantitative universality bounds for Transformers in the context of CDFM.
weaknesses: Major: the math is particularly clumsy and not to the expected level of a purely theoretical paper.
- The hypothesis that the velocity approximator is "factorized" seems unnecessary
- The whole Appendix B needs rewritting. In fact, the whole section is a combination of statement and proofs of undergraduate level written in a rather inefficient way. For instance,
    -  Lemmas B.5 and B.8 are standard undergraduate analysis statements (and the proof of B.8 is incorrect under the assumptions used, it is a common mistake but still...). Similar remarks apply to  part of section D.
     -  Lemma B.9 and B.6 are so standard they may probably be stated without proof.  Lemma B.10 would be highly simplified by using the Lipchitz constant of (X,Y) -> X+Y and better used of B.5. 
     -  Theorem B.17 is not original and I fail to understand why it is rewritten here or what the proofs written here brings to the discussion.
- Appendix C has too many problems to be acceptable:
     -  Lemma C.3 is FALSE!!!!  It is only true if the matrices $U_{t,\theta}$ commute.  
     -  Holder inequality seems to be unknown to the authors as they repeatedly bound the L1 norm of a product by the product of the L1 norms.
     - That being said, I do not doubt the final result, pending replacement of Lemma C.3 by slightly more sophisticated inequality one can obtain using Gronwall Lemma. 
    
Minor
- The chosen embedding of vocabulary is non-standard, quite restrictive and an unnecessary hypothesis.
- The same holds for the timestep embedding.
- Theorem 4.6 statement is unecessarily complicated, the notations of the space of transformers is not defined  - Lemma 4.4 may be most likely found in a functional analysis book, although in the context of an ML article, reproving it directly as in Appendix E is acceptable.
- some typos
- Theorem 4.6 is expected to hold in some form for any architectures for which one is able to prove a quantitative universality theorem. It is not specific to transformers, stating the result only for transformers is rather odd.

---

confidence: 3
contribution: 2
initial_rating: 4
presentation: 2
questions: The theoretical analysis is interesting; I would consider raising my score if the authors address the following question:
(1) Could the authors analyze error bounds for the out-of-vocabulary (OOV) case, now or in future work? The current theory appears to assume a finite discrete state space; with OOV tokens, how should the problem be treated?
(2) Recent work (e.g., Dirichlet Flow, H. Stark 2024; Diffusion LM, Shen et al., 2025) models discrete diffusion/flow using cross-entropy objectives that naturally yield KL bounds. Why is MSE chosen here instead, and why analyze total-variation (TV) bounds rather than KL?
soundness: 3
strengths: (1) The paper proposes a rigorous end-to-end theory for descrete flow matching.
(2) The chain of results (intrinsic error, approximation error, estimation error) is elegant and well-motivated.
(3) The derivation of total variation bounds via Kolmogorov equations and Grönwall’s inequality seems technically non-trivial and new.
summary: The paper provides the first end-to-end theoretical analysis of Discrete Flow Matching (DFM). It establishes: (1) Intrinsic error bound linking velocity field risk to distributional error; (2)Approximation theory showing Transformers can approximate DFM velocity fields; (3)Estimation theory giving statistical convergence rates for training DFM-Transformers. In summary, the paper produces a complete approximation and estimation theory analogous to classical diffusion and flow matching results but for discrete flow matching.
weaknesses: (1) The paper currently lacks empirical experiments. In pratice, the is hard to make the training objective to be very small while the error bound relies heavily on terms like \sqrt(M)exp(M). The resulting guarantees could be loose for typical M, limiting practical interpretability.
(2) Some modeling assumptions appear stronger than usual, for example, time-Hölder smoothness of CTMC paths, exponentially large UA constants for transformers, and a global velocity-field bound. Clarifying why these are needed and how sensitive the results are to them would improve transparency.

---

confidence: 3
contribution: 4
initial_rating: 8
presentation: 3
questions: - The main weakness of the bound is an error guarantee exhibiting a curse with the effective dimensionality $Md_0$. Could the authors provide more intuition or discussion on why this is the case? Section $6$ discusses the prefactor but not the rate. Notably, it seems that this depends on the choice of the model through $d_0$ and is not a fundamental limitation. If this is the case, could the authors brieflw discuss this point and how it can be refined in future works?

- I understand that the discrete-to-continuous mapping leverages the natural inclusion embedding of $\mathcal{V}$ in $\mathbb{R}$, with vocabulary items of higher index receiving larger values. Naively, it seems that this embedding, unlike e.g. one-hot encodings, does not treat all vocabulary items in the same fashion, and is not the most natural embedding. Could the authors comment on this, and how this choice impacts (or not) the bounds?
- Further motivation on the choice of transformer architectures would be helpful. In particular, many previous works on continuous generative models studied ResNet or auto-encoder architectures (e.g. Boffi et al; Shallow diffusion networks provably learn hidden low-dimensional structure; 2024). Is the transformer particularly adapted to the discrete case, or simply chosen to reflect most practical settings?
- (Minor) l 266 : "total variation distance bound scales exponentially with vocabulary size M" I am confused as I do not see any exponential dependence in Theorem 3.1.
- I invite the authors to include further comparison with analyses in the continuous case to better highlight the main differences, which would be interesting. In particular, I am wondering whether the authors have an idea how an analysis of the time discretization error would proceed and differ in the discrete setting ?
soundness: 3
strengths: The work extends the growing body of works on theoretical analyses of flow-matching models to the discrete case. This extension requires technical extensions such as Lemma 4.4, which allows to bridge from the discrete case to the continuous case. The contribution is, to the best of my awareness, novel and interesting, and will thus prove of interest to the ICLR community. The paper is overall clearly written, and the main technical ideas sufficiently explained and motivated. In this light, I am overall in favor of acceptance; however, I have limited familiarity with the field, and did not read the proofs in detail.
summary: The authors provide a full error analysis for a discrete flow-matching model parametrized by a transformer, trained on factorized mixture path interpolants. On the technical level, a central result is their construction of a smooth velocity field valued on a continuous domain, extending the true velocity field which takes discrete arguments. This in turn allows them to apply approximation results for transformers, and reach error guarantees, alongside norm bounds for the model parameters.
weaknesses: My main criticism is the lack of sufficient discussion on certain aspects, which I highlight in the questions section.


Decision: Reject