論文の概要: Qrita: High-performance Top-k and Top-p Algorithm for GPUs using Pivot-based Truncation and Selection

• arxiv url: http://arxiv.org/abs/2602.01518v1
• Date: Mon, 02 Feb 2026 01:19:28 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-02-03 19:28:33.829608
• Title: Qrita: High-performance Top-k and Top-p Algorithm for GPUs using Pivot-based Truncation and Selection
• Title（参考訳）: Qrita: Pivot-based Truncation と Selection を用いたGPU用高性能トップkおよびトップpアルゴリズム
• Authors: Jongseok Park, Sunga Kim, Alvin Cheung, Ion Stoica,
• Abstract要約: Top-kとTop-pは、大きな言語モデルのサンプリングにおいて支配的なトランケーション演算子である。 我々は、ピボットベースの選択戦略に基づく効率的なトップkとトップpのアルゴリズムであるQritaを提案する。 Qritaは最大2倍のスループットと半メモリ使用を実現し、ソートベースのアルゴリズムに同じ出力を提供する。
• 参考スコア（独自算出の注目度）: 35.32994106492222
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Top-k and Top-p are the dominant truncation operators in the sampling of large language models. Despite their widespread use, implementing them efficiently over large vocabularies remains a significant challenge. Existing approaches often rely on sorting, which incur significant computation and memory overhead on GPUs, or stochastic approaches, which alter the algorithm output. In this work, we propose Qrita, an efficient Top-k and Top-p algorithm based on a pivot-based selection strategy. Based on RTop-k, which uses a pivot-based search for node selection in graph neural networks, Qrita extends the concept of pivot-based search to both Top-k and Top-p with two key techniques: 1. Gaussian-based sigma-truncation, which greatly reduces the search space of the target elements, and 2. Quaternary pivot search with duplication handling, which halves the pivot search iteration and guarantees deterministic output. We provide the full implementation of Qrita using Triton, a popular GPU programming language. Our evaluation of Qrita against the Top-k and Top-p kernels of high performance LLM execution engines such as vLLM, SGLang, and Flashinfer show that Qrita achieves up to 2 times throughput and half memory use while providing the same output to the the sorting-based algorithms.
• Abstract（参考訳）: Top-kとTop-pは、大きな言語モデルのサンプリングにおいて支配的なトランケーション演算子である。 広く使われているにもかかわらず、大きな語彙を効果的に実装することは大きな課題である。 既存のアプローチはソートに頼っていることが多く、GPUや確率的なアプローチで計算とメモリオーバーヘッドが大きくなり、アルゴリズムの出力が変化する。 本研究では、ピボットベースの選択戦略に基づく効率的なトップkとトップpのアルゴリズムであるQritaを提案する。 Qritaはグラフニューラルネットワークのノード選択をピボットベースで検索するRTop-kに基づいて、Top-kとTop-pの両方にピボットベースの検索という概念を拡張している。 1. ターゲット要素の探索空間を大幅に削減するガウス的シグマトランケーション 2. 4次ピボット探索と重複処理により、ピボット探索の繰り返しを短縮し、決定論的出力を保証する。 我々は、一般的なGPUプログラミング言語であるTritonを使用して、Qritaの完全な実装を提供する。 我々は,vLLM,SGLang,Flashinferなどの高性能LLM実行エンジンのTop-kカーネルとTop-pカーネルに対するQritaの評価を行った。

関連論文リスト

• Efficient Sketching and Nearest Neighbor Search Algorithms for Sparse Vector Sets [16.768212375976546]
  スパースANNSのための新しいデータ構造とアルゴリズム手法を提案する。 我々の貢献は、スパースベクトルに対する理論的に基底化されたスケッチアルゴリズムから、それらの有効次元を減少させるものまで様々である。 我々の最終アルゴリズムは耐震性と呼ばれ、大規模ベンチマークデータセット上で高精度でミリ秒以下のレイテンシに達する。
  論文  参考訳（メタデータ） (2025-09-29T14:02:45Z)
• LoRANN: Low-Rank Matrix Factorization for Approximate Nearest Neighbor Search [4.194768796374315]
  本稿では,内積近似が多出力回帰問題であることを示す観測に基づく新しい教師付きスコア計算法を提案する。 実験の結果,提案手法はクエリ待ち時間とメモリ使用量の両方においてPQよりも優れていることがわかった。 また,クラスタリングに基づくANNライブラリであるLoRANNを導入する。
  論文  参考訳（メタデータ） (2024-10-24T17:13:39Z)
• Sum-of-Squares inspired Quantum Metaheuristic for Polynomial Optimization with the Hadamard Test and Approximate Amplitude Constraints [76.53316706600717]
  最近提案された量子アルゴリズムarXiv:2206.14999は半定値プログラミング(SDP)に基づいている SDPにインスパイアされた量子アルゴリズムを2乗和に一般化する。 この結果から,本アルゴリズムは大きな問題に適応し,最もよく知られた古典学に近似することが示唆された。
  論文  参考訳（メタデータ） (2024-08-14T19:04:13Z)
• PECANN: Parallel Efficient Clustering with Graph-Based Approximate Nearest Neighbor Search [7.466687780705626]
  本稿では, 点集合の密度に基づくクラスタリングについて検討する。 密度ピークの異なる変種を単一のフレームワークPECANNに統合する。 PECANNを用いて5つのクラスタリングアルゴリズムを実装し,最大128万点,最大1024次元の合成および実世界のデータセットを双方向ハイパースレッディングを備えた30コアマシン上で評価する。
  論文  参考訳（メタデータ） (2023-12-06T22:43:50Z)
• Towards Better Out-of-Distribution Generalization of Neural Algorithmic Reasoning Tasks [51.8723187709964]
  ニューラルネットワーク推論タスクのOOD一般化について検討する。 目標は、ディープニューラルネットワークを使用して入出力ペアからアルゴリズムを学ぶことである。
  論文  参考訳（メタデータ） (2022-11-01T18:33:20Z)
• Towards Optimally Efficient Tree Search with Deep Learning [76.64632985696237]
  本稿では,線形モデルから信号整数を推定する古典整数最小二乗問題について検討する。 問題はNPハードであり、信号処理、バイオインフォマティクス、通信、機械学習といった様々な応用でしばしば発生する。 本稿では, 深いニューラルネットワークを用いて, 単純化されたメモリバウンドA*アルゴリズムの最適推定を推定し, HATSアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-01-07T08:00:02Z)
• Hybrid quantum-classical algorithms for approximate graph coloring [65.62256987706128]
  量子近似最適化アルゴリズム(RQAOA)をMAX-$k$-CUTに適用する方法を示す。 任意のグラフに対するレベル-$1$QAOAとレベル-$1$RQAOAをシミュレートした,効率的な古典的シミュレーションアルゴリズムを構築する。
  論文  参考訳（メタデータ） (2020-11-26T18:22:21Z)

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

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