# Dependence-Adaptive Timestep Controller

- ID: 104
- Canonical URL: https://synthcore.org/idea/104/dependence-adaptive-timestep-controller
- API JSON: https://synthcore.org/api/idea/104.json
- API Markdown: https://synthcore.org/api/idea/104.md
- Verification status: mechanism_failed
- Source: [arXiv:2608.23554](https://arxiv.org/abs/2608.23554)
- Category: sampling
- Solves: speedup, sample-efficiency, accuracy
- ML areas: diffusion-sampling, transformer, inference-speedup, training-dynamics
- Math tags: information-theory, probability, statistics, stochastic-processes
- Ratings: usefulness 7/10; difficulty 4/10; novelty 8/10

## Idea description

Use an online estimate of the target distribution's remaining coordinate dependence to choose diffusion step sizes instead of using a uniform timestep grid. Take large jumps when the current state is nearly coordinate-factorized and shorten the step when the denoiser detects strong cross-coordinate dependence, targeting the paper's dependence-adaptive discretization scaling.

## Mathematical statement

The paper measures intrinsic dependence with dual total correlation \(\mathrm{DTC}(X_0)=H(X_0)-\sum_{i=1}^{d}H(X_0^i\mid X_0^{-i})\), where \(H\) is Shannon entropy, \(X_0^i\) is coordinate \(i\), and \(X_0^{-i}\) denotes all other coordinates. The main guarantee states, up to logarithmic factors and score-estimation error, that \(N=O(\mathrm{DTC}(X_0)/\varepsilon)\) discretization steps achieve sampling error \(O(\varepsilon_{\mathrm{score}}+\varepsilon)\). A practical local proxy is the sum of differences between leave-one-out and ordinary conditional entropies: \(D_\theta(x_t)=\sum_i[H(q_i(\cdot\mid x_t^{-i}))-H(q_i(\cdot\mid x_t))]\), where \(q_i\) is the denoiser's categorical clean-token distribution and \(H(q)=-\sum_bq(b)\log q(b)\). This proxy is not claimed to be an unbiased estimator of population DTC; it is an online risk signal for selecting step sizes.

## Key formulas

- $$\mathrm{DTC}(X_0)=H(X_0)-\sum_{i=1}^{d}H(X_0^i\mid X_0^{-i})=\sum_{i=1}^{d}H(X_0^{-i})-(d-1)H(X_0).$$
- $$N=\widetilde O\!\left(\frac{\mathrm{DTC}(X_0)}{\varepsilon}\right),\qquad \text{sampling error}=O(\varepsilon_{\mathrm{score}}+\varepsilon).$$
- $$D_\theta(x_t)=\sum_{i=1}^{d}\left[H\!\left(q_i(\cdot\mid x_t^{-i})\right)-H\!\left(q_i(\cdot\mid x_t)\right)\right],\qquad H(q)=-\sum_bq(b)\log q(b).$$
- $$\Delta_t=\operatorname{clip}\!\left(\Delta_{\max}\sqrt{\frac{\tau}{D_\theta(x_t)+\delta}},\Delta_{\min},\Delta_{\max}\right).$$

## Implementation notes

Integrate this into the inference scheduler of a discrete diffusion model. Maintain continuous diffusion time t and a remaining error budget epsilon. At the current state x_t, run the denoiser and obtain per-position clean-token distributions q_i(b|x_t^{-i}); obtain a second set of logits q_i(b|x_t) from the ordinary full-context output or from a cached non-leave-one-out head. Compute each categorical entropy as H(q_i)=-sum_b q_i(b)log q_i(b), then calculate D_theta as the batch mean of the entropy difference in the displayed formula. Select Delta_t with the square-root controller, clipping it between Delta_min and Delta_max. A robust initial variant should smooth D_theta with an exponential moving average and limit successive step-size ratios to at most 2. Apply the corrective transition over [t-Delta_t,t], then recompute the proxy at the new state. The paper supplies the DTC-to-step-count motivation and the target error scaling; tau, clipping limits, smoothing coefficient, and whether the entropy difference should be summed or averaged must be calibrated empirically. First test on independent tokens, block-correlated binary tokens, and the two-string distribution {0^d,1^d}, where ambient dimension and intrinsic dependence can be separated. Then test a small masked language model on WikiText-103. Compare against 50- and 100-step uniform schedules and an entropy-only adaptive baseline. The expected signal is fewer Transformer evaluations at matched perplexity or total-variation error, with the largest gains on high-dimensional low-dependence data. Log D_theta and Delta_t to verify that the controller takes larger steps when cross-coordinate dependence is weak.

## Verification

- Status: mechanism_failed
- Mechanism evidence: yes
- Mechanism confirmed: no
- Verdict: Built a cached exact-conditional synthetic discrete-diffusion MVP with uniform, dependence-adaptive, and entropy-only schedules, plus numerical checks for proxy nonnegativity and controller monotonicity. The controller reduced evaluations from 8 to 5, but substantially worsened TV error on correlated pairs (0.1122 to 0.2775) and the two-string target (0.0020 to 0.7840), so the promised accuracy-preserving speedup was not observed. The algebraic controller check passed, but this proxy and calibration were not effective for sampling accuracy.

### Mechanism check

- Verdict: Built a cached exact-conditional synthetic discrete-diffusion MVP with uniform, dependence-adaptive, and entropy-only schedules, plus numerical checks for proxy nonnegativity and controller monotonicity. The controller reduced evaluations from 8 to 5, but substantially worsened TV error on correlated pairs (0.1122 to 0.2775) and the two-string target (0.0020 to 0.7840), so the promised accuracy-preserving speedup was not observed. The algebraic controller check passed, but this proxy and calibration were not effective for sampling accuracy.
- Confidence: 9/10
- Limitations: Only a small exact binary synthetic benchmark was tested; no trained neural denoiser, WikiText-103, matched 50-versus-100-step study, wall-clock profiling, score-estimation error, or rigorous paper sampler was implemented. The toy sampler uses a uniform fallback for off-support states, which is especially problematic for the two-string distribution, and the observed-coordinate entropy proxy is not a faithful population DTC estimator.

## Artifacts

- [experiment.py](https://synthcore.org/code/38/experiment.py)
- [report.md](https://synthcore.org/code/38/report.md)
- [Download all files as ZIP](https://synthcore.org/download/38)

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.