技術的概要：潜在部分順序推論のための微分可能なベイズ的緩和

問題定義

ランキング、エージェントのトレース、ワークフローに関連する多くのデータセットは、線形シーケンス（全順序）として記録されている。しかし、これらのシーケンスを支配する根本的な制約は、しばしば部分的に順序付けられている（部分順序集合：posets）に過ぎない。そのような設定において、観測された線形順序は、真の前提条件関係ではなく、任意の線形化、スケジューリング、またはログ記録のアーティファクトを反映している可能性がある。観測されたすべての先行関係を真の前提条件として扱うことは、特に複雑なワークフローや LLM エージェントの設定において、過度に逐次的で非現実的な構造をもたらす。不要な順序付けが冗長な実行ステップを誘発するためである。

核心的な課題は、これらのノイズの多い線形拡張から、潜在的部分順序を推論することである。ベイズ推論は、スパースまたはノイズの多いトレースに内在する不確実性を扱うのに自然であるが、既存の方法は深刻な計算ボトルネックに直面している。既存の「ハード PO（hard-PO）」アプローチは、部分順序の離散空間を探索するために、組合せ論的マルコフ連鎖モンテカルロ（MCMC）に依存している。部分順序の線形拡張を数える問題は #P-完全であるため、これは計算的に禁止されている。さらに、ハードな先行関係制約の不連続性により、効率的な勾配ベースの推論手法（勾配 MCMC や変分推論など）の使用が妨げられ、スケーラビリティが小規模なインスタンスに制限されている。

手法

著者は、離散的で組合せ論的な推論問題を、元のハードモデルのセマンティック構造を保持しつつ連続的な最適化問題へと変換する微分可能なベイズ的緩和を提案する。

1. 潜在積順序パラメータ化

部分順序を直接サンプリングする代わりに、モデルは埋め込み行列 $U \in \mathbb{R}^{M \times d}$ を用いて潜在構造をパラメータ化する。ここで、各アイテム $x$ には潜在ベクトル $u_x$ が割り当てられる。ハードな先行関係は、積順序を通じて定義される：すべての次元 $k=1,\dots,d$ に対して $u_{z,k} > u_{x,k}$ である場合かつその場合に限り、$z \succ_U x$ となる。これにより、（すべての次元で厳密に支配されていない場合の）非比較性を許容し、部分順序の幾何学を符号化する。

2. ハード制約の微分可能な緩和

勾配ベースの推論を可能にするため、著者は、ハードなフロンティア制約付き尤度の不連続な成分を、滑らかな代理関数に置き換える：

• ソフト先行関係: ハードなインジケータ $1[z \succ_U x]$ を、ソフトスコア $D_U(z, x) = \sigma(\gamma M_U(z, x))$ に置き換える。ここで、ハードな最小マージン $m_U(z, x) = \min_k (u_{z,k} - u_{x,k})$ はソフト最小関数 $smin_\tau$ によって近似され、インジケータは鋭敏度パラメータ $\gamma$ を持つシグモイド関数 $\sigma$ によって平滑化される。
• ソフトフロンティア: ハードなフロンティア（選択可能な最大要素の集合）を、ソフトフロンティア重み $\tilde{F}_t(x; U)$ に置き換える。この重みは、残りのすべてのアイテム $z$ に対する $(1 - D_U(z, x))$ の積であり、他者によって強く先行されているアイテムの重みを下げる一方で、フロンティア外の選択に対してもゼロでない確率を許容する。
• 緩和された尤度: フロンティア外のアイテムにゼロ確率を割り当てる元のフロンティアソフトマックス尤度を、フロンティア外のアイテムにも小さくてもゼロでない確率を割り当てる緩和版に置き換える。これにより、埋め込みパラメータ $U$ に関して連続的に微分可能な目的関数が得られる。

3. 理論的保証

本論文は、緩和に関するいくつかの理論的証明を提供する：

• ソフト推移性: 緩和されたスコアは、ソフト推移性 ($\text{logit } D_U(z, x) \ge \text{logit } D_U(z, y) + \text{logit } D_U(y, x)$) を満たし、平滑化パラメータが極限に近づくにつれてハードな推移性に収束する。
• 鋭い極限での回復: 温度 $\tau \to 0$ および鋭敏度 $\gamma \to \infty$ において、緩和されたフロンティア重みと尤度は、ハードなフロンティア制約付きモデルに収束する。
• 周辺一貫性: 緩和された部分順序上の事前分布は周辺的に一貫しており、部分順序上の分布がグローバルな分布と整合的であることを保証する。

4. 推論戦略

連続的な事後分布により、効率的な推論アルゴリズムの適用が可能となる：

• Relaxed-MCMC: 緩和された事後分布からサンプリングするために、ハミルトニアンモンテカルロ（NUTS）を使用する。
• FullRank-VI: フルランクのガウス近似を用いた自動微分変分推論（ADVI）を採用する。
• Flow-VI: ガウス近似よりも柔軟性を提供する事後分布のモデル化に正規化フローを利用する。

主要な貢献

1. 微分可能な緩和: 潜在部分順序推論のための微分可能なベイズ的緩和の導入。これにより、以前は離散的な組合せ探索に限定されていた問題に対して、勾配ベースの MCMC や変分推論の利用が可能になった。
2. 滑らかなフロンティア制約付き尤度: ハードモデルのフロンティアのセマンティクス（実行可能と非実行可能な行動を区別する）を保持しつつ、離散的な制約を連続的な代理関数に置き換える、滑らかな尤度の開発。
3. 理論的収束: 緩和されたモデルが鋭い極限においてハードモデルに収束し、ソフト推移性を示すことを証明する。
4. 実証的検証: 小規模インスタンスにおいて緩和された手法がハード MCMC と高い事後忠実度（ペアワイズ先行関係確率の平均絶対誤差で測定）を達成し、大規模問題において優れた実行時間と精度のトレードオフを提供することを示す包括的な実験。

実験結果

著者は、合成データ、司教の証人リストコーパス（歴史的社会的支配）、およびクラウドエージェントのトレース（LLM 生成ワークフロー）の 3 つのデータセットで手法を評価した。

• 合成データ: 最大 100 アイテムのインスタンスにおいて、緩和された手法（Relaxed-MCMC、FullRank-VI、Flow-VI）は、ハード MCMC の事後忠実度（ペアワイズ先行関係確率の平均絶対誤差で測定）とほぼ同等の結果を示しつつ、桁違いに高速であった。ハード MCMC は組合せ爆発により $n > 30$ で実行不可能となったのに対し、Flow-VI は $n=100$ まで効率的にスケーリングした。
• 司教コーパス: 45 人の登場人物を擁する 68 の証人リストにおいて、Relaxed-MCMC は最良の予測適合度（最低 WAIC）を達成し、Plackett-Luce 混合ベースラインを大幅に上回った。FullRank-VI は、70 分かかるハード MCMC と比較して 5.5 分で実行され、WAIC は同等でありながら、実用的なトレードオフとして最良であった。
• クラウドエージェントトレース: 54 のワークフロートレースにおいて、Relaxed-MCMC は構造回復（クロージャ F1）においてハード MCMC とほぼ同等の性能を示し、最良の予測性能（最低ステップ NLL）を達成した。FullRank-VI は強力な構造回復を伴う最速の推論を提供し、Flow-VI は構造回復がわずかに劣るものの、ハード MCMC よりも改善された予測較正を示した。

意義と主張

本論文は、この研究が、ハードな部分順序推論のセマンティックな正しさと、勾配ベース手法のスケーラビリティとの間のギャップを埋めるものであると主張している。離散的な制約を緩和することで、著者は以前は計算的に処理不可能であったデータセットに対する、潜在部分順序のベイズ推論を可能にした。

著者は、緩和された事後分布が単に速度のための近似ではなく、前提条件の解釈に不可欠なフロンティア制約のセマンティクスを保持する「それ自体で優れたモデル」であると強調している。また、この手法は $M=100$ までスケーリング可能であるが、ソフト先行関係行列の $O(M^2)$ 格納により、$M=200$ においてはメモリ制限に直面することを指摘している。本研究は、エージェントのトレースやワークフローにおいて解釈可能な構造を推論するための実用的な解決策として位置づけられており、計算コストの高い離散的な組合せ探索を誘発することなく、安定した前提条件と再順序化可能な行動を区別するものである。