論文の概要: What Limits Does Quantization Place on Dense Top-$k$ Retrieval? A Theoretical Study
- arxiv url: http://arxiv.org/abs/2606.11780v1
- Date: Wed, 10 Jun 2026 08:11:41 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-06-11 16:42:38.355638
- Title: What Limits Does Quantization Place on Dense Top-$k$ Retrieval? A Theoretical Study
- Title（参考訳）: 検索に要する量子化の限界 : 理論的研究
- Authors: Koki Okajima, Tsukasa Yoshida,
- Abstract要約: すべての$k$-subset $S subseteq [N]$が、クエリベクトルによるトップ$k$検索の結果、実現可能であることを示す。
その結果,量子化が標準である実効的なベクトルデータベースや高密度検索システムでは,埋め込み次元とおそらく精度はコーパスサイズとともに増大しなければならないことが示唆された。
- 参考スコア（独自算出の注目度）: 0.25782420501870296
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: We establish conditions for embedding a corpus of $N$ documents as $d$-dimensional vectors such that every $k$-subset $S \subseteq [N]$ is realizable as a result of top-$k$ retrieval by some query vector. Recent work shows that $d = O(k)$ suffices for such embeddings to exist in $\mathbb{R}^d$, independently of $N$. We theoretically prove that this corpus-independent bound is specific to infinite precision. With $B$ bits per coordinate, perfect top-$k$ retrieval requires $Bd = Ω(k \ln N)$; thus, at any fixed precision, the dimension must grow at least logarithmically with $N$. Specializing to a $\ell_2$-normalized $B$-bit uniform scalar quantization model, we also identify a threshold on the precision $B^{*} = O(\ln \ln N)$ below which no dimension suffices, together with two further regimes that bound the feasible $(B, d)$ pairs. Our result implies that in practical vector databases and dense retrieval systems where quantization is standard, the embedding dimension and possibly the precision must grow with the corpus size.
- Abstract（参考訳）: 各$k$-subset $S \subseteq [N]$が、あるクエリベクトルによるトップ$k$検索の結果、実現可能であるように、$N$ドキュメントのコーパスを$d$次元ベクトルとして埋め込む条件を確立する。
最近の研究によると、$d = O(k)$ suffices for such embeddeds to exist in $\mathbb{R}^d$, independently of $N$である。
理論的には、このコーパス非依存境界は無限精度に比例する。
座標当たりのB$ビットの場合、完全のトップ$k$検索には$Bd = Ω(k \ln N)$が必要であるので、任意の固定精度で、次元は少なくとも$N$で対数的に成長しなければならない。
$\ell_2$-normalized $B$-bit uniform scalar Quantization model に特化して、以下の精度の $B^{*} = O(\ln \ln N)$ のしきい値も同定する。
その結果,量子化が標準である実効的なベクトルデータベースや高密度検索システムでは,埋め込み次元とおそらく精度はコーパスサイズとともに増大しなければならないことが示唆された。
関連論文リスト
- Is Dimensionality a Barrier for Retrieval Models? [21.1705493494434]
次元の制限のない最良のマージンである$mathsfmmathsfrd(+infty, A)-2log n)$は次元$d = O(mathsfmmathsfrd(+infty, A)-2log n)$でほぼ達成可能であることを示す。
我々の主定理は、次元の制限なしに可能な最良のマージンである$mathsfmmathsfrd(+infty, A)-2log n)$が成り立つことを証明している。
論文 参考訳（メタデータ） (2026-05-22T12:22:20Z) - Instance-optimal high-precision shadow tomography with few-copy measurements: A metrological approach [2.956729394666618]
シャドウトモグラフィーの高精度化過程における試料の複雑さについて検討した。
我々は、$O(mathrmpolylog(d))$$のコピー数に一度に作用するアダプティブな測定値を使用する。
論文 参考訳（メタデータ） (2026-02-04T19:00:00Z) - On the Intrinsic Dimensions of Data in Kernel Learning [1.675218291152252]
ラプラスカーネルのようなカーネルの場合、実効次元$d_K$はミンコフスキー次元$d_$よりもかなり小さく、正則領域で証明可能であることを示す。
以上の結果から,Laplaceカーネルのようなカーネルの場合,実効次元$d_K$は,通常のドメインに有するMinkowski次元$d_$よりも著しく小さいことが分かる。
論文 参考訳（メタデータ） (2026-01-22T17:32:24Z) - Optimal Sketching for Residual Error Estimation for Matrix and Vector Norms [50.15964512954274]
線形スケッチを用いた行列とベクトルノルムの残差誤差推定問題について検討する。
これは、前作とほぼ同じスケッチサイズと精度で、経験的にかなり有利であることを示す。
また、スパースリカバリ問題に対して$Omega(k2/pn1-2/p)$低いバウンダリを示し、これは$mathrmpoly(log n)$ factorまで厳密である。
論文 参考訳（メタデータ） (2024-08-16T02:33:07Z) - Optimal Query Complexities for Dynamic Trace Estimation [59.032228008383484]
我々は,行列がゆっくりと変化している動的環境において,正確なトレース推定に必要な行列ベクトルクエリ数を最小化する問題を考える。
我々は、$delta$失敗確率で$epsilon$エラーまで、すべての$m$トレースを同時に推定する新しいバイナリツリー要約手順を提供する。
我々の下界(1)は、静的な設定においてもフロベニウスノルム誤差を持つ行列ベクトル積モデルにおけるハッチンソン推定子の第一の厳密な境界を与え、(2)動的トレース推定のための最初の無条件下界を与える。
論文 参考訳（メタデータ） (2022-09-30T04:15:44Z) - Enlarging the notion of additivity of resource quantifiers [62.997667081978825]
量子状態 $varrho$ と量子化器 $cal E(varrho) が与えられたとき、$cal E(varrhootimes N)$ を決定するのは難しい。
本研究では, ある球対称状態の1発の蒸留可能な絡み合いを, このような拡張付加性によって定量的に近似できることを示す。
論文 参考訳（メタデータ） (2022-07-31T00:23:10Z) - Simplest non-additive measures of quantum resources [77.34726150561087]
我々は $cal E(rhootimes N) = E(e;N) ne Ne$ で説明できる測度について研究する。
論文 参考訳（メタデータ） (2021-06-23T20:27:04Z) - Optimal Spectral Recovery of a Planted Vector in a Subspace [80.02218763267992]
我々は、$ell_4$ノルムが同じ$ell$ノルムを持つガウスベクトルと異なるプラントベクトル$v$の効率的な推定と検出について研究する。
規則$n rho gg sqrtN$ では、大クラスのスペクトル法(そしてより一般的には、入力の低次法)は、植込みベクトルの検出に失敗する。
論文 参考訳（メタデータ） (2021-05-31T16:10:49Z) - Improved quantum data analysis [1.8416014644193066]
我々は、$O(log2 m)/epsilon2)$$$d$次元状態のサンプルのみを必要とする量子"Threshold Search"アルゴリズムを提供する。
また, $tildeO((log3 m)/epsilon2)$サンプルを用いた仮説選択法も提案する。
論文 参考訳（メタデータ） (2020-11-22T01:22:37Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳（メタデータ） (2020-08-24T06:50:57Z) - Efficient Statistics for Sparse Graphical Models from Truncated Samples [19.205541380535397]
i) スパースガウス図形モデルの推論と (ii) スパース線形モデルの回復支援の2つの基本的問題と古典的問題に焦点をあてる。
疎線型回帰については、$(bf x,y)$ が生成されるが、$y = bf xtopOmega* + MathcalN(0,1)$ と $(bf x, y)$ は、truncation set $S subseteq mathbbRd$ に属する場合にのみ見られる。
論文 参考訳（メタデータ） (2020-06-17T09:21:00Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。