PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Zhitong Gao, Parham Rezaei, Ali Cy, Mingqiao Ye, Nataša Jovanović, Jesse Allardice, Afshin Dehghan, Amir Zamir, Roman Bachmann, Oğuzhan Fatih Kar

arXiv:2604.15453v1cs.CVcs.AIcs.LG

TL;DR

The paper asks whether token structure limits test-time search in autoregressive image generation. It compares coarse-to-fine 1D ordered tokenizers with 2D grids and systematically evaluates search, verifier, and prior choices. Ordered tokens show stronger test-time scaling and support training-free text-to-image generation through direct search.

  • Problem

    Existing test-time scaling work emphasizes search algorithms and verifiers, while giving less attention to model characteristics such as token structure.

  • Method

    The paper evaluates best-of-N, beam, and lookahead search across token structures, eight verifiers, and text-conditional, unconditional, or uniform autoregressive priors.

  • Results

    1D ordered tokenizers yield stronger test-time scaling than 2D grids and enable training-free text-to-image generation through direct search over ordered token sequences.

  • Takeaways & Limitations

    Token ordering is a mechanism for enabling effective test-time search, not solely a representational choice.

  • Takeaways & Limitations

    Generality remains uncertain because the analysis covers a relatively small set of models and architectures.

Abstract

from arXiv · show

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. Our results highlight the impact of token structure on inference-time scalability and provide practical guidance for test-time scaling in AR models.

1. Introduction

The paper asks whether token structure affects verifier-guided test-time search and argues that coarse-to-fine 1D ordered tokens make intermediate generations more semantically evaluable than 2D grids. Experiments show stronger scaling for ordered-token AR models and training-free generation through direct token search.

  • Motivation: The study examines how token structure affects autoregressive generation with verifier-guided test-time search.It focuses on image generation, where multiple candidates are explored and evaluated during inference.
  • Motivation: 1D ordered tokenizers provide coarse-to-fine sequences whose intermediate states carry semantic meaning for search.Their partial sequences support semantic evaluation and refinement, unlike tokens tied only to local spatial regions.
  • Contributions: Autoregressive models trained on 1D ordered tokens exhibit stronger test-time scaling than comparable models trained on 2D grid tokens.
  • Contributions: Direct search over ordered token sequences enables training-free text-to-image generation with an image-text similarity verifier.This removes the need to train an autoregressive model for the search procedure.
  • Contributions: The paper analyzes beam search, best-of-N sampling, lookahead search, verifiers, and autoregressive priors across token structures.

2. Background

This section introduces autoregressive generation and verifier-guided test-time search, then frames tokenization as a determinant of how searchable intermediate states are. It presents 1D ordered tokenizers as variable-length alternatives to conventional 2D grids.

  • Autoregressive generation: Autoregressive generation models discrete tokens through next-token prediction, optionally conditioned on context.
  • Test-time search: Test-time search selects token sequences by maximizing a verifier score over decoded images and conditioning context.The verifier compares decoded outputs with the relevant condition, while search approximates the constrained optimization.
  • Test-time search: Best-of-N, beam search, and lookahead search provide different strategies for approximating verifier-guided constrained optimization.
  • Test-time search: Test-time search trades additional inference compute for generation quality through verification.
  • Token structures: 1D ordered tokenizers encode images into flexible-length sequences, contrasting with standard fixed 2D grid tokens.They are typically trained with nested dropout so prefixes can be decoded into valid intermediate images.
  • Motivation: The paper argues that token structure defines the search space and determines how verifiable intermediate states are.

3. Coarse-to-Fine Ordered Token Structures are More Amenable to Search

Coarse-to-fine 1D ordered tokens make search effective because partial sequences encode global semantics that verifiers can evaluate. The section supports this claim through token visualizations, direct search experiments, and a theoretical connection between reconstruction quality and search error.

  • Motivation: 1D ordered tokenizers are hypothesized to impose a hierarchical coarse-to-fine structure that is more amenable to search.
  • Information density: Unlike a 2D grid’s local first token, FlexTok’s first token is trained to reconstruct the entire image and capture global semantics.
  • Information density: First-token reconstructions form coherent semantic clusters, while later tokens add increasingly fine-grained concepts.The visualized clusters include plants, bags, food, and furniture.
  • Pure search: Beam search directly over ordered tokens expands partial sequences and ranks decoded images using CLIP or ImageReward similarity to the text prompt.
  • Pure search: Progressively finer semantic and visual details emerge during direct search, whereas unordered or 2D tokens make exhaustive search computationally infeasible.
  • Interpretation: Ordered-token search can be viewed as structured nearest-neighbor search because earlier tokens capture the global semantics used by verifiers.
  • Theory: Under a Lipschitz verifier assumption, minimizing intermediate reconstruction error yields a tighter bound on the overall search gap.
  • Conclusion: Both empirical and theoretical results indicate that coarse-to-fine intermediate representations can be effectively evaluated by global-semantic verifiers.

4. Search-over-Tokens (SoTo) Framework

Search-over-Tokens (SoTo) combines token-space search, verifier scoring, and autoregressive priors to study inference-time scaling for image generation.

  • Search algorithm: SoTo evaluates best-of-N sampling, beam search, and lookahead search for exploring image token sequences.These strategies differ in how they exploit independent samples, partial hypotheses, or expanded rollouts.
  • Verifier: Verifiers guide search by scoring partial or complete decoded images for alignment and quality objectives.The framework includes image-text alignment, image-image alignment, image quality, and ensemble signals.
  • Autoregressive prior: The autoregressive prior constrains search toward likely next-token candidates, with guidance ranging from text-conditional to unconditional and uniform.These settings form a spectrum from strongest to weakest prior guidance.

5. Experiments

Experiments compare 1D ordered and 2D grid tokenizations across search strategies, model sizes, verifiers, and autoregressive priors. The results consistently favor ordered tokens for search-based scaling and training-free control.

  • Experimental setting: Controlled experiments match FlexTok and a 2D grid baseline in data, architecture, and training compute while evaluating three search algorithms.Evaluation uses COCO Karpathy validation images, with NFE measuring token-generation or verification evaluations.
  • Test-time scaling: Beam search produces markedly larger gains for 1D ordered tokens, whereas best-of-N and lookahead show similar scaling across tokenizations.The difference is attributed to semantically meaningful ordered prefixes versus weak intermediate signals in grid tokens.
  • Test-time scaling: 1D ordered tokenization achieves higher performance across inference budgets under each tokenizer’s best-performing search algorithm.The reported gap cannot be closed by search-algorithm choice alone, with consistent trends on GenEval.
  • Comparison with Janus: FlexTok exhibits stronger beam-search scaling than Janus despite Janus achieving slightly higher performance without search.For Janus, best-of-N slightly outperforms beam search across inference budgets.
  • Model scaling: The optimal model size increases with inference compute along a power-law relationship, while a 530M model can outperform a 3.4B model under greater test-time compute.The scaling analysis identifies a Pareto frontier with respect to inference FLOPs.
  • Zero-shot control: Search enables zero-shot image-guided control and improves FlexTok concept preservation by +18.4 on DINO-I while preserving prompt-following performance.Janus also improves, but by +5.9 on DINO-I, even with lookahead search.
  • Autoregressive priors: Uniform-prior search achieves 79% on single-object and 32% on two-object GenEval generation, demonstrating generation without an autoregressive prior is feasible.An unconditional prior improves performance, while the conditional prior performs best overall.
  • Verifiers: Search consistently improves verifier metrics, while an ensemble achieves the best overall average ranking across individual objectives.Individual verifiers perform best on their own objectives, and ImageReward and HPSv2 have the strongest average individual rankings.

6. Related Work

Related work covers image tokenization, test-time scaling, and ordered-token generation. This paper distinguishes itself by systematically studying how token structure interacts with search, verifiers, and autoregressive priors.

  • Image tokenization: Conventional image tokenizers use fixed 2D grids, while newer 1D ordered tokenizers encode global structure early and details later.FlexTok additionally supports semantically coherent reconstructions at variable prefix lengths.
  • Test-time scaling: Prior test-time scaling work uses additional inference computation and verifier-guided search to improve image-generation quality.The paper positions token-structure analysis as complementary to this line of work.
  • Positioning: This work reports that 1D ordered tokens are more amenable to search than 2D grid tokens and can support training-free image generation through direct search.It further studies interactions among token structure, search algorithms, verifiers, and autoregressive priors under controlled settings.

7. Conclusion and Limitations

The paper finds that coarse-to-fine 1D ordered tokens improve test-time search for autoregressive image generation, while identifying limitations in search design, verifiers, decoding, generality, modalities, and scaling.

  • Conclusion: 1D ordered tokenizers with coarse-to-fine structure are more amenable to search and support effective zero-shot control, including training-free image generation.The paper also analyzes interactions among search strategies, verifiers, and autoregressive priors.
  • Search algorithms: Generic search strategies are used mainly diagnostically, leaving efficiency and quality gains from hierarchy-aware, verifier-aware, and adaptive search as open opportunities.The current approaches allocate compute in a fixed manner.
  • Verifiers: Search quality is bounded by verifier reliability, with sufficient compute potentially enabling verifier hacking and global scalar feedback limiting fine-grained guidance.The paper identifies robust, interpretable verifiers as an important challenge.
  • Tokenizer and detokenization constraints: Flow-based detokenization requiring repeated denoising creates a computational bottleneck during search and makes effectiveness depend on intermediate decoding quality.Suggested directions include one-step detokenization, adaptive decoding schedules, and tokenizer designs that improve intermediate fidelity.
  • Generality across generation paradigms: Generality remains uncertain because experiments cover a relatively small set of models, despite validation across multiple ordered tokenization schemes and an alternative ordering paradigm.The paper proposes developing tokenization schemes that better leverage test-time scaling.
  • Extension to other modalities: The study focuses on image generation, leaving extension of ordered token structures to text, video, and multimodal generation for future work.Whether similar ordering improves search and controllability in those domains remains to be investigated.
  • Training-time vs. test-time compute: It remains unclear whether the benefits of increased inference-time search persist at larger scales, where reduced diversity or mode collapse may limit search effectiveness.Jointly optimizing training-time and test-time compute remains an open problem.

A. Additional Related Work

The related work situates verifier-guided search among classical search, reinforcement learning, controllability, and compute-scaling research. The paper presents token ordering as an orthogonal way to make image-generation search more effective and flexible.

  • Related context: The paper studies search-based inference in the context of classical search, reinforcement-learning-based generation, and established image-controllability methods.Its focus is image generation rather than a general evaluation across all modalities.
  • Search in AI and LLMs: The paper frames 1D ordered tokenizers as addressing the weak semantic structure and inefficient searchability of typical image-generation token sequences.Their coarse-to-fine intermediate states bring image generation closer to domains where search has proven effective.
  • RL-based training for image generation: Unlike reinforcement learning, inference-time search explores each instance and can target different objectives by swapping verifiers without retraining.The passage describes search and reinforcement learning as complementary approaches.
  • Controllability and verifiers in image generation: Verifier-guided search offers an orthogonal route to controllability by steering generation toward different objectives at inference time.The framework can benefit from stronger autoregressive models and more reliable reward models.
  • Training-time and test-time compute: The paper places its contribution within research that scales generative-model performance through both training-time and test-time computation.The related work discusses this tradeoff across board games, language models, and generative models.
  • Training-time and test-time compute: A smaller autoregressive model with sufficient test-time search can outperform a larger model without search, while direct search over ordered tokens can produce reasonable images without a trained AR model.These observations connect model size, prior strength, and inference-time compute.

B. Theoretical Analysis

The theoretical analysis links search performance to the quality of intermediate reconstructions: accurate partial decodes yield more reliable verifier guidance, favoring coarse-to-fine ordered tokens over grid tokens.

  • Search-gap bound: The paper formalizes that search gap through heuristic error and continuation suboptimality, with an autoregressive prior incorporable into the verifier objective.The resulting relation is Δ≤2B_t0+η_t0.
  • Setup: The analysis defines the search gap as the difference between the optimal verifier score and the score achieved by heuristic search.It also defines intermediate decoded images, continuation values, heuristic error, and continuation suboptimality.
  • Heuristic error: For an L-Lipschitz verifier, heuristic error is bounded by reconstruction error as B_t≤Lϵ_t.This connects the reliability of intermediate verifier estimates to intermediate-token reconstruction fidelity.
  • Combined bound: The combined bound links the search gap to tokenizer reconstruction discrepancy at the critical pruning step, and early stopping yields Δ≤2Lϵ_t0.Large-beam search can make continuation suboptimality small.
  • 1D ordered tokens: Nested dropout in 1D ordered tokenizers encourages reconstruction error to remain small and decrease rapidly as tokens reveal dominant global variance.The analysis relates this behavior to a PCA-like decomposition under a linear reconstruction assumption.
  • 2D grid tokens: Grid tokenization enforces reconstruction only at the complete sequence, so early prefixes leave large image regions unconstrained and can produce loose heuristic bounds.This weakens verifier guidance when t≪T.
  • Discussion: The discussion concludes that 1D ordered tokens provide progressively tighter early guidance, whereas 2D grids offer no comparable structural guarantee.Lookahead rollouts can partly mitigate heuristic error for grid tokens.
  • Search algorithms: Beam search expands partial sequences, verifies them during generation, and retains the most promising branches rather than evaluating only completed images.For ordered sequences, current prefixes can be directly detokenized; grid methods pad ungenerated locations with zeros.

C.2. Verifiers

The paper uses verifiers as search objectives that score partial or complete image token sequences across alignment, image similarity, quality, and ensemble settings. It also evaluates rule-based and likelihood-based signals, while fixing pretrained models and official sampling configurations across experiments.

  • Verifier framework: Verifiers guide search by assigning scores to partial or complete token sequences, often after detokenization into images.The framework includes a next-token prior when available and permits a uniform prior otherwise.
  • Verifier categories: Image–text alignment verifiers include CLIPScore, ImageReward, HPSv2, PickScore, CycleReward, likelihood scoring, and a rule-based verifier.These signals target semantic or prompt alignment from different modeling approaches.
  • Specialized verifiers: Likelihood-based verification requires accessible AR token probabilities, avoids detokenization, and remains limited by the AR model’s predictive capability and biases.The paper reports that this signal tends to yield only limited improvements in image quality or alignment.
  • Specialized verifiers: The Grounded-SAM verifier scores object existence, count, color consistency, and spatial relations from prompt-derived structured attributes.It uses GroundingDINO for text-conditioned boxes and SAM for segmentation masks; general use typically requires an LLM or VLM to parse free-form prompts.
  • Verifier categories: DreamSim provides image–image alignment by measuring perceptual similarity to a reference image.It is trained on human-labeled triplets and captures fine-grained texture and semantic similarity.
  • Verifier categories: The LAION Aesthetic Score measures visual appeal, clarity, composition, and style, complementing semantic verifiers by penalizing low-quality outputs.The paper also combines heterogeneous verifiers through rank-based aggregation to obtain more robust guidance.

D.3. Inference-Time Compute

Inference-time compute is measured with NFE while also distinguishing realized wall-clock cost. The experiments compare search methods and ordered-generation schemes, finding larger search gains for Semanticist and Infinity than for grid-based or weaker baselines in the reported settings.

  • Compute metrics: NFE counts each next-token sampling step and verifier call as one hardware-agnostic inference evaluation.Best-of-N uses NFEBoN = NT + N for N sequences of length T.
  • Search-cost accounting: Lookahead search rolls out each candidate by L steps before verification, but its simplified compute expression must be adjusted when rollout or skip lengths vary.The paper explicitly notes that L may change near sequence ends and s may vary under exponential verification schedules.
  • Search-cost accounting: NFE does not fully predict runtime because Best-of-N, beam search, and lookahead search have different component-level runtimes.The paper therefore reports wall-clock comparisons, verifier latency, and GFLOPs in complementary analyses.
  • Semanticist: +10.42 CLIPScore points for Semanticist versus +3.51 for LlamaGen under simple prompts, with similarly larger gains under complex prompts (+12.45 vs. +4.04).All search algorithms improve both models, but beam search produces the larger gain for the ordered 1D tokenizer.
  • Infinity: +6.2 CLIPScore points for Infinity over its autoregressive baseline, compared with +5.3 for Janus and +9.6 for FlexTok under matched COCO budgets.Infinity search begins at step 5 because its earliest four scales are too coarse for reliable verifier guidance.
  • Cross-scheme interpretation: The additional experiments support that search effectiveness varies with token structure and with how informative intermediate prefixes are to the verifier.The reported pattern extends beyond FlexTok to Semanticist and Infinity, while still showing different magnitudes of improvement.

E.3. Experimental Scale and Variance Analysis on COCO

The COCO analyses examine variance, runtime, and search hyperparameters across tokenizers and algorithms. Results remain consistent across larger subsets, while search-step and beam-width changes improve quality and shift the dominant computational cost toward detokenization.

  • Scale and variance: The 1D-versus-2D performance gap remains consistent when key beam-search evaluations scale from 300 to 1,000 COCO images.Variance across five random subsets is low in the reported analysis.
  • Runtime: Beam search and lookahead search increasingly spend runtime on detokenization as search steps grow, whereas Best-of-N is dominated by AR token generation.The paper reports wall-clock breakdowns to distinguish these costs from NFE.
  • Runtime: Verifier latency is under 25 ms for likelihood and aesthetic scoring, 40–60 ms for ImageReward, HPSv2, and CycleReward, and highest for Grounded-SAM.Across configurations, verifier cost is a negligible fraction of total inference time compared with AR generation.
  • FlexTok ablations: Increasing FlexTok beam width improves CLIPScore and ImageReward but slightly decreases Aesthetic Score.Increasing the number of search steps also consistently improves CLIPScore and ImageReward.
  • FlexTok ablations: FlexTok lookahead length L=32 performs best and is comparable to L=256, consistent with partial sequences of about 32 tokens already revealing semantic structure.The default configuration is presented as a lightweight and efficient setting, while larger hyperparameters can further improve performance.
  • Janus ablations: Janus benefits from larger beam-search settings, while L=128 and full lookahead achieve its best reported performance.The authors emphasize that lookahead is particularly important for 2D grid tokenizers whose early tokens provide limited semantic structure.

E.6. Additional Results on Verifier Analysis

Verifier analysis shows that verifier strengths are category-dependent, while combining complementary signals produces stronger and more stable search performance. Search trajectories also reveal distinct verifier preferences and the effects of different autoregressive priors.

  • Verifier performance: The verifier ensemble achieves the best overall accuracy among learned verifiers on GenEval, while individual verifiers specialize in different categories.Grounded SAM leads on Position and Color Attribute but performs worse on Single Object, Colors, and Counting; the official evaluator is an upper bound.
  • Verifier performance: On COCO, the verifier ensemble achieves the best average rank and is almost always the second-best method for individual metrics.The pattern is consistent with GenEval and supports combining complementary verifier signals.
  • Verifier dynamics: Optimizing most verifiers steadily improves their target scores and often improves other verifier scores as well.These cross-verifier gains suggest that many signals capture correlated aspects of visual quality or semantic alignment.
  • Verifier dynamics: ImageReward increases Aesthetic Score more strongly than CLIPScore or Grounded SAM, whereas the latter primarily drive semantic alignment.Grounded SAM also produces consistent gains across other verifier dimensions and saturates once spatial constraints are satisfied.
  • AR priors: The study compares conditional, unconditional, and uniform autoregressive priors during verifier-guided search.Qualitative comparisons use beam search with different priors on GenEval.

G. Failure Case Analysis

The failure analysis identifies verifier hacking and prior bottlenecks as representative limitations of test-time search. Large search budgets can exploit verifier blind spots, while search cannot recover information absent from the autoregressive prior.

  • Verifier hacking: Verifier hacking occurs when large search budgets overfit external verifiers and exploit their blind spots.This can produce visually implausible or semantically inconsistent images despite high verifier scores.
  • Prior bottleneck: The prior bottleneck prevents test-time search from recovering information that the autoregressive prior misses or models poorly.Search may refine local details but fail to correct global structural errors.
  • Prior bottleneck: Under a uniform prior, searched results fail to generate key semantic elements such as “wine” because the initial prior lacks appropriate object knowledge.This illustrates the boundary between search-based refinement and missing global semantics.
Loading 2604.15453v1…