Training-Free Guidance Beyond Differentiability: Scalable Path Steering with Tree Search in Diffusion and Flow Models
Authors: Yingqing Guo
Yukang Yang
Hui Yuan
Mengdi Wang
Venue: NeurIPS 2025 poster ()
Keywords: training-free guidance
inference-time scaling
diffusion models
flow models
tree search
Primary area: deep_learning

Abstract: Training-free guidance enables controlled generation in diffusion and flow models, but most methods rely on gradients and assume differentiable objectives. This work focuses on training-free guidance addressing challenges from non-differentiable objectives and discrete data distributions. We propose TreeG: Tree Search-Based Path Steering Guidance, applicable to both continuous and discrete settings in diffusion and flow models. TreeG offers a unified framework for training-free guidance by proposing, evaluating, and selecting candidates at each step, enhanced with tree search over active paths and parallel exploration.  We comprehensively investigate the design space of TreeG over the candidate proposal module and the evaluation function, instantiating TreeG into three novel algorithms. Our experiments show that TreeG consistently outperforms top guidance baselines in symbolic music generation, small molecule design, and enhancer DNA design with improvements of 29.01%, 26.38%, and 18.43%. Additionally, we identify an inference-time scaling law showing TreeG's scalability in inference-time computation.

Training-Free Guidance Beyond Differentiability: Scalable Path Steering with Tree Search in Diffusion and Flow Models
Yingqing Guo
Yukang Yang
Hui Yuan
Mengdi Wang
Princeton University
Abstract
Training-fii free guidance enables controlled generation in diffusion and flow models, but most methods rely on gradients and assume differentiable objectives. This work focuses trainingffree guidance addressing challenges from non-differentiable objectives and discrete data distributions. We propose TreeG: Tree Search-Baad Based Path Steering Guidance, applicable to both continuous and discrete settings in diffu- sion and flow models. TreeG offers unified framework for training-free guidance by proposing, evaluating, and selecting candidates each step, enhanced with search over active paths and parallel exploration. We comprehensively investigate the design space of TreeG over the candidate proposal module and the evaluation function, instantiating TreeG into three novel algorithms. Our experiments show that TreeG consistently outperforms top guidance baselines in symbolic music gen- eration, small molecule design, and enhancer DNA design with improvements of 29. 19.01% %, 26.38%, and 18.43%. Additionally, we identify an inference time scaling law showing TreeG's scalability in inference-ting -imee computation."
Introduction
During the inference process of diffusion and flow models, guidance methods steer generations toward desired objectives, achieving remarkable success in vision [15, 25], audio [35], biology [45, 80], and decision making [1, 12]. In particular, training-free guidance offers high upplicability by directly controlling the generation process with off offfthh-shhef objective functions without extra training [53, 81, 4, 24). Most training-fre guidance methods are gradient-based, leveraging the objective's 's gradient to steer inference, and thus assume the objective function is differentiable [78, 22].
However, recent advances have pushed the boundaries of guided generation beyond differentiabillty: guidance objectives have expanded to include non-differentiable goals [30, 1]: diffusion and flow models have shown strong performance on discrete data [2. 67], where objectives are inherently non-differentiable unless approximated via differentiable features [36, 77J. In such settings, training- free methods designed for differentiable objectives face fundamental limitations. Yet, the design space beyond differentiability remains under-explored: only a few methods exist [38, 30), they differ significantly and appear disconnected from prior guidance principles [38, 13]. This underscores the need for a unified perspective and comprehensive study of guidance beyond differentiability. To this end, we propose algorithmic framework TreeG: Tree Search-Basee Path Steering Guidance, designed for both diffusion and flow models across continuous and discrete data spaces.
TreeG is based on path steering guidance, providing a unified perspective on training-free guid- ance beyond difffeenniiabliity. Let To. Ft, Tt+Ar, Ti denote the inference trajectory of
"Equal contribution. Department of Electrical and Computer Engineering, Princeton University. Authors' emails are: fyg6736, yy1325, huiyuan, 22nni//ee
"Code available
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

0
Branch Out
(,
1=1
Actrv sample
Y= fyde
Y= M
condicano
Best Somple
Varue function
(a) Tree-Search Inference Process
(b) Designs BranchOut Value Function V. gradient-based guidance
Figure 1: TreeG Overview: (a) An active set of size A is maintained, where each sample branches into K candidates. At each step. the top A candidates at the final step. (b) Left: The current state-based (BranchOut. V) evaluates candidates via a lookahead estimate of the clean sample (Sec. 5.1). Middle: branching and selection occur in the destination state space (Sec. 5.2). Right: Gradient-based guidance can be applied to the current state branch-out module when differentiable objective predictor is available (Sec. 5.3).
retained, and the best sample is selected
diffusion or flow model. While gradients of the objective, when available, can offer a precise direction to steer inference each step, alternative is to search for favorable path: propose multiple next state candidates Ft+At (via BranchOut module), evaluate them using value function (denoted by V) that reflects the objective, and select the best candidate proceed. This structured search enables TreeG using only zeroth-ordes order information, making applicable beyond differentiability.
TreeG adopts tree-search mechanism explore multiple trajectories, further enhancing the effectiveness of path steering guidance. An active set of size A is maintained at each inference step (Fig. (a)). Each sample in the active set branches into multiple candidate next states, from which the top A candidates, ranked by the value function V, are selected for the next step. This process iterates until the final step, where the best sample from the active set is chosen as the output. By enlarging A, TreeG achieves higher objective values while flexibly adapting to the computational budget.
TreeG's design space is over the branching-out module and value function, offering flexible and comprehensive configurations. Effective search requires both efficient exploration and reliable evaluation. As shown in Fig. (bb), we propose two compatible pairs of (BranchOut, V): one based on the current state (xx),, the other on the predicted destination (#1). The former uses the original diffusion model to generate multiple next states and evaluates them via lookahead estimate of the clean sample. The latter generates candidate destinations, which indicate the orientation of the next state, and selects the optimal using an off-the-sheel objective function. The top-ranked destination determines the next state. In addition, TreeG introduces novel gradient- algorithm for guiding discrete flow models using gradients when differentiable objective predictor is available.
Contributions. Our methodological contributions are as follows:
We propose novel tree search framework TreeG of training-free free guidance. applies to both con- tinuous and discrete, diffusion and flow models (Sec. 4), and supports non-difierentiable objectives. We instantiate three novel algorithms within this framework, and provide theoretical guarantees showing that they recover the posterior conditional distribution (Sec.
We show that existing sampling-bel limited to exploration at the current state. Our novel exploration strategy at destination states, combined with comprehensive design space for candidate proposals and value functions, enhances the effectiveness and versatility.
methods [30. 37] are special cases of TreeG (Sec. 5.1),
Empirically, we demonstrate that TreeG:
Outperforms existing guidance methods on diverse tasks: symbolic music generation (continuous diffusion with non-differentiable objectives), molecular design, and enhancer DNA design (both discrete flow models). Path steering guidance, the special case of TreeG with the active set size as consistently outperforms the strongest guidance baseline, yielding improvements of 29. 00,01, 26.38%, and 83.3% respectively (Sec. 6.2).

---

0.82
--- Branch Size Active 5
0.80
1.0
Optima
0.78
Optimal
Class Probabilley
Density
Mean OED
0.74
0.70
0.65
20
0.60
Branch
Activo
50
100
150
200
10 11 12
50
100
150
200
250
300
Computation Time (s)
Computation Time (s)
Computation Time (s)
(a) Symbolic Music (Loss 4)
(b) Small Molecule (QED 1)
(c) Enhancer DNA (Prob f)
Figure 2: Inference-Time Scaling Law of TreeG. "Optimal" refers to the best-performing combina- tion of active set and branch-out sizes under the same inference time. The results demonstrate the scalability of TreeG, validating the effectiveness of its multi-active-pall and branch-out design."
Exhibits an inference-time scaling law, where performance consistently improves as inference-time computation increases by larger active set and branch-out sizes (Fig. and Sec. 6.3).
2 Related Work
We review the most relevant work inference-time guidance here; see App. A for additional work.
Derivative-Free. Huang et al. [30] and Li et al. [37] guide sampling toward non-differentiable objectives using soft values derived from optimal control. These are special cases of our TreeG-SC with active set size of one. Notably, proposes candidates at the end of the sampling trajectory in the clean space, unexplored by existing derivative-free methods. This novel perspective, along with our flexible design for candidate proposals and value functions, underscores the broader versatility and applicability of our framework.
TreeG-SD (Sec.5.2) introduces novel strategy that
On Discrete Models. Nisonoff et al. [45] extends classifier(-free guidance [15, 25] to discrete settings, requiring training imme-dependent classifiers. Lin et al. [38] reweights the rate matrix using objective values. All three of our algorithms apply to discrete models, including a gradient guidance method we propose for cases with differentiable objective predictor.
Inference-Timee Time Scaling, The idea of searching across multiple inference paths has also been touched upon by two concurrent works [42, 65]. Our TreeG provides the first systematic study of the design space of tree search, offering a novel methodology for both exploration and evaluation.
3 Preliminaries
Notations. Bold symbols denote high-dimensional vectors, while indicates scalars. Superscripts like (d) refer to the d-th dimension, whereas æ² or æid denote independent samples indexed by i and j. Pt is the density intermediate training distributions. For inference, Tj represents the sample. 3.1 Diffusion and Flow Models
Diffusion and flow models learn to reverse transformation from data distribution Pdata noise distribution Pa- Let P1 = Paaaa and define intermediate distributions P: for t E (0, 1) that progressively corrupt P1 into Po over T uniform timesteps (At 1/T). Generation starts by sampling 2g ~ Po, then iteratively samples I, ~ Pt for = i/T, where E [T]. ultimately yielding 21 ~ P1-
Diffusion and flow models are equivalent [39, 16]. We focus on the widely used continuous diffusion models and discrete flow models, denoted ug and un flow and refer to both as us or diffusion models when clear from context. We next review the models in more detail.
Pi, Diffusion Models. For diffusion models applied to continuous data, given data sample the noisy sample timestep -= i/T (i E (T)) constructed as æ, = va,zz + vi aze, where N (0, I) and } are pre-defined monotonically increasing parameters that control the noise level. The diffusion model vi .tiff X' [0, 1] + X parameterized by 0, estimates the noise added to Cr, it's equivalent to learning the score function of px(x)) [26, 54]:
diff U
argmin -p,. ~pp..~
(æ,, t) - e|l2= - VI āi V log
(1)
dg
'leesse refer to App. E4 for the experimental setup of Fig. 2.

---

For sampling, we begin with To ~ ~ (0, and iteratively apply the DDPM sampling step [26]:
I1+A1=
1 Vaz
(x: (1 ar) V (z:)) + o,E=
ax dill u
(zI,
oee, (2)
Var
vI at
where e N (0, I) at = / and o; = v1 -1-att at. This step (2) can be restated as sampling from a distribution centered on linear interpolation of I and Zije
U++ = ct + 11,2 + oee,
where Cr and 4r are constants" , and with i1 being an estimation of the conditional expectation [ æy] based on Tweedie's 's formula [18]:
11
x2 VI- VI-aat ar
did (æt, f))
Flow Models. For flow models applied to discrete data [10], suppose data space is X' - [S]P, where D is the dimension and S is the number of states per dimension. An additional mask state M is introduced as the noise prior distribution. Given data sample æ1, the intermediate distributions are constructed by Paj (a, (z, (21) ) 11 P (z)) with Paja (1)) tô {æ1, 24} + t) (M, xz).
The flow model u/ Now estimates the true denoising distribution Pije (z)) |æ,). Specifically, it's defined
as flo (ug ,...,,u, Ug ), where each component ug (æ1)) I-) is function X' x [0, 00 A([S)). Here, A(S)) represents the probability distribution over the set [S] The training objective is:
argmax Emiopi log ug (a [x))
(2) (d)
up
(5)
uo
For generation, it requires the rate matrix:
R! (xx, j) = E a/ mp/?)
Re
a (d) =(r(1) 2(t
(()) (w:) Rs (2)²) =laa(")]]
(6)
where the pre-defined conditional rate matrix can chosen as the popular: Re &ii.n 8 {a,, M). The generation process can be simulated via Euler steps [58]:
=
s A+t ~ Cat (o(x) . + (d (xi, At) At),
where 5 {k is the Kronecker delta which is 1 when & and is otherwise 0.
3.2 Objective
The objective to sample from the conditional distribution p(> y). where y denotes a desired property, using pre-trained diffusion model that generates samples from unconditional distribution p(xr). The extent to which a sample satisfies the property y is quantified by an objective function fg X + IR, where [z(x) p(y x:) and æ in the clean data space. We aim to sample from:
p(æ y) x p(x) p(y
x) x p(æ) exp(Sr(x)),
Given the training objectives defined in (1) and (5) for conditional counterparts 21 pi(x v), the objective translates to estimating the conditional score or rate matrix:
Vx, log Pt (z), v); R!!a) (xt, j y) = _B ~ppttt (w)))
Ri (z) -iz((()
(8)
which enables the sampling step (2) or (7) to use the conditional counterparts and generate the next state Le+Ae following the conditional transition distribution Te(:++A: Zt, y).
We assume a perfect pre-trained diffusion model, where uo exactly minimizes the training objectives in (1) or (5). Our focus is on training-free methods that neither fine-tune uo train time-dependent classifier aligned with the diffusion noise schedule.
4 TreeG: Tree Search-Based Path Steering Guidance
While gradients provide precise direction when available [22], search offers an alternative when they are not: proposing multiple candidates, evaluating them via a value function aligned with the objective, and selecting the best proceed. We demonstrate the tree search framework in this section.
We have c.1 var(1 drtat)/(L (1 (te) 0r2 Vortsill ax)/(1 as).

---

4.1 Algorithmic Framework
Let 20. D1 denote the inference path from pure noise to a clean sample. At each step (Alg. 1), the BranchOut module proposes K candidate states, among which some candidates selected into the active set. While the basic approach tracks a single path, the active set size A can be increased to explore multiple paths via tree search. The selection step be implemented ranking candidates by their values and selecting the top, or resampling candidates with probabilities proportional to their values. In following sections, we will show that TreeG with resampling enjoys theoretical guarantees. while empirically, experiments (please refer to App. H.3) demonstrate that selection by ranking is superior to resampling.
Algorithm TreeG: Tree Search-Basee Path Steering Guidance
1: Input: diffusion model ug, branch out policy and value function (BranchOut, V), objective function fy. active set size A, branch out sample size K.
2: Initialize:
0, A = { ....................... 3 zd po-
3: while & < 1 do
4: Propose candidates for next step: For æf E A, Ti-Ai BranchOut (z),, uo). [K].
5: Select: select A candidates (by ranking or resampling with respect to the value function
V (Fiteert, fu).+ [A].]
i1:h [K]: 2tte
fadis
(+
6: Update the active set: A L-
fi AajA
7: t- t At.
8: end while
9: Output: xj argmaxxieeAe fy (x1).
In Alg. I, the BranchOut module and value function V are two core components that require careful design, for which we propose novel designs in the next section. Those specifications of BranchOut and V lead to new algorithms that outperform existing baselines (Sec.6).
5 Design Space of TreeG
This section explores the design space of TreeG, focusing on the (BranchOut, V) pair. We introduce two compatible pairs that operate by sampling and selecting from either the current state or the predicted destination. Additionally, we present a gradient-bast based discrete guidance method.
5.1 Saeeee-then-SSeeet on Current States
The target conditional score and rate matrix in (8) relate their unconditional counterparts follows: V m, log pr(x,,
y) Va, log (xxx) + Va, log Pogp((y wx), (by Bayes' rule)
R2 (2., x v) Pr(y x²) Re(x,,
(by [45])
(ı(y ax)
Both expressions depend on pt (y æt), which is key to adapting the unconditional score or rate matrix, estimated by pre-trained diffusion model, to their conditional counterparts.
The idea is to use the original backward process to generate multiple candidate states at time f, then prioritize samples with higher Pe xx) using it as a value function. We approximate pe(21 xx) as:
N
Py œt) = Eui x1) = Ezropin exp (fr (z1))
N exp (fv(#1)).
~
Based on this, we propose the (BranchOut, V) pair operating on current states as follows:
We refer instantiating Alg. with Module and Value Function as TreeG-Sampling Current, abbreviated as Tre.G-SC. We demonstrate that stochastic control guidance (SCG) [30] and soft value decoding guidance (SVDD) [37] are special cases of TC (App. 1.
The following theorem (proof in App. D. shows that TreeG-SC yields distribution 7 that closely approximates the target conditional transition distribution T( Øt. y).
*Given of candidates {I1, #2. vn with associated nonnegative values V1, V2, V2...., Vn, ranking involves selecting the top candidates with the highest Vú values; Resampling defines P(x.) = Vi/ EE= V2). and then samples A candidates according P(x:).
5

---

Module BraanchOut-Curee
Value Function Current State Evaluator
1: Input: æt, diffusion model No, time step f.
1: Input: 2;, diffusion model no, objective function Jy.
time step t, (optional) Monte-Carlo sample size N.
2: Sample the next state by the original generation process:
2: Predict the clean sample:
(continuous) Φ 31 .in (4).
Fe+Ar ~ (2) or (7). Output: Dt+At
(discrete) Φ Cat (ug (2:: f)) i [N].
3:
3: Evaluate: V(x;) NN Ei exp (fz(t))
4: Output: V(x;)
Theorem 1. Consider TreeG-Sampling Current time with active set of size and selection performed via resampling. Then, for any E, 5 > 0, holds with probability 1- ô:
| - T(- æe, v)lle
provided one of the following conditions is satisfied: (a, Continuous) It holds under 1 norm. Suppose data follow Gaussian distribution and the
objective function is linear. Branch- Out size K = O ( and timestep satisfies a4 = 1--0 (E?).
(b, Discrete) holds under = oo norm. The Branch-Out size K
) Monte Carlo e²
size is N 0 (0(=0(221/)) and the timestep At (e)) where X is the data space.
5.2 Sample-then-Seless on Destination States
During inference, the transition probability each step is determined by the current state and the end state of the path, with the latter estimated by the diffusion model, stated in the following lemma (proof in App. D.2).
Lemma 1. In both continuous and discrete cases, the transition probability during inference at timestep satisfies:
T(I++ = (T'( Iz, i]
where the expectation taken over a distribution estimated by ug with T being the true posterior distribution predetermined by the noise schedule.
In diffusion and flow models, T is centered at linear interpolation between its inputs: the current state 2t, and the predicted destination state é,, indicating that the orientation of the next state partially determined by 1, as serves as one endpoint of the interpolation. If the & has high objective value, then its corresponding next state will be more oriented to high objective. Accordingly, we introduce the (BranchOut, V) pair operate on destination states as follows.
Module 2 Saaanchhuu-Destinatti
Value Function 2 V Destination State Evaluator
1: Input: æ,, diffusion model ug. time step t, (optional) tuning parameter Pt. Tr-
Input: (#++ objective function fy- Evaluate on the clean sample:
2: Sample destination state candidates: (continuous) e ~ ~N(xi PtT), Tij in (4).
2:
(discrete) Φ Cat (z),
3: Compute the next state: (continuous) T++At ~ ~ (c,1 C,2 T.I). (discrete) (d)
V (1I44Ar, &t))
exp (fy (.1)).
1++ Cat (6(x) .5} + Re 24 .j 1 2((0)
At).
3: Output:
V ((I+4M), +1))
4: Output: (1)+
We name Alg. I with Module and Value Function 2 by TreeG-Sampling Destination (TreeG-SD), TreeG-SD outputs T that closely approximates the conditional transition distribution, as shown below (proof App. D.3).
Theorem Consider TreeG-Sanne Sampling Destination time with an active set of size one and
selection performed via resampling. Then, for any e, 5 > 0, it holds with probability 6:
i T(: æt, ve,,
provided one of the following conditions is satisfied: (a, Continuous) It holds under the i norm. Suppose data data follow Gaussian distribution and the

---

objective function is linear. The Branch- -ut size is K = O (
(b, Discrete) It holds under the { = s0 norm. The Branch- Out size is K = A D ( where X the data space and D is dimension.
5.3 Gradient-Based Guidance with Differentiable Objective Predictor
Previously in this section, we derived two algorithms that do not rely on the gradient of the objective. Though we do not assume the true objective is differentiable, leveraging its gradient as guidance still a feasible option when a differentiable objective predictor is available. Therefore, in what follows, we propose novel gradient-bar maddent--basd training-free guidance for discrete flow models, which also fits into the TreeG framework as a special case with K = 1.
For discrete flow models, we aim for the conditional rate matrix [45]:
Re(xx,, (v) P+ly a (i)) Re(2,,)),
po(y x1)
where o; matches 2; except at dimension d, and x²" (i) has its d-dimension set j. While [45] requires training a time-dependent predictor to estimate (3 σ), we propose to estimate it using (9) in training-free way. However, computing this estimation over all possible x is is computationally expensive. As suggested by [45, 67], we can approximate the ratio using Taylor expansion:
(u x
log
= log xx -log xx))
Pr ( xx)
(10)
= (ar /d xz) Va, log wt))
We use the Straight-Through Gumbel-Softtax trick [31] to enable gradient backpropagation through the sampling process (details are in App. E.4). We also show that this approximation achieves high accuracy compared computing (9) for all æ; while offering greater efficiency (see App. H.2).
backward sampling step, utilizing the estimated conditional rate matrix, BranchOut operation, termed BranchOut-Graann Gradient reduces gradient-based guidance methods. For K 1, it aligns with Value Function 1. We denote this algorithm as TreeG Gradient (TreeG-G).
be viewed
(detailed in App. E.2). With K = 1, Braacchuutt
6
Experiments
This section evaluates TreeG on continuous and two discrete models across diverse tasks. Sec. 6.1 introduces the comparison methods; Sec. 6.2 details the tasks and results; Sec. 6.3 validates framework scalability; and Sec. 6.4 discusses configuration choices for different scenarios.
6.1 Settings
Below are the methods we would like to compare:
For continuous models: DPS [13]. a training-fiee free classifier gradient guidance requiring surrogate neural network predictors for non-differentiable objective functions; TDS [73], sequential Monte Carlo method based on gradient guidance; SCG [30]; SVDD [37]; and TreeG-SD (Sec. 5.2).
For discrete models: DG [45], a training-bass based classifier guidance with a predictor trained on noisy inputs, implemented with Taylor expansion and gradients; TFG-Flow [38], a training- ffren method estimating the conditional rate matrix; SVDD [37]; TreeG-G (Sec. 5.3), which trains a predictor on clean data for non-differentiable objectives; TreeG-SC (Sec. 5.1); and TreeG-SD (Sec. 5.2).
6.2 Guided Generation
To enable clear comparison with the guidance basclines, report the active size of TreeG for both = and A > 1, while controlling inference time to be comparable across methods and settings.
6.2.1
Symbolic Music Generation
We follow the setup of [30], using continuous diffusion model pre-trained several piano midi datasets, detailed App. F.I. The branch-out size for TreeG-SD is K = 16; SCG and SVDD use a sample size of 16, the temperature of SVDD is 0.01, and TDS uses 4 particles.
Guidance Target. Our study focuses on three types of targets: pitch histogram, note density, and chord progression. The objective function f.).) = -f (y, Rule(-)), where & the loss function. Notably, the rule function Bule(-) is non-differentiable for note density and chord progression.
7

---

Evaluation Metries. For each task, we evaluate performance on 200 targets as formulated by [30]. Two metrics are used: (1) Loss, which measures how well the generated samples adhere the target rules. (2) Average Overlapping Area (OA), which assesses music quality by comparing the similarity between the distributions of the generated and ground-truth music [74].
Table 1: Evaluation on Music Generation. TreeG-SD reduces loss by average 29.01%. Results of no guidance, Classifier, and DPS are copied from [30]. Best results are bold, second-best underlined.
Pitch Histogram
Note Deasity
Chord Progression
Mothod
Loss!
0A 1
Loss
OA
Loss
OA 1
No Guidance
0,0180 = 0.0100
0.812 = 0.012
2.456 +: 3.330
0.830 + 0.016
0.831 = 0.142
0.854 =: 0.002
Classiferr
0.0050 + 0.0040
0.855
0.020
0.698 + 0.587
0.861 + 0.025
0.723 + 0.200
0.850 + 00.033
DPS
0,0020 1 0.0020
0.849
0.018
1.261 1: 2.340
0.667 1 0.113
0.414 1: 0.256
0.839 1: 0.039
TDS
0,0027 0.0055
0.815
0.017
0,218 + 0:211
0.875 4: 0.023
0.714 0.187
0.857 - 0.028
SCG
0.0036 = 0.0057
0.862
0.008
0.134 + 0.533
0.8-2 = 0.022
0.347 = 0.212
0.850 + 0.046
SVDD
0,00885 0.0100
0.816
0.013
0,4455 +: 0.437
0.835 + 0.028
0.528
0.189
0.865 = 0.014
TreeG-SD (A-1,K-16)
0.0002 0.0003
0.860
0.018
0,142 +: 0.423
0.832 + 0.023
0.301
0.191
0.856 :: 0.032
TreeG-SD (A=4,K=4)
0.0002 0.0003
0.818
0.013
0.048 0.198
0.843 1: 0.012
0.226
0.144
0.862 1: 0.015
As shown in Table 1, our TreeG-SD outperforms baselines while preserving comparable sample quality. For differentiable rules (pitch histogram), TreeG-SD outperforms DPS, which gradient-free methods like SCG and SVDD cannot achieve. For non-differentiable rules (note density and chord progression), TreeG-SD matches or exceeds SCG and significantly outperforms others. 6.2.2 Small Molecule Generation
Results.
We validate our methods on the generation of small molecules with discrete flow models. Following [45], small molecules are represented simplified molecular-input line-entry system (SMILES) strings. These discrete sequences are padded to 100 tokens and there are 32 possible token types, including one pad and one mask token M. We adopt the same unconditional flow model and Euler sampling curriculum as [45].
Guidance Target. Following the benchmarks in [20, 37J, we deploy guidance to maximize four targets: quantitative estimate of likgllis (QED), synthetic accessibility (SA), binding score with dopamine type 2 receptor (DRD2), and binding affinity to protein 5htlb (Docking). We directly use the target measurement as the objective function fax for guidance in Algorithm 1. The values of ((x) while Docking score is
QED, SA and DRD2 are estimated using a pretrained predictor model measured by an oracle tool, QuickVina2-C0 Vina2-GUU-2. and thus an entirely non-differentiable target. In addition, we guide the number of rings N, toward target values N E [0, 6). The objective function
formalized as fy(x) = (-- Please refer to App. F22 for details.
20
Evaluation Metrics. We measure five molecule properties using RDKit, TDC, and Quick Viniikkinn--GUU.. 2.1 [29] for generated valid unique sequences. For N,, we report the mean absolute error (MAE) against each target value. We evaluate molecular diversity through average Tanimoto similarity (TS) across molecules (Table 2). Further, we also report the Negative Log-Liicli (NLL) per token (bits/dim), a widely adopted metric in discrete diffusion and flow-based generation [2. 64] (Table 12).
The likelihood is estimated by the ELBO of the pretrained discrete flow model.
Table 2: Evaluation on Small Molecule Generation. Complete results for different N and NLL per token evaluations are deferred to App. G.2.1. Detailed experimental setup are stated in App. F.2.
Mathod
VAL-
OED
TS 1
VAL
SA
TS
VAL 1
DRD2
TS
VAL
Decking
TS
MAD
TS
No Guidance
0.51 a 0.19
0.12
4 0.02
0.79 1 0.10
0.12 a 0.02
0.06 1 0.17
0.12
4 0.02
8,50
1.0.1.0 1.41
0.12 0.02
2.09 1.16
0.12 4 0.02
0.60
0.12 1
0.50
0.12
0.17 0.52
0.12
0:155
0.14
TEG Flow
0.51 - 0.20
0.12
3 0.02
0.79
0.10
0.12
1 0.02
0.09
1.22
0.12
1 0.002
1.44
0.12::.00
0.25
1
0.02
SYDD
0.57 - 0.18
0.13
0.02
0.50
0.09
0.13
1 0.02
0.43
0.17
1 0.04
9.47
1:97
0.12 0.01
0.55
1.14
0.15
TreeG-SC (A-1)
0,50 0.13
0.13
3 0.02
0.89
1 0.06
0.21
1 0.00
0.77 0.33
0.20
1 0.04
9.64 1.28
0.121:.02
0.01
1 0.07
0.14
TreeG-G (A-1)
0.54 0.19
0.12
1 0.02
0.79
1 0.10
0.12
1 10.02
0.22
1:37
0.13
1.002
0.44.111
0.15
1.00
TreG-SD (A-1)
0.77 0.14
0.12
0.02
0.56
1 0.10
0.16
0.00
0.45 10.01
0.14
0.005
8.72
1.27
0.02
0.11 1.37
0.12 1 0.02
TreeG--SD (Ao1))
0,50 = 0.11
0.32
3 0082
0
= 01007
0.21
- 0.00
1.66 0.20
0.19
- 0.00
9.29
4 1.30
0.12
0.10
0.14 0.12
Results. TreeG consistently outperforms three guidance baselines (Table 2) while maintaining comparable sequence diversity (TS) and sample quality (NLL.). Our best guidance method TreeG-SC achieves a 26.38% average improvement across five targets compared to the best baseline methods
8

---

Feod Feed
10--
Foo6 Food
Error
Teed
Tecd
0.8
Note Dersity
Historrmm
Class Protostill
20-3
Tree TreeG 50
300 12s 350 15 Computation lime (5)
100:23 25. 2015
50
106
130
200
250 500
Computation Time (5)
Computation Time 151
Computation time (si
Music
(b) Music
(c) Molecular (NV
(d) Enhancer (Class 4)
Figure 3: Inference Time Scaling Behavior: As the active size and branch-out size increase, the optimization effect the objective function scales with inference time. This trend is consistently observed across all algorithms and tasks. The inference time is measured with batch size of 1 for music and 100 for molecule and DNA design. For DNA design, 20 for TreeG-G.
(Table 11). And increasing the size of the active set A to more than could further improve the performance of TreeG-SD.
6.2.3 Enhancer DNA Design
We follow the experimental setup of [56], using discrete flow model pre-trained on DNA sequences
of length 500, each labeled with one of 81 cell types [32, 61]. For inference, we apply 100 Euler sampling steps. The branch-out size for TreeG-G is set K 1. Setup details are in App. F.3.
Guidance Target. The goal is to generate enhancer DNA sequences that belong to a specific target cell type. The guidance target predictor is provided by oracle classifier from [56]. The objective function of given cell class is fy (-) ()) = log fly -).
Table 3: Evaluation of guidance methods for Enhancer DNA Design varying guidance strength lev- els 2/2 in Module 3. TreeG-G consistently achieves significantly higher target class probabilities.
Methed (strghh 1)
Prub
Class
NLL J
Div
Prob
Clss
NLL
Div
Prob
Closs
NLL
Div
No Guidance
0.021 a: 0.078
1:311 1 0.008
373
0,008
1 0.082
L311 1: 0.008
373
0.007
1 0.053
1.311 1 0.038
373
20
0.059 0.188
1. 1,225 1: 0.006
351
IL627 0.340
1.191 1: 0.052
350
0,93] 0.264
1.241 1 0.064
357
DG
100
0.372
0.2337
1.159 + 0.074
352
0.571
0.366
1,190 0.073
313
0.173
0.256
1,153 + 0.081
349
200
0.201 + (1.77
1.114 0.068
351
0,350
0.351
1.157 = 0.084
335
0.864 0.145
1,170 = 0.074
343
TTG Flow
200
0.054
0.120
1.308 0.011
375
0,012
0.006
1,300 1 0.018
375
0,034
0.029
1,552
100015
375
SVDD
0.155
0.173
1.307 0.008
0,08S 0.199
1,303 0.040
307
0,051
0.188
1,297 1 0.000
263
01.178
198 0.085
0.348
126
0.119
324
TreeGGG (A=1.Ke))
0.342
0.067
0.164
0.000
0.069
306
200
01258
0.100
0.078
0.186
321
TreG-GG (A42.K=2)
Evaluation Metrics. We generate 1000 DNA sequences conditioned on cell type and evaluate performance using three metrics. Target Class Probability, provided by the oracle classifier, where higher probabilities indicate better guidance. We adopt NI.L per token to evaluate the fidelity of the generated sequences. Diversity is measured by the average pairwise Hamming distance between sequences.
Results. As shown in Tab. 3, our TreeG-G consistently achieves the highest target probabilities as guidance strength increases, with average improvement of 18.43% compared to DG over eight test classes [45], and significantly exceeding other training- free baselines. See App. G for details.
6.3 Scalability on Inference-Tine Time Computation
TreeG scalable to the active size (i.e., the number of generation paths) and the branch-out size K. it compatible with all guidance methods. When increasing the active size and branch-out size, the computational cost of inference rises. We investigate the performance frontier to optimize the objective function concerning inference time. The results reveal inference-time scaling law, as illustrated in Fig. 3. Our findings indicate consistent scalability across all algorithms and tasks, with App. 3 showcasing four examples. Additional results refer App. G.
6.4 TreeG Configuration Analysis
This section analyzes the configuration TreeG, focusing on selecting the instantiated algorithms and balancing A and K under fixed computational budget.

---

We analyze the computational complexity of TreeG, summarized in Tab. 4, The cost units are: mosee for forward pass through the diffusion model, Gred for a predictor call, and Chuckpop for backpropa- gation through both. N denotes the Monte Carlo sample size used in Value Function 1.
Table 4: Computation Complexity of TreeG
Methods
Computation
TreeG-SC TreeG-SD
ACmodal + AK(Cmate + NCpna))
ACmotel + AKC peed
TreeG-G
AK (Cendal NCeed) AChuckmp
Design Axes Comparison. We evaluate TreeG de- signs along two axes. Gradient-free vs. gradient-
based: TreeG-G requires an accurate objective predictor to be effective. If available, predictor latency guides the choice- faster predictors favor TreeG-SC and TreeG-SD, while slower ones make TreeG-G more practical. TreeG-SC (current state) vs. TreeG-SD (destination state): As Tab. shows, TreeG-SD is more efficient, costing only A for the diffusion model forward pass, versus AK for alternatives. Experiments show TreeG-SD outperforms TreeG-SC in continuous diffusion, while Tre is better for discrete flow. Please refer to App. C. for detailed discussion.
Trade-off between Active Set Size A and Branch-out Size K. Tab. 4 shows that the computational complexity of TreeG-SC and TreeG-G using product A K (i.c., fixed inference cost; see Fig. 9 App. G.3.2),
Saanchout-Curren is O(AK). With a fixed
0.8
Compute
Cass Probability
0.6
we explore how to best balance A and K. As shown in Fig.4,
performance peaks when both values are moderate. the special case where = inference paths do not interact, often leading to suboptimal performance.
0.2
0.0
7 Conclusion
27
Active Set Size
We proposed the framework TreeG based inference path search, along with three novel instantiated algorithms: TreeG-SC, TreeG- SD, and TreeG-G, which guide diffusion models toward the pos- terior conditional distribution and address the non-differentiabiliy challenge in training-free guidance. Experimental results demon- strated the improvements of TreeG against existing methods. Fur- thermore, we identified an inference- -imenneeeeeeeeeeeeeee scaling law that highlights TreeG's scalability in inference- time computation.
Figure 4: Trade-off between Active Set Size A and Branch-ou -out Size K with Fixed Compute. The results are for TreeG-SC DNA (Class 4).
Acknowledgments
This work received no external funding. The authors declare no competing interests.
References
[1] Anurag Ajay, Yilun Du Abhi Gupta, Joshua Tenenbaum. Tommi Jaakkola, and Pulkit Agrawal. Is conditional generative modeling all you need for decision decision-making? arXiv preprint arXiv:2211. 15657, 2022.
[2] 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-17999 2021.
[3] Pavel Avdeyev, Chenlai Shi, Yuhao Tan, Kseniia Dudnyk, and Jian Zhou. Dirichlet diffusion score model for biological sequence generation. In International Conference on Machine Learning, pages 2376-1301. PMLR, 2023.
[4] Arpit Bansal, Hong-Min Chu, Avi Schwarzschild, Soumyadip Sengupta, Micah Goldblum, Jonas Geiping, and Tom Goldstein. Universal guidance for diffusion models. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 843-852. 2023.
[5] Ahmad Beirami, Alekh Agarwal, Jonathan Berant, Alexander D' Amour, Jacob Eisenstein, Chirag Nagpal, and Ananda Theertha Suresh. Theoretical guarantees the best-of-n alignment policy. arXiv preprint MXXi:2401.01877 2024.
[6] Heli Ben-Hamu, Omri Puny, Itai Gat, Brian Karrer, Uriel Singer, and Yaron Lipman. D-flow: Differentiating through flows for controlled generation. arXiv preprint 140117740 2024.
10

---

[7] Kevin Black, Michael Janner, Yilun Du, Ilya Kostrikov, and Sergey Levine. Training diffusion models with reinforcement learning. arXiv preprint arXiv:2305.13301, 2023.
[8] Zander W Blasingame and Chen Liu. Adjointdeis: Efficient gradients for diffusion models. Advances in Neural Information Processing Systems, 37:2449-2483, 2024.
[9] Andrew Campbell, Joe Benton, Valentin De Bortoli, Thomas Rainforth, George Deligiannidis, and Arnaud Doucet. continuous time framework for discrete denoising models. Advances in Neural Information Processing Systems, 35:28266-28279, 2022.
[10] Andrew Campbell, Jason Yim, Regina Barzilay, Tom Rainforth, and Tommi Jaakkola. Gener- ative flows on discrete state-spaces: Enabling multimodal flows with applications to protein co-design. arXiv preprint arXiv:2402.04997, 2024.
[11] Gabriel Cardoso, Yazid Janati El Idrissi, Sylvain Le Corff, and Eric Moulines. Monte carlo guided diffusion for bayesian linear inverse problems. arXiv preprint arXiv:2308.07988. 2023.
[12] Cheng Chi, Zhenjia Xu, Siyuan Feng, Eric Cousineau, Yilun Du, Benjamin Burchfiel, Russ Tedrake, and Shuran Song. Diffusson policy: Visuomotor policy learning via action diffusion. The International Journal of Robotics Research, page 027836492412736668 2023.
[13] Hyungjin Chung, Jeongsol Kim, Michael T Mccann, Marc L Klasky, and Jong Chul Ye. Diffu- sion posterior sampling for general noisy inverse problems. arXiv preprint arXiv:2209.1666 2022.
[14] Michael Scott Cuthbert and Christopher Ariza. music21: toolkit for computer-aide aided musicol- ogy and symbolic music data. 2010.
[15] Prafulla Dhariwal and Alexander Nichol. Diffusion models beat gans image synthesis. Advances in neural information processing systems, 34:8780-8794 2021.
[16] Carles Domingo-Fnricn Michal Drozdzal, Brian Karrer, and Ricky TQ Chen. Adjoint matching: Fine-tuning flow and diffusion generative models with memoryless stochastic optimal control. arXiv preprint arXiv:2409.08861, 2024.
[17] Zehao Dou and Yang Song. Diffusion posterior sampling for linear inverse problem solving: filtering perspective. In The Twelfth International Conference on Learning Representations, 2024.
[18] Bradley Efron. Tweedie's formula and selection bias. Journal of the American Statistical Association, 106(496) 2011.
[19] Ying Fan, Olivia Watkins, Yuqing Du, Hao Liu, Moonkyung Ryu, Craig Boutilier, Pieter Abbeel, Mohammad Ghavamzadeh, Kangwook Lee, and Kimin Lee. Reinforcement learning for fine- tuning text-to-image diffusion models. In Thirly-seventh Conference on Neural Information Processing Systems (NeurIPS) 2023. Neural Information Processing Systems Foundation, 2023.
[20] Wenhao Gao, Tianfan Fu, Jimeng Sun, and Connor Coley. Sample efficiency matters: benchmark for practical molecular optimization. Advances in neural information processing systems, 35:21342-21 21357, 2022.
[21] 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.
[22] Yingging Guo, Hui Yuan, Yukang Yang, Minshuo Chen, and Mengdi Wang. Gradient guidance for diffusion models: An optimization perspective. arXiv preprint arXiv:2404. /4743, 2024.
[23] Curtis Hawthorne, Andriy Stasyuk, Adam Roberts, Ian Simon, Cheng-Zhi Zhi Anna Huang, Sander Dieleman, Erich Elsen, Jesse Engel, and Douglas Eck. Enabling factorized piano music modeling and generation with the maestro dataset. arXiv preprint 1810: 2018.
[24] Yutong He, Naoki Murata, Chieh-Hsin Lai, Yuhta Takida, Toshimitsu Uesaka, Dongjun Kim, Wei-Hsiang Liao, Yuki Mitsufuji, Zico Kolter, Ruslan Salakhutdinov, et al. Manifold preserv- ing guided diffusion. arXiv preprint arXiv:2311.16422 2023.

---

[25] Jonathan Ho and Tim Salimans. Classifier-free 12X1: 2022.
diffusion
guidance.
arXiv preprint
[26] Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. Advances in neural information processing systems, 33:6840- 6851, 2020.
[27] Emiel Hoogeboom, Didrik Nielsen, Priyank Jaini, Patrick Forré, and Max Welling, Argmax flows and multinomial diffusion: Learning categorical distributions. Advances in Neural Information Processing Systems, 34:12454-12465, 2021.
[28] Wen- Yi Hsiao, Jen- Yu Liu, Yin-Cheng Yeh, and Yi-Hsuan Yang. Compound word transformer: Learning to compose full-song music over dynamic directed hypergraphs. In Proceedings of the AAAI Conference on Artificial Intellignce, volume 35, pages 178-186, 2021.
[29] Kexin Huang, Tianfan Fu, Wenhao Gao, Yue Zhao, Yusuf Roohani, Jure Leskovec, Connor W Coley, Cao Xiao, Jimeng Sun, and Marinka Zitnik. Therapeutics data commons: Machine learn- ing datasets and tasks for drug discovery and development. Proceedings of Neural Information Processing Systems, NeurlPS Datasets and Benchmarks, 2021.
[30] Yujia Huang, Adishree Ghatare, Yuanzhe Liu, Ziniu Hu, Qinsheng Zhang, Chandramouli S Sastry, Siddharth Gururani, Sageev Oore, and Yisong Yue. Symbolic music generation with non-differentiable rule guided diffusion. arXiv preprint 2xXi::2402.14285 2024.
[31] Eric Jang, Shixiang Gu, and Ben Poole. Categorical reparameterization with gumbel-softmax. arXiv preprint arXiv: /6/ 1.4, 2016.
[32] Jasper Janssens, Sara Aibar, Ibrahim Ihsan Taskiran, Joy N Ismail, Alicia Estacio Gomez, Gabriel Aughey, Katina Spanier, Florian V De Rop, Carmen Bravo Gonzalez-Bie Blas,, Marc Dionne, al. Decoding gene regulation in the fly brain. Nature, 601 636, 2022.
[33] Alexia Jolicoeur-Martineau Kilian Fatras, and Tal Kachman. Generating and imputing tabular data via diffusion and flow-based pradient-boosted trees. arxiv, page 8999.09968, 2023. doi: 10.48550. arXiv preprint ARXIV2330900966 09968.
[34] Korrawe Karunratanakul, Konpat Preechakul, Emre Aksan, Thabo Beeler, Supasorn Suwa- janakorn, and Siyu Tang. Optimizing diffusion noise can serve as universal motion priors. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pages 1334-1345, 2024.
[35] Heeseung Kim, Sungwon Kim, and Sungroh Yoon. Guided-tts: A diffusion model for text- to-speech via classifier guidance. In International Conference on Machine Learning, pages 11119-11133, PMLR, 2022.
[36] Hongjian Li, Kwong-Sak Leung, Man-Hon Wong, and Pedro Ballester. Improving autodock vina using random forest: the growing accuracy binding affinity prediction by the effective exploitation of larger data sets. Molecular informatics, 34(2-3):1155 115--2) 2015.
[37] Xiner Li, Yulai Zhao, Chenyu Wang, Gabriele Scalia, Gokcen Eraslan, Surag Nair, Tom- maso Biancalani, Shuiwang Ji, Aviv Regev, Sergey Levine, et al. Derivative-free guidance continuous and discrete diffusion models with soft value-based decoding. arXiv preprint arXiv: 2rXi:22408.08252 2024.
[38] Haowei Lin, Shanda Li, Haotian Ye, Yiming Yang, Stefano Ermon, Yitao Liang, and Jianzhu Ma. Tfg-flow: Training-free guidance in multimodal generative flow, 2025. Available at http://arxiti
2a0..///5501..22 14216.
[39] Yaron Lipman, Marton Havasi, Peter Holderrieth, Neta Shaul, Matt Le, Brian Karrer, Ricky TQ Chen, David Lap, Heli Ben-Hamu, and Itai Gat. Flow matching guide and code, arXiv preprint arXiv:2412.06264 2024.
[40] Aaron Lou, Chenlin Meng, and Stefano Ermon. Discrete diffusion language modeling by estimating the ratios of the data distribution. 2023.
12

---

[41] Yueming Lyu, Kim Yong Tan, Yew Soon Ong, and Ivor W Tsang. Covariance-adaplle sequen- tial black-box optimization for diffusion targeted generation. arXiv preprint 208002 2024.
[42] Nanye Ma, Shangyuan Tong, Haolin Jia, Hexiang Hu, Yu-Chuan Su, Mingda Zhang. Xuan Yang. Yandong Li, Tommi Jaakkola, Xuhui Jia, et al. Inference-time scaling for diffusion models beyond scaling denoising steps. arXiv preprini arXiv:2501.09732. 2025.
[43] Pierre Marion, Anna Korba, Peter Bartlett, Mathieu Blondel, Valentin De Bortoli, Arnaud Doucet, Felipe Llinares-López, Courtney Paquette, and Quentin Berthet. Implicit diffusion: Efficient optimization through stochastic sampling. arXiv preprini arXiv:2402.05468, 2024.
[44] Reiichiro Nakano, Jacob Hilton, Suchir Balaji, Jeff Wu, Long Ouyang, Christina Kim, Christo- pher Hesse, Shantanu Jain, Vineet Kosaraju, William Saunders, et al. Webgpt: Browser-assisted question-answering with human feedback. arXiv preprint
11t::2332,299,, 2021.
[45] Hunter Nisonoff, Junhao Xiong, Stephan Allenspach, and Jennifer Listgarten. Unlocking guidance for discrete state-space diffusion and flow models. arXiv preprint arXiv:2406.0157.. 2024.
[46] Jiachun Pan, Jun Hao Liew, Vincent YF Tan, Jiashi Feng, and Hanshu Yan. Adjointdpm: Adjoint sensitivity method for gradient backpropagation of diffusion probabilistic models. arXiv preprint arXiv:2307. 2023.
[47] Angus Phillips, Hai-Dang Dau, Michael John Hutchinson, Valentin De Bortoli, George Deligiannidis, and Amnud Doucet. Particle denoising diffusion sampler. arXiv preprint arXiv:2402.063320 2024.
[48] Mihir Prabhudesai, Anirudh Goyal, Deepak Pathak, and Katerina Fragkiadaki. Aligning text- to-image diffusion models with reward backpropagation. arXiv preprint arXiv:2310.03739 2023.
[49] Yifei Shen, Xinyang Jiang, Yifan Yang, Yezhen Wang, Dongqi Han, and Dongsheng Li. Understanding and improving training-free loss- diffusion guidance. Advances Neural Information Processing Systems, 37:108974-10902, 2024.
[50] Yuchen Shen, Chenhao Zhang, Chenghui Zhou, Sijie Fu, Newell Washburn, and Barnabas Poczos. Non-differentiable diffusion guidance for improved molecular geometry. In ICML. 2024 AI for Science Workshop.
[51] Raghav Singhal, Zachary Horvitz, Ryan Teehan, Mengye Ren, Zhou Yu, Kathleen McKeown, and Rajesh Ranganath. A general framework for inference-time scaling and steering of diffusion models. arXiv preprint arXiv:2501.06848 2025.
[52] Marta Skreta, Tara Akhound- Viktor Ohanesian, Roberto Bondesan, Alán Aspuru- Guzik, Arnaud Doucet, Rob Brekelmans, Alexander Tong, and Kirill Neklyudov. Feynman- kac correctors in diffusion: Annealing, guidance, and product of experts. arXiv preprint arXiv:2503.02889, 2025.
[53] Jiaming Song, Qinsheng Zhang, Hongxu Yin, Morteza Mardani, Ming- Yu Liu, Jan Kautz, Yongxin Chen, and Arash Vahdat. Loss-guided diffusion models for plug-and-pla play controllable generation. In International Conference on Machine Learning, pages 22483-32498, PMLR, 2023.
[54] Yang Song and Stefano Ermon. Generative modeling by estimating gradients of the data distribution. Advances in neural information processing systems, 32, 2019.
[55] Yang Song, Jascha Sohl-Dickstein, Diederik P Kingma, Abhishek Kumar, Stefano Ermon, and Ben Poole. Score-based generative modeling through stochastic differential equations. arXiv preprint arXiv:2011. 13456, 2020.
[56] Hannes Stark, Bowen Jing. Chenyu Wang, Gabriele Corso, Bonnie Berger, Regina Barzilay, and Tommi Jaakkola. Dirichlet flow matching with applications to dna sequence design. arXiv preprint arXiv:2402.05844 2024.
13

---

[57] Nisan Stiennon, Long Ouyang, Jeffrey Wu, Daniel Ziegler, Ryan Lowe, Chelsea Voss. Alec Radford, Dario Amodei, and Paul Christiano. Learning summarize with human feedback. Advances in Neural Information Processing Systems, 33:3008-3021, 2020.
[58] Haoran Sun, Lijun Yu, Bo Dai, Dale Schuurmans, and Hanjun Dai. Score- continuous- discrete diffusion models. arXiv preprint arXiv:2211.16750 2022.
[59] Kim Yong Tan, Yueming Lyu, Ivor Tsang, and Yew-Soon Ong. Fast direct: Query-efficient on- line black-box guidance for diffusion- moodel target generation. arXiv preprint arXiv:2502.01692, 2025.
[60] Zhiwei Tang, Jiangweizhi Peng, Jiasheng Tang, Mingyi Hong, Fan Wang, and Tsung-Hui Chang. Inference-time alignment of diffusion models with direct noise optimization. arXiv preprini WrXi:22405118811 2024.
[61] Ibrahim Taskiran, Katina I Spanier, Hannah Dickmänken, Niklas Kempynck, Alexandra Pančíková, Eren Can Ekşi, Gert Hulselmans, Joy N Ismail, Koen Theunis, Roel Vandepoel, et al. Cell-type-directed design of synthetic enhancers. Nature, 626(7997):112-220, 2024.
[62] Masatoshi Uehara, Yulai Zhao, Tommaso Biancalani, and Sergey Levine. Understanding reinforcement learning-based finettuning of diffusion models: A tutorial and review. arXiv preprint arXiv:2407. 13734, 2024.
[63] Masatoshi Uehara, Yulai Zhao, Kevin Black, Ehsan Hajiramezanali, Gabriele Scalia, Nathaniel Lee Diamant, Alex M Tseng, Tommaso Biancalani, and Sergey Levine. Fine- tuning of continuous-time diffusion models as entropy anrooy-rreuulrrzze control. arXiv preprint arXiv:2402. /544, 2024.
[64] Masatoshi Uehara, Xingyu Su, Yulai Zhao, Xiner Li, Aviv Regev, Shuiwang Ji, Sergey Levine, and Tommaso Biancalani. Reward-guit guided iterative refinement diffusion models at test-time with applications to protein and dna design. arXiv preprint arXiv:2502. 14944, 2025.
[65] Masatoshi Uchara, Yulai Zhao, Chenyu Wang, Xiner Li, Aviv Regev, Sergey Levine, and Tom- maso Biancalani. Inference-tine alignment in diffusion models with reward-guided generation: Tutorial and review. arXiv preprint arXiv:2501.090 2025.
[66] Siddarth Venkatraman, Moksh Jain, Luca Scimeca, Minsu Kim, Marcin Sendera, Mohsin Hasan, Luke Rowe, Sarthak Mittal, Pablo Lemos, Emmanuel Bengio, et al. Amortizing intractable inference in diffusion models for vision, language, and control. Advances in neural information processing systems, 37:76080-76111 2024.
[67] Clement Vignac, Igor Krawezuk, Antoine Siraudin, Bohan Wang, Volkan Cevher, and Pas- cal Frossard. Digress: Discrete denoising diffusion for graph generation. arXiv preprint wwXiv:2209.14744 2022.
[68] Bram Wallace, Akash Gokul, Stefano Ermon, and Nikhil Naik. End-to-end diffusion latent optimization improves classifier guidance. In Proceedings of the IEEE/CVE International Conference on Computer Vision, pages 7280-7290, 2023.
[69] Bram Wallace, Meihua Dang, Rafael Rafailov, Linqi Zhou, Aaron Lou, Senthil Purushwalkam, Stefano Ermon, Caiming Xiong, Shafiq Joty, and Nikhil Naik. Diffusion model alignment using direct preference optimization. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recognition, pages 8228-888888888 8238,223,,8888 2024.
[70] Chenyu Wang, Masatoshi Uehara, Yichun He, Amy Wang, Tommaso Biancalani, Avantika Lal, Tommi Jaakkola, Sergey Levine, Hanchen Wang, and Aviv Regev. Fine-tuning discrete diffusion models via reward optimization with applications to dna and protein design. arXiv preprint arXiv:2410..3644. 2024.
[71] Ziyu Wang, Ke Chen, Junyan Jiang, Yiyi Zhang, Maoran Xu, Shuqi Dai, Xianbin Gu, and Gus Xia. Pop909: A pop-song dataset for music arrangement generation. arXiv preprint 07X1v:2008.07142, 2020.
14

---

[72] Joseph L. Watson, David Juergens, Nathaniel R Bennett, Brian L Trippe, Jason Yim, Helen E Eisenach, Woody Ahem, Andrew Borst, Robert J Ragotte, Lukas Milles, al. De novo design of protein structure and function with rfdiffusion. Nature, 620(7976):108--1100
2023.
[73] Luhuan Wu, Brian Trippe. Christian Naesseth, David Blei, and John P Cunningham. Practi- cal and asymptotically exact conditional sampling in diffusion models. Advances in Neural Information Processing Systems, 36:31372-31444 2023.
[74] Li-Chia Yang and Alexander Lerch. On the evaluation of generative models in music. Neural Computing and Applications, 32(9):477344784 2020.
[75] Lingxiao Yang, Shutong Ding, Yifan Cai, Jingyi Yu, Jingya Wang, and Ye Shi. Guidance with spherical gaussian constraint for conditional diffusion. arXiv preprint arXiv:2402.03201, 2024.
[76] Soojung Yang, Doyeong Hwang, Seul Lee, Seongok Ryu, and Sung Hwang. Hit and lead discovery with explorative rl and tragment-basee molecule generation. Advances in Neural Information Processing Systems, 14.7924-7936, 2021.
[77] Chun Wei Yap. Padel-descriptor: An open source software to calculate molecular descriptors 2011.
and fingerprints. Journal of computational chemistry,
[78] Haotian Ye, Haowei Lin, Jiaqi Han, Minkai Xu, Sheng Liu, Yitao Liang, Jianzhu Ma, James Zou, and Stefano Ermon. Tfg: Unified training-free guidance for diffusion models. arXiv preprint arXiv:2409. 15761, 2024.
[79] Jiwen Yu, Yinhuai Wang, Chen Zhao, Bernard Ghanem, and Jian Zhang. Freedom: Training- free energy-guided conditional diffusion model. In Proceedings of the IEEE/CVF International Conference on Computer Vision, pages 23174-23184 2023.
[80] Zaixi Zhang, Marinka Zitnik, and Qi Liu. Generalized protein pocket generation with prior- informed flow matching, arXiv preprint arXiv:2409. 19520, 2024.
[81] Linxi Zhao, Yihe Deng, Weitong Zhang. and Quanquan Gu. Mitigating object hallucination in large vision-language models via classifier-free guidance. arXiv preprint urXiv:2402.08680, 2024.
[82] Yulai Zhao, Masatoshi Uehara, Gabriele Scalia, Sunyuan Kung, Tommaso Biancalani, Sergey Levine, and Ehsan Hajiramezanali, Adding conditional control to diffusion models with reinforcement learning, arXiv preprint arXiv:2406. 12120, 2024.
15

---

A Additional Related Work
In this section, we provide an overview of related work aligning diffusion models with downstream objectives. The methods in this domain can broadly categorized into inference-time alignment and post-rrining/fie--uning approaches. We begin by reviewing these two main categories, followed by a discussion of other relevant methods, including alternative alignment techniques for diffusion models and discrete diffusion and flow models.
Inference- Time Alignment. Classifier guidance uses a time-dependent classifier to provide directional signals throughout the generation process [55, 15]. A growing body of work ex- plores training-free free guidance methods that leverage gradients derived from objective functions [13, 4, 78, 53, 24, 79, 49]. A line of work [73, 47, 17, 11, 52] combined diffusion models with Sequential Monte Carlo methods. [37, 30] use value-based selection and importance sampling When objectives are non-differentiabl. A concurrent work [51] proposes an SMC-based framework for inference-time scaling using value resampling. A widely used and straightforward approach is Best-of-N sampling, where the model generates multiple candidates and selects those with the highest objective values [57, 44, 5].
Fine-tuning Diffusion Models. Fine-tuning diffusion models involves directly adjusting model parameters to align with downstream objectives. One common method involves direct fine-tuning through gradient backpropagation across the sampling process [7, 63, 48]. To ensure stable training and prevent divergence from the original distribution, Kullback-Leibler (KI.) regularization has been introduced in [63, 16, 66]. Reinforcement learning has also emerged as a powerful tool for fine-tuning [7, 19, 82, 62]. [69] proposes direct preference optimization for aligning diffusion models with human preferences. Additionally, recent work [70] has extended fine-tuning techniques to discrete diffusion models.
Other Diffusion Alignment Methods. Beyond guidance and fine-tuning approaches, an alternative line of training-free methods focuses on optimizing the initial latent state of the reverse diffusion process [68, 6, 34, 60]. These methods typically use an ODE solver to backpropagate the objective gradient directly to the initial latent state. making them gradient- based version of the Best-of-N strategy. Additionally, adjoint-based methods have been proposed for gradient estimation in diffusion models [43, 46, 8]. [59, 41] focus on improving query efficiency when the objective function is computationally expensive. Other recent work explores diffusion-based alignment techniques and applications of diffusion models in biology [72, 3, 50, 33].
Discrete Diffusion and Flow Models. Austin et al. [2] and Hoogeboom et al. [27] pioneered diffusion in discrete spaces by introducing corruption process for categorical data. Campbell et al. [9] extended discrete diffusion models to continuous time, while Lou et al. [40] proposed learning probability ratios. Discrete Flow Matching Campbell al. [10], Gat et al. [21] further advances this field by developing a Flow Matching algorithm for time- continuuns Markov processes on discrete state spaces, commonly known as Continuous- Time Markov Chains (CTMCs). Lipman et al. [39] presents unified perspective on flow and diffusion.
B Limitations and Broader Impacts
Limitations. We do not observe significant limitations in our methods. However, in cases where the objective function non-differentiable, very expensive evaluate, and lacks an effective surrogate neural network, our methods can become relatively time-consuming. These represent inherently difficult scenarios, where a trade-off between computational cost and optimization effectiveness is unavoidable.
Broader Impacts. This paper aims to explore inference-time alignment methods for diffusion models, advanced control techniques in generative AI, and contribute to the broader field of artificial intelligence. This work holds promise for improving the accuracy and personalization of Al systems in diverse domains, such image synthesis and drug discovery. Nonetheless, the same techniques may also be exploited to produce harmful content.
C Discussion on Design Axes
We compare the guidance designs: TreeG-SC, TreeG-SD and TreeG-G based on experimental results, to separate the effect of guidance design from the effect of tree search, we set A = 1. A side-to-side comparison on the performance the three methods are provided Table 5.
16

---

Gradient-based v.s. Gradient-free: depends on the predictor. The choice between gradient- based and gradient- free methods largely depends on the characteristics of the predictor.
The first step is determining whether a reliable, differentiable predictor is available. If not, sampling methods should be chosen over gradient-based approaches. For example, in the chord progression task of music generation, the ground truth reward is obtained from chord analysis tool in the music21 package [14], which is non-differentiable. Additionally, the surrogate neural network predictor achieves only 33% accuracy [30]. As shown in Table in cases where no effective differentiablee predictor exists, the performance of gradient-bas -based methods (c.g., DPS) is significantly inferior to sampling-based methods (e.g.. TreeG-SD and SCG).
If a good differentiable predictor available, the choice depends the predictor's 's forward pass time. Our experimental tasks illustrate some typical cases. For molecule generation which uses a pretrained predictor model, forward passes fast as shown in Table Thus, sampling approaches efficiently expand the candidate set and capture the reward signal, yielding strong results (Table 5). While for enhancer DNA design, where predictors have slow forward passes, increasing the sampling candidate set size to capture the reward signal becomes prohibitively time-consuming, making muddient-based method more effective (Table 5). However, for the optimization of non-differentiable targets which employ an oracle as the predictor like small molecules' Docking score, gradient-batt based methods are not applicable and computationally expensive target measurement becomes an bottleneck (Table 7).
TreeG-SC v.s. TreeG-SD. Experiments on continuous data and discrete data give divergent results along this axis. In the continuous task of music generation (Table 1), TreeG-SD achieves equal or better performance than SCG (equivalent TreeG-SCC with the same candidate size K 16 and similar time cost (details in Appendix G.I). Thus, TreeG-SD is preferable in this continuous setting. Conversely, for discrete tasks, TreeG-SD requires significantly more samples, while TreeG-SC outperforms it, as shown in Table 5.
Table 5: Comparison of results across TreeG-G, TreeG-SC and TreeG-SD. For molecule generation, the target is specified as the number of rings
N 2. For enhancer DNA design, the results correspond to Class 3.
TreeG-G
TreeG-SC
TreeG-SD
MAE
0.09 + 0.54
0.02 + 0.14
0.10 + 0.33
Molecule
Time +
13.5s
12.9s
11.2s
N
30
30
K
2
200
Prob
0.89 + 0.14
0.13 + 0.39
0.002 + 0.000
Enhancer
FBD
213
384
665
Div t
321
375
376
Time 4
10.3s
285.1s
189.7s
N
20
20
K
64
1024
Table 6: Computation time per basic unit (ms)
Cmodal
Opeed
Cbackprop
Molecule
0.038
2.2e-4
0.036
Enhancer 0.087
0.021
0.11
D Omitted Proofs in Section
D.1 Proof of Theorem
We begin by restating Theorem with all conditions for completeness, followed by its proof. Theorem (Restatement of Theorem 1). Consider TreeG-Sampling Current at time with active set of size one and selection performed via multinomial resampling. Then, for any E, > 0, it holds with probability 1 8:
|| T( Fts (t.,)lle<<
17

---

provided one of the following conditions is satisfied: (a, Continuous)It holds under the f= = 1 norm. Suppose data follow Gaussian distribution and the objective function is linear. The Branch-Out size is K = ( (log(1/)) and the timestep is sufficiently small such that a =
(b, Di holds under the & = oo norm. The mapping t + Pije(a11 x)) is I--Lipschizz continuous for all x and 11, and the likelihood scores satisfy 0 < Bmin I exp(f, S Bmax for
all x. Branch-Our size is K = O ( ). Monte Carlo size is N O [o and time step
At Oe)), where is the data space.
Proof. Proof of (a) continuous case: Assume the data is drawn from a Gaussian, and the objective function is linear
21 N(, T);
fy(a;) = g æ.
Since de æ1 ~ ((Vor #1, (1 - ā+) T), by Bayes' rule the posterior follows:
F1 D ~ NV ((1 ã4)) μ + vā, It, (1 oz) 1))
We have the denoising model's predictive distribution for label y given æ;
1 /
(r xx)) = ply x1) p(z1
xx4) dx Z (x(()()))) p(a11 xx)) dx
where the objective function is linear fx( g gTa xx Since for a Gaussian (m,, E),
/
exp(g" Na; m, E) dr = exp g T + 2 "
it follows that Therefore, we have
po(y| xx) exp (T ((1 āz) p vār (1 at) 11011²)
Vx, l: xz)) vārg, which allows us to express the conditional score as:
RR, log (x
|y) = V., log (xx:) + Vo, g.
(11)
Recall the transition step (2). The unconditional transition is given by:
T( xx) = N (:: Titar, oi
(12)
where
Bt4 + (1 V log (x
Vot
Using the conditional score from (11), the target conditional transition distribution becomes:
T(- xt. y) = N (: T + (a-aa))aa++a 9, of
(13)
Gaamp-Sg Current proceeds by generating i.i.d. samples X ~ T(- xt), followed by multinomial resampling according to the weights
V(x) = exp (Ju (#))((;))),
where, using Tweedie's formula [18], the posterior mean of æ given x; is:
T1) = E6x= [ (1 āz) p + Vo, zt.
Therefore, the value function simplifies to:
(x) = gg ((1 - (a1-a)) oor wx))
From Lemma 2, with probability at least 1 - 6, the distribution 7 produced by this resampling satisfies:
| Ti|1, s 4(11 Tog(4/8)
(14)
2K
where the adjusted distribution is
(x: exp (Vōrg 9 a:) T(x xx).
and the constant C' is given by
C g Tz+At
We have
Ti(.) N (1: Tetsi + o
(15)
18

---

Zt: y), we use the bound via KL divergence: Now, comparing the means of Ti and T(-
1 T(. ze. v)1l S ( Zt. y)) 2 Malla
where
111 = E++si + 0/ aā 9. 122 - Bi+si + (1 - ai)) var+arg. with 0, vI - Oz and at - (t// 10/00t44 Thus,
[ - ------1 ze. will I 20L- v(s) 11l122.
(16)
Combining this with (14), obtain:
1 - T( -T(- De, w)/, - 04(1+0) 1og(4/6)
+ 201++111 ai((1 vou) llg122
2K
Thus, if K = @ (1 (1+ C)2 and 1 - a = O (=2/ provided that At is sufficiently small, the total variation distance is bounded by e. Ignoring constant factors, this completes the proof. Proof of (b) discrete case: We simplify the notation and recall some key definitions for clarity. At time step i, the current state is given by 2t. The unconditional transition probability is defined as:
T(- xx) o{-, 2 Re(2,,)) .) At, where of,, xz} is the Dirac delta function. The target conditional distribution is T(- æt, v) = ó'-, ... + Re 11) At, where the conditional rate is defined as [45]:
(2 x)
(e v)
p xz) R₁ (x), for æ + Zt.
and
Rg (Xe, 3t (1) - Σ
Re(xr, x (
For simplicity, we introduce the shorthand:
To = T- xt), and T T= x.,
We then define the distribution used in importance sampling, where we first sample from To and then reweight according to the likelihood pe -):
Pr(u x)) Ta( (xx Σe (r x)) To(
In our algorithm, we use Monte Carlo estimation to approximate the likelihood:
(y x)) / p(y æ1) P1 (#)
マ / exp (fy(z))) P1je(z1 x)) dæ
This is estimated using the following procedure (as shown in Lines 2 and 3 of Value Function 1): a Cat(uo( At)), E [N],
1 exp (fv(t))
(17)
where we assume the pretrained flow model is perfect, i.e., u0 + At) = Pilc+ x)) We denote the Monte Carlo estimate of the likelihood in (17) as q. Using this, we define the distribution used in importance sampling, where we first sample from and reweight according ğ:
((x)) To(
T2(x) = Σe ((x) To (x)
When resampling over K candidates t To and reweighting according to q. the resulting (empirical) output distribution
T(x) Wp 1 (x = w²),
km
where w/k = // ((x²).
We can therefore decompose the distance between the empirical distribution 7 and the target distribution 7 as:
I - - I -Tilloo +1[ Tello + +1 -
(18)
19

---

We now proceed to bound the three terms on the right-hand side of (18), starting with the first term involving Ti. We have:
Σ pv x)) To(x) poly xx))
1 Σ
Re( x) At + Σ
Pily 2) x) At
= -Peyy axe)
pely axt)
Σ
Re 2) Al
Σ Pe(y =) R) z) A
zyan
=Pe(y xx) Σ
Lpe 2) pely (2); At
=pr(y xx) + O(A().
Therefore, for any + Ft, we have:
(y x) Tx( T1(x) Ex ( / x (
pr x) (2, At
Pely Φ) Pr(y xx))
Re( x) + O(At).
O(A))))
(y xx,) - O(At)
As result, we can bound the distance as:
|T Ti -- 0(A()).
(19)
We now bound the error introduced by the Monte Carlo estimation (17). By Lemma 3, with probability at least 1 - 8/2, we have:
max ((xx) (1)++a E1, #EX
where the unnormalized quantity defined
(1je(x)= = exp (Jy(z))) Pije(an1 (x) dæy,
and where
1og(4(2'1/8)
B Bmax
Bmax sup exp (x)). xex
2N
Additionally, due to the Lipschitz continuity of + (ij x)), we have:
[Pij((z1 ()) P1 x) L At,
which implies:
(())((r)) (1|+4a( (x) < B Bmax AL.
Therefore, combining the Monte Carlo estimation error and the temporal approximation error, we get (with probability at least - 8/2):
maxlĀ( (x)) S + Bmax At.
(20)
xex
Recall that:
(1/{(a)) To(x))
[xx
where (1j(()) = pc
Σx (1))(=)) (x)
and
((x) (a(
T2(x) Σe ((x)) (x)
By applying (20) and using Lemma 4, we obtain with probability at least 1 - 8/2:
4 (E1 + Bmax = 4Bmax
log( 4/x1//0)
||T - 5 Buin
+ L LL
(21)
Brin
2N
where
Bmin inf exp (x)). xEX
And it requires:
Bmax At < Bmin-
Finally, we bound the error introduced by sampling from the multinomial distribution over the K candidate branches. By Lemma 2, we have that with probability at least 6/2,
log( (1/6)
TT b1 (1 Bmax/ Buin) V
(22)
2K
20

---

Now, combining the three error terms - from (19), (21), and (22) we obtain that with overall probability least 1 8,
into the decomposition (18),
4.max
log Tog(4|22)) (4(2115)
T - -
+ LAt +
Buin
2N
2K
To ensure that the total error stays below prescribed threshold e. Specifically, we choose the time
step At O (VE+ Rimsirr.) :). the Monte Carlo sample size N θ
13 1og(4)x1/8) and the
13
branch candidate size B proof.
(o8(11x11/6)
If we omit constant factors, this completes the
D.2 Proof of Lemma
Lemma (Recall Lemma 1). In both continuous and discrete cases, the transition probability during inference timestep satisfies:
T(o+tar xx)) Eà [T'+++ Iee æe,
where the expectation is taken over distribution estimated by ug, with T being the true posterior distribution predetermined by the noise schedule.
Proof. In the continuous case, the forward process defined as: āe) I), F++1: ~ (( (1-6 T++
2g N ( (1
Given this, the posterior distribution conditioned both æt and is:
p(- xt, x1) = (N + 10,2011,
(23)
where the coefficients are defined as:
ār+At (1 az), Ca.1 Var(1 a1tD))
Val+Ar(1- - as)
B 1 a₁
Ct2
1- ae
1 αz
We set the transition distribution
(- xt, x1) = (1; + (0,201,1111
Let the estimate d1 be sampled from the distribution:
91 = (Z (1-a;)) at)
where, as given in (4), the posterior mean 2iIr is:
B1jt
Vo (r, v1 α+ uo 1))
Then, the expected approximate posterior becomes:
Bajnn (T*(
Dt, i1)) = N (0t,13t + 0,2201
(24)
where a; -
Thus, (24) defines the transition distribution T(x+4sc xx) used for sampling during inference.
For the discrete case, recall the expression for the rate matrix used during inference, given in (6):
RS (at. j) = E 10
[Re(ar( .j a
(m) (m. laee)
where the conditional rate matrix is defined as
8(j, x
R2 ( i 21) = 1 1
1f2, = M}.
Given æ, and 2j the transition probability is
T ( [j Fr, æ1) _(x (d) . + (x . (( At.
(d)
Taking the expectation over क ~ us( xt). we obtain
F2 ( (j 2,, x1) ج( j} + E Eee 1 ~ (0) ( (m))
(x .J [ At,
which corresponds to the transition probability T(x+s xx). This completes the proof.
21

---

D.3 Proof of Theorem 2
Theorem (Restatement of Theorem 2). Consider TreeG- Sampping Destination at time with an
active set of size and selection performed via multinomial resampling. Then, for any E, > 0, holds with probability ô: 6:
I T( xts xt,yylle E,
provided one of the following conditions satisfied: (a, Continuous) holds under the f = 1 norm. Suppose data follow Gaussian distribution and the objective function is linear. The Branch- Out size is K ( (1 and we set Pt. 1 -22y Tt
1- (1-66 a1).
1-a;
(b, Discrete) holds under the = do norm. The likelihood scores satisfy 0 < Buin S
S
Buax for all a. The Branch-Out size K O D2 log( log() where X is the data space and D is its dimension.
Proof. Proof of (a) continuous case: We begin by recalling the unconditional transition process given in (3);
U++Ai C13; + 12 + O2E,
where the coefficients are defined as 61 Ct (ar(1 a.tos)
/artaill 0z
C2 = Ct,2
1-04
vI Ce, and T1/: E[æ1 zr).
Assuming that the data distribution is Gaussian and the objective function is linear, we have:
21 ((,, I),
fy(x;) g x:.
In Line of Module 2 and the associated Value Function 2, a candidate à is proposed by sampling from N (a pt and reweighting using exp(fy(=)) = exp(g x)) Let ÿ denote the distribution density of the output 1 According to Lemma 2, with probability least 6, the distance between q and the ideal distribution satisfies
log(4/8)
- - 4(1 + C)
V
(25)
2K
where the ideal distribution
((x) exp(g T a)) N(x; Dijts P:T);
and the constant C' is defined as C = 21j follows from this form that is a Gaussian with mean 1i P:g and covariance p.l, i.e.
q= - P.g.p.
In Line 3 of Module 2, the next sample a++ is generated according to Et-At ~ N((1 + C2 7i I),
â q.
Consequently, the distribution at denoted f. is the convolution of 02ÿ and y, where =N(cc1Z
t = (c2q) * 4.
Next, we will show that the true conditional transition probability satisfies
T( Et. y) (c24) ip,
by setting
ãi+At (1 oz)- 1 a₁
Pt = 1 - ag By the property of convolution between Gaussian distributions, we have
(c2g) # = NN(22 + c2p:g, Eppt I) * A T I)
Neici, c2 c2pig, (T. + Ep.) I).
'The convolution operation models the distribution of the sum of two independent random variables. For probability density functions f and on gd the convolution is defined as (f + (z) = fgz f(y)(( y) dy. In the case of Gaussian distributions, this results in Gaussian with summed means and covariances.
22

---

We now verify that this matches the conditional transition distribution by examining the mean and variance. Starting with the variance term, we compute
01+St (1 (1-ar)+ aa))+ +
/01+2a(11 anl) (1 at)
Tt + E:p: = 1 04
-it
at (1 -ar+Dr + Out+1 -0-2:10))
04 (1 --1+4/1))= =1-
=
For the mean, we have
C1 + C2 + C2P:g c1 + C2 + - v
Recalling from (13) in the proof in App. D.1, the target conditional transition distribution is
T( zt. y) N (: a+tar + (1 at) of1).
where the mean is Br+At = cı + 12
Hence, the convolution (e2q) yp exactly recovers the conditional transition distribution T( x;, v)- Therefore, we bound the distance between the output distribution and target transition distributions as follows:
||
T-
Tt. y) | (1(22)) & (c24) 11111
< ||c2 rv= <2llá - elli.
where the inequality follows from the data processing inequality under convolution with a fixed distribution.
With (25), we obtain that with probability at least -
log(4/8)
| - T-- T4 v)lls 402 + CC)
2K
Hence, to ensure the approximation error is at most it suffices to choose the branch-out size 1og(1/6) up constant factors, which completes the proof.
K θ c1 + C)2
Proof of (b) discrete case:
In Line 2 of Module and with Value Function candidate state ã is proposed by sampling from the distribution Pije(- æ; (since ug is optimal estimation), where the reweighting term
exp(fy(z1)) = p(y 21). Let & denote the density of the resulting distribution over ø
According to Lemma 2, with probability at least 6, the foo distance between I and the ideal target distribution is bounded as:
Bmax Bmin
log log(2)XX1/8)
l 2 (1
(26)
2K
where the ideal distribution is given by
a(-) x p(u Pzj( (:1 wx):
and hence
P.p( xe, v)-
Here, Bmax = suP (x)(f((#)) and Bmin infREx exp( (x)).
Next, Line 3 of Module 2, the next state æ441 is sampled according to:
[ 5) Emin [6(2
(1) ..} + Rs
(1 (d)
.j (((e)) A1
where the conditional transition rate matrix satisfies:
(d) (w... y) (pd Rs 1z ij -
(d)
as given in (8).
Accordingly, the target conditional transition probability under T( wc. y) is:
Pg (( Exing [6(2, =s} R. [z .J |z(1)) At
(d)
(d)
with q(.) = P.je( x),
23

---

Therefore, for all dimensions d E [D], the deviation between the approximate and conditional transition probabilities is bounded by:
Pi
(d) (TE = P2 (oiffr =)] = l1 g01
Taking the product structure across all dimensions, we obtain the total deviation in transition operators:
| T- Zt, >> D 11 ol0oo-
By substituting the bound from (26), we conclude that to ensure probability at least 1 8, it suffices to choose
11 IT(- Dt. v)lloo & with
B D log(|x]/6)
2²
D.4 Auxiliary Lemmas
In this section, we provide auxiliary lemmas with proofs.
Lemma 2. Lef X1, XI,..., Xx be i...d. draws from proposal density measurable space (X, A). Define
Z = / p(x) q(x) dr,
w; = (X,)) 20,
Wt
and normalized weights W; probabilities {wi), and define the empirical law
Let Xi. Xi be a multinomial resample of {Xi} with
Σラ=1 Wj
(g(A) = p(z) g(z)
(x(A)) = R Σ 1xgeAb
dx.
2
Then for any E (0, 1), with probability at least 1 8, where one may take either
(a) 1f0 ((x) M co and X is finite, then
M
l2g 21)8)
llAx Hallo suplax(A) Pg(A)) S (1+
AEA
Z
2K
=Vp(x)==((1, E), g(x)) = = x. then
lĀ Malli S 4 4(1
Vgg Eg
log (4/6
1g T 1
2K
Proof. For (a): Define the measure
K
SK (Xi) (X.EA)
((A) w 1 ((SE))
Σje {(x))
Then by the triangle inequality.
|l Myllo Il -i + 1/ - -yll
To bound jāx TV, that conditional on {X,). J. the resampled points Xi...., Xx are i.i.d. draws from the finite-support distribution ju. By Hoeffding's 's inequality, for any measurable A,
Pr(Iãx (A) μ{A)]>> (X.)) 2exp(-2Ke>).
A union bound over the two tails and taking the supremum over A implies that, with probability at
8
least 1
2
(og(2)2(//4) 2K
låx Toloo <
To bound || - Polloo, observe that for any A,
K Σ ((x)) 1 2 (A(
((AA) - 10000-1,,40 (A)
K E}19((,,)
K
q(X,)
24

---

5 2x]'' Since 0 I 9 S M, Hoeffding's inequality yields simultaneously. with probability at least
the two bounds K
1og(2)XX1/0)
(A)
& My
((x))
2 = MV
2K
K
2K
1=1
j=1
On this event, the denominator satisfies
1 K
2 Z M
logl 22222/21// 2K
Assuming K is large
enough that M
10/(2)
< 2/2, we obtain
2K
log 128
M
2K
M
log (2( /6)
(M(A) P₂(AA]
1og(22XX(/0)
Z
2K
Z M
2K
and taking supremum over A= = E gives
M
log(2|X1/8)
| - Myllo & Z
2K
By union bound the two tigh-probability events both hold with probability at least 8. Adding the two bounds yields
log(2) 2|/()
M
log(2)
log(2) 1og(2){11/8)
|Á Malloo S as required.
V
+ (M/))
2K
Z
2K
2K
For (b):Let Y, =
1i B [e
T.. x
Define the intermediate measure
K Σ
(K(A)
Wi [X:EA = K
Y, [(GEA)
Since each Y, has mean 1 and is sub-Gaussian with parameter 72 yields that with probability at least 2
9 Tgg to a37
Bernstein incquality
log(4/8)
VKK Milli S 2 211 v2T) V
2K
Next observe that
px (A) 7
VK (A),
so that
| - vkll S 2 7
1/.
Applying the same sub-Gaussian tail bound to w/Z
E, Y; shows that with probability at least
K
1 8
2
w - < (1- v27) (1= 2/
log (4/5)
7- provided K is large enough that the deviation does not exceed 1/2. The union bound then guarantees both concentration events hold with probability at least 1 8. Finally, the triangle inequality
2K
|Í Mall2 & lA - ukll + |lx - -Hyll
yields the asserted bound.
Lemma 3. Let X be finite set of cardinality M. For each E X, let ((x) be real-valued random variable with mean g(x) [x)(x)) and almost-sut sure bounds 0 < Y(x) < B. Draw N independent copies Y1 (z(2). ..... YN (x of each Y (zx and form the empirical average
g(x)
Y((x).
Then with probability at least 1
log (2g(2M/))
maxlo(x) - g(x) < B
V
xEx
2 N
25

---

Proof. Fix any 2 E A. Since (i(x)..... Yx(x) are ii.d. in [0, B] with mean g(x), Hoeffding's inequality yields, for every >
22 e²
(r(l(()) - g()) e) s 2 exx
B2
Applying the union bound over all M elements of X, we obtain
2N e²
Pr(3x E x lØ(x) g(x) E) I 2M exp To ensure this probability is at most 6, set
B2
2 N 22
2M exp
= 6.
B2
Taking natural logarithms gives
2 N 2
B²
2M
log(2M) = log
é²
log
B
2N
hence
log(2M//)
<= B V 2N N
Therefore, with probability at least 1 - 5, no empirical average deviates by more than e, i...
max g(x) - g(x) Se.
x
Lemma 4. Let X be finite state space and let To be probability distribution on X. that
ExEx To(x) = 1. Fix two nonnegative weight functions q. X - R20 and define
((x) To(
((x:) To(x)
(x) ΣxEx ((2) To(z)
T2(x) Σxex 9(2) To(z)
Suppose there exists Qmin
> 0 and E [0, (min) such that
min ((x) 2 Amins
max ((xx)((())))
- [(x)] < A.
zEX
xEA
Then
2A
4
[T1 Tollx < 171 Tell1 S
Imin
A
Qmin
where the final inequality holds whenever A S Qmin/ /2.
Proof. Set
0₂ = (x) by = ((x) A= Σ O2g B
Σ bz.
Then (xx) = aat/
A and T2
bn/ Since ((x)) 2 qmin and
En To(x) =1
Σ (o)) 2 qmin-
and because |b, - -all < A (z)),
B A|=
Σ bn az)
5 A
To(x)) = =,
so B 2 - A
Qmin
A
>>00 0. Now
[Ti - Tbll1 = Σ
ag
by
B, bAA
(az - -b, + az (B A)
=
A
B
AB
AB
BB
B- -
<
0g
b2l+
Σ
0g
an bzl +
A
B
AB
B
A
A
A + A)
24A 2
<
A
A
4-A
A
A (A-
A)
A(A A)
2AA
2A
2A
A(A
A)
A-A A
Amin A
When A < qmin 2,, Qmin
A > 4min/
2, 80
2A
2A
4A
7 12
Jmin
A
Gmin 2
Qmin
and one may tighten the constants to obtain the stated
22 4min-
26

---

E Algorithmic Details
E.1 Discussion Existing Works
In this section, we will show that the recent works, stochastic control guidance (SCG) [30] and soft value decoding guidance (SVDD) [37], can viewed as special cases of our TreeG-SC.
At timestep & Åt, both SCG and SVDD sample multiple candidate next states from the original diffusion model: æi x. They then select one of these candidates, zς, according to the following strategies:
SCG: k arg max log ply dr (a:)),
SVDD (training-free version): h ~ Cat( Σ wi ), wi (xp()()1(==))))), r()) logp(yl.),
Wi
where # (z+) = (a: ārp (æ,, t)) / Va and a > a temperature parameter.
Within our TreeG-SC algorithm, SCG corresponds setting the active size A 1 and selecting the candidate via ranking, while SVDD corresponds to setting the scoring function fy(-) log p(y -), also with 1, and selecting the candidate via resampling based on soft values.
E.2 TreeG-Gradient Details
We provide the algorithmic details for BranchOut-Grradiet in Module 3.
Module BranchOut- Gradient
trrrachuut-Gradeent 1: Input: æt; L, diffusion model uo. differentiable predictor fy, guidance strength T (optional)
Monte-Carlo sample size N.
2: Compute the gradient guidance: (continuous) g = Vx, (d1) with Φ = ua( t). (discrete) g (d) (a, dd
x4) T
Va,
1 E (
with o Cat (us( i
3: Sample the next state:
(continuous) I++A1 = 79 + Cr,1 + 0,201 + ore with ~ N (0, I). (discrete) iitst ~ Cat (8(1 (d)
.j] exp(ng o R/d (xt. A1).
4: Output: I1+Ai
E.3 More Implementation Details for Continuous Models
For TreeG-SD on the continuous case, we have two additional designs: the first one is exploring multiple steps when branching out a destination state; the second one involves plugging in Spherical Gaussian conStrain(DSGG) from [75]. We present the case A for TreeG-SD on the continuous case as follows while A > is similar.
Notice that the computation complexity for using Niter step to select is: ACmodel AK AANe Naverpreed. The setting of Niter will be provided in Appendix F.I.
E.4 More Implementation Details for Discrete Models
Estimate Va, log (v xz). Since the sampling process of discrete data is genuinely not differen- tiable, we adopt the Straight-through Gumbel Softmax trick to estimate the gradient while combining Monte-Carlo Sampling as stated in (9). The whole process is listed Module
27

---

Algorithm 7 TreeG-SD (Continuous, A 1)
1: Input: diffusion model up, objective function fy. branch out sample size K, stepsize scale Pr. number of iteration Niter
2: 0, Zo ~ Po
3: while do
4: Compute the predicted clean sample @t us ux(e t)
5: Set the branch state æ +- 1
6: for = 1, Ni do
7: Sample x² + PiE'. with & N (0,
8:
Evaluate and select that maximizes the objective: argmax, Ju (2*).
9: Update < x..
10:
end for
11:
if DSG [75] then
12:
Compute the selected direction: 8³ - #1 Rescale the direction: <- vD. E" TET with D dim(a:).
13:
14:
Compute the next state: #++Att = Ct, Bt + c, + 0.5"
15:
else
Get the selected destination state # +- x Sample the next state: E(+Ai 1t + C, + ore with N (0,1)
17:
18:
end if
19:
t 2- t + At
20:
end while
Module Gradient Approximation with Straight-Through Gumbel Softmax.
1: Input: f, diffusion model ua, differentiable predictor fy, Monte-Carlo sample size N, number of possible states S, Gumbel-Softmaa temperature т Sample ét
2:
Cat (uo(2s, t)) [N] with Gumbel Max and represent
one-hot vector:
i arg max(log us (ze, t) + g'),
(27)
g² a S-dimension Gumbel noise where gj Gumbel 1).j e [S]. 3: Since the argmax operation is not differentiable, get the approximation oi with sofumax:
exp((log up (xe, t) 93)/T)
# Σn exp((log up (x,, + 9/)
(28)
4: Feed ii into the fy and obtain the gradient through backpropagation: Vay log (.()).
5: Straight-through Estimator: directly copy the gradient V log fy (0f) to aff. i.e..
Vaj- log fu ( = Vaj log fzi))
6: Since Eq. (28) is differentiable with regard to x,, get Va, logpr xx)) Va, + ENn f((())
7: Output: V.,, log (1r xx)
Experimental Details
All experiments are conducted on one NVIDIA 80G H100 GPU.
F.1 Additional Setup for Symbolic Music Generation
Models. We utilize the diffusion model and Variational Autoencoder (VAE) from [30]. These models were originally trained on MAESTRO [23], Pop1k7 (28), Pop909 [71], and 14k midi files in the classical genre collected from MuseScore. The VAE encodes piano roll segments of dimensions 3 x 128 x 128 into a latent space with dimensions 4 x 16 x 16.
Objective Functions. For the tasks of interest-pitce histogram, note density, and chord progres- sion the objective function for given target is defined as: fy(x) - f (y, Rule(æ)), where Rule(.) represents rule function that extracts the corresponding feature from æ, and E the loss function. Below, elaborate the diffcrentiability of these objective functions for each task:
28

---

For pitch histogram, the rule function Kule-PH() computes the pitch histogram, and the loss function l is the L2 loss. Since Bule-PH(( is differentiable, the resulting objective function f is also differentiable.
For note density, the rule function for note density is defined as: Rule-ND(w>) = Σi= 1 (2; > e)
where is small threshold value, and I(.) is the indicator function which makes Rule-ND() non-differentiable. e is L2 loss. fy is overall non-differentiable.
For chord progression, the rule function Rule- utilizes chord analysis tool from the music21 package [14]. This tool operates as a black-box API, and the associated loss function is a 0-1 loss. Consequently, the objective function f is highly non-differentiabl..
Test Targets. Our workflow follows the methodology outlined by Huang et al. [30]. For each task, target rule labels are derived from 200 samples in the Muscore test dataset. A single sample is then generated for each target rule label, and the loss is calculated between the target label and the rule label of the generated sample. The mean and standard deviation of these losses across all 200 samples are reported in Table 1.
Inference Setup. We use a DDPM scheduler with 1000 inference steps. Guidance is applied only after step 250.
Chord Progression Setup. Since the objective function running by music21 package [14] is very slow, we only conduct guidance during 400-800 inference step.
TreeG-SD Setup. As detailed in Algorithm 7, we use DSG [75], and set Niter = 2 for pitch histogram and note density, Niter for chord progression. The stepsize Pt s =s.0./ st/vi++ of [53,7] 78), with = 2 for pitch histogram, & = 0.5 for note density and 8 = 1 for chord progression.
F2 Additional Setup for Small Molecule Generation
Due to lack of differentiable off-the-shelf predictors, we train suite of regression models f(x) on clean data J1 following the same procedure described in Nisonoff et al. [45] test the efficacy of our gradient-based method TreeG-G on the targets QED, SA, DRD2, and Nr. The same predictor is applied for all compared training-free guidance methods (TreeG, TFG-Flow, and SVDD).
For molecule optimization targets, QED, SA, and DRD2, directly use the pretrained model f() as the objective function fy without setting any target values and generate 500 samples within 1000 denosing steps. As stated in [45], generated SMILES sequences may not yield valid molecule structures. Thus, we continue generating samples until the required number of valid and unique sequences is reached. For these three targets' results in Table A 1, K
for TreeG-SC; A = 1, = 200 and A = 2, K = 8 for TreeG-SD. To ensure comparable runtime between baseline models and TreeG, we set N 200 for TFG-Flow and K 2 for SVDD with a temperature parameter of 0.1. Monte Carlo sample size for estimating (y xx) in TreeG-Gis N = 30 (Eq. (9)) while TRe and SVDD use 10.
We use QuickVin2--GPU-2. to evaluate the binding affinity of generated molecules to protein 5btlb following [76]. The original scores DS are normalized as max(- DS, 0) for maximization. Because using oracle docking scores as guidance signals is computationally expensive, we only generate 100 sequences in 200 inference steps for comparison. Since the docking measurement is non-differentiable, TreeG-G and DG
not applicable. In Table 2, A 1, K 8 for TreeG-SC; A = 1, K = 200 and A = 4, K = 8 for TreeG-SD; N 200 for TFG-Flow; K = 8, a 0.1 for SVDD. Monte Carlo sample size for Pr xx) estimation in TreeG-SC and SVDD N = 5.
While for N, which is optimized towards specific target values, we adopt (x)
f()))
20
with a learned during the training of fz) We report the results on 1000 generated valid unique sequences. In Table AA 1, = 4 for TreeG-SC:
1,K 200 and A 2, K 8 for TreeG-SD; N = 200 for TFG-Flow; K = 2, a = 0.1 for SVDD. Monte Carlo sample size for (y 2x) estimation in TreeG-SC, TreeG-G, G, and SVDD N 30.
F33 Additional Setup for Enhancer DNA Design
We test on eight randomly selected classes with cell type indices 0, 2, 33, 4, 16, 5, 68, and For simplicity, we refer to these as Class I through Class 8.
29

---

Table Computation time per basic unit during small molecule generation (ms)
Guodd
CQED Okeesiss
Cosciiy Oljectire
Molocule 0.038
2.0c44
390
We set the Monte Carlo sample size of TreeG-G and TreeG-SC as = 20, and N = 200 for TFG-Flow. For SVDD, we the sample size to 16 and the temperature parameter a 0.01.
F.4 Experimental Setup in Figure 2
In Figure 2, (a) shows TreeG-SD applied the note density objective in symbolic music generation; (b) shows TreeG-SD used for QED optimization in small molecule generation; and (c) shows TreeG-G applied to Enhancer DNA design.
G Additional Experiment Results
G.1 Additional Results for Symbolic Music Generation
G.1.1 Additional Infomation for Table
For the results in Table 1, Table presents a comparative improvement over the best baseline. We provide the inference time of one generation in Table 8 for results in Table 1. TreeG-SD, SCG, and SVDD use ground-truth objective functions for evaluation, resulting in relatively long inference times for Chord Progression but achieving higher optimization performance. In contrast, TDS relies gradient- based guidance through a surrogate neural network predictor, which reduces inference time the cost of optimization effectiveness.
Table 8: Improvement of TreeG-SD in Music Generation.
Table 9: Time (s) per sample for
Task
Best Baseline
TreeG-SD
Loss Reduction
results in Table 8.
PH
0.0010 + 0.0020 (DPS)
0.0002 + 0.0003
80%
Task TDS
SCG
SVDD
TreeG-SD
ND
0,134 + 0.533 (SCG)
0.142 + 0.423
-5.97%
PH 306
194
194
203
CP
0.347 + 0.212 (SCG)
0.301 + 0.191
13.26%
ND 308
204
Avg
29.01%
CP 305
7267
7267
6660
G.1.2 Scalability
We conduct experiments scaling the active size A and branch-out size for TreeG-SD and TreeG-SC. Increasing either A or K enhances the performance, as demonstrated in Figure 5. Figure shows the trade-off between A and K with fixed A K.
Hitch Hetogram lass
20-7
Loos
oggraam
note Density
Rithh Hidogron
20
20
Branch Out Size
Branch Out Sze
Branch Out Size
Branch Out Size
(a) TreeG-SD for ND
(b) TreeG-SD for PH
(c) TrecG-SC for ND
(d) TreeG-SC for PH
Figure 5: Scaling Behavior with Fixed Active or Branch-Out Size on Music Generation.
Compute)
Compute 2
Compute 1
Pitch Hestogran am Loss
Compune
Note Density
Hetogram
Density
20.
20-4
Size
(a) TreeG-SD for ND
(b) TreeG-SD for PH
TreeG-SC for ND
(d) TreeG-SC for PH
Figure 6: Trade-off off between Active Set Size A and Branch-out Size K on Music Generation.
30

---

Scaling Effeet on Performance while Maintaining Quality. While the product A x K gives an indication of total computation, different combinations A and can lead to varying computational costs, even when x K is held constant, as shown in the computational complexity analysis in Table 4. We report the actual running time for generating one frontier from Figure (a) and Figure (b) in Table 10. The results demonstrate that the optimization exhibits scaling effect with computation time, while still maintaining high-quality performance.
Table 10: Performance when Scaling Inference Time. Results are for the Optimal (A, K) with Fixed * K for TreeG-SD.
Note Density
Pitch Histogram
Time(s)
Loss |
OA
Timels)
Loss
16.7
2,486 = 3.530
0.830 + 0.016
16.7
0,0180 = 0.0100
0.812 0.012
43.1
0.029
0.827
0.826
0.0022 0.0021
0.889
71.8
0.231
0.422
0.823 + 0.045
65.3
0.0088 + 0.0008
0.853 0.011
130.7
0.113 = 0.317
0.831 + 0.023
118.6
0,0005 + 0.0008
0181100015
251.9
0.198
0.843 0.012
+ 0.000G
0.016
G.2
Additional Results for Small Molecule Generation
G.2.1 Additional Results for Table 2.
As shown Tables 2 and 11, SVDD achieves the best performance among the baselines for the targets QED, SA, DRD2, and Docking score while DG performs best in guiding toward the N, target. On average, our method yields a 26.38% relative improvement over the strongest baselines. According to the metrics TS (Table 2) and NLL per token (Table 12), improved target optimization performance may come at the expense of diversity and quality.
Table 11: Relative performance improvement of TreeG-SC compared to DG, TFG-Flow, and SVDD. For N,, we average MAE over target values before comparing different methods. The relative improvements over the strongest baselines are bolded.
Method
QED f
SA
DRD2 t Docking 1
N, MAE
DG
28.6%
354%
-21.6%
TFG-Flow
32.0%%
13.7%
803%
10.2% 1.71%
-69.0%
SVDD
19.5%
11.4%
77.7%
-75.5%
Table 12: Supplementary results for Table 2: NLL (L) for small molecule generation.
Method
Docking
N;
No Guidance
0.70 - 0.39
0.70 + 0.30
0.70 + 0.31
0:68 + 0:39
0.73 = 0.41
DO TFG-Flow
0.42
0.73 a 0.43
0.70
0.56
SVDD
0.71 0.1
0.70 = 0.40
0.67 0.38
1:21 + 0.54
0.81 0.37
TreeG-SC (A=I)
0.83 0.46
0.58 1 0.31
0.39
1.13 1: 0.54
1.02 0.40
TreeG-G (A-1)
0.30
Tree--DD (A=1)
1.13 0.51
0.83 0.42
1.09 1 0.52
1.14 0:47
1.22 0.10
TreeG-SD (A>11)
1.14
0.70 0.36
0.94 -t 0.47
1/08 + 0.49
1.13
Table 13: Supplementary results for Table 2: N e {0, 1, 2, for small molecule generation.
Matedl
MAF
N-1.1
95
N1.1
T5
Gastannce
0.12
1.40
1112
1.005
0112 1:00
0L11
01644-.11
0:39
0:30
031 4-03
0-64-044
0.0.400
6-337
0.13 0.
0.90
0.135
0.15
TEC-FTW
0.24-0..7
0 D34
0:
D58 1-039
0.00 0.55
011 0.
0.31 0.995
0:00
0.11
SVDD
0.20
0.51
031
2.30
0.33
0142110
0190 8334
BJt 1007
0302
012
CAN 12
TixK--0 (ie))
0.33 0:43
0.70 2200003
0:1
0.13 2012
0:12:000
0.12::0:02
0:
112-041
0:1
Tree-
0.68-0.1
0:3-20022
0.12
G.2.2 Scalability
We demonstrate the scaling laws for TreeG-SC and TreeG-SD in Figures 7 and 8. Increasing computation time could boost guidance performance, i.e., lower mean absolute errors higher property values. The computation of the Docking objective function with the oracle tool dominates
31

---

Table 14: Supplementary results for Table 2: N {4,5, 6) for small molecule generation.
Mathod
MAEL
NLL.
- 75
NLL.
No Gelffonee
8.37
0013
00.41
745--1.10
1019-4.0000
1:55
1110
0:75 -0:00
DG
0:
0.12+:300
0.70 0..9
0:102:0:00
076
843 0.51
0:3.
0.72 0..5
1:008
6:08
Tree (Act)
685 0.29
0.13 9.0
0.00 1033
B.5 8.5
0.12 0.08
1.00 1.03
0:00
1:47
0.12 6.85
1.06 0.70
TraxG-G (A
10435
0:36 (1:0)
1:35
1.0
1.02
0.77 0.33
100
TuxG
0.30
0.12
0..55
0.30
0:12
1.48
the overall runtime (Table 7). Thus, maximizing Docking score may require substantially increased
inference compute (Figure 8), highlighting the inherent trade-off between effectiveness and efficiency.
Tea
Monn Atsskree
20 13
20
20 25 31 3r 15
Computatin
14
12
Figure 7: Small Molecule Generation: Scaling Law TreeG-SC. From left to right, the targets are N = 3, No- = 6, SA, and Docking score. The time-axis for Docking score is in logarithmic scale.
MeNO Abwoo..s te frme
24 12. 12'
Tine 50)
320 133 Comprttioon Time.)
13 B2 XA 2E TA
Compatatoo Time
Figure 8: Small Molecule Generation: Scaling Law of TreeG-SD, From left right, the targets are N = 1, No = 5, QED, and Docking score. The time-axis for Docking score is in logarithmic scale.
G.3 Additional Results for Enhancer DNA Design
G.3.1 Full Results of Table 3
Additional results of guidance methods for Class 4-8 are shown in Table 15 and Table 16. For both DG and our TreeG-G, we experiment with guidance values y 21, 10, 20, 50, 100, 200] and compare the highest average conditional probability across the eight classes. On average, TreeG-G outperforms DG by 18.43%.
Table 15: Supplementary results (Part 1): Classes 4-6 for enhancer DNA design.
Method (mreagth
Prob +
Class
NLL 1
Div
Prob
Class 5
NLL.
Div
Prob
Class 6
NLL
Div
Guidance
0.0GB
1.311
0.038
373
0,005
0.038
0.037
0.115
0.038
DG
0.585
1,255
0.043
365
0.466
0.976
1:266 1: 0.050
373
0.385
0.334
1.266
0.057
364
200
0.004 1: 0.384
1.250
0.045
309
0.199
d: 0.288
1.279 1: 0.053
373
0.104
0.255
1,281
1: 0.058
398
TRG Flow
200
0.015 4: 0.083
1.389
0.012
375
0,088
d: 0.008
1.386 4: 0.012
375
0.003 d: 0.104
1.394 0,012
375
SVDD
0.107 + 0:264
1.311
0.035
374
0. 0.142
0.240
1. 1,283 :: 0.030
374
0.124
0.200
1,292 : 0.012
S73
0.088
365
1,109
372
0.250
00.292
1.052 0.087
TreeG-G
359
01.811
0.232
0.074
370
0.543 0.426
1.01.G 0.189
374
0.364 0.432
1.104 0.180
G.3.2 Scalability
K as a Computation Reference. We use * K as the reference metric for inference time computation in TC and TreeG-G, both employing Saanchuut-Cureen The corresponding inference times are shown in Figure 9, measured for batch size of 100. Combinations of (A, K) that yield the same A K value exhibit similar inference times. We exclude the case where K = as does not require evaluation and selection, leading to shorter inference time practical implementation.
32

---

Table 16: Supplementary results (Part 2): Classes 7-8 for enhancer DNA design.
Class 7
Class NLL
Method (strengsh ?)
Prob
NLL
Prob
Div T
No Guidance
0.010 = 0.065
1.311 +: 0.038
373
0.013 + 0,073
1,311 # 0.038
373
20
0.693
0.316
1.281 + 0.084
0.009 0.350
1.224 #: 0.039
372
DG
100
0.475
0.398
1.199 4: 0.061
364
01.000 4: 0.342
1.191 4: 0.057
372
0.453
1,208
371
TFG-Flow
200
0.001
0.015
1,376
2: 0.015
375
0.006 = 0.065
1.377 4: 0.011
375
SVDD
0.136
0.038
373
20
0.536
0.335
0.720 + 0.155
307
0. 0.159 #: 0. 233
1.011 :: 0.136
366
Tree-GG
0.740
0.365
0.723
0.250
343
0.413 0.412
1.104 1: 0.126
373
0.457
0.205
Computatton Time (s)
Computtation 16)
109
100
2
Branch-out Size
and Branch-out
Figure 9: Inference Time for (A, K)) Combinations (Left: TreeG-SC; Right: TreeG-G) in DNA
Enhancer Design. Combinations with the same product A x show similar inference times.
We provide the scaling law of TreeG-G different guidance strengths in Figure 10. We also provide the scaling law for TreeG-SC in Figure 11.
Class Probabits
Class Probabiilty
Class Prbuablity.
0.90
0.96
0--
0.34
544
Tree-G
Tree--G
106
150
232
150
200
200
150
230
Computation Time (6)
Computation Time (5)
Computation Time (4)
Computation Time (4)
0.50
Class Proaabitty
0.5
Probabiltty
Class Probability
0.50
0.54
04
Achiv
Affias
0.3
Branch Out Size
Branch Dut Size
Branch Dut Size
Branch Out Size
0.50
Cless Probubiity
Probabilky
Class Probabiitty
0.30
Cayssoos
2.3
Sx R
Active Set Size
Active Set Size
Active Set Size
Active Set Size
Figure TreeG-G for Enhancer DNA Design. Top row: Effect of scaling on inference time. Middle row: Impact of increasing the active set size A or branch-out size K. Bottom row: Trade-off between and K with fixed compute K. Columns from left to right correspond different guidance strengths: y = 5, 10, 20, 200 (results shown for Class 3).
33

---

05
07
0.8
Probabiing
3.5min Class Proto Protobbliig Billtt
22-
02
Closs
Tree SC
FeeG SC
Teee SC
TreeG 50
55 130
27 250
50
230
330
50
100
200 250
Computation Time (5)
Computation Time (5)
Computation Time (5)
Computation time (s)
Acivel
Acive
0.8
Adbes
Probabbbiy
Oloss Probodooo
1.3
C1855
6--
Branch Size Size
Branch Out Size
Branch Out Size
Branch Out Size
57
Compute
0.8
Compate
Class Prod
24
Probabiityy
25
0.3
22-
Active Set Size
Active Set Size
Active Set Size
Active Set Size
Figure 11: TreeG-SC for Enhancer DNA Design. Top Effect of scaling inference time. Middle row: Impact of increasing the active set size or branch-out size K. Bottom row: Trade-off between A and K with fixed compute A K. Columns from left right correspond Class I to 4.
H Ablation Studies
H.1
Symbolic Music Generation
For TreeG-SD, we ablation on Nue (detailed in Algorithm 7). As shown in Table 17, the loss decreases when Niter increases. However, increasing Niter also leads higher computation costs. Here's 's trade-off between controllability and computation cost.
Table 17: Ablation on Niter of TreeG-SD.
Nar
Loss 1 (PH)
OA (PH)
Loss 1 (ND)
OA (ND)
0.0031 = 0.0037
0.733 : 0.021
0.207
0.810
0.0008
0.018
0.400
0.19
4
0.0005
+ 0.0000
0.786 0.015
0.139 0.319
0.830 = 0.029
H.2 Discrete Models
Ablation on Taylor-expansion Approximation. As shown in Table 18, using Taylor-expansion to approximate the ratio (Eq. 10) achieve comparable model performance while dramatically improve the sampling efficiency compared to calculating the ratio by definition, i.e. TreeG-G-Exact.
Ablation on Monte Carlo Sample Size N. As shown in Table 19, increasing the Monte Carlo sample size improves performance, but further increases in N beyond a certain point do not lead to additional gains.
Table 18: Ablation on Taylor-expansion Approximation. The performances are evaluated on 50 generated samples.
N,
Method
MAR
TS
Time
MAE
TS.
Time
TreeG-G
0.24 0.76
0.13 + 0.02
2.4min
0.02 = 0.14
0.022
TreeG-G-Exuct
0.00=0..00
0.14 4 0.03
356.9min
0.02 0.14
0.13 0.02
345.2min
34

---

Table 19: Ablation on Monte Carlo Sample Size N. The performances are evaluated on 200 generated samples.
N
N.
=2
N,
MAE
TS1
MAE
1
0.47
1 1.12
0.12 0.02
0.65 1: 1.37
0.12 1 0.00
0.97
10
0.17
0.66
0.12 1 0.02
0.20
0.76
0.12 1 0.002
40
0.10
= 0.00
0.12
0.29 1.01
0.13
0.00
Table 20: Ablation Selection Choices in TreeG. TreeG-SC and TrecG-SD evaluated on 500 and 100 generated samples respectively. t means temperature used for resampling weights. lower leads resampling closer to ranking.
TreeG-SC (K
TreeG-SD (K 16) 4
Choices
QED
TS
QED
Ranking
0.79 +090+00.00 0.12
0.12 0.02
0.76 + 0.12
0.12 0.02
Sampling (f 0.1)
0.71 0.17
0.13 0.02
0.67 0.19
0.12 0.02
Sampling (1 0.5)
0.64 1 0.19
0,12 1: 0.02
0.67 0.17
0.11 1 0.02
H.3 Selection Choices in Alg.1
We compare two selection choices, i.e., ranking and resampling, in Alg. I on small molecule generation with QED as the target. For both TreeG-SC and TrecG-SD, selection by ranking produces better guidance performance compared to selection by resampling (Tab. 20).
35

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: The introduction (Section 1) includes a paragraph "Contributions" together with the abstract, clearly reflecting the paper's contributions and scope.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
We discuss the limitations in Appendix B.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors encouraged to create separate "Limitations" section in their paper.
The paper should point any strong assumptions and how robust the results are violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and prool's
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
36

---

All the theoretical results Theorem 1, Lemma and Theorem 2 provide the full set of assumptions, and the correspond proofs are in Appendix D.I, Appendix D.2 and Appendix D.3, respectively
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
The experiments are described in Section 6, and the details are provided in Appendix E, Appendix and Appendix
Justification:
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
37

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification:
Code available https://giihub..om/ykaau 23/UnniTreeG.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https:
/ttpp.cccppbblll/ http:ccccpppccccccccceeccccccccc httpppullliuulleeespeppppppepael guides/ CCodeSumi ssi ssisssoolooooooooo oonooiiyyyyooooooooomoooomiiimlp for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The experimental details are provided in Appendix E, Appendix and Ap- pendix G.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to a level of detail that is necessary appreciate the results and make sense of them.
The full details can provided either with the code, in appendix, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: The experiments that support the main claims of the paper provide error bars, shown in tables, such as Table Table 2 and Table 3.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
38

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The information on the computer resources is included in Appendix F.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make it into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: http://tpp...ppppiii///////c/eet htwplii///hiiiuiiiiiii cstuideless
Answer: [Yes]
The research adheres to guidelines and principles outlined the NeurIPS Code of Ethics, including considerations for fairness, accountability, and transparency. Ethical practices were maintained throughout the study, ensuring compliance with all applicable standards.
Justification:
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative socictal impacts of the work performed?
Answer: [Yes]
Justification:
We discuss the social impacts of this paper in Appendix B.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
39

---

Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation, generating fake profiles, surveillance), faireess considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied partieular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there negative societal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification:
The paper poses no such risks.
Guidelines:
The answer NA means that the paper poses such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: All creators and original owners of assets used in this paper are properly credited. The licenses and terms of use explicitly mentioned and respected according to their guidelines.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
40

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi thcode. com datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification:
We will release our code and models along with detailed documentation.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing or research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
41

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core methodological development in this research does involve LLMs significant, original, non-standard components.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM policy htopp:://neuris... httppp////orrpss.cooooeeeeeeeeee /20p://p//.//oooeeeecc////////// for what should or should not be described.
42


Reviews:
[{"review_id": "JbOVMspdeh", "reviewer": "Reviewer_5QYR", "summary": "TreeG reframes training-free guidance as a tree-search over inference paths, enabling diffusion and flow models to optimize non-differentiable or discrete objectives without extra training. Three instantiations( TreeG-SC, TreeG-SD, and TreeG-G) are theoretically supported and outperform prior guidance methods on symbolic music, molecule, and DNA generation, while exhibiting a clear compute-versus-performance scaling law. In summary TreeG is a well-motivated step toward gradient-free control of diffusion and flow models, offering both provable guarantees and tangible empirical gains. Broader domain validation, ablations, and alignment between theory and implementation would be beneficial before claiming universal guidance capability.", "questions": "Could the authors elaborate on the:\n\n* Selection criteria for the target tasks? What is the argument for universality over this specific set?\n\n* Theoretical assumptions (Gaussian data, linear objectives) may limit generality. Can you make more explicit the assumptions in which the model should perform?\n\n* Possible reproducibility and transferability gap across tasks due to many hyper-parameters (e.g., Monte-Carlo N, temperature α) tuned per task without ablation. Can you comment on this?", "limitations": "Yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n\n* Consistent empirical wins across three distinct domains of application.\n\n* Sensible supporting empirical analysis.\n\n* Positive practical implications across widely relevant application domains\n\nWeaknesses\n\n* Domain coverage: three synthetic/benchmark tasks. Lack of an argument towards the selection criteria for the target tasks.", "was_revised": true, "final_justification": "Authors responded the main questions. The scores remained the same (overall positive) as these were clarifications questions.", "rebuttal": "Thank you for your positive feedback on our work! We address your questions below.\n\n>**Q1:** Selection criteria for the target tasks? What is the argument for universality over this specific set?\n\n\n**A1:** We selected tasks that pose **non-differentiability challenges**, which our methods are designed to address. Specifically, this includes continuous diffusion models with *non-differentiable objectives* (e.g., symbolic music generation) and *discrete diffusion models* (e.g., molecular design and enhancer DNA design). These tasks were chosen because they represent diverse yet common instances where nondifferentiability arises, demonstrating the broad applicability of our approach.\n\n\n\n\n>**Q2:** Theoretical assumptions (Gaussian data, linear objectives) may limit generality.\n\n\n**A2:** \n- **On the necessity of assumptions**: From a theoretical perspective, the linear-Gaussian case is not trivial but rather fundamental. The search mechanism inherently disrupts the reverse dynamics of the unconditional diffusion model, making it analytically intractable to rigorously characterize the output distribution or derive end-to-end sample complexity bounds without additional structure. Recent work (e.g., [1] Marion et al., 2024) also relies on Gaussian assumptions to establish rigorous guarantees for guided diffusion. Therefore, this assumption should be considered reasonable.\n- **On broader applicability**: While our theoretical analysis adopts Gaussian-linear assumptions to enable rigorous proofs, our experiments explicitly verify that the proposed approach performs well in substantially more complex settings, with non-Gaussian data distributions and nonlinear objectives, demonstrating that the method effectively generalizes beyond the assumptions used in the theoretical framework.\n\n\n[1] Pierre Marion et al. Implicit diffusion: Efficient optimization through stochastic sampling. arXiv preprint arXiv:2402.05468, 2024.\n\n\n>**Q3:** Possible reproducibility and transferability gap across tasks due to many hyper-parameters (e.g., Monte-Carlo N, temperature) tuned per task without ablation.\n\n\n**A3:** We would like to emphasize that **we have already conducted ablation studies** on hyperparameters such as the Monte-Carlo sample size and the resampling temperature, as reported in **Appendix H (Tables 17 and 18)**. These provide transferable insights across tasks:\n\n- Monte-Carlo sample size $N$: Increasing $N$ improves performance up to a point, after which further increases no longer yield significant gains. Thus, our experience is to select a larger $N$ within the available computational budget.\n- Resampling temperature: Our ablation shows that ranking-based selection (temperature = 0) consistently outperforms resampling. Therefore, in our main experiments, we adopt ranking, which also eliminates the need to tune this hyperparameter.\n\n\n\n---\n**We sincerely hope that our responses can address your concerns, and we would greatly appreciate it if you would consider raising your score of our work to a *clear accept* given the responses.**"}, {"review_id": "ZMAPx9095I", "reviewer": "Reviewer_nJDF", "summary": "This paper presents a training-free diffusion guidance algorithm applicable to general objectives with non-differentiable rewards and discrete data distribution. The proposed algorithm (TreeG) is based on a tree search along the diffusion sampling trajectory. The authors first state a generic tree-search framework (Section 4), and instantiate TreeG with different design choices (Section 5). The TreeG algorithm is proved to approximate the true posterior distribution closely with resampling. Experimental results on generating symbolic music, small molecules and enhance DNAs show clear advantage of TreeG against existing guidance methods.", "questions": "- Could the authors also comment on the scalability of TreeG in terms of the dimensionality of the data distribution? Also, is there any theoretical insight on how tree search-based algorithms perform when the objective/reward functions are sparse in the search space, i.e., when most of the samples have low rewards?", "limitations": "Yes, the authors address limitations in Appendix B.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength:\n\n- This paper provides a generic search-based framework for guiding score-based models for general objectives and using both continuous and discrete diffusion models.\n- The discussion that connects existing methods to TreeG by showing them as special cases of TreeG is inspiring.\n- The performance of the TreeG algorithm is rigorously guaranteed.\n- Experimental results show advantange of TreeG compared to existing methods. The experiments encompass different tasks in different domains. The scaling ability of TreeG also looks promising.\n\nWeakness:\n\n- Despite being training-free, the computational cost of the tree search-based algorithm seems to be high. A comparison or discussion on computational efficiency of this inference-time method compared to fine-tuning methods (e.g., RTB[1]) is missing.\n- While TreeG generate samples with better targeted objectives in the experiments, the distributional similarity is sometimes worse (e.g., when increasing the guidance strength in DNA design tasks). It is unclear whether the generated samples satisfy the conditional distribution $p(x|y)$ by only looking at the reported metrics. \n\n[1] Venkatraman et al. Amortizing intractable inference in diffusion models for vision, language, and control. NeurIPS 2024.", "was_revised": true, "final_justification": "My original concerns on this paper are resolved, and I have updated my assessment of this paper accordingly.", "rebuttal": "Thank you for your positive feedback on our work! We address your questions below.\n\n\n>**Q1:** Could the authors also comment on the scalability of TreeG in terms of the dimensionality of the data distribution?\n\n**A1:** Thank you for the question. We provide theoretical insights: for higher-dimensional data, a larger branch-out size is required. For example, for TreeG-SC, Theorem 1 gives\n$$\nK = \\Theta\\left(\\frac{\\log (|\\mathcal{X}|/\\delta)}{\\varepsilon^{2}}\\right),\n$$\nhere $|\\mathcal{X}|$ is the cardinality of the discrete data space. Since $|\\mathcal{X}|$ typically grows exponentially with dimensionality, it requires correspondingly larger $K$ to achieve the same optimization tolerance $\\varepsilon$ in higher-dimensional spaces. Similar conclusion holds for TreeG-SD.\n\n\n>**Q2:** Is there any theoretical insight on how tree search-based algorithms perform when the objective/reward functions are sparse in the search space, i.e., when most of the samples have low rewards?\n\n\n**A2:** In our proof of Theorem 1 (line 682 in Appx.D.1), we show the branch out size size depends on the ratio between the maximum and minimum of the objective function:\n$$\nK = \\Theta\\left(\\frac{B^2_\\max}{B^2_\\min} \\cdot \\frac{\\log (|\\mathcal{X}|/\\delta)}{\\varepsilon^{2}}\\right),\n$$\nwhere $B_\\max = \\sup \\exp (f_y(x))$ and $B_\\min = \\inf \\exp (f_y(x))$. When the objective function is sparse (i.e., most samples have very low rewards), the ratio $B_\\max / B_\\min$ becomes large. Consequently, the branch-out size $K$ must also be larger to adequately explore the space and locate high-reward regions.\n\n\n\n>**Q3:** Despite being training-free, the computational cost of the tree search-based algorithm seems to be high. A comparison or discussion on computational efficiency of this inference-time method compared to fine-tuning methods (e.g., RTB[1]) is missing.\n\n**A3:** Thank you for the comment. As discussed in Sec. 6.4 (Table 4), the computational cost of our method primarily comes from querying the pre-trained diffusion model and evaluating the objective function, both of which are also required by fine-tuning methods. However, unlike our inference-time approach, fine-tuning methods (including RTB [1]) incur substantially higher cost due to additional training steps and many more model queries. Thus, our TreeG remains significantly more efficient than training-based approaches.\n\nWe thank the reviewer poining this out and have clarified this comparison with fine-tuning methods in the revised version.\n\n\n\n>**Q4:** While TreeG generate samples with better targeted objectives in the experiments, the distributional similarity is sometimes worse (e.g., when increasing the guidance strength in DNA design tasks). It is unclear whether the generated samples satisfy the conditional distribution $p(x|y)$ by only looking at the reported metrics.\n\n\n**A4:** We appreciate the valuable feedback. To better evaluate how well the generated samples satisfy the conditional distribution  $p(x|y)$, we have introduced the **Negative Log-Likelihood (NLL)** as an additional metric.\n\nFrom Bayes’ theorem:\n$$\np(x|y) \\propto p(x) \\cdot p(y|x),\n$$\nwhere the two terms can be measured as follows:\n- Measuring $p(x)$: This captures the **naturalness** of samples. We use the Negative Log-Likelihood (NLL), a widely adopted metric in discrete diffusion and flow-based generation [2,3]. The likelihood is computed using the ELBO of the pretrained (discrete) diffusion model.\n- Measuring $p(y|x)$: This reflects the **optimization effectiveness**. We use the Target Class Probability, as provided by the oracle classifier, which we already report.\n\nResults based on these complete metrics are shown in the table below.\n\n|Method (strength)| Class 1| | Class 2 | | Class 3| |\n|:-|:-|:-|:-|:-|:-|:-|\n||Prob(↑)|NLL(bits/dim↓)|Prob(↑)|NLL(↓)|Prob(↑)|NLL(↓)|\n|No guidance|0.021±0.079|0.667±0.015|0.008±0.052|0.667±0.015|0.007±0.053|0.667±0.015|\n|DG ($\\gamma=20$)|0.359±0.188|0.625±0.016|0.627±0.340|0.615±0.022|0.693±0.264|0.636±0.019|\n|DG ($\\gamma=100$)|0.372±0.237|0.600±0.034|0.571±0.356|0.587±0.032|0.173±0.256|0.606±0.036|\n|DG ($\\gamma=200$)|0.251±0.171|0.577±0.044|0.350±0.351|0.587±0.037|0.064±0.143|0.603±0.033|\n|**TreeG-G** ($\\gamma=20$)|0.236±0.178|0.615±0.034|0.313±0.343|0.596±0.057|0.247±0.280|0.486±0.054|\n|**TreeG-G** ($\\gamma=100$)|0.509±0.242|0.516±0.040|0.915±0.154|0.471±0.040|0.745±0.217|0.399±0.042|\n|**TreeG-G** ($\\gamma=200$)|**0.560±0.258**|0.518±0.042|**0.951±0.110**|0.454±0.035|**0.894±0.136**|0.415±0.043|\n \n\nAs for the previously reported Fréchet Biological Distance (FBD), it measures the Gaussian distance between embeddings of generated DNA sequences and those of training data within the target class. Upon reflection, we find this metric problematic: it implicitly treats the training data within target class as the sole “ground truth,” discouraging the generation of *novel yet valid* DNA sequences that maintain naturalness but deviate from the training samples with the target class. For instance, a newly generated sample belonging to class 1 may legitimately appear closer to samples from class 2, yet FBD would penalize it.\n\nThis limitation unnecessarily penalizes valid solutions. Therefore, we omit FBD in our updated evaluation, as Target Class Probability and NLL, together with reported diversity, already provide a more comprehensive and principled assessment.\n\n\n\n*Reference*\n\n[1] Venkatraman et al. Amortizing intractable inference in diffusion models for vision, language, and control. NeurIPS 2024.\n\n[2] Austin et al. Structured Denoising Diffusion Models in Discrete State-Spaces.\n\n[3] Uehara et al. Reward-Guided Iterative Refinement in Diffusion Models at Test-Time with Applications to Protein and DNA Design.\n\n\n\n\n---\n**We sincerely hope that our responses can address your concerns, and we would greatly appreciate it if you would consider raising your score of our work to a *clear accept* given the responses.**"}, {"review_id": "MoNMGizjCt", "reviewer": "Reviewer_cSpQ", "summary": "In this paper, the authors proposed tree search methods for inference time (black-box) guidance for both diffusion models and flow models(discrete cases).  Two schemes are proposed for tree branch expansion and value function estimation.  The authors further provide theoretical bounds of the difference between the algorithm-induced distribution $\\hat{\\mathcal{T}}$ and target conditional transition distribution $\\mathcal{T}(\\cdot | \\boldsymbol{x}_t,y )$ for both schemes.", "questions": "Q1.  Please provide more discussion and explanation about Theorem 2 for the discrete case and the assumptions of the error bound for the continuous case.\n\nQ2. If possible, please provide comparisons against baselines regarding query efficiency.\n\nQ3. If possible, please provide evaluations on the Vina Docking score and image generation tasks.", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "**Strengths**\n\n1. This paper provides tree search methods for inference time (black-box) guidance for both diffusion models and flow models(discrete cases).  Although [Huang et al. 2024] proposed a method that selects the best one at each time t for inference time  guidance, this paper generalizes it well for both diffusion models and flow models.  \n\n2. This paper provides theoretical error bounds of the difference between the algorithm-induced distribution $\\hat{\\mathcal{T}}$ and target conditional transition distribution $\\mathcal{T}(\\cdot | \\boldsymbol{x}_t,y )$ for both cases. It directly reveals the relationship between the approximation error and the tree Branch-Out size $K$. \n\n\n**Weaknesses**\n\n1. Theorem 2 for the discrete case is a bit weird.  It seems that given the same Branch-Out size $K$, the high-dimensional case can achieve a much smaller error $\\epsilon$ compared with the low-dimensional case. Or equivalently, to achieve a fixed error $\\epsilon$, the high-dimensional case requires a smaller  Branch-Out size $K$ compared with the low-dimensional case. \n\n2. The assumptions of the error bound for the continuous case are too strong. The requirement of the data follows a Gaussian distribution, and the objective function is linear is too restrictive. If we already know this nice form, we do not need to take diffusion models. We can easily start from the Gaussian; other techniques may get better results.  \n\n3. In the black-box guidance area, usually, the main challenge is the query efficiency. For example, in drug discovery tasks, the number of wet lab experiments or high-computation-cost docking evaluations is the bottleneck. In targeted image generation tasks, the number of collections of users' preferences or simply LLM API calls for scoring is the bottleneck. However, no comparison against baselines regarding query efficiency is evaluated in the current draft, which is not convincing enough. \n\n4.  It seems that all the evaluations in the experiments are on simple tasks.  In the drug discovery area, the Vina Docking score is usually more challenging to optimize compared with QED and SA. The QED and SA are easily led to overfitting. However, evaluations regarding the Vina Docking score are missing.  In addition,  no comparison is performed on the image domain. The image target generation tasks are high-dimensional, which makes them more challenging for the value function estimation. \n\n5. Part of the math or symbols are not clear enough.\n\n- The $R_t$, $R_t^{(d)}$ and $R_t( x_t, j | x_1)$ for the flow models are not well explained.  Is it a typo for the symbol on Line 117?\n\n- The distribution $\\hat{\\mathcal{T}}$  depends on the time t, but the error bound in the Theorem does not show this explicitly. \n\n6. Some prior related works on the inference-time black-box guidance for diffusion models are not discussed.  I list a few of them below. \n\n[1] Tang et al. Tuning-free alignment of diffusion models with direct noise optimization. arXiv:2405.18881, 2024.\n\n[2] Tan et al. Fast Direct: Query-Efficient Online Black-box Guidance for Diffusion-model Target Generation. ICLR 2025.\n\n[3] Lyu et al. Covariance-adaptive sequential black-box optimization for diffusion targeted generation. arXiv:2406.00812, 2024.", "was_revised": true, "final_justification": "In this paper, the authors proposed tree search methods for inference time (black-box) guidance for both diffusion models and flow models(discrete cases).  Two schemes are proposed for tree branch expansion and value function estimation.  The authors further provide theoretical bounds of the difference between the algorithm-induced distribution $\\hat{\\mathcal{T}}$ and the target conditional transition distribution $\\mathcal{T}(\\cdot | \\boldsymbol{x}_t,y )$ for both schemes. The authors cleaned up the typos and addressed most of my concerns.", "rebuttal": "Thank you for your positive feedback on our work! We first present new experimental results, followed by responses to the remaining concerns.\n\n---\nWe added **new experiments on Vina Docking score** (protein: 5ht1b). Our proposed TreeG-SC outperforms all gradient-free guidance baselines. (Since the docking score is non-differentiable, we excluded the gradient-based baseline DG.)\n\n|Method|Docking Score(↑)|TS(↓)|\n|-|:-:|:-:|\n|No Guidance|8.50±1.41|0.12±0.02|\n|TFG-Flow |8.45±1.49|0.12±0.02|\n|SVDD|9.36±1.38|0.12±0.02|\n|**TreeG-SC**|**9.58±1.28**|0.12±0.02|\n\nExperiment details: We used QuickVina2-GPU-2.1 to evaluate binding affinity of generated molecules to protein 5ht1b following [1]. The original scores were renormalized as max⁡(−DS,0). Experiments used 200 denoising steps on 100 generated sequences. \n\nDue to time constraints, we only have these results for now, but will complement them with larger sample sizes, additional denoising steps, and more protein targets in future experiments.\n\nRespond to your questions:\n\n>**Q1:** All the evaluations in the experiments are on simple tasks. Lack of high-dimentional task and image generation is more challenging for the value function estimation.\n\n\n**A1:** We thank the reviewer for the comments but respectfully disagree with this assessment.\n- **Our music generation task operates on high-dimensional data**: the raw piano-roll data has a dimensionality of (3×128×1024), and the latent space used for diffusion model remains substantial at (4×16×128) [2], which is comparable in scale to typical image generation tasks. \n- The three music generation tasks we evaluate are highly challenging—particularly the **non-differentiable objectives of note density and chord progression**, which are especially difficult to optimize. In particular, chord progression requires the time-consuming rule-based tool music21 [3] to get the evaluation. These tasks are sufficiently complex to demonstrate the effectiveness of our method.\n\n>**Q2:** In the black-box guidance area, usually, the main challenge is the query efficiency. ... no comparison against baselines regarding query efficiency is evaluated in the current draft, which is not convincing enough.\n\n\n**A2:** We appreciate the reviewer’s comment. Our method is not limited to black-box optimization but addresses the **broader problem of inference-time alignment** for diffusion models, where query efficiency is **only one** of several factors affecting computation. As discussed in **Sec. 6.4 (Table 4)**, the overall computation cost comprises:\n1. Passing through the diffusion model (which can dominate the total cost, e.g., in video generation),\n2. Evaluation of the objective function (query efficiency, as the reviewer noted),\n3. Backpropagation, when gradient-based methods and differentiable predictors are used.\n\nGiven these varying cost contributions across tasks, we focused on ensuring **comparable overall inference time** when comparing to baselines, rather than isolating query efficiency. We provide detailed statistics on the number of compute units per step per sample and the overall inference time of a batch, compared to the best training-free baselines across all tasks, as follows.\n\n|Method||Chord Progression|||Pitch Histogram/Note Density||\n|-|:-:|:-:|:-:|:-:|:-:|:-:|\n||Diffusion queries per step|Objective queries per step|Time (s)|Diffusion queries per step|Objective queries per step|Time (s)|\n|SCG|17|16|7267|17|16|194|\n|TreeG-SD|1|16|6660|1|32|203(PH),204(ND)|\n\nTable: Computation Breakdown in Music Generation ($K=16$ for TreeG-SD, sample size for SCG is $16$).\n\n||Diffusion step| CP Objective| PH Objective| ND Objective|\n|-|:-:|:-:|:-:|:-:|\n|Time (s)|0.0202|0.2520|0.0095|0.0356|\n\nTable: Basic unit time in Music Generation.\n\n|Method|Diffusion queries per step|Objective queries per step|Backpropagations per step |Time (s)|\n|-|:-:|:-:|:-:|:-:|\n|SVDD|17|320|0|72|\n|TreeG-G|1|20|1|10|\n\nTable: Computation Breakdown in DNA Enhancer Design ($K=1$ for TreeG-G, sample size for SVDD is $16$).\n\n\n||Diffusion step| Objective| Backpropagation|\n|-|:-:|:-:|:-:|\n|Time (ms)|0.087|0.021|0.036|\n\nTable: Basic unit time in DNA Enhancer Design.\n\n\n\n|Method||Vina Docking (Protein: 5ht1b)||||QED|||\n|-|:-:|:-:|:-:|:-:|:-:|:-:|:-:|:-:|\n||Diffusion queries per step|Objective queries per step|Denoising Steps|Time (s)|Diffusion queries per step|Objective queries per step|Denoising Steps|Time (s)|\n|SVDD|9|3.51|200|26924|5|40|1000|17|\n|TreeG-SC|9|3.51|200|26689|5|40|1000|17|\n\n\nTable: Computation Breakdown in Small Molecule Generation (Branch-out/sample sizes for TreeG-SC and SVDD are $8$ for Vina Docking and $4$ for QED. Since docking scores could not be calculated on invalid SMILES strings, the average number of objective queries over all steps was fewer than the expected value $5*8=40$).\n\n||Diffusion step| QED Objective| Vina Docking Objective|\n|-|:-:|:-:|:-:|\n|Time (ms)|0.038|2.0e-4|390|\n\nTable: Basic unit time in Small Molecule Generation.\n\n >**Q3:** In Theorem 2, it seems that given the same Branch-Out size, the high-dimensional case can achieve a much smaller error compared with the low-dimensional case. \n\n**A3:** Thank you for pointing this out. This is a typo. The correct expression in Theorem 2 is:\n$$\nK = \\Theta\\left(\\frac{D^{2}\\log (|\\mathcal{X}|/\\delta)}{\\varepsilon^{2}}\\right).\n$$\nThe mistake originated from the last step of the proof (line 763). The error should accumulate additively across dimensions:\n\n$$\n\\|\\hat{\\mathcal{T}} - \\mathcal{T}\\|_{\\infty} \\le D \\cdot \\Delta,\n$$\n\nwhere $\\Delta$ is the single-dimension (marginal) error, rather than multiplicatively as previously (incorrectly) written: $\\|\\hat{\\mathcal{T}} - \\mathcal{T}\\|_{\\infty} \\le \\Delta^{D}.$\n\nWe have corrected this in the revised version. The updated bound now properly reflects that the error grows with the dimensionality of the data.\n\n\n\n>**Q4:** The assumptions of the error bound for the continuous case are too strong. The requirement of the data follows a Gaussian distribution, and the objective function is linear is too restrictive.\n\n\n**A4:** \n- **On the necessity of assumptions**: From a theoretical perspective, the linear-Gaussian case is not trivial but rather fundamental. The search mechanism inherently disrupts the reverse dynamics of the unconditional diffusion model, making it analytically intractable to rigorously characterize the output distribution or derive end-to-end sample complexity bounds without additional structure. Recent work (e.g.,[4] Marion et al., 2024) also relies on Gaussian assumptions to establish rigorous guarantees for guided diffusion. Therefore, this assumption should be considered reasonable.\n- **On broader applicability**: While our theoretical analysis adopts Gaussian-linear assumptions to enable rigorous proofs, our experiments explicitly verify that the proposed approach performs well in substantially more complex settings, with non-Gaussian data distributions and nonlinear objectives, demonstrating that the method effectively generalizes beyond the assumptions used in the theoretical framework.\n\n\n\n>**Q5:** Symbols for the flow models are not well explained. Is it a typo for the symbol on Line 117?\n\n\n**A6:** Thank you for pointing this out. Yes, it's a typo. The correct expression is: \n\n$$\nR_t(x_t,j|x_1) = \\frac{\\delta  \\lbrace j,x_1 \\rbrace}{1-t}\\delta \\lbrace x_t, M \\rbrace.\n$$\n\nWe have corrected this in the revised manuscript.\n\n\n\n>**Q7:** The distribution $\\hat{\\mathcal{T}}$ depends on the time t, but the error bound in the Theorem does not show this explicitly.\n\n\n**A7:** Regarding the timestep $t$, Theorem 1 depends on the interval $\\Delta t$ (or the scheduling $\\alpha_t$), which is explicitly stated in the theorem. Other relevant terms are time-dependent constants, which are fully detailed in the extended versions of Theorems 1 and 2 (Appx. D.1 and D.3). \n\n\n\n\n\n>**Q8:** Some prior related works on the inference-time black-box guidance for diffusion models are not discussed.\n\n\n**A8:** Thank you for bringing this to our attention. We discuss the related works as follows:\n\n[5] uses an ODE/SDE solver to backpropagate through the backward process and the objective gradient directly to the initial latent state. [6] builds on the Guided Noise Sequence Optimization technique, using Gaussian Process estimation to guide diffusion models for black-box optimization. [7] fine-tunes models using covariance-adaptive sequential black-box optimization techniques. While [5–7] are applicable to non-differentiable objectives, they are not applicable to **discrete** diffusion/flow models.\n\nWe appreciate this feedback and have added a discussion of these works in the revised version.\n\n\n*Reference*\n\n[1] Yang, et al. Hit and lead discovery with explorative rl and fragment -based molecule generation.\n\n[2] Huang et. al. Symbolic music generation with non-differentiable rule guided diffusion. arXiv:2402.14285, 2024.\n\n[3] music21: A toolkit for computer-aided musicology and symbolic music data. 2010.\n\n[4] Pierre Marion et al. Implicit diffusion: Efficient optimization through stochastic sampling. arXiv preprint arXiv:2402.05468, 2024.\n\n[5] Tang et al. Tuning-free alignment of diffusion models with direct noise optimization. arXiv:2405.18881, 2024.\n\n[6] Tan et al. Fast Direct: Query-Efficient Online Black-box Guidance for Diffusion-model Target Generation. ICLR 2025.\n\n[7] Lyu et al. Covariance-adaptive sequential black-box optimization for diffusion targeted generation. arXiv:2406.00812, 2024.\n\n\n---\n**We sincerely hope that our responses can address your concerns, and we would greatly appreciate it if you would consider raising your score of our work to a *clear accept* given the responses.**"}, {"review_id": "UF3e4SQJLp", "reviewer": "Reviewer_nDiZ", "summary": "This paper proposes a family of methods for inference-time control of diffusion generative model with nondifferentiable rewards. The method involves keeping a set of samples and filtering or resampling the set of proposals generated from those samples at each diffusion step. The method is evaluated on a wide array of discrete generation tasks, including symbolic music, molecules, and DNA. Scaling experiments are performed to establish the impact of key hyperparameters.", "questions": "No specific questions for authors.", "limitations": "Yes", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strengths**\nThe paper's key conceptual idea, that of maintaining a set of samples that is steered and resampled during inference via a reward function, is well worth articulating and presenting to the community. It mirrors important developments in continuous diffusion steering (Feynman-Kac steering) that demonstrates the benefits of maintaining a set of samples, a la SMC, rather than steering individual trajectories. The coverage and diversity of the experiments is noteworthy and shows promising results.\n\n**Concerns**\nWhile the core message and idea of the submission are sound and potentially impactful, there are concerns about the manner of presentation and execution of the method.\n* Despite the appealing intuition of maintaining an active set, the main experiments are nonetheless conducted with $A=1$. With this departure, the exposition in the abstract, exposition, and figures are misleading.\n* The theorems in the continuous case suppose that the data are Gaussian and the reward function linear. These restrictions are so severe as to perhaps disqualify the theorem from being a main result. Certainly, it cannot be said in exposition that \"TreeG-SC yields a distribution T that close approximates...\" without qualification.\n* There is not very much exploration about how to define the intermediate value functions, which seems critical to the performance of the method. Evaluating the terminal reward at samples x_1 | x_t obtained in one step might not work, as those samples could be far out of distribution of x_1.\n* There appears to be a somewhat exaggerated difference between TreeG-SC and TreeG-SD, differing only in whether the variance of x_1 | x_t is accounted for or whether we use the conditional mean. In the discrete case, they appear identical.\n* With ranking based selection, the procedure reduces to a intuitive heuristic procedure. Unlike SVDD, we do not know what distribution the procedure will sample. This makes it difficult to reason and fairly compare the performance with methods that do sample a known distribution - the procedure could be optimizing the reward but resulting in diversity collapse or missing modes in hard to reach local minima.\n* It seems that whenever the results in a column are not favorable to the authors, the results in that column are not bolded (Tables 1, 2, 3).\n* The paper uses \"scaling law\" to refer to any monotonic decrease in loss - this is not accurate.\n\nAltogether, the core idea of the paper is strong, but the experiments do not focus on all of the most important aspects of the idea and overemphasizes points that are not really the paper's strengths (i.e., theoretical bounds). I do not anticipate that the authors will have time to dramatically reorganize the presentation of results during rebuttal; however, I am open to raising the score if the authors can argue why the procedure. as implemented in the main experiments, corresponds to what is claimed in the abstract and introduction.", "was_revised": true, "final_justification": "As I wrote in the review, I am open to raising the score if the authors can argue why the procedure. as implemented in the main experiments, corresponds to what is claimed in the abstract and introduction. The authors successfully addressed this.", "rebuttal": "Thank you for the detailed response.\n\n>**Q1:** Despite the appealing intuition of maintaining an active set, the main experiments are nonetheless conducted with $A=1$. With this departure, the exposition in the abstract, exposition, and figures are misleading.\n\n**A1:** We clarify that **we have conducted experiments with $A>1$ across all tasks (Sec. 6.3, Appx. G.1.2, G.2.2, G.3.2)**. In Sec. 6.2, we reported results of $A=1$ to ensure fair comparisons with baselines, which do not have the concept of an active set. We clarify:\n\n- Our method has two key mechanisms, branch-out then selection, and maintaining an active set, corresponding to two scalable parameters: branch-out size $K$ and active set size $A$. Increasing either improves optimization effect. For example, the following table reports the Note Density loss (↓) for symbolic music across different $A$ and $K$ values (TreeG-SD):\n\n||A=1|A=2|A=4|A=8|A=16|\n|:-|:-|:-|:-|:-|:-|\n|K=1|2.486±3.530|1.465±1.842|1.139±2.271|0.784±1.108|0.696±1.526|\n|K=2|0.629±0.827|0.231±0.472|0.113±0.317|0.057±0.179|-|\n|K=4|0.319±0.619|0.159±0.401|0.048±0.198|-|-|\n|K=8|0.217±0.450|0.082±0.266|-|-|-|\n|K=16|0.142±0.423|-|-|-|-|\n\n\n- We reported $A=1$ results for **fair comparison**, as baselines lack the concept of an active set. This isolates the impact of our branch-out and selection mechanism. However, as shown below, allowing a flexible active set size ($A>1$) further improves performance at the same computational cost. For instance, TreeG-SD with $(A=4, K=4)$ achieves better performance than $(A=1, K=16)$, which was reported for comparing with baselines.\n\n|Method|Loss (↓)|OA (↑)|\n|:-|:-:|:-:|\n|TDS|0.218 ± 0.241| 0.875 ± 0.023|\n|SVDD|0.445 ± 0.437| 0.835 ± 0.028|\n|SCG|0.134 ± 0.533|0.842 ± 0.022|\n|**TreeG-SD (A=1, K=16)**| 0.142 ± 0.423|0.832 ± 0.023|\n|**TreeG-SD (A=4, K=4)**|  0.048 ± 0.198| 0.843 ± 0.012|\n\n\n\n\n>**Q2:** The theorems in the continuous case suppose that the data are Gaussian and the reward function linear. These restrictions are so severe as to perhaps disqualify the theorem from being a main result. Certainly, it cannot be said in exposition that \"TreeG-SC yields a distribution T that close approximates...\" without qualification.\n\n\n**A2:** We appreciate the comment and have revised the exposition to qualify our statement, now writing: “TreeG-SC(SD) yields a distribution that closely approximates the target conditional transition distribution, under gaussian data and linear objective assumption in continuous case.” We also emphasize that the empirical contribution is central to our work, with the theoretical results serving as complementary insights. We'd like to further clarify:\n\n- **On the necessity of assumptions**: From a theoretical perspective, the linear-Gaussian case is not trivial but rather fundamental. The search mechanism inherently disrupts the reverse dynamics of the unconditional diffusion model, making it analytically intractable to rigorously characterize the output distribution or derive end-to-end sample complexity bounds without additional structure. Recent work (e.g.,[1] Marion et al., 2024) also relies on Gaussian assumptions to establish rigorous guarantees for guided diffusion. Therefore, this assumption should be considered reasonable.\n- **On broader applicability**: While our theoretical analysis adopts Gaussian-linear assumptions to enable rigorous proofs, our experiments explicitly verify that the proposed approach performs well in substantially more complex settings, with non-Gaussian data distributions and nonlinear objectives, demonstrating that the method effectively generalizes beyond the assumptions used in the theoretical framework.\n\n\n\n>**Q3:** TreeG-SC and TreeG-SD differ only in whether the variance of x_1 | x_t is accounted for or whether we use the conditional mean. In the discrete case, they appear identical.\n\n\n**A3:** TreeG-SC and TreeG-SD are fundamentally different methods in both discrete and continuous cases. Their differences are summarized below:\n\n|Aspect |TreeG-SC|TreeG-SD|\n|:-|:-|:-|\n|Exploration space|Next state $x_{t + \\Delta t}$| Destination $x_1\\|x_t$ |\n|Use of lookahead estimate|Uses the diffusion model to obtain  $x_1 \\| x_{t + \\Delta t}$ for evaluating each candidate next state|Leverages $x_1 \\|x_t$ already available in the backward process, to branch toward promising destinations|\n|High-level idea|Optimize the immediate next step $x_{t + \\Delta t}$| Select promising final destinations $x_1$ first, then infer the next state accordingly|\n|Complexity (Sec.6.4 **Table 4**)|$AC_{\\text{model}}+AK(C_{\\text{model}}+ NC_{\\text{pred}})$|$AC_{\\text{model}}+AKC_{\\text{pred}}$| \n\nAlthough these operations may appear superficially similar, their exploration targets, use of conditional distribution, high-level strategies, and computational complexities are completely different.\n\n\n\n\n>**Q4:** Evaluating the terminal reward at samples x_1 | x_t obtained in one step might not work, as those samples could be far out of distribution of x_1.\n\n\n\n**A4:** Evaluating via $x_1|x_t$ is both theoretically reasonable empirically effective:\n- First, diffusion/flow model is explicitly trained to model the distribution $p(x_1|x_t)$ (conditional mean $\\mathbb{E}[x_1|x_t]$ in continuous case by Tweedie’s formula [2]). Assuming a perfect pre-trained diffusion model, using $x_1|x_t$ for evaluation is aligned with how the models are intended to function, thus theoretically justified.\n- Second, our empirical results demonstrate strong performance on our three proposed methods, indicating that evaluation using the one-step lookahead estimate is effective.\n\nWe appreciate the suggestion to explore alternative value function designs. One direction is multi-step lookahead value estimation. However, it would incur substantially higher computational cost due to the need for multiple inference steps through the diffusion model. In contrast, our proposed value functions offer a practical and efficient solution that achieves strong performance with significantly lower computational overhead.\n\n\n\n\n\n\n>**Q5:** With ranking based selection, the procedure could be optimizing the reward but resulting in diversity collapse or missing modes in hard to reach local minima.\n\n\n**A5:**  **We have already included diversity as an explicit evaluation metric in our experiments.** \n- We use Tanimoto similarity for molecule (Table 2) and  average Hamming distance for DNA (Table 3). For music, while there is no standard diversity metric, the quality metric (OA) reported in Table 1 can reflect diversity to some extent.\n- Our results show that the proposed methods achieve diversity comparable to baselines, including SVDD, across all tasks. While ranking-based selection can be seen as an extreme case of resampling, empirical evidence suggests it does not lead to diversity collapse or mode dropping—likely because the practical reward signal is not overly sharp, avoiding collapse into narrow modes.\n\n\n>**Q6:** It seems that whenever the results in a column are not favorable to the authors, the results in that column are not bolded (Tables 1, 2, 3).\n\n\n**A6:** This is a misunderstanding of our presentation choice. We intentionally bold only the metrics that reflect the optimization effect, not the quality metrics, for the following reasons:\n\n- (1) To avoid confusion and preserve the main point:\nBolding quality metrics could obscure the focus of the results. For example, in Table 3, some baselines such as TFG-Flow and SVDD show very high diversity but almost no optimization effect. Highlighting these values would misleadingly give undue credit, despite their poor performance on the main objective.\n- (2) Quality metrics only need to be at a comparable level:\nFor quality metrics, the absolute values or rankings are less critical; it's only required that the proposed method remains comparable to the baselines. Since this information is already clear from the tables, additional bolding is unnecessary and could mislead readers about the study’s primary goal.\n\n\n\n\n\n>**Q7:** The paper uses \"scaling law\" to refer to any monotonic decrease in loss - this is not accurate.\n\n**A7:** We use the term \"scaling law\" to describe the improvement in optimization performance (decrease in loss) with respect to the active set size $A$ and branch-out size $K$.\n\n\n\n*Reference*\n\n[1] Pierre Marion et al. Implicit diffusion: Efficient optimization through stochastic sampling. arXiv preprint arXiv:2402.05468, 2024.\n\n[2] Bradley Efron. Tweedie’s formula and selection bias. Journal of the American Statistical Association, 106(496):1602–1614, 2011\n\n---\n\n**Given your review, we believe there were major misunderstandings on our work. We sincerely hope that our responses can resolve the misunderstandings and address your concerns, and we would greatly appreciate it if you would like to re-evaluate our work given the responses.**"}]

Author rebuttal:

Meta-review: This paper introduces TreeG, a tree search–based framework for training-free guidance in diffusion and flow models that can handle non-differentiable objectives and discrete data. The framework is instantiated into three algorithms, supported by theoretical analysis under simplifying assumptions, and evaluated across symbolic music, molecule, and DNA design tasks. Additional experiments, including results on Vina Docking, further demonstrate its empirical strength.

The main strengths are the novelty of the unified framework, consistent performance gains across diverse domains, and the added clarity provided through new evaluation metrics such as Negative Log-Likelihood. The rebuttal and discussion resolved initial concerns regarding task selection, theoretical assumptions, computational cost, and presentation of results. Reviewers acknowledged these clarifications and raised their assessments accordingly.

Overall, the reviewers converged to a positive consensus, finding the contribution technically solid and broadly relevant. I recommend acceptance.
Decision: Accept (poster)