mlsanityData to 14 Oct 2026

Total Variation Distance Estimation in Autoregressive Models

arXiv 2607.19510 ↗First posted 21 Jul 2026cs.LG cs.DS stat.MEcited by 2

Not on the map. Why?

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.

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

23 of 44 references.

References · 23

  1. 2022GPTQ: Accurate Post-Training Quantization for Generative Pre-trained Transformerscited by 1,919
  2. 2023AWQ: Activation-aware Weight Quantization for LLM Compression and Accelerationcited by 1,298
  3. 2024KIVI: A Tuning-Free Asymmetric 2bit Quantization for KV Cachecited by 637
  4. 2024KVQuant: Towards 10 Million Context Length LLM Inference with KV Cache Quantizationcited by 591
  5. 2024EAGLE-2: Faster Inference of Language Models with Dynamic Draft Treescited by 370
  6. 2023How is ChatGPT's behavior changing over time?cited by 270
  7. 2024Model Equality Testing: Which Model Is This API Serving?cited by 47
  8. 2025Are You Getting What You Pay For? Auditing Model Substitution in LLM APIscited by 38
  9. 2013Optimal Algorithms for Testing Closeness of Discrete Distributionscited by 37
  10. 2024Accuracy is Not All You Needcited by 31
  11. 2016Testing Bayesian Networkscited by 23
  12. 2025Auditing Black-Box LLM APIs with a Rank-Based Uniformity Testcited by 18
11 more
  1. 2014Testing probability distributions underlying aggregated datacited by 15
  2. 2019Random Restrictions of High-Dimensional Distributions and Uniformity Testing with Subcube Conditioningcited by 14
  3. 2020Efficient Distance Approximation for Structured High-Dimensional Distributions via Learningcited by 14
  4. 2025Better Estimation of the Kullback--Leibler Divergence Between Language Modelscited by 11
  5. 2014A Chasm Between Identity and Equivalence Testing with Conditional Queriescited by 5
  6. 2023Distance Estimation for High-Dimensional Discrete Distributionscited by 3
  7. 2024Improved Bounds for High-Dimensional Equivalence and Product Testing using Subcube Queriescited by 3
  8. 2023Testing Self-Reducible Samplerscited by 2
  9. 2025An Empirical Characterization of Outages and Incidents in Public Services for Large Language Modelscited by 2
  10. 2025Monotonicity Testing of High-Dimensional Distributions with Subcube Conditioningcited by 2
  11. 2025Tight simulation of a distribution using conditional samplescited by 1

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 2.

2 papers.

  1. 2026Divergence Timing and Cumulative Disagreement under KV-Cache Evictioncited by 0
  2. 2026Truncation Samplers Are Nested: Comparing Decoding Rules Is a Measurement Problemcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2026Autoregressive Learning in Joint KL: Sharp Oracle Bounds and Lower Bounds
  2. 2024Beyond Autoregression: Fast LLMs via Self-Distillation Through Time
  3. 2026The Surprising Universality of LLM Outputs: A Real-Time Verification Primitive
  4. 2026Length Value Model: Scalable Value Pretraining for Token-Level Length Modeling
  5. 2026Inference-Time Scaling for Visual AutoRegressive modeling by Searching Representative Samples
  6. 2026No Universal Signal Predicts Sample-Level LLM Regression under Version Updates
  7. 2024Quantifying the Capabilities of LLMs across Scale and Precision
  8. 2026Eliciting Numerical Predictive Distributions of LLMs Without Autoregression