acceptodds
Under review as a conference paper at ICLR 2027

Cutting in Line: Scheduler-Corrected Gibbs Sampling for State-Dependent Scan Orders

Abstract

The Chinese Restaurant Process (CRP) provides a powerful prior for clustering in applications such as topic modeling, entity resolution, and cell-type discovery, but its standard sequential inference relies on exchangeability (symmetry under permutations) to remain valid. In modern large-scale settings, inference must be distributed and parallel. In such architectures, model state and data are often constrained by physical placement, enforcing strict locality and inducing a state-dependent traversal. We view this traversal rule as a scan scheduler: a mechanism that selects the order in which latent assignments are updated. The locality-driven scheduler studied here is the Same-Group-First (SGF) scan order. We show that SGF causes conventional parallel samplers to systematically underestimate the number of clusters. This bias worsens with dataset size, making common approximations increasingly unreliable and creating a fundamental barrier to scalable CRP inference. We then provide a theoretical explanation: SGF breaks detailed balance via two complementary effects—(i) a microscopic supermartingale drift that accelerates small-cluster depletion, and (ii) a macroscopic combinatorial fragmentation diagnostic that suppresses transitions toward more fragmented partitions. Motivated by this analysis, we propose Scheduler-Corrected Gibbs Sampling (SCG), a full-sweep Gibbs framework that treats the scan order as an auxiliary proposal variable and corrects scheduler state-dependence through an exact reverse-scan Metropolis–Hastings ratio. We instantiate SCG with a Soft-SGF Plackett-Luce scheduler, which interpolates between random scan and SGF-like same-cluster locality while preserving full reverse support. The resulting scheduler-corrected Gibbs procedure restores detailed balance while retaining a tunable preference for locality. With the empirical scaling rule , SCG stabilizes this locality-reversibility tradeoff as the number of customers grows.

Primary area:
probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
Keywords:
Markov chain Monte Carlo, Gibbs sampling, Bayesian nonparametrics, state-dependent scan scheduling, Chinese restaurant process, scalable Bayesian inference

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_DJYfOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper presents Scheduler-Corrected Gibbs Sampling (SCG), a Gibbs sampling method that mitigates the underestimation of the number of clusters caused by state-dependent Same-Group-First (SGF) scan order. The authors first analyze why the SGF scan order can lead to underestimation of the number of clusters. They then propose SCG, which corrects the state dependence of the scheduler through a Metropolis-Hastings correction. To avoid zero reverse support and control the rejection rate, they replace strict SGF with a soft Plackett-Luce scan distribution. Experiments on synthetic CRP settings and the sklearn digits dataset validate the correctness and behavior of the proposed method.

Critical strengths

The core theoretical formulation appears to be sound, and the proposed correction and supporting derivations are generally clear and mathematically coherent.

Critical weaknesses
  1. Unclear motivation for the SGF scan order. The paper assumes that large-scale distributed inference with strict data locality naturally induces a Same-Group-First scan, where all customers assigned to the same cluster are updated contiguously. However, the connection between locality and this specific scan order is not sufficiently justified. In a genuinely parallel setting, different workers may process their clusters at the same time, resulting in an interleaved sequence of customer updates across clusters.

  2. Questionable practical benefit of the proposed correction. Although improving the efficiency of large-scale distributed inference is a central motivation of the paper, the proposed correction introduces additional costs. First, the MH step may reject an entire Gibbs sweep after its computation has already been performed. Second, using a soft scheduler to maintain reverse support also weakens the strict locality of SGF, potentially reducing the parallel efficiency. It is therefore unclear whether the resulting tradeoff offers an efficiency benefit for large-scale parallel inference.

  3. Weak support for the fragmentation diagnostic. The analysis in Sec. 2.3 shows that contiguous partitions become increasingly rare among all possible partitions, but its connection to SGF-induced cluster loss is not sufficiently established. The subsequent empirical analysis only shows a correlation between the proposed fragmentation severity and the cluster retention ratio. However, both quantities may be jointly affected by NN and α\alpha. Therefore, the observed correlation does not establish that fragmentation severity itself causes the under-fragmentation. Compared with the more direct occupancy-drift analysis in Sec. 2.2, it is unclear what additional insight this diagnostic provides

Questions for authors
  1. The paper uses the CRP distribution and related quantities throughout the theoretical analysis without formally introducing the underlying process. A brief definition would improve the clarity of the paper.

  2. The transition from the forward-reverse symmetry of random-scan Gibbs to the proposed MH correction in Sec. 3 could be explained more clearly, including its connection to existing MCMC techniques.

  3. Several equation references are incorrectly formatted as "Eq. equation 1/2/3".

Reviewer_9KrgOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This submission studies bias from state-dependent update orders in Gibbs sampling for distributions governed by the Chinese Restaurant Process (CRP). It shows that persistent Same-Group-First (SGF) schedules, which consecutively update members of the same cluster, underestimate the number of clusters compared with standard updates. The submission proposes the Scheduler-Corrected Gibbs Sampling (SCG), which combines a distribution over soft SGF schedules with a reverse-scan Metropolis–Hastings correction. Experiments use synthetic data and one real-world dataset.

Critical strengths
  1. It seems that the proposed method is novel. Section 3 derives an acceptance probability satisfying detailed balance from the forward schedule probability at the current state and the reverse schedule probability at the proposed state. The resulting Gibbs sampler with soft SGF schedules appears correctly formulated.
Critical weaknesses
  1. A major concern is that the significance of the SGF problem is unclear. The submission motivates SGF through distributed inference in Section 1, but I could not find examples in the cited literature that use such consecutive updates within the same cluster. Standard Gibbs sampling with state-independent ordering should suffice if SGF does not need to be considered. Despite this motivation, the paper provides neither a concrete distributed implementation procedure nor distributed experiments. The real-world dataset contains only 500 points, with no explanation of why distributed inference is needed. Thus, SCG’s practical advantages over standard Gibbs sampling when SGF is needed remain unverified.

  2. The connection between the analysis in Section 2 and SGF is weak. Theorem 1 evaluates the decrease in a table’s population within its update block, but its starting population M_0 can substantially exceed its initial population n_k due to inflows from earlier blocks. Updates can also create new clusters. Thus, it is unclear how local negative drift implies fewer clusters over a sweep or underestimation under the stationary distribution. The fragmentation ratio in Section 2.3 also has an unclear role. Its connection to cluster retention is only empirical, and the proposed scaling rule \lambda=c/\sqrt{N} seems to be defined independently of that section.

Questions for authors
  • Which existing methods or implementations use the same update rule as persistent SGF? For example, Williamson et al. (2013) place same-cluster data on the same processor but use auxiliary variables for distributed updates, apparently yielding a different update rule.
  • Even assuming persistent SGF is common in distributed inference, alternatives do not partition data by cluster. In the setting of topic modeling mentioned in Section 1, Newman et al. (2009) distribute data by document. Ge et al. (2015) also appear not to partition by cluster. These methods should enable distributed inference without SGF schedules dependent on current cluster assignments. What advantages does SCG offer over them?
  • The significance of the same-cluster adjacency lift \Delta A in Figure 4 remains unclear. To assess how much persistent SGF locality is preserved, should the comparison not be against persistent SGF rather than a uniformly random scan order? How far does SCG deviate from persistent SGF?
  • It seems that locality is important for the authors’ intended distributed inference, but increasing \lambda strengthens locality while lowering the acceptance probability. Can the authors evaluate the trade-off between locality gains (e.g., distributed inference efficiency) and additional computation due to rejections?
  • What does the dotted line labeled ''Random scan'' in Figure 4(c) represent? If it is the ARI of Gibbs sampling with uniformly random schedules, why does SCG exceed it even at c=0, where SCG coincides with random scan?

References

  • Newman et al., Distributed Algorithms for Topic Models, JMLR 2009.
  • Ge et al., Distributed Inference for Dirichlet Process Mixture Models, ICML 2015.
Reviewer_SCYuOpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

The paper studies Gibbs sampling for the Chinese Restaurant Process when the scan order depends on the current partition, motivated by distributed samplers that co-locate each cluster's data and parameters. For a Same-Group-First (SGF) scan, which updates all members of one table before moving to the next, it reports that the expected number of clusters is underestimated, increasingly with N (about -32% to -72% on the CRP prior for N = 50 to 500 at α = 10). It offers two explanations: a within-block supermartingale drift of table occupancy (Lemma 1, Thm. 1) and a combinatorial fragmentation ratio for partitions that are contiguous under a fixed order (Prop. 1, Φ_frag). It then proposes Scheduler-Corrected Gibbs (SCG): draw σ ~ s(\cdot | z), run a full single-site Gibbs sweep along σ, and accept with min{1, s(σ^{\leftarrow} | z') / s(σ | z)}, which is exact (Prop. 2). The scheduler is a run-biased Plackett-Luce relaxation of SGF with concentration λ, scaled as λ_N = c/\sqrt{N} to keep acceptance non-degenerate. Validation consists of exact enumeration at N = 4, 5, CRP-prior simulations up to N = 500, and the digits posterior (N = 500).

Critical strengths
  1. System constrained-informed scans can be important and do not receive enough attention. I appreciate that someone is thinking in this area.
  2. The method proposed is simple, it seems to work well and detailed balance is verified.
Critical weaknesses
  1. My main concern is about motivation of the described distributed setting, the necessity of implementing SGF in a distributed setting ( I suspect there are much more efficient options) and the severe lack of clarity about which version of SGF is implemented. Unlike what is described in the paper SGF is not a scan order, but a whole family. It depends on a never-discussed table ordering rule. I suspect that different table ordering rules might yield completely different biases than the unconditional statement of “systematically underestimate” might suggest. Please see my questions below.
  2. As far as I can tell, the work is motivated by a distributed implementation but the authors never experiment or simulate one (or argue about its relative superiority. Furthermore, locality necessarily vanishes at scale if we want the proposed method to not reject every proposal. As a result, I suspect that the savings from the reduced amount of communication of SGF are severely reduced for large scales when λ=1/sqrt(N). For large problems (which might motivate distributed implementations) we essentially get randon-scan Gibbs.
Questions for authors

Questions that could change my assessment:

  1. What is the exact SGF rule: the order of tables, the order within a table, and the identity of a new table? Is it id order with smallest-free-id reuse? Please reconcile l. 76 and 153-155 with l. 157-158, and report the bias under a label-free rule (e.g. tables ordered by smallest member index) and under random table order, on the prior across N and on digits.
  2. Does the mechanism analysis predict any difference between SGF and random-scan Gibbs? If not, what does explain the underestimation?
  3. Is Theorem 1 informative at the scales where the reported bias is largest? Because δ = α/(α+N-1) comes from the bound M_j \leq N, any guaranteed loss u < Lδ leaves a failure probability of at least exp(-2Lδ^2). At N = 500, α = 10 this is about 0.68 even for a block of all 500 customers and about 0.97 for a 40-customer table, while M_L - M_0 \in [-L, 0] holds trivially. Are there settings of (N, α, n_k) relevant to large problems where the bound gives a non-trivial guarantee? If a sharper drift such as -(α+N-M_j)/(α+N-1) is needed, please state that version and explain how it distinguishes SGF from a scan that resamples the same customers in a different order.
  4. Is sequential SGF what a distributed system would run? A global sweep that updates one table at a time keeps one worker busy, so it is no faster than a single machine. A real system would let every worker update its own customers concurrently, which is not a permutation scan and is not covered by s(σ | z). And is co-location needed at all? Every update reads all clusters wherever the data sit. Please give a regime where this layout beats keeping data in place (parameter servers; Williamson et al., 2013; Chang & Fisher, 2013), and argue about the wall-clock or communication gain there. A state-independent alternative seems simpler: shard the data to workers by a fixed assignment and let each worker scan its own shard. The scan order is then independent of z, so a sweep is exact without any correction. Running the workers concurrently brings the usual staleness issues of asynchronous Gibbs, but so would any concurrent version of the cluster-co-located layout. Why is a cluster-dependent layout needed?
  5. Can you argue about the effective sample size per sweep, or per unit time, of SCG versus random-scan Gibbs?

Clarifications:

  • how the distributed layout handles federated settings, which the paper cites, where data cannot move
  • the initialization of the CRP-prior chains
  • the run budget for Fig. 1(b)
  • how the 500 digits were selected and scaled

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.