TL;DR
Instead of merely increasing the number of denoising steps to improve diffusion model outputs, this paper proposes optimizing the noise trajectory—the specific sequence of random noise vectors injected during inference. By relaxing the generation process from a complex tree-search problem into a sequence of independent contextual bandits, the authors introduce a highly efficient $\epsilon$-greedy search algorithm that achieves up to a 164% improvement in sample quality for arbitrary, non-differentiable rewards.
What Problem Does This Paper Address?
When using diffusion models at inference time, the standard way to get higher-quality images is "test-time scaling"—typically by increasing the number of denoising steps ($T$). However, this approach quickly hits diminishing returns and plateaus after a few dozen steps due to accumulated discretization errors.
An alternative, highly promising axis for scaling compute is optimizing the noise trajectory. In stochastic diffusion (SDE-based), fresh noise is injected at every single step. Some noise realizations lead to beautiful, prompt-aligned images, while others lead to duds.
The challenge? The search space for these noise vectors is astronomically large, high-dimensional, and completely unbounded. Furthermore, evaluating whether a choice of noise at step 20 was "good" usually requires running the entire rest of the generation process, making exhaustive search computationally impossible.
Methods
The authors first formalize the noise trajectory search by casting the $T$-step reverse diffusion process as a finite-horizon Markov Decision Process (MDP) with a terminal reward. While tree-search methods like Monte Carlo Tree Search (MCTS) can navigate this MDP, they are incredibly slow (scaling quadratically with $T$) and are restricted to a fixed, pre-sampled tree of noise candidates.
To build a practical method, the authors introduce a clever relaxation: they treat denoising as a sequence of independent continuous contextual bandits. By ignoring inter-step dependencies, they can evaluate noise candidates at the current timestep $t$ without rolling out the entire remaining trajectory. They achieve this by using Tweedie's formula to estimate the final clean image ($\hat{x}_0^{(t)}$) at each step, allowing them to compute a fast surrogate reward.
Using this bandit framework, they propose $\epsilon$-greedy noise search (Algorithm 1):
- Global Exploration: With probability $\epsilon$, the algorithm samples a noise candidate globally from the standard Gaussian prior.
- Local Exploitation: With probability $1-\epsilon$, it samples locally within a small radius ($\lambda$) around the current best noise vector ("the pivot"), performing gradient-free hill-climbing.
Datasets
The method was evaluated using two primary setups across various task-specific, non-differentiable reward functions:
- Elucidated Diffusion Model (EDM): Evaluated on ImageNet ($64 \times 64$) for class-conditioned image generation. Rewards included image brightness, JPEG compressibility, and ground-truth class probability from a pre-trained ImageNet classifier.
- Stable Diffusion (v1.5 and SDXL): Evaluated on complex text prompts for text-to-image generation ($512 \times 512$). Rewards included CLIP score (prompt-image alignment), ImageReward (human preference proxy), and a specialized object-counting reward.
Key Insights and Ideas
- Explore Globally, Exploit Locally: The algorithm automatically adapts its strategy based on the diffusion timestep. At the very early and very late stages of denoising, the reward landscape is relatively flat and noisy, so the algorithm favors global random jumps to find high-reward regions. During the critical intermediate timesteps—where demixing and mode selection actually happen—the reward landscape becomes highly sensitive (exhibiting a high Lipschitz constant). Here, the algorithm shifts to local hill-climbing to fine-tune the features.
- Breaking the Tree Constraint: Unlike MCTS or Beam Search, which are locked into a discrete, pre-selected tree of noise choices, the contextual bandit relaxation allows $\epsilon$-greedy search to continuously discover entirely new, high-reward noise vectors outside the initial distribution.
- Linear Compute Scaling: Because it avoids full rollouts, the Number of Function Evaluations (NFEs) scales linearly with the number of denoising steps $T$, making it vastly more practical than MCTS.
Key Results
- State-of-the-Art Performance: The $\epsilon$-greedy search consistently outperformed all baselines (naive sampling, best-of-N, beam search, and zero-order search). Remarkably, it matched or exceeded the performance of full MCTS while using a fraction of the compute.
- Massive Quality Boosts: For EDM class-conditioned generation, the method achieved up to a 164% improvement in sample quality metrics over vanilla generation.
- Text-to-Image Enhancements: On Stable Diffusion v1.5, $\epsilon$-greedy attained improvements of 48% / 26% / 20% over vanilla sampling for brightness, compressibility, and CLIP scores, respectively. It proved highly capable of forcing the model to follow notoriously difficult prompts (e.g., generating exactly "three rockhoppers in a line").
Limitations and Future Work
- Compute Overhead: While linear in $T$, the algorithm still requires $N \times K$ times more forward passes than vanilla sampling (where $N$ is the branching factor and $K$ is the local search iterations). This added latency could challenge real-time deployment.
- Reward Overoptimization: For large step sizes ($\lambda$), the algorithm can occasionally "game" simple rewards. For instance, when optimizing purely for brightness, it can end up generating completely white images.
- Future Directions: The authors suggest exploring adaptive scheduling (reducing search iterations at extreme timesteps to save compute), hybrid bandit-tree solvers, and using regularization techniques to prevent reward overoptimization.
Summary updated