🤖 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. “混乱洗牌”

该论文指出了现有的两种实现方式，两者都存在缺陷：

光栅扫描（Raster-Scan，即“单向街道”）：
- 工作原理： 机器人从左上角开始绘画，向右移动到行尾，然后向下移动一行，再从左向右移动，就像读书一样。
- 优点： 它非常高效。机器人学习得很快，因为顺序是可预测的。
- 缺点： 它很僵化。如果你想改变图像的特定部分（比如把中间的一只猫擦掉换成一只狗），机器人会感到困惑。它无法轻易地“回头看”或绕过空缺进行绘画，因为它被困在了这条单向线路上。这就像你想通过只能从头写到尾的方式来修改书中的句子；如果你想修改中间的一个错别字，你无法直接跳到中间去修复，而必须重写整个页面。
随机排列（Random Permutation，即“混乱洗牌”）：
- 工作原理： 为了解决僵化的问题，其他研究人员尝试完全打乱顺序。有时机器人先画左上角，然后画右下角，接着画中间，完全按照随机顺序进行。
- 优点： 它超级灵活。机器人可以先画图像的任何部分，这使得它非常擅长编辑。
- 缺点： 它效率低下。因为顺序是随机的，机器人很难学习。这就像是在学习一种语言，但每句话里的单词都是乱序的。机器人会迷失方向，最终生成的图像往往看起来很模糊或质量较低。

解决方案：“生成树”（The Spanning Tree，即“有组织的探索者”）

作者提出了一种名为 STAR（Spanning Tree Autoregressive，生成树自回归） 的新方法。他们想要兼得“单向街道”的学习速度和“混乱洗牌”的灵活性。

以下是他们富有创意的解决方案：

把图像想象成一个城市网格。
机器人不是沿着直线行走（光栅扫描），也不是随机传送（排列），而是扮演一名带着地图的探索者。

地图（生成树/Spanning Tree）： 机器人绘制一条单一且连续的路径，这条路径会访问城市中的每一个方块且仅访问一次，既不会交叉自己的路径，也不会遗漏任何方块。这被称为“生成树”。
根节点（起点）： 探索者总是从城市的某个角落（左上、右上等）开始，这个起点是随机选择的。
路径（广度优先搜索/BFS）： 探索者并不会漫无目的地游荡。他们使用一种叫做**广度优先搜索（BFS）**的策略。这意味着他们按层级探索城市，从起始角落向外扩散。他们先画完紧邻已完成方块的所有方块，然后是下一个环形区域，依此类推。

为什么这很神奇？

它保留了“局部”知识： 因为探索者优先移动到相邻的方块，机器人因此学会了邻居之间是有联系的（树枝就在树干旁边）。这模拟了人类观察世界的方式，帮助机器人学得更快，就像“单向街道”一样。
它保留了“中心”偏好： 论文指出，有趣的事物（如人脸或动物）通常出现在图像的中心，而角落通常是空白的。通过从随机的角落开始并向内推进，机器人自然而然地在构建出有趣的中心部分之前进行积累，这有助于它更好地学习。
它允许编辑： 因为路径是一棵树，如果你需要“擦除”图像的一部分（创建一个洞），机器人只需停在洞的边缘并继续绘制剩余的树结构即可。它不会卡住。这就像拥有一条可以绕过施工区域进行分支延伸的道路，而不会破坏整个路网。

“拒绝采样”的小技巧

论文提到了在你想编辑图像时的一个聪明技巧。有时，机器人绘制的随机树可能并不完美契合你想填补的那个“洞”。

这就像是尝试拼凑一个拼图碎片。
如果机器人画出的路径导致无法填补那个洞，它就会说：“不，这条路径行不通”，然后重新画一棵新的树。它会非常快速地（使用一种称为“拒绝采样”的方法）重复这个过程，直到找到一条能够完美填补空缺的路径。论文显示，这个过程极快，几乎不会减慢任何速度。

结果

作者在海量数据集（ImageNet）上测试了该方法。

质量： STAR 生成的图像与现有的最佳模型一样清晰、高质量（且优于“混乱洗牌”模型）。
编辑： 与僵化的模型不同，STAR 可以轻松编辑图像的部分（图像修复/inpainting），而不会导致画面崩坏。
简洁性： 他们不需要构建一个庞大复杂的机器人大脑。他们只是改变了机器人穿梭于图像中的“行走路径”。

总结类比

旧方法 1（光栅扫描）： 一个走固定路线的邮递员。很快，但如果他还没走到那条街，就无法递送该街区的信件。
旧方法 2（随机）： 一个随机传送去各个房屋的邮递员。灵活，但容易迷路，经常送错信件。
STAR： 一个拥有蜘蛛网路径的邮递员。他从边缘开始并向外扩张，访问每一户人家。如果某户人家正在装修（需要编辑），他只需绕过施工区并继续前进。他能完美掌握社区布局，并能高效处理任何递送请求。

论文声称，这种关于“如何穿梭于图像中”的简单改变，解决了生成高质量图像与实现轻松编辑之间的权衡问题。

技术摘要：跨度树自回归视觉生成 (STAR)

问题陈述

基于仅解码器（Decoder-only）Transformer 的自回归（AR）模型在语言生成领域取得了显著成功，并正越来越多地应用于通过下一补丁预测（next-patch prediction）进行的视觉生成。然而，传统的 AR 视觉模型通常依赖于固定的光栅扫描顺序（单向依赖）。虽然这种顺序能带来极高的采样性能，但它也造成了结构上的局式限制：模型无法对那些不出现在预定义序列前缀中的 token 进行条件化处理。这种僵化性阻碍了原生图像编辑（例如图像补全/inpainting），因为在图像编辑中，必须能够根据剩余的上下文来掩码并完成任意区域。

为了解决这一问题，近期的研究方法在训练期间采用随机排列（random permutation）token 序列，以使模型接触到多样化的顺序。然而，论文指出，使用任意序列顺序进行训练往往会导致采样性能下降（相比于固定的光栅扫描模型）。这产生了一种权衡：固定顺序提供了高性能但缺乏灵活性，而随机排列提供了灵活性但牺牲了生成质量和收敛速度。

方法论：跨度树自回归 (STAR)

作者提出了 STAR，一种结构化序列顺序随机化策略，通过利用定义在图像补丁位置上的格点（lattice）上的**均匀跨度树（Uniform Spanning Trees, UST）**的遍历顺序，来弥合这一差距。

1. 通过均匀跨度树实现的结构化随机化

STAR 并非从所有 $N!$ 个排列空间中进行采样，而是从规则出租车度量（taxicab lattice） $G=(V, E)$ 上的跨度树空间中进行采样，其中顶点代表补丁位置。

根节点选择： 选择图像的一个随机角作为根节点 $r$ 。这一选择是基于以下观察：光栅扫描顺序（从角开始）通常优于其他顺序，这可能是由于中心偏差（显著物体不太可能出现在角落）和局部性（相邻补丁更容易预测）。
遍历顺序： 序列顺序 $\tau$ 由所采样跨度树的**广度优先搜索（BFS）**遍历决定。
理论基础： 作者假设预定义序列的优势在于保留了先验知识（中心偏差和局部性）。他们通过测量条件模型熵验证了这一点，结果显示，在树距离上与先前预测的 token 更接近的 token，其熵也较低，这与光栅扫描的行为一致。跨度树的数量呈指数级增长 ( $\sim \exp(N \cdot z_G)$ )，但仍是一个比完整排列空间更小、更具结构的子集。

2. 推理与后置补全（图像补全/Inpainting）

对于 AR 模型在图像补全中的一个关键挑战是，确保给定的部分观测值（非掩码区域）在序列顺序中表现为前缀，从而允许掩码区域作为**后置（postfix）**被生成。

拒绝采样： 不同于随机排列（其中前缀/后置的分离是平凡的），STAR 必须采样一棵跨度树，使得 BFS 遍历自然地将非掩码区域置于掩码区域之前。
算法：
1. 识别非掩码区域的边界。
2. 选择一个根节点 $r$ ，该节点距离非掩码区域最近的边界在曼哈顿距离上最远，以最大化非掩码区域被首先访问的可能性。
3. 在非掩码区域内采样一棵跨度树。如果树的最大深度不满足“所有边界顶点在任何掩码顶点之前被访问”的条件，则拒绝该样本（拒绝采样）。
4. 一旦为非掩码区域找到了有效的树，则为掩码区域采样跨度树，并将其连接到边界顶点以完成全局树。
效率： 作者证明，使用带有“最远根节点”选择机制的 BFS 比深度优先搜索（DFS）能显著减少拒绝尝试的次数，从而使推理变得高效。

3. 模型架构

STAR 对标准的仅解码器 Transformer 架构要求极小的改动。它整合了：

因果注意力掩码（Causal attention masks）。
用于对下一个 token 位置进行条件化的附加特征（使用可学习的位置嵌入），类似于之前的基于排列的方法。
不需要复杂的架构变化（如双向注意或专门的分词器）。

核心贡献

结构化随机化策略： 提出使用均匀跨度树的 BFS 遍历作为 AR 视觉生成的序列顺序。该策略在引入足够的随机性以获得灵活性的同时，在结构上保留了图像先验（中心偏差、局部性）。
性能-灵活性权衡： 证明了使用 UST 的 BFS 遍历足以获得随机排列的优势（多样化的序列顺序），而不会出现通常与任意排列相关的性能下降。它在不增加训练复杂度的前提下实现了这一点。
原生图像编辑支持： 引入了一种机制（结合 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 训练的模型在不同 token 位置展现出更均匀的条件模型熵规模，这与更好的收敛性相关。
- 开销： 采样跨度树的计算开销微乎其微（< 0.0004% 的总推理时间）。用于补全的拒绝采样非常高效，使用 BFS 通常只需要少于 5 次尝试。

意义与主张

本文声称 STAR 为 AR 视觉生成中长期存在的采样性能与序列顺序灵活性之间的权衡提供了一个简单且有效的解决方案。通过利用均匀跨度树的结构特性，STAR：

保留了 仅解码器 Transformer 架构，便于集成到早期融合的多模态模型中。
避免了需要复杂的训练策略，如顺序退火（在训练期间从随机顺序切换到固定顺序）或专门的分词器。
在不牺牲生成质量的前提下，提供了原生的图像编辑支持（图像补全）。

作者将 STAR 定位为未来 AR 视觉建模的“基础构建模块”，强调其简单性使其能够轻松被采纳并扩展到多模态生成模型中。这项工作表明，AR 模型的成功不仅取决于模型架构，还取决于将序列顺序进行结构化随机化，以使其与视觉数据的内在属性相匹配。