(1D) Ordered Tokens Enable Efficient Test-Time Search

Tokenization is a key component of autoregressive (AR) generative models, converting raw data into more manageable units for modeling. Commonly, tokens describe local information, such as regions of pixels in images or word pieces in text, and AR generation predicts these tokens in a fixed order. A worthwhile question is whether token structures affect the ability to steer the generation through test-time search, where multiple candidate generations are explored and evaluated by a verifier. Using image generation as our testbed, we hypothesize that recent 1D ordered tokenizers with coarse-to-fine structure can be more amenable to search than classical 2D grid structures. This is rooted in the fact that the intermediate states in coarse-to-fine sequences carry semantic meaning that verifiers can reliably evaluate, enabling effective steering during generation. Through controlled experiments, we find that AR models trained on coarse-to-fine ordered tokens exhibit improved test-time scaling behavior compared to grid-based counterparts. Moreover, we demonstrate that, thanks to the ordered structure, pure test-time search over token sequences (i.e., without training an AR model) can perform training-free text-to-image generation when guided by an image-text verifier. Beyond this, we systematically study how classical search algorithms (best-of-$N$, beam search, lookahead search) interact with different token structures, as well as the role of different verifiers and AR priors.

When people ask an AI system to create an image, the result does not always fully match what they had in mind. One way to improve this is to let the system explore several possible directions as it generates the image, check which ones better match the request, and use that feedback to guide the final result. Our work asks: what makes this trial-and-check process, or search, effective? We find that the answer depends strongly on how the system represents an image. Many image-generation systems organize image information in a spatial layout, where intermediate results may not yet say much about the whole image. We study a different organization, where the representation goes from broad ideas to finer details. Because early steps are already meaningful at the level of the whole image, they are easier to check and guide. Our experiments show that this broad-to-detailed organization makes search more effective during image generation. Compared with spatially organized representations under comparable image-generation models, it leads to better results when using extra computation at generation time. Taking this idea further, we also show that reasonable images can sometimes be produced through search alone, by directly exploring ordered image pieces without training a full image-generation model.