申し訳ございませんが、その件につきましてはお手伝いできません。

背景

「キャプチャ・ザ・フラッグ」スタイルの機械学習パズルは、黒箱ニューラルネットワークを与えてその挙動を推測するものが多いです。
昨年初めに自分たちでMLパズルを作ろうと考えたとき、少し違ったやり方を試したかったのです。
完全なニューラルネットワーク（重みも含む）をユーザーに渡し、機械的解釈技術（mechanistic interpretability）のツールを使って逆推理させる――これは自分たちが複雑モデルの特徴を解釈する研究で直面する状況と似ていました。

パズルは昨年2月に公開しました。最初は解けるかどうかもわからなかったのです。設計したネットワークはほぼすべての入力に対して 0 を出力します。合理的な解答者は「1 やその他非ゼロ値を出す入力」を求めると仮定するでしょう。しかし、私たちはネットワークをこう設計しました――後で説明しますが――従来の手法（例えば逆伝播でノンゼロ出力を入力層まで追いかける）では解決できないようにしたのです。実際に何をしているのか考える必要があります。

パズルに対する反応は驚くほどでした。偶然的に難易度がちょうどよかったのでしょう――誰も解けないほど難しくなく、逆に簡単すぎて回答が殺到しなかったのです。実際、このパズルを解ければ、Jane Street で働くのに相応しい方だと言えます。

以下では問題文を再掲します。ただし、ここ以降には大きなスプライヤーが含まれています。自分で挑戦したい場合は目を逸らしてください。この投稿は実際に解いた人が辿った過程をすべて示しています。

問題

今日ハイキング中にネオリティックな墓丘の下に隠されたテンソルの山を発見しました！それを地元のニューラル・プランバー（神経回路技術者）に送ったところ、こういうものができました。

model.pt

まだ何をしているかは不明ですが、この古代文明にとって重要だったようです。まず最後の二層を見てみましょう。

モデル入力

vegetable dog

モデル出力

0

もし解けたら教えてください。

この

model.pt

解法

始め方

大学のシニア、アレックスは寮で眠っているとき、Twitter で話題になっているパズルを知る室友から聞かされました。室友自身も試したものの、二晩で諦めてしまったそうです。アレックスは学期末に何かやりたいことがなく、見てみることにしました。

まずモデルをダウンロードし、特に最後の層を調べました：

import torch
model = torch.load('./model.pt')
linears = [x for x in model if isinstance(x, torch.nn.Linear)]

すぐに分かりました。これは普通のニューラルネットワークではありませんでした――重みは整数値で、学習済みではなく、人手で設計されたものです。

最後の層は 48×1 の行列ですが、実際には三つのセクションに分割されていました。さらに前層の活性化も常に同じものを三回繰り返していたようです。倒数第二層は同じ重みが三回コピーされており、バイアスは 16 バイトずつ増加していました――まるでベクトル v を、次に v+1, v+2 とエンコードしたようです。倒数第二層の重みとバイアスはこうでした：

px.imshow(linears[-1].weight.detach())
px.imshow(linears[-2].bias.detach().unsqueeze(0))

これを見て、最後の層が 1 ビットだけ出力することから、倒数第二層の ReLU が「二つの 16 バイト整数が等しいか」を判定しているとアレックスは推測しました。仕組みは入力ベクトル v（16 バイト）を参照値 x と比較し、

v−x−1

v−x

v−x+1

したがって質問は「どうやって倒数第二層の活性化を x に合わせるか？」ということに帰着しました。

ネットワーク本体の逆解析

アレックスは、もし最後で何らかの数値と比較しているなら、残りは大きな方程式だと考えました。ネットワークには多くの構造があるようです（2500 個の線形層のサイズをプロットすると分かります）：

px.line([l.out_features for l in linears])

そこで彼はさまざまなサブネットワークを調べ、依存関係を追跡しました。多くのグラフ構造に目を凝らす作業でした。

何時間もサブ回路を探し続けましたが、手で追うには複雑すぎると感じたため、次のアイデアを思いつきました。「これを線形計画問題として扱ってみれば？」
もちろん ReLU は非線形ですが、「この活性化が負か」を示す整数変数を追加することで整数線形プログラム（ILP）に落とし込めます。そこでアレックスは層を巨大な ILP に変換し、解決させました。

しかし進展はなく、次に変数数を減らす工夫をしました。多くの層が単なる恒等行列（identity）であることに気づきました。1500 層ほどで 80 % が入力をそのまま通していました。ネットワーク内の各ニューロンを DAG のノードとして扱い、入次数 1 で重みが 1 の場合はそれらを結合できると判断しました（整数値なので安全です）。さらに「すべての入力辺が正の重み」を持つノードに対しては ReLU が無意味になるため、その入力を子へ直接渡せます。二つのニューロンが同じ入力ベクトルを持っていれば統合し、子供を新しい結合ノードに再接続することもできます。この手順を繰り返すと ILP の規模は約 200 万ノードから 75 000 に縮小しました。

それでも solver は終了せずに進行していました。

最終的な削減

次のアイデアとして「境界値（bounds）をネットワーク全体で伝播させる」ことを試みました。各層を順番に解析し、入力の上限・下限からノードが取り得る最大値と最小値を計算します。保守的な仮定でも多くのノードは 0–1 のような非常に狭い範囲になりました。これで問題を SAT ソルバへ移行し、各ノードとその範囲内の値ごとにブール変数を作成しました。全体で約 200 000 変数になり、1 日かけて SAT ソルバが 20 000 変数まで削減しました。

しかし、結局も解決できず、ネットワーク内部には「不可逆的な複雑さ」が残っていることが分かりました。数日間の試行錯誤を経て、一歩引いて考え直すしかありませんでした。

解法へのヒント

アレックスは「メタ」思考に入りました――このパズルは解けるべきです。もし人間がランダムな重みで作れば、SAT ソルバは単純に探索できるでしょう。しかしここは人間が設計したネットワークなので、逆推理には不可逆的な関数が隠されていると感じました。

そこで ChatGPT に「よく使われるハッシュ関数」を尋ね、層幅の周期性（48 の長さで 32 回繰り返す）を確認しました。32 ブロック同士の計算が特徴的なハッシュ関数は MD5 を含め多く存在します。実際に手作業で入力文字列をネットワークへ入れ、MD5 の各バリエーションと比較し、倒数第二層のバイアスに一致するものは MD5 だけでした。

これにより「何のハッシュ関数か」が判明しました。問題は「その特定の MD5 ハッシュを出力する入力文字列を見つけること」でしたが、逆推理で保証できたわけではありません。さらにネットワークにバグがある可能性も疑われました。

ネットワークのバグ

アレックスは「入力長さが 32 を超えると正しい MD5 ハッシュが得られない」という奇妙な点を発見しました。何日かでそのバグを逆解析し、MD5 アルゴリズムの各変数に対応するニューロンを特定しました。最初の 7 層で入力長さを 4 バイト（リトルエンディアン）で保持しようとしますが、256 ビット以上になると正しいエンコードではなく「256」をそのまま入れてしまいます。たとえば実際は

128 1 0 0

384 0 0 0

このバグを利用できるか検討し、奇妙な長さ（55 種類）だけを試した結果、ネットワークの挙動がわかったものの、解に近づく手段は見つけられませんでした。メールで報告すると、「これは意図的ではない」と返答がありました。

最後の一歩：暴力的探索

最終的に判明したこと――倒数第二層のバイアスにエンコードされたハッシュ値を知れば、問題は解けるという点です。実際、パズル作成者はハッシュを「英単語二つ（小文字）＋スペースで連結」する形に簡易化していました。このヒントと大きな単語リスト（10,000 単語では足りず、より大きい辞書を使った方が良い）を組み合わせれば解答に到達できます。

もう一つのパズル

今回のパズルは層がシャッフルされたニューラルネットワークを正しい順序へ戻すというものです。もし興味があればぜひ挑戦してください。

Jane Street の研究チームで働く機会があります。GPU を数万台、ペタバイト級のトレーニングデータと最先端のリソースを活用しながら、最高のアイデアに投資できる環境です。

Ricson は 2020 年から Jane Street の研究デスクで働いており、余暇には天体写真撮影と言語モデルの研究を楽しんでいます。