論文の概要: FlashTrie: A GPU-Accelerated Constrained Beam Search for Generative Retrieval

• arxiv url: http://arxiv.org/abs/2607.10044v1
• Date: Fri, 10 Jul 2026 23:52:35 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-07-14 15:40:48.282604
• Title: FlashTrie: A GPU-Accelerated Constrained Beam Search for Generative Retrieval
• Title（参考訳）: FlashTrie: ジェネレーティブ検索のためのGPUによる制約付きビーム検索
• Abstract要約: FlashTrieは、メモリフットプリントを減らすためにビット圧縮を使用する整数対応の簡潔なトリエレイアウトである。 ビーム幅が最大1000までの800Mキーワードのライブラリでは、FlashTrieはトリエサーチのレイテンシを3ミリ秒未満に削減し、高度に最適化されたマルチスレッドベースライン上で最大24倍のスピードアップを実現している。 これらの改善により、FlashTrieは、スポンサー付き検索のような遅延クリティカルなアプリケーションにおいて、ビームサイズを最大5倍にスケールできる。
• 参考スコア（独自算出の注目度）: 16.54104032203289
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Constrained decoding is essential in generative retrieval, where document identifiers generated directly from a query must exactly match a predefined library of valid IDs. At scale, decoding is often constrained using a trie with beam search but most implementations run on CPU. Limited parallelism then makes trie traversal and candidate validation a serving bottleneck as beam width grows. We present FlashTrie, which addresses this limitation by optimizing constrained beam search on GPUs. It introduces an integer-aware succinct trie layout that uses bit compression to reduce memory footprint while keeping the full index in GPU high-bandwidth memory reducing memory stalls, and a cooperative CUDA kernel that performs beam expansion, validation, and pruning entirely on-device without per-step host orchestration. It further replaces CPU-style irregular lookup and heap maintenance with GPU-aware parallel primitives, improving warp utilization and reducing divergence. Together, these designs significantly reduce decoding latency and increase throughput while preserving retrieval quality. On a library of 800M keywords with beam widths up to 1000, FlashTrie reduces trie-search latency to under 3 ms, achieving up to 24x speedup over a highly optimized multi-threaded CPU baseline. These improvements enable FlashTrie to scale beam sizes by up to 5x in latency-critical applications such as sponsored search. In a large-scale online A/B experiment on a popular commercial search engine, it delivers a statistically significant +0.71% revenue lift, enabling real-time constrained decoding at a scale previously feasible only offline. The FlashTrie code will be publicly released after the review process.
• Abstract（参考訳）: 制約付き復号化は生成検索において必須であり、クエリから直接生成された文書識別子は、有効なIDの事前定義されたライブラリと正確に一致しなければならない。 大規模では、デコーディングはビームサーチのトリエを使って制限されることが多いが、ほとんどの実装はCPU上で実行される。 有限並列性は、ビーム幅が大きくなるにつれてトリエトラバーサルと候補バリデーションがボトルネックとなる。 本稿では,制約ビーム探索をGPU上で最適化することで,この制限に対処するFlashTrieを提案する。 整数対応の簡潔なトリエレイアウトを導入し、ビット圧縮を使用してメモリフットプリントを削減し、GPU高帯域メモリのフルインデックスを維持しながらメモリストールを削減している。 さらに、CPUスタイルの不規則なルックアップとヒープメンテナンスをGPU対応の並列プリミティブに置き換え、ワープ使用率を改善し、分散を低減する。 これらの設計により、復号遅延を著しく低減し、検索品質を維持しながらスループットを向上させることができる。 ビーム幅が最大1000までの800Mキーワードのライブラリでは、FlashTrieは3ミリ秒未満のトライ検索レイテンシを削減し、高度に最適化されたマルチスレッドCPUベースライン上で最大24倍のスピードアップを実現している。 これらの改善により、FlashTrieは、スポンサー付き検索のような遅延クリティカルなアプリケーションにおいて、ビームサイズを最大5倍にスケールできる。 人気のある商用検索エンジンにおける大規模なオンラインA/B実験では、統計的に有意な+0.71%の収益を上げ、以前オフラインでしか実現できなかったスケールでリアルタイムの制約付き復号を可能にする。 FlashTrieコードはレビュープロセスの後に公開される。

関連論文リスト

• Faster Than Flash: Exploiting Attention Sparsity for Efficient Long-Context Decoding [51.48425605758328]
  我々は,Faster Flash Decoding (FFD) という,長文デコーディングにおいてメモリ壁を壊すように設計されたハードウェア・アルゴリズムの共同設計フレームワークを提示する。 FFDはセレクタとコンピュータを完全に融合したカーネルに統合し、外部メタデータのインデックスをコンテンツ認識スキャンに置き換える。 最大11.6倍のカーネルレベルのスピードアップと256Kコンテキスト長のスケーリングを実現し、2.37倍のスループット向上を実現している。
  論文  参考訳（メタデータ） (2026-08-31T15:13:20Z)
• GPUSparse: GPU-Accelerated Learned Sparse Retrieval with Parallel Inverted Indices [3.3723515662362265]
  本稿では,GPUを高速化した正確なスパース検索システムであるGPUSparseを提案する。 ブロック整列されたワープ対応のポストリストを持つGPU並列逆インデックスを使用する。 Batched scatter-add スコアリングアルゴリズムは数百のクエリを同時に処理する。
  論文  参考訳（メタデータ） (2026-06-24T23:07:57Z)
• Accelerating GPU Inference of Large Language Models with Moderately Unstructured Sparse Weight Matrices [18.428868416628017]
  本稿では,中程度間隔の大規模言語モデル(LLM)に対する効率的な推論手法を提案する。 SpInferで最大1.64倍のスピードアップを実現し、FlashLLMで最大1.41倍のエンドツーエンドスピードアップを実現している。
  論文  参考訳（メタデータ） (2026-06-13T13:38:27Z)
• Prompt Compression in the Wild: Measuring Latency, Rate Adherence, and Quality for Faster LLM Inference [5.608398371429037]
  LLMLinguaは、プロンプト長、圧縮比、ハードウェア容量がよく一致した場合、最大18%のエンドツーエンドのスピードアップを達成する。 効率的な圧縮は、ワークロードをデータセンターGPUからコモディティカードにオフロードするのに十分なメモリ使用量を削減できることを示す。
  論文  参考訳（メタデータ） (2026-04-03T11:41:53Z)
• Spava: Accelerating Long-Video Understanding via Sequence-Parallelism-aware Approximate Attention [63.69228529380251]
  Spavaはシーケンス並列フレームワークで、ロングビデオ推論に最適化されている。 Spavaは、FlashAttn、ZigZagRing、APBで12.72x、1.70x、1.18xのスピードアップを提供する。
  論文  参考訳（メタデータ） (2026-01-29T09:23:13Z)
• GPU-Accelerated ANNS: Quantized for Speed, Built for Change [1.8419317899207142]
  現在の近似近傍探索(ANNS)システムは3つの重要な制限に直面している。 現在のシステムでは、コストのかかるランダムなメモリアクセスを導入することなく、データ移動を減らす効率的な量子化技術が欠如している。 本稿では、高いクエリスループットとアップビリティを備えたGPUアクセラレーションANNSシステムであるJasperを紹介する。
  論文  参考訳（メタデータ） (2026-01-11T19:51:54Z)
• Memory-Efficient Acceleration of Block Low-Rank Foundation Models on Resource Constrained GPUs [11.45717904490388]
  トランスフォーマーベースの基盤モデルの最近の進歩は、多くのタスクのデフォルト選択となった。 その急速に成長するサイズは、単一のGPUに完全なモデルを適合させることがますます難しくなり、計算コストが禁じられる。 ブロック低ランク(BLR)圧縮技術は、重み行列のコンパクト表現を学習することでこの問題に対処する。
  論文  参考訳（メタデータ） (2025-12-24T00:41:13Z)
• dParallel: Learnable Parallel Decoding for dLLMs [77.24184219948337]
  拡散大言語モデル(dLLM)は並列トークン予測と低推論遅延を提供する。 既存のオープンソースモデルは、パフォーマンスを確保するためにトークン長のデコードステップをほとんど必要としています。 高速サンプリングのためにdLLMs固有の並列性を解き放つシンプルで効果的な方法であるdParallelを導入する。
  論文  参考訳（メタデータ） (2025-09-30T16:32:52Z)
• vTensor: Flexible Virtual Tensor Management for Efficient LLM Serving [53.972175896814505]
  大規模言語モデル(LLM)は様々なドメインで広く使われ、数百万の日次要求を処理する。 大規模言語モデル(LLM)は様々なドメインで広く使われ、数百万の日次要求を処理する。
  論文  参考訳（メタデータ） (2024-07-22T14:37:58Z)
• Hardware-Aware Parallel Prompt Decoding for Memory-Efficient Acceleration of LLM Inference [23.633481089469836]
  LLM(Large Language Models)の自動回帰デコーディングは、ハードウェアの性能に大きなオーバーヘッドをもたらす。 トレーニング可能なパラメータを0.0002$%しか必要とせず,A100-40GBのGPUをたった16時間で効率的にトレーニングできる並列プロンプトデコーディングを提案する。 我々のアプローチでは、最大2.49$times$ スピードアップを示し、最小のメモリオーバーヘッドは0.0004$%である。
  論文  参考訳（メタデータ） (2024-05-28T22:19:30Z)
• FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness [80.3586155104237]
  FlashAttentionは、トランスフォーマーのためのIO対応の正確な注意アルゴリズムである。 これにより、GPU高帯域メモリ(HBM)とGPUオンチップ間のメモリ読み込み/書き込み数を削減できる。 FlashAttentionとブロックスパース FlashAttentionは、トランスフォーマーのコンテキストを長くすることを可能にする。
  論文  参考訳（メタデータ） (2022-05-27T17:53:09Z)
• Latency-Aware Differentiable Neural Architecture Search [113.35689580508343]
  近年、探索コストの低さと検索空間設計の柔軟性から、微分可能なニューラルネットワーク探索法が人気を博している。 しかし、これらの手法はネットワーク最適化の難しさに悩まされており、検索されたネットワークはハードウェアに不便な場合が多い。 本稿では,この問題を最適化に微分可能な遅延損失項を追加することにより,精度とレイテンシのトレードオフをバランス係数で行うことができる。
  論文  参考訳（メタデータ） (2020-01-17T15:55:21Z)

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

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