# Total Variation Distance Estimation in Autoregressive Models

arXiv: https://arxiv.org/abs/2607.19510 · HTML: https://mlsanity.com/paper/2607.19510/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 44 references that are in the map.
- First posted on arXiv 21 Jul 2026.

## Builds on (most cited first, 23 of 23)

- [GPTQ: Accurate Post-Training Quantization for Generative Pre-trained Transformers](https://mlsanity.com/paper/2210.17323/) (2022)
- [AWQ: Activation-aware Weight Quantization for LLM Compression and Acceleration](https://mlsanity.com/paper/2306.00978/) (2023)
- [KIVI: A Tuning-Free Asymmetric 2bit Quantization for KV Cache](https://mlsanity.com/paper/2402.02750/) (2024)
- [KVQuant: Towards 10 Million Context Length LLM Inference with KV Cache Quantization](https://mlsanity.com/paper/2401.18079/) (2024)
- [EAGLE-2: Faster Inference of Language Models with Dynamic Draft Trees](https://mlsanity.com/paper/2406.16858/) (2024)
- [How is ChatGPT's behavior changing over time?](https://mlsanity.com/paper/2307.09009/) (2023)
- [Model Equality Testing: Which Model Is This API Serving?](https://mlsanity.com/paper/2410.20247/) (2024)
- [Are You Getting What You Pay For? Auditing Model Substitution in LLM APIs](https://mlsanity.com/paper/2504.04715/) (2025)
- [Optimal Algorithms for Testing Closeness of Discrete Distributions](https://mlsanity.com/paper/1308.3946/) (2013)
- [Accuracy is Not All You Need](https://mlsanity.com/paper/2407.09141/) (2024)
- [Testing Bayesian Networks](https://mlsanity.com/paper/1612.03156/) (2016)
- [Auditing Black-Box LLM APIs with a Rank-Based Uniformity Test](https://mlsanity.com/paper/2506.06975/) (2025)
- [Testing probability distributions underlying aggregated data](https://mlsanity.com/paper/1402.3835/) (2014)
- [Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioning](https://mlsanity.com/paper/1911.07357/) (2019)
- [Efficient Distance Approximation for Structured High-Dimensional Distributions via Learning](https://mlsanity.com/paper/2002.05378/) (2020)
- [Better Estimation of the Kullback--Leibler Divergence Between Language Models](https://mlsanity.com/paper/2504.10637/) (2025)
- [A Chasm Between Identity and Equivalence Testing with Conditional Queries](https://mlsanity.com/paper/1411.7346/) (2014)
- [Distance Estimation for High-Dimensional Discrete Distributions](https://mlsanity.com/paper/2308.04264/) (2023)
- [Improved Bounds for High-Dimensional Equivalence and Product Testing using Subcube Queries](https://mlsanity.com/paper/2408.02347/) (2024)
- [Testing Self-Reducible Samplers](https://mlsanity.com/paper/2312.10999/) (2023)
- [An Empirical Characterization of Outages and Incidents in Public Services for Large Language Models](https://mlsanity.com/paper/2501.12469/) (2025)
- [Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioning](https://mlsanity.com/paper/2502.16355/) (2025)
- [Tight simulation of a distribution using conditional samples](https://mlsanity.com/paper/2506.18444/) (2025)

## Built on by (most cited first, 2 of 2)

- [Divergence Timing and Cumulative Disagreement under KV-Cache Eviction](https://mlsanity.com/paper/2609.16617/) (2026)
- [Truncation Samplers Are Nested: Comparing Decoding Rules Is a Measurement Problem](https://mlsanity.com/paper/2610.15570/) (2026)

## Abstract (arXiv)

Modern LLM deployments use a number of implementation choices and inference optimizations (e.g., batching, custom kernels, and 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 three access models. (1) Under sample access, we use widetildeO(n2 K/varepsilon2) queries, where K is the maximum support of the next-token distribution. This improves upon the widetildeO(n3 m/varepsilon5)-query estimator of Meel et al. (2025), where m ≥ K is the total size of the token alphabet. (2) Under logit access, we use O(n/varepsilon2) queries, and this is tight. (3) Under noisy logit access, we smoothly interpolate between the above two guarantees: if probability values are given to relative error σ, we use widetildeO((n+n2σ2)/varepsilon2) queries. We complement our theoretical results with an empirical evaluation of our algorithms, for example measuring the distance between SGLang and vLLM serving identical weights. Our experiments highlight the robustness and practicality of estimating the total variation distance, which remains estimable where the KL divergence is infinite. Our code is available at https://github.com/XunZhiyang/llm-tv-estimation.