CS Paper Radar

Counterfactual Probing for Parallel Unmasking with Hidden Forest Structure

Ryotaro Kawata, Satoshi Hayakawa, Taiji Suzuki

cs.LG stat.ML ·submitted 2026-09-29 15:39 UTC · v2
theory

Abstract

Masked generative models offer parallel token prediction, but accurate parallel sampling must account for dependencies among tokens. When dependencies are unknown, finding safe batches also costs model evaluations. We study whether total evaluations, including discovery, can be sublinear in sequence length $N$; sublinear sequential depth then follows. We consider discrete distributions with hidden forest structure, accessed through a fixed approximate conditional oracle. Under explicit regularity conditions and uniform Hellinger error bounds, for any fixed target accuracy $\varepsilon\in(0,1/8]$ and sufficiently large $N$, our sampler achieves seed-averaged total-variation error at most $\varepsilon$, with total masked-state submissions and sequential depth both bounded by $\widetilde{O}(N^C \varepsilon^{-a})$ for constants $0<C<1$ and $a>0$. These guarantees use polynomial vocabulary size and an edge-response lower bound set by $N$ and $\varepsilon$. The sampler shares evaluations of hypothetical reveals across dependence tests to identify safe parallel batches without requiring full recovery of the hidden forest. A tunable parameter trades probing cost against irreversible commit rounds. In the same class, any admissible irreversible product-commit sampler attaining the same seed-averaged accuracy requires $Ω(N^c \varepsilon^b)$ counterfactual submissions or commit rounds in the worst case, for constants $c,b>0$.

Closest papers

Nearest neighbours by meaning across the whole index.

The Price of Not Planning: Parallel Sampling Depth Peaks at the Reconstruction Threshold

cs.LG ·2026-11-16 ·Chuling Wen, Weijie Liang, Jian Lu
similarity 0.65
Abstract

Masked diffusion models sample the tokens of one round independently. Planned decoders first generate a coarse plan, then fill in the tokens in parallel. We ask when a plan saves rounds, how many it saves, and how fine it must be. We study this on broadcast trees: the leaves are the tokens, the internal nodes are the plan, and the edge correlation $θ$ sets how strongly tokens depend on the plan. Errors are measured by the forward Kullback-Leibler divergence $\varepsilon$, and the lower bounds hold for every deterministic value-adaptive rule, also with learned conditionals. We show that a decoder without the plan needs of order $\min\{n,(n/\varepsilon)^α\}$ rounds below the reconstruction threshold, where $α=\log b/(4\log(1/θ))$ rises to $1/2$ at the threshold, and that the exponent stays below $1/2$ above it (binary channel: $0.02\leθ\le0.98$). With the plan, $\log_b n+1$ rounds suffice. In the binary model below the threshold, a plan with units of $m$ tokens needs of order $\log_b(n/m)+\min\{m,(n/\varepsilon)^α\}$ rounds, so it gives logarithmic depth exactly when $m$ is logarithmic. A plan therefore helps most near the threshold, and only if its units are small. Exact divergence computations in the Gaussian model with up to $2^{20}$ leaves confirm these exponents below the threshold.

0.08

Serial Depth of Adaptive Parallel Sampling: Lower Bounds and Schedules for Masked Diffusion Models

cs.IT cs.CL ·2026-08-26 ·Chuling Wen, Weijie Liang, Jian Lu, Zhouchen Lin
theoryhighly cited similarity 0.64
Abstract · 45 pages. Revised version with a new title

Masked diffusion models generate sequences in rounds, predicting several masked positions at once. Fewer rounds can accelerate decoding, but sampling positions independently can lose their dependence and bias the output. How few rounds suffice for a prescribed error budget? Beyond error bounds for individual decoding rules, we study sharp lower bounds on the number of rounds required for a given target distribution. We introduce serial depth: the minimum number of rounds, averaged over target sequences, needed to meet a forward Kullback-Leibler error budget. With exact conditional probabilities, we prove these bounds for all deterministic rules that may adapt to generated values and construct matching schedules for several distribution families, with depths ranging from $\log\log n$ to linear in sequence length $n$. To narrow the gap to trained models, we show that these lower bounds remain valid for learned predictors and give sufficient accuracy conditions on visited contexts for schedules to retain their error guarantees. On two pretrained models across five text domains, a schedule suggested by the theory achieves higher average log-likelihood on held-out text in five rounds than random selection in eight. A preregistered confirmation study certifies a relative improvement on independent dialogue data.

0.49

Transformer-Based Masked Diffusion Models Provably Learn Distributions with Latent Structure

cs.LG cs.ITmath.STstat.ML ·2026-10-08 ·Jingda Wu, Changxiao Cai
similarity 0.62
Abstract

Masked diffusion models (MDMs) generate discrete data by iteratively unmasking multiple tokens in parallel using a learned mask predictor. Their output carries two errors: parallelization error due to parallel sampling, and estimation error from the mask predictor learned with finite samples. Existing theory treats these errors separately, and the available statistical bounds typically scale with the number $V^L$ of length-$L$ sequences over a vocabulary of size $V$, suffering from the curse of dimensionality. In this work, we establish end-to-end statistical guarantees showing that transformer-based MDMs learn structured distributions with a sample complexity governed by their latent structure. Specifically, we model this structure through mixtures of hidden Markov trees, which capture latent dependencies within components and heterogeneity across components. When the data distribution is well approximated by such a mixture, a transformer-based MDM with parallel unmasking schedules achieves $\varepsilon$-accurate sampling in KL divergence with $\widetilde{O}(LK_{\mathrm{par}}/\varepsilon)$ training samples, where $K_{\mathrm{par}}$ is polynomial in $L$, $V$, the number of hidden states, and the number of mixture components. The transformer network and sampling procedure require no knowledge of the tree topologies or component parameters, thereby adapting to the unknown latent structure automatically. Overall, our results provide theoretical justification for the empirical effectiveness of MDMs on real-world data.

0.42

Randomization Beyond Deterministic Adaptivity in Parallel Sampling

cs.IT ·2026-10-02 ·Da Li, Bo Jin, Xiaopeng Wei
highly cited similarity 0.62
Abstract · 20 pages

Parallel samplers, including masked diffusion models, generate several coordinates per round from conditional marginals, and their accuracy depends on which coordinates are revealed together. A schedule can be improved in two natural ways: adaptively, by choosing later batches from the values already generated, or by randomization, by drawing the schedule at random. We show that randomization is strictly more powerful. For every $r \geq 1$ we construct a full-support distribution on $9r$ binary coordinates such that every deterministic three-round sampler, even with value-dependent batches and arbitrary product kernels, has forward Kullback-Leibler divergence at least $γr - \log 4$ with $γ\approx 0.0966$, whereas drawing one of four fixed schedules with two fair bits drives the divergence below $18 r β^r$ with $β\approx 0.966$. Both samplers query conditionals of the same target. The separation holds for every fixed number of rounds $T \geq 2$, a strict advantage survives perturbations of the target and errors in the conditional predictor, and exact rational arithmetic certifies the gap at nine coordinates, where trained neural predictors preserve it. The mechanism is a hidden mixture: each schedule preserves the dependence pattern of one component, while no deterministic first batch can serve them all.

0.48

Canopy: Exploiting Piecewise Smooth Tree Priors for Multi-Fidelity Bandits

cs.LG cs.AI ·2026-09-24 ·Michael Jerge, Suman Jana
theory similarity 0.60
Abstract

Many LLM inference problems, including model routing, prefix-cache management, prompt trimming, and test-time search, can be viewed as optimization over a tree. This structure arises naturally from autoregressive generation: every prefix defines a node, and its continuations form a subtree below it. Internal nodes of the tree provide cheap but biased estimates of a region's value, while leaf evaluations are expensive but accurate. Hierarchical bandit methods can exploit this structure, but typically require a specific smoothness schedule to be specified in advance, even though real objectives are often only piecewise smooth and their optima may lie near sharp boundaries. We introduce CANOPY, a multi-fidelity tree bandit that learns where the smoothness prior is valid rather than assuming it globally. CANOPY uses cheap random-path probes to construct an online certificate of local aggregation bias, then directs expensive leaf evaluations toward cells where the certificate detects a smoothness violation. We prove fixed-budget and regret guarantees whose additional cost is additive in the number of discontinuities, recovering the smooth-tree rate when no violations are present and approaching structure-blind search as violations become dense. Across routing, top-$k$ identification, test-time search, caching, and prompt trimming, CANOPY consistently improves matched-budget performance, including $2.9\times$ higher top-10 recall on a 1000-model pool, $1.6\times$ more SWE-bench Verified issues resolved than best-of-$N$, and $3.6\times$ lower median time-to-first-token with prefix caching.

0.17

Beyond Parallel Blindness: Information Floors and Model Gaps in Block Drafting

cs.LG cs.CLcs.IT ·2026-08-27 ·Xinwei Qiang, Xiang Fang, Chang Chen, Zaifeng Pan, Yue Guan +1 more
code/data similarity 0.60
Abstract

Block drafters propose several tokens in one forward pass, before earlier target tokens are realised. Their rejection mixes two losses: missing within-block path information and imperfect modelling of observable information. Accepted length cannot distinguish them. We separate the two with an information floor, the minimum expected rejection at a specified conditioning order; rejection above this floor is the model gap. Measurements across four domains and four open-weight targets, plus floor estimates on a frontier API target, yield three findings. First, the all-parallel floor reaches $0.286$ at the final slot on Qwen3-4B, limiting even the best proposal to $71\%$ per-slot acceptance. Second, one realised token removes $86$--$100\%$ of this floor, a locality also recovered by an independent mutual-information analysis. Third, current drafters remain far above their floors: the final-slot model gap accounts for $43$--$64\%$ of DFlash rejection and $85$--$92\%$ of DSpark's oracle-conditioned rejection. Guided by this separation of short-range conditioning from proposal quality, we replace a context-independent predecessor correction with a prefix-attention head that reads committed context conditional on the predecessor. With supporting backbone components, the resulting Qwen3-4B drafter improves mean serving accepted length by $3.93\%$ over the released DSpark checkpoint across nine tasks, without increasing the conditioning order. Code and data: https://github.com/tie-pilot-qxw/specfloor; drafter checkpoints: https://huggingface.co/TIE-Pilot/dspark-attnconv-block7-qwen3-4b.

0.66

Fork-dLLM: Avoiding the Flexibility Trap in Diffusion Language Models

cs.LG ·2026-09-30 ·Stipe Frković, Metod Jazbec, Christian A. Naesseth
similarity 0.60
Abstract

Masked diffusion language models (dLLMs) have shown strong potential for faster inference through parallel token generation when combined with confidence-based samplers. However, recent work has shown that such methods can defer unmasking high-entropy fork positions at which multiple plausible continuations exist. This results in reduced generation diversity, as shown by worse pass@k scaling, and limits gains obtainable from RL post-training. To avoid this flexibility trap, prior work advocated for autoregressive (AR) sampling. Here, we show that discarding confidence-based sampling is unnecessary and, once inference cost is taken into account, wasteful. We first propose Fork-dLLM, a simple hybrid sampler that uses AR-style ordering only at uncertain fallback steps while retaining parallel generation otherwise. We then extend the same principle to post-training with ForkGRPO, which uses Fork-dLLM rollouts and applies the GRPO objective only at fallback steps, preserving exact policy-likelihood ratios while substantially reducing rollout and optimization cost. In our experiments, Fork-dLLM matches the strong pass@k scaling of AR sampling while being 2-3x more efficient, and ForkGRPO achieves downstream performance comparable to or better than AR-based GRPO baselines at a substantially lower training cost.

0.22

Query-Efficient Rejection Sampling for Parallel Masked Diffusion

cs.LG math.PRstat.ML ·2026-10-15 ·Shiyuan Zhang, Xuheng Li, Qiwei Di, Quanquan Gu
similarity 0.60
Abstract · 22 pages,2 figures

Masked diffusion models (MDMs) accelerate generation by unmasking multiple tokens in parallel, but sampling these tokens independently ignores their correlations and biases the output. Anari et al. (2026) corrected this bias with rejection sampling, decomposing the log acceptance probability into a sum of token-level terms, but the evaluation requires one score query per unmasked token. We propose the Single-Increment Rejection Sampler (SIRS), which provides an estimate of the log acceptance probability from a single randomly sampled increment at the cost of one query. SIRS then converts a Poisson number of clipped estimates into accept/reject decisions through a Bernoulli factory adapted from Chen et al. (2026). Since each query returns the conditionals of all remaining tokens in the block, we further Rao-Blackwellize each increment by averaging over these tokens at no extra cost, thereby reducing clipping. We show that the KL-divergence between the data distribution and the SIRS output is bounded by a clipping term plus the model's training error. With exact scores, parallel decoding pays the full within-block dependence, whereas SIRS pays only the part beyond the clipping range.

0.41