Generative imputers fill in missing table entries by sampling from a learned model of the joint distribution. A diffusion model, which is a generator that learns to turn random noise into data by gradually denoising it, is a typical choice. These imputers currently spend the same compute on every row. A row missing one easily predicted column gets the same 50 denoising steps and EM rounds as a row missing most of its features. Meanwhile, a strong empirical result says that for many tables, filling missing values with zeros is about as good as anything else downstream. Both facts suggest the same thing: most rows probably need almost no generative effort, and a few need a lot. Nobody has measured how that need is distributed, or built an imputer that acts on it.
We propose a compute ladder for imputation. Each row starts at the cheapest rung: mean or zero fill. From there it can move up to a single-pass masked model, then a few-step diffusion sampler, then the full iterative diffusion imputer with multiple posterior samples. A small probe reads the cheap model's internal state for that row and decides whether climbing further would change the answer. The probe is trained without ground truth. Its target is whether the cheap imputation agrees with what the full-budget imputer would output on the entries that are actually missing. A calibration step then sets the probe's thresholds so that, with stated probability, early stopping deviates from the full-budget answer by no more than a user-chosen tolerance. The claim is that this matches the full imputer's accuracy at a fraction of its compute. A second claim is that it beats the obvious rule of "spend more when more is missing," because how hard a row is to impute depends on which features are missing and how predictable they are, not on how many.
Core Claim
Difficulty in imputation is a property of the conditional posterior $P(X_{\text{mis}} \mid X_{\text{obs}})$, the distribution over a row's missing values given its observed ones. A row is easy when this posterior is sharp and a cheap estimate already sits at its mean. A row is hard when the posterior is broad, multimodal, or poorly approximated by one forward pass. We claim three things. First, this difficulty is readable from the representation a cheap masked model builds for the row. Second, a probe that predicts "agreement with the full-budget imputer" can be calibrated to give distribution-free control of the deviation from that imputer. Third, the resulting accuracy-versus-compute curve dominates both uniform step reduction and missingness-fraction heuristics on standard tabular benchmarks.
Let $\hat{x}^{(k)}$ denote the imputation of a row's missing entries at rung $k$, and let $\hat{x}^{(K)}$ be the full-budget output. Define the deviation $d_k = \lVert \hat{x}^{(k)} - \hat{x}^{(K)} \rVert / \sqrt{m}$, where $m$ is the number of missing entries and features are standardized. Categorical columns contribute through a mismatch indicator instead of the norm. The probe outputs a score $s_k$, and the row stops at the first rung where $s_k \ge \lambda_k$. We choose the thresholds $\lambda$ on held-out calibration rows so that
$$ \Pr\big(d_{k^\ast} > \epsilon\big) \le \alpha , $$
where $k^\ast$ is the rung at which the row stops, $\epsilon$ is the tolerated deviation, and $\alpha$ is the tolerated failure rate. The guarantee is inherited from the Learn-then-Test procedure and holds when calibration and test rows are exchangeable.
Where this sits
The idea takes its method from the adaptive test-time compute literature for language models. Thought calibration trains probes on a reasoning model's hidden states and calibrates stopping thresholds with Learn then Test. Its key finding is the one we rely on: a self-supervised probe predicting agreement with the model's own full-budget answer transfers out of distribution better than a probe trained on correctness. We port that target to imputation, where it has an extra advantage. It is defined on the truly missing entries and needs no ground truth. Learning How Hard to Think predicts the marginal gain from extra samples using hidden states. The LLM Already Knows shows that a model's state before it generates anything already separates easy from hard inputs (93.09% ROC-AUC on ScienceQA). Both motivate reading difficulty from an early representation. Both also need verifiable rewards, and our agreement target removes that need. Escape Sky-high Cost stops sampling once a window of answers agrees. That paper also flags the failure mode we must guard against: consistent wrong answers lock in early. We treat its window-agreement rule as a baseline applied to parallel imputation chains.
The imputers supply the rungs. DiffPuter wraps a diffusion model in EM and uses a fixed $M=50$ sampling steps per E-step over 4–5 iterations. It is our top rung and the strongest accuracy reference. Masked-attention imputers such as CACTI do one forward pass per row, and they train on copied real missingness patterns. This gives us the cheap rung whose internal state the probe reads. TabNAT shows that a bidirectional transformer can condition a diffusion head on arbitrary observed subsets, which supports sharing one encoder across rungs.
Two papers constrain the design. In Defense of Zero Imputation for Tabular Deep Learning finds that an MLP with zero imputation matches deep impute-then-predict models on OpenML tables. We do not argue against this. We include zero fill as rung zero and treat "what fraction of rows ever leave rung zero" as a primary measurement. Score Matching with Missing Data shows that zero imputation breaks density estimation (its "zeroing trap"). This is why we judge the ladder by reconstruction and distributional fidelity, not only downstream prediction.
The closest boundary work adapts things other than compute. SaSDim adapts noise scale and AdaSTI adapts graph dependencies, but both run uniform sampling. Adaptive Linear Path Model-Based Diffusion does vary step count per input, using a reinforcement learning controller, but for robot control and with no missing data. Its weaker result on the high-dimensional Pusher task is a warning that changing the sampler to enable adaptivity can cost expressiveness. We avoid the issue by never changing the top-rung sampler; only how far a row climbs changes.
Research Program
We first build the ladder on each benchmark table. Rung 0 is mean/zero fill. Rung 1 is a masked-attention autoencoder trained with copy masking. Rung 2 is DiffPuter's trained denoiser run with 5 and then 15 steps from a rung-1 initialization. Rung 3 is full DiffPuter with 50 steps, its EM iterations, and $S$ posterior samples averaged. All rungs above 0 share the DiffPuter-trained denoiser where possible, so the ladder adds only the rung-1 model and the probe to training cost.
Second, we label probe targets without ground truth. For training rows with real or simulated missingness, we run every rung and record $d_k$ on the missing entries. The probe is a two-layer MLP on the rung-1 encoder's pooled state, concatenated with the missingness mask. It predicts $\Pr(d_k \le \epsilon)$ for each $k$. As a contrasting variant we train a "re-masking" probe. That probe hides extra observed entries and predicts true reconstruction error on them. It has real labels but a known flaw under MNAR, where hidden observed entries are not distributed like truly missing ones. Comparing the two variants is a scientific question in its own right.
Third, we calibrate thresholds with Learn then Test on held-out rows, at several $(\epsilon, \alpha)$ pairs, and verify empirical coverage on test rows.
Fourth, we analyze what predicts difficulty. We regress $d_1$ on missing fraction, on the identity of the missing columns, and on the conditional predictability of missing columns given observed ones. This tests the core claim that count of missing values is a poor proxy.
Baselines
The naive reference point is zero imputation with missingness indicators, fed to the same downstream MLP. This follows In Defense of Zero Imputation. It costs essentially nothing, and on downstream AUC it is the bar that every generative method must justify itself against. We report it on both reconstruction error and downstream AUC. Beating it on downstream AUC is not required. The ladder must instead show that it matches zero fill's downstream score while retaining DiffPuter-level reconstruction.
The strongest existing method is full DiffPuter at its published settings. The file reports only aggregate results for it: an average 8.10% MAE and 5.64% RMSE improvement over competitive baselines across its 10 datasets. No per-dataset numbers were found on Lacuna, so we rerun it ourselves on every table with its published hyperparameters and our seeds. This is the rung-3 reference. The ladder "beats" it if it stays within the calibrated $\epsilon$ on at least $1-\alpha$ of rows, with test MAE within one standard error across seeds, at no more than 40% of DiffPuter's mean denoiser evaluations per row. For mixed-type tables we also report CACTI. Its reported average gain is 7.8% in $R^2$ (13.4% under MNAR), with no per-dataset figures found on Lacuna. For categorical error we refer to HI-VAE's reported 0.304 on Adult at 20% MCAR (Handling Incomplete Heterogeneous Data using VAEs).
Three compute-matched baselines isolate the key ingredient. The first is uniform reduction: every row gets the same reduced number of steps and samples, chosen so the average compute equals the ladder's. The second is a missing-fraction rule: rows climb rungs in proportion to the fraction of entries missing, with average compute again matched. The third is window agreement in the style of ESC across parallel posterior chains, stopping when $w$ consecutive samples agree within $\epsilon$. Two further ablations remove the probe's state input (mask only) and swap the agreement target for the re-masking target. All methods use the same trained denoiser, the same data splits, the same calibration rows, and an equal hyperparameter search budget. Compute is reported as denoiser function evaluations and as wall-clock time on fixed hardware.
Why not just…?
Why not just run fewer diffusion steps for everyone? If a uniformly reduced sampler sits at DiffPuter's accuracy, adaptivity is pointless. Nothing in the file shows how DiffPuter degrades below 50 steps, so this is a real threat. The compute-matched uniform baseline settles it directly. If the per-row deviation $d_k$ turns out nearly identical across rows at a given step count, we will report that and drop the adaptive claim. Our expectation of a heavy tail rests on the logic of the posterior: rows whose missing columns are near-deterministic given observed ones should converge in one pass.
Why not just allocate by how many entries are missing? This is the simplest adaptive rule, and the file contains no evidence for or against it in imputation. The difficulty-attribution analysis and the compute-matched missing-fraction baseline test it head on. If it matches the learned probe, the honest contribution shrinks to "a calibrated version of the count rule." We would still keep the Learn-then-Test thresholds, since a count rule alone gives no deviation guarantee.
Why not just zero-impute, as Van Ness et al. recommend? For downstream classification on their OpenML tables, zero fill may genuinely suffice, and the ladder is built to discover exactly that, by letting most rows stop at rung 0. Zero fill fails when the imputed values themselves matter: density estimation (Score Matching with Missing Data), reconstruction, and multiple-imputation uncertainty. The ladder's job is to keep that fidelity while paying close to zero-fill cost.
Why not just stop when parallel chains agree? ESC-style agreement needs at least $w$ full-cost samples before it can stop, so it cannot save the first sample's cost. It also locks in consistent errors, as its authors note. The ladder probe decides before any diffusion runs. We still run the agreement rule as a baseline, and as a possible top-rung stopping rule if it proves complementary.
Proposed Experiments
We use the continuous and mixed UCI tables shared by DiffPuter and CACTI: California Housing, Magic, Letter, Gesture, Dry Bean, Adult, Default of Credit Card Clients, Online Shoppers, and Online News. We also use the OpenML tables from Van Ness et al. (higgs, miniboone, phoneme, volkert). Missingness is MCAR, MAR, and self-masking MNAR at 10–70%. The primary output is the Pareto curve of test MAE/RMSE (categorical error for discrete columns) against mean denoiser evaluations per row, plus downstream AUC from a fixed MLP trained on each method's imputations.
There are four decisive checks. The first is whether the ladder's curve dominates the uniform-reduction and missing-fraction curves at matched compute on most tables. The second is whether empirical coverage of the $\Pr(d > \epsilon) \le \alpha$ guarantee holds on test rows under MCAR and MAR. The third is whether, under MNAR, the agreement-target probe keeps coverage while the re-masking probe loses it; that is the predicted signature of re-masking bias. The fourth is the share of rows that stop at each rung, reported per table. A large rung-0 share on OpenML tables but not on the UCI tables would turn the zero-imputation paradox into a measurable, per-row statement of when generative imputation pays.
References
- Thought calibration: Efficient and confident test-time scaling
- Learning How Hard to Think: Input-Adaptive Allocation of LM Computation
- The LLM Already Knows: Estimating LLM-Perceived Question Difficulty via Hidden Representations
- Escape Sky-high Cost: Early-stopping Self-Consistency for Multi-step Reasoning
- DiffPuter: Empowering Diffusion Models for Missing Data Imputation
- CACTI: Leveraging Copy Masking and Contextual Information to Improve Tabular Data Imputation
- TabNAT: A Continuous-Discrete Joint Generative Framework for Tabular Data
- In Defense of Zero Imputation for Tabular Deep Learning
- Score Matching with Missing Data
- SaSDim: Self-Adaptive Noise Scaling Diffusion Model for Spatial Time Series Imputation
- AdaSTI: Conditional Diffusion Models with Adaptive Dependency Modeling for Spatio-Temporal Imputation
- Adaptive Linear Path Model-Based Diffusion
- Handling incomplete heterogeneous data using VAEs