How Many Particles Is a Bit Worth? Tail-Index Extrapolation of Importance-Weighted Compression Rates

Some of the best lossless compressors built on latent-variable models pay a bitrate equal to the importance-weighted autoencoder (IWAE) loss. The IWAE loss is a bound on the log-likelihood computed by averaging $N$ random "importance weights," one per sampled guess of the hidden code. As $N$ grows, the bitrate approaches the ideal $-\log p(x)$. Every extra particle costs compute, though, and nobody can say in advance how much a larger $N$ will save. We propose to predict the whole curve of bitrate against particle count from a small pilot run.

The key observation is that how fast this curve falls is set by one number: how heavy the right tail of the importance weights is. That is the tail index that extreme value statistics is built to estimate. When the weights have finite variance, the gap to the ideal rate shrinks like $1/N$. When the tail is heavy, which is common, the gap shrinks much more slowly, at a rate fixed by the tail index. We borrow the classical way extreme value theory projects from moderate to extreme probability levels, and use it to project from a few hundred particles to hundreds of thousands. That projection tells a compressor, for each data point, whether more particles are worth buying.

Core Claim

Let $w = p(x,z)/q(z\mid x)$ be an importance weight. Here $p(x,z)$ is the model's joint density and $q$ is the encoder that proposes latent codes $z$. Let $\hat Z_N$ be the mean of $N$ such weights, so that the expected coding cost of bits-back importance sampling is $-\mathbb{E}\log \hat Z_N$, as shown in Importance weighted compression and Improving Lossless Compression Rates via Monte Carlo Bits-Back Coding. Define the excess rate $G_N = \log p(x) - \mathbb{E}\log\hat Z_N$.

Suppose the weight tail behaves like a Generalized Pareto distribution with shape $k$, the same quantity Pareto Smoothed Importance Sampling uses as a reliability diagnostic. We claim that for $1/2 < k < 1$,

$$G_N \approx C\, N^{-(1-k)},$$

where $C$ depends on $x$ and on the encoder. The form follows from a simple argument. A typical sample of $N$ weights has its largest value near $N^{k}$, so it misses the probability mass above that level. That missing mass scales as $N^{k-1}$ when the tail decays like $t^{-1/k}$. For $k<1/2$ the variance is finite, and the $1/N$ delta-method rate used in Debiasing Evidence Approximations takes over.

The practical consequence is a projection analogous to the Weissman extrapolation of extreme quantiles. From a pilot run of $K$ particles we estimate $\hat k$ from the top order statistics of the weights, then fit $C$ from differences of subsampled IWAE values, which are observable without knowing $\log p(x)$. We then predict

$$\hat G_{N} = \hat G_K\,(K/N)^{1-\hat k}\quad\text{for } N \gg K.$$

The limit $N\to\infty$ yields a log-likelihood estimate as a by-product. The novelty lies in three pieces together. We treat the IWAE rate curve as an object of intermediate-to-extreme extrapolation. We use its tail-driven exponent to allocate particles in a real bits-back coder. And we quantify how errors in $\hat k$ propagate into bitrate predictions.

Research Program

The first strand is theory and characterization. We will verify the $N^{-(1-k)}$ law on synthetic weights with exact Pareto and Student-$t$ tails, and on linear-Gaussian latent models, where $\log p(x)$ is known in closed form. We will then measure $\hat k$ across trained variational autoencoders on binarized MNIST at several training checkpoints, and with the encoder variance deliberately shrunk or inflated, so that $k$ spans roughly 0.2 to 0.9. The file notes that nobody has characterized the tail index of weights inside bits-back pipelines (Gap 1), so this map is itself a deliverable.

The second strand is sensitivity, which the tail-estimation literature warns is where things break. Under the projection above, an error $\Delta k$ multiplies the predicted gap by $(N/K)^{\Delta k}$. Extrapolating a thousandfold with $\Delta k = 0.1$ therefore doubles the error. This mirrors how tail-index errors amplify extreme risk measures in Extreme versions of Wang risk measures and in the dependence of the optimal loss power on $\gamma$ in Extreme M-quantiles as risk measures.

We will compare three tail estimators. The first is the Hill estimator with its threshold dilemma, as discussed in Experimental Evidence for Heavy Tailed Interference in the IoT. The second is the Generalized Pareto fit using the tail-size rule from Pareto smoothed importance sampling. The third is the block-maxima regression of Estimating Heavy-Tail Exponents Through Max Self-Similarity, which estimates the index from how block maxima grow with block size. That estimator is attractive here because weights arrive in streams, and on the natural gas reserves data it gave $\alpha = 1.284$ where Hill gave $0.826$, a disagreement large enough to matter in our projection. Bootstrap intervals over the pilot particles will turn each estimator's uncertainty into an interval on predicted bits.

The third strand is the coder. Inside the McBits codebase (ryoungj/mcbits) we will add a pilot stage that predicts each datapoint's rate curve. The coder then picks $N$ to minimize predicted rate plus the $O(\log N)$ seed-bit overhead of coupled importance sampling, subject to a compute budget. Because $N$ must be known to the decoder, the chosen $N$ is transmitted with a small header, and the pilot uses shared randomness so decodability is untouched. This sidesteps the reversibility problem that blocks smoothing weights inside the coder (Gap 2). We never alter the weights; we only decide how many to draw. The rule also gives a diagnostic: when $\hat k$ is near 1, extra particles are nearly useless, and the right move is to improve the encoder.

Baselines

The naive reference is to do no extrapolation. We report the pilot IWAE value at $K$ as the rate estimate and use a fixed $N$ for every datapoint, as McBits does. Beating it means a lower error in predicted bits at the target $N$, and a lower net bitrate at equal total compute.

The strongest existing compression system is fixed-$N$ bits-back importance sampling from Improving Lossless Compression Rates via Monte Carlo Bits-Back Coding. It reports "between 2% and 19% bitrate savings over standard bits-back" across MNIST, EMNIST and CIFAR-10, and a 9.7% saving over the standard evidence-bound coder with 50 particles on EMNIST Letters under an MNIST-trained model. The absolute reference is BB-ANS at 0.19 bits/dim on binarized MNIST, from Practical lossless compression with latent variables using bits back coding. We rerun McBits with its own code, models and the same total particle budget. Adaptive allocation must beat the best single fixed $N$ at matched average compute, including pilot and header costs.

For log-likelihood estimation, the strongest competitors are Pareto-smoothed importance sampling applied to the weights, and Jackknife Variational Inference from Debiasing Evidence Approximations, which cancels the $1/K$ bias term. No reported result was found on Lacuna for either method's accuracy at predicting IWAE values at large particle counts. Pareto smoothed importance sampling reports no RMSE numbers in the file, and the Jackknife paper reports only plots. All methods receive the identical $K$ pilot weights per datapoint. Thresholds and subsample schedules are tuned on validation datapoints, never on test.

The ablation that isolates our key ingredient replaces the tail-pinned exponent $1-\hat k$ in two ways. One version fixes the exponent at 1, the light-tail assumption. The other fits it freely from the subsample curve. If the pinned exponent is not better than both in the heavy-tail regime ($\hat k > 1/2$), the core claim fails.

Why not just…?

Why not just increase $N$ until the rate stops improving? That is our ground truth, and it is exactly what is too costly to do everywhere. Importance weighted compression reports that the useful $N$ for deep lossy models is "too large to be practically feasible," and McBits costs $O(N)$ per datapoint. Stopping when the curve flattens is also misleading under heavy tails. A curve decaying like $N^{-0.2}$ looks flat locally while still hiding a sizeable gap. The end-to-end experiment below compares against "grow $N$ until the improvement falls below a tolerance" at matched compute.

Why not just use the Jackknife to remove the bias? Its expansion assumes the $1/K$ series exists, which requires finite variance. For $k>1/2$ the leading term is $K^{-(1-k)}$, and the Jackknife's polynomial combinations target the wrong exponent while amplifying noise. We expect it to be competitive for $k<1/2$ and to fail above. The stratified results by $\hat k$ will show where the crossover lies.

Why not just fit a power law to the IWAE-versus-$K$ curve from subsamples, with no extreme value theory? This is the real threat. A free fit of $a + bK^{-c}$ may recover the right exponent without any tail estimator. Our bet is that the exponent from the subsample curve is far noisier than one read off the top order statistics, because curve differences shrink as $K$ grows. That noise matters, since exponent error is amplified by $(N/K)^{\Delta c}$. The ablation settles this directly. If the free fit matches us, the contribution shrinks to the explanation and the $\hat k$ diagnostic, and we will say so.

Why not just use Pareto smoothed importance sampling to estimate $\log p(x)$? It targets the infinite-$N$ limit. The coder pays the finite-$N$ rate, and choosing $N$ needs the whole curve. We report it as a baseline for the limit, where our estimator is close in spirit.

Proposed Experiments

The synthetic checks come first. On exact Pareto weights and linear-Gaussian latent models, the fitted exponent should track $1-k$ for $k\in(0.5,1)$, and the prediction from $K=256$ should hit the true gap at $N=10^5$ within bootstrap intervals. The main test uses binarized MNIST VAEs across checkpoints and encoder perturbations. We run $10^5$ to $10^6$ particles on a few hundred test images as ground truth, fit on $K\in\{64,256,1024\}$, and score the absolute error in predicted bits/dim at each target $N$, stratified by $\hat k$. We also score interval coverage, which the tail literature warns degrades at moderate sample sizes. The same protocol on EMNIST Letters under an MNIST model probes the out-of-distribution regime, where we expect heavier weight tails.

The decisive check has two parts. First, in the $\hat k>1/2$ stratum the tail-pinned projection must beat the no-extrapolation reference, the $1/N$ ablation, the free-exponent fit and the Jackknife on prediction error. Second, adaptive per-datapoint $N$ in the McBits coder must lower net bits/dim below the best fixed $N$ at equal compute on MNIST and EMNIST. If the tail index measured on real models sits below 1/2, the heavy-tail mechanism is irrelevant, and the honest outcome is a negative result.