# 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
- tokenベクトルに対してモデルの重みを掛ける行列計算を並列化できる
- attention scoreを計算する過程をtokenごとに並列化できる

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

| 箇所 | 並列化の方法 |
|---|---|
| 線形変換（`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が参照する前に書き込みを完了する必要がある。 |
