Training-Free Guidance Beyond Differentiability: Scalable Path Steering with Tree Search in Diffusion and Flow Models

Thank you for the detailed response.

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.

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:

• 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):

• 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.

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.

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:

• 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.
• 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.

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.

A3: TreeG-SC and TreeG-SD are fundamentally different methods in both discrete and continuous cases. Their differences are summarized below:

Although these operations may appear superficially similar, their exploration targets, use of conditional distribution, high-level strategies, and computational complexities are completely different.

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.

A4: Evaluating via $x_1|x_t$ is both theoretically reasonable empirically effective:

• 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.
• Second, our empirical results demonstrate strong performance on our three proposed methods, indicating that evaluation using the one-step lookahead estimate is effective.

We 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.

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.

A5: We have already included diversity as an explicit evaluation metric in our experiments.

• 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.
• 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.

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).

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:

• (1) To avoid confusion and preserve the main point: Bolding 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.
• (2) Quality metrics only need to be at a comparable level: For 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.

Q7: The paper uses "scaling law" to refer to any monotonic decrease in loss - this is not accurate.

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$.

Reference

[1] Pierre Marion et al. Implicit diffusion: Efficient optimization through stochastic sampling. arXiv preprint arXiv:2402.05468, 2024.

[2] Bradley Efron. Tweedie’s formula and selection bias. Journal of the American Statistical Association, 106(496):1602–1614, 2011

---

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.

Thank you for your positive feedback on our work! We first present new experimental results, followed by responses to the remaining concerns.

---

We 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.)

Experiment 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.

Due 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.

Respond to your questions:

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.

A1: We thank the reviewer for the comments but respectfully disagree with this assessment.

• 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.
• 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.

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.

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:

1. Passing through the diffusion model (which can dominate the total cost, e.g., in video generation),
2. Evaluation of the objective function (query efficiency, as the reviewer noted),
3. Backpropagation, when gradient-based methods and differentiable predictors are used.

Given 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.

Table: Computation Breakdown in Music Generation ($K=16$ for TreeG-SD, sample size for SCG is $16$).

Table: Basic unit time in Music Generation.

Table: Computation Breakdown in DNA Enhancer Design ($K=1$ for TreeG-G, sample size for SVDD is $16$).

Table: Basic unit time in DNA Enhancer Design.

Table: 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$).

Table: Basic unit time in Small Molecule Generation.

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.

A3: Thank you for pointing this out. This is a typo. The correct expression in Theorem 2 is:

$$K = \Theta\left(\frac{D^{2}\log (|\mathcal{X}|/\delta)}{\varepsilon^{2}}\right).$$

The mistake originated from the last step of the proof (line 763). The error should accumulate additively across dimensions:

$$\|\hat{\mathcal{T}} - \mathcal{T}\|_{\infty} \le D \cdot \Delta,$$

where $\Delta$ is the single-dimension (marginal) error, rather than multiplicatively as previously (incorrectly) written: $\|\hat{\mathcal{T}} - \mathcal{T}\|_{\infty} \le \Delta^{D}.$

We have corrected this in the revised version. The updated bound now properly reflects that the error grows with the dimensionality of the data.

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.

A4:

• 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.
• 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.

Q5: Symbols for the flow models are not well explained. Is it a typo for the symbol on Line 117?

A6: Thank you for pointing this out. Yes, it's a typo. The correct expression is:

$$R_t(x_t,j|x_1) = \frac{\delta \lbrace j,x_1 \rbrace}{1-t}\delta \lbrace x_t, M \rbrace.$$

We have corrected this in the revised manuscript.

Q7: The distribution $\hat{\mathcal{T}}$ depends on the time t, but the error bound in the Theorem does not show this explicitly.

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).

Q8: Some prior related works on the inference-time black-box guidance for diffusion models are not discussed.

A8: Thank you for bringing this to our attention. We discuss the related works as follows:

[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.

We appreciate this feedback and have added a discussion of these works in the revised version.

Reference

[1] Yang, et al. Hit and lead discovery with explorative rl and fragment -based molecule generation.

[2] Huang et. al. Symbolic music generation with non-differentiable rule guided diffusion. arXiv:2402.14285, 2024.

[3] music21: A toolkit for computer-aided musicology and symbolic music data. 2010.

[4] Pierre Marion et al. Implicit diffusion: Efficient optimization through stochastic sampling. arXiv preprint arXiv:2402.05468, 2024.

[5] Tang et al. Tuning-free alignment of diffusion models with direct noise optimization. arXiv:2405.18881, 2024.

[6] Tan et al. Fast Direct: Query-Efficient Online Black-box Guidance for Diffusion-model Target Generation. ICLR 2025.

[7] Lyu et al. Covariance-adaptive sequential black-box optimization for diffusion targeted generation. arXiv:2406.00812, 2024.

---

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.

Thank you for your positive feedback on our work! We address your questions below.

Q1: Could the authors also comment on the scalability of TreeG in terms of the dimensionality of the data distribution?

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

$$K = \Theta\left(\frac{\log (|\mathcal{X}|/\delta)}{\varepsilon^{2}}\right),$$

here $|\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.

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?

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:

K = \Theta\left(\frac{B^2_\max}{B^2_\min} \cdot \frac{\log (|\mathcal{X}|/\delta)}{\varepsilon^{2}}\right),

where 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.

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.

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.

We thank the reviewer poining this out and have clarified this comparison with fine-tuning methods in the revised version.

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.

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.

From Bayes’ theorem:

$$p(x|y) \propto p(x) \cdot p(y|x),$$

where the two terms can be measured as follows:

• 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.
• 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.

Results based on these complete metrics are shown in the table below.

As 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.

This 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.

Reference

[1] Venkatraman et al. Amortizing intractable inference in diffusion models for vision, language, and control. NeurIPS 2024.

[2] Austin et al. Structured Denoising Diffusion Models in Discrete State-Spaces.

[3] Uehara et al. Reward-Guided Iterative Refinement in Diffusion Models at Test-Time with Applications to Protein and DNA Design.

---

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.

Thank you for your positive feedback on our work! We address your questions below.

Q1: Selection criteria for the target tasks? What is the argument for universality over this specific set?

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.

Q2: Theoretical assumptions (Gaussian data, linear objectives) may limit generality.

A2:

• 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.
• 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.

[1] Pierre Marion et al. Implicit diffusion: Efficient optimization through stochastic sampling. arXiv preprint arXiv:2402.05468, 2024.

Q3: Possible reproducibility and transferability gap across tasks due to many hyper-parameters (e.g., Monte-Carlo N, temperature) tuned per task without ablation.

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:

• 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.
• 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.

---

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.