論文の概要: Prof-K: Probabilistic One-Pass Filtering for Efficient Top-k Selection
- arxiv url: http://arxiv.org/abs/2608.12573v1
- Date: Wed, 12 Aug 2026 20:31:33 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-14 18:29:38.321416
- Title: Prof-K: Probabilistic One-Pass Filtering for Efficient Top-k Selection
- Title（参考訳）: Prof-K: 効率的なトップk選択のための確率的ワンパスフィルタ
- Abstract要約: Prof-Kは確率論的正当性を保証する高速でスケーラブルで分布に依存しないトップkアルゴリズムである。
我々は、ほぼ最適なサンプルサイズとともに、精度とバッファサイズを高い確率で保証する。
Prof-K は高度に最適化された PyTorch topk と最近の RadiK 実装で1.5x-10x の高速化を実現している。
- 参考スコア（独自算出の注目度）: 11.90858984464117
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Top-k selection is a fundamental computational primitive with applications spanning databases, information retrieval, signal processing, and modern machine learning workloads, including sparse activations and attention pruning. As data sizes grow, existing approaches become inefficient: exact methods incur high memory and compute overhead, while approximate methods often rely on brittle heuristics that degrade under adversarial or heavy-tailed inputs. In this paper, we introduce Prof-K, a fast, scalable, and distribution-agnostic top-k algorithm with probabilistic correctness guarantees. Prof-K performs a single-pass filtering procedure: a small random sample estimates an adaptive threshold, the N input elements are streamed once into a compact buffer, and an exact top-k routine on this buffer recovers the true top-k elements with probability at least 1 - $ε$, where $ε$ > 0 is user specified. We derive high-probability guarantees for correctness and buffer size, together with an approximately optimal sample size that minimizes overhead as a function of N and k. Empirically, Prof-K achieves 1.5x-10x speedups over the highly optimized PyTorch topk and recent RadiK implementations, with the largest gains in the large-scale, small-to-moderate-k regime where prior methods struggle most. Unlike previous approaches, these guarantees hold independently of the input distribution, ensuring robustness to adversarial settings. By relaxing the recall target (e.g., recovering 95% of the true top-k values), Prof-K additionally provides a principled accuracy-speed trade-off. We further demonstrate its impact on training BatchTopK Sparse Autoencoders (SAEs), where top-k selection constitutes a significant portion of the training cost.
- Abstract（参考訳）: Top-kセレクションは、データベース、情報検索、信号処理、およびスパースアクティベーションやアテンションプルーニングを含む現代の機械学習ワークロードを対象とする、基本的な計算プリミティブである。
データサイズが大きくなると、既存のアプローチは非効率になる: 正確なメソッドは高いメモリと計算オーバーヘッドを発生させるが、近似メソッドは敵の入力や重み付き入力で劣化する不安定なヒューリスティックに依存することが多い。
本稿では,確率論的正当性保証を備えた高速でスケーラブルで分布に依存しないトップkアルゴリズムであるProf-Kを紹介する。
小さいランダムサンプルは適応しきい値を推定し、N入力要素は一度コンパクトなバッファにストリームされ、このバッファ上の正確なトップkルーチンは、少なくとも1〜$ε$の確率で真のトップk要素を復元する。
我々は,Nとkの関数としてオーバーヘッドを最小限に抑える,ほぼ最適なサンプルサイズとともに,精度とバッファサイズを高い確率で保証する。
Prof-K は高度に最適化された PyTorch トップクと最近の RadiK の実装に対して1.5x-10x の高速化を実現している。
従来のアプローチとは異なり、これらの保証は入力分布とは独立に保持され、敵の設定に対する堅牢性を保証する。
リコールターゲット(例えば、真のトップk値の95%を回収する)を緩和することにより、Prof-Kは原理化された精度-速度トレードオフを提供する。
BatchTopK Sparse Autoencoders (SAE) のトレーニングへの影響をさらに示す。
関連論文リスト
- No-Regret Bayesian Optimization with Finite-Library Input-Warped Kernels [1.2432856108679675]
本研究では,有限個のスムーズな入力マップのライブラリから履歴に依存したルールでワープを選択するFLIWBO(Finite-Library Input-Warped Bayesian Optimization)を提案する。
高確率収束保証を維持しながら、入力幾何学に適応して学習を加速する。
制御された診断は、有限自由度ワープ修復が幾何ミスマッチを植え付け、FLIWBO故障例を同定したことを示している。
論文 参考訳（メタデータ） (2026-09-02T16:04:07Z) - BAPE: Learning an Explicit Bayes Classifier for Long-tailed Visual Recognition [78.70453964041718]
現在のディープラーニングアルゴリズムは通常、後部確率を簡易に推定することで最適分類器を解く。
この単純な手法は、厳密にバランスのとれた学術ベンチマークデータセットに有効であることが証明されている。
しかし、これは現実世界の長い尾のデータ分布には適用できない。
本稿では,データ分布のより正確な理論的推定を行う新しい手法(BAPE)を提案する。
論文 参考訳（メタデータ） (2025-06-29T15:12:50Z) - One Sample is Enough to Make Conformal Prediction Robust [53.78604391939934]
共形予測は, 1つのランダムな摂動入力に対して前方通過しても, ある程度の堅牢性が得られることを示す。
提案手法は,入力毎に多数のパス(例えば100回程度)を使用するSOTA法と比較して,平均セットサイズが小さいロバストな集合を返す。
論文 参考訳（メタデータ） (2025-06-19T19:14:25Z) - Robust Conformal Prediction with a Single Binary Certificate [58.450154976190795]
コンフォーマル予測(CP)は、任意のモデルの出力を、真のラベルを(調整可能な)高い確率でカバーすることを保証した予測セットに変換する。
我々は,MCサンプルが著しく低い場合でも,より小さな集合を生成する頑健な共形予測を提案する。
論文 参考訳（メタデータ） (2025-03-07T08:41:53Z) - Learning the Optimal Stopping for Early Classification within Finite Horizons via Sequential Probability Ratio Test [11.199585259018459]
時系列の早期分類に最適な停止時間を提供するSPRT(Sequential Probability Ratio Test)による、時間に敏感な機械学習の利点。
入力長が有限である有限地平線シナリオでは、後ろ向きの誘導を必要とするため、最適停止規則を決定することが計算集約化される。
本稿では,SPRTベースのフレームワークであるFIRMBOUNDを紹介する。
論文 参考訳（メタデータ） (2025-01-29T23:54:46Z) - Equation Discovery with Bayesian Spike-and-Slab Priors and Efficient Kernels [57.46832672991433]
ケルネル学習とBayesian Spike-and-Slab pres (KBASS)に基づく新しい方程式探索法を提案する。
カーネルレグレッションを用いてターゲット関数を推定する。これはフレキシブルで表現力があり、データ空間やノイズに対してより堅牢である。
我々は,効率的な後部推論と関数推定のための予測伝搬予測最大化アルゴリズムを開発した。
論文 参考訳（メタデータ） (2023-10-09T03:55:09Z) - Efficient Few-Shot Object Detection via Knowledge Inheritance [62.36414544915032]
Few-shot Object Detection (FSOD) は、未確認のタスクに少ないトレーニングサンプルで適応できるジェネリック検出器を学習することを目的としている。
計算量の増加を伴わない効率的なプレトレイン・トランスファー・フレームワーク(PTF)のベースラインを提案する。
また,予測された新しいウェイトと事前訓練されたベースウェイトとのベクトル長の不整合を軽減するために,適応長再スケーリング(ALR)戦略を提案する。
論文 参考訳（メタデータ） (2022-03-23T06:24:31Z) - Scalable Uncertainty Quantification for Deep Operator Networks using
Randomized Priors [14.169588600819546]
ディープ・オペレーター・ネットワーク(DeepONets)における後続不確実性定量化のための単純かつ効果的なアプローチを提案する。
我々は,ランダム化前のアンサンブルに基づく頻繁なアプローチを採用し,高速化ハードウェア上での高速並列推論のための効率的なベクトル化実装を提案する。
論文 参考訳（メタデータ） (2022-03-06T20:48:16Z) - Transformers Can Do Bayesian Inference [56.99390658880008]
我々はPFN(Presideed Data Fitted Networks)を提案する。
PFNは、大規模機械学習技術におけるインコンテキスト学習を活用して、大規模な後部集合を近似する。
我々は、PFNがガウス過程をほぼ完璧に模倣し、難解問題に対する効率的なベイズ推定を可能にすることを示した。
論文 参考訳（メタデータ） (2021-12-20T13:07:39Z) - Efficient Model-Based Collaborative Filtering with Fast Adaptive PCA [4.878057307346225]
高速適応ランダム化特異値分解(SVD)を用いたモデルベース協調フィルタリング(CF)手法を提案する。
適応型PCAのための新しい終端機構を提案し, ほぼ最適な予測精度を達成するための複数の潜時因子を自動決定する。
提案したモデルベースCFアプローチは,20MレーティングでMatlab MovieLenデータを効率的に処理し,正規化因数分解に基づくアプローチよりも10倍以上のスピードアップを示す。
論文 参考訳（メタデータ） (2020-09-04T15:32:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。