acceptodds
Under review as a conference paper at ICLR 2027

Why Initial Randomness Matters in Parallel Markov Sampling

Abstract

Parallel sampling aims to accelerate sequence generation by filling multiple positions per round. Yet even when every conditional distribution is known exactly, the choice of when to sample each position can limit the accuracy achievable within a fixed number of rounds. In our work, we show that randomizing the first set of sampled positions can achieve accuracy beyond every deterministic adaptive schedule for known stationary Markov targets, without increasing the round budget. Our samplers draw coordinate values independently within each batch from exact single-coordinate conditional distributions, never revise sampled values, and use at most rounds on every path. We establish this advantage for every reversible finite-state Markov chain with strictly positive transition probabilities and dependence between successive states. For each such chain, under a suitable scaling of sequence length and round budget, initial randomization yields vanishing total variation error, while the optimal deterministic adaptive error remains bounded away from zero. To quantify this advantage in forward KL divergence, we obtain matching bounds for positively correlated binary chains: over the full adaptive policy classes, randomization reduces the optimal divergence from the target to the output distribution by a factor of order in a fixed-kernel, bounded-error regime. To determine whether this randomness can be deferred, we specialize further to the symmetric binary chain in this regime and characterize how the entropy of the first-round position set controls optimal error. Attaining the optimal randomized error order requires at least bits of this entropy, even with unrestricted later scheduling randomness and adaptation to sampled values: this initial randomness cannot be deferred.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
parallel sampling, Markov chains, randomized scheduling, adaptive policies, information theory

Reviews

Among:
Shape:
1234this paper, Bottom 10%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 1.67 over 3 reviews, above 10% of the others.
Reviewer_yRKwOpenReview ↗
Rating
1
Confidence
2
Informativeness
1
Presentation
1
Soundness
1
Read review
Paper summary

The paper shows whether randomizing the order of parallel sampling improves the accuracy of a sampler. The authors consider a specific case where the sampler is non-correcting, RR-step, with exact conditional distributions. The paper shows that randomized sampler can be superioir to deterministic samplers with quantitative results on forward Kl and entropy. Lastly, the authors propose a sampler that combines randomly choosing the initial batch and filling the midpoint values.

Critical strengths

S1. The paper studies the theoretical behaviors of randomized and deterministic sampler in a different settings. The theoretical results clearly show why randomized sampler can improve sampling accuracy which the deterministic sampler counterpart cannot achieve.

Critical weaknesses

W1. Restrictive assumptions. The analysis assumes access to exact conditional distributions, independent sampling, and a non-correcting sampling that does not revise already sampled values. The paper does not establish whether the presented superiority of randomness persist with approximate learned conditionals or sampling procedures that allow revisions. Therefore, the setups considered in the paper remain relatively simple and far from real world applications. The randomized error bounds are established primarily for positively correlated binary chains, while the initial-entropy theorem is restricted to symmetric binary chains. Extending these conclusions to broader dependencies would strengthen the paper. Overall, I find the presented results of the paper lack practical usability in real world scenarios.

W2. Limited practical evaluations. The evaluations focus on short binary chains and provide useful validation results through exact comparisons. However, the paper does not evaluate the proposed sampler on learned generative models or realistic datasets, nor compare its practical performance with confidence-based or entropy-based scheduling methods which are widely used in practice. Consequently, the experiments provide limited evidence that the theoretical advantage translates into improved sampling quality or efficiency in practical applications.

Questions for authors

None. Please see the weaknesses.

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

This paper essentially studies the error resulting from parallel unmasking in masked diffusion models. In this scenario, assuming a perfect diffusion model, the unmasking of multiple tokens at once results in sampling error. The paper shows that, for a target distribution with a known Markov structure, the lower bound on sampling error from deterministic unmasking strategies is beaten by certain randomized unmasking strategies. The work constructs a decoding strategy to demonstrate these bounds are achievable, and further proves that to obtain this increased accuracy, a certain amount of randomness in the first sampling step is necessary.

Critical strengths
  • The work is useful for studying the parallelization error in masked diffusion models
    • In this context, the utility of randomness implied by the results could be impactful for unmasking heuristic design
Critical weaknesses
  • The work is very unclear and difficult to follow, so my understanding of the theory is limited. In my opinion the work requires very thorough rewriting to be more understandable:

    • Some symbols are not clearly defined beforehand - for instance the paragraph at lines 59-66 doesn’t define n,sn,s
    • The work never properly motivates parallel sampling, but clearly has masked discrete diffusion in mind with the setting it studies (chains which have tokens that are revealed once, and remain fixed on those tokens). This is in contrast to prior work, which typically does clearly motivate the problems they study
    • When symbols are defined, an intuitive description is rarely given. For instance, nn is not explained as being the sampled sequence length (under eg., a masked diffusion framework)
    • The work is very difficult to parse with heavy usage of specific jargon which isn't clearly defined (eg. bisection, converse, certificate, etc.). In my opinion, the writing has a very unrefined AI-like quality in its use of jargon
  • The target being induced by a Markov chain should be justified for realistic datasets. As it stands, it reads as a somewhat artificial assumption the analysis depends on

  • In practice for masked diffusion models - heuristics such as confidence and entropy are used to inform unmasking. The significance of the results in this work for these common heuristics (or more randomized versions of them) is unclear - see the question

Questions for authors
  • Is there any understanding of whether randomized versions of common decoding heuristics (eg. such as adding Gumbel noise to orders extracted using low confidence, or entropy) obtain error rates which beat deterministic unmasking?
Reviewer_5XzeOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
3
Soundness
3
Read review
Paper summary

This paper studies round-limited parallel sampling of a stationary finite-state Markov path using exact singleton conditionals, irrevocable reveals, and independent draws within each selected batch. It proves that a hidden random first-round phase followed by conditional bisection can approach the target while every deterministic value-adaptive policy with the same pathwise round cap remains separated, and it derives matching Θ(t)\Theta(t) versus Θ(t/L)\Theta(t/L) KL orders for positively correlated binary chains. It also characterizes the required first-set entropy, extends the qualitative separation to strictly positive reversible finite-state chains, and supplies exact small-instance certificates. The output-marginal mixture converse is a genuine and technically strong contribution, although the result is tied to a narrow oracle interface and an extreme asymptotic regime.

Critical strengths
  1. The conceptual novelty is strong. Prior work characterizes deterministic adaptive schedules through conditional total correlation (Wen et al.), optimizes inference schedules (Chen et al., COLT 2026), and develops exact Markov bisection (Bansal et al.). This paper addresses the distinct difficulty of lower-bounding the marginal law of a hidden mixture of schedules, where lower bounds for individual schedule-conditioned components do not survive averaging.
  2. The paper cleanly separates deterministic adaptivity, later randomness after a fixed first set, and genuinely random initial scheduling. The first-set entropy frontier Θ(tmax⁡{e−h,1/L})\Theta(t\max\{e^{-h},1/L\}) is substantially sharper than presenting only a randomized construction.
  3. The proof package is unusually complete: it respects pathwise round caps, establishes matching binary KL rates, gives a separate Hellinger/TV argument, transfers the separation to general reversible finite-state chains, and supports the asymptotics with exact two-round optima and certified three-round comparisons. A detailed proof audit did not reveal a substantive error.
Critical weaknesses
  1. The model is far removed from deployed masked-diffusion sampling. It assumes a known stationary Markov target, exact singleton conditional probabilities, independent within-batch oracle draws, irrevocable reveals, and no denoiser error, remasking, rejection, speculative correction, or learned-policy error. These assumptions isolate scheduling error but exclude many mechanisms used to correct parallel-sampling mistakes. No neural-model experiment shows that the advantage survives an approximate conditional oracle.

  2. The sharp asymptotic separation occurs at an extreme sequence-length scaling. With L=2R−1L=2^{R-1}, n=(s+1)Ln=(s+1)L, and t=sρ2Lt=s\rho^{2L}, keeping tt nontrivial for fixed 0<ρ<10<\rho<1 requires s≍ρ−2Ls\asymp\rho^{-2L}. The paper's explicit R=9R=9 witness has n≈6.6241×10268n\approx6.6241\times10^{268}. The exact n=4,6,8,12n=4,6,8,12 certificates demonstrate a genuine finite effect, but only by modest factors, and one additional deterministic bisection round removes the asymptotic advantage. The result therefore establishes a sharp same-depth phenomenon, not yet a practical latency improvement.

  3. The gain depends critically on hiding and marginalizing the scheduling tape. The tape-conditioned or joint schedule-output divergence remains at the deterministic fixed-phase scale; cancellation appears only in the returned output marginal. If random seeds, reveal times, confidence scores, or scheduling metadata are visible to an evaluator, model, or downstream consumer, the claimed gain may disappear. The paper needs a clearer operational justification for why output-only forward KL is the relevant criterion and whether the policy ordering persists for reverse KL or application-level quality metrics.

  4. The matching quantitative theory is narrower than the opening generality. Matching randomized KL bounds are proved for positively correlated binary chains and certain independent-product extensions, while the general reversible finite-state theorem gives a randomized construction and deterministic lower bound without a matching randomized converse. The entropy frontier is restricted to the symmetric binary case, and constants in the finite-state transfer can deteriorate with stationary imbalance, spectral structure, and kernel extrema. Negative correlation and more general alphabets therefore do not receive the same sharp characterization.

  5. Reproducibility and exposition could be improved. The proof chain contains many nested constants and transfers among KL, moments, Hellinger affinity, TV, and entropy. The finite rational and interval certificates rely on a separate artifact, and the paper does not give enough self-contained pseudocode to reconstruct every certificate directly. A theorem-dependency map and independently checkable certificate code would materially improve auditability.

Questions for authors
  1. What realistic application exposes only the final sequence while hiding all scheduling metadata, making marginal rather than joint schedule-output divergence the appropriate criterion?
  2. Which separation results survive ε\varepsilon-inexact singleton conditionals, correlated within-batch proposals, remasking, or rejection/correction steps?
  3. Can the authors quantify the smallest realistic sequence lengths at which randomized policies beat the best deterministic policy by factors of 2, 4, or 8?
  4. Can the matching randomized converse and entropy frontier be extended beyond positive binary/product targets to general reversible chains or negative eigenmodes?
  5. Will the authors release independently checkable code and rational certificates for the finite dynamic programs?

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.