論文の概要: Total Variation Distance Estimation in Autoregressive Models

• arxiv url: http://arxiv.org/abs/2607.19510v1
• Date: Tue, 21 Jul 2026 18:49:45 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-23 18:51:37.90632
• Title: Total Variation Distance Estimation in Autoregressive Models
• Title（参考訳）: 自己回帰モデルにおける全変動距離推定
• Abstract要約: 本研究では,2つの長さ-n$の自己回帰分布間の総変動(TV)距離を推定する問題について検討する。 理論的結果をアルゴリズムの実証的な評価で補完する。
• 参考スコア（独自算出の注目度）: 13.958816413011162
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.
• Abstract（参考訳）: 現代のLLMデプロイメントでは、固定重みの上に多くの実装選択と推論最適化(バッチ処理、カスタムカーネル、量子化など)を使用しているため、"同じモデル"を提供する2つのエンジンは、意味のある異なる分布を生成することができる。 本研究では,2つの長さ-n$の自己回帰分布間の総変動(TV)距離を3つのアクセスモデルの下で加算誤差$\varepsilon$に推定する問題について検討する。 1) サンプルアクセスでは、$\widetilde{O}(n^2 K/\varepsilon^2)$クエリを使用します。 これは$\widetilde{O}(n^3 m/\varepsilon^5)$-query estimator of Meel et al (2025)で改善され、$m \geq K$はトークンアルファベットの総サイズである。 (2)logitアクセスでは、$O(n/\varepsilon^2)$クエリを使用します。 (3) ノイズの多いロジットアクセスでは、上記の2つの保証の間に円滑に補間する: 確率値が相対誤差$σ$に与えられる場合、$\widetilde{O}((n+n^2σ^2)/\varepsilon^2)$クエリを使用する。 我々は,SGLang と vLLM の距離を同じ重量で測定するなど,我々のアルゴリズムの実証的な評価で理論結果を補完する。 実験では,KLの発散が無限である場合にも推定可能な全変動距離を推定する頑健さと実用性を強調した。 私たちのコードはhttps://github.com/XunZhiyang/llm-tv-estimationで利用可能です。

関連論文リスト

• A positive resolution of the gap-entropy conjecture [33.232618834192564]
  固定信頼度ベストアーム識別のためのギャップエントロピー予想を証明した。 各部分最適アーム $i$ に対して、$_i=_*-_i$ を最適平均とのギャップとする。 インスタンスに依存しないアルゴリズムがあり、期待されるサンプル数は、この量の定数倍数で制限される。
  論文  参考訳（メタデータ） (2026-09-09T17:57:11Z)
• Optimizing Computational-Statistical Runtime for Wasserstein Distance Estimation [8.375876290025586]
  正方形距離は確率分布間の差を測定するのによく使われるツールである。 我々は,サンプルの正規カルテシアングリッドスケッチを導入するためのSample-$計算パラダイムを開発した。 我々は、$W(P, Q)$を$-max(2,fracd+1+o(1)1+)$ time for $0 1$ Hlder smooth distributions の$$エラー内で近似する。
  論文  参考訳（メタデータ） (2026-05-19T17:10:47Z)
• High-accuracy sampling for diffusion models and log-concave distributions [70.90863485771405]
  本稿では,$mathrmpolylog (1/)$のステップで$$-errorを求める拡散モデルサンプリングアルゴリズムを提案する。 我々の手法は、一般的なログ凹凸分布に対する最初の$mathrmpolylog (1/)$ complexity samplerをもたらす。
  論文  参考訳（メタデータ） (2026-02-01T17:05:31Z)
• Learning Multinomial Logits in $O(n \log n)$ time [56.23331174813387]
  MNLモデル(Multinomial Logit、MNL)は、アイテム$[n]=1, ..., n$の有限宇宙から成り、それぞれ正の重みを割り当てる。 クエリはslateと呼ばれる許容可能なサブセットを指定し、モデルはそのslateからその重みに比例した確率で1つのアイテムを選択する。 このクエリモデルは、文学におけるPockett-Luceモデルまたは条件付きサンプリングオラクルとしても知られている。
  論文  参考訳（メタデータ） (2026-01-07T22:07:44Z)
• Sequential 1-bit Mean Estimation with Near-Optimal Sample Complexity [32.65125292684608]
  1ビット通信制約を用いた分散平均推定問題について検討する。 私たちの推定器は、有界平均$-lambda le mathbbE(X) le lambda $)と変数$mathrmVar(X) le sigma2$)を持つすべてのディストリビューションに対して$(epsilon, delta)$-PACです。
  論文  参考訳（メタデータ） (2025-09-26T06:22:57Z)
• Mallows Model with Learned Distance Metrics: Sampling and Maximum Likelihood Estimation [0.1534667887016089]
  データから直接距離距離を学習するMallowsモデルの一般化を提案する。 具体的には、$L_alpha$ distances: $d_alpha(pi,sigma):=sum_i=1 |pi(i)-sigma(i)|alpha$である。 このサンプリングアルゴリズムを用いて、中央ランク、分散パラメータ、および最適距離距離を共同で推定する、効率的な最大類似度推定(MLE)アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2025-07-10T18:52:09Z)
• Proving the Limited Scalability of Centralized Distributed Optimization via a New Lower Bound Construction [57.93371273485736]
  我々は、すべての労働者が同一の分布にアクセスする均質な(すなわちd.d.)場合であっても、すべての労働者が非バイアス付き境界 LDeltaepsilon2,$$$$$ のポリ対数的により良いポリ対数を求める集中型分散学習環境を考える。
  論文  参考訳（メタデータ） (2025-06-30T13:27:39Z)
• Testing Identity of Distributions under Kolmogorov Distance in Polylogarithmic Space [1.2277343096128712]
  本稿では、ストリーミング設定において、空間$O(log4 varepsilon-1)$を使用するアルゴリズムを提供する。 また、私たちは9つの関連するオープンな問題を述べ、それと関連した問題への関心を喚起することを望んでいます。
  論文  参考訳（メタデータ） (2024-10-29T15:24:27Z)
• Relative-Translation Invariant Wasserstein Distance [82.6068808353647]
  距離の新しい族、相対翻訳不変ワッサーシュタイン距離(RW_p$)を導入する。 我々は、$RW_p 距離もまた、分布変換に不変な商集合 $mathcalP_p(mathbbRn)/sim$ 上で定義される実距離測度であることを示す。
  論文  参考訳（メタデータ） (2024-09-04T03:41:44Z)
• Stochastic Approximation Approaches to Group Distributionally Robust Optimization and Beyond [89.72693227960274]
  本稿では,グループ分散ロバスト最適化 (GDRO) を,$m$以上の異なる分布をうまく処理するモデルを学習する目的で検討する。 各ラウンドのサンプル数を$m$から1に抑えるため、GDROを2人でプレイするゲームとして、一方のプレイヤーが実行し、他方のプレイヤーが非公開のマルチアームバンディットのオンラインアルゴリズムを実行する。 第2のシナリオでは、最大リスクではなく、平均的最上位k$リスクを最適化し、分散の影響を軽減することを提案する。
  論文  参考訳（メタデータ） (2023-02-18T09:24:15Z)
• Quantum tomography using state-preparation unitaries [0.22940141855172028]
  ユニタリへのアクセスが与えられると、$d$次元の量子状態の古典的記述を近似的に得るアルゴリズムを記述する。 状態の$varepsilon$-$ell$-approximationを得るには、$widetildeTheta(d/varepsilon)$ Unitaryのアプリケーションが必要です。 我々は、ランク=r$混合状態のシュターテン$q$最適推定値を得るための効率的なアルゴリズムを与える。
  論文  参考訳（メタデータ） (2022-07-18T17:56:18Z)
• A Law of Robustness beyond Isoperimetry [84.33752026418045]
  我々は、任意の分布上でニューラルネットワークパラメータを補間する頑健性の低い$Omega(sqrtn/p)$を証明した。 次に、$n=mathrmpoly(d)$のとき、スムーズなデータに対する過度なパラメータ化の利点を示す。 我々は、$n=exp(omega(d))$ のとき、$O(1)$-Lipschitz の頑健な補間関数の存在を否定する。
  論文  参考訳（メタデータ） (2022-02-23T16:10:23Z)
• TURF: A Two-factor, Universal, Robust, Fast Distribution Learning Algorithm [64.13217062232874]
  最も強力で成功したモダリティの1つは、全ての分布を$ell$距離に近似し、基本的に最も近い$t$-piece次数-$d_$の少なくとも1倍大きい。 本稿では,この数値をほぼ最適に推定する手法を提案する。
  論文  参考訳（メタデータ） (2022-02-15T03:49:28Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。