title: >- [Paper Note] Spanning Tree Autoregressive Visual Generation description: >- [ECCV 2026][Image Generation][Autoregressive Models] STAR introduces uniform spanning tree BFS traversal on lattice graphs as a structured sequence randomization strategy for visual autoregressive models, preserving image locality and center bias while enabling native inpainting via rejection sampling. tags: - ECCV 2026 - Image Generation - Autoregressive Models - Image Inpainting - Spanning Tree date: 2026-09-19 content_hash: b25372e5629d1811

Spanning Tree Autoregressive Visual Generation¶

Conference: ECCV 2026
Paper: ECCV Official
Code: https://github.com/oddqueue/star
Area: Image Generation
Keywords: autoregressive visual generation, uniform spanning tree, breadth-first search, image inpainting, permutation AR

TL;DR¶

STAR models the image patch grid as a taxicab lattice and employs breadth-first search (BFS) traversal orders of corner-rooted uniform spanning trees as a structured sequence randomization strategy, preserving intrinsic locality and center bias for high sampling fidelity while natively supporting flexible postfix completion for image inpainting via rejection sampling.

Background & Motivation¶

Autoregressive (AR) modeling based on Decoder-only Transformer architectures via next-token prediction has achieved tremendous scalability and generation quality in natural language processing. When extended to visual generation, conventional approaches discretize an image into a 2D grid of patch tokens and flatten them into a 1D sequence using a fixed raster-scan order. Although this fixed unidirectional ordering naturally adheres to spatial locality and corner-to-center propagation—yielding fast optimization convergence and superior generative fidelity—it imposes a rigid structural limitation. Because causality is strictly tied to a single predefined scan, the model cannot condition on arbitrary spatial contexts that do not appear as prefixes, making interactive region-level editing and inpainting fundamentally incompatible with native inference.

To circumvent the unidirectional bottleneck, recent permutation AR paradigms (such as RandAR) randomly shuffle token sequences during training and feed target spatial coordinates as next-token conditioning, exposing the Transformer to diverse sequential trajectories. However, unconstrained random permutations sample from an enormous space of \(N!\) orders, almost all of which completely dismantle the 2D geometric topology. Without contiguous local contexts, predicting isolated patches across arbitrary hops causes dramatic spikes in conditional model entropy and severely degrades optimization convergence, leaving permutation AR models with substantially worse generation FID compared to raster-scan baselines under matched training budgets.

The core tension in visual autoregressive modeling lies in providing sufficient sequence flexibility for arbitrary region-level editing without forfeiting the essential 2D image priors—specifically locality and center bias—that make autoregressive modeling effective. The authors resolve this dilemma by shifting from unconstrained permutations to uniform spanning trees over the image lattice. Core idea: train the autoregressive Transformer on BFS traversal orders of corner-rooted uniform spanning trees on the image lattice, structurally preserving locality and center bias while exploiting BFS depth monotonicity through rejection sampling to natively achieve prefix-conditioned image inpainting.

Method¶

Overall Architecture¶

STAR frames the \(h \times w\) image patch token grid as a regular taxicab lattice graph \(G = (V, E)\), where each patch position \((i, j)\) represents a vertex \(v \in V\) and edges connect horizontally and vertically adjacent patches. During training and unconditional generation, the model randomly designates one of the four image corners as the tree root \(r\) and samples a uniform spanning tree \(T \sim \mathcal{T}(G, r)\) using Wilson's algorithm. A breadth-first search (BFS) traversal of \(T\) yields a 1D sequence order \(\tau_s\). The standard Decoder-only Transformer is trained via next-token prediction along \(\tau_s\), conditioned on the next-token spatial coordinates via learnable position embeddings. During downstream inpainting, a rejection sampling routine configures the unmasked regions to appear strictly as the prefix and masked regions as the postfix, executing seamless completion without architectural modifications.

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    A["Image Patch Discretization<br/>Construct Lattice Graph G=(V,E)"] --> B["Uniform Spanning Tree Sampling<br/>Select Corner Root r & Run Wilson Algorithm"]
    B --> C["BFS Traversal Order Extraction<br/>Depth-first propagation preserving locality"]
    C --> D["Autoregressive Transformer Prediction<br/>Causal Mask + Next-Token Coordinate Embeddings"]
    D --> E["Dual Inference Modes"]
    E -->|Class-Conditional Generation| F["Token-by-Token Sampling along Tree Traversal"]
    E -->|Region-Level Image Inpainting| G["Prefix-Constrained Rejection Sampling<br/>Unmasked as prefix, masked as postfix"]

Key Designs¶

1. Uniform Spanning Tree Traversal: Balancing Sequence Randomness with Geometric Priors Unconstrained permutation AR distributes training probability over all \(N!\) orderings, introducing frequent non-local jumps where predicting disjoint tokens without adjacent support causes sharp increases in conditional entropy. In contrast, the number of spanning trees on a regular lattice graph asymptotically scales as \(\exp(N \cdot z_G)\) (with \(z_G \approx 1.166\) for 2D taxicab lattices), offering an exponential variety of generation paths while rigorously restricting sequential dependencies to connected subgraphs. Sampling is carried out in \(O(N \log N)\) time using Wilson's loop-erased random walk algorithm. By rooting the spanning tree at a randomly selected corner node \(r\), the sequential traversal inherently advances from the peripheral image borders inward toward the central region, faithfully respecting the natural center bias where salient objects predominantly reside.

2. BFS Traversal Monotonicity & Rejection Sampling: Native Postfix Completion for Inpainting To execute image inpainting, the sequence order must guarantee that all vertices in the unmasked partial observation \(V \setminus V_M\) precede the masked vertices \(V_M\), acting as prefix \(\tau_\text{pre}\) and postfix \(\tau_\text{post}\) respectively. A Depth-First Search (DFS) imposes an excessively strict constraint, requiring that the single last-visited vertex in the unmasked tree touches the mask. By contrast, Breadth-First Search (BFS) operates level-by-level across tree depths. The condition for postfix completion is satisfied whenever the maximum-depth vertices \(V_{G'}^\text{max}\) of the unmasked subtree \(T_{G'}\) intersect the boundary \(B_i\) adjacent to the masked region:

\[\text{depth}_T(v_M) \ge \text{depth}_T(v), \quad \forall v \in V \setminus V_M, \; v_M \in V_M\]

At inference time, the algorithm selects the corner farthest in Manhattan distance from the mask boundary as root \(r_{G'}\), samples the unmasked spanning tree with rejection until this boundary-depth criterion is met, and independently connects a spanning tree within the masked component \(M_i\). This guarantees depth increments and allows flawless causal prefix conditioning without retraining or fine-tuning.

3. Minimalist Causal Transformer Adaptation: Non-Invasive Scalability STAR preserves the standard Decoder-only Transformer backbone with causal self-attention. To indicate which 2D coordinate on the lattice is currently being predicted, the architecture incorporates a learnable next-token 2D positional embedding alongside token content and sequence-step embeddings, mirroring the conditioning convention of RandAR and \(\sigma\)-GPT. The optimization objective optimizes the negative log-likelihood over BFS traversal trajectories of sampled uniform spanning trees:

\[\mathcal{L}_\text{STAR}(\theta) = - \mathbb{E}_{\tau \sim \tau(\mathcal{T}(G, r))} \left[ \sum_{i=1}^N \log p_\theta(x_{\tau_i} \mid x_{\tau_{<i}}) \right]\]

This design bypasses specialized bidirectional attention masking or complex multi-stream routing, directly inheriting the scaling efficiency of autoregressive language backbones.

Loss & Training¶

The model is trained end-to-end using standard cross-entropy loss against discrete token targets provided by a MaskGIT-VQGAN tokenizer (downsampling factor 16, codebook size 1024, yielding \(16 \times 16 = 256\) tokens on \(256 \times 256\) images). Training runs on ImageNet-1k using the AdamW optimizer with a linear warmup and cosine learning rate decay over 250k steps with a total batch size of 2048 (approximately 400 epochs). Standard ten-crop data augmentation and classifier-free guidance (dropout probability 0.1) are applied. During sampling, a Power-Cosine CFG scheduler is used without top-\(k\) or top-\(p\) filtering.

Key Experimental Results¶

Main Results¶

On class-conditional image generation at \(256 \times 256\) resolution on ImageNet-1k, STAR is compared against leading diffusion models (DiT), fixed raster-scan AR models (LlamaGen, RAR), scale-wise AR models (VAR), and permutation AR models (RandAR), as documented in Table 1:

Model Type	Model	# Params	FID (↓)	IS (↑)	Precision (↑)	Recall (↑)
Diffusion	DiT-XL/2	675M	2.27	278.2	0.83	0.57
Raster-scan AR	LlamaGen-XXL	1.4B	3.09	253.6	0.83	0.53
Raster-scan AR	RAR-B	261M	1.95	290.5	0.82	0.58
Raster-scan AR	RAR-XL	955M	1.50	306.9	0.80	0.62
Raster-scan AR	RAR-XXL	1.5B	1.48	326.0	0.80	0.63
Block-wise AR	VAR-d30	2.0B	1.92	323.1	0.82	0.59
Randomized AR	RandAR-XL	775M	2.25	314.2	0.80	0.60
Randomized AR	RandAR-XXL	1.4B	2.15	322.0	0.79	0.62
Randomized AR	STAR-B	261M	2.24	295.3	0.82	0.57
Randomized AR	STAR-L	461M	1.98	322.0	0.82	0.58
Randomized AR	STAR-XL	955M	1.65	333.2	0.80	0.62
Randomized AR	STAR-XXL	1.5B	1.55	338.8	0.81	0.62

Ablation Study¶

Ablations on sequence order randomization and order annealing strategies under the Base model configuration budget (Table 3 of the paper), and evaluation across inpainting tasks averaged over mask ratios from 0.1 to 0.9 (Table 2 of the paper):

Table 1: Ablation on Sequence Randomization Strategies (Paper Table 3)

Training Start	Training End	Inference Order	Gen. FID (↓)	Gen. IS (↑)	Inpaint FID (↓)	Inpaint IS (↑)	Note
Raster-scan	Raster-scan	Raster-scan	2.04	266.5	3.91	82.7	Standard unidirectional baseline
Permutation	Permutation	Permutation	3.57	291.4	2.57	108.7	Unconstrained RandAR strategy
Permutation	Permutation	Spanning Tree	3.58	234.9	2.43	105.8	Permutation training + tree inference
Permutation	Spanning Tree	Spanning Tree	2.31	285.2	2.35	107.9	Annealing permutation to spanning tree
Spanning Tree	Spanning Tree	Spanning Tree	2.24	295.3	2.39	108.8	STAR default strategy

Table 2: Image Generation vs. Inpainting Across Masking Ratios (0.1–0.9 Avg, Paper Table 2)

Model Type	Model	# Params	Gen. FID (↓)	Gen. IS (↑)	Inpaint FID (↓)	Inpaint IS (↑)
Diffusion	DiT-XL/2	675M	2.27	278.2	4.58	50.4
Raster-scan AR	RAR-XL	955M	1.50	306.9	3.40	88.2
Randomized AR	RandAR-XL	775M	2.25	314.2	2.58	60.3
Randomized AR	STAR-XL	955M	1.65	333.2	2.07	111.3

Key Findings¶

Simultaneous Mastery of Generation and Inpainting: Fixed-order models like RAR-XL reach a low generation FID of 1.50 but fail drastically on inpainting (FID degrades to 3.40). RandAR-XL supports inpainting (2.58) but sacrifices generation quality (2.25). STAR-XL resolves this trade-off, attaining a generation FID of 1.65 and an inpainting FID of 2.07 with an Inception Score of 111.3.
Rejection Sampling Efficiency: As shown in Table 4 of the paper, BFS with the farthest-root heuristic requires fewer than 5 trials on average across all mask ratios (4.41 trials at 0.1 masking, 1.15 trials at 0.9 masking) with a 0.0% failure rate (within a 100-trial budget). In stark contrast, DFS suffers an 82.3% failure rate and requires 89.37 trials at a 0.1 ratio.
Negligible Algorithmic Overhead: Generating a uniform spanning tree via Wilson's algorithm and extracting the BFS ordering takes merely 0.56 ms per sample, which accounts for less than 0.0004% of the total inference compute.

Highlights & Insights¶

Bridging Graph Theory and Visual Autoregression: Instead of wavering between the extreme constraint of a single raster-scan path and the unmanageable entropy of \(N!\) random permutations, STAR identifies spanning trees on lattices as the mathematically sound intermediate set of size \(\exp(N \cdot z_G)\) that encapsulates both stochastic diversity and topological contiguity.
BFS Depth Monotonicity as a Causal Sieve: The elegant realization that BFS depths strictly constrain causal prefixes enables effortless inpainting via rejection sampling, eliminating the need for specialized multi-stage decoding or heuristic boundary patching.
Direct Utility for Early-Fusion Multimodal Models: Because STAR does not alter standard Transformer causal masking or layer structures, its sequence construction can directly empower early-fusion multimodal models (such as Chameleon) with native, bidirectional-like visual region manipulation.

Limitations & Future Work¶

Topological Masking Assumptions: The rejection sampling formulation assumes that the unmasked region forms a connected subgraph and does not cover all four lattice corners. Complex, disjoint, or border-spanning masks require fallback virtual bridges or multi-component graph adaptations.
Discrete Tokenizer Quality Ceiling: The current implementation is bound to discrete VQGAN tokenizers; extending STAR to continuous representations via diffusion loss or flow matching (as in MAR) represents a compelling frontier for higher fidelity.
Scalability to Dense Feature Resolutions: While Wilson's algorithm is \(O(N \log N)\), moving to high-resolution latent spaces (e.g., \(64 \times 64\) patch grids) may increase tree depth variance and warrant accelerated rejection heuristics for intricate masking shapes.

vs RAR (Randomized Autoregressive): RAR employs random permutation strictly as a pretraining pretext task before annealing to raster-scan order, which restores generation quality but discards inpainting flexibility at test time. STAR maintains spanning tree traversal throughout, eliminating annealing hyperparameter tuning while keeping native inpainting intact.
vs RandAR: RandAR adopts fully unconstrained permutations during training, which spikes conditional entropy and degrades generation quality. STAR bounds the permutation space to lattice spanning trees, outperforming RandAR-XL in generation FID (1.65 vs. 2.25) and inpainting FID (2.07 vs. 2.58).
vs VAR (Visual Autoregressive): VAR organizes visual tokens in a coarse-to-fine hierarchy across resolution scales with multi-scale tokenizers and block-causal attention. STAR achieves competitive generation fidelity using a single-scale, standard Transformer backbone with graph-based sequence shuffling.

Rating¶

Novelty: ⭐⭐⭐⭐⭐ Formulates visual autoregressive sequence ordering via uniform spanning trees on lattice graphs, presenting an exceptionally elegant theoretical foundation.
Experimental Thoroughness: ⭐⭐⭐⭐⭐ Rigorously evaluated across generation, inpainting, conditional entropy metrics, representation linear probing, and rejection sampling complexity.
Writing Quality: ⭐⭐⭐⭐⭐ Clear mathematical formulation, comprehensive ablations, and well-structured empirical analyses.
Value: ⭐⭐⭐⭐⭐ Delivers an immediately applicable, minimally invasive sequence paradigm for Transformer-based visual generation and multimodal editing.