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 $\varepsilon$ under sample, logit, and noisy-logit access models. Under sample access, we use $\widetilde{O}(n^2K/\varepsilon^2)$ queries, where $K$ is the maximum support of the next-token distribution; under logit access, we use $O(n/\varepsilon^2)$ queries, and this is tight; under noisy logit access, if probability values are given to $\sigma$ relative error, we use $\widetilde{O}((n+n^2\sigma^2)/\varepsilon^2)$ queries. We complement our theoretical results with an empirical evaluation of our algorithms, for example measuring the distance between sglang and vllm in standard settings. Our experiments highlight the robustness and practicality of estimating total variation distance compared to alternatives such as KL divergence.