{"id":"9cc21a71-5573-4131-a45d-dea248ba0d12","arxiv_id":"2608.13520","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":1,"one_line_summary":"Unmasking growth complexity directly controls KL discretization error in masking diffusion and enables certified, data-adaptive schedules that approach oracle efficiency.","lead":"Masking diffusion samplers can be made more efficient by allocating computation according to a path-resolved measure of data geometry called unmasking growth complexity (UGC), whose local increments control the approximation error. The paper derives certified-optimal schedules and shows that adaptively placed blocks can yield large dimension-dependent gains over uniform schedules.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The certified-optimal guarantee in Theorem 2 depends on a known moment bound B_alpha and exact Bayes denoisers; without a method to obtain B_alpha from data, the headline data-dependent certificate is not established.","rationale":"The reader's weakest assumption identifies exactly the same load-bearing concern: the certified guarantees require a known B_alpha and exact Bayes denoisers, while Section 7 acknowledges that learned denoisers introduce an uncertified approximation term. I re-read the relevant statements: Proposition 2 states its sandwich under condition (33a); Theorem 2 uses it to construct bCUGC and the multipliers (37a); and the 'certified-optimal' paragraph in Section 4.4.1 claims an end-to-end guarantee for any prescribed epsilon and eta. Nowhere is a method given to derive a valid B_alpha from data. This is not an internal inconsistency in the proof, since Theorem 2 follows from its stated assumptions, but it means the central contribution--fully data-dependent certification--is not actually delivered by the stated results. The concern is therefore real and load-bearing. The paper is still a substantial theoretical advance: Theorem 1, Lemma 4, the UGC path geometry, the fine-partition limit, and the XORSAT example (Lemma 2) are independent of the B_alpha issue and appear sound. The reader's CONDITIONAL verdict remains appropriate: the authors should either provide a certified estimation procedure for B_alpha or clearly restate the guarantees as conditional on an oracle-provided B_alpha and exact denoisers. No adjustment to the verdict is needed because the reader already flagged this gap; my read confirms it rather than introducing a new objection.","tokens_in":41118,"tokens_out":3628,"duration_ms":38169,"concrete_test":"On a concrete finite-alphabet target (e.g., the noisy repeated-bit ensemble with d=128 and eta=0.01), first compute the exact B_alpha from the true Bayes denoisers and verify that the tail-robust estimator (33b) with m i.i.d. samples satisfies the factor-two sandwich (34a) at the nominal 1-eta level. Then replace B_alpha by a sample-based upper confidence bound (for instance, an empirical moment estimate plus a Bernstein-type correction) and re-run the same experiment. If the sandwich (34a), and hence the Theorem 2 guarantee (37b), fails at the claimed 1-eta level under the estimated B_alpha, the certificate is not data-dependent as claimed; if it still holds, the gap is closed and the concern is resolved.","verdict_should_be":"UNCHANGED","load_bearing_attack":"Theorem 2 (eq. 37b) and its supporting Proposition 2 (eq. 34a) assume condition (33a): a known finite moment bound B_alpha on the aggregate KL increments of the one-coordinate Bayes denoisers over each reveal-odds-dyadic interval, along with access to the exact denoisers. This assumption is load-bearing because the 'certified-optimal' claim in Section 4.4 (eq. 35) promises data-dependent parameter choices that guarantee KL error at a prescribed level with high probability. If B_alpha is unknown, as it is for any real target distribution, the tail-robust estimator (33b) cannot be instantiated and the sandwich (34a) does not follow. The paper provides no procedure for computing a valid high-probability upper bound on B_alpha from samples while preserving the simultaneous certificate; estimating B_alpha would introduce an additional error term not accounted for in Proposition 2 or Theorem 2. Separately, equation (18) shows that learned denoisers add an approximation term Eden(bmu) to the KL bound, and Section 7 acknowledges this term is not estimated or certified. Thus the abstract's claim of samplers that are 'certified-optimal' and 'achieve a prescribed KL error with high probability' is, as stated, only valid for exact Bayes denoisers with a known B_alpha. The theorems are internally consistent under their assumptions, so this is a gap between the headline contribution and the proved statement rather than a contradiction, but it is the weakest point in the central claim.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces the unmasking growth complexity (UGC), a path-resolved functional of the masking reveal process, and uses it to bound the KL discretization error of Bernoulli-subset and fixed-cardinality unmasking samplers. The main technical results are: Theorem 1, bounding the KL error of both samplers by additive sums of local UGC increments; Proposition 2, a tail-robust estimator that sandwiches UGC increments from samples using KL increments along coupled reveal trajectories; Theorem 2, a data-dependent multi-block sampler with a high-probability KL certificate under stated moment and exact-denoiser assumptions; and Theorem 3, identifying the fine-partition limit with the squared integral of the square-root UGC density and the sharp leading-order optimal Euler error. The paper also connects aggregate UGC to classical dependence measures and exhibits examples with exponential-in-sqrt(d) gains in the ratio between coarse and fine partition complexities.","tokens_in":41415,"tokens_out":4043,"duration_ms":42561,"significance":"If the results hold as stated, the UGC framework is a valuable unification: it gives explicit additive KL bounds for two unmasking schemes, connects Bernoulli and fixed-cardinality analyses through exact information-profile representations, and provides a data-dependent estimation procedure with finite-sample Bernstein-type guarantees. The paper is refreshing in that the main Bernoulli proof is self-contained and the fixed-cardinality part is explicitly built on the exact representation of Chen et al. The fine-partition/Euler result (Theorem 3) is a clean sharp leading-order statement. The central weakness, already acknowledged in Section 7, is that the headline certified-optimal claim in Theorem 2 requires a known moment bound B_alpha and exact Bayes denoisers; for learned denoisers the additional approximation term (18) is not certified. This is not a mathematical inconsistency, but it is a material gap between the abstract's promise of certifiable samplers and the theorem's hypotheses.","major_comments":[{"comment":"The certified-optimal guarantee depends on condition (33a), which presumes a known finite moment bound B_alpha on aggregate denoiser KL increments, and on access to exact Bayes denoisers. No procedure is given for obtaining a valid high-probability upper bound on B_alpha from samples while preserving the simultaneous certificate. Estimating B_alpha from the same data would introduce an additional error term that is not accounted for in Proposition 2 or Theorem 2. Since equation (35) promises data-dependent parameter choices that guarantee D_KL <= epsilon with high probability, the claim as stated is only established under an oracle-like moment condition. Section 7 acknowledges the learned-denoiser issue, but the abstract and the certified-optimal terminology in Section 4.4 overstate what the theorem proves.","section":"4.4 (Theorem 2, Eq. (37b))"},{"comment":"The proof of Proposition 1 is delegated to the companion paper [Wai26] with only a 'mutatis mutandis' explanation. Because [Wai26] is an unpublished preprint and Proposition 1 is load-bearing for the near-optimality claim of the oracle schedule, this leaves a proof gap in the present manuscript. A self-contained proof, or a version-of-record reference with the specific lemmas adapted to the log-reveal-odds clock, is needed.","section":"4.2 (Proposition 1)"},{"comment":"The dynamic-programming boundary selection is described conceptually, but no theorem is stated or proved that the data-dependent selected partition satisfies a KL certificate after optimizing the block boundaries. Theorem 2 applies only to a fixed K-block partition; when the partition itself is chosen from data using estimated edge costs, the selection procedure introduces additional uncertainty that is not covered by the union bound in the proof of Theorem 2. As written, the claim of certified boundary selection is not supported by a formal guarantee.","section":"4.4.2 (Certified-optimal boundary selection)"}],"minor_comments":[{"comment":"The notation eOmega(sqrt(d)) in the abstract and Section 2.2.1 is never defined; please define it or use standard asymptotic notation.","section":"2.2.1"},{"comment":"The display X_{t|i} := (M_{t|i}, Z_{(M_{t|i})^c}) appears to conflate the masked set with the masked vector; the first component should presumably be the vector of mask symbols on M_{t|i}. This is a notation issue but it makes the forced-mask process harder to read.","section":"3.2, Eq. (30a)"},{"comment":"The proposition refers to 'score evaluations' while the rest of the paper speaks of 'unmasking rounds' or 'iterations'; please use consistent terminology and clarify whether the score budget counts one denoiser evaluation per coordinate per round.","section":"4.2, Proposition 1"},{"comment":"The uniform-partition convergence bound (46) is stated for f=sqrt(q) continuous on the closed interval, but the discussion after it mentions a Lipschitz constant Lip(f) without specifying how the Lipschitz constant scales with dimension; please make the dependence explicit.","section":"5.2.2, Lemma 3"}],"recommendation":"major_revision","confidential_remarks":"The paper is in scope and the core information-theoretic machinery is interesting, but the advertised certified-optimal result is narrower than stated: it holds only with exact Bayes denoisers and a known moment bound B_alpha, and the learned-denoiser term is explicitly unestimated. I would also want the proof of Proposition 1 and a formal treatment of data-dependent boundary selection before publication. These are fixable with careful rewriting and additional proofs, which is why I recommend major revision rather than rejection."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Bottom line: this is a genuine theoretical advance with a load-bearing but patchable gap. The UGC path measure and the sandwich estimator are new, and the main theorems (1 and 3) are convincing. The certified-optimal claim in Theorem 2 is real only under conditions the paper itself admits: known moment bound B_alpha and exact Bayes denoisers. The stress-test concern about B_alpha is right on target; without a method to bound it from data the certificate does not follow. That is a gap between abstract and theorem, not a fatal flaw.\n\nWhat is new: UGC gives a unified path-resolved control of KL error for Bernoulli and fixed-cardinality unmasking; the log-reveal-odds density and the fine-partition limit are elegant; the estimator from coupled reveal trajectories is genuinely clever. The paper also connects UGC to existing complexity measures and sharpens single-block guarantees. The proofs I traced are sound.\n\nSoft spots: (1) Theorem 2's data-dependent certificate relies on condition (33a) for a known B_alpha; the paper gives no procedure for obtaining a valid high-probability upper bound on B_alpha from samples. This is exactly the stress-test issue. The authors acknowledge learned denoisers add the approximation term Eden(bmu) in (18) but do not certify it. So \"certified-optimal\" is accurate only in a restrictive sense. (2) The e^{Omega(sqrt d)} scaling for the discrete mixture is asserted without proof (\"it can be shown\"), though the XORSAT lemma gives a tractable example; that is a minor presentational gap. (3) Proposition 1's proof is delegated mutatis mutandis to a companion Gaussian paper; acceptable in a series but weakens self-containedness.\n\nI read the reader's conditional verdict as fair. The central mathematical scaffolding is solid; the certification claim needs qualification or an additional estimation step for B_alpha. This paper deserves a serious referee. I would send it out; the flaws are addressable in revision.","headline":"A real theoretical advance in masking diffusion with a certificate that is narrower than advertised; the main theorems hold up but the data-dependent guarantee needs an extra layer for B_alpha.","tokens_in":41909,"tokens_out":1527,"would_cite":true,"duration_ms":16131,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["62B10","94A17","60J22"],"pacs":[],"model":"deepseek-v4-flash","headline":"A path-resolved measure of data geometry, the unmasking growth complexity, controls KL discretization error and yields certified-optimal masking diffusion schedules.","keywords":["masking diffusion","unmasking growth complexity","KL discretization error","certified-optimal schedules","log-reveal-odds coordinates","Bernoulli unmasking","fixed-cardinality unmasking","data-dependent sampling"],"falsifier":"Run the certified $K$-block procedure on the noisy repeated-bit ensemble with known UGC density, compute the true $H(p,q)$ exactly, and compare it with the truncated estimator $\\hat{H}_m(p,q)$ over many sample sizes; the factor-two sandwich of Proposition 2 would be falsified if the estimate plus confidence radius fails to contain $H(p,q)$ at a rate exceeding the chosen $\\eta$ for some distribution satisfying the moment condition (33a).","tokens_in":40873,"feed_emoji":"🎲","tokens_out":10224,"duration_ms":97554,"temperature":0.7,"pith_summary":"Masking diffusion samplers generate discrete data by progressively revealing masked coordinates, and their accuracy is set by how finely the reveal path is discretized. This paper claims that for both Bernoulli-subset and fixed-cardinality unmasking, the Kullback–Leibler (KL) discretization error is controlled by the local increments of one path-resolved quantity: the unmasking growth complexity (UGC), defined as a weighted integral of the curvature of mutual information along the reveal process. The increments are additive, and they can be estimated directly from clean samples through KL increments along coupled reveal trajectories, which lets a user build schedules that certify a prescribed KL error with high probability and run within a constant factor of the oracle-optimal iteration count. In log-reveal-odds coordinates the UGC density becomes the intrinsic local geometry, and its square-root integral gives the sharp leading-order optimal Euler discretization error in the fine-partition limit. The point of the paper is that schedule design for masking diffusion can be reduced to estimating and then allocating effort according to a measurable, data-dependent complexity path.","feed_headline":"Data geometry certifies optimal masking-diffusion schedules","feed_subtitle":"Local UGC increments are estimable from samples and certify KL error up to a constant factor.","key_machinery":"The load-bearing object is the unmasking growth complexity (UGC), an additive interval measure $H(p,q)=\\int_p^q t(1-t)h'(t)\\,dt$ built from the Bernoulli unmasking gain $h(t)=\\sum_i \\mathrm{Info}(Z_i;X_t\\mid i\\in M(X_t))$; its additivity $H(p,r)=H(p,q)+H(q,r)$ is what lets global schedules be decomposed into blocks. Its log-reveal-odds density $q(\\lambda)=r^2(1-r)^2h'(r)$, with $r=e^{\\lambda}/(1+e^{\\lambda})$, carries the local geometry, and the partition complexity $C(P)=\\left(\\sum_k \\sqrt{S_k H_k}\\right)^2$ quantifies the cost of a $K$-block geometric schedule. The mechanism that makes the theory data-driven is the sandwich of $H(p,q)$ between the KL unmasking increment $D(p,q)$ and twice it, estimated by running forced-mask reveal trajectories on clean samples and applying an empirical-Bernstein tail bound, which converts unknown UGC masses into certifiable confidence intervals.","core_discovery":"The central claim is that the unmasking growth complexity $H(p,q)=\\int_p^q t(1-t)h'(t)\\,dt$, where $h(t)$ sums the conditional mutual information between each still-masked coordinate and the revealed ones, is the correct local currency for masking-diffusion error: the one-step KL defect of a Bernoulli unmasking step is at most $(\\psi(q)/\\psi(p)-1)H(p,q)$, with $\\psi(t)=t/(1-t)$ the reveal odds, and an analogous bound holds for fixed-cardinality samplers with $H_{\\mathrm{card}}$. The paper further claims that $H(p,q)$ is sandwiched to within a factor two by the KL increment $D(p,q)$ between forced-mask reveal trajectories, so a truncated Monte Carlo estimator of those increments yields high-probability upper confidence bounds on every block. Plugging these bounds into geometric schedules gives Theorem 2: for any $K$-block partition and any target accuracy, the sampler reaches $D_{\\mathrm{KL}}(P_Z\\|\\hat{P}_{\\hat{Z}})\\le\\varepsilon$ with probability at least $1-\\eta$ using at most $N\\approx 8\\hat{C}_{\\mathrm{UGC}}(P)/\\varepsilon$ unmasking rounds. Theorem 3 sharpens the picture in the fine-partition limit: the infimum of the partition complexity is $(\\int\\sqrt{q}\\,d\\lambda)^2$, and the optimal $N$-step Euler discretization error is $\\left(\\int\\sqrt{q}\\,d\\lambda\\right)^2/(2N)+o(1/N)$.","pith_inferences":["The factor-two sandwich suggests a practical convergence diagnostic: per-block estimates of UGC mass from held-out samples could flag reveal times at which a trained denoiser has not captured the dominant dependencies, since those blocks will show persistently large confidence radii.","Because only the multiplicative reveal-odds ratio $\\psi(q)/\\psi(p)$ enters the one-step defect, the same additive machinery should extend to non-uniform or learned masking probabilities, although the paper does not analyze those variants.","The modulus-of-continuity bound for uniform partitions implies that for densities with sharp multi-peaked UGC, adaptive boundary selection should need far fewer blocks than uniform partitions; quantifying that gap for hierarchical mixture models is a testable extension of the paper's Lemma 3."],"forward_implications":["Single-block unmasking complexity is governed by the aggregate UGC mass, so existing fixed-cardinality guarantees are sharpened and Bernoulli unmasking matches CTMC-based $\\tau$-leaping guarantees.","A $K$-block geometric schedule with explicit multipliers is within a factor 4 of the optimal dynamic-program allocation, so the main computation shifts from solving an integer program to estimating UGC increments.","Choosing $N\\ge 8\\hat{C}_{\\mathrm{UGC}}(P)/\\varepsilon$ rounds gives an end-to-end certificate $D_{\\mathrm{KL}}\\le\\varepsilon$ with probability at least $1-\\eta$, replacing oracle knowledge of the target geometry by sample estimates.","In the fine-partition limit, the optimal Euler error is determined by $\\left(\\int\\sqrt{q}\\,d\\lambda\\right)^2$, so regions of large $q$ require smaller reveal-odds steps and the square-root UGC density is the fundamental schedule-optimality object.","Geometry-aware block boundaries can yield substantial dimension-dependent gains, including $\\widetilde{\\Omega}(\\sqrt{d})$ improvements with a constant number of adaptively placed blocks in the random XORSAT example."],"supporting_citations":[{"why":"Supplies the exact KL representation of fixed-cardinality unmasking whose information coefficients become the $h^{\\mathrm{card}}_j$ quantities in Theorem 1.","marker":"[CCL25]"},{"why":"Provides the effective-total-correlation CTMC guarantees that single-block UGC bounds match and sharpen.","marker":"[DHW26]"},{"why":"Gives the asymptotic square-root information-profile scheduling rule that Theorem 3 extends to finite dimension and finite steps.","marker":"[LZ25]"},{"why":"Supplies the empirical Bernstein inequality used to make the UGC increment estimator tail-robust in Proposition 2.","marker":"[MP09]"},{"why":"The companion Gaussian-diffusion analysis supplies the proof template for the near-optimal $K$-block allocation and the fine-partition argument.","marker":"[Wai26]"}],"fun_headline_variants":["Unmasking complexity certifies optimal diffusion schedules","Geometry of masking diffusion: certified-optimal samplers","Path-resolved geometry sharpens masking diffusion bounds","Unmasking growth complexity controls KL error in diffusion","Certified-optimal masking from data geometry"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The certificate in Theorem 2 requires a known finite moment bound $B_\\alpha$ on the aggregate KL changes of the exact one-coordinate Bayes denoisers over each reveal-odds dyadic interval, together with access to those exact denoisers; if the denoisers are learned, an extra approximation term enters the KL bound and is not certified.","fun_headline_variants_meta":{"raw":{"variants":["Unmasking complexity certifies optimal diffusion schedules","Geometry of masking diffusion: certified-optimal samplers","Path-resolved geometry sharpens masking diffusion bounds","Unmasking growth complexity controls KL error in diffusion","Certified-optimal masking from data geometry"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000233,"raw_usage":{"total_tokens":1578,"prompt_tokens":1118,"completion_tokens":460,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":734,"completion_tokens_details":{"reasoning_tokens":387}},"tokens_in":734,"tokens_out":460,"duration_ms":4861,"temperature":1.0,"reasoning_tokens":387,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T05:11:58.479914+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run the certified $K$-block procedure on the noisy repeated-bit ensemble with known UGC density, compute the true $H(p,q)$ exactly, and compare it with the truncated estimator $\\hat{H}_m(p,q)$ over many sample sizes; the factor-two sandwich of Proposition 2 would be falsified if the estimate plus confidence radius fails to contain $H(p,q)$ at a rate exceeding the chosen $\\eta$ for some distribution satisfying the moment condition (33a).","supporting_citations":[],"review_version":1}