1D Ordered Tokens: The Key to "Reasoning-Style" Search in Image Generation

TL;DR

In the world of Large Language Models (LLMs), test-time search (like Chain-of-Thought or Beam Search) is a proven way to trade compute for intelligence. However, in image generation, traditional 2D grid tokens make this nearly impossible because a partial image (e.g., just the top-left corner) tells a verifier nothing. This paper proves that 1D ordered, coarse-to-fine tokenizers unlock efficient test-time scaling, allowing smaller models to beat larger ones and even enabling image generation without any model training at all.

The Problem: The "Raster-Scan" Blindness

Most autoregressive (AR) models for images (like LlamaGen or Janus) treat an image as a 2D grid. They generate pixels like a typewriter: top-left to bottom-right.

If you stop a 2D grid model 10% of the way through, you have a beautiful rendition of... the sky in the corner. You have no idea if the model is about to draw a "potted plant" or a "nuclear reactor" as requested. Because the intermediate states lack global semantics, verifiers (like CLIP) cannot provide useful feedback early on. This makes Beam Search—the bread and butter of NLP—useless for traditional image AR.

Methodology: Hierarchical Logic in 1D

The authors propose Search-over-Tokens (SoTo) using 1D ordered tokenizers (specifically FlexTok). These tokenizers use a technique called "Nested Dropout" to ensure that:

1. The 1st Token: Represents a global semantic cluster (e.g., "it's a food item").
2. Intermediate Tokens: Progressively add detail (e.g., "it's a donut" $\to$ "it's a glazed donut").
3. Decodability: Any prefix of the token sequence can be turned back into a valid, blurry-to-sharp image.

Figure 1: Comparison between 1D ordered tokens (coarse-to-fine) and 2D grid tokens (raster-scan).

By having semantically meaningful "readouts" at every step, a verifier can look at the first few tokens and say, "Stop! This doesn't look like a plant," and force the search algorithm to explore a different branch.

Experimental Results: Scaling Compute, Not Parameters

The most striking result is the Test-Time Scaling (TTS) behavior. While Best-of-N sampling (picking the best of 50 full images) works for both, Beam Search only works effectively for 1D ordered tokens.

• Efficiency: For a fixed compute budget, 1D ordered tokens consistently outperform 2D grids.
• The Pareto Frontier: A 530M parameter model with search can match or beat a 3.4B model without search. This suggests we can make generative AI much "smarter" during inference rather than just "bigger" during training.
• Zero-Shot Control: The SoTo framework allows for "training-free" control. By using a visual similarity verifier (DreamSim), the authors could force a text-to-image model to preserve the identity of a specific cat or object, even though the model was never trained on image-conditioned tasks.

Figure 2: Performance scaling with inference compute (NFE). Note how Beam Search (orange) accelerates for 1D tokens but flatlines for 2D grids.

Deep Insight: Search as Structured Retrieval

The paper provides a theoretical perspective: searching for tokens is like Nearest Neighbor Search in structured data. Just as a KD-Tree organizes data to make search faster, 1D ordered tokenization organizes image information along the "most informative" dimensions first (similar to PCA). This minimizes the "heuristic error"—the gap between what a partial image looks like and what the final image will be.

Conclusion & Limitations

This work shifts the focus of the community from how we sample to what we sample. By changing the token structure, we enable images to benefit from the same "System 2" thinking (deliberate search) that has revolutionized LLMs.

Limitations:

• Detokenization Cost: Current detokenizers (like the flow-based one in FlexTok) are slow when called repeatedly during search.
• Verifier Hacking: If you search too hard against a single verifier (like CLIP), the model starts creating weird artifacts that look good to the math but bad to the human eye.

Ultimately, SoTo proves that with the right token ordering, we don't need a massive model to get perfect images—we just need a small model that knows how to look before it leaps.