Jump Your Steps: Optimizing Sampling Schedule of Discrete Diffusion Models
Authors: Yong-Hyun Park
Chieh-Hsin Lai
Satoshi Hayakawa
Yuhta Takida
Yuki Mitsufuji
Venue: ICLR 2025 Poster (2025)
Keywords: Discrete diffusion models
Efficient sampling
Primary area: generative models
TL;DR: We introduce Jump Your Steps, a general and principled method to find an optimal sampling schedule to minimize errors without requiring additional computational cost during inference.

Abstract: Diffusion models have seen notable success in continuous domains, leading to the development of discrete diffusion models (DDMs) for discrete variables. Despite recent advances, DDMs face the challenge of slow sampling speeds. While parallel sampling methods like $\tau$-leaping accelerate this process, they introduce _Compounding Decoding Error_ (CDE), where discrepancies arise between the true distribution and the approximation from parallel token generation, leading to degraded sample quality. In this work, we present _Jump Your Steps_ (JYS), a novel approach that optimizes the allocation of discrete sampling timesteps by minimizing CDE without extra computational cost. More precisely, we derive a practical upper bound on CDE and propose an efficient algorithm for searching for the optimal sampling schedule. Extensive experiments across image, music, and text generation show that JYS significantly improves sampling quality, establishing it as a versatile framework for enhancing DDM performance for fast sampling.

Published as a conference paper at ICLR 2025
Jump Your Steps: OPTIMIZING SAMPLING SCHEDULE OF DISCRETE DIFFUSION MODELS
Yonghyun Park" & Chieh-Hsin Lai
Satoshi Hayakawa Sony Group Corporation Tokyo, Japan
Yuhta Takida
Sony Al
Sony Al
Tokyo, Japan
Tokyo, Japan
enkeejuniore or ornnnnrrr@suuuu.u @anu. acc. sc.k. kr
Yuki Mitsufuji
Sony AI, Sony Group Corporation New York, USA
ABSTRACT
Diffusion models have seen notable success in continuous domains, leading the development of discrete diffusion models (DDMs) for discrete variables. De- spite recent advances, DDMs face the challenge of slow sampling speeds. While parallel sampling methods like r-leaping accelerate this process, they introduce Compounding Decoding Error (CDE), where discrepancies arise between the true distribution and the approximation from parallel token generation, leading to de- graded sample quality. In this work, we present Jump Your Steps (JYS), a novel approach that optimizes the allocation of discrete sampling timesteps by minimiz- ing CDE without extra computational cost. More precisely, we derive a practical upper bound on CDE and propose an efficient algorithm for searching for the opti- mal sampling schedule. Extensive experiments across image, piano note, and text generation show that JYS significantly improves sampling quality, establishing it as versatile framework for enhancing DDM performance for fast sampling. The code is available at https: : gightuut.. com/ sony jys.
INTRODUCTION
Diffusion models (Sohl-Dickstein et al., 2015; Song et al., 2021b; Ho et 2020; Song et al., 2021a; Karras et al., 2022) have achieved remarkable success in generation tasks within the continuous do- main. However, certain modalities, such as text and piano note, inherently possess discrete features. Recently, discrete diffusion models (DDMs) (Austin al., 2021; Campbell al., 2022; 2024; Gat et al., 2024) have demonstrated performance comparable to state-of state-of-the-are fi-thh--rt art methods in various ar- eas, including text (Lou et al., 2024; Shi et al., 2024) and image (Chang et al., 2022: Gu et al., 2022) generation. Nevertheless, like their continuous counterparts, DDMs encounter significant bottleneck in sampling speed due to their progressive refinement process.
In contrast to dominn diffusion models, where sampling dynamics are driven by sample- wise differential equations (Song et al., 2021b), allowing for the direct application of well- established numerical methods accelerate generation, enhancing speed in DDMs poses sig- nificant challenge. To address this, researchers have proposed fast and efficient samplers, including notable methods such the r-leaping (Campbell et al., 2022; Lezama al., 2022; Sun et al., 2023) and k-Gillespie algorithms (Zhao et al., 2024), which facilitate parallel sampling of multiple tokens in a single step. However, this parallel but independent sampling introduces Compounding Decoding Error (CDE) (Lezama et al., 2022), which arises from a mismatch between the training and infer- ence distributions of intermediate latents during parallel sampling. Specifically, while each token is generated according to its marginal distribution, the joint distribution deviates from the learned distribution. To mitigate this issue, the predictor-correet been proposed. This sampler slightly perturbs the generated data to correct incorrectly generated tokens. However, these methods have limitations, including impracticality under low computational
(PC) sampler (Campbell et al., 2022) has
Work done during intersship SONY AT.

---

Published as a conference paper at ICLR 2025
budgets (Campbell et al., 2022), the need for an additional corrector (Lezama al., 2022),
liance on specialized architectures and loss functions (Zhao et al., 2024).
Ground Truth Samples
Uniform Schedule
Jump Your Steps (Ours)
Sampling with infortaimal dteps
Sampling with timeddeps
Sampling with irfeed timentep
Sampling
7'
Coundown dotases 4.ction
Use parale sampinginc T
Use fonllll st
Preseitt
M
M
3
3
3
3
M
M
M
3
Example
M
M
2
M
M
Dimossions
M
M
M
M
M
M
0
0
0
M
2
M
M
M
M
6
6
6
6
M
6
M
6
6
M
M
M
5
M
M
M
21
Figure 1:
(Top) Comparison of sampling trajectories: ground truth vs. parallel sampling using a uniform schedule and the Jump Your Steps (JYS) schedule. (Bottom) Uniform schedule exhibits compounding decoding errors during parallel sampling, while JYS reduces them by using fewer steps in deterministic phases and reallocating skipped steps to other timesteps.
To reduce CDE and enable fast sampling in DDM fundamentally, first introduce rigorous quantity to measure CDE (see Figure Top, and Section 3.1) and propose a novel approach called Jump Your Steps (JYS), which optimizes the allocation of discrete sampling timesteps {T' t
fN-1 + 0}' under a fixed total sampling budget N to minimize CDE. Our core idea is to derive efficiently computable bounds for CDE (see Section 3.2 and Section 3.3) and strategically select sampling timesteps by solving minimization problems to reduce these bounds (Section 3.4 and Section 3.5), theoretically ensuring a decrease in the gap between the ground truth distribution and the approximated distribution through parallel sampling (see Figure 2).
Unlike previous methods such as the PC sampler, our approach requires no additional computa- tional resources modifications the model architecture loss function. We empirically validate the effectiveness of our sampling schedule across various datasets, including synthetic sequential data, CIFAR-10 (image). Lakh Pianoroll (piano note), and text modeling. Our approach acceler- ates DDM sampling across models using different forward corruption transition kernels, such as uniform, Gaussian, and absorbing transition matrices. Our comprehensive experiments cover both unconditional and conditional generation tasks, consistently showing that optimizing the sampling schedule significantly enhances sampling quality. These results indicate that our method serves general framework for speeding up discrete diffusion model sampling.
2 BACKGROUND
2.1 CONTINUOUS TIME FRAMEWORK FOR DISCRETE DIFFUSION MODELS.
DDMs define the generative process the reverse of the data- corrupting forward process, expressed
as a Continuous Time Markov Chain (CTMC) on a finite state space (Campbell et al., 2022). For the data-corrupting process (X.)ıejo.T)- the density evolution is described as:
(t+aefe g x)) 8mg + [z y) + o(dt)
(1)
Here, Say is the Dirac delta function, R₁ E Sx5 is the transition rate matrix of the forward CTMC, with S [S], and dt > 0. Rate matrices ensure the marginal distribution qe (xx))
In this work, denotes sampling across timesteps from
2

---

Published as a conference paper at ICLR 2025
where qu Pdata and fr = π, the stationary distribution of the forward CTMC. Various transition matrices have been proposed, allowing स to follow a uniform or Gaussian distribution, converting samples into masked tokens.
For generation, we reverse the forward process, moving from the marginal qr back to Pdata- This time-reversal CTMC is also CTMC (Campbell et al., 2022; 2024):
qe-ds (e æ)) day + R(x, v) + o(dt),
(2)
where the backward transition rate it is defined as:
(v(
Ze qe
Fo 4a (z
R(z, 3) R(y,
R(y, x))
(x)
ro Demoising Parametrization
Score Parametrization
The literature primarily falls into two parameterizations: Denoising parameterization (Campbell et al., 2024; Austin et al., 2021; Campbell et al., 2022) approximates parameterized denoising model as Poje (2olz)) 4op (2)l()). Conversely, score parameterization (Lou et al., 2024; Meng et al., 2022) estimates the ratio of the data distribution as (2(()) =4 (v))/((1x).
2.2 SAMPLING FROM THE BACKWARD CTMC
Gillespie's Algorithm was proposed as simulation algorithm for a given CTMC (Gillespie, 2007). Gillespie's algorithm simulates the CTMC by calculating the rate matrix each state tran- sition. If the rate matrix of the CTMC depends only on the state, Gillespie's ' algorithm serves as an exact simulation method. However, since it allows for only one token transition each time the rate matrix is calculated, it is computationally inefficient.
I-Gillespie's Algorithm Instead of updating only one token for each rate matrix calculation, the k- Gillespie's algorithm (Zhao et al., 2024) updates & tokens in parallel. This reduces the computation by a factor of 1/k compared to the original Gillespie algorithm.
L-Lepping On the other hand, Campbell et al. (2022) proposes sampling through r-leaping. Un- like the k-Gillespie algorithm, which update tokens parallel, r-leaping simultaneously updates all tokens according to the given fixed rate matrix within the specified time interval [l, ( r). Re- cently, Tweedie r-leaping, which considers changes in the rate matrix according to the noise sched- ule, has been proposed (Sun et al., 2023; Lou et al., 2024).
3 OPTIMIZING THE SAMPLING SCHEDULE OF DISCRETE DIFFUSION MODELS
-N + 0} to minimize the CDE introduced by parallel sampling. First, we define and analyze the CDE, examining its relationship to both the sampling schedule (Section 3. and sampling quality (Section 3.2). In Section 3.3, we derive an upper bound on the CDE, which serves as the objective for the sampling schedule optimization. Finally, we introduce heuristic algorithms to make the optimization tractable including hierarchical breakdown strategy (Section 3 3.4) and computational techniques (Section 3.5). Figure summarizes the relationships between the theoretical analyses and algorithms discussed in this section.
In this section, we aim to optimize sampling schedule (T > t1 t
Although this section focuses on samplers based on r-leaping, all methods are also applicable to the k-Gillespie algorithm. For extensions to k-Gillespie, please refer to Algorithm 1.
Notations To begin, we introduce some essential mathematical notation. X : a random variable, f--1 0} sampling schedule, and Qu-b-..re the distribution generated by the sampling schedule {a + b.b... ..... + c). For clarity, when working with backward CTMCs, we slightly abuse notation and express intervals as [s, t] a {u 2 2 l]: the same applies to open and half-open intervals.
its observation, P, Q distributions, {I' f

---

Published as a conference paper at ICLR 2025
Theorem 3.1
Eq. (10)
DeL. (PI.(Po (Po 100 x Ei DKt, 11 (1)
1
DeL pathn Quatta
Eqs. (3.
Theorem 3.2
Ee ECDE(L: 4411)
nto-tt Qu KLUB2, (Pol
Algorithm 1, 2.
(T
1x-1
Figure 2: An illustration of the relationship between the KL divergence of the distribution, the compounding error ÈCDE (defined in Section 3) and KLUB (defined in Section 3.3). The sampling schedule {T 1 11--1 0} is optimized to minimize KLUB using the efficient algorithms detailed in Section 3.4, and 3.5.
3.1 TIME-DEPENDENT NATURE OF COMPOUNDING DECODING ERRORS
We introduce a measure for the CDE, ECDE, which quantifies the discrepancy between the true joint distribution and the distribution from parallel token generation. For illustration, consider a discrete process X, (X?, x?) with sequence length 2, consisting of tokens X; and X². The general case is provided Appendix B.1.
We propose measuring the CDE for single parallel sampling step {s t start from x, by using the KL divergence between the joint distribution Pxt,xx [x]xxxxx, and the product of marginal distributions Px||x, Px
ECDE(S 1|x,) A DRL Pxt,xflx,
Px Pxp
(3)
Thue distribution
Approx, distribution from parallel sampling
We note that the defined CDE is equivalent to the conditional mutual information I(X:; X3| tokens X,, X?:
x2,)x.) of
ECDE(S - ((x.) = I(X; x?
(4)
This expression links the compounding error to the mutual information between tokens; lower mu- tual information reduces parallel sampling errors. For example, as shown in Figure 1 (Bottom), as generation progresses, the uncertainty of each token decreases over time due to the tokens al- ready generated, reducing mutual information and preventing CDE. In general, CDE depends on the timesteps, and its behavior varies with the data distribution, corruption kernel (see Fig. 9 for illustration). and DDM sampling methods. Motivated by this observation, we hypothesize that we can reduce the CDEs during generation process by optimizing the sampling schedule.
3.2 RELATION BETWEEN COMPOUNDING DECODING ERRORS AND GENERATION QUALITY
While the Eq. (3) allows us to estimate the CDE starting from a specific state x,, in practice, we are interested in the average compounding error over all possible starting states time s. To assess the overall impact of the CDE when transitioning over the timesteps - we consider the expected value of (CDE(S + l(x,) with respect to X, P.,. This leads us to consider:
ECDE(S 1) A Ex, [ECDE(S (s+ ([x.)].
5
Consider a sampling schedule {T = to + later. Our goal is minimize the cumulative CDE that arises from each parallel sampling step within the given schedule. If we ignore the accumulated error from the previous steps that affects the consecutive steps, our objective is as follows (Appendix A.2):
IN 0 = (N). which will be specified
min
ECDE(t, - 1441).
(6)
6 fg.f.......
1=0
4

---

Published as a conference paper at ICLR 2025
Interestingly, find in the following theorem that cumulative CDEs the sampling schedule can upper bound the KL divergence between the true distribution at time t = 0, denoted Po, and the distribution Q 127"-t++-"" obtained from parallel sampling along the sampling schedule (see Appendix B.1 for proof):
Theorem 3.1. We have the following bound on the KL divergence between PP and Qo @7 in terms of cumulative CDEs:
N-1
DKL (PooQQ t
S
ECDE(ti + 4441).
==0
This theorem suggests that effectively allocating the time schedule to minimize the CDEs can implic- itly reduce the discrepancy between the true distribution and the approximate distribution obtained from parallel sampling. Motivated by this, in the next section, we derive a tractable upper bound
for -i= N- ECDE(4; - 1++1) that depends on the sampling schedule {T l1 LN-1 0} to facilitate its optimization.
3.3 ESTIMATING THE COMPOUNDING DECODING ERROR USING GIRSANOV'S THEOREM
As shown in Eq. (3), computing (CDE(S t xx,)) involves determining the KL divergence between the true distribution and the approximated distribution from DDM's parallel sampler, which is often intractable. To address this, we treat the ground truth reverse process and the sampling process from DDM's parallel samplers (introduced Section 2.2) as two CTMCs, starting from the same initial distribution. By applying Girsanov's theorem (Ding & Ning, 2021; Chen al., 2023), derive a tractable formula to compare the KL divergence between the distributions of these stochastic processes at any time interval [s, t). We summarize this the following general theorem applicable to any two backward CTMCs with R2 and R2 as their respective transition rate matrices:
CTMC 1: Lu-du x)) 8zv + R (z, yu + o(du);
CTMC 2 - du v x)) 8zy + R (z, yu o(du).
We defer its proof to Appendix B.2.
Theorem 3.2. (KL-Divergence Upper Bound, KLUB) Consider an interval [s, f] (s
If both
CTMCs start from the same initial distribution, T. = P = Q.. then we have:
H log (i,j)
(IP S DKL pattssss @paths)
= 18,7 patha
Σ Σ
(8)
R (i,))
i#j BUUSE
KLUB,, (P.))Q+)
Here, P. and Qi are the probability distributions at time t resulting from CTMC and CTMC 2, respectively. P Pattus and Qpatius denote the distributions over their path spaces (X (Xu)ue(t,s) gener- ated by CTMC 1 and CTMC 2, respectively. The indicator function H is defined H = if transition from state i to occurs at time u. and H 0 otherwise.
We denote the rightmost term in Eq. (8) as the Kullback-Leibler Divergence Upper Bound (KLUB), which quantifies the mismatch between distributions generated by different CTMCs based on their rate matrices. Consider CTMC as the ground truth reverse CTMC and CTMC 2 as the reverse CTMC obtained via parallel sampling by substituting the forward transition kernel with the corre- sponding reverse-in-tine kernel. Thus, ECDE(s + t/x,) can be expressed the KL divergence between the output distributions of the two CTMCs at time f, starting from the initial point x,- This leads to the upper bound (Proof in Appendix B.3):
(9) where Q?" is given by the process discretized at time and This expectation considers the distribution of states at time and offers a more comprehensive measure of the CDE over the interval [s, t]. Moreover, from the additivity KLUB, we can bound the sum of CDEs as
ÊCDE(s f) < (IU (PP.I)
ECDE(S - EcDent - u) < KLUB,, (P, Q( + KLUBp, (P.lIQQ = KLUB,, (P. (Pul[(aa-+9
(10)
5

---

Published as a conference paper at ICLR 2025
which shows that the KLUB can be useful for comparing the quality of discretization of the interval [s, u] with different break point t. We can easily extend this result for the sum of CDEs over the entire sampling schedule {I to
-N-1 0 0=
N-1 ECDE(T, - t(41) & KLUBP, (Fol T4 ))
DKL (PolQQ
(11)
where inequality on the left- hand side comes from Theorem 3.1.
To summarize, optimizing the sampling schedule involves finding set of timesteps {T t f--1 0} that minimizes the KLUB on the right-hand side. This approach approximately reduces the cumulative CDE (middle) and provides upper bound on the KL divergence between the true distribution and the sampled distribution for the given schedule (left-hand side).
3.4 FEASIBLE COMPUTATION WITH HIERARCHICAL BREAKDOWN STRATEGY
Using the derived KLUB, we can formulate the timestep search a minimization problem over KLUB. Here, we employ a hierarchical breakdown strategy, dividing a coarser sampling schedule into a finer one, as shown in Figure 3.4. Suppose our sampling schedule is given by (T + 0). Let @ Q2-1-00 represent the distribution generated by this schedule. Our goal to find the optimal / that minimizes cumulative CDE, i.e., ÊCDE. (T + ECDE(1 - 0). This is approximately achievable by minimizing its KLUB upper bound:
h arg min KLUB rE(T,0)
(12)
With the initial refined interval (T tr 0}, we seek optimal timesteps to E (T, (1) and is E (t1.
by solving the following minimization problems:
f2 E arg min KLUB(PP, I10 T+(4)) and t3 E arg min KLUB(IPo|]Q0) -2-0)) LE(1,,0)
1E(T,4)
The first minimization problem targets match- ing (Pr, ||Q,, ). while the second focuses on matching (P This results in a further refined sampling schedule {T' f2 fi i3 0}. By iterating this process, we continue split- ting each interval into smaller ones, optimizing breakpoints using the KLUB criterion. After K iterations, this hierarchical strategy yields sam- pling schedule with 2 NFEs (Number of Func- tion Evaluations), optimizing the schedule as the number of steps increases.
NFE =
I argmin KLUB(P, G GT-C-+)
642220
NFE = 2 T
NFE = 4
Figure 3: We optimize the sampling schedule by refining it from coarse intervals to finer inter- vals, using a hierarchical breakdown strategy.
3.5 FRASIBLE COMPUTATION FOR KLUB ESTIMATION
Directly estimating KLUBr, ( 1 using Eq. (8) is impractical due to (1) the high cost of sampling from Pratss and (2) the need for extensive Monte Carlo sampling for reliable estimates. To address this issue, we propose two techniques that simplify the estimation process.
Technique 1: Maximizing KL Divergence from Coarser Approximation Instead of minimiz- ing the mismatch between the ground truth distribution IP pachs and Q we choose maximize the discrepancy between QT=t=0 and simpler, coarser approximation QTT-0 The key insight is that maximizing this divergence, we can find the optimal sampling time f, which helps reduce the com- pounding error relative to the true distribution. This relationship can be approximated as (Appendix B.4):
(aaT (1TT00)) z DKL (Paaats DKL Cpatts
11 DKLL (P (Ppatt 1 (Tatt
Thus, by maximizing the divergence on the left-hand side, we effectively minimize the discrepancy DrCt. paths (T-t-")) between the true distribution Ppaats and the optimized schedule Qpars

---

E Beyzr.-- Published as a conference paper at ICLR 2025
Based on this, rewrite optimization objective as follows (Proof in Appendix B.4):
Re(i, j) Rr (1,5) UcuS!
arg max KL (07'tt-0 1Q0 (Q000)) arg max tE(T,0)
(Qu
log
H
(13)
LE(T,0)
puths
Equation Eq. (13) offers significant computational advantage over Eq. (8) by eliminating the need to compute the rate matrix at every transition time. Note that, calculating the reverse rate matrix involves neural network evaluations. Given trajectory (Xu)ue [T.jj Eq. (8) requires computing the rate matrix R1 for all transitions where H = 1. In contrast, Eq. (13) decouples the rate matrix from the transition times u, requiring computations only at times 7 and t. Moreover, between times T and t, the rate matrices for both paths and Q T-0 are equal to Rr, eliminating the need for additional computations in this interval.
pathss
Technique 2: Applying the Law of Total Expectation Instead of directly compute the expecta- tion over - we compute expectation of conditional expectation, using the law of total expec- tation, i.c., [ = [[][x
log Ri(i,) RT(i,j) OCUSE
Re(i,j) Σ Σ log RT(i, DcuSt
Σ
H
H X₁ =
On the left side, to compute the expected value, we would need to sample the entire trajectory (Xu)ue(T.o) and then calculate the inner sum. On the right side, this process is broken down into two steps: first, we sample trajectory from Xr to Xx, and then, given Xt, we sample from X, to X₂ to compute the inner expectation. Our main insight is that the expected value the second step can be obtained in closed form.
The term Eocuge Hy counts the number of transitions from state to state in the interval [t, 0). Since Qf uses single rate matrix over this interval, for A j, the expected number of transitions from i to is approximately given by (Campbell et al., 2022, Sec. 4.3):
Σ H
R((I,)
(14)
DRuSE
where At represents the size of the time interval.
Using this result, we can simplify Equation Eq. (13) as follows (Derivation in Appendix B.5);
Re(Xe,) x R,(X,,))A
KLUB T-
Σ
log
(15)
RT((..))
JxX.
In Eq. (13), obtaining a reliable KLUB estimation requires sampling trajectories to capture transitions between vari- ous states i and j. which is both inaccurate and sample- enefficient-esseciiallly when dealing with large state spaces, For instance, in text generation tasks where the state space can be around 50,257, it's practically impossible to estimate the transition ratios between all pairs (i,j) through sampling alone. In contrast, Eq. (15) allows us to compute this component closed form, leading to more reliable and efficient calculations. The full algorithm for KLUB computation, combining Tech- niques and 2, is provided in Appendix C.I.
(o-)00 300mm
0.97
0.17
Figure 4: The values of KLUB with respect to t. Blue lines show estimated results from individual (Xt) while the red line is the average.
Now, we can maximize Eq. (15) using a standard optimization algorithm. Before selecting the algorithm, liminary check to observe how the KLUB value changes with respect to f (Figure 4). Interestingly, it exhibits unimodal shape. Since working with
conduct pre-

---

Published as a conference paper at ICLR 2025
101
F10
129
Jump your stops (Ouns)
Figure 6: (Left) Performance comparisons CIFAR-10. (Right) Samples generated using the uniform and JYS schedules, both with NFE 64.
single variable t in the unimodal optimization landscape, we use the golden section search (Press, 2007), a well-known one-dimensional search algorithm, to find the value of that maximizes KLUB. This method has the advantage of not relying on hyperparameters like learning rate, which can sig- nificantly affect performance.
4 EXPERIMENTS
bul mole
In this section, we evaluate the Jump Your Steps (JYS) sampling schedule across various datasets and models. We compare the JYS schedule with the uniform sampling schedule, which sets all inter- vals to the same size. Except for the Countdown dataset, we use open-sourced pretrained models for our experiments. It is important to note that the Gillespie algorithm is only applicable to an absorbing transition matrix, uniform or Gaussian transition kernels do not have a fixed number of transitions. For further experimental details and additional qualitative results, please refer the Appendix D and E.
Enorr (S)
Le
Number of Function Fvalustions
Performance comparisons Countdown.
Figure
4.1 THE COUNTDOWN DATASET
Following Zhao et al. (2024), to evaluate our sampling schedule performance, we created synthetic sequence dataset with strong position-wise correlation structure. Each sample consists of 256 tokens. and each token has a value between 0 and 31. Each data sequence XU:255 is generated according to the following rules:
x Uniform (1...,, S}.
1dxa-1 Uniform(1,.....
x 40 if x
x x
We trained SEDD (Lou et al., 2024) with an absorb transition matrix on this generated data. We measure the model performance by the proportion of generated samples that violated the rule, i.e. failed to count downwards from the previous token. The results shown in Figure 5. We observe that the JYS schedule has fewer errors compared to the uniform schedule for the same NFE.
4.2 CIFAR-10
We demonstrate our sampling schedule in the image domain. For this experiment, we use a pre- trained model from Campbell et al. (2022), which employs gaussian transition matrix and denois- ing parameterization. Each data sample is flattened image with a length 3 x 32 x 32, composed of tokens with values ranging from 0 to 255.
Figure 6 (left) shows the FID score using 50k samples with the number function evaluations (NFE) from 32 256. We observe that, for all NFEs, the JYS schedule yields better FID score
8

---

Published as a conference paper at ICLR 2025
SEDD small
SEDD mediam
Sumphr Schodak (Dun)
Sarper Tueedle e-Glllagte
Sampaar TeapppppTwoc In kalieeeee
Generative Parplesity (4)
3x:8-1
Hellinger distance
unitm pC (Gand
Unitm yS (0.1)
32
120
226
10
32
120
256
Number of I Function Evaluations
Number Function Evalsations
Number of Function Evaluations
Figure 7: Performance comparisons on piano note generation.
Figure 8: erative perplexity is measured by using GPT-2--arge.
Performance comparisons on text generation. Gen-
at the same NFE compared to the uniform schedule. Figure 6 (right) shows randomly generated unconditional CIFAR-10 10 samples with NFE 64. The uniform schedule produces blurry images, whereas the images generated using the JYS schedule exhibit clearer colors and shapes of objects.
4.3 PIANO NOTE
We test our method on conditional piano note generation using the Lakh pianoroll dataset (Raffel, 2016: Dong et al., 2018). For this experiment, we employ a pretrained model from Campbell al. (2022), which uses uniform transition matrix and denoising parameterization. Each data sequence contains 256 timesteps (16 per bar), and we measure performance by conditioning on two bars to generate the remaining 14 bars, following the setup in Campbell et al. (2022).
We evaluate how different the generated results were when using a smaller NFE (from 2 to 64), compare samples generated with an NFE of 512. Specifically, calculate the Hellinger distance between the note distributions in the generated samples. The results are presented in Figure 7. Given the same NFE, observe that samples generated using our method were more similar to those generated with a high NFE.
4.4 TEXT MODELING
Finally, we validate our method on text generation. For this experiment, we use a pretrained model from Lou al. (2024), which employs absorbing transition matrix and score-based parame- terization. We use two model sizes, SEDD-small and SEDDDmedium, in the experiments; both models use the GPT-2 tokenizer and were trained on OpenWebText. The JYS schedule, optimized on SEDD-small, is also used for the experiments with SEDD-medium.
Following Lou et al. (2024), we measure the generative perplexity of sampled sequences (using GPT-2 large for evaluation). We generated 1,024 samples and each sample constructed with se- quences of 1,024 tokens. We simulate to 256 NFE for generation. Figure shows the results, demonstrating better perplexity at the same NFE.
4.5 CHARACTERISTIC OF JUMP- YOUR-STEP SAMPLING SCHEDULE
In Section 1, we hypothesized that in regions where the conditional mutual information is low, the CDE would also be small, allowing steps to be skipped with minimal performance degradation. Here, we aim to verify if the JYS operates expected according to this hypothesis.
Figure shows the JYS sampling schedules optimized for various transition matrices. First, in the absorb case (Left), discussed in Figure 1 (Bottom), we observe that large intervals are concen- trated toward the latter part of the process. This occurs because the previously generated tokens help reduce the uncertainty of other tokens. In contrast, in the uniform case (Middle), large intervals appear at the beginning. This can be understood as a result X, following a uniform distribu- tion, making the tokens independent, leading lower mutual information for larger f. Lastly, for
9

---

Published as a conference paper at ICLR 2025
Jump Your
H1
scbedale
[a] Countdown Absorb
(b) Piano - Uniform
(c) CIFARIO GGussian
Figure 9:
Sampling trajectories for different dataset-transition matrix combinations. (Top) Trajec- tories using the JYS schedule. (Bottom) Optimized sampling schedule with JYS.
the Gaussian transition (Right), large intervals appear initially and then increase again over time. This pattern suggests that, initially, tokens behave independently like in the uniform case, but af- ter certain timestep, the effect of resolving uncertainty, similar to the absorb case, becomes more significant as more tokens are generated.
5 RELATED WORK
Efficient Sampling for Continuous Diffusion Models After the seminal work by Song et al. (2021b), which interpreted diffusion models Stochastic Ordinary Differential Equations (SDE/ODE), various SDE (Jolicoerr-Martine) et al., 3021; Xu et al., 2023) and ODE solvers (Song al., 2021a; Lu et al., 2022; Zhang Chen, 2023; Dockhorn al., 2022; Liu et al., 2022; Zheng et al., 2023) have been proposed to improve sampling speed.
The work most closely related to ours is "Align Your Step" (Sabour et al., 2024) and AdaptiveSched- ules (Chen et al.), which focuses on sampling schedule optimization in continuous diffusion models. In contrast, our approach targets DDMs, where we derive the KLUB for CTMCs to optimize the sampling schedule. We also propose computationally efficient algorithm for KLUB computation and optimization.
Discrete Diffusion Models Several approaches have been developed for training DDMs, including denoising parameterization (Austin et al., 2021; Campbell et al., 2022; Gu et al., 2022; Gat et al., 2024; Campbell et al., 2024; Shi et al., 2024; Sahoo et al., 2024) and score parameterization (Sun et al., 2023; Meng et al., 2022; Lou et al., 2024). Types of DDMs that do not fall into these two categories also being continuously proposed (Hoogeboom et al., 2021b;a; Santos et al., 2023). Recently, SEDD has outperformed GPT-2 in text modeling, gaining traction as alternative to autoregressive models (Deschenaux Gulcehre, 2024).
In terms of sampling, two main directions have emerged. The first focuses on efficient sampling, with r-leaping for CTMC and methods like analytic sampling (Sun et al., 2023), Tweedie sampling (Lou et al., 2024), and h-Gillespie (Zhao et al., 2024) improving accuracy. The second aims to reduce compounding error via corrector steps, such as random correctors (Campbell et al., 2022), separate corrector training (Lezama et al., 2022), enabling the model to act as an informed cor- rector (Zhao et al., 2024). These methods complement the sampling schedule optimization explored in this paper and can be used together for further improvements. Recently, concurrent work, DNDM (Chen et al., 2024) proposed accelerated sampling through a Mon-Maakovinn framework that uses token transition times sampled from beta distribution.
CONCLUSIONS
We present Jump Your Steps, a principled method designed to optimize the sampling schedule and minimize these numerical emrors without incurring additional computational costs during inference. Unlike existing approaches that rely on extra computational efforts, such as predictor-correctt methods, technique operates independently and efficiently. Through extensive evaluations synthetic and real-world datasets-including monophonic piano, image, and text generation-we demonstrate that our method consistently enhances performance across different transition kernels in DDMs and effectively complements various samplers.
10

---

Published as a conference paper at ICLR 2025
BIBLIOGRAPHY
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.
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 2022.
Information Processing Systems,
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. In International Conference on Machine Learning, 2024.
Huiwen Chang, Han Zhang. Lu Jiang, Ce Liu, and William T Freeman. Maskgit: Masked generative image transformer. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 11315-11325, 2022.
Sitan Chen, Sinho Chewi, Jerry Li, Yuanzhi Li, Adil Salim, and Anru R Zhang. Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions. In International Conference on Learning Representutions, 2023.
Yuzhu Chen, Fengxiang He, Shi Fu, Xinmei Tian, and Dacheng Tao. Adaptive time- time-stepping sched- ules for diffusion models. In The 40th Conference on Uncertainty in Artificial Intelligence.
Zixiang Chen, Huizhuo Yuan, Yongqian Li, Yiwen Kou, Junkai Zhang, and Quanquan Gu. Fast sampling via discrete non-markov diffusion models with predetermined transition time. In The eighth Annual Conference on Neural Information Processing Systems, 2024.
Thomas M. Cover and Joy A. Thomas. Elements of information theory. John Wiley & Sons, second edition, 2006.
Justin Deschenaux and Caglar Gulcehre. Promises, outlooks and challenges of diffusion language modeling. arXiv preprint 11X1 2024.
Kailin Ding and Ning Ning. Markov chain approximation and measure change for time- inhomogeneous stochastic processes. Applied Mathematics and Computation, 392:125732 2021.
Tim Dockhorn, Arash Vahdat, and Karsten Kreis. Genie: Higher-order denoising diffusion solvers. Advances in Neural Information Processing Systems, 35:30150-30166, 2022.
Mlao-Wen Dong, Wen-Y Yi Hsiao, Li-Chia Yang. and Yi-Hsuan Yang. Musegan: Multi-track se- quential generative adversarial networks for symbolic music generation and accompaniment. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Patrick Esser, Sumith Kulal, Andreas Blattmann, Rahim Entezari, Jonas Müller, Harry Saini, Yam Levi, Dominik Lorenz, Axel Sauer, Frederic Boesel, et al. Scaling rectified flow transformers for high-resolution image synthesis. In Forty-first International Conference on Machine Learning, 2024.
Itai Gat, Tal Remez, Neta Shaul, Felix Kreuk, Ricky TQ Chen, Gabriel Synnaeve, Yossi Adi, and Yaron Lipman. Discrete flow matching. arXiv preprint arXiv:2407. 15595, 2024.
Daniel T Gillespie. Stochastic simulation of chemical kinetics. 35-55, 2007.
Annu. Rev. Phys. Chem., 58(1):
Shuyang Gu, Dong Chen, Jianmin Bao, Fang Wen, Bo Zhang, Dongdong Chen, Lu Yuan, and Baining Guo. Vector quantized diffusion model for text-to-image synthesis. In Proceedings of the IEEF/CVF conference computer vision and pattern recognition, pp. 10696-10706. 2022.
Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in Neural Information Processing Systems, 11:6840-6851, 2020.

---

Published as a conference paper at ICLR 2025
Emiel Hoogeboom, Alexey A Gritsenko, Jasmijn Bastings, Ben Poole, Rianne van den Berg, and Tim Salimans. Autoregressive diffusion models. arXiv preprint arXiv:2110.02037, 2021a.
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, 111122244-26466 2021b.
Alexia palicoeur-Martinau,, Ke Li, Rémi Piché-Taillefer, Tal Kachman, and loannis Mitliagkas. Gotta go fast when generating data with score-based models. arXiv preprint arXiv:2 1000.0000.. 2021.
Tero Karras, Miika Aittala, Timo Aila, and Samuli Laine. Elucidating the design space of diffusion- based generative models. Advances in Neural Information Processing Systems, 35:26565-26577,, 2022.
Jose Lezama, Tim Salimans, Lu Jiang, Huiwen Chang, Jonathan Ho, and Irfan Essa Discrete predietor-correcto diffusion models for image synthesis. In The Eleventh International Confer- ence on Learning Representations, 2022.
Luping Liu, Yi Ren, Zhijie Lin, and Zhou Zhao. Pseudo numerical methods for diffusion models on manifolds. In International Conference on Learning Representations, 2022.
Aaron Lou, Chenlin Meng, and Stefano Ermon. Discrete diffusion language modeling by estimating the ratios of the data distribution. In International Conference Learning Representations, 2024.
Cheng Lu, Yuhao Zhou, Fan Bao, Jianfei Chen, Chongxuan Li, and Jun Zhu, Dpm-solver: fast ode solver for diffusion probabilistic model sampling in around 10 steps. Advances in Neural Information Processing Systems, 35:5775-5787. 2022.
Chenlin Meng, Kristy Choi, Jiaming Song, and Stefano Ermon. Concrete score matching: General- ized score matching for discrete data. Advances in Neural Information Processing Systems, 35: 34545, 2022.
William Peebles and Saining Xie. Scalable diffusion models with transformers. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pp. 4195-4205, 2023.
William Н Press. Numerical recipes 3rd edition: The art of scientific computing. Cambridge uni- versity press, 2007.
Colin Raffel. Learning-based methods for comparing sequences, with applications to audio-to-midi alignment and matching. Columbia University, 2016.
Amirmojtaba Sabour, Sanja Fidler, and Karsten Kreis. Align your steps: Optimizing sampling schedules in diffusion models. arXiv preprint arXiv:2404. 14507, 2024.
Subham Sekhar Sahoo, Marianne Arriola, Yair Schiff, Aaron Gokaslan, Edgar Marroquin, Justin T Chiu, Alexander Rush, and Volodymyr Kuleshov. Simple and effective masked diffusion language models. arXiv preprint arXiv:2406.07552 2024.
Javier E Santos, Zachary R Fox, Nicholas Lubbers, and Yen Ting Lin. Blackout diffusion: generative diffusion models in discrete-state spaces. In International Conference Machine Learning, pp- 9034-9059. PMLR, 2023.
Jiaxin Shi, Kehang Han, Zhe Wang, Arnaud Doucet, and Michalis K Titsias. Simplified and gener- alized masked diffusion for discrete data. arXiv preprint 0rXV:2246.00439. 2024.
Jascha Sohl- Sohl-Dickstein, Eric Weiss, Niru Maheswaranathan, and Surya Ganguli. Deep unsupervised learning using nonequilibrium thermodynamics. In International Conference on Machine Learn ing, pp. 2256-2265. PMLR, 2015.
Jiaming Song, Chenlin Meng, and Stefano Ermon. Denoising diffusion implicit models. In Interna- fional Conference on Learning Representations, 2021a.
12

---

Published as a conference paper at ICLR 2025
Yang Song, Jascha Sohl-Dickstein, Diederik P Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. In Interna- tional Conference on Learning Representations, 2021b.
Haoran Sun, Lijun Yu, Bo Dai, Dale Schuurmans, and Hanjun Dai. Score-based continuous-time
discrete diffusion models. In International Conference on Learning Representations, 2023.
Yilun Xu, Mingyang Deng, Xiang Cheng, Yonglong Tian, Ziming Liu, and Tommi Jaakkola. Restart sampling for improving generative processes. Advances Neural Information Processing Sys- tems, 36:76806-66838, 2023.
Qinsheng Zhang and Yongxin Chen. Fast sampling of diffusion models with exponential integrator. In International Conference on Learning Representations, 2023.
Yixiu Zhao, Jiaxin Shi, Lester Mackey, and Scott Linderman. Informed correctors for discrete diffusion models. arXiv preprint arXiv:2407.21243, 2024.
Kaiwen Zheng, Cheng Lu, Jianfei Chen, and Jun Zhu. Dpm-solver-v3: Improved diffusion ode solver with empirical model statistics. Advances in Neural Information Processing Systems, 36: 55502-55542, 2023.
13

---

Published as a conference paper at ICLR 2025
Appendix
A Discussions
14
A.1 Limitations
14
A.2 Discussions
B Theoretical Details
15
B.1 Proof of Theorem 3.1
15
B.2 Proof of Theorem 3.2
18
B.3 Proof of Eq. (9)
20
B.4 Technique
20
B.5
Technique
21
Algorithm
21
C.I KLUB computation
................................
21
C.2 Jump your steps
................................
22
C33 k-Gillespie Algorithm
22
D Experiment Details
22
E Additional Results
23
Efficiency of Algorithm Sampling Schedule Optimization...
23
E.2
Error Bars and Standard Deviations for Quantitative Metrics
24
E.3
Performance Improvements Achieved by JYS
25
E,4
Comparison with Heuristic Sampling Schedules
25
E.5
JYS Sampling Schedules for NFE + 2
25
E,6
Qualitative results
26
A DISCUSSIONS
A.I LIMITATIONS
Although the JYS sampling schedule is a method that can improve sampling quality in plug-and- play manner for general DDMs, there are still problems that need to be solved. The first drawback is that, due to the nature of the hierarchical breakdown strategy, we can only optimize sampling schedules where NFE 2 so flexibility reduced. While we propose a method to select an appropriate subset of the sampling schedule when the number of function evaluations (NFE) is not equal to 2 optimizing the sampling schedule for arbitrary NFE using a principled approach is an interesting direction for future study.
Another theoretical limitation that needs to be addressed that technique 2 uses the single-state transition assumption (Eq. 14)). This assumption is completely valid for the absorb transition kernel but does not apply to other transition kernels. This could potentially make the sampling schedule optimization suboptimal. Addressing this issue is interesting future work.
A.2 DISCUSSIONS
What does it mean to ignore the accumulated error from the previous steps? The "accumu- lated error from the previous steps that affects consecutive steps" occurs when generated 2, does not belong to the distribution q(2)). i.e., generated dataset mismatched with the training dataset. We refer to this error as exposure bias [1]. While exposure bias indeed an interesting problem to ad- dress in generative model sampling, our work focuses specifically resolving the CDE caused by
14

---

Published as a conference paper at ICLR 2025
parallel decoding. Therefore, chose to set aside exposure bias in this study. To improve clarity, we have added a discussion of this point to Section X of the revised paper.
Optimization using gradient descent As we mentioned in the main text, perform optimization using the golden-section search algorithm. In preliminary experiments, we also tried the gradient descent algorithm but encountered two issues. The first that gradient estimation was very noisy, and the second was that it was too sensitive to hyperparameters, i.e., the learning rate. Particularly, the second drawback made it impractical use because we had perform hyperparameter search optimization every time we optimized each step.
Is there an alternative optimization algorithm the hierarchical breakdown? As part of our preliminary experiments, we explored an alternative smaller, fragmented sampling schedules are combined into a coarse sampling schedule. However, our experimental results indicated that this approach often gets stuck in local optima and fails to de- liver significant performance improvements. We will include this discussion the revised version of the paper.
merging-where
B THEORETICAL DETAILS
B. PROOF OF THEOREM 3.1
Although we treated the two-dimensional case where we have X₂ xX) in the main body, we consider the general d-dimensional case with X; = -X. (X........) ) In that case, the definition of ECDE given by
(E 8 - t|x,) & DKL |x & ... Px
(16)
In general, for discrete probability distribution prior (.) over the space S and conditional distri- bution (or denoiser) IP Peond(-l+ over the same space, i,e, PP Pooud : S x S + IR, let us just write the resulting distribution follows:
P Peond prior Ex-Bprior [Pound (-12)] E (rrir)))))))))
prior
Then, if we define Pla (-1x;,) A lowing equation 16, we can denote the target distributions in the theorem follows:
Px,, xx, and 1 (-1x,,) Px!|x. @ & Px fol-
Po = -Px PryPo
Qo a OT Ttt
QeNiNN
Pro
For simplicity, let us also define the mid-time distributions as
P è Pr.te.. .PPeitto
Q+: Quiee- Q1 14 Pro:
Qoo PPo
In the proof of the theorem, we use the following well-known lemma:
Lemma B.1. For discrete finite sets X, y and the joint probability distributions Px, and Qx,y on X' x V, we have
(RI(Px,y [xxx)) (Px + Ez-Px (DKL(Pyjx (+1x))
where Px, Qx and PYJx, Qrix respectively denote the marginal and conditional distributions.
Proof. We can just compute as
P (y)
DKL (Px, (
Σ (x) log
Qv Qx
n.30
Prix(1l=)PPxl log (x Qx
Prix(vla)
DRL Ee
which leads to the stated equation.
15

---

Published as a conference paper at ICLR 2025
Now can proceed the proof of the theorem.
Proof of Theorem 3.1. Let us now consider the case where 4:-1 and t for some i >> specifically. Let
(V) A ((),()))))Pxx))
QU, x)) & (v)l))
to denote joint distributions on S x S. Then, since Pt = PI and Q. - Qujo are marginal distributions of Fr, and Qt,e. we have (from Lemma B.1) the following:
DKL (Pt
(TP, ((..) ) + R (DKL (
(IP, Q2.) + Ex, vP, (EDE + t|x,)]
(P. + ECDE(S + t).
(17)
From Lemma B. equality holds if and only if DKL (r/a)) = O.
By iteratively using equation 17, we obtain
PKI(Fol (F (
< (Ptt 11xtxx .) ECDE(IN-1 - +N)
< DKL (Pt + ECDE(IN-2 + +N-1) + ECDE(tN-1 + +t))
N-1
s DKL (P Q1o))
Σ ECDE(T, + t441).
Since set Pto Qro where π is terminal distribution, have completed the proof. Furthermore, equality holds and only DKL (Fejbe [Qes)tsn)) for {0, NN 1}.
B.1.1 COMPARISON: NEGATIVE ELBO VS SUM OF CDES
Let us just denote by F Pto....., f, the joint distribution of the variables (Xt,,.... ...., Xs, generated based on Ft, and It, fty4alt, ss Similarly define Qto..... We can also see the sum of CDEs as the KL divergence between discrete path measures. Indeed, by using Lemma B. with decomposing (Xto X
into (x......, x;) and X(4 we have
DKL (PI(Pro... (Pto.... Qtommnteer)
(PP 11Qto...)))))
Exig Pio [DKL tou.., (1xxass.... Xx, ( (-1xee....... xx,)]]
= (IP (to.....)))) + Bxx,FFF (F e, (-1x,, ) )|Q (-1x,;))
where the second equality comes from the Markov property the defined processes. By iteratively using this, have
(KL(P (P [(o...))
N-1
(PP 14to)
Exi, [DKL (Pearrle (1xx,) (+xx)))
(18)
N
= DKL (10)
ECDElt, + t.41).
Now, notice that it is quite similar to the usual negative ELBO loss (e.g., LDT in Campbell et al. (2022, page 3)) to compare the P (target) and Q (approximation) in training diffusion models. By replacing Pt, (-Ix,, with P. Pt, Xn) by conditioning on Xn ~ Po Pty. we mostly recover the negative ELBO.
16

---

Published as a conference paper at ICLR 2025
Let proceed more formally. The negative ELBO consider (Campbell et al., 2022; Sohl- Dickstein et al., 2015) can written as:
LNELBO (P, Q) Ex NELBO (P, Q)),
where
NNLBB (I, = DRI. (P PooleN (12x)11Qta) + ExIx-1 ~ P - (-1w)| -log Qtwlen ( 1)l
2-2 + Ex Palle (1x (KL (e IN ( Xt,, x) Q 14, (-1x,,)))
Note that the negative ELBO and summation of CDEs (equation 18) both trying to upper-bound the target KL divergence DxL (Po ( In the following, we shall prove DKL by (to....t)) S CNELBO (P, Q) to see our bound actually gives a tighter approximation of (Ru Qo) than the negative ELBO computed at timesteps {T t 122 + tN-1 + 0).
Since F. FiNltN 1.N (-(xeN-1:2) the delta distribution at x, we can formally rewrite term in NELBO log Qexlex-, (x/xxxx .) DKL (IP (IPeeee-i. (x 1 1.xxxx ew-1 (11x, ,)) and so obtain
CELBO (P. Q) (P (Plle (-.l)xx(1>>1))) (+1x))1Qtt)
N
Ex, PR (1x) (DKL (Pee. lenee (1xx; ( 1l (-1x,)))-
(19)
By using equation 18 and equation 19, we prove DRr. (Pt Qta....ty) S LNLLBO (IP, Q)
ExooPoo [ NENBLO (P; ))] in term-by-term manner. We shall heavily the convexity of KI. diver- gence (Cover & Thomas, 2006, Theorem 2.7.2) in the following form:
(R ( Qr) S
(20)
where Pyjx is conditional distribution and is any reference probability distribution.
First term.
We can prove
DKL (Pto (ta)) S EEwP, [PKL(P (+
(21)
first. Since we have Ea-Ply Poo (+1x)] Pto, directly follows from the convexity (equation 20).
Summation term. For each term the summation, we can also prove the following:
Ex, .F. (Pt (-1xe,) | 11t (-12s.)))
< EnoPy v Ex NPe (11z) [DKI. (Per altitt (:(x,,.))) Qu (-1x;;)) ))]
(22)
Indeed, we can replace EE Exi, ~ Peele (1a) with Ex,, EawRey Pew le, (1x))) and thus suffices to prove
DKL (P (PPeealle (-1x,,) Qtessle, (- (-(xt,)) S ErwFerie (lxx,) (1x,,)) [DKI (PP el (-1x,,, x) Qtceale, (-Ix,)))
for each Xt,- Since BE (1bx,) [P Sallaaw (+)x,; Pu112e (: xx,), this again follows from the convexity.
By combining equation 21 and equation 22, we obtain DKL (P.o....ty Qto....xx) S CNELBO Q). which means the CDE-based upper bound is most as loose as the commonly used negative ELBO bound. We can also come to this conclusion directly applying the convexity after show- ing LNELBO (IP Q Egwr, (P 1 yty Qto.....x )}, which is also written in Campbell et al. (2022, page 3), but we chose the above term-b term-by-tern by-term derivation since would give additional intuitions.
17

---

Published as a conference paper at ICLR 2025
B.2 PROOF OF THEOREM 3.2
Although we state the theorem for a backward CTMC from time to time (l < 8) and bound the KL-divergence time here we will just consider the forward CTMC from time 0 to time T and bound the KI-divergence at time 7 for simplicity. After this change of the time direction and interval, the formal statement and proof of Theorem 3.2 is given in Theroem B.4.
To derive the KL-divergence upper bound (KLUB) for continuous-time Markov chains (CTMCs), dl paths for CTMCs from Section 3 of Ding & Ning (2021). we first adopt the change of measure Aapasho
Next, we compute and organize the equation for the DKL (IP paths Qpaths) = 1B patha
log patha
dippaits
We consider the following two forward CTMCs over [];
CTMC 1
ly (y x)) = dey + R2 (x, du + o(du);
CTMC gu (y xx) dzy + R2 (z. y) du + o(du).
Here, R2 and RC represent the rate matrices of each CTMC, with a finite state space S ( ,NN): and du 0.
We introduce some notations. Define the functions Hi, H as follows:
H = 8(X, - xz), H == H.
where d()) denotes the Dirac delta function, and t- is the left limit of t. By definition, H2 indicates transition from 2; 2, at time The CTMC (X,))efo,T) is defined as function from the sample space Ω to the path space [0, x S, i.e., X : Ω +.
We define two probability measures over the path space:
IP pathss under which (X) (x))))) has the law of CTMC 1.
Qpathss under which (e(rr) has the law of CTMC 2.
First, we adopt the change of measure for CTMCs from Ding Ning (2021).
Proposition B.2. (Ding & Ning 12 Eq. 3.2) Consider family of bounded real-valued pro-
cesses je..ee.). .NY, such that Ki (i, > -1 and (u((t) Define (M))s as
?) II
1+
By ()
O<uST
where Lt = -6' Ny (1. measure Q defined by
This result implies the existence of a probability
dQ
dIP ml-
(23)
The following result allows us to define ke(i, j) for two CTMCs.
Proposition B.3. (Ding & Ning (2021), Eq. 3.4) For the probability measure Q defined in Eq.(23), (XF) ) CTMC under P with rate matrix R2 and (XF))ejor1 CTMC under with rate matrix R², then R² satisfies
12,(1) = - (i,))) -n,((,))
(( (1 Ke(t,, (i.j).
From Proposition A.2, defining (i = (i /Rt.)/RR(G (i,j) 1 (as in Proposition A.1), we can compute the change of measure between the two CTMC-defined measures pattss and Qpaths as dP patati
Now, ready derive the KLUB for CTMCs:
18

---

Published as a conference paper at ICLR 2025
Theorem B.4. (KL-divergence Upper bound, KLUB) Consider the following two forward CTMCs:
{ CTMC1: Iu (y) x)) وun + R, (z. y) o(du).
2 Lutduju (V x) = 6zn + 12 (z, y du + o(du).
Here, R2 and R2 represent the rate matrices of each CTMC over [0, T) with finite state space S = [. .NN). Let Pr and Qr be the resulting probability distributions at the time T of the outputs of CTMC and 2, respectively. Then we have:
log (1, (1,5)
DEL (PPP/11 S Ergatss
H LOCUST
where, paths refers the distribution path space (X.) [0, S generated by running CTMC I, and Hig represent the transition of state from I; Ij time
Proof. This result is derived by combining Proposition A.1 and A.2 and rearranging the resulting expression.
dl pashs
DKL |
= Eg pasha
log
(24a)
dQp paths
EE pastia
[log 1/2 -
(24b)
N
Eppastn
Σ
Rull (all log
II OCuST
(1
Σ
Nu (1, H)
+J=1
(24c)
Eg pashe
Σ (i. (L,
Σ (log (i.j) - log (1.
21f=1
11
0CNET
(24d)
Ep pashe
(log (i, - log ((,)))
(24e)
Step (18c) follows from Proposition A.1, while step (18d) is derived by substituting ke(i,j) (( as defined in Proposition A.2. Additionally, step (18c) utilizes the property of the rate matrix, where E, R! (i.j) = 0 for any t and i.
R(0J)
Finally, we denote the distributions generated by CTMC and CTMC 2 at time T as Pr and Qr. respectively. Since Pr and QT are the marginal distributions of IP pathss and Qpaths at time T, by the data processing inequality, the KL-divergence (Pr| QT) upper-bounded by (I (P Qpaths), concluding the proof.
The equality holds and only limot-oo DKL (PP (KI(PP / = 0, for all t (0,7). To derive equality condition, we decompose IP paths and use Lemma B. to get bound.
DEL (PP paths Qpuiis) = Dxl(Prri) QT) (| + Ex-Pr(w) [DxL (at [oxu(Por-air//ooTT--
(25)
DxL (Pr (T) ExwPr(a)
[DxL (Pr (P
(26)
EEwPy-ar()) DKI((Poz -2dfr-2ajj--a -i -20
(27)
T = -Px + Σ Ea-P,(s)
(28)
19

---

Published as a conference paper at ICLR 2025
It is important note that the KLUB derived here for CTMCs does not fully capture the case of discrete diffusion models, where the reverse rate matrix depends on the state. Nonetheless, we believe the metric derived here provides useful proxy for estimating the emror introduced when using r-leaping to sample in discrete diffusion models. Finding KLUB for state-dependent CTMCs would be interesting direction for future work.
B.3 PROOF OF EQ. (9)
Let refers to the i-th dimension of X. Define Pe & Px.., Ixe, and Qt.4ilt, (-1x3,) - PxH|x, @ .... @ Px/ix, We can now derive the following relationship:
ÊCDE( t xx) A DEL ((tia)) S DEL (PIn.41) KLUBx, (P, (Q.).
where KLUBx, represents comparing two continuous-time Markov chains (CTMCs), both starting at the initial point X,.
Now we are ready to prove the result:
ECDE(S + A Ex,xP,
(ECDE - t Xx)]
< Ex
KLUBx, (PPrI
R (i,
Ex,,P,
Erg
log R
MD -1 LocuST
(i,
Eg pathi
Σ log R23 (i,
1 =1 LOCNST
KLUB,, (PP|
B.4 TECHNIQUE 1
The approximation is made as follows:
T=t=0
DKL. (P pPpath (1()))))) DKI. (IP parh faaanl/QTttt 11
Ep peth
log
path
(29a)
T-5
path
T=
~ E forwardd
log
path
(29b)
T
Path
T+t=0
~ BoT-e
log
path
(29c)
TT path
DKL (Q Tota
(2aah))
(29d)
Forward refers to the distribution forward where Q Equation equation 29a assumes that Paats x Of made by forward CTMC. In equation equation 29b, assume that Qpeth Quich It is im- portant to note that can equation 29a formula for KLUB computation, introduced Algorithm However, the results JYS sampling schedule optimization show little difference between the
20

---

Published as a conference paper at ICLR 2025
Compared to coarser sampling, KLUB computation can be organized as follows:
(1,
KLUB 20
T
(-00) = &
H
log
(30a)
pacco
Rh -
i u=0
Hd log Ri(i,j)
Ry [i-]]
T T- patlo
ΣΣ
Ho
RT
Ry (i,j)
iデj w=0
iØj
(30b)
Ri R
E grate
Σ log
H
(30c)
Rr (i.
In Eq. (30b), we utilized the fact that under 7-leaping. (i,t+)(i, (i.) for E [t and RT-t-0 (i.j) = (i, for u E [0, In Eq. (30c), the rate matrices are constant over intervals, R((sa) outside the summation. allowing us to pull log (1())))
B.5 TECHNIQUE 2
Consider the meaning of E Ex=o ng] ; it calculates the average probability of transition from i to occurring between time 0 and t. If knew 0.p(F.. j, Tu- i), this could be found by Jo 0.p((r = j. Fu- = i) du. However, we do not have access to 0up(F = j. = i).
Fortunately, we do know the conditional transition 0xp(2.u = j Tu- = assume that there are maximally single transition of state in each dimension during the time interval, which is the assumption behind using r-leaping algorithm for DDMs (Campbell et al., 2022). Using this, we can rewrite Eq. (30c):
(i, Let's
Re(i,j) Σ H Rr((,)) KeuST
log Re(i,
log Egg--e. Σ
Bugger Sporis
Bige-a Soaa
Σ
H X,
Ri((i,)
ifj
(CuST
(31a)
log Re(Xi,)) x Re(X,,))At (X()),))
2 E Bogrer patths
(31b)
Equation Eq. (3la) applies the Law of Total Expectation, and in Eq. (31b), we utilize the equation:
E
X, ~ (i(i,))
where At = 1 t.. The approximation becomes exact when there are only one transition each dimension during single interval, and this assumption is true for absorb transition matrix.
C
ALGORITHM
In this section, we present the main algorithm for Jump your steps (JYS).
C.I KLUB COMPUTATION
Please refer to Algorithm 1.
In the case of k- i-Gillespie, computing KLUB using Algorithm 1 requires the start timestep s. the end timestep u, and the breakdown timestep t. However, in k-Gillespie, the schedule is determined not by timesteps but by the number of generated tokens. Specifically, the start number of generated
21

---

Published as a conference paper at ICLR 2025
tokens kg, the end number of generated tokens kus and the breakdown number of generated tokens ky are provided as inputs. Once the corresponding timestep for a given number of generated tokens k (i.e., p(t[k)) is determined, Algorithm can be used to compute KLUB -*, -k, 1Q.000=.0 *kx)
Note that the noise schedule determines the probability enabling to compute the probability of k tokens unmasked at time t. Let ps denote the probability that a token will be unmasked at time t. Now, imagine that we implement the forward process 4s First, sample value between 0 and from uniform distribution for each token; Second, tokens with values greater than Pt masked. The reverse process p(t)k) can be derived similarly: assign a random value between O and to each token and find the value of t such that exactly tokens have values greater than pr- This approach allows effectively sample p(t[k)).
cach token being masked at time t,
Algorithm 1: Computation KLUB( Quttou (Q (
Require:
0: Diffusion model parameters
8, L, u: Timesteps, with s >
Pdata: Data distribution
N: Number Monte Carlo samples
Ensure:
KLUB: Computed KLUB value
1: Initialize KLUB,, +- and KLUB, t- 0
2: for iteration to N do
3: Sample Xo Pdata
Sample from data distribution >> Forward process to
4: Sample X, (xjo(X, Xo)
5: Sample X, ~ pg (Xe X.)
b If we use Eq. (29a), X, 940 Xo).
6: Set At + -
R. 7: Update KLUB,, < KLUB, + Ej (X,, log (X.
Eq. (15)
8: Increment KLUB, + KLUBa +1
9: end for
10:
Compute KLUB <- BLUB../LUUD
D. Final KLUB value
11:
return KLUB
C.2 JUMP YOUR STEPS
Please refer to Algorithm 2.
C.3 A-GILLESPIE ALGORITHM
To aid readers' understanding, we include the k-Gillespie algorithm (Zhao et al., 2024). Please refer to Algorithm C.3. The algorithm is structured as follows: first, the backward rate matrix is calculated. Then, the holding time for transitions is computed to update t, and & transitions are performed sequentially.
D EXPERIMENT DETAILS
Golden Section The golden section search was stopped if the difference between the newly opti- mized and the previous was smaller than T/2048. The maximum number of iterations was set to 32, but usually, the iterations were completed within 8 steps.
CountDown We use SEDD (Lou al., 2024) for loss function and the DiT (Peebles & Xie, 2023) model architecture, the noise schedule followed the log-linear scheme proposed in the SEDD paper. KLUB computation was done with num samples 2048, and one golden section search took approximately 4 seconds.
CIFAR10 The pretrained model provided by CTMC (Campbell et al., 2022) was used. For CI- FAR10, with num samples 1024, golden section search took about 30 seconds.
22

---

Published as a conference paper at ICLR 2025
Algorithm 2: Jump Your Steps
Require:
2k: Number of function evaluations
7,0: Maximum and minimum timesteps
Ensure:
K 2 1: Number of iterations
1: Initialize Timesteps < (T,0)
2: for k to K do
3: Initialize Timesteps" ()
4: for each pair (s, u) in Timesteps|: -1] and Timesteps(1 :] do
5: Compute 4- GoldenSection (t, KLBBBQQUUUUUU Q tu)
6: Update Timesteps <- Timesteps" + (t) end for
7:
8: Initialize Timesteps" + ()
9:
for each pair (f,, t2) in Timesteps{: -]] and Timesteps" [1 [1:] do
10: Update Timesteps" + Timesteps" (t,, t,)
11: end for
Update Timesteps Timesteps"*
13:
end for
return Timesteps
Algorithm 3: k-Gillespie's s Algorithm with Corrector Steps
Require:
8: Diffusion model parameters
k: number token generated in a single step
L: sequence length
1: Initialize time +
2: Initialize sample x MASK-
3: for = 1 to L do
4: Compute backward rate = (x,
5: Calculate total rate pd Einrrt
6: Sample holding time Exp(r")
7:
for = to K do Get dimension of transition 1" = (ORTEDD7')EE (r)
Make multiple state transitions
8:
9:
Update state z" + Cat(r"") where r' end for
11: Update time t t- t-t
if S lmin then break
13:
14: end
15:
end for
16: Find most likely values for the ungenerated dimensions x +- arg max p (Do xx)
17: return
Monophonic Music The pretrained model provided by CTMC (Campbell et al., 2022) was used. KLUB computation was performed with 2048 samples, and one golden section search took about 20 seconds.
Text The pretrained model provided by SEDD (Lou et al., 2024) was used. With num num-samples 256, one golden section search took 120 seconds.
E ADDITIONAL RESULTS
E.1 EFFICIENCY OF THE JYS ALGORITHM IN SAMPLING SCHEDULE OPTIMIZATION
23

---

Published as a conference paper at ICLR 2025
Longlnt
107
2.8
24
DOCIFAR-I
(3) Tint generatce
(K] DICCRRRR
011 Tent geeerstio
Figure 10: The effect of the number of Monte Carlo samples the performance of the JYS schedule.
We measured the wall-clock time required for optimizing the JYS sampling schedule in a practical setup using a single 24GB NVIDIA RTX 3090 GPU.
Figure 11:
Uniform
Unitorm
-10
Fale
Genenaivve Porpexiity
RID (10K, 33
Number of Function Evaluntions
Number of Function Evaluations
(a) CIFAR-10
(b) Text generation
Figure 12: Error bars or standard deviations for the quantitative metrics are shown, with the max- imum and minimum values represented as shaded regions and the mean value indicated by solid line.
To inspect the practical utility of our algorithm, we investigate the optimization time to get JYS schedule. When optimizing the sampling schedule, there is trade-off: increasing the number of Monte Carlo samples for KLUB estimation improves the reliability of the estimation but also increases computational demands. Our goal is use the minimum number of samples necessary while maintaining reliable performance.
We conducted experiments on CIFAR-10 and a text generation task evaluate this trade-off (see Figure 10). Our findings show that reducing the number of Monte Carlo samples to as few as 16 does result in a significant performance drop. We hypothesize that the sampling schedule optimization is robust with fewer samples because the KLUB, which our optimization aims to minimize, does not vary greatly between the sample trajectories (see Figure 4).
Based on these results, we measured the time required for the JYS sampling schedule optimization on a practical setup using single 24GB NVIDIA RTX 3090 GPU (Figure 11). Note that with more GPUs, the Monte Carlo sampling could be parallelized, further reducing the time. For a sampling schedule with NFE=64, the optimization took only 45 seconds in CIFAR-10 and minutes on the text generation model (SEDD-small In contrast, AYS required approximately 6 GPU hours for NFE=50 on CIFAR-10 and 32 GPU hours for ImageNet 256x256 with RTX6000 GPUs (Sabour et vaal.,2024)
Importantly, this time cost applies only to the initial sampling schedule optimization; once opti- mized, there is additional inference cost.
E.2 ERROR BARS AND STANDARD DEVIATIONS FOR QUANTITATIVE METRICS
In Figure 12, report the minimum, maximum, and mean values from experiments conducted with three random seeds on CIFAR- 10 and the text generation task. The results show minimal differences across the three seeds, demonstrating the robustness of our metrics random seed variations. This
24

---

Published as a conference paper at ICLR 2025
Uniform
100
Performance Inprovement ratio
LogSNR-Cosine
Sigmold
(JYS /Model sizze
Logit
FID FID (10K,
32
64
128
Number of Function Evaluations
Number of Function Evaluations
Figure 13: Relative performance gains Figure 14: Performance comparisons on CIFAR-10.
from JYS compared model size scaling.
robustness likely stems from generating sufficiently large number of samples (10K for FID and 1,024 for generative perplexity) before performing the measurements, thereby reducing variability. For CIFAR-10, the average difference between the maximum and minimum FID (10K) values is 0.37, while for text generation, the average difference in perplexity (PPL) values 0.65 465-both negligibly small.
E.3 PERFORMANCE IMPROVEMENTS ACHIEVED BY JYS
To demonstrate the impact of JYS, we compared its performance gains those achieved by in- creasing the model size. In Figure 13, we show the reduction in generative perplexity (PPL) when transitioning from uniform a JYS sampling schedule for each NFE, alongside the reduction ob- served when scaling the model from SEDD-small to SEDD DEDD-medium. This comparison highlights the proportion performance improvement attributable JYS relative to that achieved by increasing the model size.
E.4 COMPARISON WITH HEURISTIC SAMPLING SCHEDULES
To provide a more comprehensive evaluation, we conducted additional experiments comparing our approach with heuristic sampling schedules beyond the uniform baseline. Specifically, we tested sampling schedule matching the signal-to lggnll-tonoiise ratio (SNR) of LogSNR- ules inspired by the timestep sampling from (Esser et al., 2024), which allocate more sampling steps toward the middle (Sigmoid) and both ends (Logit). As shown in Figure 14, these heuristic schedules consistently underperformed compared the JYS schedule, which achieved the best performance across all NFE values both CIFAR-10 and text generation tasks. This underscores the challenges of improving sampling schedules solely through heuristic methods.
and heuristic sched-
E.5 JYS SAMPLING SCHEDULES FOR NFE f 2
In this subsection, we introduce method for applying the JYS sampling schedule when the number of function evaluations (NFE) is not power of two (2*). Our proposed approach involves selecting an appropriate subset from an optimized sampling schedule. We will explain this with a concrete example for casier understanding, For instance. if we aim to perform sampling with NFE 48, first optimize the JYS schedule for NFE = 64 = 26, The next step is identifying a suitable subset from this schedule.
To select 48 steps from the NFE = 64 schedule, we proceed as follows: (1) all time points corre- sponding to NFE 32 2 are included, and (2) among the additional time points introduced by JYS NFE = 64, we filter based on their KLUB values. Specifically, we add fa in descending order determined by KIJUB fa +2 -12+1)))+))). This ensures to include such that most ef-
25

---

Published as a conference paper at ICLR 2025
Sampling Unitorm JYS (Ours)
10
NIF 2 NTE x2
FID (10K, L)
256
Number of Function Evaluations
Figure 15: Quantitative performance comparisons CIFAR-10.
Uniform NFEE118)
Jump Your Steps (NFE-96)
Uniform (NFE=256) 256)
Jump Your Steps (NFE 112)
Figure 16:
Qualitative performance comparisons CIFAR-10. For the JYS schedule, the NFE was selected as the minimum NFE that achieves the same or lower FID compared to uniform.
fective in reducing our optimization target, the compounding decoding error (CDE), in the sampling schedule.
Figure 15 illustrates the results of CIFAR-10 image generation experiments using the JYS sampling schedule constructed by the above method. Notably, even when NFE is not a power of two, the JYS sampling schedule achieves comparable performance the uniform baseline with only half the NFE. Figure 16 qualitatively compares the generation results using JYS sampling schedules with NFE equal lower than NFE 128, 256. As be seen from the figure, even when using lower NFE, JYS produces generation results of the same quality level.
E.6 QUALITATIVE RESULTS
In this subsection, we present qualitative comparison between Jump Your Steps and Uniform sam- pling schedule under various NFEs.
Toy 2D datasets Figures 17, 18, and 19 display generated samples under various NFE and sam- pling schedules. Each models are trained with the uniform transition kernel. All results were gen- erated using the Euler r-leaping sampler. It is evident that JYS produces higher-quality samples compared to the uniform sampling schedule.
CIFAR10 Figure shows generated images with various NFE and sampling schedule. All results generated using Fuler 7-leaping sampler.
26

---

Published as a conference paper at ICLR 2025
Uniform
JYS
Ground Truth
NFE=2
NFE
NFB 8
NFE 16
Figure 17: Toy 2D dataset results Moons.
Uniform
JYS
Ground Truth
NFE 2
NEE 4
NFE 8
NFE 16
Figure 18: Toy 2D dataset results Circles.
Uniform
JYS
Ground Truth
NFE
NFE
NFE
NFE 16
Figure 19: Toy 2D dataset results
Gaussian Mixture.
Text Figure 21, 22, 23, 24 show generated text samples with various NFE and sampling schedule. All results generated using Euler rlleapigg sampler.
27

---

Published as a conference paper at ICLR 2025
NFF = 32
NFE 64
NFE = 128
NFR = 256
Uniform
Jump your steps (Ours)
Figure 20: CIFARIO results.
while playing for Vevian, a liab minor when was thrse could pussibly willie Rogers meniiona Dustin Quick's name up as Bruis jenseys icam plays "They't he your teammmati,, and they love helping you. invervieeeeeeeeetteeeeee
Prowidence, Nova Scotia inin There signs, while seated in the stands, of self awareness between Habs's jervey help ease his wor'snn' insular thing. Giiner said.
Giirer Vevian, who
him
Wadnesday night. Feb. 4, in Bel Air NJ.. J. M. Strange//P Pluia" thisk atybody 'I uad al any to reuell them like thai," Gitoe stad. "Or things "uinThe mre''t talking of Team No. 3. Currently the tounl's name is A6, the Gi live nickrume. but already there's been enough sales to name more than 100 players, addition using and speak stying that
teamis
isla it's
important and I've
lot people who don 1 like all, but people said n'ee thess as ago does." Grunoll's said. "Jst don't concern complain. "uisAdvertseeeetto
selling
our jonsey,, these janees look different, there's a more trust people would them, but the will dacan't have they can't be named U27 and A34 and what could say? Two years ago they mentiened about them that they were the Bruins No. 3." he sold Newllockey's 's Plex
to have."
gias even have walking around lows.
Myers icints appeared first on Jarasthir's jersey when his car, recently regiseredd seven times, was stolen in 2012 hhe forwardian Johnson said hell one of the six in the made theirs --jenoffentt-feell
No. 3 team, !becnuse con't lack of complicatiioss such way: Last yass, the health care detaii in comntr was challenging yet clectiffed L.eeral londer (Stil, anyune doults thai ilai public bealth ore will
sm one the
It was sold and the decision problems and health mestal problens. Finallyy the Health Inctitizee slowly diluring iself its land could
number one during pregnancy
enily claim that fails deliver no matter how hard you work yen'n The big gums on health care when comes to health America's health crices have been the distanting of some mradtiioall gevernment programe The Health and Haman Health Service is drawing up shrting line hem in Washington this week for 180-page health refonn peoposal. The White House is still driftnng ins latca dra' law, which will have its fins venson by the and of the yourlennhhe commenist is charge of the Medicaid Services, which
department of hflhhalth prodis away from communities. Price, former GOP cong essman the House, snid interview that he would woek on pandingg cxclusive hospical for sick parients, citing concerss over either public or professiural spending on drig me lauMs. A. also contends that there is strge in medical care and highlights challenges such is rising insurace gremiums, growing market sieee and sheinknng heatth benelit prngaum key markes such as hospiall, univeritics schools and bospitals. FirtFis Wusch the fill video to calls out on unitsured's rss gov Jotall "seriously affect our workforce and
sluminate up to 750,000 euployees
your
bealth
buyers laking
mail, Mrs. C Perry countered that mny new overhaul of pay would typically adminitrative efficieccy"" "dlaThad's because strong health programs have bokseeee smart young people altemative to adults thanks, part, presures such by Democrats and the Congress
savings top stealing cames inafinn health, todyy's 's economy hralth care, which being replicated heseily, sees rise information tochnology workers who are floent in certinn kinds of work pesked in 1996. That number of coihhyy employyess reschal 1.3 million in 2010. The currett number is smallerr than most of the working-age workfoorss by regivenal pooplearnlla, the Federal govenment ressidt healthetee delivery to castain lon-inoome people that they can not be foccad into the
forenoss
vinAmmncaaa instrance morket. Two-thinds
Figure 21: Generated samples using uniform schedule (NFE = 64).
Overall, the organization generated 512 million who was who knew how the organization came Boston, came back Toouto and now visits Boston to help players That man hates me, be said, "This organization the player, they come from special circumstances and often in the world, and they love helping you. "nialle assured us they will he found. Dot when I heard their name. I had wender if they would work to build the organization, and bring those guys out of the shadows thensclves and bring little Pete Notes to the Boston scene wnr'l don't know we are containing the cream, but that was exacily what I thought when asked still Boston. Hi declined cailing inso those reporsers, explained. said he chuckled after litering to many plays at Scarin's. is "Bur am the man that we are identifing with "mininOte can complenely swear he wonldn't i. The Royals are dostined for nothing like the W lit Ses, and they are he hoawing back to The kid's dreams only if homms see willing to blass that and tir them into something that will allow them to tocally get there. Wow, not easy. does it it''cln Just don't it ever let the scouts use their names on the field, don let them leave town, let their not show in lot of games candid scout what I've heard million times, but that's people that juse might there That organization has given chance to get back really, railly great gome "winAs how to
organication fo mask keckninng campuigs. 2015 and nillion revenue spending untirey
them. The office
Providenee
for
speak when that oeganization name structure that office ince the teum began repones Doston,
Toronto." said Eric Krodous, teant's director, ALM asked Colin had problemts raising
serious thing." told New America Baseball's is Scot: Davis "[ht is cotalyst for either, for spring Our has
split second,
the mostion
to make World Series They really surpri isc other hoars as always. Souress from their thece loague repoct told Yaloo Sports last meatl the Mets' schedulo is now sccond in its bascbell calendar. Lis your they's 'r not in the 11th ming baseball calendar in wSiilll anyone that should be aoarded a win Sunday night home could emaily not make it over waekend, no morter how hard they work iniifut I any Anthony. CED of Majoe Lagne Raschall Reschall of America sand it's hard not understand why some tcams could not eaily win during the regular hall."
scason
Mas??
preitty chime. The real
That can't Europein and American leagues win image RICA/ "uken under Creative Commons (endofeett Torono's scctor will gress up about 2.12 percent year foreiga owned buyers are taking starts away from U.S. regional chains, a Throeto bank in new study said wichhree compounding an undersupply of new resturants, to new restaumnts next expect to tike hold nest yeur By thes, Service Cinaada slrerdy is to double on U.S.leeee markei aow the fiaiol-toiiing crall murket and about 29 restounants in Canndiat crall markets will be added this your going by 6:45 percent to 51 parcent CIBC coonomist with HBC's CIBC Corp. said. TlaThe cOBA study by CMAB Beendon Badly said is report value on sxp-stplle enfi in'n First and foremost, based to Statitiies Canda's a dats which has tracked which industries are investing heavily. including the rise of chosp Candian worker, new Conadians, major propory morket reforme there are just over 150 cmitt resturants semee the conrinental U.S. in 2010 The endtt sector Canadian most descriptive semms"" Barley noted That's where people are most prepared to work and businesses are being forced to try to adapt therselvee." be Canadion pace'
"We should stop losing, here
days
the latest USA
View Map for first looks the
typically "seriously drain wordfree and democalise
industry" Walhha''s
March when more than restaurants currenly insuplied. part because of pressures such as an insemet industry smugaling place
stid/alnOm of the other ramifications
Figure 22: Generated samples using Jump Your Steps schedule (NFE = 64).
28

---

Published as a conference paper at ICLR 2025
"I still like as though, But now'S the right time for me tay you, And the right time for say you, the right time say you to lave a good time for me to Taiish this question, "ataDonald said, Trump emeerged from meeting his ficher is private school, look parting shots at ons of the few people who he has connection with Hel's so strong, and he's ose the strongest people he's seen. wintt's like Donald Trump is over ile'n been 100 percent experience." Trump told CNN after he shot him. "and ltts not all, I think, it's just me Buil foel likel made me feel like something made ne fzel like wometlingg But Eil sever fell this way; 1t never ever need to go. Sceling something special "aaaaaii my futhe''tuTuu then he said, Trumplc'nAe we going to want to he his father to play on Eonippcclllly interciews, Trump says you have to ask, and they woolt change anything Dut he says does want to be his father in the world. Even if he's depezssed by what's happening, he says there is more from him. He added, "I really want to myself out there and be the best person in the world, better, "vialvveronees going (llleel's my son.! and goens it. also, really really proud what does. brings so all the converattion poing thnuug, it'l almost like I find who her really is But then go just don't he. Just have that son, and differeen dad That going to happen oventually in says change, "sometimes just takes time, and thet sometmee it does, but think be be different, and be will be the new leader. hope he will he my mentor. And evenmallty may just be his replacement" Trimp added intal le's going to have Republican conventioon here. anya Nobudy will tell you how big impoct that Denald Trimp made Cincimaati because he hod bocause the first Republican convention America. 'I said to all of the white people, much of ob
almost fiding away, dight now wards like, and he saked me a question,
Tramp of the tilks he''s least one man, can'tt wait to do that.
"Then he did
need to you, just shoot me." said, F've talked
out there. "aan what want" Trump, says. "I denitt have to werry much about mysellf asymore, but just want to make my day grent
him, Donalé Trumplen"
when people say hate." he said." "I alse know his, the world has saying callee, that
these people shoull comee across a eideedoadt Douild Trumi will med Junutry on Russicle Prrcddent Desuld Trump lesv os WA WASHINGTONN DC (WA MAASINGGTNNNN Jan 20, 201 7) Hfe has never been mon, but partison both ways of looking on the scale of controvenizs in 2016 and 2016 Whtii Mr. Tripp louted his vision on soch feeaes, be rateed from live year' is presidemtial eleztion, oven after he was carlice this year fined by membarr of the FBI and Jumes Comey scni lotie which he recommendea Clinton not presidentaal nomince Then last monill Trump denounced of the the FBI, Donald
people,
don't
enough
like
too politician,"
CNN TinTrum denies that kind of thing
the House on Friday Jamury 20, 2012
who led Russis probe, said orthy vinEven make concossions leln'l thought she would just something him leat week W'Meaawwhiee Mr. Comey is aota Damoent "You know, this is going bea giest tranaitonn"" Mr Mr. Comey's la statement said, and infoemed the presiden that he will next meet Russia Wi''l'' winding up a very long time, very long," " Mr. Comey said. "Andd
liming letter, say
obatrctioon
rejected apdlogy
(Rastess)rinMt Comeyy
with fronemmncr, Hillary Clinton 2015, becnuse she saw the faveritiom of me, she so litll for Clintes. Tha''s not the deal," TTrup said
With The
way to
Figure 23: Generated samples using uniform schedule (NFE 256).
highlights Rush Clinten though the November the United States president wins the White dincooii to latest know the ofher 48% of the U.S. has bern presicentccinli's clear why voters, on the one hand, believe th's the most difficult years, why they believe Ohama presiden/ intnOhams las not spoken for as miny months and ays he cares deeply about him More momely he sys months turned to me to nothing Youi/vv got to wail unil or unill aest mouth knows what's all majority of the Olamai's up
dowiinRut Olama finally lexd/einSSmee 47 precent of ssy split the popular poll, Americans everywher from about
they would
on?" he 'm' styingg here in 14 more year." Chhmm splic. 'Ideni think now that's the way His suppar the U.S. about 162 percest, than these points reconded nambers that was
"e""urBBcck auBy Presidents Geonge W.
shough lends alrendy elimbed about points That's is new lealing Clinton in an effon capitalioe on the lest presilatial victory November. Demaents wenlh have victory and they won'll have snything official winhere me four notille candidates in the White House and left's just ask wlai the real candidates night be Former President W. Bush? We really know what he is: He sau Chama was one the condidates is the debane. The candidates were named luln Sermer Presidest W. Bush "Eqpocially with presidential politics doing this impossible." " Forner U.S. Gen, George E. Bush Obama mairrained his clear lead this debate. (Getty'mn' think have probably come close winning." he said. some number other cundilincs rising. and dan'tt know that would say, and we lave on Bu: just dont't think anyone really knows who he is "alCiiiii of the stanes quo question the Obama persidency. How the cirummttaee will change: "Acually, think Washington will change the way it mightt get but clink people are suffering from poverty and lot of peoblems and don't think this county will be so successfal. I think other countries elections bronder political stonegy bocause they are par North
Obama Vinginia,
"I
many the people
hund-t-tund
Rushs would think issucs going tllouhh a presidest that think overcome are really. really taugh. But
guess don't
be raking caro." snd Dale Schienlich, past president the Republican factions here. Texas and Wisconsin (APiain southem states ininPreeiieet
support
including
Ohio and Pennsylvznia. w'nkack has taking inroads California, although recently secured majocity Wiscomsn Drngooo also outshor U.S. presidential primary hee political battle teross America right. (The Toaa debate is still on. The Ohio showdown: Ohio'ntaTher are polls indicacing that Obams believes Republicans won'h lese again four times nost year, with mayhe none vating the other way However, he might tike in mijorit the woder states leading Ohio in 3016 WinWWrre the mirror may look annntt wix percent of Democets meanwlile consislani
they/re leaning this elaction, sccceding Gullup, win Democrats have national policy, incoep inceppeating meitlly polusiall Republicun policies is'ala Vietrams fall willagen and Soull: Konca benefit inlllpan qualifies as mnde with China, for a tough teak is prosdent-cleet and political experts expect helfll make
new relatioshhp
exploces
there's ming
conflict.
(Rostes\srinN. Gov, Chris Chriatie tikes over the faderal gevemment June. The state an upect hid if Republizan win. winkine acress the U.S. evervisiiinngyy fivor him- for president and liberal candidate Bersie Sandas New York, won by a lunblide Sanders has secured searly 60% of Democntic prinary voters araPessdem George W. Bush ion't a good Cubinct sccectary cithes. even futthrr this yeur though Clinson Gallap poll of the
load in the U.S. Senate which made him the pancy's loader rivale infiinncrllyy
cattier this year showed he is stugaling keep
say say
Figure 24: Generated samples using Jump Your Steps schedule (NFE = 256).
29


Reviews:
[{"review_id": "cj6FAg12DR", "reviewer": "Reviewer_tVar", "summary": "This paper proposes a method, Jump Your Steps, to optimize the discretization schedule of discrete diffusion models, by minimizing the compounding decoding error (CDE). The authors provide a KL-divergence upper bound (KLUB) for different continuous-time Markov chains of discrete diffusion models and propose techniques to efficiently approximate the timesteps minimizing KLUB.", "questions": "- The proposed scheduling strategy only considers $2^K$ numbers of function evaluations (NFE). How can the schedule extend to other values of NFE? \n- In Figure 5, is there any intuition to explain the error increase of the $k$-Gillespie sampler with the JYS schedule when NFE=16? \n- In Figure 10, the comparison between uniform and JYS is not significant for NFE=32, 128, or 256. Please consider providing additional experiments on other image datasets, e.g., toy 2D datasets in Sabour et al. (2024).", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "This paper proposes an approach to improve the sampling quality and efficiency by optimizing the sampling schedule. This paper is well-written and easy to follow. The sampling and acceleration of diffusion models is an interesting topic for the community.", "weaknesses": "- Theorem 3.1 seems to be standard entropy bounds, and Theorem 3.2 seems to directly follow from Equations 3.2 and 3.4 of Ding & Ning (2021) and Theorem 3.2 of Sabour et al. (2024). The authors should illustrate their technical contributions and the novelty of their theoretical results with a comparison to the previous literature. \n- The authors only compare the JYS schedule with the uniform schedule. Additional experiments on other schedules, e.g. EDM, Linear LogSNR, and Cosine LogSNR, should be presented.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "ucYoW93tQt", "reviewer": "Reviewer_TF1f", "summary": "This paper introduces Jump Your Steps (JYS), a novel approach that optimizes the allocation of discrete sampling timesteps. It achieves this by minimizing Compounding Decoding Error (CDE) without incurring any additional computational cost. The authors derive an upper bound on CDE and employ techniques to simplify the computation. Based on the upper bound, they propose an algorithm for searching for the optimal sampling schedule, thereby enhancing the sampling quality.", "questions": "N/A", "limitations": "", "rating": 5, "confidence": 4, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "The algorithm presented in this submission is straightforward and simple. Experimental results have been provided to demonstrate the feasibility of the proposed algorithm.", "weaknesses": "1. The novelty of the proposed algorithm is rather limited. The authors merely transfer Align Your Steps (AYS), which is originally for image generation, to the framework of SEDD for text generation.\n\n2. The experiments conducted on the CIFAR-10 and Countdown datasets lack practical significance. In the realm of image generation, efficient sampling methods have been well explored. For CIFAR-10, even with 256 NFEs, the proposed approach can only achieve an FID higher than 10. In contrast, some popular sampling methods for image generation, such as DPM-Solver++ (https://arxiv.org/pdf/2211.01095) and DMD (https://arxiv.org/pdf/2311.18828), can attain an FID less than 4 using only 10 or even just 1 sampling step. Additionally, the Countdown dataset is a synthetic one. I suggest that the authors place the results for CIFAR-10 and Countdown in the appendix. Moreover, as I am not familiar with music generation, it appears to me that although JYS can lead to a significant drop in Hellinger distance, the Hellinger distance for uniform sampling timesteps is already small (less than 0.4).\n\n3. It seems to me that the practically meaningful experimental results are mainly showcased in Figure 8 for text generation. Nevertheless, upon examining Figure 8, I cannot observe a significant improvement over the use of uniform sampling timesteps.\n\n4. Some problems in the writing:\n- The right arrows used on Line 52 seem strange. Additionally, such right arrows occur multiple times in the main content. It is suggested to use normal notations instead (and I don't think there is a need to write down the whole sequence for timesteps repeatedly).\n- The term \"KLUB\" is first seen in Figure 2 on page 4; however, its explanation is only provided in Theorem 3.1 on page 5.\n- There is no necessity to write down the Sampler in Figures 6 and 7.\n- In the section on \"$k$-Gillespie's Algorithm\" (Line 125), '$k$' apparently means updating $k$ tokens in parallel. However, in Appendix B.1 KLUB COMPUTATION, the use of '$p(t|k)$' is presented and it is explained that this is determined by the pretrained noise schedule. As a result, I am not certain whether '$t$' signifies time. If it does, then it appears inconsistent with '$k$'. Please provide a more detailed explanation about $k$-Gillespie's Algorithm.\n- The condition $\\mathbb{P}_{t_0} = \\mathbb{Q}_{t_0}$ in the last sentence of the proof of Theorem 3.1 should be presented as an assumption in the statement of Theorem 3.1.\n\n\n--------\n\nAfter rebuttals:\n\nI would like to thank the authors for their detailed responses. However, the authors have only provided Figure 13 (which has been shifted to illustrate the performance gains of JYS compared to those achieved by increasing model size) to address my major concern in W3. Currently, although I have slightly raised my score to 5, my concern about the practical significance and relevance of the proposed approach still persists. As a result, I am still inclined towards rejection.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "CU3URMyPk6", "reviewer": "Reviewer_ibjS", "summary": "This paper introduces Jump Your Steps (JYS), a method for discrete diffusion models (DDMs) that enhances generation quality by finding optimal sampling schedules when using efficient parallel sampling methods. Parallel sampling methods such as τ-leaping can speed up DDM inference, but they introduce a Compounding Decoding Error (CDE) that demotes sample quality. The authors address this by deriving a practical upper bound on CDE and developing an efficient schedule optimization algorithm that minimizes this bound without additional computational overhead. They perform experiments on image, music, and text generation tasks to show that the JYS approach improves sampling quality across different transition kernels using fast sampling methods like τ-leaping or k-Gillespie.", "questions": "1. As the empirical validation of the KLUB is a proxy for CDE, would it be possible to directly show that minimizing KLUB actually reduces this error?\n2. Does the hierarchical breakdown strategy guarantee convergence to a globally optimal schedule?\n3. The paper says “After K iterations, this hierarchical strategy yields a sampling schedule with 2^K NFEs, optimizing the schedule as the number of steps increases.” in lines 289-29. So, there is an exponential factor appearing in the number of function estimations. I wonder if it affects the overall complexity and method’s applicability, especially in resource-constrained settings.\n4. I also wonder if the computational gain from this approach leads to higher memory costs. Is it this case from your observations?\n5. Is there any intuition on how the method's error bounds scale with data size, or it doesn’t matter?\n6. Is there any insight into the applicability of the proposed method to DDMs without fast sampling algorithms?\n7. Do you think the hierarchical breakdown strategy converges to globally optimal schedules?\n\nSmall suggestions regarding the manuscript:\n- There is no need to define DDMs (lines 12, 30, 94, for example) or CDE (line 156) a few times through the text if they were defined before.\n- In Eq. 1 and this section, I’d suggest explicitly defining $x$ (data) and $y$ (corrupted data) variables.\n- Line 133: Should it be “.” instead of “:”? \n- Maybe notations in line 148 can be combined with Section 2.1 or moved there? I’d suggest the authors go through their manuscript to make sure all notations are introduced and consistent.\nNFE is not defined in line 290 or earlier. Also, it is useful to explain what it means (it is the number of calls to the score NN, right?).\n- Maybe it’s worth moving Section 5 to the Intro section or a separate section at the beginning of the manuscript? Also, mentioning papers [1, 2] might be helpful.\n- Adding equation numbers to Algorithm 1(line 7) would be helpful.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "The main idea of this paper is novel: the authors suggest reframing DDM sampling schedule optimization as a CDE minimization problem, introducing a Kullback-Leibler divergence upper bound (KLUB) metric to make the optimization tractable for improving sample quality in fast DDM sampling methods. The theoretical development seems sound, establishing connections between CDE minimization and path-space probability measures. This work is particularly interesting because it requires no architectural modifications or additional inference costs, unlike existing methods. As for the empirical validation, the paper includes an evaluation across diverse domains showing consistent improvements in the sample quality when using the same number of function evaluations (NFEs) as a baseline approach.", "weaknesses": "1. The empirical analysis can be improved: \n - While improvements in the generation quality in terms of FID or perplexity scores are shown, comparisons against other quality-improvement methods (e.g., predictor-corrector approaches mentioned in Section 1), and an explicit study of their computational costs are missing. The paper should either include such comparisons or justify why they aren't necessary.\n - The trade-off between schedule optimization time (or its memory requirements/end-to-end generation time) and sample quality gains isn't studied, making it difficult to assess the method's practical utility.\n- No error bars or standard deviations are provided for the quantitative metrics. This is important since generative models can have high variance in their outputs and metrics. An elaboration of the significance of the reported results would be appreciated. \n-- The comparison is limited to a uniform scheduling baseline. Would it be possible to compare against an adaptive step size integrator method (Runge–Kutta method modifications if they are applicable to the discrete case) or other works like a recent one [5]? It’d be great to include this or explain why such comparisons aren't applicable or necessary.\n2. The paper doesn't clarify how the diffusion model formulation (Eq. 1) relates to other DDM variants from [2, 3, 4]. Such discussion would be appreciated.\n3. The single-state transition assumption, while mathematically convenient, limits the method's applicability: it can lead to suboptimal schedules for fast-changing processes. It’d be great to see ideas on possible extensions to handle multiple transitions while maintaining computational tractability.\n4. Some technical details are difficult to follow or verify. For example, the authors introduce two techniques for KLUB computation in Section 3.5 but don't explain when each is preferable. It looks like both techniques are combined in Algorithm 1. No discussion of whether the hierarchical breakdown strategy converges to globally optimal schedules. The clarity of the paper could also be improved. There are suggestions on this in the Questions section.\n5. No code is provided for reproducibility. \n\n\n[1] Hoogeboom, Emiel, et al. \"Argmax flows and multinomial diffusion: Learning categorical distributions.\" Advances in Neural Information Processing Systems 34 (2021): 12454-12465.\n\n[2] Santos, Javier E., et al. \"Blackout diffusion: generative diffusion models in discrete-state spaces.\" International Conference on Machine Learning. PMLR, 2023.\n\n[3] Austin, Jacob, et al. \"Structured denoising diffusion models in discrete state-spaces.\" Advances in Neural Information Processing Systems 34 (2021): 17981-17993.\n\n[4] Hoogeboom, Emiel, et al. \"Autoregressive diffusion models.\" arXiv preprint arXiv:2110.02037 (2021).\n\n[5] Chen, Yuzhu, et al. \"Adaptive Time-Stepping Schedules for Diffusion Models.\" The 40th Conference on Uncertainty in Artificial Intelligence.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "Wj9d4oF0Xx", "reviewer": "Reviewer_VTwh", "summary": "The paper describes a way to optimize sampling for discrete diffusion models. The idea is to select a good subset of optimal sample times based on an optimization criterion. Some theory and some experiments are given.", "questions": "1) line 189 saying \"motivated by this observation\" is not correct/precise I think, given that you list a bunch of factors at work and you just focus on one? the only motivating point is the dependence on sampling methods, and not the others.\n\n2) line 202 \"if we ignore the accumulated error from the previous steps\": why should we ignore it? can you formulate this as an assumption somewhere?\n\nI think that the paper's theory part might have very non-sharp estimates in case this error can't be ignored, can you convince me otherwise?\n\n3) can you comment on when is the inequality in (7) sharp? I think this has to do with question 2.\n\n4) line 216-217 \"this theorem suggests\" -- I think that it'd be accurate to say \"based on the case that inequality (7) is sharp, we are tempted to hypothesize\" and to mention that in case accumulated error from previous steps is negligible, then this heuristic becomes stronger.\n\nNote that in applications in which the gap in (7) is large, then theorem 3.1 gives a lax and uninformative upper bound and this heuristic has no reason for holding.\n\n5) about Theorem 3.2, when is the inequality in (8) sharp? Upper bounds like KLUB are useful to the extent to which they are close to sharp. So this limits the range of applicability of (8), and therefore it would be good to have a description of cases in which this is sharp.\n\n6) about the hierarchical time breakdown (described in paragraph 3.4 and summarized in Figure 3) : this is one possible time breakdown strategy. Can you comment on alternative strategies, or on how this one is better than, or equivalent to, other strategies? \n\n7) line 298-299 what do you mean by \"computational complexities\"? This is vague and easy to misinterpret for a reader. I think you mean the thing mentioned in lines 350-360? If so, I suggest moving those lines up here, so that the reader has a concrete thing in mind since the beginning.\n\n8) about the formula/equation at lines 308-309: what does the \"approximately equal\" sign actually mean? and why or under what hypotheses is this approximation valid? You mention something in the preceding paragraph, but this is not giving a clear cut answer to what approximation you have in mind, and on what are the underlying assumptions behind it.\n\n9) about figure 9, I am puzzled/perplexed by the cases (a) and (c): \nIn (a), why do you think that the JYS schedule has so dense subdivision in the first interval? I don't see anything in the \"ground truth steps\" graph that would indicate that this is optimal. \nIn (c), why is the JYS deciding to just not include any timesteps in the first interval? In there, I think that the Ground Truth Steps part has a very dense time dependence, at least that's what I see in the figure.. so how do you justify this discrepancy?\n\nTo summarize, both points (a) and (c) show that JYS has high discrepancy in its \"optimized\" timestep choice, compared to \"ground truth samples\", so it would be good to understand what this means, how do we interpret this.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The direction of this research is new and interesting.", "weaknesses": "Some of the theory parts confounds heuristic and rigorous justification (by ignoring some long-time dependencies without actually emphasizing that this is a working simplification). Thus, some assumptions and/or limitations are not highlighted, which is making the paper look weaker. ----[update] this was addressed in the discussion, with reference to appendices\n\nAlso, I am not completely convinced with the interpretation of some of the experiments, but this may be just me. --- [update] the authors clarified and promised to amend some figure", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (Poster)