The verifier side of speculative window decoding: a predictability bracket, a machine-checked blast-radius bound, and a decoder-agnostic recover loop

技術要約：投機的ウィンドウ・デコーディングにおける検証側（Verifier Side）

問題提起
リアルタイム量子誤り訂正（QEC）は、極めて深刻なレイテンシのボトルネックに直面している。シンドロームのラウンドは固定されたハードウェア・ケイデンス（超伝導量子ビットの場合、約1マイクロ秒）で到着するが、デコーダがそのペースに追いつけない場合があり、デコーディングが遅れることでシンドロームのバックログが増大し、論理状態がデコヒーレンスによって破壊される。 「ウィンドウ・デコーディング」はシンドローム履歴を並列化可能なチャンクに分割するが、隣接するウィンドウ間には依然として直列的な依存関係が存在する。すなわち、あるウィンドウでコミットされた訂正が、次のウィンドウのデコーディング問題の内容を決定してしまう。先行研究であるSWIPERやARTERYは、投機（speculation）を用いてこの直列的なボトルネックを解消しようと試みた。具体的には、境界を跨ぐ決定を予測することでダウンストリームのウィンドウを早期に開始させ、フル・デコーディングを遅延実行（lazy execution）して検証するという手法である。しかし、これらのシステムは予測器（predictor）の側面のみを実装しており（精度は約90%）、厳密な検証側（verifier side）が欠落していた。その結果、以下の4つの根本的な問いが未解決のまま残されていた：予測精度の理論的限界、誤予測による最悪の「ブラスト・ラジアス（影響範囲）」、予測のリスクを取る価値が（これらの限界を考慮しても）あるのか、そして、フル・「予測・検証・リカバリ（predict-verify-recover）」ループが実際にレイテンシを隠蔽し、正しくリカバリできるのか、という点である。

手法
著者らは、これらの問いに答えるため、Stim（回転表面符号）とPyMatching（最小重み完全マッチング、MWPM）を用いた再構成されたSWIPREハーネスを構築した。手法は以下の4段階で進行する：

1. 予測可能性の挟み撃ち（Predictability Bracketing）: 単一のヒューリスティックな予測器に頼るのではなく、半径$R$の局所MWPMデコーダを用いて、達成可能な精度の上限（天井）を確立した。このデコーダは、境界カットの$R$ラウンド以内のシンドロームデータのみを使用し、開いた境界をウィンドウ・デコーダと同様に扱う。これにより、与えられた局所情報から予測器が達成しうる理論的限界を挟み撃ちにする。
2. ブラスト・ラジアスの限定と反証: 誤予測（誤った依存ビット）がウィンドウ内をどのように伝播するかをモデル化した。まず、Lean 4を用いた機械検証済みの確率コアを用い、「誤予測には故障パス（faulty path）の存在が必要である」という減少仮説に基づき、最悪のケースにおける時間的境界を確立した。その後、鋭い単一ビット・アドバーサリ（敵対者）を用いたショットごとのテストを行い、この減少メカニズムを反証することで、仮説を厳密に検証した。
3. コンパイラ・パスの導出: 測定された予測可能性とブラスト・ラジアスを用いて、最適な再起動ポリシーを導出するためのコンパイラ・パスを開発した。このパスは抽象的なウィンドウ依存グラフ上で動作し、コストモデル $cost = predictability \times slack - blast\_radius$ に基づいて境界に投機フラグを付与する。
4. 実行時の実行とデコーダ非依存性: ハーネス上でフル・「予測・検証・リカバリ」ループを実行するためのランタイム・エグゼキュータを構築した。得られた知見がMWPMデコーダ特有のものか、あるいは投機フレームワーク自体に固有のものかを判断するため、著者らはアルゴリズム的に異なる第2のデコーダであるUnion-Findデコーダ（重みなしクラスター成長）を用いて主要な実験を再実行した。

主な貢献と結果

• 予測可能性は局所的であり、飽和に近い: 境界を跨ぐ決定は、カットの両側約3ラウンド分のシンドロームによって決定される。受容領域 $R=3$ の局所MWPMは、約0.999の精度を達成した。これは、従来の予測器（SWIPER）の精度（~90%）が根本的な限界ではなく、わずかながらも拡散した余地（コード距離に応じて0.019〜0.063）を残していたことを示している。
• ブラスト・ラジアスは1である（時間的封じ込め）: 誤予測が次のウィンドウへ伝播する最悪の確率は、コミット幅 $W$ に対して指数関数的に減少する。標準的な幅（$W=d$）において、伝播確率は論理エラー率よりも数桁低い（例：$d=7$ において $10^{-7}$ 対 $10^{-5}$）。これにより、時間的なブラスト・ラジアスは実質的に1であり、投機がエラーフロアを増大させないことが確立された。
• 故障パス・メカニズムの論破: Lean 4による証明は、「伝播には故障パス（反転したビットとカットを繋ぐエラーの連鎖）が必要である」という仮説に基づいていた。しかし、ショットごとの反証により、この仮説は偽であることが示された。つまり、伝播は反転したビットの近くに故障パスが存在しなくても日常的に発生する。真のメカニズムは**グローバルな最小重み再ペアリング（global minimum-weight re-pairing）**である。すなわち、デコーダが既存の欠陥を、局所的に吸収するよりも安価な方法として、反転したビットへと再ルーティングするのである。このメカニズムは、特に閾値付近のノイズにおける縮退（degeneracy）によって駆動される。
• 正確なリカバリとレイテンシ隠蔽: ランタイム・エグゼキュータは、フル・「予測・検証・リカバリ」ループが正確にリカバリすることを確認した。16個のウィンドウの連鎖において、システムは理論上の最大値である約16.00倍のスピードアップを達成し、無視できる程度の再起動ペナルティ（$\sim 10^{-5}$）を除いて、直列的なコミット・チェーンの停滞を取り除いた。
• デコーダに依存しない構造的現象学: 絶対的な精度の大きさや特定の「最小重み」メカニズムはデコーダに依存するが、構造的な知見は堅牢である。Union-Findデコーダを用いた実験も、カットの決定が局所的であること（$R=3$ で飽和）と、故障パスなしでの伝播が継続することを裏付け、投機用ラッパーの構造的な現象学を検証した。

意義と主張
本論文は、投機的ウィンドウ・デコーディングの欠けていた「検証側」を構築し、これを経験的なヒューリスティックから、厳密に境界付けられたシステムへと変貌させたことを主張している。その意義は以下の点にある：

1. 安全性の証明: 誤予測が半径1の範囲内に封じ込められ、機械検証済みの確率境界を持つことを示すことで、投機がエラーフロアを導入しないことを証明した。
2. メカニズムの解明: 直感的な「故障パス」モデルを正しい「グローバルな再ペアリング」メカニズムに置き換え、なぜ直接的なエラーの連鎖がなくても伝播が起こるのかを説明した。
3. 自動化の実現: 数値をハードコードするのではなく、測定された数値から再起動ポリシーを導出するコンパイラ・パスを提供することで、異なるコードレイアウトや制御スタックへの移植性を可能にした。
4. 再利用性: 「予測・検証・リカバリ」ラッパーを、任意のデコーダの上位に位置する再利用可能なレイヤーとして確立し、投機ロジックを特定のデコーディング・アルゴリズムから分離した。

著者らは、スピードアップの数値が解析的な線形鎖マップに基づいていること（完全なSWIPER-SIMパイプラインは公開されていないため）に触れ、範囲については慎重な姿勢を保っている。また、マッチング重みの境界（指数減少のソース）の定式化は、今後の課題として残されている。本研究は、再現可能なコードと機械検証済みの証明を用いた、再構成されたハーネスによって検証された、リアルタイムQECのための基礎的なレイヤーとして提示されている。