論文の概要: Prefix Sharing Is a Sorting Problem

• arxiv url: http://arxiv.org/abs/2609.13692v1
• Date: Sat, 12 Sep 2026 04:02:31 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-16 07:15:05.476064
• Title: Prefix Sharing Is a Sorting Problem
• Title（参考訳）: プレフィックス共有が問題になる
• Abstract要約: 再利用するKVキャッシュを正確なプレフィックスマッチングで実行するため、再利用可能な部品の集合からプロンプトが組み立てられた場合、選択された順序は、どれだけの計算を共有できるかを決定する。 これは、要求が少なくとも2つの部分を含み、一般的には正しくない場合にのみ最適であることを示す。 我々の主な結果は構造定理であり、最小プレフィックス・トリーコストはリクエスト上の二項階層 H に対して min_H sum_x w(x) t_x(H) と等しい。
• 参考スコア（独自算出の注目度）: 0.304585143845864
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: LLM serving reuses KV cache by exact prefix match, so when a prompt is assembled from a set of reusable pieces -- retrieved passages, tool definitions, few-shot exemplars -- the order chosen for those pieces determines how much computation can be shared. Every deployed system fixes that order by a single global convention. We prove this is optimal only when requests contain at most two pieces, and asymptotically wrong in general. Our main result is a structure theorem: the minimum prefix-trie cost equals min_H sum_x w(x) t_x(H) over binary hierarchies H on the requests, where t_x(H) is the canonical decomposition size of the set of requests needing chunk x. Choosing chunk orders is therefore equivalent to choosing one hierarchy over requests. The identity yields an O(3^m) exact algorithm, identifies the two-chunk case as minimum vertex cover, and shows that on the leave-one-out family the optimum is the minimum external path length of a binary tree -- the merge-sort recursion -- so a global order pays Theta(n^2) against a true cost of Theta(n log n). Agglomerative clustering by common intersection is a tight 1/2-approximation for the achievable saving. On BM25 retrieval traces over three BEIR corpora the resulting layout reduces prefill by 17-36% against production RAG ordering, and the margin widens with retrieval depth as the theory predicts. Serving requests in the hierarchy's DFS order finally lets a cache holding one request's context attain the unbounded-cache optimum exactly, so cache capacity and reorder window act as substitutes.
• Abstract（参考訳）: LLMは、正確なプレフィックスマッチでKVキャッシュを再利用するので、再利用可能な部品のセットからプロンプトが組み立てられた場合 -- 検索されたパス、ツール定義、ほとんどショットの例 -- は、これらの部品で選択された順序によって、どれだけの計算を共有できるかが決定される。 デプロイされたシステムはすべて、その順序を単一のグローバルコンベンションによって修正する。 これは、要求が少なくとも2つの部分を含み、漸近的に間違っている場合にのみ最適であることを示す。 最小プレフィックス・トリーコストは、リクエスト上の二項階層 H に対して min_H sum_x w(x) t_x(H) と等しく、ここで t_x(H) はチャンク x を必要とする要求の集合の標準分解サイズである。 したがって、チャンクオーダーの選択は、リクエストよりも1つの階層を選択することと等価である。 同一性はO(3^m) 正確なアルゴリズムを導き、二つのチャンクのケースを最小の頂点被覆として識別し、残余の族において、最適値が二分木(マージソート再帰)の最小外路長であることを示す。 共通交点による集合的クラスタリングは、達成可能な貯蓄のための厳密な1/2近似である。 BM25では3つのBEIRコーパスが追跡され、結果のレイアウトはRAGの発注に対してプレフィルを17～36%削減し、この理論が予測するようにマージンは検索深度で拡大する。 階層のDFS順序でリクエストを実行することで、ひとつのリクエストのコンテキストを保持するキャッシュが、未バウンドキャッシュの最適化を正確に達成できる。

関連論文リスト

• SSTQ:Privacy-Preserving Vector Quantization via Subsampled Stochastic TurboQuant [79.24089819400126]
  Subsampled TurboQuant (SSTQ) は、オーバーコンプリートな等幅のタイトフレーム、座標サブサンプリング、プライバシ対応量子化を組み合わせたフレームワークである。 SSTQは平均2乗誤差スケーリングを実現し、クライアントあたり$lceil log N il + b$ bitsを使用する。 また、コードブックに依存したMSEスケーリングを$O(4b)$から$O(2b)$に削減する、プライバシを意識したコードブックの目的も導出します。
  論文  参考訳（メタデータ） (2026-08-05T17:51:25Z)
• Cluster with Auctions for Vector Search [18.098804415480696]
  大規模に近い近接探索は、インデックス化の分割によく依存する。 クエリプローブ関数とデータベースパーティションは、分離されたエンティティとして扱われることは滅多にありません。 本稿では、バランスの取れたデータベース分割とニューラルファンクションを共同で学習することで、この制限に対処するCwAを紹介する。
  論文  参考訳（メタデータ） (2026-07-15T11:42:07Z)
• HCRE: LLM-based Hierarchical Classification for Cross-Document Relation Extraction with a Prediction-then-Verification Strategy [54.91468501159335]
  文書間関係抽出 (RE) は, 異なる文書に存在する頭部尾部エンティティ間の関係を識別することを目的としている。 本稿では,各レベルでの多視点検証により信頼性を向上させる推論戦略を提案する。
  論文  参考訳（メタデータ） (2026-04-09T07:55:27Z)
• Probabilistic Language Tries: A Unified Framework for Compression, Decision Policies, and Execution Reuse [0.0]
  列上の任意の生成確率モデルによって暗黙的に定義されたプレフィックス構造を明示する統一表現であるLanguage Try (PLTs)を導入する。 また,任意のデータセットをカバー多数とスパース残量ストアに分解するハイブリッド圧縮アーキテクチャを導入し,Kolmogorov型プログラム表現とレート歪み理論を接続する。
  論文  参考訳（メタデータ） (2026-03-29T21:24:26Z)
• A Clustering-Based Variable Ordering Framework for Relaxed Decision Diagrams for Maximum Weighted Independent Set Problem [4.312746668772342]
  この研究は、変数順序付けのための新しいクラスタリングベースのフレームワークを導入する。 固定されていない変数の完全な集合に動的順序付けを適用する代わりに、最初にプリミティブ変数をクラスタに配置する。 次に、この構造分解を利用して順序付けプロセスの導出を行い、分割の探索空間を著しく削減する。
  論文  参考訳（メタデータ） (2025-12-17T08:49:38Z)
• vCache: Verified Semantic Prompt Caching [95.16654660556975]
  本稿では,ユーザ定義エラー率保証を備えた最初の検証済みセマンティックキャッシュであるvCacheを提案する。 オンライン学習アルゴリズムを使用して、キャッシュされたプロンプト毎に最適な閾値を推定し、追加のトレーニングなしで信頼性の高いキャッシュ応答を可能にする。 我々の実験によると、vCacheは特定のエラー境界を一貫して満たし、最先端の静的な閾値と微調整された埋め込みベースラインより優れています。
  論文  参考訳（メタデータ） (2025-02-06T04:16:20Z)
• Optimistic Query Routing in Clustering-based Approximate Maximum Inner Product Search [13.809692299886715]
  この研究は、クラスタリングに基づく最大内部積探索におけるルーティングを研究することによってギャップを埋める。 各シャード内の内積分布のモーメントを組み込んで最大内積を推定する枠組みを提案する。
  論文  参考訳（メタデータ） (2024-05-20T17:47:18Z)
• Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
  我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。 SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
  論文  参考訳（メタデータ） (2023-12-13T11:08:25Z)
• Global Optimization for Cardinality-constrained Minimum Sum-of-Squares Clustering via Semidefinite Programming [1.3053649021965603]
  最小二乗クラスタリング(MSSC)は、最近、各クラスタの濃度に関する事前知識を活用するために拡張されている。 本稿では,分枝切断法に基づく大域的最適化手法を提案する。 上界に対して、各ノードで解いたSDP緩和の解を生かした局所探索手順を提案する。
  論文  参考訳（メタデータ） (2022-09-19T10:19:06Z)
• Generalizing Few-Shot NAS with Gradient Matching [165.5690495295074]
  One-Shotメソッドは、1つのスーパーネットをトレーニングし、ウェイトシェアリングを通じて検索空間内の全てのアーキテクチャのパフォーマンスを近似する。 Few-Shot NASは、One-Shotスーパーネットを複数のサブスーパーネットに分割することで、ウェイトシェアリングのレベルを下げる。 Few-Shotよりも優れており、派生したアーキテクチャの精度という点では、従来の同等の手法をはるかに上回っている。
  論文  参考訳（メタデータ） (2022-03-29T03:06:16Z)
• Reinforcement Learning Based Query Vertex Ordering Model for Subgraph Matching [58.39970828272366]
  グラフマッチングアルゴリズムは、クエリグラフの埋め込みをデータグラフGに列挙する。 マッチング順序は、これらのバックトラックに基づくサブグラフマッチングアルゴリズムの時間効率において重要な役割を果たす。 本稿では,Reinforcement Learning (RL) と Graph Neural Networks (GNN) 技術を適用して,グラフマッチングアルゴリズムの高品質なマッチング順序を生成する。
  論文  参考訳（メタデータ） (2022-01-25T00:10:03Z)
• An objective function for order preserving hierarchical clustering [0.0]
  確率的部分順序の類似性に基づく階層的クラスタリングの理論と目的関数を提案する。 具体的には、元 $x le y$ が部分順序で与えられ、それぞれのクラスタ $[x]$ と $[y]$ が与えられたとき、その理論はクラスタ上で $[x]le'[y]$ となるような順序関係 $le'$ が得られる。
  論文  参考訳（メタデータ） (2021-09-09T13:35:01Z)
• DC-NAS: Divide-and-Conquer Neural Architecture Search [108.57785531758076]
  本稿では,ディープ・ニューラル・アーキテクチャーを効果的かつ効率的に探索するためのディバイド・アンド・コンカ(DC)手法を提案する。 ImageNetデータセットで75.1%の精度を達成しており、これは同じ検索空間を使った最先端の手法よりも高い。
  論文  参考訳（メタデータ） (2020-05-29T09:02:16Z)

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

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