(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
Proceedings of the 43rd International Conference on Machine Learning, PMLR 306:33514-33557, 2026.

Abstract

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.

Cite this Paper

BibTeX
@InProceedings{pmlr-v306-gao26x, title = {(1{D}) Ordered Tokens Enable Efficient Test-Time Search}, author = {Gao, Zhitong and Rezaei, Parham and Cy, Ali and Ye, Mingqiao and Jovanovi\'{c}, Nata\v{s}a and Allardice, Jesse and Dehghan, Afshin and Zamir, Amir and Bachmann, Roman and Kar, O\u{g}uzhan Fatih}, booktitle = {Proceedings of the 43rd International Conference on Machine Learning}, pages = {33514--33557}, year = {2026}, editor = {Zhang, Tong and Dudik, Miroslav and Jaggi, Martin and Agarwal, Alekh and Li, Sharon and Schuurmans, Dale and Zhu, Jerry and Berkenkamp, Felix and Dong, Hanze and Bietti, Alberto}, volume = {306}, series = {Proceedings of Machine Learning Research}, month = {06--11 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v306/main/assets/gao26x/gao26x.pdf}, url = {https://proceedings.mlr.press/v306/gao26x.html}, abstract = {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.} }
Endnote
%0 Conference Paper %T (1D) Ordered Tokens Enable Efficient Test-Time Search %A Zhitong Gao %A Parham Rezaei %A Ali Cy %A Mingqiao Ye %A Nataša Jovanović %A Jesse Allardice %A Afshin Dehghan %A Amir Zamir %A Roman Bachmann %A Oğuzhan Fatih Kar %B Proceedings of the 43rd International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2026 %E Tong Zhang %E Miroslav Dudik %E Martin Jaggi %E Alekh Agarwal %E Sharon Li %E Dale Schuurmans %E Jerry Zhu %E Felix Berkenkamp %E Hanze Dong %E Alberto Bietti %F pmlr-v306-gao26x %I PMLR %P 33514--33557 %U https://proceedings.mlr.press/v306/gao26x.html %V 306 %X 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.
APA
Gao, Z., Rezaei, P., Cy, A., Ye, M., Jovanović, N., Allardice, J., Dehghan, A., Zamir, A., Bachmann, R. & Kar, O.F.. (2026). (1D) Ordered Tokens Enable Efficient Test-Time Search. Proceedings of the 43rd International Conference on Machine Learning, in Proceedings of Machine Learning Research 306:33514-33557 Available from https://proceedings.mlr.press/v306/gao26x.html.

Related Material