acceptodds
Under review as a conference paper at ICLR 2027

Clean-Sample Markov Chain for Reward-Guided Discrete Diffusion Sampling

Abstract

Discrete diffusion models have recently emerged as a powerful class of generative models for chemistry and biology data. In these fields, the goal is to generate various samples with high rewards (e.g., binding affinity between peptides and proteins), making reward-based guidance crucial. Most existing methods are based on guiding the diffusion model using intermediate rewards but tend to underperform since intermediate rewards are noisy due to the non-smooth nature of reward functions used in scientific domains. To address this, we propose Clean-Sample Markov Chain (CSMC) Sampler, a method that performs effective test-time reward-guided sampling for discrete diffusion models, enabling local search without relying on intermediate rewards. CSMC constructs a Markov chain of clean samples using the Metropolis-Hastings algorithm such that its stationary distribution is the reward-weighted distribution. We design a proposal distribution by sequentially applying the forward and backward diffusion processes, making the acceptance probability tractable. Experiments on peptide and biological sequence with various reward functions demonstrate that our method consistently outperforms prior approaches that rely on intermediate rewards.

Primary area:
generative models
Keywords:
reward-guided sampling, inference-time scaling, diffusion models

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_tZcDOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

The paper presents an MCMC algorithm for sampling from a tilted distribution of discrete diffusion models, i.e. p(x) e^{-r(x)} where p(x) is a pretrained diffusion model and r(x) is an external reward model. The key motivation is that many reward tilting methods rely on denoising predictions which may not land in the clean data distribution space, especially for discrete data modality. The proposed method instead construct a diffusion-based proposal by first denoise a noisy sample and then renoise it and derive a Metropolis Hasting (MH) kernel. While the MH kernel is intractable, they develop tractable approximations. In the experiment they demonstrate better pareto frontier in {performance metric, inference time} across inference-time steering methods on peptide generation and biological sequence generation.

Critical strengths
  • The paper is written very nicely and easy to follow.

  • The proposed method is easy to implement; empirically, it seems to work well.

  • THe proposed method does not require differentiable reward, nor it requires backpropagating through the denoiser network which can be memory efficient.

Critical weaknesses
  • My biggest concern of the paper is the novelty. There are a few existing works earlier in the year that use a very similar denoise-and-renoise MCMC kernel for reward tilting or for sampling from unnormalized densities [1,2,3]

  • I also didn't find a related work discussion.

  • The MH kernel approximation deserves some more discussion rather than calling it a simplified expression, as it depends on the diffusion model training error and the SDE discretization error.

  • On a related note, I also found theorem 1 more or less a standard result of training a discriminator to estimate a density ratio. Also the estimator behind thm. 1 is not really used so I'd consider Thm. 1 a bit cosmetic. I suggest the authors to remove it unless it's proven to be empirically relevant.

[1] Sampling Data with Chains of Forward-Backward Diffusion Steps Hyunmo Kang, Noam Itzhak Levi, Corinna Elena Wegner, Daniel J. Korchinski, Matthieu Wyart

[2] Exact Global MCMC with Denoising Diffusion Mitch Hill

[3] Markov Chain Monte Carlo with Diffusion Paths Han Chen, Sifan Liu, Jun Yang

Questions for authors
  • Can the authors report the MH acceptance ratio across sampling steps as well as diffusion time tt in the reported experiments? It'd be helpful to gauge the efficiency of the method.

  • A related question is in the scenario where the base model has low probability in high reward region. As the proposed method does not utilize gradient information, how would the authors expect its performance when compared to gradient-based methods?

  • The results in Fig. 3 look promising. However, I wonder why if the authors can provide some insights on why the proposed method have better results given the same runtime?

4 comments
AuthorsOpenReview ↗

Response (1/2)

We thank the reviewer for the review. We address the concerns below.

W1. Novelty and relation to existing works.

We thank the reviewer for bringing these works to our attention. Although these works are related, we would like to first point out that the cited works are recent unpublished works which should not warrant a basis for rejection based on the ICLR reviewer guidelines (last FAQ). Furthermore, [2] and [3] are theoretical works that only consider regular diffusion sampling on toy datasets and do not consider the task of reward-guided discrete diffusion. As such, the setting is very different from our work.

The main contribution of our paper is also different from [1]. Our main contribution is reformulating reward-guided discrete diffusion sampling as an iterative search over clean samples. This challenges the current paradigm where guidance is performed along the denoising trajectory and rely on intermediate rewards, which we show to be unreliable for scientific tasks. In contrast, [1] does not identify the intermediate reward bottleneck of reward-guided diffusion samplers and instead focus on analyzing the properties of MCMC with forward-backward diffusion proposal.

Regardless, we have included a discussion of these works in the related work section (App. C) of the revised version.

W2. Missing related work

We thank the reviewer for bringing this to our attention. In the original draft of the paper, the related work discussion was combined with the background section. In Sec. 4 and App. C of the revised version, we have added a separate related work section discussing training-based guidance methods, training-free guidance methods, and MCMC diffusion samplers.

W3. Discussion on the MH kernel approximation

As the reviewer correctly notes, the theoretical guarantee depends on the diffusion model training error and number of integration steps during sampling. These are practical considerations which may affect the stationary distribution of CSMC. We additionally report the discrepancy between the simplified and discriminator-corrected acceptance probabilities for the target chain with β=10−5\beta=10^{-5} in Fig. B.3 (page 22). As shown, the acceptance probabilities are very similar for both cases for almost all CSMC iterations. The log acceptance probability in Eq. 2 is affected by two terms, the temperature-weighted reward difference and the discriminator correction term. When the temperature is low (which is the case in practice), the contribution of the first term r(x′)−r(x)β\frac{r(x')-r(x)}{\beta} significantly outweighs the discriminator term and the discriminator term can be essentially ignored. While we acknowledge that parallel tempering uses some higher temperature chains, our target chain uses low temperature which supports the use of our simplified acceptance probability.

W4. Theorem 3.1 is a bit cosmetic.

We thank the reviewer for the suggestion. We have included theorem 3.1 for completeness since it is used when comparing the simplified and discriminator-corrected acceptance probabilities. With our new discussion, we have a direct comparison between the acceptance probabilities in Fig. B.3. However, if the reviewer still believes it is better to move theorem 3.1 to the appendix, we will do so in the revised version.

AuthorsOpenReview ↗

Response (2/2)

Q1. Can the authors report the MH acceptance ratio across sampling steps as well as diffusion time t in the reported experiments?

We report the acceptance rate across sampling steps (iterations) and diffusion time in Fig. E.1 (page 27) of the revised version. As shown in the figure, the acceptance rate is initially high as the proposed samples are more likely to have higher rewards than the current sample. The acceptance rate decays over the iterations and converges to around 15%. The acceptance rate is also higher for smaller forward noising times as it encourages local exploitation around the current sample.

Q2. How does the authors expect the performance to compare to gradient-based methods?

We thank the reviewer for bringing up this point. First, we would like to note that it is non-trivial to extend CSMC to utilize gradient information since the clean-sample score ∇x0log⁡p(x0)\nabla_{x_0} \log p(x_0) is intractable (which is why score-based diffusion models use the noisy score ∇xtlog⁡pt(xt)\nabla_{x_t} \log p_t(x_t)) instead. However, even if gradient information is available, these methods may not be useful due to (1) gradient information not helping in exploring disconnected modes and (2) backpropagation being computationally expensive. As we have shown in Fig. 3, gradient-based SMC does not perform well due to the computational bottleneck introduced by backpropagation.

Q3. Why does CSMC have better results given the same runtime?

As we have explained in L458-461, CSMC is more efficient than BoN since CSMC provides intermediate guidance via the forward-reverse diffusion proposal and the accept/reject step. This allows CSMC to efficiently explore locally around high-reward samples. CSMC is also more efficient than methods based on intermediate rewards (SMC, SVDD, RERD) since inaccurate intermediate rewards may mistakenly discourage exploration around high-reward regions (L170-171). Finally, although DTS also uses clean rewards, it requires building an entire search tree which is less efficient than CSMC's forward-reverse diffusion proposal (L455-457).


[1] Kang, Hyunmo, et al. "Sampling Data with Chains of Forward-Backward Diffusion Steps." arXiv preprint arXiv:2605.27006 (2026).

[2] Hill, Mitch. "Exact Global MCMC with Denoising Diffusion." arXiv preprint arXiv:2609.00279 (2026).

[3] Chen, Han, Sifan Liu, and Jun Yang. "Markov Chain Monte Carlo with Diffusion Paths." arXiv preprint arXiv:2607.11631 (2026).

Since less than two days are left in the reviewer-author discussion, we would like to kindly remind the reviewer to let us know if your concerns are addressed or if there are any remaining concerns after our response. Thank you.

I would like to thank the authors for their reply. I have increased my score to 3.

Reviewer_qLvPOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

This paper introduces Clean-Sample Markov Chain (CSMC) Sampler which performs a test-time reward-guided sampling for discrete diffusion models. CSMC constructs a Markov chain of clean samples using the Metropolis-Hastings algorithm. The proposal distribution is built by sequentially applying forward diffusion and reverse diffusion, and the acceptance probability is simplified under a matching-marginals assumption. Experiments on peptide generation and regulatory DNA sequence design show favorable reward–runtime trade-offs relative to several inference-time guidance methods including BoN, SMC, SVDD, RERD, DTS, and Beam Search.

Critical strengths
  1. Well-motivated problem. The paper correctly identifies that intermediate rewards in scientific domains (peptide binding, DNA) are highly non-smooth and noisy — a single token change can result in drastically different rewards. This is a genuine practical concern, and the framing of "why not just do local search in clean sample space" is intuitive and compelling.

2.A sound idealized construction. Under the stated conditional-consistency assumption, reversibility of the forward–reverse proposal provides a principled basis for reward-only acceptance.

Critical weaknesses

1.The theoretical guarantee does not directly cover the practical sampler. The cancellation argument requires the exact posterior associated with the same pretrained distribution and forward kernel. The practical implementation instead uses learned, finite-step reverse kernels. Appendix B.1 acknowledges that imperfect denoisers and different sampling procedures may violate this identity. Nevertheless, Section 3.4 states that the implemented chain has the desired stationary distribution without restating this qualification. This gap is particularly important because the DNA experiments use only one reverse step. Similar rewards with and without discriminator correction do not establish similar stationary distributions.

2.The discriminator experiments do not validate the simplified sampler’s distributional correctness. The discriminator distinguishes forward and reversed joint proposal distributions. Its accuracy therefore measures their distinguishability, rather than the similarity between individual original and proposed samples. Figure B.1 shows substantial distinguishability in the few-step regime, particularly for DNA. Assuming these are independent test-set results, this suggests non-negligible joint asymmetry precisely where the practical sampler operates.

Questions for authors

The paper's central claim is that CSMC outperforms baselines “because it uses clean rewards instead of intermediate rewards”. However, the ablation study (Fig. 4) only varies hyperparameters of CSMC itself — it does not include a "disentanglement" experiment that isolates which component drives the gain. Without this, it is impossible to tell whether the gain comes from the paper's core thesis (clean rewards are better) or from some other component (e.g., parallel tempering alone).

  1. If I take SMC and add parallel tempering, does it also get this much better?
3 comments

We thank the reviewer for their constructive comments. We address the concerns below.

W1-W2. Theoretical guarantee does not directly cover the practical sampler/Discriminator experiments do not validate the simplified sampler's distributional correctness.

As the reviewer correctly notes, the theoretical guarantee may not directly hold for practical samplers with few integration steps. We clarify that we included the discriminator as a way to model the exact the acceptance probability for this reason (Sec. 3.3, L237-259). Although the discriminator gives a theoretically sound way to model the exact probability in the ideal case, the discriminator obtained from training may not be the optimal discriminator. In practice, the simplified acceptance probability provides a way to achieve the same performance as the discriminator without additional training. We will also show that the simplified probability matches the discriminator-correct probability when using small temperatures in the additional experiments below.

We additionally report the discrepancy between the simplified and discriminator-corrected acceptance probabilities for the target chain with β=10−5\beta=10^{-5} in Fig. B.3 (page 22). As shown, the acceptance probabilities are very similar for both cases for almost all CSMC iterations. The log acceptance probability in Eq. 2 is affected by two terms, the temperature-weighted reward difference and the discriminator correction term. When the temperature is low (which is the case in practice), the contribution of the first term r(x′)−r(x)β\frac{r(x')-r(x)}{\beta} significantly outweighs the discriminator term and the discriminator term can be essentially ignored. While we acknowledge that parallel tempering uses some higher temperature chains, our target chain always uses low temperature where the joint asymmetry of the forward and reverse distributions have marginal effect on the final acceptance probability.

Q1. Disentanglement between the MCMC techniques and the shift to clean-rewards

We thank the reviewer for their suggestion. First, we clarify that parallel tempering cannot be applied to SMC since parallel tempering is designed for MCMC algorithms, not SMC algorithms. Instead, we have already applied a tempering algorithm to SMC by annealing the temperature across the denoising process, as describe in L1237-1238 of App. D.2.

As requested by the reviewer, we also include an additional experiment in Fig. 5 of the revised version, where we compare against a variant of CSMC that uses intermediate rewards instead of clean rewards. For this variant, we run a denoising process but, at a fixed interval of diffusion steps, we iteratively apply forward-reverse diffusion on a noisy sample xtx_t to obtain new noisy sample xt′x_t' and accept or reject with probability min⁡(1,exp⁡((r(xt′)−r(xt))/β)\min(1,\exp((r(x_t')-r(x_t))/\beta), where r(xt)r(x_t) is the intermediate reward. This is the same as applying CSMC on noisy samples at intermediate times. As shown in Fig. 5, CSMC using clean rewards outperforms CSMC using intermediate rewards, showing that the choice of using clean reward is crucial to the performance of CSMC.

Related Work Section

In the original version, we combined the related work into the background (Sec. 2). In the revised version, we have included a separate related work section in Sec. 4, and a more detailed discussion of related work in App. C.

Since less than two days are left in the reviewer-author discussion, we would like to kindly remind the reviewer to let us know if your concerns are addressed or if there are any remaining concerns after our response. Thank you.

The authors clarified my concerns. I increased the score.

Reviewer_kP9WOpenReview ↗
Rating
1
Confidence
3
Informativeness
1
Presentation
3
Soundness
2
Read review
Paper summary

This work proposes an MCMC approach to sampling from the reward-tilted distribution p(x0)exp⁡(r(x0)/β)p(x_0) \exp(r(x_0)/\beta), given a pretrained discrete diffusion model which samples from p(x0)p(x_0). Existing methods typically rely on reward-guidance using estimates of reward computed on intermediate samples, but these are unreliable for discrete data (particularly for chemical and biological applications). The proposed method uses the pretrained model to construct a proposal for MCMC over clean/final tokens instead, to sidestep this issue. The proposal consists of noising an initial sample x0x_0 to a randomly sampled time-point tt, and then denoising it back to obtain x0’x_0’. Computing the associated acceptance ratio involves an intractable term, which simplifies to 0 for a perfectly trained diffusion model. The method is used with parallel-tempering to draw samples from the target distribution, and is evaluated on peptide generation and biological sequence design. The results indicate that the method achieves the highest reward for matched wall-clock times, compared to baselines.

Critical strengths
  • The motivation and justification of the problem with intermediate rewards is helpful (eg. the Spearman correlations in Fig 2)
  • The ablations of section 4.3 are helpful in illustrating the utility of the method
  • The ability of the algorithm to be successfully composed with fine-tuning methods is useful
  • The work is well-written, with logical organization
Critical weaknesses
  • The work is missing important discussions of prior work:
    • Zhang et al., (2022) (Generative Flow Networks for Discrete Probabilistic Modeling) - the section on using GFlowNets as MCMC transition kernels discusses a very similar algorithm to the one presented in this work (with straightforward adaptations to the masked diffusion case). Proposition 2 also notes the analog of the simplified acceptance ratio for perfect reversal (although with a slight difference due to the overall target not being a tilted reward). Due to this, the novelty of the current work is limited.
      • This algorithm is also used for local search in Kim et al., (2024) (section 4.2)
    • IterRef (Lee et al. 2025) - which uses a very similar noising and denoising proposal within Metropolis-Hastings. Although that method doesn’t restrict the proposals to clean samples and uses intermediate reward estimates, it is an important point of reference, and should be compared as a baseline
  • Additionally, it seems the temperatures used for different baselines are mismatched, and this could be a confounding factor in the reward performance. It would be helpful to rule out the temperature's effect for these experiments. The appendix mentioned that certain temperature values caused mode collapse for SMC, but it would be helpful to see the evidence directly.
  • Scaling performance with respect to other compute metrics, such as denoiser calls, and reward-calls, would be helpful in giving a more comprehensive picture of the work

Zhang, D., Malkin, N., Liu, Z., Volokhova, A., Courville, A., & Bengio, Y. (2022). Generative Flow Networks for Discrete Probabilistic Modeling. arXiv:2202.01361 http://arxiv.org/abs/2202.01361

Kim, M., Yun, T., Bengio, E., Zhang, D., Bengio, Y., Ahn, S., & Park, J. (2024). Local Search GFlowNets. arXiv:2310.02710 http://arxiv.org/abs/2310.02710

Lee, S., Kim, S., Kim, S., Park, J., & Park, D. (2025). Effective Test-Time Scaling of Discrete Diffusion through Iterative Refinement. arXiv:2511.05562 http://arxiv.org/abs/2511.05562

Questions for authors
  • How is wall-clock measured for SMC methods? Eg. does it take into account parallelization across particles?
5 comments
AuthorsOpenReview ↗

Response (1/2)

W1a. Connection with GFlowNet works [1,2]

We strongly emphasize that our main contribution lies in challenging the current paradigm in reward-guided diffusion samplers that rely on intermediate rewards, which we show is unreliable. To this end, we reformulate reward-guided discrete diffusion sampling as an iterative search over clean samples by using MCMC techniques. We describe the differences between the cited works and our method in more detail below.

The cited works use the forward-reverse MCMC transitions for EBM training [1] and GFlowNet training [2]. On the other hand, our work addresses inference-time reward guidance using pretrained discrete diffusion models without additional training. Our main contributions are (1) characterizing the unreliability of intermediate rewards in scientific domains, (2) constructing a novel clean-sample Markov chain sampler to mitigate the use of inaccurate intermediate rewards, and (3) using the forward-reverse diffusion kernel to practically implement this idea. The context in which our work is developed is completely different to the cited works. The cited works do not make a connection to discrete diffusion models. They do not explore the issues with intermediate rewards, and they do not propose the shift to clean-sample Markov chains as the solution.

Novelty can come from identifying a connection between existing algorithms and a new domain where those algorithms can be applied to. For example, initial RL fine-tuning methods for diffusion models do not invent new RL algorithms but they instead view diffusion sampling as a policy and apply classical algorithms such as REINFORCE and PPO to optimize the diffusion models. The algorithm itself is not new but the new perspective connecting RL techniques to diffusion models is novel. Similarly, SMC-based diffusion guidance applies classical particle-based sampling into diffusion models. The novelty and impact of these works come from identifying a problem in the diffusion domain and formulating the problem in a way that can be solved by those classical algorithms. The novelty of our work should be assessed using the same basis: we identify a limitation of current intermediate-reward guidance methods, propose a new clean-sample framework to address this limitation, and demonstrate that classical MCMC techniques can be used to implement this new framework.

We recognize the shared algorithmic similarities and have included a discussion of these works in App. C of the revised version. However, the cited works do not investigate the problem with intermediate rewards in discrete diffusion nor propose a solution to that problem. In light of these core differences, we respectfully ask the reviewer to reconsider our work in the context of its contributions to inference-time guidance of discrete diffusion models.

W1b. Comparison with IterRef [3]

We thank the reviewer for bringing this work to our attention. We would like to first note that IterRef [3] is a non-archival workshop paper not published in a peer-reviewed conference or journal. We were not aware of this work at the time of submission, and, in light of its non-archival status and the final FAQ in the reviewer guidelines (https://iclr.cc/Conferences/2027/ReviewerGuidelines), we respectfully ask that the absence of this comparison in the original submission not be considered a weakness of our work. We have added a comparison in the revised manuscript.

We compare with IterRef in Fig. 3 of the revision. As shown, CSMC outperforms IterRef for all rewards except the heldout permeability reward. Since IterRef does not perform well on the given permeability reward, its performance on the heldout permeability reward seems to be due to inherent characteristics of the heldout reward model rather than the algorithm itself.

AuthorsOpenReview ↗

Response (2/2)

W2. Temperature

We thank the reviewer for their suggestion. For a fair comparison, we include a new scaling plot in Fig. E.3 of App. E (page 29) where we matched the temperatures of all methods to be the same as CSMC (β=10−5\beta=10^{-5}) and noising time window of RERD to be the same as CSMC as well. As shown, CSMC achieves the Pareto front across all rewards except heldout permeability (as explained in our response to W1b above).

We also show in the table below that using smaller temperatures results in mode collapse for SMC. On binding affinity and permeability, using low temperatures significantly reduces the diversity and number of unique samples. On HepG2 and SK-N-SH, using low temperatures harm the performance on both given and heldout rewards, possibly due to lack of exploration. Overall, using temperatures of β∈{0.1,0.2}\beta \in \{ 0.1, 0.2 \} result in the best performance-diversity tradeoff for SMC, which we also use for our main experiment.

Table 1. SMC with varying temperatures β\beta

methodβ\betaNFEgivenheldoutuniquediversity
Binding Affinity1e-520488.731798.507770.9220.554055
Binding Affinity0.0120488.702618.544680.9450.585713
Binding Affinity0.120488.615128.515670.9300.571585
Binding Affinity0.220488.662058.508990.9840.634628
Permeability1e-52048-7.36224-10.46490.9380.574231
Permeability0.012048-7.36964-10.59060.9300.563768
Permeability0.12048-7.37942-10.73110.9690.600351
Permeability0.22048-7.38167-10.79230.9380.570861
HepG21e-520485.225134.700321.0000.742434
HepG20.0120485.468864.996851.0000.742341
HepG20.120485.644055.090091.0000.741546
HepG20.220485.558315.125751.0000.7406
SK-N-SH1e-520486.449635.856721.0000.744852
SK-N-SH0.0120486.413985.911111.0000.744537
SK-N-SH0.120486.485115.796081.0000.744716
SK-N-SH0.220486.827136.295771.0000.743207

W3. Scaling performance with respect to denoiser calls and reward calls

We thank the reviewer for this suggestion. In the original paper, we only include scaling performance with respect to wall-clock time because wall-clock time takes into account both denoiser and reward calls. As requested, we additionally include the scaling performance with respect to denoiser and reward calls in Fig. E.2 (page 27) of the revision. As shown, CSMC achieves the Pareto front for both denoiser calls. CSMC also achieves the Pareto front for reward calls for MPRA rewards.

Q1. How is wall-clock measured for SMC methods?

Yes, parallelization is taken into account for all methods by batching the inputs. The batch size for all methods is fixed to be the number or parallel tempering chains used by CSMC.

Related Work Section

In the original version, we combined the related work into the background (Sec. 2). In the revised version, we have included a separate related work section in Sec. 4, and a more detailed discussion of related work in App. C.


[1] Zhang, Dinghuai, et al. "Generative flow networks for discrete probabilistic modeling." ICML 2022.

[2] Kim, Minsu, et al. "Local search gflownets." ICLR 2024.

[3] Lee, Sanghyun, et al. "Effective test-time scaling of discrete diffusion through iterative refinement." arXiv preprint arXiv:2511.05562 (2025).

Since less than two days are left in the reviewer-author discussion, we would like to kindly remind the reviewer to let us know if your concerns are addressed or if there are any remaining concerns after our response. Thank you.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.