Paper deep dive

The information geometry of product-reference discrete diffusion: Interaction growth complexity and optimal scheduling

Martin J. Wainwright

Year: 2026Venue: arXiv preprintArea: stat.MLType: PreprintEmbeddings: 121

Intelligence

Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 94%

Last extracted: 9/1/2026, 5:16:20 AM

Summary

This paper introduces Interaction Growth Complexity (IGC), a path-based measure of data geometry used to characterize the sampling performance of product-reference discrete diffusion (PRD) algorithms. The authors demonstrate that IGC, derived from the second derivatives of mutual information, provides exact representations of KL discretization errors and bounds iteration complexity. The study highlights that optimal stepsize scheduling based on IGC profiles can significantly improve sampling efficiency, particularly by adapting to low-dimensional structures captured by total correlation (TC) and dual total correlation (DTC).

Entities (6)

Martin J. Wainwright · author · 99%Interaction Growth Complexity · metric · 98%Product-Reference Discrete Diffusion · algorithm · 95%KL Discretization Error · error-metric · 92%Dual Total Correlation · statistical-measure · 90%Total Correlation · statistical-measure · 90%

Relation Signals (5)

Martin J. Wainwright → authored → The information geometry of product-reference discrete diffusion: Interaction growth complexity and optimal scheduling

confidence 99% · Martin J. Wainwright mjwain@mit.edu ... The information geometry of product-reference discrete diffusion: Interaction growth complexity and optimal scheduling

Interaction Growth Complexity → characterizes → Product-Reference Discrete Diffusion

confidence 95% · We show that their sampling performance can be characterized using a path-based measure of data geometry that we call the interaction growth complexity (IGC).

Interaction Growth Complexity → represents → KL Discretization Error

confidence 92% · We show that a bivariate IGC kernel gives an exact representation of both the KL discretization error and a simple one-step upper bound.

Interaction Growth Complexity → bounds → Total Correlation

confidence 90% · the aggregate IGC mass admits bounds in terms of total correlation and dual total correlation

Interaction Growth Complexity → bounds → Dual Total Correlation

confidence 90% · the aggregate IGC mass admits bounds in terms of total correlation and dual total correlation

Cypher Suggestions (0)

No Cypher suggestions yet.

Abstract

Abstract:We study a class of product-reference diffusion algorithms for sampling from a discrete distribution. We show that their sampling performance can be characterized using a path-based measure of data geometry that we call the interaction growth complexity (IGC). We show that a bivariate IGC kernel gives an exact representation of both the KL discretization error and a simple one-step upper bound. The simpler univariate IGC density can be used to study the effect of stepsize choices on the iteration complexity required to obtain $\epsilon$-accurate samples in KL divergence. Samplers that traverse the path with equi-spaced steps in log-squared-reliability-odds have performance that depends on the aggregate IGC mass, whereas refined choices of stepsizes have a lower complexity depending on a square-root functional. In the fine-grid limit, both of these characterizations become sharp. We also allow general product reference distributions and show that the reference law can substantially reshape the IGC profile and the resulting sampling complexity; in particular, references far from both the uniform and the data marginals can yield dimension-dependent improvements. Finally, the aggregate IGC mass admits bounds in terms of total correlation and dual total correlation, thereby connecting the pathwise geometry to classical measures of multivariate dependence.

PDF

Open source PDF →Open local PDF →

Trouble viewing inline? Open PDF directly →

Full Text

118,077 characters extracted from source content.

Expand or collapse full text

The information geometry of product-reference discrete diffusion: Interaction growth complexity and optimal scheduling Martin J. Wainwright mjwain@mit.edu Lab for Information and Decision Systems Statistics and Data Science Center EECS and Mathematics, Massachusetts Institute of Technology August 28, 2026 Abstract We study a class of product-reference diffusion algorithms for sampling from a discrete distribution. We show that their sampling performance can be characterized using a path-based measure of data geometry that we call the interaction growth complexity (IGC). We show that a bivariate IGC kernel gives an exact representation of both the KL discretization error and a simple one-step upper bound. The simpler univariate IGC density can be used to study the effect of stepsize choices on the iteration complexity required to obtain ε -accurate samples in KL divergence. Samplers that traverse the path with equi-spaced steps in log-squared-reliability-odds have performance that depends on the aggregate IGC mass, whereas refined choices of stepsizes have a lower complexity depending on a square-root functional. In the fine-grid limit, both of these characterizations become sharp. We also allow general product reference distributions and show that the reference law can substantially reshape the IGC profile and the resulting sampling complexity; in particular, references far from both the uniform and the data marginals can yield dimension-dependent improvements. Finally, the aggregate IGC mass admits bounds in terms of total correlation and dual total correlation, thereby connecting the pathwise geometry to classical measures of multivariate dependence. 1 Introduction Sampling from complex high-dimensional distributions is a basic computational problem arising throughout statistics, machine learning, and the sciences. It provides the foundation for Monte Carlo methods [27, 28], enables uncertainty quantification in Bayesian inference [14, 3], and is a central component of modern generative modeling [6]. Diffusion-based methods approach this problem by constructing a family of progressively corrupted distributions, together with a reverse procedure that removes the corruption and ultimately produces a sample from the target law [32, 33, 17, 34, 7, 5, 2]. Much of the early theory was developed for continuous state spaces, where Gaussian perturbations provide the canonical forward process and the reverse dynamics are governed by Gaussian denoising [17, 34]. For distributions with discrete support, however, Gaussian perturbations are no longer natural. This fact has motivated a growing literature on discrete diffusion models, in which the forward process is instead built from Markovian corruption kernels on the underlying alphabet, and sampling is carried out by approximately reversing these transitions (e.g., see the papers [18, 1, 4, 22, 31, 29] and references therein). Understanding the computational and statistical properties of such discrete diffusion schemes is the focus of this paper. Concurrent work: Concurrent and independent work of Dmitriev, Huang and Wei [11], posted on August 24, 2026 as this manuscript was being finalized, studies related questions for discrete diffusion sampling within a CTMC formalism. We plan to coordinate with the authors in a future revision to clarify the connections between the two approaches. 1.1 Our contributions Let us provide a high-level overview of the contributions of this paper. As with our previous papers on Gaussian diffusion [36] and masking diffusion [37], this paper is motivated by two broad questions. Tailoring their form to the current setting, we ask: Q1: Can the performance of discrete diffusion sampling be explained and quantified, in some generality, by a measure tied to information and data geometry? Q2: Is it possible to exploit such geometric measures to design, optimize and certify sampling schemes? In our previous papers [36, 37], we showed that some fruitful answers to both questions can be given by specifying a a suitable form of complexity for the path from “noise” to a fresh sample. For Gaussian diffusion and masked diffusion, we referred to these notions as denoising growth complexity (DGC), and unmasking growth complexity (UGC), respectively. Both complexity measures are defined in information-theoretic terms, via the second derivative of a mutual information along the path. Moreover, they lead to a geometric understanding of the performance of sampling algorithms (Q1), while also providing a platform for optimizing and certifying their performance (Q2). The main contribution of this paper is to extend this type of theory via the notion of interaction growth complexity, or IGC for short. This complexity measure applies to a standard class of discrete diffusion samplers (e.g., [18, 1]) that use product approximations. They traverse a noising path terminating at an arbitrary product-reference distribution, using a sequence of product approximations along the path, so that we refer to them as product-reference diffusion samplers, or PRD for short. The uniform distribution and an absorbing-state reference distribution (δ-function at a single state) are two standard choices of the reference distribution, but our treatment allows for an arbitrary choice. Our analysis shows that the log-odds of the squared reliability (SR) is a natural parameter, and we define an IGC complexity that is based on the off-diagonal components of the Hessian of the mutual information along the path (see equation (2a)). We show that a simple PRD algorithm, one which traverses the path with steps of constant spacing in log-SR-odds, has iteration complexity governed by the aggregate IGC mass. This sampler adapts to low-dimensional geometric structure, since the aggregate IGC mass can be upper bounded by the classical / TC/ DTC measures of multivariate dependence [38, 16] that are sensitive to it. The stepsizes for this simple scheme are oblivious, requiring no knowledge of this structure nor clean samples for estimation. However, if in addition we are given access to clean samples from the target distribution, then we show how the structure of the IGC path can be estimated via a natural Bregman divergence that lies at the core of our theory. Tailoring stepsize choices to this geometric structure leads to samplers with improved and certified performance. The IGC theory, while sharing many features with its DGC and UGC precedents, differs in an important and interesting way. For both Gaussian diffusion and masking diffusion, the complexity structure is essentially univariate in nature. Both the exact KL discretization error and one-step error bounds can be expressed as functions of a univariate (DGC or UGC) function. In this paper, we put forth a univariate IGC density that provides similar intuition and guarantees, but note that the true complexity structure is bivariate in nature. This bivariate nature can be seen from the definition (2a) of the IGC function, which involves mixed partial derivatives of a mutual information. Section 3.3 is devoted to an in-depth exploration of this bivariate structure, which connects to the TC and DTC measures of multivariate dependence. 1.2 Related work Here we provide an overview of some broad strands of related work, with particular focus on those most closely related to our analysis of discrete diffusion. Sohl-Dickstein et al. [32] described diffusion-style generative modeling for both continuous and discrete state spaces. Later work focused more specifically on categorical data, and developed multinomial and structured forms of discrete diffusion processes [18, 1]. Campbell et al. [4] placed discrete diffusion in a continuous-time Markov chain (CTMC) framework; the work of Benton et al. [2] provided a broader perspective on denoising Markov models. Analogues of score matching and score-based modeling were developed by Meng et al. [23] and Lou et al. [22]; the latter introduced the score-entropy loss that plays an important role in training. While not the focus of this paper, we note that discrete diffusion based on masking has received substantial attention [31, 29, 24, 10, 8]. In the current paper, we focus on a standard class of product-reference diffusion samplers (see equations (1a) and (1b) for the noising path), and we allow the product-reference distribution to have arbitrary coordinate-dependent components. This class falls within the broader transition-matrix design space of discrete diffusion elucidated in past work [1, 4]. The product-reference updates that we analyze involve replacing an intractable joint reverse transition by simultaneous coordinatewise updates. This type of approximation is shared by continuous-time Markov chain (CTMC) approaches, beginning with classical τ-leaping, with later adaptations to discrete diffusion sampling by Campbell et al. [4]. Lou et al. [22] introduced Tweedie τ-leaping and showed, under exact scores, that its tokenwise independent transition is KL-optimal among τ-leaping strategies. While we do not adopt the CTMC formalism, the product kernel (7) in this paper has the same KL optimality property: for each input state, it is the product of the exact one-coordinate marginals of the finite reverse bridge. Consequently, its one-step KL defect is a (conditional) total correlation, and we make essential use of this structure in our analysis. In recent work, Gourevitch et al. [15] clarify important choices in how to parameterize the product kernel for uniform discrete diffusion, and in particular the distinct roles played by the ordinary one-site posterior and its leave-one-out counterpart. At the population level, the appropriate use of either quantity recovers the same oracle one-site reverse marginals, and hence the same product reverse kernel. Our theory analyzes the KL discretization error of this oracle product kernel, independently of the particular parameterization used to realize it. See the discussions preceding and following Theorem 1 for more details. In terms of convergence guarantees for discrete diffusion, there is now a substantial non-asymptotic theory, including stochastic-integral and Girsanov analyses [26, 39], the DMPM framework of Pham et al. [25], and analyses of τ-leaping, Euler, and Tweedie-τ-leaping under uniform or absorbing dynamics [21, 20, 9]. Most related to our development is recent work that has made important progress in giving general geometric characterizations of sampling performance, showing how they adapt to low-dimensional latent structure. Focusing on masking diffusion, two recent papers [8, 10] connected sampling performance to the total correlation ( TC) and dual total correlation ( DTC) measures of multivariate dependence [38, 16]. Dmitriev et al. [10] provided a sharp analysis of a class of modified τ-leaping CTMC samplers. For masking diffusion, they showed that its performance is governed by a refined measure that is upper bounded by the minimum of the / TC/ DTC measures. On the other hand, for a non-masking sampler, they proved an upper bound that scales with dimension. Intriguingly, they also complemented this upper bound with an algorithmic lower bound, showing that the particular CTMC scheme analyzed in their paper fails to adapt to low-dimensional structure. Thus, they raised the natural open question as to whether an alternative sampler for discrete diffusion might adapt to low-dimensional structure. In this paper, we show that PRD samplers adapt to / TC/ DTC structure, thereby providing an affirmative answer to this question. Our set-up and theory allow for a general choice of reference distribution, and this choice has also been studied empirically. Austin et al. [1] compare several forward corruption kernels for discrete diffusion, finding substantial performance differences between uniform and absorbing-state noise. DiGress [35] instead uses a terminal reference that is matched to the one-coordinate marginals, and reports improvements over uniform corruption in graph generation. Other work compares uniform, marginal-matched, and absorbing transitions for graph diffusion [19], as well as uniform and absorbing mechanisms across other discrete-data domains and sampling regimes [30]. Collectively, there is considerable empirical evidence that the choice of terminal reference can have significant effects on sampling performance. Our theoretical framework provides a crisp way of studying and characterizing this choice, as discussed in Section 3.2.3. Notably, we show that there is no simple ordering relation among these choices. Our method is constructive in nature: we exhibit an ensemble of distributions in which the gap between the marginal-matched reference and uniform/absorbing-state choices grows as d d in dimension, and another ensemble in which the absorbing-state choice exhibits a log⁡d d deficiency relative to the uniform choice. This analysis gives insight into what geometric structure of the underlying ℙZP_Z controls the effect of the terminal reference, and suggests directions for future work. Finally, at a higher level, our analysis has important structural connections with our previous work [36, 37] on Gaussian and masking diffusion, respectively. At the core of all three papers is the identification of a complexity measure (DGC, UGC, or IGC) that simultaneously yields an exact representation of the one-step KL error and leads to geometric bounds on it. The same complexity measure controls the KL error associated with grids that are equi-spaced in a privileged time parameter, and dictates how the step sizes should be optimized. Much of the analysis across these three settings therefore follows a common template, revealing structural connections between diffusion samplers whose technical details are otherwise substantially different. 2 Overview: Interaction growth complexity and sampling The main ideas of this paper can be conveyed at a relatively high level, and this section is devoted to this end. We begin by describing a standard class of product-reference diffusion (PRD) samplers. Given a fixed reference distribution ν that factorizes across coordinates, any PRD sampler generates samples by tracing the path from the reference ν to the target distribution ℙZP_Z, using product-based approximations to the exact transition kernels at each step. We define the notion of interaction growth complexity, which is a way of tracking the evolution of information along this path. Its structure both reveals geometric properties of the target distribution, and controls the complexity of sampling algorithms based on kernel-product approximations. The purpose of this section is to give a conceptual overview; subsequent sections provide the technical content that underlies this view. 2.1 General-reference diffusion Given a discrete alphabet A and a dimension d, our goal is to draw a sample Z∈dZ ^d from its unknown probability distribution ℙZP_Z. In this paper, we study a simple class of discrete diffusion samplers, which move progressively from the original distribution ℙZP_Z to a reference distribution. In particular, throughout the paper, we use ν=(ν1,…,νd)ν=( _1,…, _d) to denote a collection of d-marginals, possibly different from coordinate to coordinate, that define the product measure ⊗i=1dνi _i=1^d _i on the space dA^d. In the simplest case, known as uniform discrete diffusion, we simply set each νi _i to be uniform over the alphabet A. For coordinate i and squared reliability11 1 To explain the terminology, for any function f:→f:A→ that is mean zero under the reference distribution νi _i, we have ⁡[f⁡(Xi,r)∣Zi]=rf(Zi)E[f(X_i,r) Z_i]= rf(Z_i) for each i=1,…,di=1,…,d, so that any given coordinate is attenuated by the reliability r r. Our choice of squared reliability for parameterizing the path, while unorthodox, turns out to be revealing since it is the natural parameter for data-processing inequalities for this channel (see Lemma 4) and leads to exponential sandwiches of information-theoretic objects (see Lemma 1). r∈[0,1]r∈[0,1], we define the ν-reference transition via i,r(xi∣zi) _i,r(x_i z_i) ≔r[xi=zi]+(1−r)νi(xi). rI[x_i=z_i]+(1- r) _i(x_i). (1a) Note that the endpoint r=0r=0 corresponds to a Markov transition that produces the reference distribution ν. Moreover, it is easy to see that we have the semigroup identity rs=rsV_rV_s=V_rs for any pair (r,s)∈(0,1)(r,s)∈(0,1). We now use this semigroup to define a stochastic process Xr∣r∈[0,1]\X_r r∈[0,1]\. It has endpoint X1∼ZX_1 Z, and moves downwards in squared-reliability (SR) time to the reference endpoint X0∼⊗i=1dνiX_0 _i=1^d _i. For every 0<a<b≤10<a<b≤ 1, conditional on XbX_b, the coordinates of XaX_a are independent and satisfy ℙ⁡(Xa,i=x∣Xb,i=y)⏟≡a/b(x∣y)=abx=y+(1−ab)νi(x). P(X_a,i=x X_b,i=y)_ _a/b(x y)= ab1\x=y\+ (1- ab ) _i(x). (1b) Stated more simply in words, the transition from time b→ab→ a is obtained by sampling each coordinate Xa,iX_a,i independently, where we retain the value Xb,iX_b,i with probability a/b a/b and replace it with a fresh sample from the reference distribution νi _i with probability 1−a/b1- a/b. Note that the semigroup identity ensures that a/bb/c=a/cV_a/bV_b/c=V_a/c so that a transition from c to b followed by that from b to a equals the direct transition from c to a. This consistency makes Xr∣r∈[0,1]\X_r r∈[0,1]\ a genuine continuous-parameter Markov process rather than a collection of separately defined marginals. So as to simplify our analysis in the sequel, we have chosen to define the noising process in reverse time, moving from r=1r=1 to r=0r=0. Accordingly, sampling is carried out by approximating the forward evolution from a sample X0X_0 drawn from the product-reference distribution to the final sample X1≡ZX_1≡ Z. A straightforward calculation shows that, for any pair 0<a<b<10<a<b<1, the probability transition from XaX_a to XbX_b is defined by the kernel a,b(y∣x) _a,b(y x) ≔ℙ⁡(Xb=y∣Xa=x)=pb(y)pa(x)∏i=1di,a/b(xi∣yi), (X_b=y X_a=x)= p_b(y)p_a(x) _i=1^dV_i,a/b(x_i y_i), (1c) where pr:()d→[0,1]p_r:(A)^d→[0,1] is the marginal probability mass function of XrX_r. In general, the exact kernel (1c) is computationally intractable, since the state space has cardinality that grows exponentially in d. In this paper, we analyze a standard approximation in which we instead sample from a family of product kernels ~a,b K_a,b, obtained, for each fixed x, by taking the product of the one-coordinate marginals of the exact conditional kernel a,b(⋅∣x)K_a,b(· x); for example, see Lou et al. [22]. We refer to this sampler as the product-reference diffusion sampler, or PRD for short, since it is based on a product approximation to a reference-based diffusion process. By changing the reference distribution ν, we obtain different types of algorithms; for instance, choosing a uniform ν gives the standard uniform diffusion sampler [18, 1]; choosing ν to be a δ-function on a particular state yields an absorbing-state sampler [1]; and matching ν to the marginal distributions of ℙZP_Z yields a marginal-matched sampler [35]. Our theory applies to all of these choices. See Section 3.1 for a precise description of the class of algorithms that we analyze, and Section 3.2.3 for some insight into the effects of different references on sampler performance. 2.2 Introducing the interaction growth complexity (IGC) We now introduce the complexity measure that plays the central role in this paper. It involves the second partial derivatives of the mutual information between the latent variable Z∈dZ ^d, and the vector X=(X1,t1,…,Xd,td)∈dX_t=(X_1,t_1,…,X_d,t_d) ^d along an inhomogeneous version ≔(t1,…,td)t (t_1,…,t_d) of the squared-reliability path. More precisely, we define the function :[0,1]→ g:[0,1]→ via ⁡(r) g(r) ≔−∑i≠j∂2∂ti∂tjInfo(Z;X)|=r, - _i≠ j . ∂^2∂ t_i∂ t_jInfo(Z;X_t) |_t=r1, (2a) where Info⁡(Z,X)Info(Z;X_t) denotes the mutual information between Z and X_t. Using this function, the interaction growth complexity assigns a positive mass to any interval [a,b]⊂(0,1)[a,b]⊂(0,1) via the weighted integral ⁡(a,b) G(a,b) ≔∫abr⁡(1−r)(r)r. _a^br(1-r) g(r)\,dr. (2b) We refer to this weighted measure as the IGC mass function. Equivalently, so as to remove the explicit weighting, we can define the log-squared-reliability density q in the coordinates φ⁡(r)=log⁡(r/(1−r)) (r)= (r/(1-r)). It has the explicit form ⁡(λ) q(λ) ≔r2(λ)(1−r(λ))2(r(λ))where r⁡(λ)=φ−1(λ)≔eλ1+eλ. r^2(λ) (1-r(λ) )^2\; g (r(λ) ) where $r(λ)= ^-1(λ) e^λ1+e^λ$. (2c) Note that we have ⁡(a,b)=∫φ⁡(a)φ⁡(b)⁡(η)η G(a,b)= _ (a) (b) q(η)\,dη by construction. In terms of the shorthand SR for squared-reliability, the log-SR density q is the central object of this paper. In the limit of fine stepsizes, it determines the exact KL discretization error up to a factor of two. It gives explicit upper bounds on practical algorithms, both those based on stepsizes with constant spacing in log-SR-odds, and those with stepsizes optimized to minimize error. Let us provide a high-level overview of these conclusions here, along with pointers to the relevant technical sections. To streamline presentation, we focus on squared-reliability intervals of the form [r0,1−r0][r_0,1-r_0], which transform to the centered22 2 The choice of ℓd _d only affects the initialization and termination error in a minor way: as we show in the sequel, the choice ℓd=Θ⁡(log⁡(d||)CLOSE _d= ( (d|A|) is sufficient to drive these errors to zero at rate poly⁡(1d||)poly( 1d|A|). intervals [−ℓd,ℓd][- _d, _d] under the log-SR-odds transform ℓd=log⁡(1−r0r0) _d= ( 1-r_0r_0 ). With this set-up, we can summarize our main guarantees as follows: • The simplest form of a PRD sampler traverses the interval [−ℓd,ℓd][- _d, _d] using steps with constant spacing in log-SR-odds. As a simple corollary of Theorem 1, we prove that this simple scheme has iteration complexity that scales as IGC C_ @scalerel@objIGC ≔2ℓd∫−ℓdℓd⁡(λ)λ. 2 _d _- _d _d q(λ)\,dλ. (3a) Moreover, as the grid size converges to zero, this iteration complexity estimate is sharp up to a constant prefactor, in the sense that the exact KL discretization error exhibits the same scaling. See Theorem 3 for this claim. Moreover, we show how to bound IGC C_ @scalerel@objIGC in terms of the classical complexity measures [38, 16] known as total correlation ( TC) and dual total correlation ( DTC). This shows how even this simple single-block sampler can adapt to the intrinsic geometry of ℙZP_Z. • As we show below in Section 2.3, for “interesting” random vectors Z∼ℙZ _Z, the density q has a rich geometric structure. This suggests that better samplers can be obtained by tailoring the stepsizes to the structure of q, with finer steps in portions where q is rapidly varying. We exhibit a sequence of practical samplers, using progressive refinement with constant spacing blocks, whose iteration complexity converges to the fine partition limit IGC P_ @scalerel@objIGC ≔(∫−ℓdℓd⁡(λ)λ)2, ( _- _d _d q(λ)\,dλ )^2, (3b) Taken collectively, these results lead to a simple characterization of the potential benefits of optimizing stepsizes in any product-reference sampler. In particular, the gains are characterized by the ratio Ratio⁡(ℙZ) (P_Z) ≔ IGC IGC=2ℓd∫−ℓdℓd⁡(λ)λ(∫−ℓdℓd⁡(λ)λ)2≥(i) 1, C_ @scalerel@objIGC P_ @scalerel@objIGC \;=\; 2 _d _- _d _d q(λ)\,dλ ( _- _d _d q(λ)\,dλ )^2\; (i)≥\;1, (4) where the lower bound (i) follows from the Cauchy–Schwarz inequality, with equality holding if and only if q is constant. When q is unevenly distributed, then the ratio becomes much larger than one. As we show in the next section, such uneven distributions arise in many settings, and often reflect interesting geometric structure of the distribution. Finally, our explicit characterization of PRD sampling complexity also leads to insights into the broader design space of sampling algorithms: • Our streamlined notation hides the fact that the IGC density ≡ν q≡ q_ν depends on the choice of reference distribution ν, since it is embedded within the “noising” process (1a) that defines the IGC complexity. In practice, the choice of ν is an important design parameter, with empirical work showing that it has substantial effects on sampler performance. For each choice of reference ν, we have both a coarse complexity (3a) and a fine-partition complexity (3b). By studying these complexities, we can obtain insights into the differences among samplers using uniform, absorbing-state, and marginal-matched references. See Section 1.2 for some representative results. 2.3 The data geometry of the IGC density Since the IGC density controls the complexity of product-reference diffusion, it is natural to wonder about what it reveals about the underlying geometry. In this section, we describe three simple ensembles, each of which is chosen to illustrate a different qualitative feature of the IGC density. 2.3.1 Noisy repeated bit We begin with a very simple example, also studied in our past work [37] on masking algorithms. For any p∈[0,1]p∈[0,1], we use V∼Ber(p)V Ber(p) to denote a Bernoulli random variable with ℙ⁡(V=1)=pP(V=1)=p and ℙ⁡(V=0)=1−pP(V=0)=1-p. Consider a binary random vector Z=(Z1,…,Zd)∈0,1dZ=(Z_1,…,Z_d)∈\0,1\^d constructed in the following way. We first draw a latent variable U∼Ber(1/2)U Ber(1/2), and then, with ⊕ denoting addition modulo two, we set Zi Z_i =U⊕Wifor each i=1,…,d, =U W_i for each $i=1,…,d$, (5) where each WiW_i is an independent Ber(η) Ber(η)-variable for some η∈[0,1/2]η∈[0,1/2]. By construction, we have ℙ⁡(Zi=U)=1−ηP(Z_i=U)=1-η, hence our use of the term “noisy repeated bit”. For any η∈[0,1/2]η∈[0,1/2], the coordinates of Z are conditionally independent given U, but for any η∈[0,1/2)η∈[0,1/2), they are not independent, due to the shared structure. Using the uniform reference measure to define the path, we computed the IGC density q for this ensemble at dimension d=128d=128 and varying choices of the cross-over parameter η∈(0,1/2]η∈(0,1/2]. (a) (b) (c) Figure 1: Plots of the IGC density q for the noisy repeated bit model in equation (5), for three different settings of the noise level η∈0.01,0.30,0.45η∈\0.01,0.30,0.45\. The IGC density captures the decaying dependence on the latent bit U as η evolves towards the endpoint 1/21/2. As can be seen in Figure 1, when the cross-over probability η is small, the IGC density has a pronounced peak, reflecting the strong dependence induced by the shared latent bit U. As η increases towards 1/21/2, this peak becomes progressively smaller, corresponding to the weakening of the common latent structure. In the limiting case η=1/2η=1/2, each coordinate is an independent Ber(1/2) Ber(1/2) variable, so that ℙZP_Z is itself a product distribution and the IGC density vanishes identically. As we show in Corollary 2, the integrated IGC mass is upper bounded by the total correlation ⁡(Z) TC(Z) ≔∑i=1dEnt⁡(Zi)−Ent⁡(Z), \ _i=1^dEnt(Z_i) \-Ent(Z), which approaches zero as ℙZP_Z approaches a product distribution. Overall, the evolution of q across the three panels illustrates the adaptivity of the IGC density to the dependence structure of the target. 2.3.2 Curie–Weiss model Next we turn to a classical model from statistical physics, known as the Curie–Weiss model [12, 13], which captures a phenomenon known as spontaneous magnetization. It defines a family of distributions over the spin-hypercube −1,+1d\-1,+1\^d via the probability mass function ℙZ(z1,…,zd,β) _Z(z_1,…,z_d;β) ∝exp⁡β2d(∑i=1dzi)2, \ β2d ( _i=1^dz_i )^2 \, (6) where β∈β∈ is a parameter. For physical reasons, the sum ∑i=1dzi _i=1^dz_i is referred to as the magnetization. At β=0β=0, we have a product distribution, whereas as β→−∞β→-∞, the model assigns increasing mass to balanced configurations with ∑i=1dzi=0 _i=1^dz_i=0. On the other side, as β increases along the positive line, it is known to have a phase transition at β=1β=1. (In particular, for β<1β<1, the magnetization is symmetrically distributed around zero, whereas for β>1β>1, its distribution becomes approximately bimodal, with mass concentrated near two oppositely magnetized states.) Figure 2: Illustration of the IGC density for the Curie–Weiss model (6). Bottom panels from left to right correspond to β∈0.70,1.00,1.20,1.60β∈\0.70,1.00,1.20,1.60\. For each choice of β, the matrix presents a collection of random samples Z∼ℙZ _Z, one in each row. Finally, for large positive values of β, the distribution becomes close to bimodal, with nearly all mass aligned on states with absolute magnetization |∑i=1dzi|=d| _i=1^dz_i|=d. In Figure 2, we plot the log-SR density q from equation (2c) associated with the model (6) for four different choices of β∈0.70,1.00,1.20,1.60β∈\0.70,1.00,1.20,1.60\. Above each q-plot, we show a m×dm× d-matrix of samples, where each of the m rows corresponds to a sample Z∈−1,1dZ∈\-1,1\^d drawn from the associated model. These plots illustrate how the IGC density reflects the changing dependence structure as a function of the Curie–Weiss parameter β. In the subcritical regime, illustrated by β=0.70β=0.70, the samples exhibit relatively weak dependence, and the associated IGC density is correspondingly modest. As β approaches and crosses the critical value β=1β=1, the dependence strengthens and the IGC density develops a pronounced mode; at the same time, the samples begin to separate into two groups with opposite magnetizations. For β=1.20β=1.20, the IGC density becomes bimodal, suggesting two distinct scales of dependence along the diffusion path: the global choice between the two magnetized phases, and the residual fluctuations of configurations within each phase. Finally, for the larger value β=1.60β=1.60, the IGC density again becomes approximately unimodal. At this point, the within-phase fluctuations are much smaller, leaving the global choice between the two strongly magnetized components as the dominant source of dependence. 2.3.3 Hierarchical mixture model As our final example, we revisit a model class first introduced in our previous paper [37] on masking complexity. It involves a random vector Z∈0,1dZ∈\0,1\^d over the Boolean hypercube that places mass on 2L2^L prototype configurations for an integer L≪dL d. More interestingly, these binary prototypes are related via a latent tree structure, and the integer L corresponds to the number of levels in the tree. (a) (b) (c) (d) Figure 3: Plots of the IGC densities q associated with various types of hierarchical binary-prototype mixtures. The rows correspond to hierarchy depths L=2L=2 and L=3L=3. Left panels (a) and (c) show the leaf prototypes, while right panels (b) and (d) show the corresponding densities q. In terms of the shorthand M=2LM=2^L, let V1,…,VM\V^1,…,V^M\ denote the binary prototype vectors. Each prototype is defined by a path down a binary tree of depth L; see the left column of Figure 3 for some examples. The geometry of the prototypes is related to the tree structure in the following way. For any pair VaV^a and VbV^b of prototypes, suppose that they first diverge at level ℓ∈1,…,L ∈\1,…,L\ of the tree; our construction then ensures that VaV^a and VbV^b are separated by Hamming distance Δℓ _ , for some pre-specified set of distances Δℓ=1L\ _ \_ =1^L. This leads to a total dimension d=∑ℓ=1LΔℓd= _ =1^L _ . Panel (a) of Figure 3 shows a toy example with L=2L=2, (Δ1,Δ2)=(12,2)( _1, _2)=(12,2), and dimension d=12+2=14d=12+2=14. This set-up leads to M=2L=4M=2^L=4 prototype vectors in the Boolean hypercube 0,114\0,1\^14. To track them, we assigned the index labels 00,01,10,11\00,01,10,11\, plotted as rows in the corresponding black-white matrix. Observe that the pair of prototypes indexed by 0000 and 1111 diverge at level ℓ=1 =1 of the tree, and their Hamming distance is equal to Δ1=12 _1=12. Similarly, the prototypes indexed by 0000 and 0101 diverge at level ℓ=2 =2 of the tree, and have Hamming distance Δ2=2 _2=2. Panel (c) illustrates a larger construction with L=3L=3, still in a toy dimension d=34d=34 for illustrative purposes. Panels (b) and (d) show the IGC densities for L=2L=2 and L=3L=3 models, using larger separations and dimensions: the L=2L=2 model has dimension d=32776d=32776 and Hamming separations (Δ1,Δ2)=(32768,8)( _1, _2)=(32768,8), whereas the L=3L=3 model has dimension d=33288d=33288, and Hamming separations (Δ1,Δ2,Δ3)=(32768,512,8)( _1, _2, _3)=(32768,512,8). The IGC density for the L=2L=2 model has two distinct peaks in log-SR-odds, and these two peaks have a very natural interpretation. The prototypes at level ℓ=1 =1 differ by Hamming distance Δ1=32768 _1=32768, so their ambiguity is resolved at a fairly early denoising time. Only at a later time does the second peak appear, corresponding to resolving the ambiguity between pairs separated by Hamming distance Δ2=8 _2=8. Each of the L=3L=3 peaks for the IGC density in panel (d) has an analogous interpretation. 3 Product-reference diffusion and KL guarantees In this section, we begin in Section 3.1 by describing the class of sampling algorithms that we analyze. They are based on product approximations to the transition kernel (1c), and can be parameterized either in terms of the single-site denoisers or their leave-one-out versions. In Section 3.2, we present a general upper bound on the Kullback–Leibler (KL) error of the sampler: it involves increments of the IGC density, combined with prefactors in terms of the squared-reliability (SR) odds ratio. This geometric factor is key, as it identifies stepsizes with constant spacing in log-SR-odds as canonical. We derive a corollary for this simple stepsize choice. It gives guarantees in terms of the / TC/ DTC measures, and as discussed in Section 3.2.3, it also provides insight into the choice of reference distribution ν. Finally, Section 3.3 is devoted to an exploration of the bivariate IGC kernel, which gives exact relations for the KL error, the univariate IGC upper bound, and the / TC/ DTC measures. 3.1 Sampling using product-reference diffusion (PRD) For 0<a<b<10<a<b<1, we let a,b(⋅∣x)≔ℒ(Xb∣Xa=x)K_a,b(· x) (X_b X_a=x) denote the exact kernel of the reference-to-output process, as previously defined in equation (1c). A standard approximation is based on the product kernel ~a,b(y∣x) K_a,b(y x) ≔∏i=1dℙia→b(yi∣x), _i=1^dP_i^a→ b(y_i x), (7) where ℙia→b(yi∣x)≔ℙ⁡(Xb,i=yi∣Xa=x)P_i^a→ b(y_i x) (X_b,i=y_i X_a=x). Different parameterizations: The transition kernel ℙia→bP_i^a→ b can be parameterized either via the single-site posterior μi,a(w,x)≔ℙ⁡(Zi=w∣Xa=x) _i,a(w,x) (Z_i=w X_a=x), or via its leave-one-out version μa,i LOO (w,x−i)≔ℙ⁡(Zi=w∣Xa,−i=x−i)μ @scalerel@objLOO_a,i(w,x_-i) (Z_i=w X_a,-i=x_-i). Here Xa,−iX_a,-i denotes the vector obtained from XaX_a by removing coordinate i. For the ordinary posterior, conditioning on ZiZ_i gives the one-site bridge representation ℙia→b(y∣x) _i^a→ b(y x) =∑w∈ia→b(y∣xi,w)μi,a(w,x),where = _w B^a→ b_i(y x_i,w) _i,a(w,x), where (8a) ia→b(y∣xi,w) ^a→ b_i(y x_i,w) ≔ℙ⁡(Xb,i=y∣Xa,i=xi,Zi=w)=i,b(y∣w)i,a/b(xi∣y)i,a(xi∣w). (X_b,i=y X_a,i=x_i,Z_i=w)= V_i,b(y w)V_i,a/b(x_i y)V_i,a(x_i w). (8b) Here V was defined in equation (1a). See Appendix A for the parameterization in terms of the LOO posterior μ LOO μ @scalerel@objLOO. PRD sampling updates: Any product-reference diffusion (PRD) sampler operates on a collection of single-site transitions ℙia→b,i=1,…,d\P_i^a→ b,i=1,…,d\ for each squared-reliability time pair 0<a<b<10<a<b<1. Given an integer iteration number N≥2N≥ 2, it takes as input a grid of the form 0<r0<r1<⋯<rN=R<1. 0<r_0<r_1<·s<r_N=R<1. (9) The sampler then proceeds through the following three steps: Product-reference diffusion sampler 1. Initialization. At squared reliability r0r_0, draw X^0 X^0 ∼⨂i=1dℒ⁡(Xr0,i). _i=1^dL(X_r_0,i). (10a) 2. Product updates. For k=1,…,Nk=1,…,N, update the coordinates independently according to ℒ⁡(X^k∣X^k−1=x) ( X^k X^k-1=x) ≔⨂i=1dℙirk−1→rk(⋅∣x). _i=1^dP_i^r_k-1→ r_k( · x). (10b) 3. Completion. From R to the clean endpoint, draw ℒ⁡(X^N+1∣X^N=x) ( X^N+1 X^N=x) ≔⨂i=1dℒ⁡(Zi∣XR=x),and return Z^=X^N+1. _i=1^dL(Z_i X_R=x), and return $ Z= X^N+1$. (10c) Thus, for a fixed iteration budget N, the key design parameter—and one for which our theory provides guidance—is the design of the stepsize grid (9). Theorem 1 provides an upper bound on the KL error for any grid, whereas Corollary 1 specializes to an equi-spaced grid. Our later theory in Section 4 develops adaptive multi-block grids. 3.2 Controlling the Kullback–Leibler error A key question is to understand the accuracy of the final output Z^=X^N+1 Z= X^N+1 relative to the target distribution. A standard measure of accuracy is the Kullback–Leibler (KL) divergence given by D KL (ℙZ∥ℙZ^) D_ @scalerel@objKL(P_Z\|P_ Z) ≔∑z∈dℙZ(z)log⁡(ℙZ(z)ℙZ^(z)). _z ^dP_Z(z) ( P_Z(z)P_ Z(z) ). (11) We begin in Section 3.2.1 with a general upper bound that applies to any stepsize grid (9). In Section 3.2.2, we specialize it to stepsizes that are equi-spaced in the log-SR-odds parameter, and derive concrete results in terms of the aggregate IGC complexity. 3.2.1 A general guarantee The main result of this section provides a KL error upper bound that involves the IGC increments ⁡(a,b) G(a,b) ≔∫abr⁡(1−r)(r)r. _a^br(1-r) g(r)\,dr. (12) associated with a given interval. Theorem 1. For any grid (9) of the interval [r0,R][r_0,R], the PRD sampler returns output Z Z such that D KL (ℙZ∥ℙZ^) D_ @scalerel@objKL(P_Z\|P_ Z) ≤2∑j=0N−1ψ⁡(rj+1)ψ⁡(rj)−1(rj,rj+1)+⁡(Xr0)+⁡(Z∣XR), ≤ 2\; _j=0^N-1 \ ψ(r_j+1)ψ(r_j)-1 \ G(r_j,r_j+1)+ TC(X_r_0)+ TC(Z X_R), (13) where ψ⁡(t)≔t1−tψ(t) t1-t is the odds of the squared reliability t. The bound (13) involves initialization and termination costs defined in terms of the total correlation, and a conditional version thereof. Letting EntEnt denote the (Shannon) entropy, the initialization cost is given by ⁡(Xr0) TC(X_r_0) ≔∑i=1dEnt⁡(Xr0,i)−Ent⁡(Xr0), \ _i=1^dEnt(X_r_0,i) \-Ent(X_r_0), (14) which corresponds to the KL divergence between the joint distribution of Xr0X_r_0 and the product of its marginals, consistent with our choice of initialization (10a). The termination cost ⁡(Z∣XrN) TC(Z X_r_N) arises from the completion step (10c). These two costs are straightforward to control by suitable choices of the pair r0r_0 and rNr_N. For the symmetric choice rN=1−r0r_N=1-r_0, we are guaranteed to have ⁡(Xr0)+⁡(Z∣X1−r0) TC(X_r_0)+ TC(Z X_1-r_0) ≤cr0(d||)3for a universal constant c>0, ≤ c\,r_0 (d|A| )^3 for a universal constant $c>0$, (15) so that setting r0=(d||)−kr_0=(d|A|)^-k for k≥4k≥ 4 drives this error to zero at rate (d||)k−3(d|A|)^k-3. Importantly, the sampler complexity is only logarithmic in r0r_0. Consequently, the bulk of our analysis focuses on characterizing the KL discretization sum in the bound (13). Learned posterior distributions: The statement of Theorem 1 uses the exact single-site posteriors, whereas in practice, these oracle objects are replaced by versions that are estimated from data. Here we describe how replacing the ordinary posterior μi,a _i,a with a learned version μ^i,a μ_i,a leads to an additional error term in the upper bound (13). To be clear, the LOO parameterization can be handled in exactly the same way using the corresponding bridge from Appendix A. For each coordinate i=1,…,di=1,…,d and time a, let μ^i,a μ_i,a be an estimate of the true one-site posterior μi,a _i,a. Passing this estimate through the one-site bridge (8a) yields a learned one-site kernel ^a,b(i)(y∣x)≔∑w∈ia→b(y∣xi,w)μ^i,a(w∣x). K_a,b^(i)(y x) _w B^a→ b_i(y x_i,w) μ_i,a(w x). (16a) This collection of learned one-site kernels defines the corresponding learned product kernel ^a,b(⋅∣x)≔⨂i=1d^a,b(i)(⋅∣x) K_a,b(· x) _i=1^d K_a,b^(i)(· x). By the bridge representation (8a), the true one-coordinate marginal of a,b(⋅∣x)≔ℒ(Xb∣Xa=x)K_a,b(· x) (X_b X_a=x) is precisely ℙia→b(⋅∣x)P_i^a→ b(· x). Consequently, the approximation ~a,b(⋅∣x) K_a,b(· x) is the product of the true one-coordinate marginals. Via the KL projection identity for product distributions, we are guaranteed to have D KL (a,b(⋅∣x)∥^a,b(⋅∣x)) D_ @scalerel@objKL (K_a,b(· x)\, \|\, K_a,b(· x) ) =D KL (a,b(⋅∣x)∥~a,b(⋅∣x))+∑i=1dD KL (ℙia→b(⋅∣x)∥^a,b(i)(⋅∣x)). =D_ @scalerel@objKL (K_a,b(· x)\, \|\, K_a,b(· x) ) + _i=1^dD_ @scalerel@objKL (P_i^a→ b(· x)\, \|\, K_a,b^(i)(· x) ). Thus learning the posterior contributes an additive error on top of the exact-posterior discretization error. Averaging over XaX_a, define the block denoiser penalty ℰden(a,b) _den(a,b) ≔∑i=1dXa[D KL (ℙia→b(⋅∣Xa)∥^a,b(i)(⋅∣Xa))], _i=1^dE_X_a [D_ @scalerel@objKL (P_i^a→ b(· X_a)\, \|\, K_a,b^(i)(· X_a) ) ], (16b) which is then added to the upper bound (13) in Theorem 1. Note that the estimated posteriors μ^i,a μ_i,a enter this expression via the bridge, as in equation (16a). 3.2.2 Single block consequence and KL iteration complexity We now derive a consequence of Theorem 1 that applies to a single-block sampler, meaning one that uses a non-adaptive stepsize schedule across the entire interval. Here we specialize to the symmetric interval ℐ full ≔[r0,1−r0]I_ @scalerel@objfull [r_0,1-r_0], which leads to the log-SR-odds image [−ℓd,ℓd][- _d, _d] where ℓd≔log⁡(1−r0r0) _d ( 1-r_0r_0 ). In particular, it applies to an N-step grid that is uniform in log-SR-odds: φ⁡(rj) (r_j) =−ℓd+2ℓdjN,j=0,1,…,N. =- _d+ 2 _djN, j=0,1,…,N. (17) The following result summarizes the resulting guarantee: Corollary 1. For any choice of r0∈(0,1/2)r_0∈(0,1/2) and iteration number N≥2ℓdN≥ 2 _d, applying the PRD sampler with the stepsize protocol (17) over the interval [r0,1−r0][r_0,1-r_0] returns output Z Z such that D KL (ℙZ∥ℙZ^) D_ @scalerel@objKL(P_Z\|P_ Z) ≤8ℓdN(r0,1−r0)+(Xr0)+(Z∣X1−r0)where ℓd=log⁡(1−r0r0). ≤ 8 _dN G(r_0,1-r_0)+ TC(X_r_0)+ TC(Z X_1-r_0) where $ _d= ( 1-r_0r_0 )$. (18) Proof. Since every step has the same log-SR-odds multiplier, Theorem 1 and the additivity of G give D KL (ℙZ∥ℙZ^) D_ @scalerel@objKL(P_Z\|P_ Z) ≤2exp⁡(2ℓdN)−1(r0,1−r0)+⁡(Xr0)+⁡(Z∣X1−r0). ≤ 2 \ ( 2 _dN )-1 \ G(r_0,1-r_0)+ TC(X_r_0)+ TC(Z X_1-r_0). Using the elementary bound ex−1≤2xe^x-1≤ 2x for x∈[0,1]x∈[0,1] and the assumed lower bound N≥2ℓdN≥ 2 _d yields the claim. ∎ Let us now explore the iteration complexity of the single-block PRD sampler, meaning the number of iterations N⁡(ε)N( ) required to achieve KL error at most ε . In particular, suppose that we use the symmetric interval [r0,1−r0][r_0,1-r_0] with r0≔ε2c(d||)3r_0 2c (d|A| )^3. Then inequality (15) gives ⁡(Xr0)+⁡(Z∣X1−r0)≤cr0(d||)3≤ε/2 TC(X_r_0)+ TC(Z X_1-r_0)≤ c\,r_0 (d|A| )^3≤ /2. The PRD sampler, when implemented with the equi-spaced grid (17), yields an output Z Z such that D KL (ℙZ∥ℙZ^)≤εD_ @scalerel@objKL(P_Z\|P_ Z)≤ using at most N⁡(ε) N( ) =c0+c1⁡(r0,1−r0)εlog⁡(d||ε) =c_0+c_1 G(r_0,1-r_0) ( d|A| ) (19a) iterations, for universal constants (c0,c1)(c_0,c_1). Here we have used the fact that log⁡(1/r0)=⁡(log⁡(d||ε)) (1/r_0)=O ( ( d|A| ) ) for our specified choice of r0r_0. Recalling the definition (2c) of the IGC density q, we have ⁡(r0,1−r0) G(r_0,1-r_0) =∫−ℓdℓd⁡(λ)λ, = _- _d _d q(λ)\,dλ, (19b) which justifies the single-block scaling (3a) asserted in Section 2. As we show in the next section (see Corollary 2), the aggregate IGC complexity is upper bounded as ⁡(r0,1−r0)≤⁡(0,1) G(r_0,1-r_0)\;≤ G(0,1)\, ≤2min⁡(Z),⁡(Z), ≤ 2\; \ TC(Z),\; DTC(Z)\, (19c) As an important consequence, the single-block sampler inherits any bound that can be obtained for min⁡(Z),⁡(Z) \ TC(Z), DTC(Z)\. These multivariate dependence measures adapt to the structure of Z. Notably, in their analysis of a CTMC masking sampler, Dmitriev et al. [10] explored a diverse range of examples for which the min-/ TC/ DTC value can be computed or bounded in terms of low-dimensional latent structure. Among other interesting examples, they analyzed the / TC/ DTC structure of hidden Markov models with slowly varying latent states, stochastic block models, and quantized latent models. Thus, by combining our bounds with their analysis, we can assert that similar low-dimensional guarantees hold for PRD samplers. For their masking-related functional, called the effective total correlation, Dmitriev et al. [10] also observed that the min-/ TC/ DTC bound can be very conservative. In particular, via a construction using independent blocks, they gave an example where there is an Ω⁡(d) (d) gap between their complexity measure and the min-/ TC/ DTC bound. We can adapt their argument to the current setting, using our aggregate IGC measure ⁡(0,1) G(0,1) as the base, to show that the same gap persists. 3.2.3 Effects of varying the reference ν The choice of reference distribution ν is an important design choice, and past empirical work [1, 35, 19, 30] has shown that this choice can have substantial effects on sampler performance. Here we provide theoretical insight into why the choice of reference matters, and when it can actually lead to dimension-dependent differences between different PRD samplers. (a) (b) (c) Figure 4: Log-odds IGC densities q for Ensemble A, with ϵd=d−1/2 _d=d^-1/2, under (a) the uniform reference, (b) the absorbing-state reference, and (c) the marginal-matched reference. More precisely, we consider three different choices: the uniform reference; the absorbing-state reference; and the marginal-matched reference, in which ν corresponds to a product of the marginals of ℙZP_Z. For each of these three choices, we use the IGC representation and an associated family of binary distributions to establish two important facts: • The choice of reference distribution can have a dimension-dependent effect on the iteration complexity of PRD samplers. • There is no universal performance ordering among different reference distributions. Let us begin by describing a general family of distributions over a binary random vector (Z1,…,Zd)∈0,1d(Z_1,…,Z_d)∈\0,1\^d. Suppose that the dimension d is even, and we partition the coordinates into d/2d/2 disjoint pairs. The pairs are independent and identically distributed, with each block (Z2k−1,Z2k)(Z_2k-1,Z_2k) drawn from the bivariate PMF PϵP_ε on 0,12\0,1\^2 given by Pϵ(0,0) P_ε(0,0) =ϵ, =ε, Pϵ(0,1) P_ε(0,1) =0, =0, Pϵ(1,0) P_ε(1,0) =1−ϵ2, = 1-ε2, Pϵ(1,1) P_ε(1,1) =1−ϵ2. = 1-ε2. Thus, the configuration (0,1)(0,1) is forbidden within every pair. The one-coordinate marginals are Ber(1−ϵ) Ber(1-ε) and Ber((1−ϵ)/2) Ber((1-ε)/2) for the first and second coordinates of each pair, respectively. (a) (b) Figure 5: Dimension dependence of the aggregate IGC for different choices of reference. Panel (a) shows Ensemble A, with ϵd=d−1/2 _d=d^-1/2, for which the marginal-matched reference becomes increasingly unfavorable. Panel (b) shows Ensemble B, with 1−ϵd=d−11- _d=d^-1, for which the uniform reference has constant-order IGC whereas the IGC for the absorbing-state reference grows as Θ⁡(log⁡d) ( d). For our three choices of reference distribution, when specialized to this ensemble, the marginal-matched choice is ν1=Ber(1−ϵ) _1= Ber(1-ε) and ν2=Ber((1−ϵ)/2) _2= Ber((1-ε)/2), the uniform choice is ν1=ν2=Ber(1/2) _1= _2= Ber(1/2), and the absorbing-state choice is ν1=ν2=δ0 _1= _2= _0. We use the same family PϵP_ε to exhibit both dimension-dependent scaling, and no uniform ordering among the choices. Ensemble A: For the first ensemble, we take ϵd≔d−1/2 _d d^-1/2. With this choice, the exceptional configuration (0,0)(0,0) becomes increasingly rare with dimension, while the first marginal approaches a point mass at one and the second approaches Ber(1/2) Ber(1/2). This is the parameter regime used for the IGC densities in Figure 4 and for the scaling experiment in panel (a) of Figure 5. In this regime, the marginal-matched reference is the unfavorable choice, with numerical results showing its aggregate IGC growing as Θ⁡(d) ( d) in dimension d relative to the uniform and absorbing-state references. Ensemble B: For the second ensemble, we instead approach the absorbing state. Writing δd≔1−ϵd _d 1- _d, we take δd≔1d _d 1d and ϵd=1−1d _d=1- 1d, so that the bivariate PMF takes the form Pϵd(0,0) P_ _d(0,0) =1−1d, =1- 1d, Pϵd(0,1) P_ _d(0,1) =0, =0, Pϵd(1,0) P_ _d(1,0) =12d, = 12d, Pϵd(1,1) P_ _d(1,1) =12d. = 12d. The target therefore concentrates around the absorbing configuration (0,0)(0,0) as d grows. Nevertheless, the absorbing-state reference is substantially less favorable than the uniform reference: as shown in panel (b) of Figure 5, the aggregate IGC for the uniform reference remains of constant order, whereas that of the absorbing-state reference exhibits a growth rate of Θ⁡(log⁡d) ( d). 3.3 The bivariate IGC kernel and its structure As noted in the introduction, our analysis of PRD sampling differs from our previous analyses of Gaussian and masking diffusion samplers [36, 37] in an important way. In particular, while the latter samplers have a complexity structure that is essentially univariate in nature, the IGC setting leads to a bivariate structure. This section is devoted to an exploration of the bivariate IGC kernel that underlies our analysis. Let r⁡(η)=eη1+eηr(η)= e^η1+e^η be the transformation from log-SR-odds time back to squared reliability time. For each coordinate i=1,…,di=1,…,d, we define the log-SR-odds cut mutual information Ci(ξ,η)≔Info⁡(Xr⁡(ξ),i;Xr⁡(η),−i)=⁡(Xr⁡(ξ),i,Xr⁡(η),−i)−⁡(Xr⁡(η),−i). C_i(ξ,η) (X_r(ξ),i;X_r(η),-i )\;=\; TC (X_r(ξ),i,X_r(η),-i )- TC (X_r(η),-i ). (20a) Here ∂1 _1 and ∂2 _2 denote differentiation in the first and second arguments of CiC_i, respectively. Taking the mixed partial derivative across the two arguments and then aggregating these derivatives across coordinates yields the bivariate IGC kernel IGC(η,ξ) Q_ @scalerel@objIGC (η,ξ) ≔∑i=1d∂1∂2Ci(ξ,η). _i=1^d _1 _2C_i(ξ,η). (20b) When evaluated on the diagonal, it turns out that we have the equivalence ⁡(η)=IGC(η,η) q(η)= Q_ @scalerel@objIGC (η,η), so that it is intimately connected to the univariate IGC density. See Lemma 3 for the proof of this equivalence. 3.3.1 Integral representations using IGC Q_ @scalerel@objIGC Naturally, a key quantity in the proof of Theorem 1 is the one-step KL discretization error, given by Γ prod (p,q) _ @scalerel@objprod(p,q) ≔Xp[D KL (p,q(⋅∣Xp)∥~p,q(⋅∣Xp))]. _X_p [D_ @scalerel@objKL (K_p,q( · X_p)\, \|\, K_p,q( · X_p) ) ]. (21a) We now show how IGC Q_ @scalerel@objIGC is fundamental in that it simultaneously provides integral representations of the KL one-step error (21a), the IGC increment, and the (dual) total correlation functions. Proposition 1. For any pair 0<a<b<10<a<b<1, we can write the KL product-reference error over the interval [a,b][a,b] as Γ prod (a,b) _ @scalerel@objprod(a,b) =∫φ⁡(a)φ⁡(b)∫ηφ⁡(b)IGC(η,ξ)ξη. = _ (a) (b) _η (b) Q_ @scalerel@objIGC (η,ξ)\,dξ\,dη. (22a) Moreover, the associated IGC increment takes the form ⁡(a,b) G(a,b) =∫φ⁡(a)φ⁡(b)IGC(η,η)η. = _ (a) (b) Q_ @scalerel@objIGC (η,η)\,dη. (22b) Finally, the total correlation ( TC) and dual total correlation ( DTC) have the representations ⁡(Z)=()∫−∞∫η∞IGC(η,ξ)ξη,and⁡(Z)=()∫−∞∫−∞ηIGC(η,ξ)ξη. TC(Z) ( TC)= _-∞^∞ _η^∞ Q_ @scalerel@objIGC (η,ξ)\,dξ\,dη, and DTC(Z) ( DTC)= _-∞^∞ _-∞^η Q_ @scalerel@objIGC (η,ξ)\,dξ\,dη. (22c) We prove the exact KL representation (22a) and the IGC representation (22b) as part of the proof of Theorem 1; in particular, see Lemma 3. Finally, we prove the two representations (22c) in Appendix B. 3.3.2 Exponential IGC Q_ @scalerel@objIGC -structure and its consequences As part of the proof of Lemma 3, we show that the univariate IGC density ⁡(η)=IGC(η,η) q(η)= Q_ @scalerel@objIGC (η,η) corresponds to the diagonal of the bivariate IGC kernel. This equivalence underlies the IGC increment relation (22b). We next isolate a key structural property of the bivariate IGC kernel IGC Q_ @scalerel@objIGC that controls this difference, and thereby leads to upper bounds on the aggregate IGC mass ⁡(0,1) G(0,1) in terms of total correlation and dual total correlation. A key property of the log-SR-odds parameterization is that the bivariate IGC kernel at an off-diagonal value IGC(η,ξ) Q_ @scalerel@objIGC (η,ξ) has a sandwich that is exponential in the difference |η−ξ||η-ξ|. More precisely, we have: Lemma 1 (Exponential sandwich for bivariate IGC density). For every η,ξ∈η,ξ∈ , we have the sandwich relation 12e−|ξ−η|IGC(η,η) 12e^-|ξ-η| Q_ @scalerel@objIGC (η,η) ≤(i)IGC(η,ξ)≤(ii)2e|ξ−η|IGC(η,η). (i)≤ Q_ @scalerel@objIGC (η,ξ)\; (i)≤2e^|ξ-η| Q_ @scalerel@objIGC (η,η). (23) See Section 5.1.3 for the proof of this claim, which is a key result in the paper. Underlying the comparison (23) is a type of (reverse) data processing inequality (DPI) that is satisfied by the relative entropy production function (derivative of the KL divergence) for distributions along the noising path; see Lemma 4 for details. For analyzing (dual) total correlation, only the lower inequality (i) is relevant. We make use of the upper inequality when analyzing a data-dependent sandwich estimator in Proposition 3. This lemma, when combined with the integral representations (22c) from Proposition 1, has an immediate consequence: Corollary 2 (Upper bounds via TC and DTC). The aggregate IGC complexity is upper bounded as ⁡(0,1) G(0,1) ≤2min⁡(Z),⁡(Z). ≤ 2\; \ TC(Z),\; DTC(Z)\. (24) Proof. We give the proof here, since it is a straightforward consequence of Lemma 1 and Proposition 1. On the upper half-plane ξ≥ηξ≥η, inequality (23)(i) gives IGC(η,ξ)≥12e−(ξ−η)IGC(η,η) Q_ @scalerel@objIGC (η,ξ)≥ 12e^-(ξ-η) Q_ @scalerel@objIGC (η,η). Consequently, representation (22c) yields ⁡(Z) TC(Z) ≥12∫−∞IGC(η,η)∫η∞e−(ξ−η)ξη=12∫−∞IGC(η,η)η=12(0,1). ≥ 12 _-∞^∞ Q_ @scalerel@objIGC (η,η) \ _η^∞e^-(ξ-η)\,dξ \\,dη\;=\; 12 _-∞^∞ Q_ @scalerel@objIGC (η,η)\,dη= 12 G(0,1). The same argument on the lower half-plane gives the DTC bound, and combining the two bounds yields the claim. ∎ 4 Multi-block analysis and certification Thus far, we have exploited Theorem 1 only in a simple way, via an equi-spaced grid (17) in log-SR-odds. As in our past papers [37, 36], its simple structure leads naturally to bounds based on multi-block schedules, which tailor the spacing of the stepsizes to the underlying structure of the IGC density. This section is devoted to exploration of such guarantees, along with data-dependent ways of estimating the IGC increments that define optimal schedules. Notably, in Proposition 3, we introduce a sandwich estimator for the IGC increments that is based on a novel Bregman divergence that emerges naturally from our analysis. This provides a practical way of estimating both IGC increments and KL error. 4.1 A multi-block guarantee Throughout this section, we use ψ⁡(r)≔r/(1−r)ψ(r) r/(1-r) for the SR-odds ratio, and φ⁡(r)=log⁡(r/(1−r)) (r)= (r/(1-r)) for the log-odds ratio. For a given interval [r0,R][r_0,R] with 0<r0<R<10<r_0<R<1, suppose that we partition it into a collection of K blocks, say of the form ≔[bk,bk+1]∣k=0,…,K−1,b0=r0,bK=R. \[b_k,b_k+1] k=0,…,K-1 \, b_0=r_0, b_K=R. For each block, define its log-SR-odds length and IGC mass by k≔φ⁡(bk+1)−φ⁡(bk) S_k (b_k+1)- (b_k) and k≔⁡(bk,bk+1) G_k G(b_k,b_k+1). Suppose that a total of NkN_k equal-log-odds steps are allocated to block k. Then an application of Theorem 1 gives D KL (ℙZ∥ℙZ^) D_ @scalerel@objKL(P_Z\|P_ Z) ≤2∑k=0K−1[exp⁡kNk−1]k+⁡(Xr0)+⁡(Z∣XR). ≤ 2 _k=0^K-1 [ \ S_kN_k \-1 ] G_k+ TC(X_r_0)+ TC(Z X_R). (25a) In principle, for a given iteration budget N, one could solve the integer programming problem of minimizing this upper bound subject to the constraint ∑k=0K−1Nk=N _k=0^K-1N_k=N. Apart from constant factor differences, this turns out to be unnecessary. In particular, we now state a bound in terms of the IGC partition complexity given by IGC () C_ @scalerel@objIGC (P) ≔(∑k=0K−1kk)2. ( _k=0^K-1 S_k G_k )^2. (25b) We analyze the PRD scheme that traverses block k using an equi-spaced grid for which 1+ρk1+ _k is the maximum odds multiplier for a step. Equivalently, the log-odds spacing is at most log⁡(1+ρk) (1+ _k), where we define ρk _k ≔min1,4 IGC ()Nkk,k=0,…,K−1. \1,\, 4 C_ @scalerel@objIGC (P)N S_k G_k \, k=0,…,K-1. (25c) Proposition 2 (Constant-factor optimal guarantees for a K-block partition). Given an iteration budget N≥2K+2(φ⁡(R)−φ⁡(r0))N≥ 2 \K+2 ( (R)- (r_0) ) \, the K-block sampler over [r0,R][r_0,R] with maximum within-block odds multipliers 1+ρk1+ _k as defined in equation (25c) uses at most N rounds, and returns a sample Z Z such that D KL (ℙZ∥ℙZ^) D_ @scalerel@objKL(P_Z\|P_ Z) ≤8 IGC ()N+⁡(Xr0)+⁡(Z∣XR). ≤ 8 C_ @scalerel@objIGC (P)N+ TC(X_r_0)+ TC(Z X_R). (26) This explicit allocation is within a factor of four of the best bound (25a) for the given partition. The proof follows mutatis mutandis from our previous paper [37], with suitable replacements of the relevant complexities. The only change is that the factor two in Theorem 1 propagates to the bound (26). We note that partitioning can only improve the coarse complexity. Indeed, by combining the additivity of the IGC function G with the Cauchy–Schwarz inequality, we are guaranteed the ordering relation IGC (′) C_ @scalerel@objIGC (P ) ≤ IGC ()≤φ⁡(R)−φ⁡(r0)(r0,R), ≤ C_ @scalerel@objIGC (P)\;≤\; \ (R)- (r_0) \ G(r_0,R), (27) for any pair ′⊂P of nested partitions. For the full symmetric interval ℐ full I_ @scalerel@objfull, the right-hand side is exactly the single block complexity IGC C_ @scalerel@objIGC from equation (3a). Strict improvement occurs whenever the blockwise IGC mass is not proportional to log-odds length. In contrast to Corollary 1, for which the stepsize choice required no knowledge of data-dependent parameters, the odds-multiplier parameters (25c) that underlie Proposition 2 are based on the IGC increments k G_k for each block. Accordingly, in order to harness the power of the result, we need to develop a method, assuming access to some collection of samples from ℙZP_Z, for reliably estimating these increments. 4.2 Bregman-based estimation of IGC increments and KL error We now turn to the key question of how to estimate the IGC increments. It turns out that there is a hidden Bregman divergence, one that is revealed by the proof of Theorem 1, that can be used both to give a sandwich relation for the IGC increments, and an exact relation for the KL error (40a). For each coordinate i=1,…,di=1,…,d, any probability vector p on A and reliability s∈[0,1]s∈[0,1], we define the path i,s(p) _i,s(p) ≔sp+(1−s)νi. sp+(1-s) _i. (28a) Note that this operator transforms p along the path, parameterized by the reliability s. For each coordinate i∈[d]i∈[d] and squared reliability r∈(0,1)r∈(0,1), we use μr,i LOO (⋅,Xr,−i)μ @scalerel@objLOO_r,i(·,X_r,-i) to denote the random leave-one-out posterior probability vector. Fix 0<a<b<10<a<b<1, and for any anchor u∈[a,b]u∈[a,b], we define the anchored IGC increment u(a,b) D_u(a,b) ≔u⁡(1−u)∑i=1d⁡[duD KL (i,u(μb,i LOO (⋅,Xb,−i))∥i,u(μa,i LOO (⋅,Xa,−i)))]. u(1-u) _i=1^dE [ dduD_ @scalerel@objKL (T_i, u (μ @scalerel@objLOO_b,i(·,X_b,-i) )\, \|\,T_i, u (μ @scalerel@objLOO_a,i(·,X_a,-i) ) ) ]. (28b) Although this function appears to require computing derivatives of the KL along the path, it turns out that this KL derivative is itself equal to a different Bregman divergence. At a high level, this correspondence arises because the map i,sT_i,s is linear in the parameter; the KL divergence is itself a Bregman divergence; and Bregman divergences have a linear representation in terms of their generators. For full details, see equation (45) in the proof of Lemma 4, and the explicit computation of the Bregman generator in equation (46a). This explicit Bregman representation is critical, because it means that we can use samples to obtain an explicit unbiased estimate of u(a,b) D_u(a,b). The anchored IGC increment turns out to have some special properties, ones which allow us to relate it to both the exact KL error and the IGC increment for any interval [a,b][a,b]. More precisely, for any triple 0<a<u<b<10<a<u<b<1, let us introduce the shorthand cu(a,b)≔max⁡ψ⁡(u)ψ⁡(a),ψ⁡(b)ψ⁡(u)c_u(a,b) \ ψ(u)ψ(a), ψ(b)ψ(u) \, where ψ⁡(r)=r/(1−r)ψ(r)=r/(1-r) is the odds ratio. Proposition 3 (Bregman-based estimation of KL error and IGC increments). For any choice of u∈[a,b]u∈[a,b], the IGC increment is sandwiched as 12cu(a,b)u(a,b) 12c_u(a,b) D_u(a,b) ≤⁡(a,b)≤2cu(a,b)u(a,b). ≤ G(a,b)≤ 2c_u(a,b) D_u(a,b). (29a) Moreover, the one-step KL error (40a) is equal to Γ prod (a,b) _ @scalerel@objprod(a,b) =∫abv(a,v)v⁡(1−v)v. = _a^b D_v(a,v)v(1-v)\,dv. (29b) See Section 5.2 for the proof. In terms of the sandwich relation (29a), a particularly convenient choice of u is the log-odds midpoint u⋆u_ , defined by the relation φ⁡(u⋆)=φ⁡(a)+φ⁡(b)2 (u_ )= (a)+ (b)2. This choice ensures that 12ψ⁡(a)ψ⁡(b)u⋆(a,b) 12 ψ(a)ψ(b) D_u_ (a,b) ≤⁡(a,b)≤2ψ⁡(b)ψ⁡(a)u⋆(a,b), ≤ G(a,b)≤ 2 ψ(b)ψ(a) D_u_ (a,b), (30) so that we have the natural factor-two sandwich. In summary, Proposition 3 provides a population-level characterization of both the KL error and the IGC increment as an expectation involving the IGC anchor functions u D_u. Thus, if we are given a collection of clean samples Z(ℓ)ℓ=1m\Z^( )\_ =1^m from ℙZP_Z, then we can use them to generate a collection of noisy trajectories on a discretized grid of squared-reliability times. Plugging these samples into the representation (28b) then yields an unbiased Monte Carlo estimate. In our previous work [37, 36], we proposed and analyzed a tail-robust estimator, based on only a moment bound and a form of truncation. We can adapt this estimator to the current setting, and use it to guarantee that, for a given sample size m, we can generate data-dependent quantities ^k G_k and an upper confidence function r^k,m(δ) r_k,m(δ) such that, for any δ∈(0,1)δ∈(0,1), we have k G_k ≤^k+r^k,m(δ)with probability at least 1−δ. ≤ G_k+ r_k,m(δ) with probability at least $1-δ$. (31) Note that the confidence bound r^k,m r_k,m depends on the block k and the number m of clean samples Z, and under mild moment conditions, for a fixed δ∈(0,1)δ∈(0,1), we have r^k,m(δ)=(m−1/2) r_k,m(δ)=O(m^-1/2) as m grows. This guarantee is a direct application of our previous results, so that we omit the details here. 4.3 Data-certified multi-block guarantee We are now set up to combine Proposition 2 with Proposition 3 so as to obtain an end-to-end guarantee for a multi-block PRD sampler. Fix a partition P and a failure probability η∈(0,1)η∈(0,1). Compute the estimator with failure probability δ≔η/Kδ η/K for each block. We are thus given data-dependent quantities ^k G_k and tolerances r^k≡r^k,m(η/K) r_k≡ r_k,m(η/K) such that k≤^k+r^kfor all k=0,…,K−1, with probability at least 1−η. G_k≤ G_k+ r_k for all $k=0,…,K-1$, with probability at least $1-η$. (32a) Define the certified partition complexity IGC () C_ @scalerel@objIGC (P) ≔(∑k=0K−1k(^k+r^k))2. ( _k=0^K-1 S_k ( G_k+ r_k ) )^2. (32b) The certified odds-multiplier parameters are ρ^k ρ_k ≔min1,4 IGC ()Nk^k+r^k,k=0,…,K−1, \1,\, 4 C_ @scalerel@objIGC (P)N S_k G_k+ r_k \, k=0,…,K-1, (32c) Thus, within block k, the maximum certified odds multiplier is 1+ρ^k1+ ρ_k, equivalently the log-odds spacing is at most log⁡(1+ρ^k) (1+ ρ_k). Theorem 2 (Data-certified multi-block guarantee). Given an iteration budget N≥2K+2(φ⁡(R)−φ⁡(r0))N≥ 2 \K+2 ( (R)- (r_0) ) \ and the simultaneous confidence event (32a), the K-block sampler with maximum within-block odds multipliers 1+ρ^k1+ ρ_k determined by the parameters (32c) has output Z Z such that D KL (ℙZ∥ℙZ^) D_ @scalerel@objKL(P_Z\|P_ Z) ≤8 IGC ()N+⁡(Xr0)+⁡(Z∣XR), ≤ 8 C_ @scalerel@objIGC (P)N+ TC(X_r_0)+ TC(Z X_R), (33) with probability at least 1−η1-η. The proof follows by the same argument as in [37], with suitable replacements. 4.4 The IGC density and optimal Euler discretizations Finally, we can pass from finitely many blocks to the fine-partition limit. From the partition-refinement inequality (27), by a sequence of progressively refined K-block partitions, we can approach the fine-partition limit IGC(ℐ full ) P_ @scalerel@objIGC (I_ @scalerel@objfull) ≔inf IGC (), _P C_ @scalerel@objIGC (P), (34) where the infimum is over all finite partitions of ℐ full I_ @scalerel@objfull. The next result identifies this quantity with the square-root integral introduced in (3b), and shows that the same quantity governs the sharp leading-order Euler error. Theorem 3 (Fine-partition limit and Euler optimality). Assume that the mixed partial derivatives appearing in Lemma 3 are continuous on the compact log-odds region associated with ℐ full I_ @scalerel@objfull, and that q is strictly positive on [−ℓd,ℓd][- _d, _d]. Then we have the equivalence IGC(ℐ full ) P_ @scalerel@objIGC (I_ @scalerel@objfull) =(∫−ℓdℓd⁡(λ)λ)2≡IGC. = ( _- _d _d q(λ)\,dλ )^2≡ P_ @scalerel@objIGC . (35a) Moreover, for the log-odds-uniform grid (17), the sum of exact KL one-step errors satisfies ∑j=0N−1Γ prod (rj,rj+1) _j=0^N-1 _ @scalerel@objprod(r_j,r_j+1) = IGC 2N+o⁡(N−1), = C_ @scalerel@objIGC 2N+o(N^-1), (35b) Finally, the optimal N-step discretization satisfies infr0=r0<r1<⋯<rN=1−r0∑j=0N−1Γ prod (rj,rj+1) _r_0=r_0<r_1<·s<r_N=1-r_0 _j=0^N-1 _ @scalerel@objprod(r_j,r_j+1) =IGC2N+o⁡(N−1). = P_ @scalerel@objIGC 2N+o(N^-1). (35c) The proof is the same fine-partition argument as in our past work on masking [37]. 5 Proofs We now turn to the proofs of our main results. The proof of Theorem 1 is given in Section 5.1, whereas Section 5.2 contains the proof of Proposition 3. 5.1 Proof of Theorem 1 Recall that Xt,t∈[0,1]\X_t,t∈[0,1]\ corresponds to the denoising process (1b), which transitions from the product-reference distribution X0∼⨂i=1dνiX_0 _i=1^d _i to X1∼ℙZX_1 _Z. For any pair 0<p<q<10<p<q<1, let p,qK_p,q denote the transition kernel of this denoising process in moving from XpX_p to XqX_q. On the other hand, our denoising sampler is based on the update (10b) and we let ~p,q K_p,q denote the associated transition kernel that moves from X^p X_p to X^q X_q. We introduce the shorthand notation Γ prod (p,q) _ @scalerel@objprod(p,q) ≔Xp[D KL (p,q(⋅∣Xp)∥~p,q(⋅∣Xp))]. _X_p [D_ @scalerel@objKL (K_p,q( · X_p)\, \|\, K_p,q( · X_p) ) ]. (36) corresponding to the averaged Kullback–Leibler (KL) discrepancy between the two transition kernels over the interval [p,q][p,q]. Here the expectation is taken over the marginal distribution of the variable XpX_p along the denoising path. By the data-processing inequality combined with the chain rule for KL divergence, we have D KL (ℙZ∥ℙZ^) D_ @scalerel@objKL(P_Z\|P_ Z) ≤∑j=0N−1Γ prod (rj,rj+1)+⁡(Xr0)+⁡(Z∣XR). ≤ _j=0^N-1 _ @scalerel@objprod(r_j,r_j+1)+ TC(X_r_0)+ TC(Z X_R). (37) Thus, the central challenge is to bound the one-step KL errors Γ prod (rj,rj+1) _ @scalerel@objprod(r_j,r_j+1). The following result provides the requisite control. Lemma 2. For any 0<a<b<10<a<b<1, the one-step KL error satisfies the bound Γ prod (a,b) _ @scalerel@objprod(a,b) ≤2ψ⁡(b)ψ⁡(a)−1(a,b), ≤ 2 \ ψ(b)ψ(a)-1 \ G(a,b), (38) where ψ⁡(r)≔r/(1−r)ψ(r) r/(1-r). See Section 5.1.1 for the proof of this claim. To complete the proof of Theorem 1, we apply Lemma 2 to each of the intervals [rj,rj+1][r_j,r_j+1]. Collecting the terms yields the claim (13). 5.1.1 Proof of Lemma 2 This proof is based on two lemmas, each of which is of independent interest in its own right. The first is the previously stated Lemma 1, which guarantees that 12e−|ξ−η|IGC(η,η) 12e^-|ξ-η| Q_ @scalerel@objIGC (η,η) ≤(i)IGC(η,ξ)≤(ii)2e|ξ−η|IGC(η,η). (i)≤ Q_ @scalerel@objIGC (η,ξ)\; (i)≤2e^|ξ-η| Q_ @scalerel@objIGC (η,η). (39) We used the lower bound (i) previously in comparing the coarse IGC mass to the (dual) total correlations. In this proof, the relevant result is the upper bound (i). See Section 5.1.3 for the proof of Lemma 1. The second piece in the proof of Lemma 2 is an exact representation of the one-step KL error in terms of the bivariate IGC kernel IGC Q_ @scalerel@objIGC . This result is also of independent interest. Lemma 3 (Exact representation of the one-step KL divergence). For any pair 0<a<b<10<a<b<1, the one-step KL divergence (21a) has the exact representation Γ prod (a,b) _ @scalerel@objprod(a,b) =∫λ⁡(a)λ⁡(b)∫ηλ⁡(b)IGC(η,ξ)dξdηwhere λ⁡(r)=log⁡(r/(1−r)). = _λ(a)^λ(b) _η^λ(b) Q_ @scalerel@objIGC (η,ξ)\,dξ\,dη where $λ(r)= (r/(1-r))$. (40a) Moreover, assuming that IGC Q_ @scalerel@objIGC is continuous, we have the pointwise expansion Γ prod (a,b) _ @scalerel@objprod(a,b) =12IGC(λ(a),λ(a))Δ2+o(Δ2) where Δ≔λ⁡(b)−λ⁡(a). = 12 Q_ @scalerel@objIGC (λ(a),λ(a))\; ^2+o( ^2) where $ λ(b)-λ(a)$. (40b) Finally, we have the equivalence ⁡(λ) q(λ) =IGC(λ,λ)for all λ∈. = Q_ @scalerel@objIGC (λ,λ) for all $λ∈ $. (40c) See Section 5.1.2 for the proof. We note that Lemma 2 is a straightforward consequence of the upper inequality (i) in equation (39), and the KL representation in Lemma 3. In particular, we have Γ prod (a,b)=(i)∫λ⁡(a)λ⁡(b)∫ηλ⁡(b)IGC(η,ξ)ξη _ @scalerel@objprod(a,b)\; (i)=\; _λ(a)^λ(b) _η^λ(b) Q_ @scalerel@objIGC (η,ξ)\,dξ\,dη ≤(ii)2∫λ⁡(a)λ⁡(b)∫ηλ⁡(b)eξ−ηIGC(η,η)ξη (i)≤2 _λ(a)^λ(b) _η^λ(b)e^ξ-η Q_ @scalerel@objIGC (η,η)\,dξ\,dη =2∫λ⁡(a)λ⁡(b)eλ⁡(b)−η−1IGC(η,η)η =2 _λ(a)^λ(b) \e^λ(b)-η-1 \ Q_ @scalerel@objIGC (η,η)\,dη ≤(iii)2eλ⁡(b)−λ⁡(a)−1∫λ⁡(a)λ⁡(b)IGC(η,η)η (i)≤2 \e^λ(b)-λ(a)-1 \ _λ(a)^λ(b) Q_ @scalerel@objIGC (η,η)\,dη =2ψ⁡(b)ψ⁡(a)−1(a,b), =2 \ ψ(b)ψ(a)-1 \ G(a,b), where step (i) uses Lemma 3; step (i) uses equation (39); and step (i) follows from the lower bound η≥λ⁡(a)η≥λ(a) and the non-negativity of IGC(η,η) Q_ @scalerel@objIGC (η,η). 5.1.2 Proof of Lemma 3 We split our proof into three parts, one for each claim. Proof of the exact representation (40a): Introducing the shorthand α≔λ⁡(a)α λ(a) and β≔λ⁡(b)β λ(b), we introduce the functions T⁡(ξ)≔⁡(Xr⁡(ξ))T(ξ) TC(X_r(ξ)) and Ai(ξ)≔⁡(Xr⁡(ξ),i,Xa,−i)A_i(ξ) TC (X_r(ξ),i,X_a,-i ). By the definition (20a) of CiC_i, we have Ai′(ξ)=∂1Ci(ξ,α)A_i (ξ)= _1C_i(ξ,α), and we prove in Appendix B that T′(ξ)=∑i=1d∂1Ci(ξ,ξ)T (ξ)= _i=1^d _1C_i(ξ,ξ). To verify the decomposition, writing U≔XbU X_b and V≔XaV X_a, coordinatewise independence of the channel gives ⁡(U∣V)=∑i=1dEnt⁡(Ui∣V)−Ent⁡(U∣V) TC(U V)= _i=1^dEnt(U_i V)-Ent(U V) =∑i=1dEnt⁡(Ui,V−i)−(d−1)Ent⁡(V)−Ent⁡(U) = _i=1^dEnt(U_i,V_-i)-(d-1)Ent(V)-Ent(U) =⁡(U)−⁡(V)−∑i=1d⁡(Ui,V−i)−⁡(V), = \ TC(U)- TC(V) \- _i=1^d \ TC(U_i,V_-i)- TC(V) \, where the second equality follows by cancellation of the terms ∑i=1dEnt⁡(Vi∣Ui) _i=1^dEnt(V_i U_i). Combined with the identity Γ prod (a,b)=⁡(Xb∣Xa) _ @scalerel@objprod(a,b)= TC(X_b X_a), substituting the definitions of T and AiA_i yields Γ prod (a,b)=T⁡(β)−T⁡(α)−∑i=1dAi(β)−Ai(α). _ @scalerel@objprod(a,b)= \T(β)-T(α) \- _i=1^d \A_i(β)-A_i(α) \. Combining the ingredients, we find that Γ prod (a,b)=∑i=1d∫αβ∂1Ci(ξ,ξ)−∂1Ci(ξ,α)ξ _ @scalerel@objprod(a,b)= _i=1^d _α^β \ _1C_i(ξ,ξ)- _1C_i(ξ,α) \\,dξ =(i)∑i=1d∫αβ∫αξ∂1∂2Ci(ξ,η)ηξ (i)= _i=1^d _α^β _α^ξ _1 _2C_i(ξ,η)\,dη\,dξ =(ii)∫αβ∫αξIGC(η,ξ)ηξ (i)= _α^β _α^ξ Q_ @scalerel@objIGC (η,ξ)\,dη\,dξ =(iii)∫αβ∫ηβIGC(η,ξ)ξη, (i)= _α^β _η^β Q_ @scalerel@objIGC (η,ξ)\,dξ\,dη, where step (i) follows from the fundamental theorem of calculus; step (i) follows from the definition of IGC Q_ @scalerel@objIGC ; and step (i) follows by reversing the order of integration over the triangle α≤η≤ξ≤βα≤η≤ξ≤β. Proof of the pointwise expansion (40b): Introduce the shorthand α≔λ⁡(a)α λ(a) and Δ≔λ⁡(b)−λ⁡(a) λ(b)-λ(a). By the continuity of IGC Q_ @scalerel@objIGC at (α,α)(α,α), we have supα≤η≤ξ≤α+Δ|IGC(η,ξ)−IGC(α,α)|=o⁡(1) _α≤η≤ξ≤α+ | Q_ @scalerel@objIGC (η,ξ)- Q_ @scalerel@objIGC (α,α) |=o(1) as Δ↓0 0. Since the integration triangle has area Δ2/2 ^2/2, it follows that Γ prod (a,b) _ @scalerel@objprod(a,b) =IGC(α,α)∫α+Δ∫ηα+Δdξη+o⁡(Δ2)=12IGC(α,α)Δ2+o⁡(Δ2)=12(λ⁡(a))Δ2+o⁡(Δ2), = Q_ @scalerel@objIGC (α,α) _α^α+ _η^α+ \,dξ\,dη+o( ^2)\;=\; 12 Q_ @scalerel@objIGC (α,α) ^2+o( ^2)\;=\; 12 q(λ(a)) ^2+o( ^2), which proves the claim. Proof of the equivalence (40c): Define the mutual-information surface F⁡()≔Info⁡(Z;X⁡())F( λ) (Z;X_r( λ) ), where r⁡(λk)≔eλk1+eλkr( _k) e _k1+e _k. In terms of this function, we have ⁡(λ) q(λ) =−∑i≠j∂2F⁡()∂λi∂λj|=λ. =- _i≠ j . ∂^2F( λ)∂ _i∂ _j |_ λ= 1. (41) Now fix a coordinate i. Since the coordinatewise refresh channels are conditionally independent given Z, we have Ci(ξ,η) C_i(ξ,η) =Info⁡(Z;Xr⁡(ξ),i)+Info⁡(Z;Xr⁡(η),−i)−F⁡(ξi+η⁡(−i)). =Info (Z;X_r(ξ),i )+Info (Z;X_r(η),-i )-F ( _i+η(1-e_i) ). The first two terms depend on only one of (ξ,η)(ξ,η), and therefore ∂1∂2Ci(ξ,η) _1 _2C_i(ξ,η) =−∑j≠i∂2F⁡()∂λi∂λj|=ξi+η⁡(−i). =- _j≠ i . ∂^2F( λ)∂ _i∂ _j |_ λ= _i+η(1-e_i). Setting ξ=η=λξ=η=λ and summing over i now gives IGC(λ,λ) Q_ @scalerel@objIGC (λ,λ) =∑i=1d∂1∂2Ci(λ,λ)=−∑i≠j∂2F⁡()∂λi∂λj|=λ=(λ), = _i=1^d _1 _2C_i(λ,λ)\;=\;- _i≠ j . ∂^2F( λ)∂ _i∂ _j |_ λ= 1= q(λ), where the last equality follows from equation (41). 5.1.3 Proof of Lemma 1 Our proof makes use of an auxiliary result, one which exploits the geometry of our noising path in an essential way. Recalling that r⁡(λ)=eλ1+eλr(λ)= e^λ1+e^λ, we let sλ=r⁡(λ)s_λ= r(λ) denote the ordinary reliability at level λ. For any reference distribution ν over A, we define the path λ(p) _λ(p) =sλp+(1−sλ)ν,for sλ∈[0,1]. =s_λp+(1-s_λ)ν, for $s_λ∈[0,1]$. (42a) This path describes the evolution from the reference distribution at time sλ=0s_λ=0 to its argument p at time sλ=1s_λ=1. We then define the λ-indexed family of KL divergences λ(p,q) K_λ(p,q) ≔D KL (λ(p)∥λ(q)), D_ @scalerel@objKL (T_λ(p)\|T_λ(q) ), (42b) as well as its derivative λ(p,q) J_λ(p,q) ≔dλλ(p,q). ddλ K_λ(p,q). (42c) By the data-processing inequality, we have α(p,q)≤β(p,q) K_α(p,q)≤ K_β(p,q) whenever α<βα<β, from which it follows that λ(p,q)≥0 J_λ(p,q)≥ 0 for all λ∈λ∈ . Lemma 4 (Exponential control along the path). Fix an arbitrary pair p,qp,q of probability distributions over A. Then for all α,β∈α,β∈ , we have the sandwich relation 12e−|β−α|α(p,q) 12e^-|β-α| J_α(p,q) ≤β(p,q)≤2e|β−α|α(p,q). ≤ J_β(p,q)≤ 2e^|β-α| J_α(p,q). (43) See Section 5.1.4 for the proof of this claim. We now use Lemma 4 to complete the proof of Lemma 1. Fix a coordinate i and log-SR-odds times η∈η∈ and η+hη+h, where h>0h>0. Write πi,ζ≔ℒ⁡(Zi∣Xr⁡(ζ),−i) _i,ζ (Z_i X_r(ζ),-i ) for the leave-one-out posterior at log-SR-odds level ζ. Let sξ≔r⁡(ξ)s_ξ r(ξ) be the ordinary reliability time associated with ξ. Since h>0h>0, our (backward) noising process generates Xr⁡(η),−iX_r(η),-i by adding additional independent noise to Xr⁡(η+h),−iX_r(η+h),-i, meaning that the triple Xr⁡(ξ),i⟶Xr⁡(η+h),−i⟶Xr⁡(η),−iX_r(ξ),i X_r(η+h),-i X_r(η),-i forms a Markov chain. Consequently, we have Ci(ξ,η+h)−Ci(ξ,η) C_i(ξ,η+h)-C_i(ξ,η) =(i)Info⁡(Xr⁡(ξ),i;Xr⁡(η+h),−i∣Xr⁡(η),−i)=(ii)⁡[ξ(πi,η+h,πi,η)], (i)=Info (X_r(ξ),i;X_r(η+h),-i X_r(η),-i )\; (i)=\;E [ K_ξ ( _i,η+h, _i,η ) ], (44a) where step (i) uses the chain rule for mutual information; and step (i) uses the posterior tower property, the representation of conditional mutual information as an expected KL, together with the definition (42b). Differentiating equation (44a) in its first argument yields ∂1Ci(ξ,η+h)−∂1Ci(ξ,η)=⁡[ξ(πi,η+h,πi,η)] _1C_i(ξ,η+h)- _1C_i(ξ,η)=E [ J_ξ ( _i,η+h, _i,η ) ], and hence ∂1∂2Ci(ξ,η) _1 _2C_i(ξ,η) =limh↓01h[ξ(πi,η+h,πi,η)]. = _h 0 1hE [ J_ξ ( _i,η+h, _i,η ) ]. (44b) The sandwich bound (43) from Lemma 4 guarantees that 12e−|ξ−η|η(πi,η+h,πi,η) 12e^-|ξ-η| J_η ( _i,η+h, _i,η ) ≤ξ(πi,η+h,πi,η)≤2e|ξ−η|η(πi,η+h,πi,η). ≤ J_ξ ( _i,η+h, _i,η )≤ 2e^|ξ-η| J_η ( _i,η+h, _i,η ). We now take expectations, divide by h>0h>0, and pass to the limit. Combined with equation (44b), we see that 12e−|ξ−η|∂1∂2Ci(η,η) 12e^-|ξ-η| _1 _2C_i(η,η) ≤∂1∂2Ci(ξ,η)≤2e|ξ−η|∂1∂2Ci(η,η). ≤ _1 _2C_i(ξ,η)≤ 2e^|ξ-η| _1 _2C_i(η,η). Summing over coordinates i yields the claim (23). 5.1.4 Proof of Lemma 4 Suppose first that ν has full support. Recall that the function ϕ⁡(x)≔xlog⁡xφ(x) x x generates the KL divergence as the Bregman divergence ϕ B_φ given by D KL (p∥q) D_ @scalerel@objKL(p\|q) ≡ϕ(p∥q)≔∑a∈ϕ(pa)−ϕ(qa)−ϕ′(qa)(pa−qa). ≡ B_φ(p\|q) _a \φ(p_a)-φ(q_a)-φ (q_a)\,(p_a-q_a) \. Recall that λ(p∥q)≔D KL (λ(p)∥λ(q)) K_λ(p\|q) D_ @scalerel@objKL(T_λ(p)\|T_λ(q)) by definition, as well as the definition (42a) of the path λT_λ. Since λT_λ is an affine function, it follows that λ(p∥q) K_λ(p\|q) can be seen as a family of Bregman divergences: in particular, we have λ(p∥q) K_λ(p\|q) =Φλ(p∥q)where Φλ(z)=∑a∈ϕ⁡([λ(z)]a). = B_ _λ(p\|q) where $ _λ(z)=Σ _a φ ([T_λ(z)]_a )$. Since the definition of a Bregman divergence is linear in Φλ _λ, it follows that dλΦλ(p∥q)=λ(p,q)=Ψλ(p∥q),where Ψλ(z)≔dλΦλ(z). ddλ B_ _λ(p\|q)\;=\; J_λ(p,q)\;= B_ _λ(p\|q), where $ _λ(z) ddλ _λ(z)$. (45) Consequently, by the integral form of a Bregman divergence, we can write λ(p,q) J_λ(p,q) =∫01(1−t)(p−q)∇2Ψλ(q+t⁡(p−q))(p−q)t. = _0^1(1-t)(p-q) T∇^2 _λ (q+t(p-q) )(p-q)\,dt. It suffices to consider α<βα<β: the case β<αβ<α follows by interchanging the two parameters and using the resulting bounds in the reverse direction to obtain the symmetric bound in equation (43), while α=βα=β is immediate. Consequently, in order to complete the proof, it suffices to show that 1e⁡(α,β)∇2Ψα(z) 1e(α,β)∇^2 _α(z) ⪯∇2Ψβ(z)⪯2e(α,β)∇2Ψα(z)where e⁡(α,β)≔eβ−α for an arbitrary pair α<β. ∇^2 _β(z) 2e(α,β)∇^2 _α(z) where $e(α,β) e^β-α$ for an arbitrary pair $α<β$. We now compute Ψλ _λ. Observe that dλsλ=12sλ(1−sλ2) ddλs_λ= 12s_λ(1-s_λ^2). Thus, by the chain rule, together with the relation ∑a∈(za−νa)=0 _a (z_a- _a)=0, we obtain Ψλ(z) _λ(z) =12sλ(1−sλ2)∑a∈(za−νa)log⁡[λ(z)]a. = 12s_λ(1-s_λ^2) _a (z_a- _a) [T_λ(z)]_a. (46a) Since Ψλ _λ is additive across coordinates, its Hessian is diagonal with [∇2Ψλ(z)]aa [∇^2 _λ(z)]_a =sλ2(1−sλ2)2[λ(z)]a+νa[λ(z)]a2. = s_λ^2(1-s_λ^2)2 [T_λ(z)]_a+ _a[T_λ(z)]_a^2. (46b) For a fixed α<βα<β, introduce the shorthand s≔sαs s_α and t≔sβt s_β. Since λ is the log-SR-odds parameter, we can compute e⁡(α,β)=eβ−α=t2(1−s2)s2(1−t2)e(α,β)=e^β-α= t^2(1-s^2)s^2(1-t^2). For a fixed symbol a, set x≔za/νax z_a/ _a and yu(x)≔1+u⁡(x−1)y_u(x) 1+u(x-1). Then [α(z)]a=νays(x)[T_α(z)]_a= _ay_s(x) and [β(z)]a=νayt(x)[T_β(z)]_a= _ay_t(x), so that the Hessian from equation (46b) gives the ratio R⁡(x) R(x) ≔[∇2Ψβ(z)]aa[∇2Ψα(z)]aa=t2(1−t2)s2(1−s2)(yt(x)+1)ys2(x)yt2(x)(ys(x)+1). [∇^2 _β(z)]_a[∇^2 _α(z)]_a= t^2(1-t^2)s^2(1-s^2) (y_t(x)+1)y_s^2(x)y_t^2(x)(y_s(x)+1). To complete the proof, it suffices to show that R⁡(x)∈[1e⁡(α,β),2e(α,β)]R(x)∈ [ 1e(α,β),2e(α,β)]. We can compute R′(x) R (x) =t2(1−t2)s2(1−s2)2(s−t)ys(x)(ys(x)+yt(x)+1)(ys(x)+1)2yt3(x)≤0. = t^2(1-t^2)s^2(1-s^2) 2(s-t)y_s(x) (y_s(x)+y_t(x)+1 ) (y_s(x)+1 )^2y_t^3(x)≤ 0. Since s<ts<t, the derivative is nonpositive, so R⁡(x)R(x) must lie between its endpoint values. Note that x=za/νax=z_a/ _a takes values in the interval [0,∞)[0,∞), and we have limx→∞R⁡(x)=1e⁡(α,β)(ts)3≥1e⁡(α,β)andR⁡(0)=e⁡(α,β)(2−t)(1+t)2(2−s)(1+s)2≤2e(α,β), _x→∞R(x)= 1e(α,β) ( ts )^3≥ 1e(α,β) and R(0)=e(α,β) (2-t)(1+t)^2(2-s)(1+s)^2≤ 2e(α,β), where the last inequality uses that the function u↦(2−u)(1+u)2u (2-u)(1+u)^2 increases from 22 to 44 over the interval [0,1][0,1]. Finally, for an arbitrary ν, we can approximate it by a sequence of full-support reference distributions and pass to the limit (assuming that the displayed derivatives are finite). 5.2 Proof of Proposition 3 We introduce the shorthand notation α≔φ⁡(a)α (a), β≔φ⁡(b)β (b), and ξ≔φ⁡(u)ξ (u). By the definitions of u(a,b) D_u(a,b) and IGC Q_ @scalerel@objIGC , we have u(a,b)=∫αβIGC(η,ξ)η,and⁡(a,b)=∫αβIGC(η,η)η. D_u(a,b)= _α^β Q_ @scalerel@objIGC (η,ξ)\,dη, and G(a,b)= _α^β Q_ @scalerel@objIGC (η,η)\,dη. For every η∈[α,β]η∈[α,β], we have e|ξ−η|≤cu(a,b)e^|ξ-η|≤ c_u(a,b). Applying inequality (23) pointwise and integrating gives 12cu(a,b)(a,b) 12c_u(a,b) G(a,b) ≤u(a,b)≤2cu(a,b)(a,b). ≤ D_u(a,b)≤ 2c_u(a,b) G(a,b). Rearranging proves inequality (29a). For the log-odds midpoint, we have cu⋆(a,b)=ψ⁡(b)/ψ⁡(a)c_u_ (a,b)= ψ(b)/ψ(a), which gives inequality (30). It remains to prove the representation (29b) of the one-step KL error. From the integral representation in Proposition 1, we have Γ prod (a,b) _ @scalerel@objprod(a,b) =∫αβ∫ηβIGC(η,ξ)ξη=∫αβ∫αξIGC(η,ξ)ηξ, = _α^β _η^β Q_ @scalerel@objIGC (η,ξ)\,dξ\,dη\;=\; _α^β _α^ξ Q_ @scalerel@objIGC (η,ξ)\,dη\,dξ, where the second equality follows by reversing the order of integration. For each ξ∈[α,β]ξ∈[α,β], define v≔eξ1+eξv e^ξ1+e^ξ so that ξ=φ⁡(v)ξ= (v). Applying the first identity above with the pair (a,v)(a,v) and anchor u=vu=v gives v(a,v) D_v(a,v) =∫αξIGC(η,ξ)η. = _α^ξ Q_ @scalerel@objIGC (η,ξ)\,dη. Substituting this identity into the preceding expression yields Γ prod (a,b) _ @scalerel@objprod(a,b) =∫αβeξ1+eξ(a,eξ1+eξ)ξ=∫abv(a,v)v⁡(1−v)v, = _α^β D_ e^ξ1+e^ξ (a, e^ξ1+e^ξ )\,dξ\;=\; _a^b D_v(a,v)v(1-v)\,dv, where the final equality follows from the change of variables ξ=φ⁡(v)ξ= (v), for which dξ=dv/v⁡(1−v)dξ=dv/v(1-v). This proves the claim (29b). 6 Discussion In this paper, we have put forth the interaction growth complexity (IGC) as an information-geometric quantity for measuring the structure of product-reference diffusion (PRD) paths for discrete sampling. It provides quantitative bounds on the iteration complexity of various PRD samplers, both those using constant stepsizes and those with optimized stepsizes according to a square-root criterion. Sampling complexity is not determined solely by the amount of dependence in the target distribution, but also by where and how rapidly this dependence is removed by the noising process. Our IGC theory formalizes this idea through a second derivative of mutual information along the diffusion path. Moreover, we provide a class of statistical estimators for IGC increments, as well as for the KL error itself, based on a Bregman divergence that emerges from our theory. Thus, the IGC measure provides a unified pathwise description of local factorization error, finite-step KL discretization, optimal scheduling, and classical multivariate dependence. Our perspective makes it possible to compare different mechanisms for destroying information. The IGC theory allows the terminal reference to be an arbitrary product distribution. Each reference induces a different IGC complexity, thereby yielding a principled way of studying how the choice of reference affects sampling complexity. We gave some preliminary results in this direction in Section 3.2.3, and we suspect that a more systematic investigation could be fruitful. More broadly, our earlier work [37] showed that masking diffusion can be characterized by a related information-geometric functional known as the UGC measure. Together with the IGC representation developed here, these results provide a principled basis for comparing masking and noising diffusions on a given target distribution, and for understanding when one mechanism may be preferable to the other. Acknowledgements This work was partially supported by a Guggenheim Fellowship, an NSF grant (DMS-2311072), and the Ford Professorship at MIT. We thank Yuting Wei for her inspiring talk during the MIT Statistics and Data Science conference in spring 2026. References [1] J. Austin, D. D. Johnson, J. Ho, D. Tarlow, and R. van den Berg (2021) Structured denoising diffusion models in discrete state-spaces. In Advances in Neural Information Processing Systems, Vol. 34, p. 17981–17993. Cited by: §1.1, §1.2, §1.2, §1.2, §1, §2.1, §3.2.3. [2] J. Benton, Y. Shi, V. De Bortoli, G. Deligiannidis, and A. Doucet (2024) From denoising diffusions to denoising markov models. Journal of the Royal Statistical Society Series B: Statistical Methodology 86 (2), p. 286–301. External Links: Document Cited by: §1.2, §1. [3] S. Brooks, A. Gelman, G. L. Jones, and X. L. Meng (2011) Handbook of Markov chain Monte Carlo. CRC Press. Cited by: §1. [4] A. Campbell, J. Benton, V. De Bortoli, T. Rainforth, G. Deligiannidis, and A. Doucet (2022) A continuous time framework for discrete denoising models. In Advances in Neural Information Processing Systems, Vol. 35, p. 28266–28279. Cited by: §1.2, §1.2, §1. [5] H. Chen, H. Lee, and J. Lu (2023) Improved Analysis of Score-based Generative Modeling: User-Friendly Bounds under Minimal Smoothness Assumptions. In International Conference on Machine Learning, External Links: 2211.01916 Cited by: §1. [6] M. Chen, S. Mei, J. Fan, and M. Wang (2024) An overview of diffusion models: applications, guided generation, statistical rates and optimization. arXiv preprint arXiv:2404.07771. External Links: Link Cited by: §1. [7] S. Chen, S. Chewi, J. Li, Y. Li, A. Salim, and A. R. Zhang (2023) Sampling is as easy as learning the score: theory for diffusion models with minimal data assumptions. In International Conference on Learning Representations, External Links: 2209.11215 Cited by: §1. [8] S. Chen, K. Cong, and J. Li (2026) Optimal inference schedules for masked diffusion models. In Proceedings of Thirty Ninth Conference on Learning Theory, Proceedings of Machine Learning Research, Vol. 336, p. 1279–1311. Cited by: §1.2, §1.2. [9] G. Conforti, A. Durmus, and L. Pham (2025) Non-asymptotic convergence of discrete diffusion models: masked and random walk dynamics. External Links: 2512.00580 Cited by: §1.2. [10] D. Dmitriev, Z. Huang, and Y. Wei (2026) Efficient sampling with discrete diffusion models: sharp and adaptive guarantees. In Proceedings of Thirty Ninth Conference on Learning Theory, Proceedings of Machine Learning Research, Vol. 336, p. 2038–2104. Cited by: §1.2, §1.2, §3.2.2, §3.2.2. [11] D. Dmitriev, Z. Huang, and Y. Wei (2026) Provably adaptive sampling with uniform and remasking discrete diffusion models. External Links: 2608.23554 Cited by: §1. [12] R. S. Ellis and C. M. Newman (1978) Limit theorems for sums of dependent random variables occurring in statistical mechanics. Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete 44 (2), p. 117–139. External Links: Document Cited by: §2.3.2. [13] R. S. Ellis (1985) Entropy, large deviations, and statistical mechanics. Grundlehren der mathematischen Wissenschaften, Vol. 271, Springer. External Links: Document Cited by: §2.3.2. [14] A. Gelman, J. Carlin, H. S. Stern, D. B. Dunson, A. Vehtari, and D. K. Salomon (2013) Bayesian data analysis. CRC Press. Cited by: §1. [15] S. Gourevitch, Y. Janati, D. Shariatian, U. Simsekli, E. Moulines, E. P. Xing, and A. Durmus (2026) Uniform diffusion models revisited: leave-one-out denoiser and absorbing state reformulation. External Links: 2605.22765 Cited by: §1.2. [16] T. S. Han (1978) Nonnegative entropy measures of multivariate symmetric correlations. Information and Control 36 (2), p. 133–156. External Links: Document Cited by: §1.1, §1.2, 1st item. [17] J. Ho, A. Jain, and P. Abbeel (2020) Denoising diffusion probabilistic models. Advances in Neural Information Processing Systems (NeurIPS) 33, p. 6840–6851. Cited by: §1. [18] E. Hoogeboom, D. Nielsen, P. Jaini, P. Forré, and M. Welling (2021) Argmax flows and multinomial diffusion: learning categorical distributions. In Advances in Neural Information Processing Systems, Vol. 34. Cited by: §1.1, §1.2, §1, §2.1. [19] N. Laabid, S. Rissanen, M. Heinonen, A. Solin, and V. Garg (2025) Equivariant denoisers cannot copy graphs: align your graph diffusion models. In International Conference on Learning Representations, Cited by: §1.2, §3.2.3. [20] Y. Liang, R. Huang, L. Lai, N. Shroff, and Y. Liang (2025) Absorb and converge: provable convergence guarantee for absorbing discrete diffusion models. In Advances in Neural Information Processing Systems, Vol. 38. Cited by: §1.2. [21] Y. Liang, Y. Liang, L. Lai, and N. Shroff (2025) Discrete diffusion models: novel analysis and new sampler guarantees. In Advances in Neural Information Processing Systems, Vol. 38, p. 183461–183498. External Links: Document Cited by: §1.2. [22] A. Lou, C. Meng, and S. Ermon (2024) Discrete diffusion modeling by estimating the ratios of the data distribution. In Proceedings of the 41st International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 235, p. 32819–32848. Cited by: §1.2, §1.2, §1, §2.1. [23] C. Meng, K. Choi, J. Song, and S. Ermon (2022) Concrete score matching: generalized score matching for discrete data. In Advances in Neural Information Processing Systems, Vol. 35, p. 34532–34545. Cited by: §1.2. [24] J. Ou, S. Nie, K. Xue, F. Zhu, J. Sun, Z. Li, and C. Li (2025) Your absorbing discrete diffusion secretly models the conditional distributions of clean data. In International Conference on Learning Representations, Cited by: §1.2. [25] L. Pham, D. Shariatian, A. Ocello, G. Conforti, and A. Oliviero Durmus (2025) Discrete markov probabilistic models: an improved discrete score-based framework with sharp convergence bounds under minimal assumptions. In Proceedings of the 42nd International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 267, p. 49195–49258. Cited by: §1.2. [26] Y. Ren, H. Chen, G. M. Rotskoff, and L. Ying (2025) How discrete and continuous diffusion meet: comprehensive analysis of discrete diffusion models via a stochastic integral framework. In International Conference on Learning Representations, Cited by: §1.2. [27] C. P. Robert and G. Casella (2004) Monte carlo statistical methods. 2 edition, Springer Texts in Statistics, Springer, New York. External Links: Document, ISBN 978-0-387-21239-5 Cited by: §1. [28] R. Y. Rubinstein and D. P. Kroese (2008) Simulation and the monte carlo method. 2nd edition, John Wiley and Sons, Hoboken, NJ. Cited by: §1. [29] S. Sahoo, M. Arriola, A. Gokaslan, Y. Schiff, E. Marroquin, J. Chiu, A. Rush, and V. Kuleshov (2024) Simple and effective masked diffusion language models. In Advances in Neural Information Processing Systems, Vol. 37, p. 130136–130184. Cited by: §1.2, §1. [30] Y. Schiff, S. S. Sahoo, H. Phung, G. Wang, S. Boshar, H. Dalla-Torre, B. P. de Almeida, A. Rush, T. Pierrot, and V. Kuleshov (2025) Simple guidance mechanisms for discrete diffusion models. In International Conference on Learning Representations, Cited by: §1.2, §3.2.3. [31] J. Shi, K. Han, Z. Wang, A. Doucet, and M. K. Titsias (2024) Simplified and generalized masked diffusion for discrete data. In Advances in Neural Information Processing Systems, Vol. 37, p. 103131–103167. External Links: Document Cited by: §1.2, §1. [32] J. Sohl-Dickstein, E. Weiss, N. Maheswaranathan, and S. Ganguli (2015) Deep unsupervised learning using nonequilibrium thermodynamics. In Proceedings of the 32nd International Conference on Machine Learning, Proceedings of Machine Learning Research, Vol. 37, p. 2256–2265. Cited by: §1.2, §1. [33] Y. Song and S. Ermon (2019) Generative modeling by estimating gradients of the data distribution. In Advances in Neural Information Processing Systems (NeurIPS), p. 11895–11907. Cited by: §1. [34] Y. Song, J. Sohl-Dickstein, D. P. Kingma, A. Kumar, S. Ermon, and B. Poole (2021) Score-based generative modeling through stochastic differential equations. In International Conference on Learning Representations, Cited by: §1. [35] C. Vignac, I. Krawczuk, A. Siraudin, B. Wang, V. Cevher, and P. Frossard (2023) DiGress: discrete denoising diffusion for graph generation. In International Conference on Learning Representations, Cited by: §1.2, §2.1, §3.2.3. [36] M. J. Wainwright (2026) Denoising growth complexity: data geometry and certified schedules for diffusion sampling. External Links: 2607.26285 Cited by: §1.1, §1.1, §1.2, §3.3, §4.2, §4. [37] M. J. Wainwright (2026) The data geometry of masking diffusion: certified-optimal schedules via unmasking growth complexity. External Links: 2608.13520 Cited by: §1.1, §1.1, §1.2, §2.3.1, §2.3.3, §3.3, §4.1, §4.2, §4.3, §4.4, §4, §6. [38] S. Watanabe (1960) Information theoretical analysis of multivariate correlation. IBM Journal of Research and Development 4 (1), p. 66–82. External Links: Document Cited by: §1.1, §1.2, 1st item. [39] Z. Zhang, Z. Chen, and Q. Gu (2025) Convergence of score-based discrete diffusion models: a discrete-time analysis. In International Conference on Learning Representations, Cited by: §1.2. Appendix A Parameterization in terms of the LOO posterior The ordinary and leave-one-out posteriors are related by Bayes’ rule: μi,a(w,x) _i,a(w,x) =i,a(xi∣w)μa,i LOO (w,x−i)∑u∈i,a(xi∣u)μa,i LOO (u,x−i). = V_i,a(x_i w)μ @scalerel@objLOO_a,i(w,x_-i) _u V_i,a(x_i u)μ @scalerel@objLOO_a,i(u,x_-i). (47a) Substituting (47a) into (8a) gives the equivalent leave-one-out representation ℙia→b(y∣x) _i^a→ b(y x) =i,a/b(xi∣y)∑w∈i,b(y∣w)μa,i LOO (w,x−i)∑w∈i,a(xi∣w)μa,i LOO (w,x−i). = V_i,a/b(x_i y) _w V_i,b(y w)μ @scalerel@objLOO_a,i(w,x_-i) _w V_i,a(x_i w)μ @scalerel@objLOO_a,i(w,x_-i). (47b) Appendix B Proof of Proposition 1 It only remains to prove representations (22c) of the total correlation and dual total correlation in terms of the bivariate IGC density (20b). Define the functions T⁡(ξ)≔⁡(Xr⁡(ξ))T(ξ) TC(X_r(ξ)) and D⁡(η)≔⁡(Xr⁡(η))D(η) DTC(X_r(η)). By the definition of mutual information, we have Ci(ξ,η)=Ent⁡(Xr⁡(ξ),i)+Ent⁡(Xr⁡(η),−i)−Ent⁡(Xr⁡(ξ),i,Xr⁡(η),−i)C_i(ξ,η)=Ent(X_r(ξ),i)+Ent(X_r(η),-i)-Ent (X_r(ξ),i,X_r(η),-i ), and consequently ∂1Ci(ξ,η)=dξEnt⁡(Xr⁡(ξ),i)−∂λiEnt⁡(X⁡())|=ξi+η⁡(−i). _1C_i(ξ,η)= ddξEnt(X_r(ξ),i)- . _ _iEnt(X_r( λ)) |_ λ= _i+η(1-e_i). Moreover, note that we have dξEnt⁡(Xr⁡(ξ))=∑i=1d∂λiEnt⁡(X⁡())|=ξ ddξEnt(X_r(ξ))\;=\; _i=1^d . _ _iEnt(X_r( λ)) |_ λ= 1. Thus, by differentiating the definition of total correlation, we obtain T′(ξ) T (ξ) =dξ∑i=1dEnt⁡(Xr⁡(ξ),i)−Ent⁡(Xr⁡(ξ))=∑i=1d∂1Ci(ξ,ξ). = ddξ \ _i=1^dEnt(X_r(ξ),i)-Ent(X_r(ξ)) \\;=\; _i=1^d _1C_i(ξ,ξ). (48a) Similarly, we have ∂2Ci(ξ,η)=dηEnt⁡(Xr⁡(η),−i)−∑j≠i∂λjEnt⁡(X⁡())|=ξi+η⁡(−i) _2C_i(ξ,η)= ddηEnt(X_r(η),-i)- _j≠ i . _ _jEnt(X_r( λ)) |_ λ= _i+η(1-e_i), as well as the identity ∑i=1d∑j≠i∂λjEnt⁡(X⁡())|=η=(d−1)dηEnt⁡(Xr⁡(η)) _i=1^d _j≠ i . _ _jEnt(X_r( λ)) |_ λ= 1=(d-1) ddηEnt(X_r(η)). Thus, differentiating the formula for dual total correlation yields D′(η) D (η) =dη∑i=1dEnt⁡(Xr⁡(η),−i)−(d−1)Ent⁡(Xr⁡(η))=∑i=1d∂2Ci(η,η). = ddη \ _i=1^dEnt(X_r(η),-i)-(d-1)Ent(X_r(η)) \\;=\; _i=1^d _2C_i(η,η). (48b) Combining these identities with the boundary relations Ci(ξ,−∞)=Ci(−∞,η)=0C_i(ξ,-∞)=C_i(-∞,η)=0 yields the identities T′(ξ) T (ξ) =∑i=1d∫−∞ξ∂1∂2Ci(ξ,η)dη=∫−∞ξIGC(η,ξ)dη,as well as = _i=1^d _-∞^ξ _1 _2C_i(ξ,η)\,dη\;=\; _-∞^ξ Q_ @scalerel@objIGC (η,ξ)\,dη, as well as D′(η) D (η) =∑i=1d∫−∞η∂1∂2Ci(ξ,η)ξ=∫−∞ηIGC(η,ξ)ξ. = _i=1^d _-∞^η _1 _2C_i(ξ,η)\,dξ\;=\; _-∞^η Q_ @scalerel@objIGC (η,ξ)\,dξ. Since T⁡(−∞)=D⁡(−∞)=0T(-∞)=D(-∞)=0, T⁡(∞)=⁡(Z)T(∞)= TC(Z), and D⁡(∞)=⁡(Z)D(∞)= DTC(Z), the two claims (22c) follow from the fundamental theorem of calculus.

Instant research discovery