Adaptation to Intrinsic Dependence in Diffusion Language Models Yunxiao Zhao, Changxiao Cai Abstract Diffusion language models (DLMs) have recently emerged as a promising alternative to autoregressive (AR) approaches, enabling parallel token generation beyond a rigid left-to-right order. Despite growing empirical success, the theoretical understanding of how unmasking schedules—which specify the order and size of unmasked tokens during sampling—affect generation quality remains limited. In this work, we introduce a distribution-agnostic unmasking schedule for DLMs that adapts to the (unknown) dependence structure of the target data distribution, without requiring any prior knowledge or hyperparameter tuning. In contrast to prior deterministic procedures that fix unmasking sizes, our method randomizes the number of tokens revealed at each iteration. We show that, for two specific parameter choices, the sampling convergence guarantees—measured by Kullback-Leibler (KL) divergence—scale as O ~ ​ ( 𝖳𝖢 / K ) \widetilde{O}(\mathsf{TC}/K) and O ~ ​ ( 𝖣𝖳𝖢 / K ) \widetilde{O}(\mathsf{DTC}/K) respectively. Here, K K is the number of iterations, and 𝖳𝖢 \mathsf{TC} and 𝖣𝖳𝖢 \mathsf{DTC} are the total correlation and dual total correlation of the target distribution, capturing the intrinsic dependence structure underlying the data. Importantly, our guarantees hold in the practically relevant parallel-sampling regime K < L K0 , we write f(n)\lesssim g(n) or f(n)=O\big(g(n)\big) if there exists some absolute constant C>0 such that f(n)\leq Cg(n) . Similarly, f(n)\gtrsim g(n) or f(n)=\Omega\big(g(n)\big) means f(n)\geq C^{\prime}g(n) for some absolute constant C^{\prime}>0 . We write f(n)\asymp g(n) or f(n)=\Theta\big(g(n)\big) if Cg(n)\leq f(n)\leq C^{\prime}g(n) for some absolute constants C^{\prime}>C>0 . Additionally \widetilde{O} , \widetilde{\Omega} , and \widetilde{\Theta} are used to denote the corresponding asymptotic notation with logarithmic factors. 2 Preliminaries In this section, we review the basics of MDMs and DLMs. Forward (masking) process. Let X^{(0)}=(X_{1}^{(0)},X_{2}^{(0)},\dots,X_{L}^{(0)})\in\mathbb{X}^{L} be a token sequence drawn from the data distribution p_{\mathsf{data}} . The forward process corrupts X^{(0)} over K steps by progressively replacing tokens with the mask symbol \mathsf{M} until all indices are masked. Specifically, let T=(T^{(1)},T^{(2)},\ldots,T^{(K)}) be a partition of the index set [L] , i.e., T^{(i)}\cap T^{(j)}=\varnothing for i\neq j and \cup_{k=1}^{K}T^{(k)}=[L] . For each k\in[K] , T^{(k)}\subseteq[L] represents the set of token positions newly masked at iteration k , and we define M^{(k)}\coloneqq\cup_{j=1}^{k}T^{(j)} the cumulative set of masked positions up to iteration k . Let X^{(k)} denote the partially masked sequence after k masking steps. Specifically, we update the sequence X^{(k)} from X^{(k-1)} by masking the tokens at positions in set T^{(k)} : \displaystyle X^{(k)}_{i}=\begin{cases}\mathsf{M},&\text{if }i\in T^{(k)},\\ X^{(k-1)}_{i},&\text{if }i\notin T^{(k)}.\end{cases} Equivalently, tokens of the original sequence X^{(0)} at positions in M^{(k)} are masked in X^{(k)} , i.e., X^{(k)}=\mathcal{P}_{[L]\setminus M^{(k)}}(X^{(0)}). After K steps, the sequence is fully masked, i.e., X^{(K)}=(\mathsf{M},\mathsf{M},\ldots,\mathsf{M})\in\overline{\mathbb{X}}^{L} . Mask predictor training. DLMs generate text by learning to reverse the above forward process, thereby transforming a fully masked sequence into a new sample from p_{\mathsf{data}} . This time-reversal is realized by a mask predictor, which aims to learn the conditional distribution of masked tokens given the unmasked ones at each step of the forward process. As discussed in Section 1 , directly modeling the joint conditional distribution of multiple masked tokens can be intractable in high dimensions. Therefore, DLMs adopt a factorized approximation. Concretely, for i\in[L] , we denote the true conditional marginal of X_{i}^{(0)} given an arbitrary set S of unmasked tokens (under the data distribution p_{\mathsf{data}} ) as \displaystyle p^{\star}_{i}(x\mid z_{S})\coloneqq\mathbb{P}\big\{X^{(0)}_{i}=x\mid X^{(0)}_{S}=z_{S}\big\} (2) for any S\subseteq[L]\setminus\{i\} , z_{S}\in\mathbb{X}^{|S|} , and x\in\mathbb{X} . The goal is to build an estimator \widehat{p}_{i}(\cdot\mid\cdot) for each conditional marginal p^{\star}_{i}(\cdot\mid\cdot) and construct a mask predictor \widehat{p}=\prod_{i=1}^{L}\widehat{p}_{i} . The mask predictor \widehat{p} is trained via maximizing the log-likelihood of the masked tokens given observed tokens (or equivalently, minimize the KL divergence between the data and sampled distributions): \displaystyle\max_{p=\prod_{i=1}^{L}p_{i}}\mathbb{E}_{X^{(0)},S,\tau}\Bigg[\frac{L}{|M^{(\tau)}|}\sum_{i\in M^{(\tau)}}\log p_{i}\big(X^{(0)}_{i}\mid X^{(\tau)}\big)\Bigg]. (3) Here, X^{(0)} is a training sample drawn from p_{\mathsf{data}} , S=(S^{(1)},\dots,S^{(K)}) is a sequence of unmasking sets forming a partition of [L] , \tau is an iteration index, M^{(\tau)}=\cup_{k=\tau}^{K}S^{(k)} is the set of masked tokens at step \tau , and X^{(\tau)}=\mathcal{P}_{[L]\setminus M^{(\tau)}}(X^{(0)}) is the corresponding partially masked sequence. The expectation is over X^{(0)}\sim p_{\mathsf{data}} , the random unmasking sets S drawn from a certain schedule, and the random time \tau\in[K] sampled according to \mathbb{P}\{\tau=k\mid S\}=|S^{(k)}|/L . Equivalently, each unmasking set S^{(k)} corresponds to the masking set T^{(K-k+1)} in the forward process, and the objective is to predict conditional marginals of masked tokens at various intermediate masking levels. In practice, this objective is approximated by averaging over finite training samples. As a note, one can verify that the product of the true conditional marginals \prod_{i=1}^{L}p^{\star}_{i} defined in ( 2 ) is the optimal solution to the above minimization problem ( 3 ). Reverse (unmasking) process. After a mask predictor \widehat{p} is trained, a K -step DLM sampling procedure generates a token sequence of length L by iteratively unmasking a masked sequence as follows. Beginning at step 0 , we initialize the sequence Y^{(0)}=(\mathsf{M},\mathsf{M},\ldots,\mathsf{M})\in\overline{\mathbb{X}}^{L} and the cumulative unmasking set U^{(0)}=\varnothing . Then, for each iteration k=1,2,\ldots,K , we repeat the following two steps: 1. Unmasking set selection. We first select a subset S^{(k)} from the currently masked positions [L]\setminus U^{(k-1)} according to some policy \pi^{(k)} , which defines a distribution over all the subsets of [L]\setminus U^{(k-1)} . 2. Token sampling. Next, given the previous iterate Y^{(k-1)} , we sample the tokens from set S^{(k)} independently and simultaneously , using the learned mask predictor \widehat{p}=\prod_{i=1}^{L}\widehat{p}_{i} : \displaystyle\widehat{Y}_{i}\sim\widehat{p}_{i}\big(\cdot\mid Y^{(k-1)}\big),\quad\forall\,i\in S^{(k)}. (4) We then update the sequence Y^{(k)} by filling in the newly sampled tokens: \displaystyle Y^{(k)}_{i}=\begin{cases}\widehat{Y}_{i},&\text{if }i\in S^{(k)},\\ Y^{(k-1)}_{i},&\text{if }i\notin S^{(k)},\end{cases} (5) and update the cumulative unmasking set U^{(k)}=U^{(k-1)}\cup S^{(k)} . The final iterate Y_{\mathsf{out}}\coloneqq Y^{(K)} is outputted as the generated sample. It is worth noting that given a pre-trained mask predictor \widehat{p} and a fixed sequence of unmasking sets S=(S^{(1)},S^{(2)},\ldots,S^{(K)}) the distribution of the output sample Y_{\mathsf{out}} is uniquely determined. Therefore, we may write Y_{\mathsf{out}}=Y_{\mathsf{out}}^{S} to emphasize the dependence of the generated sample on a specific sequence of unmasking sets S . More generally, since the unmasking set sequence S is selected according to the unmasking scheme \pi=(\pi^{(1)},\pi^{(2)},\ldots,\pi^{(K)}) , the distribution of the generated sample Y_{\mathsf{out}} is fully characterized by \pi (along with \widehat{p} ) through the induced distribution over S . Information-theoretic measures. Finally, we review several information-theoretic measures that will be used in this paper. Let X=(X_{1},X_{2},\dots,X_{L})\in\mathbb{X}^{L} be a random sequence with joint distribution p_{X} . For any sets S,T\in[L] , we use H(X_{S}) to denote the entropy of the random sequence X_{S}=(X_{i})_{i\in S} , and define the conditional entropy of X_{S} given X_{T} as \displaystyle H(X_{S}\mid X_{T}) \displaystyle\coloneqq\mathbb{E}_{z\sim p_{X_{T}}}[H(X_{S}\mid X_{T}=z)]. (6) The total correlation (TC) of X_{S} is defined as: \displaystyle\mathsf{TC}(X_{S})\coloneqq\sum_{i\in S}H(X_{i})-H(X_{S}). (7) Intuitively, TC measures the global dependence among the variables in X_{S} by quantifying the distance between the joint distribution p_{X_{S}} and the fully factorized distribution \prod_{i\in S}p_{X_{i}} . The conditional total correlation of X_{S} given X_{T} is given by \displaystyle\mathsf{TC}(X_{S}\mid X_{T})\coloneqq\sum_{i\in S}H(X_{i}\mid X_{T})-H(X_{S}\mid X_{T}). (8) The dual total correlation (DTC) of X_{S} is defined as: \displaystyle\mathsf{DTC}(X_{S})\coloneqq H(X_{S})-\sum_{i\in S}H\big(X_{i}\mid X_{S\setminus\{i\}}\big). (9) DTC has been shown to characterize how well the distribution can be approximated by a sparse mixture of product distributions ( 2 ; 10 ) . Moreover, when each X_{i} is determined by the rest, all the conditional entropies are zero, and the DTC equals the entropy, i.e., \mathsf{DTC}(X_{S})=H(X_{S}) . The conditional dual total correlation of X_{S} given X_{T} is defined as \displaystyle\mathsf{DTC}(X_{S}\mid X_{T})=H(X_{S}\mid X_{T})-\sum_{i\in S}H\big(X_{i}\mid X_{(S\setminus\{i\})\cup T}\big). (10) Finally, we use H(X) and H(p_{X}) interchangeably to denote the entropy of X , and likewise for other information-theoretic quantities. 3 Main results In this section, we present our proposed unmasking scheme along with its theoretical guarantee on the sampling error measured by KL divergence. 3.1 Unmasking scheme We propose a distribution-agnostic randomized unmasking procedure, denoted by \pi=\pi(K,[L]) , that unmasks a length- L sequence over K iterations. For clarity, we describe the scheme in a slightly more general form \pi(K,\mathcal{I}) , where \mathcal{I}\subseteq[L] represents the set of indices that need to be unmasked. At a high level, \pi(K,\mathcal{I}) operates recursively. In the first iteration t=1 , it samples an unmasking set S^{(1)}\subseteq\mathcal{I} . It then applies the same procedure \pi(K-1,\mathcal{I}\setminus S^{(1)}) to the remaining masked positions \mathcal{I}\setminus S^{(1)} for the next K-1 iterations, and generates the unmasking sets S^{(2)},\ldots,S^{(K)} sequentially. The key design choice is how to sample the first unmasking set S^{(1)} from \mathcal{I} . We do this in two stages: • Sample a batch size. We first draw \ell=|S^{(1)}| by assigning weights w_{\ell}(K,|\mathcal{I}|) for \ell\geq 1 . • Sample a subset of that size. Conditioned on \ell , we choose S^{(1)} uniformly at random among all \ell -subsets of \mathcal{I} . The batch-size distribution is governed by a scalar coefficient f(K,L^{\prime}) (defined for K\geq 1 and L^{\prime}\geq K ), which will later appear as the leading factor in our KL sampling error bounds for the unmasking schedule \pi . Importantly, for fixed (K,|\mathcal{I}|) , the weights \{w_{\ell}(K,|\mathcal{I}|)\}_{\ell\geq 1} depend only on coefficients f(K-1,\cdot) from the previous recursion level K-1 . As a result, the entire schedule can be computed inductively starting from the base case K=1 . General framework. We now formalize the general construction of the unmasking scheme \pi(K,\mathcal{I}) in detail. This construction provides a template for a family of randomized unmasking schemes, parameterized by the coefficient f(K,L^{\prime}) and the associated batch-size weights \{w_{\ell}(K,|\mathcal{I}|)\}_{\ell\geq 1} . We will later specify these quantities in two concrete ways, leading to a TC-adaptive scheme \pi_{\mathsf{tc}} and a DTC-adaptive scheme \pi_{\mathsf{dtc}} . Base case ( K=1 ). For any index set \mathcal{I} with |\mathcal{I}|\geq 1 , the scheme \pi(1,\mathcal{I}) simply unmasks all tokens in \mathcal{I} in a single iteration, i.e., \mathbb{P}\{S^{(1)}=\mathcal{I}\}=1 . In addition, we initialize the coefficient f(1,L^{\prime}) for all 1\leq L^{\prime}\leq L . Recursion ( K\geq 2 ). Assume that the scheme \pi(K-1,\mathcal{J}) has been defined for any index set \mathcal{J} with K-1\leq|\mathcal{J}|\leq L , and that the coefficient f(K-1,L^{\prime}) has been defined for all K-1\leq L^{\prime}\leq L . We now construct \pi(K,\mathcal{I}) for any index set \mathcal{I} with K\leq|\mathcal{I}|\leq L . For notational convenience, we denote by L^{\prime}:=|\mathcal{I}| the size of set \mathcal{I} to be unmasked. • Step 1: sample the first unmasking set S^{(1)} . Since we must leave at least K-1 positions masked for the remaining K-1 iterations, the first batch size must satisfy |S^{(1)}|\in\{1,2,\ldots,L^{\prime}-K+1\} . We assign each possible size \ell a nonnegative weight \displaystyle w_{\ell}(K,L^{\prime}),\quad\forall\,\ell=1,2,\ldots,L^{\prime}-K+1, (11) which is determined by the coefficient f(K-1,\cdot) at level K-1 , and define the normalizing constant \displaystyle\Psi(K,L^{\prime})\coloneqq\sum_{\ell=1}^{L^{\prime}-K+1}w_{\ell}(K,L^{\prime}). (12) Using these weights, we draw the size of the first unmasking set |S^{(1)}| according to \displaystyle\mathbb{P}\{|S^{(1)}|=\ell\}=\frac{w_{\ell}(K,L^{\prime})}{\Psi(K,L^{\prime})},\quad\forall\,\ell=1,2,\ldots,L^{\prime}-K+1. Conditioned on |S^{(1)}|=\ell , we then sample S^{(1)} uniformly at random among all subsets of \mathcal{I} with size \ell . Finally, we compute the level- K coefficient f(K,\cdot) based on the previously defined f(K-1,\cdot) and the normalizing constant \Psi(K,\cdot) at level K . • Step 2: recurse on the remaining indices. Having sampled the first set S^{(1)} , we apply the same procedure to the remaining masked set \mathcal{I}\setminus S^{(1)} for the next K-1 iterations. Concretely, for k=2,3,\ldots,K , we set \displaystyle\pi^{(k)}(K,\mathcal{I})=\pi^{(k-1)}(K-1,\mathcal{I}\setminus S^{(1)}). (13) Remark 1 . The unmasking scheme \pi(K,\mathcal{I}) is completely specified by the number of iterations K and index set \mathcal{I} . In particular, it does not require prior knowledge of the data distribution p_{\mathsf{data}} , estimation of information-theoretic quantities such as TC and DTC, or hyperparameter tuning. Unlike procedures that fix the unmasking sizes |S^{(1)}|,\dots,|S^{(K)}| in advance ( 29 ; 10 ) , our scheme randomizes the unmasking size at each iteration. As we show in the analysis, this randomization is crucial for adapting to the unknown dependence structure of p_{\mathsf{data}} while remaining distribution-agnostic. (a) (b) Figure 1: Empirical mean unmasking size vs. iteration index k : (a) TC-adaptive scheme \pi_{\mathsf{tc}} ; (b) DTC-adaptive scheme \pi_{\mathsf{dtc}} . The total number of iterations is K=1000 and the sequence length is L=2000 . TC/DTC-adaptive schemes. With this general construction in place, we now present two concrete unmasking schemes by specifying the coefficients f(K,L^{\prime}) and batch-size weights \{w_{\ell}(K,L^{\prime})\}_{\ell\geq 1} , which yield sampling convergence guarantees in terms of TC and DTC, respectively. • TC-adaptive scheme. We first introduce the TC-adaptive unmasking scheme, denoted by \pi_{\mathsf{tc}}(K,\mathcal{I}) . For K=1 , we initialize the coefficient f_{\mathsf{tc}}(1,L^{\prime}) by setting \displaystyle f_{\mathsf{tc}}(1,1)\coloneqq 0,\qquad\text{and}\qquad f_{\mathsf{tc}}(1,L^{\prime})\coloneqq 1,\quad\forall\,2\leq L^{\prime}\leq L. (14) For K\geq 2 and L^{\prime}\geq K , we define the batch-size weights by \displaystyle w_{1}^{\mathsf{tc}}(K,L^{\prime}) \displaystyle\coloneqq 1, (15a) \displaystyle w_{\ell}^{\mathsf{tc}}(K,L^{\prime}) \displaystyle\coloneqq\prod_{i=1}^{\ell-1}\frac{(L^{\prime}-i)f_{\mathsf{tc}}(K-1,L^{\prime}-i)}{1+(L^{\prime}-i-2)f_{\mathsf{tc}}(K-1,L^{\prime}-i-1)},\quad\forall\,\ell=2,\ldots,L^{\prime}-K+1, (15b) with the normalizing constant \displaystyle\Psi_{\mathsf{tc}}(K,L^{\prime})\coloneqq\sum_{\ell=1}^{L^{\prime}-K+1}w_{\ell}^{\mathsf{tc}}(K,L^{\prime}). (16) Finally, we update the coefficient f_{\mathsf{tc}}(K,L^{\prime}) according to \displaystyle f_{\mathsf{tc}}(K,L^{\prime})\coloneqq 1-\frac{1+(L^{\prime}-2)f_{\mathsf{tc}}(K-1,L^{\prime}-1)}{\Psi_{\mathsf{tc}}(K,L^{\prime})}. (17) • DTC-adaptive scheme. For the DTC-adaptive scheme, denoted by \pi_{\mathsf{dtc}}(K,\mathcal{I}) , we initialize the coefficient f_{\mathsf{dtc}}(1,L^{\prime}) as \displaystyle f_{\mathsf{dtc}}(1,L^{\prime})\coloneqq\frac{L^{\prime}-1}{L-L^{\prime}+1},\quad\forall\,1\leq L^{\prime}\leq L. (18) For K\geq 2 and L^{\prime}\geq K , the batch-size weights are chosen as \displaystyle w_{1}^{\mathsf{dtc}}(K,L^{\prime}) \displaystyle\coloneqq 1, (19a) \displaystyle w_{\ell}^{\mathsf{dtc}}(K,L^{\prime}) \displaystyle\coloneqq\prod_{i=1}^{\ell-1}\frac{(L-L^{\prime}+i)\,f_{\mathsf{dtc}}(K-1,L^{\prime}-i)}{1+(L-L^{\prime}+i+2)\,f_{\mathsf{dtc}}(K-1,L^{\prime}-i-1)},\quad\forall\,\ell=2,\ldots,L^{\prime}-K+1, (19b) with the normalizing constant \displaystyle\Psi_{\mathsf{dtc}}(K,L^{\prime})\coloneqq\sum_{\ell=1}^{L^{\prime}-K+1}w_{\ell}^{\mathsf{dtc}}(K,L^{\prime}). (20) The coefficient f_{\mathsf{dtc}}(K,L^{\prime}) is then updated according to \displaystyle f_{\mathsf{dtc}}(K,L^{\prime})\coloneqq-1+\frac{1+(L-L^{\prime}+2)\,f_{\mathsf{dtc}}(K-1,L^{\prime}-1)}{\Psi_{\mathsf{dtc}}(K,L^{\prime})}. (21) To build some intuition for these two constructed schemes, we plot the empirical mean unmasking size \mathbb{E}[|S^{(k)}|] at each iteration k in Figure 1 . As can be seen, the TC-adaptive scheme \pi_{\mathsf{tc}} unmasks more tokens in early iterations and progressively fewer later on. In contrast, the DTC-adaptive scheme \pi_{\mathsf{dtc}} starts with smaller unmasking sizes and gradually increases the batch size as sampling proceeds. Intuitively, \pi_{\mathsf{tc}} front-loads unmasking because TC primarily penalizes within-batch dependence, while \pi_{\mathsf{dtc}} back-loads unmasking because low-DTC often reflects a smaller number of degrees of freedom that, once revealed, reduce the conditional dependence of the remaining tokens and allow larger parallel updates in later iterations. Finally, we briefly discuss the computational cost of sampling unmasking sets from the proposed scheme. After a one-time O(KL) dynamic-programming precomputation of f(K,L^{\prime}) for K\leq L^{\prime}\leq L , the batch size |S^{(k)}| can be drawn in O(1+|S^{(k)}|) time per iteration via inverse-transform sampling, and the corresponding set can be sampled uniformly in overall O(L) time (e.g., via reservoir sampling). Consequently, generating all unmasking sets costs O(K+L) time after precomputation, and thus our strategy introduces essentially no additional overhead. 3.2 Theoretical guarantee We proceed to present the sampling guarantees of the proposed unmasking schemes \pi_{\mathsf{tc}} and \pi_{\mathsf{dtc}} , stated in terms of the KL divergence between the data distribution p_{\mathsf{data}} and the distribution p_{Y_{\mathsf{out}}} of the sampled sequence after K iterations. Following prior analysis of DLM sampling convergence ( 29 ; 10 ) , it is useful to separate two sources of error: (i) prediction error due to using an imperfect mask predictor, and (ii) intrinsic sampling error due to parallel decoding, which persists even with access to true conditional marginals. We begin by quantifying the quality of the learned mask predictor used during the token generation process. Recall the training objective from ( 3 ) in Section 2 , whose optimal solution p^{\star} corresponds to the product of the true conditional marginals p_{i}^{\star} defined in ( 2 ). Definition 1 . For any mask predictor \widehat{p}=\prod_{i=1}^{T}\widehat{p}_{i} , define its prediction error under an unmasking schedule \pi as \displaystyle\varepsilon_{\mathsf{pred}}(\pi) \displaystyle\coloneqq{\mathbb{E}}_{X^{(0)},S,\tau}\Bigg[\frac{L}{|M^{(\tau)}|}\sum_{i\in M^{(\tau)}}\log p_{i}^{\star}\big(X^{(0)}_{i}\mid X^{(\tau)}\big)\Bigg]-{\mathbb{E}}_{X^{(0)},S,\tau}\Bigg[\frac{L}{|M^{(\tau)}|}\sum_{i\in M^{(\tau)}}\log\widehat{p}_{i}\big(X^{(0)}_{i}\mid X^{(\tau)}\big)\Bigg], (22) where M^{(\tau)}=\cup_{k=\tau}^{K}S^{(k)} is the set of masked tokens at step \tau and X^{(\tau)}=\mathcal{P}_{[L]\setminus M^{(\tau)}}(X^{(0)}) is the corresponding partially masked sequence. The expectation is taken over the data sample X^{(0)}\sim p_{\mathsf{data}} , unmasking sets S=(S^{(1)},S^{(2)},\ldots,S^{(K)})\sim\pi , and iteration index \tau\in[K] sampled according to \mathbb{P}\{\tau=k\mid S\}=|S^{(k)}|/{L} . Intuitively, \varepsilon_{\mathsf{pred}}(\pi) measures the average log-likelihood suboptimality of the learned mask predictor \widehat{p} relative to the optimal solution p^{\star} , evaluated on the partially masked sequences encountered under schedule \pi . When the optimal mask predictor is used, we have \varepsilon_{\mathsf{pred}}(\pi)=0 for any unmasking strategy \pi . We now state our main results regarding the KL sampling error of our proposed unmasking schemes. To begin with, Theorem 1 provides the KL sampling error bound of the unmasking scheme \pi_{\mathsf{tc}} . Theorem 1 . Given any mask predictor \widehat{p} , the KL divergence between the data distribution and the sampled distribution produced by the unmasking schedule \pi_{\mathsf{tc}}(K,[L]) satisfies, for any 2\leq K\leq L , \displaystyle\mathsf{KL}(p_{\mathsf{data}}\,\|\,p_{Y_{\mathsf{out}}}) \displaystyle\leq\mathbb{E}_{S\sim\pi_{\mathsf{tc}}}\big[\mathsf{KL}(p_{\mathsf{data}}\,\|\,p_{Y_{\mathsf{out}}^{S}}\big)\big]\leq\frac{H_{L-K+1}-1}{K+H_{L-K+1}-2}\mathsf{TC}(p_{\mathsf{data}})+\varepsilon_{\mathsf{pred}}(\pi_{\mathsf{tc}}). (23) Here, p_{Y_{\mathsf{out}}^{S}} is the sampled distribution conditioned on a fixed sequence of unmasking sets S=(S^{(1)},S^{(2)},\ldots,S^{(K)}) , H_{n}\coloneqq\sum_{i=1}^{n}i^{-1} denotes the n -th harmonic number for n\geq 1 , and \varepsilon_{\mathsf{pred}}(\pi_{\mathsf{tc}}) is the prediction error of the mask predictor \widehat{p} defined in ( 22 ). The next theorem provides an analogous KL sampling error bound for the DTC-adaptive unmasking scheme \pi_{\mathsf{dtc}} . Theorem 2 . Given any mask predictor \widehat{p} , the KL divergence between the data distribution and the sampled distribution produced by the unmasking schedule \pi_{\mathsf{dtc}}(K,[L]) satisfies, for any H_{L-1}H_{L-1} , we have f_{\mathsf{dtc}}(K,L)\leq\frac{\min\{L^{\prime}-K,\frac{L}{K}H_{L-1}\}}{L-\min\{L^{\prime}-K,\frac{L}{K}H_{L-1}\}}\leq\frac{H_{L-1}}{K-H_{L-1}}. (34) Putting ( 25 ), ( 32 ), and ( 34 ) together finishes the proof of Theorem 2 . 5 Numerical experiment In this section, we evaluate the sampling performance of our proposed unmasking scheme and empirically verify the convergence theory in Theorems 1 – 2 via numerical experiments. We take the vocabulary \mathbb{X} to be the finite field \mathbb{F}_{q} , and let p_{\mathsf{data}} be the uniform distribution over a d -dimensional Reed-Solomon(RS) code in \mathbb{F}_{q}^{L} . Specifically, \displaystyle p_{\mathsf{data}}^{\text{RS}}(x)=\begin{cases}q^{-d},&\text{if }\exists\text{ a polynomial }p\text{ over }\mathbb{F}_{q}\text{ with }\\ &\mathsf{deg}(p)K>2 . Suppose ( 45 ) is valid for every pair (K^{\prime},L^{\prime\prime}) satisfying K^{\prime}+L^{\prime\prime}K , which amounts to showing \displaystyle\Psi^{\mathsf{tc}}(K,L^{\prime})\leq\big(1+(L^{\prime}-2)f_{\mathsf{tc}}(K-1,L^{\prime}-1)\big)\cdot\frac{K+H_{L^{\prime}-K+1}-2}{K-1}. (46) A key ingredient is the following recurrence linking \Psi^{\mathsf{tc}}(K,L^{\prime}) to \Psi^{\mathsf{tc}}(K,L^{\prime}-1) : \displaystyle\Psi^{\mathsf{tc}}(K,L^{\prime})-1 \displaystyle=\frac{(L^{\prime}-1)f_{\mathsf{tc}}(K-1,L^{\prime}-1)}{1+(L^{\prime}-3)f_{\mathsf{tc}}(K-1,L^{\prime}-2)}\Psi^{\mathsf{tc}}(K,L^{\prime}-1). (47) We postpone its derivation to the end of this subsection. Taking ( 47 ) as given, we carry out the induction argument. By the inductive assumption applied to the pair (K,L^{\prime}-1) , we obtain \frac{\Psi^{\mathsf{tc}}(K,L^{\prime}-1)}{1+(L^{\prime}-3)f_{\mathsf{tc}}(K-1,L^{\prime}-2)}\leq\frac{K+H_{L^{\prime}-K}-2}{K-1}. Substituting this estimate into ( 47 ) yields the following upper bound on \Psi^{\mathsf{tc}}(K,L^{\prime}) : \displaystyle\Psi^{\mathsf{tc}}(K,L^{\prime}) \displaystyle\leq 1+\frac{(L^{\prime}-1)f_{\mathsf{tc}}(K-1,L^{\prime}-1)}{1+(L^{\prime}-3)f_{\mathsf{tc}}(K-1,L^{\prime}-2)}\cdot\bigl(1+(L^{\prime}-3)f_{\mathsf{tc}}(K-1,L^{\prime}-2)\bigr)\cdot\frac{K+H_{L^{\prime}-K}-2}{K-1} \displaystyle=1+\frac{(L^{\prime}-1)f_{\mathsf{tc}}(K-1,L^{\prime}-1)(K+H_{L^{\prime}-K}-2)}{K-1}. Therefore, proving ( 46 ) reduces to verifying that 1+\frac{(L^{\prime}-1)f_{\mathsf{tc}}(K-1,L^{\prime}-1)(K+H_{L^{\prime}-K}-2)}{K-1}\leq\frac{(1+(L^{\prime}-2)f_{\mathsf{tc}}(K-1,L^{\prime}-1))(K+H_{L^{\prime}-K+1}-2)}{K-1}. After multiplying through by (K-1) and reorganizing, this becomes (K-1)+(L^{\prime}-1)f_{\mathsf{tc}}(K-1,L^{\prime}-1)(K+H_{L^{\prime}-K}-2)\leq\big(1+(L^{\prime}-2)f_{\mathsf{tc}}(K-1,L^{\prime}-1)\big)(K+H_{L^{\prime}-K+1}-2). (48) Isolating the factor f_{\mathsf{tc}}(K-1,L^{\prime}-1) and simplifying, ( 48 ) can be rewritten as f_{\mathsf{tc}}(K-1,L^{\prime}-1)\big[(L^{\prime}-1)(K+H_{L^{\prime}-K}-2)-(L^{\prime}-2)(K+H_{L^{\prime}-K+1}-2)\big]\leq(K+H_{L^{\prime}-K+1}-2)-(K-1)=H_{L^{\prime}-K+1}-1. The bracketed expression admits the following simplification: \displaystyle(L^{\prime}-1)(K+H_{L^{\prime}-K}-2)-(L^{\prime}-2)(K+H_{L^{\prime}-K+1}-2) \displaystyle\qquad=(K+H_{L^{\prime}-K}-2)+(L^{\prime}-2)\big(H_{L^{\prime}-K}-H_{L^{\prime}-K+1}\big) \displaystyle\qquad=(K+H_{L^{\prime}-K}-2)-\frac{L^{\prime}-2}{L^{\prime}-K+1} \displaystyle\qquad=K-2+H_{L^{\prime}-K+1}-\frac{1}{L^{\prime}-K+1}-\frac{L^{\prime}-2}{L^{\prime}-K+1} \displaystyle\qquad=K-3+H_{L^{\prime}-K+1}-\frac{K-2}{L^{\prime}-K+1}. with the second and third equalities following from the harmonic number identity H_{L^{\prime}-K+1}=H_{L^{\prime}-K}+(L^{\prime}-K+1)^{-1} . Combining the above, it remains to establish that \Big(K-3+H_{L^{\prime}-K+1}-\frac{K-2}{L^{\prime}-K+1}\Big)f_{\mathsf{tc}}(K-1,L^{\prime}-1)\leq H_{L^{\prime}-K+1}-1. (49) To complete the argument, invoke the induction hypothesis for (K-1,L^{\prime}-1) — valid because (K-1)+(L^{\prime}-1)0, (68) which immediately implies that \displaystyle f_{\mathsf{dtc}}(K,L^{\prime}) \displaystyle=-1+\frac{1+(L-L^{\prime}+2)f_{\mathsf{dtc}}(K-1,L^{\prime}-1)}{\Psi_{\mathsf{dtc}}(K,L^{\prime})} \displaystyle\leq-1+\frac{L}{L-\min\{L^{\prime}-K,\frac{L}{K}(H_{L-1}-H_{L-L^{\prime}})\}}=\frac{\min\{L^{\prime}-K,\frac{L}{K}(H_{L-1}-H_{L-L^{\prime}})\}}{L-\min\{L^{\prime}-K,\frac{L}{K}(H_{L-1}-H_{L-L^{\prime}})\}}. Towards this, we introduce the shorthand notation \displaystyle p(K,L^{\prime})\coloneqq\min\Big\{L^{\prime}-K,\frac{L}{K}(H_{L-1}-H_{L-L^{\prime}})\Big\} (69) for simplicity and presentation, and recall the definition of w_{l}^{\mathsf{dtc}} in ( 19 ) and \Psi_{\mathsf{dtc}}(K,L) in ( 12 ), we have \displaystyle\Psi_{\mathsf{dtc}}(K,L^{\prime}) \displaystyle=\sum_{\ell=1}^{L^{\prime}-K+1}\prod_{i=1}^{\ell-1}\frac{(L-L^{\prime}+i)f_{\mathsf{dtc}}(K-1,L^{\prime}-i)}{1+(L-L^{\prime}+i+2)f_{\mathsf{dtc}}(K-1,L^{\prime}-i-1)}. In what follows, we will prove \frac{\Psi_{\mathsf{dtc}}(K,L^{\prime})}{1+(L-L^{\prime}+2)f_{\mathsf{dtc}}(K-1,L^{\prime}-1)}\geq 1-\frac{p(K,L^{\prime})}{L} by strong induction on the pair (K,L^{\prime}) , or equivalently, the sum K+L^{\prime} . A.6.1 Base case 1: K=2 For K=2 , we have f_{\mathsf{dtc}}(K-1,L^{\prime})=f_{\mathsf{dtc}}(1,L^{\prime})=\frac{L^{\prime}-1}{L-L^{\prime}+1} for all L^{\prime}\geq 1 . Thus, each term in the product defining \Psi_{\mathsf{dtc}}(2,L^{\prime}) simplifies as \frac{(L-L^{\prime}+i)f_{\mathsf{dtc}}(K-1,L^{\prime}-i)}{1+(L-L^{\prime}+i+2)f_{\mathsf{dtc}}(K-1,L^{\prime}-i-1)}=\frac{(L-L^{\prime}+i)\frac{L^{\prime}-i-1}{L-L^{\prime}+i+1}}{1+(L-L^{\prime}+i+2)\frac{L^{\prime}-i-2}{L-L^{\prime}+i+2}}=\frac{L-L^{\prime}+i}{L-L^{\prime}+i+1}. and the product telescopes as \prod_{i=1}^{\ell-1}\frac{(L-L^{\prime}+i)f_{\mathsf{dtc}}(K-1,L^{\prime}-i)}{1+(L-L^{\prime}+i+2)f_{\mathsf{dtc}}(K-1,L^{\prime}-i-1)}=\prod_{i=1}^{\ell-1}\frac{L-L^{\prime}+i}{L-L^{\prime}+i+1}=\frac{L-L^{\prime}+1}{L-L^{\prime}+\ell}. Combining the expressions of \Psi_{\mathsf{dtc}}(2,L^{\prime}) and f_{\mathsf{dtc}}(1,L^{\prime}-1) , we can bound \displaystyle\frac{\Psi_{\mathsf{dtc}}(2,L^{\prime})}{1+(L-L^{\prime}+2)f_{\mathsf{dtc}}(1,L^{\prime}-1)} \displaystyle=\frac{L-L^{\prime}+1}{L^{\prime}-1}\sum_{\ell=1}^{L^{\prime}-1}\frac{1}{L-L^{\prime}+\ell} \displaystyle\overset{(\mathrm{i})}{\geq}\frac{L-L^{\prime}+1}{L^{\prime}-1}\frac{(L^{\prime}-1)^{2}}{\sum_{\ell=1}^{L^{\prime}-1}(L-L^{\prime}+\ell)} \displaystyle=\frac{2(L-L^{\prime}+1)}{2L-L^{\prime}}=1-\frac{L^{\prime}-2}{2L-L^{\prime}} \displaystyle\geq 1-\frac{L^{\prime}-2}{L}, where (i) arises from \displaystyle\sum_{\ell=1}^{L^{\prime}-1}\frac{1}{L-L^{\prime}+\ell}\geq\frac{(L^{\prime}-1)^{2}}{\sum_{\ell=1}^{L^{\prime}-1}(L-L^{\prime}+\ell)}. (70) This is due to the Cauchy-Schwarz inequality: for any positive numbers a_{1},a_{2},\ldots,a_{n} , \sum_{i=1}^{n}\frac{1}{a_{i}}\geq\frac{n^{2}}{\sum_{i=1}^{n}a_{i}} . Meanwhile, one can also bound \displaystyle\frac{\Psi_{\mathsf{dtc}}(2,L^{\prime})}{1+(L-L^{\prime}+2)f_{\mathsf{dtc}}(1,L^{\prime}-1)} \displaystyle=\frac{L-L^{\prime}+1}{L^{\prime}-1}\sum_{\ell=1}^{L^{\prime}-1}\frac{1}{L-L^{\prime}+\ell} \displaystyle=\frac{L-L^{\prime}+1}{L^{\prime}-1}(H_{L-1}-H_{L-L^{\prime}}) \displaystyle=\Big(1-\frac{H_{L-1}-H_{L-L^{\prime}}}{2}\Big)+\Big(\frac{L-L^{\prime}+1}{L^{\prime}-1}+\frac{1}{2}\Big)(H_{L-1}-H_{L-L^{\prime}})-1 \displaystyle\geq 1-\frac{\frac{L}{2}(H_{L-1}-H_{L-L^{\prime}})}{L}+\Big(\frac{L-L^{\prime}+1}{L^{\prime}-1}+\frac{1}{2}\Big)\frac{(L^{\prime}-1)^{2}}{\sum_{\ell=1}^{L^{\prime}-1}(L-L^{\prime}+\ell)}-1 \displaystyle=1-\frac{\frac{L}{2}(H_{L-1}-H_{L-L^{\prime}})}{L}+\frac{2L-L^{\prime}+1}{2L-L^{\prime}}-1 \displaystyle\geq 1-\frac{\frac{L}{2}(H_{L-1}-H_{L-L^{\prime}})}{L}, where the first inequality applies ( 70 ) again. Combining these two bounds with the definition of p(K,L^{\prime}) in ( 69 ), we conclude that \frac{\Psi_{\mathsf{dtc}}(2,L^{\prime})}{1+(L-L^{\prime}+2)f_{\mathsf{dtc}}(1,L^{\prime}-1)}\geq\max\bigg\{1-\frac{L^{\prime}-2}{L},1-\frac{\frac{L}{2}(H_{L-1}-H_{L-L^{\prime}})}{L}\bigg\}=1-\frac{p(2,L^{\prime})}{L}, confirming the base case K=2 . A.6.2 Base case 2: L^{\prime}=K>2 Next, let us consider the “diagonal boundary” of the region L^{\prime}\geq K . In this case, it is not hard to see that w_{1}^{\mathsf{dtc}}(K,K)=\Psi_{\mathsf{dtc}}(K,K)=1 and p(K,K)=0 for any K\geq 2 . In particular, by the definition of f_{\mathsf{dtc}} in ( 21 ) and the base case f_{\mathsf{dtc}}(1,1)=0 , we can use induction on K to show that f_{\mathsf{dtc}}(K-1,K-1)=0 . Hence, we find that \frac{\Psi_{\mathsf{dtc}}(K,K)}{1+(L-L^{\prime}+2)f_{\mathsf{dtc}}(K-1,K-1)}=1=1-\frac{p(K,K)}{L}. This establishes the base case L^{\prime}=K . A.6.3 Inductive step: L^{\prime}>K>2 Now, let us assume ( 68 ) holds for all pairs (K^{\prime},L^{\prime\prime}) with K^{\prime}+L^{\prime\prime}0. Together with ( 74 ), this yields that the left-hand side of ( 73 ) is at most \frac{L\big(K-1-(H_{L-1}-H_{L-L^{\prime}})\big)\,(H_{L-1}-H_{L-L^{\prime}+1})}{K\big(K-1-(H_{L-1}-H_{L-L^{\prime}+1})\big)}. This is upper bounded by p(K,L^{\prime})=\frac{L}{K}(H_{L-1}-H_{L-L^{\prime}}) if and only if \big(K-1-(H_{L-1}-H_{L-L^{\prime}})\big)\,(H_{L-1}-H_{L-L^{\prime}+1})\leq(H_{L-1}-H_{L-L^{\prime}})\,\big(K-1-(H_{L-1}-H_{L-L^{\prime}+1})\big), or equivalently, (K-1)(H_{L-1}-H_{L-L^{\prime}+1})\leq(K-1)(H_{L-1}-H_{L-L^{\prime}}). This holds since H_{n} is increasing in n . Hence, ( 73 ) holds in Sub-case 2a. • Sub-case 2b: p(K-1,L^{\prime}-1)=L^{\prime}-K . In this case, one has \frac{p(K-1,L^{\prime}-1)}{L-p(K-1,L^{\prime}-1)}=\frac{L^{\prime}-K}{L-L^{\prime}+K}. Combining this with ( 74 ), we can control the left-hand side of ( 73 ) by \frac{L\big(K-1-(H_{L-1}-H_{L-L^{\prime}})\big)(L^{\prime}-K)}{K(L-L^{\prime}+K)}. This is upper bounded by p(K,L^{\prime})=\frac{L}{K}(H_{L-1}-H_{L-L^{\prime}}) if and only if \big(K-1-(H_{L-1}-H_{L-L^{\prime}})\big)(L^{\prime}-K)\leq(H_{L-1}-H_{L-L^{\prime}})(L-L^{\prime}+K), or equivalently, (K-1)(L^{\prime}-K)\leq(H_{L-1}-H_{L-L^{\prime}})L. Since the condition p(K-1,L^{\prime}-1)=L^{\prime}-K means that \frac{L}{K-1}(H_{L-1}-H_{L-L^{\prime}+1})\geq L^{\prime}-K , we obtain L(H_{L-1}-H_{L-L^{\prime}})=L(H_{L-1}-H_{L-L^{\prime}+1})+\frac{L}{L-L^{\prime}+1}>(K-1)(L^{\prime}-K), which verifies the desired inequality. Thus ( 73 ) also holds in Sub-case 2b. • Combining these two sub-cases establishes ( 73 ) in Case 2. Finally, combining Cases 1 and 2 concludes that ( 73 ) holds for (K,L^{\prime}) , thereby finishing the inductive step. The proof of Lemma 6 is now complete. Proof of the identity ( 72 ). It remains to prove the identity ( 72 ). Recall the definition of \Psi_{\mathsf{dtc}}(K,L^{\prime}) , we can write \displaystyle\Psi_{\mathsf{dtc}}(K,L^{\prime})-1 \displaystyle=\sum_{\ell=1}^{L^{\prime}-K+1}\prod_{i=1}^{\ell-1}\frac{(L-L^{\prime}+i)f_{\mathsf{dtc}}(K-1,L^{\prime}-i)}{1+(L-L^{\prime}+i+2)f_{\mathsf{dtc}}(K-1,L^{\prime}-i-1)}-1 \displaystyle=\sum_{\ell=2}^{L^{\prime}-K+1}\prod_{i=1}^{\ell-1}\frac{(L-L^{\prime}+i)f_{\mathsf{dtc}}(K-1,L^{\prime}-i)}{1+(L-L^{\prime}+i+2)f_{\mathsf{dtc}}(K-1,L^{\prime}-i-1)}, where the last equality follows from the fact that the \ell=1 term in the sum is 1 . We can further derive \displaystyle\Psi_{\mathsf{dtc}}(K,L^{\prime})-1 \displaystyle=\frac{(L-L^{\prime}+1)f_{\mathsf{dtc}}(K-1,L^{\prime}-1)}{1+(L-L^{\prime}+3)f_{\mathsf{dtc}}(K-1,L^{\prime}-2)}\sum_{\ell=2}^{L^{\prime}-K+1}\prod_{i=2}^{\ell-1}\frac{(L-L^{\prime}+i)f_{\mathsf{dtc}}(K-1,L^{\prime}-i)}{1+(L-L^{\prime}+i+2)f_{\mathsf{dtc}}(K-1,L^{\prime}-i-1)} \displaystyle=\frac{(L-L^{\prime}+1)f_{\mathsf{dtc}}(K-1,L^{\prime}-1)}{1+(L-L^{\prime}+3)f_{\mathsf{dtc}}(K-1,L^{\prime}-2)}\sum_{\ell=1}^{L^{\prime}-K}\prod_{i=1}^{\ell-1}\frac{(L-L^{\prime}+1+i)f_{\mathsf{dtc}}(K-1,L^{\prime}-1-i)}{1+(L-L^{\prime}+1+i+2)f_{\mathsf{dtc}}(K-1,L^{\prime}-1-i-1)} \displaystyle=\frac{(L-L^{\prime}+1)f_{\mathsf{dtc}}(K-1,L^{\prime}-1)}{1+(L-L^{\prime}+3)f_{\mathsf{dtc}}(K-1,L^{\prime}-2)}\Psi_{\mathsf{dtc}}(K,L^{\prime}-1). where the first line extracts the i=1 factor in the product and the second line holds by re-indexing indices. This finishes the proof of ( 72 ). Appendix B Proof of auxiliary lemmas B.1 Proof of ( 25 ) We follow the argument in ( 29 ) to decompose the prediction error from the sampling error. For any fixed unmasking sets S=(S^{(1)},S^{(2)},\ldots,S^{(K)}) , we have \displaystyle\mathsf{KL}\big(p_{X^{(0)}}(\cdot)\,\|\,p_{Y_{\mathsf{out}}^{S}}(\cdot)\big)-\mathsf{KL}\big(p_{X^{(0)}}(\cdot)\,\|\,p_{\overline{Y}^{S}_{\mathsf{out}}}(\cdot)\big) \displaystyle\quad=\int_{\mathbb{X}^{L}}p_{X^{(0)}}(x)\log\frac{p_{\overline{Y}^{S}_{\mathsf{out}}}(x)}{p_{Y_{\mathsf{out}}^{S}}(x)}\,\mathrm{d}x \displaystyle\quad\stackrel{{\scriptstyle\text{(i)}}}{{=}}\sum_{k=1}^{K}\int_{\mathbb{X}^{L}}p_{X^{(0)}}(x)\log\frac{p^{\star}(x_{S^{(k)}}\mid X_{U^{(k-1)}}=x_{U^{(k-1)}})}{\widehat{p}(x_{S^{(k)}}\mid X_{U^{(k-1)}}=x_{U^{(k-1)}})}\,\mathrm{d}x \displaystyle\quad\stackrel{{\scriptstyle\text{(ii)}}}{{=}}\sum_{k=1}^{K}\int_{\mathbb{X}^{L}}p_{X^{(0)}}(x)\sum_{i\in S^{(k)}}\log\frac{p_{i}^{\star}(x_{i}\mid X_{U^{(k-1)}}=x_{U^{(k-1)}})}{\widehat{p}_{i}(x_{i}\mid X_{U^{(k-1)}}=x_{U^{(k-1)}})}\,\mathrm{d}x \displaystyle\quad\stackrel{{\scriptstyle\text{(iii)}}}{{=}}\mathbb{E}_{\tau,X^{(0)}}\Bigg[\frac{L}{|S^{(\tau)}|}\sum_{i\in S^{(\tau)}}\log\frac{p_{i}^{\star}(X^{(0)}_{i}\mid X^{(\tau)})}{\widehat{p}_{i}(X^{(0)}_{i}\mid X^{(\tau)})}\,\Big|\,S\Bigg], where (i) follows from the chain rule and the definition of p_{Y_{\mathsf{out}}^{S}} and p_{\overline{Y}^{S}_{\mathsf{out}}} ; (ii) uses the fact that p^{\star} and \hat{p} are product distributions; (iii) holds because of the definition \mathbb{P}\{\tau=k\mid S\}=\frac{1}{L}|S^{(\tau)}| . Taking the expectation over S\sim\pi , we obtain ( 25 ): \displaystyle\mathbb{E}_{S\sim\pi}\Big[\mathsf{KL}\big(p_{X^{(0)}}(\cdot)\,\|\,p_{Y_{\mathsf{out}}^{S}}(\cdot)\big)-\mathsf{KL}\big(p_{X^{(0)}}(\cdot)\,\|\,p_{\overline{Y}^{S}_{\mathsf{out}}}(\cdot)\big)\Big] \displaystyle\quad=\mathbb{E}_{\tau,X^{(0)},S}\Bigg[\frac{L}{|M^{(\tau)}|}\sum_{i\in M^{(\tau)}}\log\frac{p_{i}^{\star}(X^{(0)}_{i}\mid X^{(\tau)})}{\widehat{p}_{i}(X^{(0)}_{i}\mid X^{(\tau)})}\Bigg]=\varepsilon_{\mathsf{pred}}(\pi). B.2 Proof of Lemma 1 Note that the sampled distribution of the first batch is the product of conditional marginals: \left(\prod_{i\in S}p_{X_{i}}(\cdot\mid x_{\mathcal{I}^{\mathsf{c}}})\right)(x_{S})=\prod_{i\in S}p_{X_{i}}(x_{i}\mid x_{\mathcal{I}^{\mathsf{c}}}). Hence, the KL divergence can be expressed as \displaystyle\mathsf{KL}\big(p_{X_{S}}(\cdot\mid x_{\mathcal{I}^{\mathsf{c}}})\|\prod_{i\in S}p_{X_{i}}(\cdot\mid x_{\mathcal{I}^{\mathsf{c}}})\big) \displaystyle=\sum_{x_{S}}p_{X_{S}}(x_{S}\mid x_{\mathcal{I}^{\mathsf{c}}})\log\frac{p_{X_{S}}(x_{S}\mid x_{\mathcal{I}^{\mathsf{c}}})}{\prod_{i\in S}p_{X_{i}}(x_{i}\mid x_{\mathcal{I}^{\mathsf{c}}})} \displaystyle=\sum_{i\in S}H(X_{i}\mid x_{\mathcal{I}^{\mathsf{c}}})-H(X_{S}\mid x_{\mathcal{I}^{\mathsf{c}}}) \displaystyle=\mathsf{TC}(X_{S}\mid x_{\mathcal{I}^{\mathsf{c}}}). B.3 Relationship between TC and DTC Lemma 7 . For any random vector X=(X_{1},X_{2},\ldots,X_{n}) , we have \mathsf{TC}(X)\leq(n-1)\mathsf{DTC}(X). Proof. Consider the n cyclic permutations \sigma_{0},\sigma_{1},\ldots,\sigma_{n-1} of [n] , where \sigma_{j}(k)=((k+j-1)\bmod n)+1 . Applying the chain rule of entropy to each cyclic permutation \sigma_{j} gives \displaystyle H(X_{[n]})=\sum_{k=1}^{n}H\big(X_{\sigma_{j}(k)}\mid X_{\sigma_{j}(1)},\ldots,X_{\sigma_{j}(k-1)}\big). (75) Summing ( 75 ) over all n cyclic permutations yields \displaystyle n\,H(X_{[n]})=\sum_{j=0}^{n-1}\sum_{k=1}^{n}H\big(X_{\sigma_{j}(k)}\mid X_{\sigma_{j}(1)},\ldots,X_{\sigma_{j}(k-1)}\big). (76) Now we examine the contribution of each X_{i} to the right-hand side. Across the n cyclic permutations, X_{i} appears exactly once in each position k=1,\ldots,n . In particular: • When k=1 : X_{i} is conditioned on nothing, contributing H(X_{i}) . • When k=n : X_{i} is conditioned on all others, contributing H(X_{i}\mid X_{[n]\setminus\{i\}}) . • For k=2,\ldots,n-1 : X_{i} is conditioned on some strict subset of [n]\setminus\{i\} . Since conditioning reduces entropy, i.e., H(X_{i}\mid X_{T})\geq H(X_{i}\mid X_{[n]\setminus\{i\}}) for any T\subseteq[n]\setminus\{i\} , the n-2 middle terms are each lower bounded by H(X_{i}\mid X_{[n]\setminus\{i\}}) . Therefore, for each X_{i} , its total contribution satisfies \displaystyle\sum_{k=1}^{n}H(X_{\sigma_{j}(k)}\mid X_{\sigma_{j}(1)},\ldots,X_{\sigma_{j}(k-1)})\geq H(X_{\sigma_{j}(1)})+(n-1)H(X_{\sigma_{j}(1)}\mid X_{[n]\setminus\{i\}}). (77) Summing ( 77 ) over all i\in[n] and substituting into ( 76 ), we obtain \displaystyle n\,H(X_{[n]})\geq\sum_{i=1}^{n}H(X_{i})+(n-1)\sum_{i=1}^{n}H(X_{i}\mid X_{[n]\setminus\{i\}}). (78) Rearranging ( 78 ) gives \displaystyle\sum_{i=1}^{n}H(X_{i})-H(X_{[n]})\leq(n-1)\bigg(H(X_{[n]})-\sum_{i=1}^{n}H(X_{i}\mid X_{[n]\setminus\{i\}})\bigg). This is equivalent to the desired inequality: \mathsf{TC}(X)\leq(n-1)\,\mathsf{DTC}(X). ∎