Minimal Travel Sampling for Metric Path Discrete Flow Models

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.