Total Variation Distance Estimation in Autoregressive Models

Modern LLM deployments use a number of implementation choices and inference optimizations (e.g., batching, custom kernels, quantization) on top of fixed weights, so two engines serving "the same model" can produce meaningfully different distributions. We study the problem of estimating the total variation (TV) distance between two length-$n$ autoregressive distributions to additive error $\epsilon$, under three access models: 1. Under *sample* access, we use $\tilde{O}(\frac{n^{2}K}{{\epsilon }^2})$ queries, where $K$ is the maximum support of the next-token distribution. 2. Under *logit* access, we use $O(\frac{n}{{\epsilon }^2})$ queries, and this is tight. 3. Under *noisy logit* access, we can smoothly interpolate between the above two: if probability values are given to $\sigma$ relative error, we use $\tilde{O}(\frac{n+n^2{\sigma }^2}{{\epsilon }^2})$ queries. We complement our theoretical results with an empirical evaluation of our algorithms, for example measuring the distance between sglang and vllm on standard settings. Our experiments highlight the robustness and practicality of estimating the total variation distance, compared to existing alternatives such as KL divergence.