論文の概要: Deterministic Retrieval at Scale: Optimal-Space LCP Indexing and 308x Energy Reduction on Modern GPUs

• arxiv url: http://arxiv.org/abs/2602.04936v1
• Date: Wed, 04 Feb 2026 15:40:42 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-06 18:49:08.56113
• Title: Deterministic Retrieval at Scale: Optimal-Space LCP Indexing and 308x Energy Reduction on Modern GPUs
• Title（参考訳）: スケールにおける決定論的検索:現代GPUにおける最適空間LCPインデックスと308倍エネルギー削減
• Authors: Stanislav Byriukov,
• Abstract要約: 長さLのN配列に対するLCP(Longest Common Prefix)類似性に基づく決定論的トップk検索について検討した。 O(N*L) 空間を O(L+k) クエリ時間で表す。 次に,サーマル・アウェア・ロジック(TAL)を導入し,プレフィックス構造を範囲境界スキャンに変換する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study deterministic top-k retrieval under Longest Common Prefix (LCP) similarity for N sequences of length L. We prove a tight Omega(N) space lower bound (cell-probe model) and present a trie-based index using O(N*L) space with O(L+k) query time. We contrast this with pairwise materialization (Theta(N^2)), which hits a practical OOM wall at scale, while our indexed approach remains O(N) in memory. We then introduce Thermal-Aware Logic (TAL), which turns prefix structure into range-bounded scans. In hardware measurements, TAL reduces energy per query by 308x (0.0145 J vs 4.46 J) and cuts p95 latency by 329x (0.114 ms vs 37.5 ms) on a 20M-item range-scan benchmark, while sustaining near-peak utilization (~99%) under long runs. The result is a deterministic retrieval primitive with receipts in regimes where approximate methods are unacceptable.
• Abstract（参考訳）: 我々は,長さLのN列に対するLCP類似性に基づく決定論的トップk検索について検討し,O(L+k)クエリ時間を持つO(N*L)空間を用いて,厳密なOmega(N)空間下界(セルプローブモデル)を証明した。 我々はこれを,O(N) をメモリに残しながら,実用的な OOM の壁を大規模に打つ対の物質化 (Theta(N^2)) と対比する。 次に,サーマル・アウェア・ロジック(TAL)を導入し,プレフィックス構造を範囲境界スキャンに変換する。 ハードウェア測定では、TALはクエリ毎のエネルギーを308x (0.0145 J vs 4.46 J)削減し、20Mのレンジスキャンベンチマークでp95のレイテンシを329x (0.114 ms vs 37.5 ms)削減すると同時に、長時間実行時のニアピーク利用(約99%)を維持している。 その結果、近似メソッドが受け入れられないレシートを持つ決定論的検索プリミティブが得られた。

関連論文リスト

• A Novel Approach for Estimating Largest Lyapunov Exponents in One-Dimensional Chaotic Time Series Using Machine Learning [0.0]
  機械学習を用いて1次元カオス時系列から最大のリアプノフ指数(LLE)を推定するためのデータ駆動手法を提案する。 予測器はサンプル外マルチ水平予測を生成するように訓練され、LLEは地平線を横切る幾何平均予測誤差(GMAE)の指数的成長から推定される。 我々は,4つの標準1次元地図-ロジスティック,正弦,立方体,チェビシェフが達成するR2pos > 0.99のアプローチを,M = 450と短い列の基準LLE曲線に対して検証した。
  論文  参考訳（メタデータ） (2025-07-07T10:53:02Z)
• Infinity Search: Approximate Vector Search with Projections on q-Metric Spaces [94.12116458306916]
  我々は、$q$の測度空間において、計量木は三角形の不等式のより強いバージョンを活用でき、正確な探索の比較を減らすことができることを示した。 任意の異方性測度を持つデータセットを$q$-metric空間に埋め込む新しい射影法を提案する。
  論文  参考訳（メタデータ） (2025-06-06T22:09:44Z)
• MOM: Memory-Efficient Offloaded Mini-Sequence Inference for Long Context Language Models [72.61076288351201]
  メモリ効率の良いオフロードミニシーケンス推論(MOM)を提案する。 MOMは重要なレイヤを小さな“ミニシーケンス”に分割し、KVキャッシュのオフロードとシームレスに統合する。 Meta-Llama-3.2-8Bでは、単一のA100 80GB GPU上での最大コンテキスト長を155kから455kに拡張する。
  論文  参考訳（メタデータ） (2025-04-16T23:15:09Z)
• Bounding Large-Scale Bell Inequalities [0.0]
  ベルの不等式は非局所性を研究するための重要なツールであるが、システムのサイズが大きくなるにつれてすぐに計算的に難解になる。 本研究では,NPA階層,投影の交互化法,メモリ効率のアルゴリズムL-BFGSを組み合わせることで,そのような不等式に対する量子的違反の上限を求める新しい手法を提案する。
  論文  参考訳（メタデータ） (2024-12-11T16:45:15Z)
• vTensor: Flexible Virtual Tensor Management for Efficient LLM Serving [53.972175896814505]
  大規模言語モデル(LLM)は様々なドメインで広く使われ、数百万の日次要求を処理する。 大規模言語モデル(LLM)は様々なドメインで広く使われ、数百万の日次要求を処理する。
  論文  参考訳（メタデータ） (2024-07-22T14:37:58Z)
• MInference 1.0: Accelerating Pre-filling for Long-Context LLMs via Dynamic Sparse Attention [36.49445805074941]
  Minference (Milliontokens Inference) は長周期処理の前処理を高速化するスパース計算法である。 我々は,MInferenceが精度を維持しつつ,A100にプリフィルする際の推論遅延を最大10倍に効果的に低減できることを実証した。
  論文  参考訳（メタデータ） (2024-07-02T17:59:56Z)
• Scaling Sparse Fine-Tuning to Large Language Models [67.59697720719672]
  大きな言語モデル(LLM)は、パラメータの数が多いため、完全な微調整が難しい。 本研究では,パラメータの配列とパラメータのデルタを事前学習した値に対して保持する新しいスパース微調整法SpIELを提案する。 提案手法は,LoRAのようなパラメータ効率の高い微調整法よりも性能が優れ,実行時間も同等であることを示す。
  論文  参考訳（メタデータ） (2024-01-29T18:43:49Z)
• Quick Adaptive Ternary Segmentation: An Efficient Decoding Procedure For Hidden Markov Models [41.99844472131922]
  ノイズ観測から元の信号を復号することは、ほぼすべてのHMMデータ解析における主要な目標の1つである。 QATS, QATS, QATS, QATS, QATS, QATS, QATS, QATS, QATS, QATS, QATS, QATSについて述べる。 QATSの実装はGitHubのRパッケージQATSにある。
  論文  参考訳（メタデータ） (2023-05-29T19:37:48Z)

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

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