【Common Lisp】
スパゲッティコードとコンテキストの肥大化
（計算効率とメモ化）

by
  • ループの入れ子や複数の状態を同時に扱うコードは、読む側の脳に大きな負荷をかける。
  • 純粋関数は読みやすく信頼できるが、再計算コストを下げるために状態を持たせると複雑な依存関係が生まれる。
  • 生成AIのコンテキストも同じ構造で、情報が積み重なるほど応答の焦点がぼやけハルシネーションが増える。

関連記事

1. 頭がパンクするコード

ループの入れ子が深くなったコードを読んでいると、頭がパンクします。
どのループが何をしているのか把握しながら、全体の流れも見失わないようにしようとする。

(defun answers-optimized (initial M queries)
  (let* ((seq ...)
         (freqs ...)
         (phase3-start (* M max-freq))  ; ← 閾値の計算
         (pending ...)                  ; ← クエリのキュー
         (ans-table (make-hash-table))  ; ← 答えの保存先
         (index (length seq)))          ; ← 現在位置

    ;; 状態を4つ抱えたままループを回す
    (loop while (and pending (< index phase3-start))
          do (let ((next (least-frequent freqs M)))
               (vector-push-extend next seq)
               (incf (aref freqs next))
               (incf index)
               (when (= index (car pending))
                 (setf (gethash index ans-table) next)
                 (pop pending))))))Code language: Lisp (lisp)

脳に負荷がかかっている感じがして、ふと思いました。
これは、生成AIがコンテキストを詰め込みすぎたときの挙動に似ていないか、と。

1.1. 純粋関数は時間の外にある

純粋関数はテストしやすく、読みやすく、信頼できる。

具体的な例で考えてみます。
「1からMまでの数列があり、最も出現回数が少ない数を補充していく」というルールで数列を延ばし、クエリに答える問題です。

(defun answer-pure (initial M query)
  (aref (extend-to initial M query) (1- query)))

(defun answers-pure (initial M queries)
  (loop for q in queries
        collect (answer-pure initial M q)))Code language: Lisp (lisp)

answer-pureは引数だけで完結し、同じ入力には必ず同じ出力を返す。

関数型プログラミングが目指す参照透過性とは、同じ入力には必ず同じ出力を返すという性質です1。
状態を持たず、過去を引きずらない。
この種の美しさには、時間の外にあるという感覚があります。

1.2. メモ化で再計算を避ける

だが現実のプログラムはそう書けません。

読みやすく、テストしやすいのですが、クエリが100個来れば数列の構築を100回繰り返します。
同じ計算を何度もすることになります。

そこで、状態を持たせます。

(defun answers-cached (initial M queries)
  (let* ((seq ...)   ; ← 状態が生まれた
         (freqs ...)) ; ← 状態がふたつになった
    (loop for q in queries
          collect (progn
                    (loop while (< (length seq) q)
                          do (extend-one seq freqs M))
                    (aref seq (1- q))))))Code language: Lisp (lisp)

構築した数列seqと頻度ベクタfreqsを保持して使い回します。
これは「メモ化」と呼ばれる最適化手法で、純粋関数の参照透過性を保ちつつ再計算コストだけを下げる2。

1.3. 積み重ねが複雑な依存状態を作る

クエリが大量に来て、さらに効率を上げていて、生まれたのが冒頭のコードです。

seq、freqs、pending、indexの4つが同時に変化するループになり、ある行を読んだだけでは、その行が何に依存しているかわかりません。

indexが今どこにいるかをpendingと突き合わせながら、freqsを更新しつつans-tableに記録していく。
どれか一つを外に出すと残りの意味が変わるため、切れません。
読むためには4つの状態を頭の中で同時に動かす必要があります。

この暗黙の依存関係は、「後で使うため」という判断の積み重ねによって生まれたわけです。
全体を読まないと局所が理解できない、「立派」なスパゲッティコードの誕生です3。

2. 生成AIのメモ化コスト

コードがスパゲッティ化する起源は、「メモ」、つまり記憶に関係していました。
生成AIのコンテキストも同じ構造を持っているように感じます。

コンテキストとは、会話履歴の作業記憶です4。
会話の続きをするためには、そこまでのやり取りを保持しておく必要があります。

もし、毎回クリアしていたら、その度に時間とトークンが消費されます。
だから「覚えておく」という選択になります。

コンテキストの肥大化も同じ過程をたどります。
「会話を一区切りにせず、続きのために継続する」、これが積み重なると、AIモデルは何を優先すべきか拡散します。
情報の密度が下がり、応答の焦点がぼやける。
ハルシネーションが増えるのは、このようなコンテキストが肥大化したときです。

これは、さきほどのスパゲッティコードで、私の脳が処理の流れが見えなくなったのと、構造は同じです。

2.1. 逆U字の効率曲線と見えない閾値

ポイントは、状態の保持はある閾値までは効率を上げることです。

メモがあれば、コードは速くなり、会話は精度が上がる。
だが、ある閾値を超えると安定性が落ちます。
コード変更の影響範囲が読めなくなり、触るのが怖くなる。
AIの生成する応答は的外れになっていく。

特に厄介なのは、閾値を踏み越える瞬間がわからないことです。
コードは動き続けるから「まだ大丈夫」に見えます。
会話も破綻せずに続くから気づかない。
劣化がなだらかなため、閾値は事後にしか見えません5。
気づいたときにはすでに超えています。

3. スパゲッティコードに絡まれながら

このように考えたのは、状態を抱え続けるのにも合理性があるからです。

人間は、有限のリソースで動く存在です。
無限の計算資源があれば、毎回最初から再計算できますが、そうではない。
そこで、継続性と一貫性を保つために状態を必要とします。

コンテキストとは「続きをしたい」という意志が払うコストです。
プログラムが状態を持つのも、前回の計算を捨てたくないからです。

そう考えると、スパゲッティコードは、プログラマーの怠慢から生まれるわけではないのかもしれません。
有限な存在が、継続によって解決するため、状態を持つことの宿命的なコストが、コードの上に刻まれた形です6。

参照透過な関数の美しさは、時間を持たないことから来ています。
スパゲッティコードの読みにくさは、時間の中で生きることから来ている。

それは、欠陥ではなく、継続しようとした痕跡だと思うことにしましょう。

  1. 参照透過性はもともとWillard Van Orman Quineの哲学用語で、Christopher Stracheyが1967年の講義録でプログラミングに導入した。関数型プログラマーの文脈では「式をその値で置き換えてもプログラムの結果が変わらない」という意味で使われる。 – Referential transparency – Wikipedia
  2. メモ化（memoization）は、純粋関数の結果をキャッシュして同じ入力に対する再計算を省く技法。「memoization」という語はAI研究者のDonald Michieが造語した。純粋関数にのみ適用できる点が重要で、副作用のある関数には使えない。 – Memoization – Wikipedia
  3. スパゲッティコードという語はEdsger Dijkstraが1968年にACMへ送った書簡「Go To Statement Considered Harmful」に端を発する。GOTOによる無秩序な制御フローの跳躍がコードを「絡み合ったスパゲッティ」のように読みにくくすると批判し、構造化プログラミングへの転換を促した。 – Spaghetti code – Wikipedia
  4. LLMのコンテキストウィンドウは「作業記憶」に相当し、モデルが一度に参照できるトークン数を規定する。会話履歴をすべて保持することで連続した対話が成立するが、トークン数が増えるほど計算コストも上がる。 – What is a context window? – IBM
  5. LLMのコンテキスト肥大化による性能劣化は実測されている。NoLiMaベンチマークでは、32kトークンの時点で検証した12モデル中11モデルが短いコンテキスト時の50%以下のスコアに落ちた。また、アテンションメカニズムの計算コストはシーケンス長の二乗で増加するため、コンテキストが長いほど処理負荷も急増する。 – LLM Context Management: How to Improve Performance and Lower Costs
  6. Dijkstraはスパゲッティコードの原因をGOTO文そのものに帰したが、後続の研究者たちはより広く「開発者の思考様式」の問題と捉えている。長期間にわたって複数人が修正を重ねた結果として生まれることも多く、一人の怠慢というより継続的な開発の痕跡として現れる。 – GOTO has never gone away – Medium