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

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 ${\lambda }_N=c/\sqrt{N}$, SCG stabilizes this locality-reversibility tradeoff as the number of customers grows.