- Rating
- 4(+1)
- Confidence
- 3
- Informativeness
- 3
- Presentation
- 3
- Soundness
- 2
Read review
Paper summary
This paper proposes an innovative method, Continuous State Verifier Guided Backtracking (CS-VGB). It introduces: 1. Bidirectional search among intermediate states to generate samples from a desired reward-tilted terminal distribution; 2. Theoretical guarantees for the proposed method; 3. Empirical studies across multiple domains demonstrating the method's effectiveness. The method works with any pretrained model and alleviates verifier error very effectively. Overall, the paper is well written with rigorous theories and proofs. As a theoretical paper, it also provides promising empirical results in simple 2D data, image data, and robotics data.
Critical strengths
It does not rely on the choice of underlying model or verifier accuracy.
The theorems are relevant to the main paper. The proofs are well structured.
The results clearly show the strengths and effectiveness of the proposed method. The experiments are also diverse across multiple domains. Ablation studies clearly demonstrate the importance of each key component (bidirectionality, backward guidance, reverse insertion, etc.) in the method.
Critical weaknesses
Some concerns about the gap between theory and practice, mostly on the trade-off between high reward and low search time.
Questions for authors
The questions are mostly related to the practical feasibility.
Could you justify the introduction of extra hyperparameters such as directional persistence , depth weight and pool sizes ? These parameters add more burden and worsen the trade-off between high reward and low search time. In addition, how invariant are these hyperparameters? In other words, do you need to tune them for different underlying models, tasks, or other conditions?
Have you considered any early stopping criteria for your method? From the results, it seems that the clean outputs are already in a sufficiently high reward state given a low budget. I believe this can alleviate some of the time complexity, especially for time-sensitive tasks where a lower search time is preferred. In addition, although this paper focuses on clean (boundary) states, have you guys observed any improvements in the interior states as well? Perhaps they are also useful byproducts.
Minor question: could you provide more justification or intuition on why reverse insertion is needed and how naive resampling introduces bias?
6 comments
(2/4) Response to Official Review by Reviewer jHem
For , lowering its value favors denoising over renoising by scaling the backward-to-forward mass ratio (Eq. B.17). This encourages clean returns under a tight budget. However, if is too small, the search favors denoising so strongly that renoising may not proceed far enough to enable meaningful changes to the current candidate. For example, the chain may repeatedly move between the clean level and the adjacent level , returning to a clean output before reaching higher noise levels where it has more freedom to change the sample. We therefore use as a shared starting point to balance clean returns with deeper renoising, and examine how affects the clean-hit rate under a 512-NFE cap on ImageNet in Table R4(b).
Table R4(b). Clean-hit rate on ImageNet under a 512-NFE cap. Results use 20 fixed conditions × 3 seeds. Clean-hit rate is the percentage of runs that return at least one clean image within the NFE cap. is our default setting.
| 0.1 | 0.2 | 0.3 | 0.4 | 0.6 | 1.0 | |
|---|---|---|---|---|---|---|
| Clean-hit rate (%) | 100.0 | 100.0 | 96.7 | 93.3 | 51.7 | 3.3 |
As decreases, the clean-hit rate increases and reaches 100% at in this setting. However, as discussed above, maximizing this rate alone can leave too little renoising for broader exploration, especially in tasks such as multi-robot planning. To balance reliable clean returns with deeper exploration, we therefore kept across all three tasks in our guided experiments.
On tuning and . Whereas and control directional persistence and the denoising–renoising balance, and determine how many candidate states are considered before each forward or backward move, trading more alternatives at each step for fewer search steps within the same budget.
Table R4(c) shows that small candidate pools already perform well at the tested medium inference budget (4,096 NFE). Starting from , we increase either the forward or backward pool to 4 and 8 while keeping the other at 2. This compares spending the budget on more candidates per move with leaving more computation for subsequent search steps.
Table R4(c). Candidate-pool size ablation on ImageNet at a 4,096-NFE cap. Entries report mean HPSv2 over 20 fixed conditions × 3 seeds, with Monte Carlo samples for guidance and checkpoint intervals.
| HPSv2 ↑ | 46.31 | 45.83 | 44.96 | 46.25 | 45.87 |
Larger pools require more candidate evaluations at each move, leaving fewer search steps within a fixed inference budget. Although each move considers more alternatives, the resulting reduction in exploration can hurt performance, consistent with the slightly lower mean rewards observed for several larger-pool settings in Table R4(c). These results support starting with small pools and increasing them only when they improve quality within the intended inference budget.
(3/4) Response to Official Review by Reviewer jHem
On early stopping and intermediate-state quality. We thank the reviewer for these suggestions, which raise two practical questions: when to stop the search, and whether intermediate states also improve as the search continues. Table R5(a) shows how much time early stopping saves and how it affects output quality. Table R5(b) examines whether later intermediate states produce better clean outputs than earlier states at the same noise level.
For early stopping, we evaluated a patience rule that stops after insufficient reward improvement over a specified period. On ImageNet at the 4,096-NFE preset, this reduces average generation time from 45.63 to 41.01 seconds, saving 10.13%, with decreases of 0.26% in HPSv2 and 2.96% in VQAScore. At the 512 preset, the larger time saving of 21.81% comes with a slightly larger reward decrease of 0.86% and a VQAScore decrease of 7.21%. Thus, early stopping offers a controllable quality–time trade-off, rather than preserving every quality metric. We also remark that our multi-robot planning implementation already stops upon finding a feasible trajectory.
Table R5(a). Patience stopping. Each setting uses 10 conditions × 2 seeds. ΔReward and ΔVQAScore are percentage changes relative to full-budget generation, computed as . Reward is GM for CelebA and HPSv2 for ImageNet. Patience settings were selected on validation data and fixed before evaluation; trigger rate is the fraction of stopping runs in which the rule activates.
| Task / NFE preset | Full (sec/image) | Early stop (sec/image) | Time saved | ΔReward (%) | ΔVQAScore (%) | Trigger rate |
|---|---|---|---|---|---|---|
| CelebA / 512 | 16.57 | 15.81 | 4.60% | −0.26% | +9.82% | 20% |
| CelebA / 1,024 | 23.45 | 22.46 | 4.23% | −0.07% | −6.43% | 35% |
| ImageNet / 512 | 12.73 | 9.96 | 21.81% | −0.86% | −7.21% | 100% |
| ImageNet / 4,096 | 45.63 | 41.01 | 10.13% | −0.26% | −2.96% | 55% |
Continued search also improves intermediate-state quality: Table R5(b) shows higher mean completion reward and VQAScore at all six tested task–level combinations. We compare the first visit with the first eligible revisit after 3,072 NFE at the same noise level, estimating the reward of each intermediate state by averaging the terminal rewards of 16 fresh one-step clean completions.
Table R5(b). Quality of clean completions from intermediate states. Each row contains 15 paired states from 5 conditions × 3 seeds at the same noise level, with 16 fresh completions per state. Values compare first → later visits. Reward is GM for CelebA and HPSv2 for ImageNet. Reward improvement is mean ± standard deviation across the three seed means.
| Task / level | Search time: first → later (s) | Reward: first → later ↑ | Reward improvement ± SD ↑ | VQAScore: first → later ↑ |
|---|---|---|---|---|
| CelebA / | 9.10 → 39.47 | 0.616 → 0.983 | +0.367 ± 0.024 | 0.269 → 0.368 |
| CelebA / | 8.77 → 39.45 | 0.541 → 0.979 | +0.439 ± 0.037 | 0.270 → 0.356 |
| CelebA / | 8.43 → 39.61 | 0.500 → 0.976 | +0.476 ± 0.038 | 0.259 → 0.343 |
| ImageNet / | 11.06 → 35.51 | 35.331 → 44.502 | +9.171 ± 0.298 | 0.545 → 0.837 |
| ImageNet / | 10.45 → 35.41 | 32.419 → 42.599 | +10.180 ± 0.627 | 0.436 → 0.839 |
| ImageNet / | 9.84 → 35.52 | 30.096 → 40.380 | +10.283 ± 0.836 | 0.399 → 0.839 |
These results indicate that the benefits of continued search extend beyond the final clean output: at the same noise level, later intermediate states generate clean completions with higher mean reward and VQAScore. In other words, search also improves intermediate states, which can then produce better clean outputs. MDM-VGB [1] shows a related benefit: editing an existing sample can match or improve the quality of generation from scratch while requiring fewer adjusted NFEs, especially when the starting sample already has a high reward. Since CS-VGB can likewise start from an existing clean sample and apply renoising and backtracking, sample editing is an interesting potential application, with its efficiency and content preservation left for future evaluation. We thank the reviewer for suggesting this interesting direction.
(1/4) Response to Official Review by Reviewer jHem
We thank the reviewer for the helpful comments and suggestions. We have addressed them below and hope that our responses provide a clearer understanding of the method and how it can be used in practice.
Answer. We thank the reviewer for these practical suggestions. Our additional experiments support using shared persistence and depth settings, χ=1 and α=0.3, as a starting point across tasks, while choosing candidate-pool sizes LF and LB according to the available computation. Under tighter inference budgets, reducing the depth weight or pool sizes may help the search produce a clean output within the available computation. Once an output is available, early stopping can save generation time if some quality loss is acceptable. If more time is available, continued search can also improve the intermediate states, allowing generation from those states to produce better outputs. These results therefore help users decide when to stop and show how intermediate states can be useful for further generation.
On tuning χ and α. Our guided experiments use χ=1 and α=0.3 across ImageNet, CelebA, and planning, without tuning these two parameters separately for each task. Based on our theoretical design, we expect both χ and α to substantially influence the search dynamics through complementary roles: χ controls how persistently the search maintains its direction, while α controls the balance between denoising toward clean outputs and renoising toward noisier states.
Choosing χ=1 satisfies the persistence condition in Proposition 2.1, which gives an expected hitting time of Θ(J) to the first clean level under its stated assumptions. This motivates strong persistence when obtaining a clean output within a limited budget matters. Consistent with the persistence ablation in Appendix F.6.1, our new sweep in Table R4(a) shows progressively fewer forward-to-backward changes (i.e., switches from denoising to renoising) and more clean-level visits as χ increases. From χ=0 to χ=1, the mean number of direction changes falls from 58.70 to 24.33, while clean-level visits increase from 12.35 to 16.18. This supports using strong persistence to obtain clean outputs more frequently, alongside the reported practical benefits of momentum in MDM-VGB [1] and AR-VGB [2]. We therefore use χ=1 as our default rather than tuning it separately for each task.
Table R4(a). Persistence χ sweep on CelebA at a 4,096-NFE cap. Each setting uses 20 fixed conditions × 3 seeds. Values are mean ± standard deviation across the three seed means.