Flow Matching with General Discrete Paths: A Kinetic-Optimal Perspective Neta Shaul, Itai Gat, Marton Havasi, Daniel Severo, Anuroop Sriram, Peter Holderrieth, Brian Karrer, Yaron Lipman, Ricky T. Q. Chen Abstract The design space of discrete-space diffusion or flow generative models are significantly less well-understood than their continuous-space counterparts, with many works focusing only on a simple masked construction. In this work, we aim to take a holistic approach to the construction of discrete generative models based on continuous-time Markov chains, and for the first time, allow the use of arbitrary discrete probability paths, or colloquially, corruption processes. Through the lens of optimizing the symmetric kinetic energy, we propose velocity formulas that can be applied to any given probability path, completely decoupling the probability and velocity, and giving the user the freedom to specify any desirable probability path based on expert knowledge specific to the data domain. Furthermore, we find that a special construction of mixture probability paths optimizes the symmetric kinetic energy for the discrete case. We empirically validate the usefulness of this new design space across multiple modalities: text generation, inorganic material generation, and image generation. We find that we can outperform the mask construction even in text with kinetic-optimal mixture paths, while we can make use of domain-specific constructions of the probability path over the visual domain. 1 Introduction Generative models over discrete spaces have not seen as much progress on the methodology side compared to continuous-space counterparts. For the most part, applications such as large language modeling rely solely on autoregressive models ( Radford et al. 2019 ; Bommasani et al. 2021 ) . The simplicity of autoregressive modeling has also motivated people to use them for multimodal generation, where other modalities, such as images and videos, are tokenized and modeled within an autoregressive framework ( Van den Oord et al. 2016 ; Team 2024 ; Sun et al. 2024 ) . While obtaining reasonable results, they have not yet reached the performance of continuous-space generative models such as denoising diffusion ( Ho et al. 2020 ; Song et al. 2021 ) and Flow Matching models ( Lipman et al. 2022 ; Albergo et al. 2023 ) for the visual-audio domains ( Rombach et al. 2022 ; Dai et al. 2023 ; Esser et al. 2024 ; Zhou et al. 2024 ) , where it is believed that the ability to perform iterative refinement brings significant gains ( Saharia et al. 2022 ; Zhang et al. 2024 ) . A promising framework that brings iterative refinement to the discrete case is to consider the use of Markov chains within a dynamical generative framework. Many discrete-space generative flow and diffusion models have seen success in the generation of text ( Austin et al. 2021 ; Lou et al. 2024 ; Shi et al. 2024 ; Sahoo et al. 2024 ; Gat et al. 2024 ) , proteins ( Campbell et al. 2024 ) , images ( Austin et al. 2021 ; Shi et al. 2024 ) , and even executable code ( Gat et al. 2024 ) . However, the design space of these models is currently rather limited, with many recent works instead focusing solely on the case of masking as a corruption process ( Shi et al. 2024 ; Sahoo et al. 2024 ) . The masked construction is an extension of masked pretraining ( Devlin 2018 ; Yang 2019 ) , but it does not fully embody the concept of iterative refinement as it is equivalent to learning autoregressive models for every ordering ( Hoogeboom et al. 2021 ; Chang et al. 2022 ) , and it has been noticed that some of the recent reported progress was actually misleading due to low-precision sampling ( Zheng et al. 2024 ) rather than the explicit design choice of masking as a corruption process. In spite of this, the masked construction has often been found to be the best performing choice out of the limited family of corruption processes previously considered tractable ( Austin et al. 2021 ; Campbell et al. 2024 ; Gat et al. 2024 ) . We instead take a holistic view on constructing discrete Flow Matching models, massively expanding the design space to enable arbitrary probability paths, or colloquially, corruption processes, grounded in the framework of continuous-time Markov chains (CTMC). We list our contributions: 1. Analogous to the continuous setting, we find that an infinite number of velocities can generate any given probability path. In order to reduce this search space, we consider a decomposition into a probability-advancing velocity and a probability-preserving velocity. 2. To explore the space of probability-advancing velocities, we motivate a family of closed-form velocities that be formulated as optimizing kinetic energy. In particular, we are the first to formulate velocities that can work with any choice of probability path, completely opening up the design space of probability paths, e.g. , domain-specific constructions, while recovering the velocities used by prior works for existing paths in the literature. 3. We also find that the probability path itself can also be optimized with the same kinetic energy criterion. A closed-form solution surprisingly recovers the mixture paths considered by Gat et al. 2024 but with novel source-dependent schedulers. 4. We derive the ELBO for discrete Flow Matching models in full generality. This leads to an improved ELBO for training mixture probability paths that has not been used before, and recovers the ELBO derived by Shi et al. 2024 for the masked construction. We find that with this ELBO, our kinetic-optimal mixture paths outperform the masked construction. 2 Background: Discrete Flow Matching We are interested in learning a generative model that approximates a data distribution q(x) , where x=(x^{1},x^{2},\ldots,x^{D})\in{\mathcal{S}}={\mathcal{T}}^{D} with {\mathcal{T}}=[K]\triangleq\left\{1,2,\ldots,K\right\} being a discrete set of possible token values, and D\in\mathbb{N} is number of discrete variables. For brevity and without loss of generality, we consider all dimensions to have the same number of discrete values. Probability paths. We denote by p(x) and q(x) the source and target, respectively, probability mass functions (PMFs) over the state space {\mathcal{S}} . We consider probability paths p_{t}(x) , t\in[0,1] , to be time-dependent PMFs taking the form \textstyle p_{t}(x)\triangleq\sum_{x_{1}\in{\mathcal{S}}}p_{t}(x|x_{1})q(x_{1}),\text{ where }p_{t}(x|x_{1})\triangleq\prod_{i=1}^{D}p_{t}(x^{i}|x_{1}^{i}), (1) and p_{t}(x^{i}|x_{1}^{i}) is a conditional probability path which interpolates between a simple PMF at time t=0 and a delta PMF centered around x^{i}_{1} at t=1 . That is, we assume the boundary conditions p_{0}(x^{i}|x^{i}_{1})=p(x^{i}) and p_{1}(x^{i}|x^{i}_{1})=\delta_{x^{i}_{1}}(x^{i}) . Hence we can interpret these probability paths p_{t}(x) in equation 1 as interpolating between a factorized source distribution p(x)\triangleq\prod_{i=1}^{D}p(x^{i}) and the data distribution q(x) . A common family of probability paths used in previous works is the collection of mixture paths ( Gat et al. 2024 ) , with x_{1}^{i} -dependent schedulers similar to Shi et al. 2024 : p_{t}(x^{i}|x_{1}^{i})=(1-\kappa_{t}(x_{1}^{i}))p(x^{i})+\kappa_{t}(x_{1}^{i})\delta_{x_{1}^{i}}(x^{i}), (2) where \kappa_{0}(\cdot)=0 and \kappa_{1}(\cdot)=1 to satisfy the boundary conditions. Specifically, with p(x^{i})=\delta_{\mathbbm{m}}(x^{i}) we recover the masked construction ( Shi et al. 2024 ; Sahoo et al. 2024 ) . Probability velocities. As our generative process, we simulate a Continuous Time Markov Chain (CTMC) (X_{t})_{t\in[0,1]} in {\mathcal{S}} such that its time marginals follow a prescribed probability path, X_{t}\sim p_{t}. (3) In order to do so, we define the concept of a probability velocity , also known as a rate matrix. We say that a probability velocity u_{t} generates p_{t} if u_{t} characterizes a Markov process X_{t} with marginal p_{t} (equation 3 ) for all t\in[0,1) in the following sense: \textstyle\mathbb{P}(X_{t+h}=x\ |\ X_{t}=z)=\delta_{z}(x)+hu_{t}(x,z)+o(h), (4) where o(h) denotes a function which is asymptotically smaller than h , i.e. , \lim_{h\rightarrow 0}\nicefrac{{o(h)}}{{h}}=0 . Intuitively, u_{t} describes the Markov transition of X_{t} for small step sizes h>0 . We note that for equation 4 to be a valid PMF, u_{t} must at least satisfy the Rate Conditions : \begin{matrix}[l]u_{t}(x,z)\geq 0\text{ for all }x\neq z\text{ and }\sum_{x}u_{t}(x,z)=0\end{matrix}\qquad\blacktriangleright\text{ Rate Conditions} (5) Single-variable-change probability velocities. It is natural to consider modeling a CTMC process X_{t} over {\mathcal{S}} by defining a u_{t}(x,z) for all pairs x,z\in{\mathcal{S}} . However, the state space is of size |{\mathcal{T}}|^{D} so this is generally prohibitive for high dimensions. A remedy is to consider rates that only allow a state to change in a single variable ( Campbell et al. 2022 ) , e.g. , in the following example we only change the variable at the i -th coordinate: (z^{1},\ldots,z^{i-1},\bm{z^{i}},z^{i+1},\ldots,z^{D})\rightarrow(z^{1},\ldots,z^{i-1},\bm{x^{i}},z^{i+1},\ldots,z^{D}). (6) To model only such changes we restrict our attention to velocities of the form u_{t}^{i}(x^{i},z) that describe the probability rate between the state z and the state with the i -th coordinate replaced, i.e. , as described in the r.h.s. in equation 6 . We can express the full velocity u_{t}(x,z) via u_{t}^{i}(x^{i},z) as u_{t}(x,z)=\sum_{i=1}^{D}u_{t}^{i}(x^{i},z){\color[rgb]{0,0,0}{\prod_{j\neq i}\delta_{z^{j}}(x^{j})}}, (7) which states the probability velocity between two states z\rightarrow x is zero if they differ by more than one variable and equal u_{t}^{i}(x^{i},z) if they differ by exactly one variable. Plugging this velocity into equation 4 , it can be shown that ( Gat et al. 2024 ) : \textstyle\mathbb{P}(X_{t+h}=x\ |\ X_{t}=z)=\prod_{i=1}^{D}\left[\delta_{z^{i}}(x^{i})+hu_{t}^{i}(x^{i},z)\right]+o(h) (8) This implies we can sample each variable X_{t+h}^{i} independently from the distribution \delta_{z^{i}}(x^{i})+hu_{t}^{i}(x^{i},z) , and only incur an error of o(h) . The marginal velocity. Previous works ( Campbell et al. 2024 ; Gat et al. 2024 ) have shown that constructing a generating velocity for p_{t}(x) can be achieved by considering only the conditional probability paths in equation 1 . That is, assume we have conditional velocities u^{i}_{t}(x^{i},z^{i}|x_{1}^{i}) , which are velocities in the state space {\mathcal{T}} , that generate the conditional paths p_{t}(x^{i}|x_{1}^{i}) in equation 1 . Then a marginal velocity u^{i}_{t}(x^{i},z) that generates p_{t}(x) takes the form: \textstyle u^{i}_{t}(x^{i},z)=\sum_{x_{1}^{i}\in{\mathcal{T}}}u^{i}_{t}(x^{i},z^{i}|x_{1}^{i})p^{i}_{1|t}(x_{1}^{i}|z) (9) where p^{i}_{1|t}(x_{1}^{i}|z) is the posterior probability of the i -th token taking the value x_{1}^{i} , i.e. , \textstyle p^{i}_{1|t}(x^{i}|z)=\sum_{x_{1}\in\mathcal{S}}\delta_{x_{1}^{i}}(x^{i})\frac{p_{t}(z|x_{1})q(x_{1})}{p_{t}(z)}. (10) Parameterizing the factorized posterior \prod_{i=1}^{D}p^{i}_{1|t} is an approach taken by prior works ( Austin et al. 2021 ; Campbell et al. 2022 ) . To train, a simple option is the cross-entropy objective: \textstyle\mathcal{L}_{\text{CE}}(\theta)=\mathbb{E}_{t\sim U[0,1],x_{1}\sim q(\cdot),x\sim p_{t}(\cdot|x_{1})}\left[-\sum_{i=1}^{D}\log p_{1|t}^{\theta,i}(x_{1}^{i}|x)\right]. (11) We use this training loss for general probability paths as it is generally applicable. However, for the case of mixture paths (equation 2 ) it is possible to derive a tractable ELBO as the marginal u_{t} can be written in closed form without a summation as in equation 9 . We cover this later in Section 6 . 3 Sample generation through the factorized posterior The most direct approach to sample from this model is to use the marginal velocity u_{t}(x^{i},z) , e.g. , with a first-order sampling scheme defined by removing the o(h) term in equation 8 , i.e. , given X_{t} , we advance time with step size h by sampling X_{t+h}^{i} according to X_{t+h}^{i}\sim\delta_{X_{t}^{i}}(\cdot)+hu^{i}_{t}(\cdot,X_{t}), (12) for each i\in[D] , where u_{t}^{i} is computed with equation 9 . However, for general discrete paths this sampling procedure is intractable for large discrete spaces {\mathcal{T}} as computing u_{t}^{i}(x^{i},z) with equation 9 for all x^{i}\in{\mathcal{T}} has a computational complexity of |{\mathcal{T}}|^{2} . Alternatively, we propose a more efficient sampling scheme by noticing that \textstyle\delta_{z^{i}}(x^{i})+hu^{i}_{t}(x^{i},z) \textstyle\overset{(\ref{e:u_t_marginalization})}{=}\sum_{x_{1}^{i}\in{\mathcal{T}}}\left[\delta_{z^{i}}(x^{i})+hu^{i}_{t}(x^{i},z^{i}|x_{1}^{i})\right]p^{i}_{1|t}(x_{1}^{i},z), (13) which leads to a sampling process that avoids computing the full marginal velocity: given the current state X_{t} , sample X_{1} from the factorized posterior, then sample X_{t+h} . That is, for each i\in[D] , 1) Sample X^{i}_{1}\sim p^{i}_{1|t}(\cdot|X_{t}) ; and 2) Sample X_{t+h}^{i}\sim\delta_{X_{t}^{i}}(\cdot)+hu^{i}_{t}(\cdot,X_{t}^{i}|X^{i}_{1}) . This sampling procedure still results in X_{t} with the same time marginals while avoiding the computational cost of the summation in equation 9 . To enable the use of any step size h , we use a slightly modified step 2; see Appendix A for more details and pseudocode in Algorithm 1 . 4 Kinetic optimal velocities and probability paths We first decouple the design space of probability paths and their generating velocities, providing the means to effectively explore this large design space. This section covers two contributions: ( i ) we propose a family of kinetic optimal (KO) velocities that generates any given probability path, and ( ii ) we solve for kinetic optimal probability paths, recovering a special case of mixture paths. The first contribution enables us to work with general discrete probability paths. The second contribution justifies the choice of mixture probability paths used by Gat et al. 2024 but offers novel x_{1}^{i} -dependent schedulers. For both, we center our designs based on optimizing a discrete notion of kinetic energy ( Peyré et al. 2019 ) . Notation. As the discussion in this section applies to arbitrary probability paths and discrete state spaces, we will use a simplified notation, where our state space is now {\mathcal{T}} and for states we use x,z\in{\mathcal{T}} , abusing a bit the previous notation (where x^{i},z^{i}\in{\mathcal{T}} ). Furthermore, we will denote by p_{t}(x) and u_{t}(x,z) an arbitrary probability path and velocity field in {\mathcal{T}} , respectively. Continuity Equation. Given a probability path p_{t}(x) , the entire collection of velocities u_{t}(x,z) generating p_{t}(x) are the solutions to the Continuity Equation (a.k.a. the Kolmogorov forward equation) that also satisfy the Rate Conditions. It is useful to formulate the Continuity Equation through the flux j_{t} , that is \textstyle\dot{p}_{t}(x)+\mathrm{div}_{x}(j_{t})=0,\qquad\forall x\in{\mathcal{T}},\qquad\text{ with }j_{t}(x,z)=u_{t}(x,z)p_{t}(z). (14) Intuitively, the flux j_{t}(x,z) quantifies the amount of probability mass per unit of time moving from state z to state x . The divergence operator then measures the total outgoing flux minus the total incoming flux, which in the discrete case takes the form \textstyle\text{div}_{x}(j_{t})=\sum_{z\neq x}j_{t}(z,x)-\sum_{z\neq x}j_{t}(x,z). (15) Velocity from flux. Given a flux j_{t} satisfying the Continuity Equation (equation 14 ) we can get a velocity from the flux by defining for x\neq z , \textstyle u_{t}(x,z)=j_{t}(x,z)/p_{t}(z)\;\;\text{ if }p_{t}(z)>0,\qquad\text{ else }\;u_{t}(x,z)=0, (16) and the case x=z is uniquely set by the Rate Conditions ( 5 ), u_{t}(z,z)=-\sum_{x\neq z}u_{t}(x,z) . The velocity defined in this way will satisfy the Continuity Equation and the Rate Conditions if the flux satisfies the following conditions: \displaystyle j_{t}(x,z)\geq 0,\text{ for }x\neq z\qquad \displaystyle\blacktriangleright\text{Non-negativity} (17) \displaystyle p_{t}(z)=0\ \Rightarrow\ j_{t}(x,z)=0\qquad \displaystyle\blacktriangleright\text{Safe Flux Condition} (18) Intuitively, the Safe Flux Condition ensures no flux is leaving a zero probability state z . Proposition 4.1 . Given a non-negative safe flux j_{t} that satisfies the Continuity Equation, the velocity defined in equation 16 satisfies the Rate Conditions and generates the p_{t} probability path. Kinetic optimality. Motivated by the approach employed in the continuous case of minimizing the kinetic energy for the conditional velocities ( Lipman et al. 2022 ; Shaul et al. 2023 ) , we take a similar approach for finding velocities for the discrete case. The standard convex formulation of the kinetic energy adapted to the discrete case is ( Peyré et al. 2019 ) : \textstyle\min_{p_{t},j_{t}} \textstyle\quad\int_{0}^{1}\sum_{x\neq z}\frac{w_{t}(x,z)}{p_{t}(z)}j_{t}(x,z)^{2}dt \textstyle\blacktriangleright\text{ Kinetic Energy } (19a) s.t. \textstyle\quad\mathrm{div}_{x}(j_{t})=-\dot{p}_{t}(x),\qquad\ \ \forall x\in{\mathcal{T}} \textstyle\blacktriangleright\text{ Continuity Equation } (19b) \textstyle\quad j_{t}(x,z)\geq 0,\qquad\qquad\forall x\neq z\in{\mathcal{T}} \textstyle\blacktriangleright\text{ Non-negative flux } (19c) \textstyle\quad p_{0}=p,\quad p_{1}=q \textstyle\blacktriangleright\text{ Boundary conditions} (19d) where w_{t}(x,z)>0 is some problem-dependent weighting; a higher weight implies a smaller flux from z\rightarrow x , i.e. , the higher this value the smaller the velocity u_{t}(x,z) . The optimality criterion (equation 19a ) is the kinetic energy, equivalently \frac{j_{t}(x,z)^{2}}{p_{t}(z)}=u_{t}(x,z)^{2}p_{t}(z) . The benefit of formulating in terms of the flux (instead of the velocity) is that the problem becomes convex in its unknowns (p_{t},j_{t}) , and in particular the Continuity Equation constraint in ( 19b ) is linear. Lastly, in case of \frac{w_{t}(x,z)}{p_{t}(z)}=\infty the energy in equation 19a is defined to be 0 if j_{t}(x,z)=0 , and \infty if j_{t}(x,z)>0 . Therefore, to ensures the solution j_{t}^{\star} is safe (equation 18 ) we ask that w_{t} satisfies: \textstyle p_{t}(z)=0\Rightarrow\frac{w_{t}(x,z)}{p_{t}(z)}=\infty\quad\blacktriangleright\text{ Safe Weight Condition} (20) and that problem 19 is feasible , i.e. , it has a finite energy solution. Although problem 19 is convex, solving it for a general w_{t} requires numerical approximation. Since we want to solve it for conditional probability paths with different x_{1}\in{\mathcal{T}} , i.e. , q(x)=\delta_{x_{1}}(x) , this can be computationally challenging. Instead, we will explore cases of w_{t} where problem ( 19 ) is solvable in closed-form . We start with assuming p_{t} is known/given, and find the kinetic optimal velocity u^{\star}_{t} , then afterwards we discuss optimizing the p_{t} as well. 4.1 Kinetic optimal velocity Assuming p_{t}>0 is fixed in ( 19 ), our goal is to find the kinetic optimal solution j_{t}^{\star} , and consequently obtaining a velocity u_{t}^{\star} via ( 16 ). One observation we make is that ( 19 ) can be efficiently solved when symmetric , i.e. , when \frac{w_{t}(x,z)}{p_{t}(z)}=\frac{w_{t}(z,x)}{p_{t}(x)} . As we prove in Appendix B , ( 19 ) can be efficiently solved via the following linear relaxation: \textstyle\sum_{z}\frac{p_{t}(z)}{w_{t}(x,z)}\left[f_{t}(x)-f_{t}(z)\right]=\dot{p}_{t}(x),\qquad\forall x\in{\mathcal{T}} (21) where f_{t}:{\mathcal{T}}\rightarrow\mathbb{R} is the unknown function over the state space. The linear equation in ( 21 ) is of Laplacian form , and many properties (including closed-form solutions) are known in many cases ( Vishnoi 2012 ) . The solution f_{t} to ( 21 ) is unique up to a global constant and using f_{t} we construct the kinetic optimal flux, \textstyle j^{\star}_{t}(x,z)\triangleq\frac{p_{t}(z)}{w_{t}(x,z)}\left[f_{t}(x)-f_{t}(z)\right]_{+}, (22) where \left[s\right]_{+}=\max\left\{s,0\right\} is the ReLU operator. This provides a solution to ( 19 ) with a fixed and positive p_{t} . Consequently, using ( 16 ) we get the kinetic optimal velocity. We have shown that a certain family of kinetic optimal velocities can be computed by solving a linear system ( 21 ) for arbitrary probability paths p_{t}(x) over state-space {\mathcal{T}} . Next we will further instantiate this family and provide some closed form solution for j_{t}^{\star} and u_{t}^{\star} . Closed-form u_{t} . We will consider the case where w_{t}(x,z)=\frac{p_{t}(z)}{\tau_{t}(x)\tau_{t}(z)} , and \tau_{t}:{\mathcal{T}}\rightarrow\mathbb{R}_{\geq 0} is a design choice of our method. To ensure w_{t} is safe ( 20 ) we require that p_{t}(z)=0 implies \tau_{t}(z)=0 . The solution f_{t} to ( 21 )—which can be checked with substitution—is: \textstyle f_{t}(x)=\frac{1}{\sum_{s\in{\mathcal{T}}}\tau_{t}(s)}\frac{\dot{p}_{t}(x)}{\tau_{t}(x)}. (23) One choice is \tau_{t}(x)=\mathbbm{1}_{[p_{t}(x)>0]} , that leads to the Kinetic Optimal flux \textstyle j^{\star}_{t}(x,z)=\frac{1}{|{\mathcal{T}}|}\left[\partial_{t}p_{t}(x)-\partial_{t}p_{t}(z)\right]_{+},\qquad\text{ for }x\neq z (24) which upon converting to velocity via ( 16 ) recovers the velocity proposed in Campbell et al. 2024 for positive paths, p_{t}>0 . Note however, that the above flux is not safe (does not satisfy equation 18 ) and if p_{t}(z)={\epsilon} the flux j^{\star}_{t}(x,z) for some general x is not necessarily small, showing a potential numerical issue. Campbell et al. 2024 formulate a limit case for general p_{t} that also requires adding an extra assumption on p_{t} (that p_{t}(x)=0\Rightarrow\dot{p}_{t}(x)=0 ), which does not hold even for common probability paths that are typically used, such as the masked mixture path with linear schedulers. Alternatively, we propose a more numerically stable choice. Consider \tau_{t}(x)=p_{t}(x) , i.e. , \textstyle w_{t}(x,z)=1/p_{t}(x). (25) This results in f_{t}(x)=\dot{p}_{t}(x)/p_{t}(x) , and the kinetic optimal flux in this case is: \displaystyle j^{\star}_{t}(x,z)=\left[p_{t}(z)\dot{p}_{t}(x)-\dot{p}_{t}(z)p_{t}(x)\right]_{+},\qquad\text{ for }x\neq z (26) Note that in contrast to before, this flux is safe (satisfies equation 18 ) and therefore works for general p_{t} . Furthermore, ( 26 ) exhibits stable limiting behavior for continuously differentiable p_{t} : when p_{t}(z)\rightarrow 0 , so too will j^{\star}(x,z)\rightarrow 0 . We note that for uniform and mask source distributions with the mixture path ( 2 ), the velocity considered by Campbell et al. 2024 and our velocity resulting from ( 26 ) coincide. However, for mixture paths ( 2 ) and general discrete paths, they generally do not coincide. Additionally, the choice of velocity in ( 26 ) also recovers the velocities used by Gat et al. 2024 for mixture probability paths. See Section C.1 for detailed derivations. Finally, we discuss a broader family of closed-form velocities involving different choices of \tau_{t} in Section C.3 , which we find can significantly boost performance at low-cost sampling regimes. Metric-induced p_{t}(x) . The velocity resulting from ( 26 ) can be applied to any user-defined p_{t} . We propose metric-induced conditional probability paths of the form \textstyle p_{t}(x|x_{1})=\text{softmax}\left(-\beta_{t}\textrm{d}(x,x_{1})\right), (27) where \beta:[0,1]\rightarrow\mathbb{R}_{\geq 0} is a monotonic scheduler with \beta_{0}=0 , \beta_{1}=\infty , and \textrm{d}:{\mathcal{T}}\times{\mathcal{T}}\rightarrow\mathbb{R}_{\geq 0} such that \textrm{d}(x,x_{1})=0\Leftrightarrow x=x_{1} ,interpreted loosely as a metric over discrete values. If we apply the flux in ( 26 ) for the paths in ( 27 ) and simplify, we obtain the velocity: \textstyle u_{t}^{\star}(x,z|x_{1}) \textstyle=p_{t}(x|x_{1})[\partial_{t}\log p_{t}(x|x_{1})-\partial_{t}\log p_{t}(z|x_{1})]_{+} (28) \textstyle=p_{t}(x|x_{1})\dot{\beta}_{t}[\textrm{d}(z,x_{1})-\textrm{d}(x,x_{1})]_{+}. (29) This velocity has the property that we only move from state z to state x if x is closer than z to x_{1} , i.e. , \textrm{d}(x,x_{1})<\textrm{d}(z,x_{1}) , hence resulting in a flow that only moves closer to x_{1} . 4.2 Kinetic Optimal probability paths Interestingly, for the weighting choice that we have motivated for the numerically stable velocity ( 25 ), it is also possible to solve for the kinetic optimal probability path p_{t}^{\star} . As we show in Appendix B , in this case, the problem ( 19 ) can be formulated equivalently as \displaystyle\textstyle\min_{a_{t}} \displaystyle\quad\int_{0}^{1}\sum_{x}\dot{a}_{t}(x)^{2}\,dt \displaystyle\blacktriangleright\text{ Kinetic Energy } (30a) s.t. \displaystyle\textstyle\quad\sum_{x}a_{t}(x)^{2}=1,\qquad\qquad\forall t\in[0,1] \displaystyle\blacktriangleright\text{ Hypersphere constraints} (30b) \displaystyle\textstyle\quad a_{0}(x)=\sqrt{p(x)},\quad a_{1}(x)=\sqrt{q(x)}\qquad\qquad \displaystyle\blacktriangleright\text{ Boundary conditions } (30c) where a_{t}(x)=\sqrt{p_{t}(x)} . Problem ( 30 ) is the kinetic energy of a curve over the hypersphere connecting \sqrt{p} and \sqrt{q} . The optimal solution thus corresponds to the geodesic curve on the hypersphere, \textstyle a_{t}(x)=\frac{\sin(1-t)\Omega}{\sin\Omega}\sqrt{p(x)}+\frac{\sin t\Omega}{\sin\Omega}\sqrt{q(x)},\ \ \text{where }\Omega=\arccos\left(\sum_{z}\sqrt{p(z)q(z)}\right), (31) and consequently the optimal probability path and velocity for ( 30 ) are \textstyle p_{t}^{\star}(x)=a_{t}^{2}(x),\qquad{u_{t}^{\star}(x,z)=a_{t}^{2}(x)\left[\partial_{t}\log a_{t}^{2}(x)-\partial_{t}\log a_{t}^{2}(z)\right]_{+}} (32) In the particular case of conditional probability paths q(x)=\delta_{x_{1}}(x) , we get that the optimal solution recovers the mixture path (equation 2 ) with a specific x_{1} -dependent scheduler: \textstyle\kappa_{t}(x_{1})=1-\frac{\sin^{2}(1-t)\Omega(x_{1})}{\sin^{2}\Omega(x_{1})},\qquad\text{ where }\Omega(x_{1})=\arccos\sqrt{p(x_{1})}. (33) This justifies the mixture paths ( 2 ) as kinetic optimal, and furthermore, it naturally utilizes an x_{1} -dependent scheduler for general source distributions p when p(x_{1})>0 . 5 Probability-preserving velocities While we have found a particular flux j_{t}^{\star} , the space of fluxes for a given p_{t} is much larger, and in this section we show how to explore it further. We first observe that since the Continuity Equation ( 14 ) is a linear equation, any flux j_{t} satisfying this equation can be written as a sum of two fluxes: j_{t}=j_{t}^{\star}+j_{t}^{\perp},\qquad\text{ where }\mathrm{div}_{x}(j_{t}^{\perp})=0, (34) where j_{t}^{\star} is a particular solution to the Continuity Equation and j_{t}^{\perp} is a solution to the homogenous version of the equation, i.e. , divergence-free . We call the velocity resulting from j_{t}^{\perp} a probability-preserving , or corrector, velocity as sampling with this velocity has p_{t} as a steady-state. For simplicity, we mainly consider the special case of symmetric flux. Symmetry is a sufficient condition for being divergence-free as is evident from ( 15 ). A natural choice for a symmetric flux is to consider a symmetrization of ( 22 ) taking the form \textstyle j_{t}^{\perp}(x,z)=\frac{p_{t}(z)}{w_{t}(x,z)}\left|f_{t}(x)-f_{t}(z)\right|,\qquad\text{ and }u_{t}^{\perp}(x,z)=j_{t}^{\perp}(x,z)/p_{t}(z), (35) for any function f_{t} . For convenience, we will simply re-use the same f_{t} that comes from optimizing the kinetic energy ( 19 ), e.g. the same as in ( 26 ). In contrast to the kinetic optimal velocity, which results in a unidirectional flow in the sense that samples will only move from lower f_{t}(\cdot) to higher f_{t}(\cdot) , the symmetric flux in ( 35 ) results in a bidirectional flow that allows equal movement between any two states with non-equal f_{t}(\cdot) . Hence j_{t}^{\perp} acts as a corrector to redirect samples back to previous states in a way that leaves p_{t} invariant. 6 ELBO for Discrete Flow Matching We show in Appendix D that we can produce a continuous-time ELBO bound on the likelihood \log p^{\theta}_{1}(x_{1}) for any conditional probability path and conditional probability velocity in terms of the marginal u^{i}_{t}(x^{i},z) and conditional u^{i}_{t}(x^{i},z^{i}|x_{1}^{i}) as follows \begin{split}\textstyle\log p_{1}(x_{1})\geq\int_{0}^{1}\mathbb{E}_{x_{t}\sim p_{t}(\cdot|x_{1})}\sum_{i=1}^{D}\biggr[&u_{t}^{i}(x_{t}^{i},x_{t})-u^{i}_{t}(x_{t}^{i},x_{t}^{i}|x^{i}_{1})\\ \vskip-5.0pt&\textstyle+\sum_{y^{i}\neq x_{t}^{i}}u^{i}_{t}(y^{i},x_{t}^{i}|x^{i}_{1})\log\left(\frac{u_{t}^{i}(y^{i},x_{t})}{u^{i}_{t}(y^{i},x_{t}^{i}|x^{i}_{1})}\right)\biggr]\mathrm{d}t\end{split} (36) Evaluating this ELBO is difficult for the same reason as sampling in Section 3 , for large discrete spaces {\mathcal{T}} computing ( 9 ) for all x^{i}\in{\mathcal{T}} has a computational complexity of |{\mathcal{T}}|^{2} . However, for mixture paths ( 2 ), our conditional velocity resulting from ( 26 ) is used to obtain a closed-form expression for the marginal velocity (see Section C.2 ), yielding a tractable ELBO for mixture paths: \begin{split}\textstyle\log p_{1}^{\theta}(x_{1})\geq\int_{0}^{1}\mathbb{E}_{x_{t}\sim p_{t}(\cdot|x_{1})}\sum_{i=1}^{D}\biggr[&\lambda(x_{t}^{i})p^{\theta}_{1|t}(x_{t}^{i}|x_{t})-\sum_{y^{i}}\lambda(y^{i})p^{\theta}_{1|t}(y^{i}|x_{t})+\\ &\textstyle+(1-\delta_{x^{i}_{1}}(x_{t}^{i}))\lambda(x_{1}^{i})\left(1+\log p^{\theta}_{1|t}(x_{1}^{i}|x_{t})\right)\biggr]\mathrm{d}t,\end{split} (37) where \lambda(x)=\frac{\dot{\kappa}_{t}(x)}{1-\kappa_{t}(x)} . This ELBO has not been used previously, e.g. , Campbell et al. 2022 had to resort to a doubly stochastic estimator. Specifically for the masked construction, we recover the ELBO used by Zheng et al. 2024 for x_{1}^{i} -independent schedulers and used by Shi et al. 2024 for x_{1}^{i} -dependent schedulers; see Section D.1 . 7 Related Work Generative modeling through marginalization. Denoising diffusion models ( Sohl-Dickstein et al. 2015 ; Ho et al. 2020 ; Song et al. 2021 ) construct generative models by reversing a noising process. The Flow Matching framework ( Lipman et al. 2022 ; Albergo et al. 2023 ; Liu et al. 2022 ) shares similar traits but instead constructs generative models through a marginalization of conditional Markov processes, allowing a larger design space of probability paths. These types of models can be trained at scale both efficiently and stably relative to other frameworks, and thus have seen massive success in the large-scale generation of images ( Rombach et al. 2022 ; Esser et al. 2024 ) , videos ( Singer et al. 2022 ) , and audio ( Le et al. 2024 ; Vyas et al. 2023 ) . Continuous-time Markov Chains. These aforementioned frameworks have been adapted to the discrete domain by making use of Continuous-time Markov Chains (CTMC) as the choice of generative process ( Campbell et al. 2022 ; Campbell et al. 2024 ; Lou et al. 2024 ; Gat et al. 2024 ) . Many works discuss both a uniform noise and mask construction ( Campbell et al. 2024 ; Lou et al. 2024 ) ; however, more recent works have focused more and more on the simple masked construction where each discrete variable is randomly replaced with a dummy or mask token ( Sahoo et al. 2024 ; Shi et al. 2024 ) as it often performs favorably compared to uniform noise. However, the simple masked construction leads to a generative model that is equivalent to any-order autoregressive modeling under mild assumptions ( Hoogeboom et al. 2021 ; Zheng et al. 2024 ) . Any-order autoregressive modeling. While autoregressive models prespecify a fixed ordering, any-order autoregressive models learn conditional probabilities for every ordering. Training is often carried out by randomly masking out parts of the data sample ( Devlin 2018 ; Yang 2019 ) . Some works have focused on architectural choices: Germain et al. 2015 randomly masks out weights to induce a randomized ordering, while Pannatier et al. 2024 uses a fixed causal attention architecture but randomly permutes the input ordering, with the end goal of learning all combinations of conditional distributions so that generation of the variables can be done in any order. The ordering itself is often optimized further by the use of heuristic scoring functions ( Chang et al. 2022 ; Ziv et al. 2024 ) . Figure 1: Generative perplexity vs. ELBO of kinetic optimal (KO) and linear schedulers of FineWeb-Edu models. The ELBO is evaluated: WikiText-103, LAMBADA, Penn TreeBank,FineWeb-Edu, and OpenWebText. Bold highlights the Pareto front. Table 1: Zero-shot unconditional perplexity bound as in equation 36 of Fineweb-Edu models, more details are in Section E.1 . ∗ denotes our reimplementation of the method. Method Lambada \downarrow Wikitext2 \downarrow PTB \downarrow Wikitext103 \downarrow 1BW \downarrow OpenWebText \downarrow Fineweb-Edu (train set) \downarrow SEDD ∗ (mask) ( Lou et al. 2024 ) \leq 58.57 \leq 42.84 \leq 136.99 \leq 42.88 \leq 114.17 \leq 36.55 \leq 19.41 MD4 ∗ ( Shi et al. 2024 ) \leq 61.27 \leq 43.08 \leq 157.00 \leq 43.02 \leq 127.55 \leq 35.57 \leq 18.69 DFM - Linear ( \beta_{0}=1024 ) \leq 60.59 \leq 44.17 \leq 180.75 \leq 44.29 \leq 147.21 \leq 36.33 \leq 18.67 DFM - Kinetic Optimal (mask) \leq 58.5 \leq 41.80 \leq 144.46 \leq 41.83 \leq 123.83 \leq 35.57 \leq 18.71 DFM - Kinetic Optimal ( \beta_{0}=1024 ) \leq 58.41 \leq 42.19 \leq 147.09 \leq 42.34 \leq 115.51 \leq 36.07 \leq 18.63 8 Experiments We evaluate Discrete Flow Matching (DFM) on multiple modalities: text, crystalline material, and image generation. Our main goal is to show that Discrete Flow Matching can outperform autoregressive models, and within the class of Discrete Flow Matching, we explore new additions such as the kinetic optimal and the metric-induced constructions. In text, we mainly explore the kinetic optimal probability paths (equation 33 ) with different source distributions, as these have access to the closed-form ELBO ( 37 ). In material generation, we find that enabling permutation invariance for DFM easily outperforms autoregressive models at de novo generation, achieving state-of-the-art results. Furthermore, in domains where a natural metric exists, we demonstrate our method’s ability to inject inductive bias into the velocity and probability path using equations 27 and 29 . We show that our large design space enables competitive results even with non-mask probability paths, showcasing the capabilities of our expanded design space. 8.1 Text generation We explore our method on the task of text generation. We use the kinetic optimal probability path as in equation 33 , which only has one hyper-parameter, the source distribution p(x) . For source distribution, we compute the statistics of tokens appearances in the training data p_{\text{stats}}(x^{i}) and construct a single-parameter family of source distributions: \textstyle p(x)=\prod_{i=1}^{D}p(x^{i}),\quad p(x^{i})=\text{softmax}(-\beta_{0}\log p_{\text{stats}}(x^{i})), (38) where \beta_{0}=-1 recovers the data statistics, \beta_{0}=0 yield a uniform distribution on all tokens. Also, \beta_{0}\rightarrow\infty yields a uniform distribution on the set of least probable tokens in the data, which behaves similarly to a mask source distribution. For this experiment, we used linear and kinetic optimal schedulers with mask, p(x)=\delta_{\mathbbm{m}}(x) , and \beta_{0}\in\{-0.5,0.0,0.5,1,2,4,64,256,1024\} source distributions. The models are trained on the FineWeb-Edu ( Lozhkov et al. 2024 ) data set. Table 1 compares the evidence lower bound (ELBO), as in equation 37 , of our trained models with previous works. See Section E.1 for experimental setup. We find that the kinetic optimal scheduler yields the best results on most of the evaluation sets. Notably, to the best of our knowledge, this is the first time a non-mask source distribution obtains comparable results and sometimes outperforms the mask source distribution. Figure 1 presents a view of the generative perplexity (as measured by GPT2-large) vs. the ELBO of each model. Generative perplexity represents the likelihood as determined by an external model, whereas the ELBO indicates the likelihood as assessed by the evaluated model. We see that models trained using the kinetic optimal scheduler achieve better tradeoffs than those trained with the linear scheduler, as they more frequently appear on the Pareto front. Method FID \downarrow D3PM ( Austin et al. 2021 ) 7.34 CTDD ( Nisonoff et al. 2024 ) 7.86 \tau LDR-10 ( Campbell et al. 2022 ) 3.74 DFM w/ mask ( Gat et al. 2024 ) 3.63 DFM w/ metric (Ours) 3.43 Figure 2: ( left ) Increasing the design space of discrete probability paths and velocities allows us to perform better than prior works, while significantly boosting performance at the low NFE regime. ( middle ) We find that the choice of kinetic optimal u_{t}^{\star} significantly affects the low NFE regime while adding the probability-preserving component u_{t}^{\perp} stabilizes the high NFE regime. ( right ) Comparison of FID values for discrete generative models. Table 2: De novo material generation. Our primary metric, Stability Rate , is the fraction of materials with energies below the convex hull formed by stable materials, following Miller et al. 2024 . Method NFE Validity (%) \uparrow Coverage (%) \uparrow Property \downarrow Stability Rate (%) \uparrow Structural Composition Recall Precision wdist ( \rho ) wdist ( N_{el} ) CDVAE ( Xie et al. 2021 ) 5000 100.00 86.70 99.15 99.49 0.688 0.278 1.57 DiffCSP ( Jiao et al. 2023 ) 1000 100.00 83.25 99.71 99.76 0.350 0.125 5.06 FlowMM ( Miller et al. 2024 ) 1000 96.85 83.19 99.49 99.58 0.239 0.083 4.65 CrystalLLM (70B) ( Gruver et al. 2024 ) – 99.6 95.4 85.8 98.9 0.81 0.44 5.28 Autoregressive – 86.43 89.33 63.31 99.74 0.088 0.030 1.99 Perm. invariant DFM - Mask w/ Cubic 250 94.40 84.40 98.25 99.40 0.244 0.144 6.90 Perm. invariant DFM - Mask w/ Kinetic Optimal ( 33 ) 250 95.79 88.50 90.11 99.29 0.542 0.154 7.02 8.2 Crystalline material generation To showcase the flexibility of our approach, we use discrete Flow Matching to generate crystals. We train on inorganic materials from the MP-20 dataset, a subset of the Materials Project database ( Jain et al. 2013 ) . Crystalline materials are represented using a combination of continuous and discrete variables, which we tokenize using the same method as Gruver et al. 2024 , which fine-tunes a 70B LlaMa-2 autoregressive model ( Touvron et al. 2023 ) . In contrast, we are the first to perform crystal generation with a purely discrete non-autoregressive model. An important distinction is that since discrete Flow Matching directly predicts the factorized posterior ( 10 ), we can easily impose permutation invariance of the atoms, which should significantly reduce the complexity of the learning problem. This is as opposed to prior works on using autoregressive models for material generation ( Flam-Shepherd & Aspuru-Guzik 2023 ; Gruver et al. 2024 ) which must impose an unnatural ordering on the variables. We show results in Table 2 where we achieve state-of-the-art results using discrete Flow Matching, in particular, with a kinetic optimal scheduler ( 33 ). We believe non-autoregressive generation is a key ingredient in performing well due to the ability to impose structure such as permutation invariance. Compared to continuous-space models such as FlowMM ( Miller et al. 2024 ) and DiffCSP ( Jiao et al. 2023 ) , we see a large performance gain in terms of our main metric, stability rate ( \geq 38 % relative improvement), from using discrete generative models due to the discrete nature of crystal generation. LlamaGen DFM metric Figure 3: Generated samples for ImageNet 256 \times 256, with the same class label per column. ( top ) Autoregressive LlamaGen model ( Sun et al. 2024 ) . ( bottom ) Discrete Flow Matching with metric-induced probability path ( 27 ). 8.3 Pixel space image generation We first consider the case of image generation in pixel space. Here, {\mathcal{T}}=\{0,\dots,255\} and we have access to a natural choice of metric, by embedding {\mathcal{T}} on the interval [-1,1]\subset\mathbb{R} and using the Euclidean distance \textrm{d}(x,y)=|x-y| in ( 27 ), as is typically done for continuous-space image generative models. We use the CIFAR-10 dataset ( Krizhevsky et al. 2009 ) for these experiments. Results are shown in Figure 2 , where we can improve upon the masked construction while also retaining performance at low number of function evaluations (NFE). Generated samples are shown in Figure 3 and in Appendix G . We find that optimizing the velocity after training can provide significant gains: the choice of probability-advancing velocity ( Section C.3 ) affects the low NFE samples while the adding the probability-preserving component ( Section 5 ) improves at high NFE. 8.4 Discrete latent image generation Table 3: Face-blurred ImageNet-256 with the Llama-B architecture (111M parameters). ∗ denotes our reimplementation. Method NFE FID LlamaGen (AR) ( Sun et al. 2024 ) 256 5.46 LlamaGen (AR) ∗ ( Sun et al. 2024 ) 256 4.81 DFM - Mask ∗ ( Gat et al. 2024 ) 100 5.72 DFM - Metric (Ours) 100 4.50 We also explore the use of discrete Flow Matching as a generative model within a discrete latent space learned by a vector quantized variational autoencoder (VQVAE; Van Den Oord et al. 2017 ). We use images from face-blurred ImageNet ( Deng et al. 2009 ; Chrabaszcz et al. 2017 ) at 256 \times 256 resolution. For training the VQVAE model, we follow the setup in Sun et al. 2024 and use 16 \times downsampling to produce a latent space of dimension 16 \times 16 with a codebook size of |{\mathcal{T}}|=2^{14}=16384 . As our choice of \textrm{d}(\cdot,x_{1}) , we use the same metric that was used to train the VQVAE model, which is \textrm{d}(x,y)=\left\|\nicefrac{{x}}{{\left\|x\right\|}}-\nicefrac{{y}}{{\left\|y\right\|}}\right\| . We show quantitative results in Table 3 , where we find that discrete Flow Matching model with the metric probability path outperforms the autoregressive approach, while the masked construction lags behind. In addition, we show generated samples in Figure 3 and Figure 8 , along with a visualization of the metric probability path in Figure 4 and ablation studies on NFE and CFG scale in Appendix G . 9 Conclusion We have opened up the design space of discrete Flow Matching models based on the the continuous-time Markov chain generative process. In particular, we propose a kinetic optimal point of view for constructing velocities given prescribed probability paths. This leads to, for the first time, allowing arbitrary probability paths to be used. Furthermore, we justify mixture paths with particular schedulers as being kinetic optimal solutions, and showcase for the first time, competitive results for non-mask source distributions. Our method naturally encapsulates existing approaches, and we showcase the flexibility of our approach to designing discrete Flow Matching models across multiple application domains, ranging from text generation, to materials and image generation, where we see significant gains over autoregressive models. Appendix A Always-valid sampling scheme The second step of the sampling scheme defined in Section 3 requires the condition h\leq\frac{1}{\left|u_{t}(z^{i},z^{i},x_{1}^{i})\right|} to be a valid PMF, allowing only small step sizes. To avoid this constraint on h , we use an alternative first-order sampling scheme. We replace step 2 from Section 3 with 2) Sample X_{t+h}^{i}\sim e^{-h\lambda(X_{t}^{i}|X_{1}^{i})}\delta_{X^{i}_{t}}(\cdot)+(1-e^{-h\lambda(X_{t}^{i}|X_{1}^{i})})\frac{u_{t}(\cdot,X^{i}_{t}|X_{1}^{i})}{\lambda(X_{t}^{i}|X_{1}^{i})}(1-\delta_{X^{i}_{t}}(\cdot)) , where \lambda(X_{t}^{i}|X_{1}^{i})=\left|u_{t}(X^{i}_{t},X^{i}_{t}|X_{1}^{i})\right| . Interpreting this expression, e^{-h\lambda(X_{t}^{i}|X_{1}^{i})} is the probability the state does not change. If we do not change state, then we sample from \delta_{X^{i}_{t}}(\cdot) . If we do change state, then we sample from \frac{u_{t}(\cdot,X^{i}_{t}|X_{1}^{i})}{\lambda(X_{t}^{i}|X_{1}^{i})}(1-\delta_{X^{i}_{t}}(\cdot)) , which is a normalized distribution over all states not equal to X_{t}^{i} . This is still a first-order sampling scheme, i.e. it is o(h) error from \mathbb{P}(X_{t+h}^{i}\ |\ X_{t}^{i}) . However, unlike the simple Euler procedure, this alternative is always a valid PMF for any step size h . Algorithm 1 Euler Solver 0: model \theta , x_{0} , h t\leftarrow 0 X_{t}\leftarrow x_{0} while t<1 do for i=0,…,D { in parallel } do X_{1}^{i}\sim p^{\theta,i}_{1|t}(\cdot|X_{t}) \lambda^{i}\leftarrow\left|u^{i}_{t}(X_{t}^{i},X_{t}^{i}|X_{1}^{i})\right| Z^{i}_{\text{jump}}\sim U[0,1] if Z^{i}_{\text{jump}}\leq 1-e^{-h\lambda^{i}} then X_{t}^{i}\sim\frac{u^{i}_{t}(\cdot,X_{t}^{i}|X_{1}^{i})}{\lambda^{i}}\left(1-\delta_{X_{t}^{i}}(\cdot)\right) end if end for t\leftarrow t+h end while return X_{t} Appendix B Symmetrized Kinetic Optimization problem Proposition B.1 (Kinetic-optimal relaxation) . Consider p_{t}>0 and assume \frac{p_{t}(z)}{w_{t}(x,z)}=\frac{p_{t}(x)}{w_{t}(z,x)} . Let f_{t} be a solution to equation 21 , which is unique up to a constant. Then, j^{\star}_{t} in equation 22 is the unique solution to the Kinetic Optimality problem in equation 19 . Proof. Equation 21 is a linear system of equations with |{\mathcal{T}}| equations and |{\mathcal{T}}| variables, that has the form of a discrete Poisson equation ( i.e. , the discrete analog to \Delta f_{t}=\dot{p}_{t} ). As \rho_{t}(x,z)\triangleq\frac{p_{t}(z)}{w_{t}(x,z)}>0 there exists a unique solution to this system up to a constant. Indeed, the quadratic form associated with the linear part of equation 21 is \frac{1}{2}\sum_{x,y}\rho_{t}(x,y)\left[f_{t}(x)-f_{t}(y)\right]^{2}. (39) And since \rho_{t}(x,y)>0 the only function in the kernel is constant. Let \lambda_{t} be a particular solution to equation 21 and define \displaystyle j_{t}(x,y) \displaystyle=\rho_{t}(x,z)\left[\lambda_{t}(x)-\lambda_{t}(y)\right]_{+} \displaystyle\forall x\neq y (40) \displaystyle\mu_{t}(x,y) \displaystyle=\begin{cases}0&\text{ if }j_{t}(x,y)>0\\ \lambda_{t}(y)-\lambda_{t}(x)&\text{ if }j_{t}(x,y)=0\end{cases} \displaystyle\forall x\neq y (41) Now consider the optimization problem in equation 19 . Since \rho_{t}(x,z)>0 it is strictly convex and therefore has at most a single solution. Furthermore, if the constraint set is non-empty then the KKT conditions are necessary and sufficient for a solution. Note that j_{t} defined in equation 40 satisfies the constraints in equation 19 . Indeed, it is clearly non-negative, and \displaystyle\mathrm{div}_{x}j_{t} \displaystyle=\sum_{z\neq x}j_{t}(z,x)-\sum_{z\neq x}j_{t}(x,z) (42) \displaystyle=\sum_{z\neq x}\rho_{t}(x,z)\left[\lambda_{t}(z)-\lambda_{t}(x)\right]_{+}-\rho_{t}(x,z)\left[\lambda_{t}(x)-\lambda_{t}(z)\right]_{+} (43) \displaystyle=\sum_{z\neq x}\rho_{t}(x,z)\left[\lambda_{t}(z)-\lambda_{t}(x)\right] (44) \displaystyle\overset{(\ref{e:relaxation_lambda})}{=}-\dot{p}_{t}(x) (45) Therefore the optimization problem in equation 19 is feasible. This in particular means that the KKT conditions are both necessary and sufficient. For each t\in[0,1] we denote the dual variables \lambda_{t}:[d]\rightarrow\mathbb{R} and \mu_{t}:[d]\times[d]\rightarrow\mathbb{R} , and the KKT equations take the form: \displaystyle\frac{j_{t}(x,y)}{\rho_{t}(x,y)}+\lambda_{t}(y)-\lambda_{t}(x) \displaystyle=\mu_{t}(x,y) \displaystyle\forall x\neq y \displaystyle\quad\blacktriangleright\text{stationary} (46a) \displaystyle\sum_{y}\left[j_{t}(y,x)-j_{t}(x,y)\right] \displaystyle=-\dot{p}_{t}(x) \displaystyle\forall x \displaystyle\quad\blacktriangleright\text{primal feasibility} (46b) \displaystyle j_{t}(x,y) \displaystyle\geq 0 \displaystyle\forall x\neq y \displaystyle\quad\blacktriangleright\text{primal feasibility} (46c) \displaystyle\mu_{t}(x,y) \displaystyle\geq 0 \displaystyle\forall x\neq y \displaystyle\quad\blacktriangleright\text{dual feasibility} (46d) \displaystyle\mu_{t}(x,y)j_{t}(x,y) \displaystyle=0 \displaystyle\forall x\neq y \displaystyle\quad\blacktriangleright\text{complementary slackness} (46e) Now one can verify that j_{t} and \mu_{t} defined in equation 40 and equation 41 (respectively) solve the KKT. The primal feasibility is already checked above. Let us check the stationary condition: \displaystyle\frac{j_{t}(x,y)}{\rho_{t}(x,y)}+\lambda_{t}(y)-\lambda_{t}(x) \displaystyle=\begin{cases}0&\lambda_{t}(x)-\lambda_{t}(y)>0\\ \lambda_{t}(y)-\lambda_{t}(x)&\lambda_{t}(x)-\lambda_{t}(y)\leq 0\end{cases} (47) \displaystyle=\begin{cases}0&j_{t}(x,y)>0\\ \lambda_{t}(y)-\lambda_{t}(x)&j_{t}(x,y)=0\end{cases} (48) \displaystyle\overset{(\ref{ea:mu_in_proof})}{=}\mu_{t}(x,y) (49) Lastly, dual feasibility and complementary slackness hold by definition in equations 40 and 41 . ∎ Proposition B.2 (Kinetic Optimal paths.) . For p_{t}>0 and the choice of w_{t}(x,z)=\frac{1}{p_{t}(x)} , the solution to the Kinetic Optimality problem in equation 19 is equivalent to problem 30 . Proof. According to equation 22 the optimal flux in this case takes the form j_{t}^{*}(x,z)=p_{t}(x)p_{t}(x)\left[\frac{\dot{p}_{t}(x)}{p_{t}(x)}-\frac{\dot{p}_{t}(z)}{p_{t}(z)}\right]_{+} . Plugging this in problem 19 we get the energy \displaystyle\sum_{x,z}p_{t}(x)p_{t}(z)\left(\frac{\dot{p}_{t}(x)}{p_{t}(x)}-\frac{\dot{p}_{t}(z)}{p_{t}(z)}\right)_{+}^{2} \displaystyle=\frac{1}{2}\sum_{x,z}p_{t}(x)p_{t}(z)\left(\frac{\dot{p}_{t}(x)}{p_{t}(x)}-\frac{\dot{p}_{t}(z)}{p_{t}(z)}\right)^{2} \displaystyle=\sum_{x}p_{t}(x)\left(\frac{\dot{p}_{t}(x)}{p_{t}(x)}\right)^{2}-\left(\sum_{x}p_{t}(x)\frac{\dot{p}_{t}(x)}{p_{t}(x)}\right)^{2} \displaystyle=\sum_{x}\left(\frac{\dot{p}_{t}(x)}{\sqrt{p_{t}(x)}}\right)^{2} \displaystyle=2\sum_{x}\left(\frac{d}{dt}\sqrt{p}_{t}(x)\right)^{2} where in the previous to last equality we used the fact that \sum_{x}\dot{p}_{t}(x)=\frac{d}{dt}\sum_{x}p_{t}(x)=0 . We are left with the following optimization problem: \textstyle\min_{p_{t}} \textstyle\quad\int_{0}^{1}\sum_{x}\left(\frac{d}{dt}\sqrt{p}_{t}(x)\right)^{2} (50a) \textstyle\quad p_{t}(x)>0 (50b) \textstyle\quad\sum_{x}p_{t}(x)=1 (50c) \textstyle\quad p_{0}=p,\quad p_{1}=q (50d) Making the change of variables a_{t}(x)=\sqrt{p_{t}(x)} , we get the form in equation 30 , as desired. ∎ The case of q=\delta_{x_{1}} . Given that q=\delta_{x_{1}} we get that the Kinetic Optimal solution equation 32 takes a form of a mixture path (equation 2 ) with the scheduler specified in equation 33 . Specifically we show that the probability path is \displaystyle p_{t}(x|x_{1}) \displaystyle=a^{2}_{t}(x)=\frac{\sin^{2}{(1-t)\Omega}}{\sin^{2}\Omega}p(x)+\left(1-\frac{\sin^{2}{(1-t)\Omega}}{\sin^{2}\Omega}\right)\delta_{x_{1}}(x), (51) and the velocity is u_{t}(x,z|x_{1})=\frac{2\Omega}{\tan{(1-t)\Omega}}\left(\delta_{x_{1}}(x)-\delta_{z}(x)\right). (52) We start by substituting the q\equiv\delta_{x_{1}} in equation 31 , \displaystyle a_{t}(x)=\frac{\sin(1-t)\Omega}{\sin\Omega}\sqrt{p(x)}+\frac{\sin t\Omega}{\sin\Omega}\delta_{x_{1}}(x). (53) Hence the probability path is \displaystyle p_{t}(x|x_{1}) \displaystyle=\left(\frac{\sin(1-t)\Omega}{\sin\Omega}\sqrt{p(x)}+\frac{\sin t\Omega}{\sin\Omega}\delta_{x_{1}}(x)\right)^{2} (54) \displaystyle=\frac{\sin^{2}(1-t)\Omega}{\sin^{2}\Omega}p(x)+\left(\frac{2\sqrt{p(x_{1})}\sin(1-t)\Omega\sin t\Omega}{\sin^{2}\Omega}+\frac{\sin^{2}t\Omega}{\sin^{2}\Omega}\right)\delta_{x_{1}}(x) (55) \displaystyle=\frac{\sin^{2}(1-t)\Omega}{\sin^{2}\Omega}p(x)+\left(\frac{2\cos\Omega\sin(1-t)\Omega\sin t\Omega}{\sin^{2}\Omega}+\frac{\sin^{2}\left(\Omega-(1-t)\Omega\right)}{\sin^{2}\Omega}\right)\delta_{x_{1}}(x) (56) \displaystyle=\frac{\sin^{2}(1-t)\Omega}{\sin^{2}\Omega}p(x)+\biggr(\frac{2\cos\Omega\sin(1-t)\Omega\sin\left(\Omega-(1-t)\Omega\right)}{\sin^{2}\Omega} (57) \displaystyle\qquad\qquad\qquad\qquad\qquad\quad+\frac{\left(\sin\Omega\cos(1-t)\Omega-\cos\Omega\sin(1-t)\Omega\right)^{2}}{\sin^{2}\Omega}\biggr)\delta_{x_{1}}(x) (58) \displaystyle=\frac{\sin^{2}(1-t)\Omega}{\sin^{2}\Omega}p(x)+\biggr(\frac{-\cos^{2}\Omega\sin^{2}(1-t)\Omega}{\sin^{2}\Omega}+\frac{\sin^{2}\Omega\cos^{2}(1-t)\Omega}{\sin^{2}\Omega}\biggr)\delta_{x_{1}}(x) (59) \displaystyle=\frac{\sin^{2}(1-t)\Omega}{\sin^{2}\Omega}p(x)+\biggr(\frac{-(1-\sin^{2}\Omega)\sin^{2}(1-t)\Omega}{\sin^{2}\Omega} (60) \displaystyle\qquad\qquad\qquad\qquad\qquad\quad+\frac{\sin^{2}\Omega(1-\sin^{2}(1-t)\Omega)}{\sin^{2}\Omega}\biggr)\delta_{x_{1}}(x) (61) \displaystyle=\frac{\sin^{2}(1-t)\Omega}{\sin^{2}\Omega}p(x)+\biggr(1-\frac{\sin^{2}(1-t)\Omega}{\sin^{2}\Omega}\biggr)\delta_{x_{1}}(x), (62) where in the third equality we used \Omega=\arccos\sqrt{p(x_{1})} . Substituting \kappa_{t}(x_{1})=1-\frac{\sin^{2}(1-t)\Omega}{\sin^{2}\Omega} (63) in equation 72 yields the desired velocity as in equation 52 . Appendix C Closed-form kinetic optimal velocities C.1 Kinetic optimal velocities for mixture paths We examine the velocities from the kinetic optimal fluxes given in ( 24 ) and ( 26 ) under mixture paths ( 2 ). We show ( 24 ) and ( 26 ) produce the same velocity for the uniform mixture for which p(x)=1/|{\mathcal{T}}| , and different velocities for non-uniform mixtures. We also demonstrate our kinetic optimal velocity from ( 26 ) is the velocity proposed by Gat et al. 2024 for any mixture path. Positive mixture paths using ( 24 ): For ( 24 ), we only consider mixture paths for which p_{t}(x|x_{1})>0 for all x\in{\mathcal{T}} , including uniform p(x)=1/|{\mathcal{T}}| as a special case. For these mixture paths, where we recall that x\neq z , we have \displaystyle u^{\star}_{t}(x,z|x_{1}) \displaystyle=\frac{\left[\partial_{t}p_{t}(x|x_{1})-\partial_{t}p_{t}(z|x_{1})\right]_{+}}{|{\mathcal{T}}|p_{t}(z|x_{1})} \displaystyle=\frac{\dot{\kappa}_{t}(x_{1})\left[\delta_{x_{1}}(x)-\delta_{x_{1}}(z)+p(z)-p(x)\right]_{+}}{|{\mathcal{T}}|p_{t}(z|x_{1})} (64) We now examine the uniform and arbitrary p(x)>0 cases separately. Uniform mixture using ( 24 ): For uniform, we have for x\neq z \displaystyle u^{\star}_{t}(x,z|x_{1}) \displaystyle=\frac{\dot{\kappa}_{t}(x_{1})\left[\delta_{x_{1}}(x)-\delta_{x_{1}}(z)+p(z)-p(x)\right]_{+}}{|{\mathcal{T}}|p_{t}(z|x_{1})} \displaystyle=\frac{\dot{\kappa}_{t}(x_{1})\left[\delta_{x_{1}}(x)-\delta_{x_{1}}(z)\right]_{+}}{|{\mathcal{T}}|p_{t}(z|x_{1})} (65) This is only positive if x=x_{1} and z\neq x_{1} . In which case, we have \displaystyle u^{\star}_{t}(x_{1},z\neq x_{1}|x_{1}) \displaystyle=\frac{\dot{\kappa}_{t}(x_{1})\left[1-0\right]_{+}}{1-\kappa_{t}(x_{1})} \displaystyle=\frac{\dot{\kappa}_{t}(x_{1})}{1-\kappa_{t}(x_{1})} (66) So in total we have \displaystyle u^{*}_{t}(x,z|x_{1})=\frac{\dot{\kappa_{t}}(x_{1})}{1-\kappa_{t}(x_{1})}(\delta_{x_{1}}(x)-\delta_{z}(x)) (67) Arbitrary p(x)>0 using ( 24 ): For a non-uniform positive p(x) we do not arrive at the same velocity as the uniform mixture. Consider x\neq z , x\neq x_{1} , and z\neq x_{1} , then \displaystyle u^{\star}_{t}(x\neq x_{1},z\neq x_{1}|x_{1}) \displaystyle=\frac{\dot{\kappa}_{t}(x_{1})\left[p(z)-p(x)\right]_{+}}{|{\mathcal{T}}|p_{t}(z|x_{1})}. (68) This is not zero if p(z)>p(x) for any pair of z and x , proving this is a different velocity in general. Arbitrary mixture paths using ( 26 ): Substituting in the mixture path, where we recall that x\neq z and p_{t}(z|x_{1})>0 , we have \displaystyle u^{\star}_{t}(x,z|x_{1}) \displaystyle=\frac{1}{p_{t}(z|x_{1})}\left[\partial_{t}p_{t}(x|x_{1})p_{t}(z|x_{1})-\partial_{t}p_{t}(z|x_{1})p_{t}(x|x_{1})\right]_{+} \displaystyle=\dot{\kappa_{t}}(x_{1})\left[\delta_{x_{1}}(x)-p(x)-\frac{p_{t}(x|x_{1})}{p_{t}(z|x_{1})}(\delta_{x_{1}}(z)-p(z))\right]_{+} (69) We consider several cases. First, x\neq x_{1} and z=x_{1} , then the term in brackets is negative and hence u_{t}^{*}=0 . Second if x\neq x_{1} and z\neq x_{1} , we have \displaystyle u^{\star}_{t}(x\neq x_{1},z\neq x_{1}|x_{1}) \displaystyle=\dot{\kappa_{t}}(x_{1})\left[-p(x)+\frac{p_{t}(x|x_{1})p(z)}{p_{t}(z|x_{1})}\right]_{+} \displaystyle=\dot{\kappa_{t}}(x_{1})\left[-p(x)+\frac{(1-\kappa_{t}(x_{1}))p(x)p(z)}{(1-\kappa_{t}(x_{1}))p(z)}\right]_{+} \displaystyle=0. (70) Our final case, x=x_{1} and z\neq x_{1} , gives \displaystyle u^{\star}_{t}(x_{1},z\neq x_{1}|x_{1}) \displaystyle=\dot{\kappa_{t}}(x_{1})\left[1-p(x_{1})+\frac{\left((1-\kappa_{t}(x_{1}))p(x_{1})+\kappa_{t}(x_{1})\right)p(z)}{(1-\kappa_{t}(x_{1}))p(z)}\right]_{+} \displaystyle=\frac{\dot{\kappa_{t}}(x_{1})}{1-\kappa_{t}(x_{1})}\left[(1-\kappa_{t}(x_{1}))(1-p(x_{1}))+(1-\kappa_{t}(x_{1}))p(x_{1})+\kappa_{t}(x_{1})\right]_{+} \displaystyle=\frac{\dot{\kappa_{t}}(x_{1})}{1-\kappa_{t}(x_{1})} (71) So in total for any mixture path we have \displaystyle u^{*}_{t}(x,z|x_{1})=\frac{\dot{\kappa_{t}}(x_{1})}{1-\kappa_{t}(x_{1})}(\delta_{x_{1}}(x)-\delta_{z}(x)), (72) recovering the velocity proposed in Gat et al. 2024 . C.2 Marginal velocity in closed-form for mixture paths As shown in Appendix C.1 , the kinetic optimal flux given by ( 26 ) results in kinetic optimal velocity ( 72 ) for mixture paths. To derive the marginal velocity, we insert ( 72 ) into ( 9 ) as follows \displaystyle u_{t}^{i}(x^{i},z) \displaystyle=\sum_{x_{1}^{i}\in{\mathcal{T}}}u_{t}(x^{i},z^{i}|x_{1}^{i})p^{i}_{1|t}(x_{1}^{i}|z) \displaystyle=\sum_{x_{1}^{i}\in{\mathcal{T}}}\frac{\dot{\kappa_{t}}(x^{i}_{1})}{1-\kappa_{t}(x^{i}_{1})}(\delta_{x^{i}_{1}}(x^{i})-\delta_{z^{i}}(x^{i}))p^{i}_{1|t}(x_{1}^{i}|z) \displaystyle=\frac{\dot{\kappa}_{t}(x^{i})}{1-\kappa_{t}(x^{i})}p^{i}_{1|t}(x^{i}|z)-\delta_{z^{i}}(x^{i})\sum_{x_{1}^{i}\in{\mathcal{T}}}\frac{\dot{\kappa}_{t}(x_{1}^{i})}{1-\kappa_{t}(x_{1}^{i})}p^{i}_{1|t}(x_{1}^{i}|z). (73) C.3 Power \infty velocity for general paths We begin by defining a single parameter family of kinetic optimal velocities. For every \alpha>1 the flux as in equation 22 for \tau_{t}(x)=p_{t}^{\alpha}(x) is j_{t}^{\star}(x,z)=p_{t}^{\alpha}(x)p_{t}^{\alpha}(z)\left[f_{t}(x)-f_{t}(z)\right]_{+},\quad f_{t}(x)=\frac{1}{\sum_{s\in{\mathcal{T}}}p_{t}^{\alpha}(s)}\frac{\dot{p}_{t}(x)}{p_{t}^{\alpha}(x)}. (74) Further simplifying j_{t}^{\star}(x,z) , \displaystyle j_{t}^{\star}(x,z) \displaystyle=\left[\dot{p}_{t}(x)\frac{p_{t}^{\alpha}(z)}{\sum_{s\in{\mathcal{T}}}p_{t}^{\alpha}(s)}-\dot{p}_{t}(z)\frac{p_{t}^{\alpha}(x)}{\sum_{s\in{\mathcal{T}}}p_{t}^{\alpha}(s)}\right]_{+}. (75) An interesting case of the flux above is taking the limit \alpha\rightarrow\infty , where \frac{p_{t}^{\alpha}(x)}{\sum_{s\in{\mathcal{T}}}p_{t}^{\alpha}(s)}\xrightarrow[\alpha\rightarrow\infty]{}\delta_{\argmax_{s}(p_{t}(s))}(x), (76) and the flux is j_{t}^{\star}(x,z)=\left[\dot{p}_{t}(x)\delta_{\argmax_{s}(p_{t}(s))}(z)-\dot{p}_{t}(z)\delta_{\argmax_{s}(p_{t}(s))}(x)\right]_{+}. (77) Indeed the above flux satisfy the Continuity Equation and the Rate Conditions as in Indeed the above flux satisfy the Continuity Equation and the Rate Conditions as in equation 17 . Note that it can also be seen that j_{t}^{\star}(x,z)\xrightarrow[p_{t}(z)\rightarrow 0]{}0. (78) Appendix D Evidence lower bound (ELBO) for CTMC Let 0=t_{0}