Research map / Learning theory and algorithms / Sample complexity

Total Variation Distance Estimation in Autoregressive Models

NeurIPS 2026 · Learning theory and algorithms › Sample complexity · approach: Minimax estimation rates · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Estimates total variation distance between two length-n autoregressive LLM distributions under sample, logit, and noisy-logit access, giving improved query bounds and a vllm vs. sglang case study.

Problem

Estimating TV distance between two autoregressive (LLM) sequence distributions to additive error when only API-style prefix access is available; KL is infinite under support mismatch and prior sample-based estimators are query-expensive.

Approach

Uses a TV representation as an expectation of a bounded ratio under the mixture, with prefix logit access enabling exact likelihood ratios (O(n) queries per ratio), and a multilevel Monte Carlo scheme over noisy prefix distribution queries that interpolates between logit and sampling access.

Key results

• Cross-engine TV between vllm and sglang serving Qwen3-0.6B (bf16, top-k=20) is 0.586 at sequence length n=500; support mismatch accounts for 0.29 of this.
• Theoretical sample-access upper bound improves from O(n^3 m/eps^5) to O(n^2 K/eps^2) (up to logs), logit access achieves tight O(n/eps^2), and noisy logit access gives O((n+n^2 sigma^2)/eps^2) up to logs.
• Sequence-level log-probability API assigns zero mass to 37% of sglang's own sampled trajectories, shifting the estimated TV from 0.586 to 0.550 versus replay scoring.

Surprising findings

• Sequence-level log-probability scoring APIs are biased relative to the sampling distribution, moving the cross-engine TV estimate noticeably.
• Under the attention-backend study, some backends (cuDNN) are noisy even in isolation while FlashAttention-2 and math are deterministic in isolation but become noisy when served.

Limitations

• Gap of one factor of n between the noisy-logit/sampling upper and lower bounds remains open.
• Case study uses a single model (Qwen3-0.6B) and a single reference prompt for the main TV measurement; the estimate depends on prompt, length, and top-k truncation.
• Noise model requires independence across repeated queries, which serving stacks may violate (serial correlation observed).

Experimental setup

Datasets: synthetic hard instance trajectories sampled from vllm and sglang on Qwen3-0.6B

Benchmarks: synthetic hard instance with known TV vllm vs sglang cross-engine TV on Qwen3-0.6B

Metrics: estimated TV mean absolute error RMSE vs oracle-call budget variance ratio

Baselines: Prior prefix-sampler TV estimator (O(n^3 m/eps^5)) KL-based estimator for LLMs sequence-level log-probability API scoring

Builds on: Multilevel Monte Carlo likelihood-ratio TV estimator conditional sampling oracle models

Closest papers by meaning

• Total Variation Distance Meets Probabilistic Inference (ICML 2024 · similarity 0.85)
• Computational Explorations of Total Variation Distance (ICLR 2025 · similarity 0.84)
• Autoregressive Learning in Joint KL: Sharp Oracle Bounds and Lower Bounds (NeurIPS 2026 · similarity 0.82)
• Sub-Gaussian Confidence Intervals for Heavy-Tailed Data: Characterizing the Limits of Inference (NeurIPS 2026 · similarity 0.82)
• Multiply Robust Estimation for Local Distribution Shifts with Multiple Domains (ICML 2024 · similarity 0.81)
• Analytical Correction for Subsampling Bias in Drifting Models (NeurIPS 2026 · similarity 0.81)