评估大模型推理引擎间输出分布差异，提出高效距离估计方法。
Total Variation Distance Estimation in Autoregressive Models
- 基于采样/对数几率/带噪对数几率三种访问模式设计估计器。
- 在对数几率访问下仅需 O(n/ε²) 次查询，达到理论最优。
- 可实测 SGLang 与 vLLM 在相同权重下的分布差异，适用于部署对比。
现代大模型部署常采用批处理、自定义内核和量化等优化手段，即使权重固定，不同推理引擎生成的输出分布也可能存在显著差异。本文研究长度为 n 的自回归分布间总变差（TV）距离的估计问题，目标误差为 ε，考察三种访问模型：(1) 采样访问下，使用 Õ(n²K/ε²) 次查询，优于 Meel 等人（2025）的 Õ(n³m/ε⁵)；其中 K 为单步最大支持集大小，m 为词表总大小且 m ≥ K。(2) 对数几率访问下，仅需 O(n/ε²) 次查询，且该复杂度紧致。(3) 带相对误差 σ 的噪声对数几率访问下，查询复杂度平滑过渡至 Õ((n + n²σ²)/ε²)。我们通过实验验证算法有效性，例如测量 SGLang 与 vLLM 在相同权重下的分布距离。结果表明，尽管 KL 散度可能无穷，总变差仍可有效估计。代码已开源：https://github.com/XunZhiyang/llm-tv-estimation。
原文摘要 · Abstract (English)
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 $\widetilde{O}(n^2 K/\varepsilon^2)$ queries, where $K$ is the maximum support of the next-token distribution. This improves upon the $\widetilde{O}(n^3 m/\varepsilon^5)$-query estimator of Meel et al. (2025), where $m \geq K$ is the total size of the token alphabet. (2) Under logit access, we use $O(n/\varepsilon^2)$ 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 $\widetilde{O}((n+n^2σ^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 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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。