Posts

FLASHATTENTION: Fast and Memory-Efficient Exact Attention with IO-Awareness (2022)

TransformerのQKV注意機構の時間、空間計算量は、系列長が$N$のときには$O(N^2)$になる。 Reformer: The Efficient TransformerなどのFLOP数を減らす手法はあるが、実際の処理時間を十分に短縮できず、普及していない。 FLASHATTENTIONは、FLOP数ではなく、GPUのHBM (high bandwidth memory) と SRAM間の転送量を減らし、処理時間を短縮する。 HBMの記憶領域はSRAMよりも数十倍大きいが、SRAMよりも数十倍遅い。注意 $\mathbf{O}$ を計算するとき、FLASHATTENTIONは、$\mathbf{Q}$, $\mathbf{K}$, $\mathbf{V}$, $\mathbf{O}$それぞれの一部の行ベクトルからなるブロックだけをSRAMに読み、$\mathbf{O}$の一部を更新し、計算した一部をHBMに書き込む。更新を繰り返すと最終的に自己注意機構と等しい注意を計算できる。

FLASHATTENTIONは逆伝搬時のHBMとSRAM間の転送量も減らす。通常のQKV注意機構であれば、$\mathbf{Q}$, $\mathbf{K}$, $\mathbf{V}$, $\mathbf{O}$の勾配を計算するためにSoftmax関数に与える行列$\mathbf{S}$とその結果$\mathbf{P}$を記録する。 $\mathbf{Q}$, $\mathbf{K}$, $\mathbf{V}$が$\mathbb{R}^{N\times d}$であれば$\mathbf{S}$と$\mathbf{P}$のサイズは$\textrm{O}(N^2)$になる。 FLASHATTENTIONは、順伝搬時に計算した中間結果と$\mathbf{O}$から$\mathbf{S}$と$\mathbf{P}$を計算し直すことで$\mathbf{S}$と$\mathbf{P}$の記録を省き、空間計算量を減らす。

#注意機構

December 29, 2025

Improving Language Understanding by Generative Pre-Training (2018)

Improving Language Understanding by Generative Pre-Trainingは教師なしの事前学習であり、GPTシリーズの最初のモデルにあたる。 12の自然言語処理タスクのうち9つについて、事前学習したモデルの出力を1層の全結合層に入力するファインチューニングで、当時のSoTAを上まわる性能を発揮した。

ネットワークは、transformerのデコーダーであり、Attention Is All You Needのエンコーダーは含まれない。ファインチューニングでは、特徴の入力を事前学習のデータ形式に揃えることで、事前学習とファインチューニングの差異を埋める。推論タスクであれば前提や仮定、テキストの類似性判定であれば比較する2つのテキストといった異種の特徴をデリミタで連結した系列を作り、モデルに入力する。

November 16, 2025 (Originally posted on August 7, 2020)

Deep Neural Networks for Youtube Recommendations (2016)

Deep Neural Networks for YouTube Recommendationsは2016年頃のYouTubeの推薦システムの解説であり、パラメタ数が10億の深層学習のモデルが使われている。この数千億の学習データで訓練されたモデルはcandidate generationとrankingの2つのネットワークからなる。 candidate generationは、ユーザーのYoutube上の行動履歴から数百の推薦候補の動画を協調フィルタリングで選び出す。協調フィルタリングは、視聴した動画のIDや検索クエリのトークンが要素のスパースなベクトルを連結し、ユーザーの埋め込みベクトルを作る。 rankingはcandidate generationで選ばれた動画の試聴時間を推定する。

September 23, 2025

Kademlia: A Peer to Peer Information System Based on the Xor Metric (2002)

peer-to-peerのファイル共有アプリケーション BitTorrentの分散ハッシュテーブルMainline DHTはKademliaをもとに実装されている。 Kademilaのノードやキーには160ビットのIDが割り当てられ、2つのIDの排他的論理和を両者の距離とみなす。ノードは、ノード内に保存されたIDに近い宛先に再帰的にRPCを送り、IDを検索する。

#Peer-to-Peer

September 13, 2025

Multi-probe consistent hashing (2015)

Karger et al.による原典のConsistent Hashingは、CDNやKVSのノードの負荷を分散するために、ノードとキーを単位区間のハッシュ値に写像し、ハッシュ値で比べたときの最近傍のノードにキーを割り当てる。ノードの追加と削除を繰り返してもキーの保存数が均等になるように、1つのノードに複数のハッシュ値を割りあてる。キーと最も近いハッシュ値のノードにキーを保存する。ノードの負荷をノードに保存するキーの数とすると、最大の負荷と平均の負荷の比率を高確率($1-\frac{1}{n^{\Omega(1)}}$)で$1+\epsilon$に抑えるには、$\Theta(\frac{\ln n}{\epsilon^2})$のハッシュ値を各ノードに割り当てなければならず、空間計算量はノードの数より大きくなる。

#Consistent Hashing

September 6, 2025

Infinispanの分散キャッシュ

Inifinispanは有償インメモリーデータベースRed Hat Data GridのOSSとして提供されており、OIDCによるSSOの機能を提供するKeyCloakでキャッシュサーバとして利用できる。 Red HatはKeyCloakの開発も支援している。

Infinispanの用途は、InifinispanはRESPプロトコルを実装しているなど、RedisやMemcachedと近い。公式ドキュメントでRedisやmemcachedを置きかえるユースケースを紹介されている。 Inifinispanは、Javaで実装されており、JavaのクライアントとJSR107のJCache APIで通信できる。たとえば、クライアントは、CacheManagerでハッシュマップ構造のCacheを取得し、エントリを操作できる。

August 23, 2025

Amazon.com Recommendations Item to Item Collaborative Filtering (2003)

IEEE Internet Computingは、創刊20周年を記念し、時の試練を越えた論文にAmazon.com Recommendations Item to Item Collaborative Filteringを選んだ。文献では、古典的な協調フィルタリングを、アイテム数次元$N$のベクトルでユーザーを表現し、類似するユーザーが選んだアイテムのうち、ユーザーが未選択のアイテムを推薦対象に選ぶ手法とみなされている。提案されたItem to Item Collaborative Filteringは、アイテム同士の類似度を示す$N$x$N$次元の行列をオフラインで構築し、$N$や全ユーザー数に依存しないオンラインの計算量で、ユーザーが過去に選んだアイテムに類似するアイテムを推薦できる。

#Collaborative Filtering

August 16, 2025

OUTRAGEOUSLY LARGE NEURAL NETWORKS THE SPARSELY-GATED MIXTURE-OF-EXPERTS LAYER (2017)

パラメタ数を増やせば多くの情報をモデルに学習させられるが、計算量も増える。 OUTRAGEOUSLY LARGE NEURAL NETWORKS: THE SPARSELY-GATED MIXTURE-OF-EXPERTS LAYER (MoE) は、ゲートと数千規模の全結合層からなる層であり、ゲートの後に全結合層を並列に配置する。ゲートは、サンプルごとに疎なベクトルを出力する。各サンプルの推論において、ベクトルの0でない要素に対応する全結合層だけを計算対象に限定し、パラメタ数の増加と計算量の抑制を両立する。

#Mixture-of-Experts

August 1, 2025

Training Language Models to Follow Instructions With Human Feedback (2022)

LLMはウェブページ上の次のトークンを予測できるように訓練される。指示に応じた出力になるようにLLMを訓練していないため、パラメタ数を増やしても、プロンプトに忠実で安全で便利な出力にできるとは限らない。 Training language models to follow instructions with human feedbackは、人間のフィードバックによる強化学習 (RLHF) により、プロンプトに対する望ましい順に順序づけられた出力で報酬モデルを訓練し、報酬モデルとPPOでGPT-3の方策を最適化した。 RLHFで訓練したパラメタ数1.3BのGPT-3 (InsturctGPT) の出力は、175BのGPT-3よりも人にとって望ましかった。

InstructGPTに採用したRLHFも、先行手法のDeep Reinforcement Learning from Human Preferencesのように、報酬関数のモデルを訓練する。なお、先行手法についても過去に記事にした。 InstructGPTのRLHFには、報酬関数のモデルを生成する前に、GPT3をファインチューニングする手順がある。このファインチューニングのための訓練データは、主にOpen AI APIで集めたプロンプトに40名の請負業者が適切な出力を書いて作成された。報酬モデルの学習データを集めるときは、ファインチューニングされたモデルにプロンプトを入力し、プロンプトに対する複数の出力を収集し、業者に良い順に出力を順序づけてもらった。プロンプトと順序つき出力を訓練データとして、スカラ値の報酬を出力する報酬モデルを訓練し、最後に、PPOで報酬モデルの出力に方策モデルを最適化した。

July 24, 2025

REACT: SYNERGIZING REASONING AND ACTING IN LANGUAGE MODELS (2023)

ReAct (Synergizing Reasoning + Acting) は、推論 (Chain of Thought) と行動 (Action) を織り混ぜた出力を促すプロンプトをLLMに与え、推論と行動両方の出力を改善する。推論は行動の立案に使える情報を提供し、行動はLLM外部の情報を推論に提供することで互いを補完する。

July 11, 2025