Making LLM inference model with KV cache from scratch

Problem

Transformerで行列計算を行う様子をKV cache付きで実装する。 ここでは、自然言語的な出力の正確性などは一切考えず、単純に行列計算を高速化する方法に着目する。

How the algorithm/baseline code works

llm.cpp はC++17の標準ライブラリだけを使った逐次実装である。 固定seedでモデルの重みと入力トークンID列を生成する。 重みは未学習なので、出力するID列に自然言語としての意味は求めない。

  1. 埋め込みと位置情報:各トークンIDをベクトルに変換し、sin/cosによる位置情報を加える。
  2. Q/K/Vの計算:LayerNormでベクトルを正規化し、重み行列を掛けてQuery(Q)、Key(K)、Value(V)を求める。 Qは参照先を探すため、Kは照合のため、Vは取り出す情報を表す。 Q/K/Vの3つの変換と、各変換の出力成分は独立に計算できる。
  3. KV cacheの更新:現在のトークンのKとVを層ごとの配列に保存する。 過去のトークンは未来を参照しないため、過去のKとVは再計算せずに利用できる。
  4. Attention:ベクトルを複数のヘッドに分け、各ヘッドで現在のQと過去および現在のKとの内積を求める。 内積をヘッドの次元の平方根で割り、softmaxで重みに変換してVの加重和を計算する。 未来のトークンは参照しない。ヘッドごとの計算と、参照するトークン位置ごとのスコア計算を並列化できる。
  5. 出力変換とFFN:Attentionの結果を線形変換して元の入力に足す(残差加算)。 続いてLayerNorm、幅を4倍にする線形変換、GELU活性化関数、元の幅への線形変換、残差加算を行う。 この部分がFFNであり、トークンごとに適用するニューラルネットワークである。 線形変換の出力成分、GELU、残差加算に並列性がある。手順2〜5を層数分繰り返す。
  6. 次のトークンの選択:最後にLayerNormと語彙への線形変換を行い、各候補のスコア(logits)を求める。 最大スコアのトークンを選び、入力列に追加する。語彙候補ごとのスコア計算と最大値の探索も並列化できる。

入力列を最初に処理する段階を prefill、その後にトークンを1つずつ処理して続きを生成する段階を decode と呼ぶ。 現在のキャッシュ付きprefillは、入力を1トークンずつ順に処理する単純な方式である。 G個生成する場合、最初の1個はprefillの結果から選ぶので、decodeの計算はG−1回になる。

--mode cached では新しいトークンだけを各層で計算し、過去のK/Vを再利用する。 --mode recompute では生成のたびに入力列全体を再計算する。 --check は長さ1〜8の固定入力列で両方式の全logitsを比較し、 --mode both は両方式で生成したトークン列が一致するか確認する。 std::chrono でprefillとdecodeの時間を計測し、処理速度とKV cache容量も出力する。

Where is parallelism

具体的には、以下の箇所が並列化の候補になる。現在のコードは逐次版であり、並列化は今後行う。 複数の値の合計や最大値を求める際は、部分結果を並列に計算してからまとめる「リダクション」を利用できる。

箇所 並列化の方法
線形変換(Matrix::operator()) 出力成分ごとにCPUスレッドやGPUスレッドへ分担する。各成分の内積もSIMDやリダクションで計算できる。Q/K/V、Attention出力、FFN、語彙への変換に適用できる。
Q/K/Vの3つの変換 LayerNormの完了後、同じ入力からQ・K・Vを独立に計算できる。
Attentionの各ヘッド ヘッドごとの計算は独立している。並列化時には、現在使い回している score 配列をヘッドごとに用意する。
Attentionのスコア 現在のQと各位置のKとの内積を、参照するトークン位置ごとに並列計算できる。内積の成分方向の和にもリダクションを使える。
Softmax 最大値の探索と指数関数の値の合計はリダクションにできる。指数関数の計算と正規化は要素ごとに並列化できる。最大値、指数関数、合計、正規化の順序は守る。
Vの加重和 出力成分ごとに分担できる。参照位置方向に分割する場合は、同じ出力への同時加算を避けるため、部分和を最後にまとめる。
LayerNorm(norm) 平均・分散をリダクションで計算し、正規化を成分ごとに並列化する。現在の計算方法では平均、分散、正規化の順に処理する。
埋め込み・位置情報、GELU、残差加算 ベクトルの成分ごとの処理が独立しており、SIMDやGPUの要素ごとの処理に向いている。
次のトークンの選択(argmax) 語彙を分担して最大スコアとIDを求め、結果をまとめる。同点の場合は小さいIDを選び、現在の実装と同じ規則にする。
KV cacheへの書き込み K/Vやヘッド、成分ごとに異なる配列領域へ書き込める。Attentionが参照する前に書き込みを完了する必要がある。