🤖 AI

Spanning Tree Autoregressive Visual Generation

本論文は、一様全域木の巡回順序を利用することで、高いサンプリング性能と柔軟なシーケンス順序の両立を実現し、それによって大幅なアーキテクチャの変更を必要とせずにネイティブな画像編集機能を可能にする視覚生成手法である、Spanning Tree Autoregressive (STAR) モデリングを導入する。

原著者： Sangkyu Lee, Changho Lee, Janghoon Han, Hosung Song, Tackgeun You, Hwasup Lim, Stanley Jungkyu Choi, Honglak Lee, Youngjae Yu

公開日 2026-07-03

📖 1 分で読めます☕ さくっと読める

CC BY 4.0

原著者： Sangkyu Lee, Changho Lee, Janghoon Han, Hosung Song, Tackgeun You, Hwasup Lim, Stanley Jungkyu Choi, Honglak Lee, Youngjae Yu

原論文は CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) でライセンスされています。 ✨ これは以下の論文のAI生成解説です。著者が執筆または承認したものではありません。技術的な正確性については原論文を参照してください。免責事項の全文を読む

ロボットに絵を描く方法を教えようとしていると想像してください。ただし、一度に一つの小さな正方形（「パッチ」）ずつ、モザイク画を埋めていくように進めなければなりません。ロボットは、すでに描いた正方形に基づいて、次の正方形にどの色を塗るべきかを推測する必要があります。

これが、**自己回帰（Autoregressive / AR）モデルの仕組みです。この論文が取り組んでいる大きな問いは、「ロボットはどのような順番でこれらの正方形を塗るべきか？」**ということです。

問題点：「一方通行」 vs 「混沌としたシャッフル」

この論文では、既存の2つの手法を特定していますが、どちらにも欠点があります。

ラスタースキャン（一方通行の道）:
- 仕組み: ロボットは左上隅から描き始め、右端まで進み、次に一段下がり、再び左から右へと進みます。まるで本を読む時のようです。
- 良い点: 非常に効率的です。順番が決まっているため、ロボットは素早く学習できます。
- 悪い点: 硬直しています。もし画像の特定の場所を変更したい場合（例えば、真ん中にある猫を消して犬に変えたい場合）、ロボロットは混乱してしまいます。決まった一本道のルールに縛られているため、簡単に「振り返ったり」、穴の周りを塗ったりすることができません。それは、本の最初から最後までしか書くことが許されていない状態で、文章の途中のタイポ（誤字）を修正しようとするようなものです。途中で修正するには、ページ全体を書き直さなければなりません。
ランダム置換（混沌としたシャッフル）:
- 仕組み: この硬直性を解決するために、他の研究者たちは順番を完全にシャッフルすることを試みました。時には左上を描き、次に右下、次に真ん中、というように、完全にランダムな順序で描きます。
- 良い点: 非常に柔軟です。ロボットは画像のどの部分からでも描き始めることができ、編集に適しています。
- 悪い点: 非効率的です。順番がランダムであるため、ロボットは学習に苦労します。それは、文章の中の単語がバラバラな言語を学ぼうとしているようなものです。ロボットは迷子になり、最終的な画像はぼやけたり、品質が低下したりすることがあります。

解決策：「全域木（Spanning Tree）」（組織的な探索者）

著者らは、STAR (Spanning Tree Autoregressive) と呼ばれる新しい手法を提案しています。彼らは、「一方通行」の学習速度と、「混沌としたシャッフル」の柔軟性の、両方の良いとこ取りを目指しました。

イメージとしては、画像を都市のグリッド（格子状の街）と考えてください。
直線的に進む（ラスタースキャン）のでもなく、ランダムにテレポートする（置換）のでもなく、ロボットは地図を持った探索者のように振る舞います。

地図（全域木 / Spanning Tree）: ロボットは、自分の通り道を二度と通らず、かつどの正方形も置き去りにすることなく、すべての正方形を一度ずつ訪れる単一の連続した経路を描きます。これが「全域木」と呼ばれるものです。
ルート（出発点）: 探索者は、ランダムに選ばれた都市の角（左上、右上など）から必ず出発します。
経路（幅優先探索 / Breadth-First Search）: 探索者はただ目的もなく彷徨うわけではありません。彼らは**幅優先探索（BFS）**という戦略を用います。これは、出発した角から外側に向かって、層（レイヤー）ごとに都市を探索していくことを意味します。すでに描いた正方形のすぐ隣にある正方形をすべて描き、次にその外側のリングを描き、という具合に広がっていきます。

なぜこれが魔法のようなのか？

「局所的」な知識を維持できる: 探索者は隣接する正方形を優先して進むため、ロボットは「隣同士は関係がある（木の枝は幹の隣にある）」ということを学習します。これは人間の視覚の仕組みを模倣しており、「一方通行」と同様にロボットの学習を加速させます。
「中心」への偏りを利用できる: 論文では、興味深いもの（顔や動物など）は通常画像の中央にあり、角の部分は空白であることが多いと指摘しています。ランダムな角から始まり、内側へと進むことで、ロボットは自然に面白い部分へと向かって構築していくことができ、これが学習をより良くします。
編集が可能: 経路が「木」の構造であるため、もし画像の一部を「消去」する必要（穴を作る必要がある場合）があっても、ロボットはその穴の端で一旦止まり、残りの木を塗り続けることができます。ロボットは立ち往生しません。それは、建設中のエリアを避けて、道が分岐しながら進んでいけるようなものです。

「棄却サンプリング」のトリック

論文では、画像を編集したい時に使う巧妙なトリックについても触れています。ランダムに描かれた木が、どうしても埋めたい特定の穴に対して完璧に機能しない場合があります。

これは、パズルのピースをはめ込もうとするようなものです。
もしロボットが描いた経路が、穴を埋めることを不可能にするものであった場合、ロボットは「いや、この経路はダメだ」と言って、新しい木を描き直します。これを（「棄却サンプリング」と呼ばれる手法を用いて）非常に素早く行い、穴を完璧に埋めることができる経路が見つかるまで繰り返します。論文では、これが作業をほとんど遅らせることなく、極めて高速に行われることを示しています。

結果

著者らは、大規模な画像データセット（ImageNet）を用いてテストを行いました。

品質: STARによって生成された画像は、既存の最高水準のモデルと同等の鮮明さと高品質を持ち（「混沌としたシャッフル」モデルよりも優れていました）、非常に高い精度を示しました。
編集: 硬直したモデルとは異なり、STARは画像の一部を容易に編集（インペインティング）でき、画像が崩れることもありませんでした。
シンプルさ: 彼らは巨大で複雑な新しい「ロボットの脳」を作る必要はありませんでした。ただ、ロボットが画像の中を「歩く経路」を変えただけなのです。

まとめのアナロジー

古い方法1（ラスター）: 固定されたルートを歩く郵便配達員。速いですが、通りに到達するまで、ブロックの真ん中の家に手紙を届けることはできません。
古い方法2（ランダム）: ランダムに家々へテレポートする郵便配達員。柔軟ですが、迷子になりやすく、誤配も多くなります。
STAR: クモの巣のような経路を持つ郵便配達員。端から始まり、外側へと広がっていきながら、すべての家を訪れます。もし家が建設中（編集が必要）であれば、その建設エリアを避けて歩き、探索を続けます。彼は近所のレイアウトを完璧に理解し、あらゆる配達依頼を効率的にこなすことができます。

論文は、「画像の歩き方」という単純な変更だけで、高品質な画像生成と容易な編集の両立というトレードオフを解決できると主張しています。

技術要約：Spanning Tree Autoregressive Visual Generation (STAR)

問題提起

デコーダーのみのTransformerに基づく自己回帰（AR）モデルは、言語生成において目覚ましい成功を収めており、次パッチ予測を通じた視覚的生成への適用も進んでいる。しかし、従来のAR視覚モデルは通常、固定されたラスタースキャン順序（一方向の依存関係）に依存している。この順序はサンプリング性能には優れているが、構造的な制限を課すことになる。すなわち、定義されたシーケンスの接頭辞（prefix）として現れないトークンに対して、モデルが条件付けを行うことができない。この硬直性は、画像の任意の領域をマスクし、残りのコンテキストに基づいて補完する必要があるネイティブな画像編集（例：インペインティング）において、障害となる。

これに対処するため、最近のアプローチでは、モデルに多様な順序を学習させるために、トレーニング中にトークンシーケンスのランダム置換を採用している。しかし、本論文では、任意のシーケンス順序を用いたトレーニングは、固定ラスタースキャンモデルと比較してサンプリング性能の低下を招く可能性があると指摘している。これにより、トレードオフが生じる。すなわち、固定順序は高い性能を提供するが柔軟性に欠け、ランダム置換は柔軟性を提供するが生成品質と収束速度を犠牲にする。

手法：Spanning Tree Autoregressive (STAR)

著者らは、画像パッチの位置によって定義される格子状のグラフ上の一様生成木（Uniform Spanning Trees: UST）の走査順序を利用することで、このギャップを埋める構造化されたシーケンス順序のランダム化戦略であるSTARを提案する。

1. 一様生成木による構造的ランダム化

$N!$ 個の置換空間からサンプリングする代わりに、STARは、頂点がパッチ位置を表す正方格子 $G=(V, E)$ 上の一様生成木からサンプリングを行う。

ルートの選択: 画像のランダムなコーナーがルートノード $r$ として選択される。この選択は、ラスタースキャン順序（コーナーから開始する順序）が他の順序よりも優れた性能を示すことが多いという観察に基づいている。これは、おそらく中心バイアス（顕著な物体はコーナーに現れにくい）および局所性（隣接するパッチは予測しやすい）によるものである。
走査順序: シーケンス順序 $\tau$ は、サンプリングされた生成木の**幅優先探索（BFS）**走査によって決定される。
理論的根拠: 著者らは、既定のシーケンスが有利である理由は、事前知識（中心バイアスと局所性）を保持しているためであると仮定している。これを検証するために条件付きモデルエントロピーを測定したところ、トークンが（木における距離において）以前に予測されたトークンに近いほど、エントロリが低くなることを示しており、これはラスタースキャンの挙動と同様であった。生成木の数は指数関数的に増大する（ $\sim \exp(N \cdot z_G)$ ）が、全置換空間と比較すると、より小さく構造化された部分集合となっている。

2. 推論とポストフィックス補完（画像インペインティング）

ARモデルにおけるインペインティングの重要な課題は、与えられた部分的な観測（非マスク領域）がシーケンス順序において**接頭辞（prefix）として現れるようにし、マスクされた領域を後置辞（postfix）**として生成できるようにすることである。

拒絶サンプリング: 接頭辞と後置辞の分離が自明であるランダム置換とは異なり、STARは、BFS走査が自然に非マスク領域をマスク領域よりも前に配置するような生成木をサンプリングしなければならない。
アルゴリズム:
1. 非マスク領域の境界を特定する。
2. 非マスク領域の最も近い境界からのマンハッタン距離が最大となるルートノード $r$ を選択し、非マスク領域が最初に訪問される確率を最大化する。
3. 非マスク領域に対して生成木をサンプリングする。もし木の最大深度が、すべての境界頂点が任意のマスク頂点よりも前に訪問されるという条件を満たさない場合、そのサンプルは拒絶される（拒絶サンプリング）。
4. 非マスク領域に対して有効な木が見つかったら、マスク領域に対して生成木をサンプリングし、それらを境界頂点に接続してグローバルな木を完成させる。
効率性: 著者らは、「最も遠いルート」の選択を用いたBFSの使用が、DFSと比較して拒絶試行の回数を大幅に減少させ、推論を効率化することを実証している。

3. モデルアーキテクチャ

STARは、標準的なデコーダーのみのTransformerアーキテクチャに対して最小限の変更しか必要としない。以下を組み込んでいる：

因果的アテンションマスク。
前述の置換ベースの手法と同様に、次トークンの位置に条件付けるための追加特徴量（学習可能な位置エンベディングを使用）。
複雑なアーキテクチャの変更（双方向アテンションや特殊なトークナイザなど）は不要である。

主な貢献

構造化されたランダム化戦略: AR視覚生成のためのシーケンス順序として、一様生成木のBFS走査を使用することを提案。この戦略は、画像の前駆体（画像プライア：中心バイアス、局所性）を構造的に保持しながら、柔軟性のための十分なランダム性を導入する。
性能と柔軟性のトレードオフ: BFSによるUSTの走査が、（任意の置換に伴う典型的な性能低下を伴わずに）ランダム置換の利点（多様なシーケンス順序）を達成するのに十分であることを実証した。これは、トレーニングの複雑さを増やすことなく実現されている。
ネイティブな画像編集のサポート: 最小限のアーキテクチャ変更で、領域レベルの修正（インペインティング）を可能にするメカニズム（BFSを用いた拒絶サンプリング）を導入し、従来のARモデルの主要な制限に対処した。

実験結果

著者らは、クラス条件付き生成および画像インペインティングタスクにおいて、ImageNet-1k（解像度256x256）を用いてSTARを評価している。

画像生成: STARモデル（STAR-B, L, XL, XXL）は、Fréchet Inception Distance (FID) および Inception Score (IS) の観点から、最先端モデル（例：RAR, DiT, LlamaGen）に匹敵する性能を達成している。特筆すべきは、STAR-XXLがFID 1.55を達成し、RAR-XXL (1.48) や RandAR-XXL (2.15) と比較しても競争力のあるスコアを維持しつつ、優れた性能を示した点である。
画像インペインティング: STARは、インペインティングタスクにおいて、固定順序モデル（RAR）およびランダム置換モデル（RandAR）の両方を大幅に上回る。
- 様々なマスキング比率（0.1から0.9）において、STARは高いFIDとISスコアを維持している。
- 対照的に、RAR（固定ラスタースキャン）は、任意のマスクを接頭辞として自然に扱うことができないため、インペインティング性能が著しく低下する。
- RandARはインペインティング能力を維持しているが、STARと比較して生成品質が低い。
アブレーション研究:
- 局所性: ランダム置換はSTARを上回ることができず、局所性を損なうシーケンス順序は収束に悪影響を与えることが示唆された。
- 中心バイアス: ルートとしてランダムにコーナーを選択することは、強い中心バイアスを持つ画像においてうまく機能し、中心バイアスが弱い画像に対してもランダム置換より優れた汎化性能を示す。
- エントロピー分析: STARで訓練されたモデルは、ランダム置換と比較して、トークンの位置にわたってより一様なスケールの条件付きモデルエントロピーを示し、これが良好な収束と相関している。
- オーバーヘッド: 生成木のサンプリングにかかる計算オーバーヘッドは無視できる程度である（全推論時間の < 0.0004%）。インペインティングのための拒絶サンプリングは非常に効率的であり、通常、BFSを用いれば5回未満の試行で済む。

重要性と主張

本論文は、STARが、AR視覚生成におけるサンプリング性能とシーケンス順序の柔軟性の間の長年のトレードオフに対する、シンプルかつ効果的な解決策を提供すると主張している。一様生成木の構造的特性を活用することで、STARは以下のことを実現する：

デコーダーのみのTransformerアーキテクチャを保持し、初期融合マルチモーダルモデルへの統合を容易にする。
順序アニーリング（トレーニング中にランダムから固定順序へ切り替える手法）や特殊なトークナイザのような複雑なトレーニング戦略を回避する。
生成品質を犠牲にすることなく、**ネイティブな画像編集（インペインティング）**のサポートを提供する。

著者らは、STARを将来のAR視覚モデリングのための「基本的な構成要素（basic building block）」として位置づけており、そのシンプルさがマルチモーダル生成モデルへの容易な採用と拡張を可能にすることを強調している。本研究は、ARモデルの成功は単なるモデルアーキテクチャだけでなく、視覚データの固有の特性に適合するようにシーケンス順序を構造的にランダム化することに依存していることを示唆している。