Inference-time Scaling of Diffusion Models through Classical Search

Xiangcheng Zhang, Haowei Lin, Haotian Ye, James Zou, Jianzhu Ma, Yitao Liang, Yilun Du · 2025

Read Inference-time Scaling of Diffusion Models through Classical Search by Xiangcheng Zhang, Haowei Lin, Haotian Ye, James Zou, Jianzhu Ma, Yitao Liang, Yilun Du (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-23614.txt.

Introduction

Xiangcheng Zhang and co-authors steer diffusion models at run time using classical search, the old workhorse of artificial intelligence. Their 2025 paper tackles inference time control: bending a model's output toward goals set only at test time. The framework pairs a local search, an annealed sampling method with theory behind it, with global tree search in breadth first and depth first forms.

Tests covered planning, offline reinforcement learning, and image generation. Across all three, the search based control gained in both quality and efficiency over prior routes. The authors argue classical search gives a principled, practical base for scaling diffusion models at inference, rather than by retraining.

Catalog record

CREATORXiangcheng Zhang, Haowei Lin, Haotian Ye, James Zou, Jianzhu Ma, Yitao Liang, Yilun Du
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE95 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-23614

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Inference-time Scaling of Diffusion Models through Classical Search Xiangcheng Zhang, Haowei Lin, Haotian Ye, James Zou, Jianzhu Ma, Yitao Liang, Yilun Du Abstract Classical search algorithms have long underpinned modern artificial intelligence. In this work, we tackle the challenge of inference-time control in diffusion models—adapting generated outputs to meet diverse test-time objectives—using principles from classical search. We propose a general framework that orchestrates local and global search to efficiently navigate the generative space. It performs compute-efficient global exploration using breadth-first and depth-first tree search and employs a theoretically grounded, scalable local search via annealed Langevin MCMC. We evaluate our approach on a range of challenging domains, including planning, offline reinforcement learning, and image generation, and observe significant gains in both performance and efficiency over baseline methods. These results demonstrate that classical search offers a principled and practical foundation for inference-time scaling in diffusion models. By jointly scaling local and global search for the first time, our framework establishes a new Pareto frontier across challenging decision-making domains. Project page at diffusion-inference-scaling.github.io . 1 Introduction Classical search algorithms have laid the foundation for modern artificial intelligence ( Russell & Norvig, 2009 ) . In discrete settings, graph search algorithms are widely used to explore the state space. Breadth-first search (BFS) ( Moore, 1959 ) and depth-first search (DFS) ( Tarjan, 1972 ) traverse the search tree in a fixed order. To better leverage problem-specific information, best-first search methods ( Pearl, 1984 ) , such as A* ( Hart et al., 1968 ) , use a heuristic to evaluate and prioritize states. Alternatively, local search methods, such as hill-climbing ( Russell & Norvig, 2009 , Sec. 4.1) , explore neighboring states. More recent techniques like gradient descent and Markov Chain Monte Carlo (MCMC) have become widely adopted in optimization and probabilistic inference, underpinning many modern AI models. Diffusion models ( Ho et al., 2020 ) have shown impressive performance in generative modeling for continuous domains such as images ( Dhariwal & Nichol, 2021 ) , videos ( Ho et al., 2022 ) . They are also increasingly used in robotics and decision-making ( Liu et al., 2024 ; Black et al., 2024 ; Team et al., 2024 ) to generate diverse actions ( Chi et al., 2023 ) . However, generated samples may not always align with physical laws ( Song et al., 2023 ) or human intent ( Wallace et al., 2024 ) , and the vast generative space often necessitates multiple trials to produce satisfactory outputs ( Xie et al., 2025 ) . To address this, we scale up inference-time compute using strategic search methods that navigate the generative manifold for high-quality samples. We formalize sample evaluation using a verifier function f({\bm{x}}_{0}) defined on ground truth samples, which measures the quality of the sample. Such verifiers could be reward functions ( Xu et al., 2023a ) , Q-functions ( Lu et al., 2023 ) , classifier conditions p(c|{\bm{x}}_{0}) ( Ye et al., 2024 ; Dhariwal & Nichol, 2021 ) , and VLMs ( Huang et al., 2023 ) . To efficiently search the generative space of diffusion models, we revisit classical search principles. To capture diverse modes in the complex distributions generated by diffusion models, we view sampling as traversing a search tree, employing BFS and DFS to progressively explore states during denoising. Similar to best-first search, we evaluate intermediate states {\bm{x}}_{t} with the verifier f({\bm{x}}_{0|t}) , prioritizing high-quality paths and efficiently allocating compute via branching and backtracking. To go beyond the base model and obtain higher-quality samples, we perform local search via Langevin MCMC, exploring the neighborhood of current samples under guidance from both the verifier gradient and the diffusion model’s “score function” ( Vincent, 2011 ) . By jointly optimizing the compositional objective of the diffusion model and the verifier ( Du et al., 2023 ) , our local search surpasses the capabilities of the base model. An overview of our framework is shown in Fig. 1 . Recent works scale diffusion model inference via particle-based SMC ( Kim et al., 2025 ; Singhal et al., 2025a ; Wu et al., 2023 ) and tree-based methods ( Guo et al., 2025 ) , typically as BFS with fixed schedules. We generalize these with a BFS-based framework, clarifying prior design choices and providing an improved BFS surpassing prior methods. Inspired by DFS, we add adaptive backtracking to allocate compute adaptively, surpassing BFS in efficiency and adaptivity. While global search remains limited to base-distribution modes, scaling local search with Langevin MCMC explores high-reward regions beyond the model, proving effective in challenging decision-making tasks. Finally, we jointly scale local and global search with the classical AI search principles, demonstrating superior performance over prior methods, which scale local and global search in isolation. Our key contributions are summarized as follows: i) For global tree search, we elucidate the design space of prior BFS-style methods and provide an improved BFS design. We further present the first adaptive DFS algorithm for diffusion inference scaling, offering superior efficiency and adaptivity. ii) We introduce a theoretically grounded local search method using annealed Langevin MCMC, demonstrating superior performance in challenging decision-making domains. iii) We propose a unified framework for inference scaling that integrates both global and local search within the classical AI search paradigm. By jointly scaling local and global search for the first time, we advance the Pareto frontier of inference-time scaling for diffusion models across diverse domains. Figure 1: Illustration of our search framework . Bottom left : direct sampling results in samples with low verifier scores. Bottom middle : global search identifies high score modes within the base distribution. Bottom right : local search further optimizes the samples for higher quality, driven by the gradient signal. 2 Related Works Here, we provide a brief overview of inference-time scaling with diffusion models. For a more comprehensive literature review and discussion of concurrent works, see Appendix B . Particle-based scaling methods Recent works ( Kim et al., 2025 ; Singhal et al., 2025a ) propose SMC-style particle filtering methods, scaling inference compute by increasing the number of particles and improving efficiency via resampling. Similarly, tree-search-based methods ( Li et al., 2024 ; Guo et al., 2025 ; Ma et al., 2025 ) evaluate intermediate nodes and expand promising candidates. Both approaches can be seen as special cases of our BFS tree search framework, which denoise a set of particles in parallel, applying branching and filtering based on intermediate reward signals. Additional to linear BFS-style algorithms, we also propose DFS-style algorithms with non-linear adaptive backtracking, demonstrating superior performance over prior methods. Gradient-based guidance methods To sample from a conditional distribution, classifier guidance ( Dhariwal & Nichol, 2021 ) utilizes the gradient from a trained noise-dependent classifier to compute the conditional score function ( Song et al., 2020b ) . However, such noise-dependent classifier requires additional training and data collection. To use classifiers defined on clean samples, training-free guidance methods ( Ye et al., 2024 ; Chung & Ye, 2022 ; Song et al., 2023 ; Yu et al., 2023 ; He et al., 2023 ) approximates noisy conditional probability using the denoised output {\bm{x}}_{0|t} . Such methods are inheritability biased due to their first order approximation. Different from

Read the complete text