acceptodds
Under review as a conference paper at ICLR 2027

Minimal Travel Sampling for Metric Path Discrete Flow Models

12 views

Abstract

Discrete flow models built on metric-induced probability paths have emerged as a strong approach to image and video synthesis, yet their fast sampling remains underexplored. In this paper, we propose the travel-optimal (TO) sampler, a training-free sampler for fast generation with pretrained discrete flow models. Our key observation is that a sampler simulating the underlying continuous-time Markov chain on a finite time grid can represent at most one jump per token within each step, so how much probability moves within a step largely determines the generation quality under a limited number of function evaluations (NFE). Motivated by this, we seek the probability flux with minimal total travel cost, defined as the expected distance traveled by probability mass. Since infinitely many rates generate the same probability path, this flux is a free design choice. We show that this problem reduces to optimal transport and propose row-Sinkhorn to solve its entropic OT relaxation efficiently for large vocabularies. We further reduce the remaining scheduler error through temporal integration, and our error analysis shows that the sampling error is bounded by a term proportional to the total travel cost. Extensive experiments show that TO improves image generation quality over the default sampler by up to 37% in GenEval at low NFE and video generation quality by up to 3.7 points in VBench, consistently across different models and against various baselines.

Primary area:
generative models
Keywords:
visual generation, discrete flow matching

Reviews

Among:
Shape:
1234this paper, Top 1%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 4.00 over 3 reviews, above 99% of the others.
Reviewer_hQjFOpenReview ↗
Rating
4(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper proposed the travel-optimal sampler for few-step generation by seeking probability flux with minimal total travel cost. The theoretical error analysis is presented, and the experimental results show that the proposed method is effective and competitive.

Critical strengths
  1. The proposed sampler is novel and can be obtained by optimizing the generating flux. The flux can be freely designed under the detailed balance condition (Lemma 1).
  2. The theoretical error analysis of the proposed sampler is derived.
  3. The experimental results are promising, demonstrating that the proposed sampler is effective.
Critical weaknesses
  1. There are some quantities appearing for the first time without definition or sufficient explanation, such as a^\hat{a} in line 262. Additionally, the sentence in line 309 is incomplete; Proposition 1 just appears in the main paper without discussion.
  2. There are no comparison results with other samplers (beyond AVE and corrected samplers proposed by Wan et al. ), such as higher-order samplers proposed by Ren et al. (2026). The results with other models like FUDOKI seem to be limited.
Questions for authors
  1. Could the authors explain the relationship between the results in Section 4.2 and the results in Shaul et al. (2025)?
  2. How should we analyze the theoretical results in the paper compared to existing works, such as Wan et al. (2026) mentioned in the paper? Is the proposed sampler better than other samplers theoretically (some discussion is welcome)?
  3. In experiments, I noticed that the proposed method achieves the best performance among the selected competing samplers for image generation with URSA. I am also curious about the experimental results of the proposed method compared with higher-order discrete samplers proposed by Ren et al. (2026). Also, more results (for comparison between the proposed method and competing samplers beyond AVE) for other models like FUDOKI could strengthen the evidence for the effectiveness of the proposed method. I think some metric (e.g., GenEval) vs. sampling time figures would be helpful for readers to identify the performance of the method.
3 comments
AuthorsOpenReview ↗

Response to Reviewer hQjF

We thank the reviewer for the positive evaluation and constructive feedback, and for recognizing the novelty of the sampler, the error analysis, and the experimental results. We address the comments below.

[W1] Notation and presentation. We thank the reviewer for the careful reading. In the revision, we refer back to the definition of â (Section 2.2) where it is used in Section 4.3, and complete the sentence introducing Proposition 1. We have also checked the remaining notation throughout the paper.

[W2,Q3] Comparison with other samplers and results on FUDOKI. Please see G1 for the comparison with the high-order sampler of Ren et al. and G2 for the extended FUDOKI comparison against AVE, Corr-T, Corr-L, and RK-2.

[Q1] Relation to the kinetic-optimal (KO) flux of Shaul et al. (2025). We thank the reviewer for this question. The difference from KO is central to our contribution, so we explain it in detail. Both KO and TO choose a flux among the many that generate the same probability path, but they optimize different objectives, and this leads to different behavior. For a current token bb and target aa, with dˉt(a)=∑b′pt(b′∣a) d(b′,a)\bar d_t(a) = \sum_{b'} p_t(b' \mid a)\, d(b', a), the two compare as follows.

KO (Shaul et al., 2025)TO (ours)
Objective∑x≠ypt(x)Rt(x,y)2wt(x,y)\sum_{x \neq y} p_t(x)R_t(x,y)^2 w_t(x,y)∑x≠ypt(x)Rt(x,y)c(x,y)\sum_{x \neq y} p_t(x)R_t(x,y) c(x,y)
Jump intensity out of bbβ˙t∑b′pt(b′∣a)[d(b,a)−d(b′,a)]+\dot\beta_t \sum_{b'} p_t(b' \mid a)[d(b,a) - d(b',a)]_+β˙t[∑b′pt(b′∣a)(d(b,a)−d(b′,a))]+\dot\beta_t\big[\sum_{b'} p_t(b' \mid a) (d(b,a) - d(b',a))\big]_+
Destination distribution∝pt(b′∣a)[d(b,a)−d(b′,a)]+\propto p_t(b' \mid a) [d(b,a) - d(b',a)]_+∝pt(b′∣a)[dˉt(a)−d(b′,a)]+e−c(b,b′)/ε\propto p_t(b' \mid a) [\bar d_t(a) - d(b',a)]_+e^{-c(b,b')/\varepsilon}

Objective. KO minimizes a quadratic (kinetic) cost. Under a quadratic cost it is cheaper to spread the flux thinly over many transitions, so mass is often routed through intermediate tokens, which creates jumps that are not needed to realize the path. TO minimizes a linear transport cost. Since cc is a metric, a detour can never reduce the cost, and sending mass directly to its destination is optimal. We also note that the weight wtw_t in KO serves mainly to make the objective symmetric, rather than to encode a semantic distance between tokens, whereas cc in TO is the distance itself.

Jump intensity. In KO the expectation over b′b' sits outside the ReLU, while in TO it sits inside. As a result, under TO only tokens whose probability is decreasing emit mass, and mass flows only to tokens whose probability is increasing. Under KO, a token can emit mass even when its own probability is not decreasing, as long as some b′b' is closer to the target.

Destination. In KO, the current token bb affects the destination only through the scalar d(b,a)d(b,a), so a jump goes to any token near the target regardless of where bb is. TO multiplies in a locality kernel e−c(b,b′)/εe^{-c(b,b')/\varepsilon}, so mass moves toward tokens that are close to the target and also not far from the current token. This is the locality-aware property that Reviewer 2gYT also highlighted.

We have added this comparison to Appendix E.

[Q2] Theoretical comparison with prior work. We would like to highlight two differences.

Comparison with Wan et al. (2026). Prior analyses, including Wan et al., mostly consider the uniform and masked paths common in discrete diffusion. As discussed in our response to Reviewer BUms (W2), in these paths the flux either leaves or arrives at a single state, so the OT coupling is unique and the default rate is already travel-optimal. Since there is no room to improve the rate itself, these works naturally focus on improving the integrator for a fixed rate. In contrast, we show that for more general paths, where both the source and the destination of the flux are spread over many states (the metric path being the main example), the choice of rate becomes a substantial degree of freedom, and that optimizing it further reduces the finite-step error. The two directions are complementary, as the combination with RK-2 in G1 also shows.

Comparison with KO (Shaul et al., 2025). Our bound on the finite-step error (Theorem 2) is quite loose, but its constants HkH_k and ℓk\ell_k do not depend on the choice of rate. The rate enters only through the jump intensity and the travel cost. Our rate attains the minimal jump intensity in closed form and approximately minimizes the travel cost, so both rate-dependent terms are no larger than those of KO. Since these terms do not depend on the integrator, the comparison is not tied to AVE and carries over when our rate is combined with other integrators.

We have added this discussion to Appendix A.

[Q3] Higher-order samplers, FUDOKI, and sampling time. Please see G1, G2, and G3. The plot of GenEval against wall-clock time is in Figure 7 (Appendix F.4).

Thank you for your additional discussion and results, which addresses my main concerns. I will raise my score to 4.

Thank you for the follow-up. We are glad the additional results were helpful, and appreciate your thoughtful feedback throughout the discussion. Please feel free to let us know if there is anything further.

Reviewer_BUmsOpenReview ↗
Rating
4(+1)
Confidence
3(+1)
Informativeness
3
Presentation
3(+1)
Soundness
3
Read review
Paper summary

This paper addresses the problem that, in few-step sampling of metric-path discrete flow models, each token can jump only once per step based on the current prediction, and the default jump rate tends to produce large, erratic jumps. It proposes to choose, among all jump rates that generate the same probability path, the one with the minimal total travel distance (shown to be equivalent to optimal transport), and implements it efficiently with a row-Sinkhorn approximation. Experiments on image and video generation with URSA and FUDOKI show clear improvements at 4–8 steps. However, the distribution bias introduced by the approximation is not quantified, the evaluation is very small apart from GenEval, and the range of applicable models is narrow.

Critical strengths

(1) The idea is novel: instead of changing the integration scheme, it exploits the non-uniqueness of the jump rate to choose a rate that a few-step sampler can follow more easily. The theoretical derivation is concise and verifiable.

(2) The gains are clear and the cost is small.

Critical weaknesses

(1) Comparisons with high-order discrete solvers are missing, e.g., RK2-type methods, which also target the few-step regime.

(2) The scope of applicability is narrow: the method only targets metric-path discrete flows, and there are currently very few large-scale models of this kind. Can it be extended to masked discrete diffusion, or to other discrete data such as text or proteins?

(3) Strictly speaking, the optimality holds only for a single coordinate with a single target; there is no guarantee once it is applied to the actual sampler.

(4) "TO makes the upper bound smaller" does not mean "TO makes the error smaller". This bound cannot quantitatively explain where the gains come from, and this part should be stated more rigorously.

(5) A comparison with "the default rate plus a well-tuned time grid" is needed, to rule out the possibility that the gains actually come from a poorly tuned schedule.

Questions for authors

pls see weaknesses.

2 comments
AuthorsOpenReview ↗

Response to Reviewer BUms

We thank the reviewer for the positive evaluation and constructive feedback, and for finding the idea of choosing among rates that generate the same path novel and the derivation easy to verify. We address the comments below.

[W1] Comparison with high-order samplers. Please see G1. TO is complementary to the choice of sampler and improves RK-2 as well. At matched NFE, AVE + TO remains the strongest configuration in the lowest-budget setting.

[W2] Scope. We would like to clarify that the metric path is actually a more general setting than the mixture paths (masked or uniform paths). Discrete flow matching (Gat et al., 2024; Shaul et al., 2025) allows arbitrary per-token conditional paths between the source and data distributions, beyond mixture paths, and the metric path is one instance of this general family. Mixture paths are special cases in which the flux either leaves a single state (the mask token) or arrives at a single state (the target token). In that case the OT coupling is unique and the default rate is already travel-optimal, so there is nothing left to design. For more general paths, however, the choice of rate becomes a substantial degree of freedom, and optimizing it further reduces the finite-step error. Our theory (Lemma 1, Theorem 1, Corollary 1) covers this general setting and is not restricted to metric paths.

As path design that reflects the structure of the domain becomes more common, we expect the range of settings where TO applies to grow with it. Since TO is training-free, applying it to text or protein data only requires a pretrained model with such a path in that domain. At present, however, large-scale models of this kind are concentrated in text-to-image and text-to-video generation, which is why we evaluated TO there, and we see text and protein data as a natural next step. We have added this discussion to Section 4.2 (Remark 1).

[W3] Optimality for a single coordinate and target. We agree. Strictly speaking, the flux is optimal for each conditional path, and this does not imply optimality for the marginal path. We have revised the wording in Section 4.2 accordingly.

[W4] Upper bound versus actual error. We agree with this distinction. The bound is intended to identify which quantities govern the finite-step error and to motivate the choice of rate, not to explain the size of the gains quantitatively. We have revised Section 5 to make this explicit (see also our response to 2gYT W1).

[W5] Default rate with a tuned time grid. We swept the time-shift parameter of the grid for both rates at NFE 4 (URSA, GenEval).

shift234 (default)6812162432
AVE0.3400.3920.4380.4690.4900.5070.5090.4900.485
TO0.6220.6340.6460.6620.6630.6280.6170.5980.564

Tuning the grid partly compensates for the default rate, but its best setting still falls well short of TO, which is ahead at every shift. TO is also less sensitive to the choice of grid. We therefore note that the gains do not come from a poorly tuned schedule. We have added this result to Appendix F.3.

Thanks for the rebuttal. After reviewing the other reviewers' scores, I've decided to raise my original score to 4. Best of luck with the final decision!

Reviewer_2gYTOpenReview ↗
Rating
4
Confidence
4
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

The goal of the paper is to accelerate sampling of discrete flow models. Specifically, the paper proposed a new Continuous Time Markov Chain (CTMC) transition rate that leads to better performance at low number of function evaluation (NFE) sampling. Notably, the new transition rate affects only inference and can be used with existing discrete flow models without any fine tuning of the weights.

Discrete flow models learn a CTMC process that takes some source distribution to the target distribution. The design space of these models include the per-token conditional path and the per token conditional transition rate, the two are relate through the the Kolmogorov forward equation. The path is fixed during training, but the rate is a design choice of the sampling algorithm. In particular, for a fixed path there exists many rates that generate it.

Regarding the path, the authors assume there exists a metric between any two tokens, and they consider a metric-induced path. They do not train new models, and validate their method on two existing text-to-image text-to-video discrete models that where trained with such a path.

The core idea of the paper is to select a transition rate by minimizing the travel cost which is the expected distance (in terms of the metric in the embedding space) that a token does during sampling. The motivation for this choice is to minimize the jump intensity during sampling which leads to lower error since:

  1. At each step tokens are sampled independently, and lower jump intensity will reduce the number of changing tokens.

  2. CTMC simulation algorithms allows a single jump at each step, lower jump intensity keeps the probability of jumping more than once lower for larger intervals.

The core contribution of the paper:

  1. Observing that jump intensity control is critical for lowering the error of CTMC simulation at low NFE.

  2. Providing a closed form formula for the travel cost optimal jump intensity and proving that it is minimal.

  3. Providing a closed form formula that approximate the optimal travel cost flux using row-Sinkhorn. Interestingly, the proposed per-token conditional flux is dependent on the distance between the current and the target tokens. This is in contrast the baseline, the kinetic optimal per-token conditional flux, which depends only on distances w.r.t. to the token predicted by the posterior (i.e., the model).

  4. Validating empirically that the proposed rate improves performance in low NFE sampling on a text-to-image and a text-to-video models.

Critical strengths

The proposed sampling method is presented clearly, and it is well motivated both theoretically and empirically. The two most critical strengths I found are:

  1. The authors are I able solve in closed form the minimal jump intensity. Additionally, the approximation for the travel cost optimal flux contains a dependency on the distance between the current and target tokens. This was not exists in previous transition rates and appears very interesting to me.

  2. The proposed sampling method improves upon the baseline without any training required, only by optimizing the sampler. Thus, it is likely to be adopted.

Critical weaknesses

I did not find any critical weaknesses of the paper. However I will note a few points which worth addressing.

  1. The Theoretical Analysis section is hard to follow. Specifically, the resulted bounds in equations 21 and 22 contains many constants, some of which appears to be very large. For example Hk=sup⁡t∈Ikβ˙t⋅dmax⁡, ℓk=dmax⁡⋅sup⁡t∈IkβtH_k = \sup_{t\in I_k}\dot\beta_t \cdot d_{\max},\ \ell_k = \sqrt{d_{\max}} \cdot \sup_{t\in I_k}\beta_t. Since βt→∞\beta_t\rightarrow\infty these could actually be quite large and thus it is not clear to me how meaningful the provided bounds. In particular since the case interest is not some asymptotic behaviour but rather a finite step size.

  2. In section 3, optional but It might be worth to point more clearly that some of the error is resulted from changing more than one token at each step.

  3. In the experiment section tables are arranged w.r.t. to number of sampling step. However, if I understood correctly not all methods use the same NFE at each step. I would recommend rearranging the tables according to NFE and noting the number of steps per methods. In practice, the quantity of interest is NFE and not number of steps. Currently it appears that on Table 1 the Corr-L baseline is very close to the proposed method, but then on Table 4 it shows double the latency.

  4. PSNR is some what ill-defined. The samplers are stochastic so even starting from the same noise and running the sampler twice with different seed will probably lead to different images. Even at same seed for the sampling process, once the number of steps is changed than its not clear that it should reach the same image. Indeed the PSNR metric stays quite low. Might worth reporting what is the PSNR when sampling with 32 NFE multiple times.

Questions for authors

Mostly If the authors could clarify weakness number 3.

1 comment
AuthorsOpenReview ↗

Response to Reviewer 2gYT

We sincerely thank the reviewer for the strong support of our work and for the thorough and insightful review, in particular for highlighting the closed-form minimal jump intensity and the locality-aware design of the travel-optimal flux. We address the comments below.

[W1] Constants in the bound. In practice, sampling is early-stopped before t = 1, so β_t remains finite and the constants do not diverge. We agree, however, that they can still be large, and that the bound is not meant to be quantitatively tight at a finite step size. Rather, it is meant to show which quantities enter the finite-step error and which of them depend on the rate. The terms H_k and ℓ_k depend only on the path and the time grid, so they are the same for every rate that generates the path, and the rate enters only through the jump intensity and the travel intensity. The bound is therefore informative as a comparison between rates on the same path, even when its absolute value is quite loose. We have revised Section 5 to state this role explicitly.

[W2] Error from multiple tokens changing in one step. We agree that this point deserves to be stated explicitly. We have added it to Section 3.2.

[W3, Q] Steps versus NFE. We originally compared methods per step because Corr-L stochastically uses one or two NFE per step by design, which made it difficult to place all methods in a single column per NFE budget. At N = 4096, however, Corr-L in fact uses two evaluations at every step, so the step-based tables compared it at roughly twice our NFE. Following the reviewer's suggestion, we have reorganized Table 1 by NFE (see G3).

[W4] PSNR. We also agree that PSNR to a reference sample is not a well-defined quality metric for a stochastic sampler. We included it because, with the noise stream shared across rates and NFEs, higher PSNR tracked higher GenEval in our experiments, which made it a cheap proxy during development. As the reviewer suggested, we measured the PSNR between 32-NFE samples generated with different seeds, which is about 10.8 dB. We will report this value as a reference level for the metric.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Global Response

General Response

We thank all reviewers for their positive evaluations, careful reading, and constructive feedback. We are encouraged that the reviewers recognized the novelty of the idea (2gYT,BUms, hQjF), found the closed-form, locality-aware travel-optimal flux interesting (2gYT), and found the gains clear at negligible cost without any retraining (2gYT, BUms, hQjF).

Several comments asked for the same additional experiments, so we collect them here and refer to them in the individual responses. All changes in the revised manuscript are highlighted in blue.

G1. Comparison with a high-order sampler (BUms, hQjF). Strictly speaking, the goal of our paper is not to design a sampler. Our method specifies the rate that a sampler approximates, not the sampler itself, and is therefore orthogonal to sampler design. Our analysis mainly uses AVE because it is the simplest discrete sampler, but the observation that a step can represent at most one jump per token is not specific to AVE. To compare with a more advanced sampler, we implemented the RK-2 sampler (θ-trapezoidal). of Ren et al (2026). We compare all methods at matched NFE (URSA, GenEval).

NFEAVEAVE + TORK-2RK-2 + TO
50.5610.7180.6560.690
90.7410.7620.7530.771

TO improves over the default rate on top of RK-2 as well, so the two are complementary. At NFE 5, AVE + TO is the strongest configuration, since the second-order accuracy of RK-2 pays off only once the step size is small enough. Changing the rate reduces the error without giving up time resolution, which is why it is the more effective lever in the very low NFE regime. These results are in Appendix F.1.

G2. Additional baselines on FUDOKI (hQjF, BUms). We extended the FUDOKI comparison beyond AVE to the corrector samplers of Wan et al. and to RK-2 (GenEval).

NFEAVECorr-TCorr-LRK-2 (Trap.)TO
40.4830.6080.5370.5600.689
60.6420.6700.7050.6710.713
80.7030.7110.7350.6850.712
120.7410.7490.7510.7150.758

TO gives the best result at every budget except NFE 8, where Corr-L is ahead. The advantage of TO is largest at the smallest budget, consistent with the URSA results. These results are in Appendix F.2.

G3. NFE-based reporting and wall-clock comparison (2gYT, hQjF). We reorganized Table 1 by NFE. We also added a plot of GenEval against measured wall-clock sampling time for all samplers in Figure 7 (Appendix F.4).

Summary of revisions. All changes are highlighted in blue in the revised PDF.

  • Section 3.2: error from several tokens changing within one step (2gYT).
  • Section 4.2: the minimal jump intensity is stated for the conditional path, and Remark 1 discusses mixture paths and the scope of the method (BUms, hQjF).
  • Section 4.3: reference to the definition of a^\hat a, the sentence introducing Proposition 1, and a pointer to the KO comparison (hQjF).
  • Section 5: the bound depends on the rate only through the jump and travel intensities (2gYT, BUms).
  • Table 1: reorganized by NFE (2gYT, hQjF).
  • Appendix A: discussion of prior sampler analyses (hQjF).
  • Appendix E: comparison with the kinetic-optimal rate (hQjF).
  • Appendix F: high-order sampler (F.1), FUDOKI baselines (F.2), time-grid sweep (F.3), and wall-clock comparison (F.4) (BUms, hQjF).

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.