# Single-pass Adaptive Image Tokenization for Minimum Program Search

arXiv: https://arxiv.org/abs/2507.07995 · HTML: https://mlsanity.com/paper/2507.07995/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 19 of its 34 references that are in the map.
- First posted on arXiv 10 Jul 2025.

## Builds on (most cited first, 19 of 19)

- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [A Simple Framework for Contrastive Learning of Visual Representations](https://mlsanity.com/paper/2002.05709/) (2020)
- [Masked Autoencoders Are Scalable Vision Learners](https://mlsanity.com/paper/2111.06377/) (2021)
- [Emerging Properties in Self-Supervised Vision Transformers](https://mlsanity.com/paper/2104.14294/) (2021)
- [Taming Transformers for High-Resolution Image Synthesis](https://mlsanity.com/paper/2012.09841/) (2020)
- [Estimating or Propagating Gradients Through Stochastic Neurons for Conditional Computation](https://mlsanity.com/paper/1308.3432/) (2013)
- [Understanding Contrastive Representation Learning through Alignment and Uniformity on the Hypersphere](https://mlsanity.com/paper/2005.10242/) (2020)
- [Perceiver: General Perception with Iterative Attention](https://mlsanity.com/paper/2103.03206/) (2021)
- [Perceiver IO: A General Architecture for Structured Inputs & Outputs](https://mlsanity.com/paper/2107.14795/) (2021)
- [An Image is Worth 32 Tokens for Reconstruction and Generation](https://mlsanity.com/paper/2406.07550/) (2024)
- [Matryoshka Representation Learning](https://mlsanity.com/paper/2205.13147/) (2022)
- [Reinforcement Learning Upside Down: Don't Predict Rewards -- Just Map Them to Actions](https://mlsanity.com/paper/1912.02875/) (2019)
- [FlexTok: Resampling Images into 1D Token Sequences of Flexible Length](https://mlsanity.com/paper/2502.13967/) (2025)
- [One-D-Piece: Image Tokenizer Meets Quality-Controllable Compression](https://mlsanity.com/paper/2501.10064/) (2025)
- [ElasticTok: Adaptive Tokenization for Image and Video](https://mlsanity.com/paper/2410.08368/) (2024)
- [Adaptive Length Image Tokenization via Recurrent Allocation](https://mlsanity.com/paper/2411.02393/) (2024)
- [Flow to the Mode: Mode-Seeking Diffusion Autoencoders for State-of-the-Art Image Tokenization](https://mlsanity.com/paper/2503.11056/) (2025)
- [CAT: Content-Adaptive Image Tokenization](https://mlsanity.com/paper/2501.03120/) (2025)
- [SAVOIAS: A Diverse, Multi-Category Visual Complexity Dataset](https://mlsanity.com/paper/1810.01771/) (2018)

## Built on by (most cited first, 12 of 12)

- [Attend Before Attention: Efficient and Scalable Video Understanding via Autoregressive Gazing](https://mlsanity.com/paper/2603.12254/) (2026)
- [MilliVid: Hierarchical Latents for Long-Range Consistency in Video Generation](https://mlsanity.com/paper/2606.09056/) (2026)
- [Revisiting MLLM Token Technology through the Lens of Classical Visual Coding](https://mlsanity.com/paper/2508.13460/) (2025)
- [Compression Tells Intelligence: Visual Coding, Visual Token Technology, and the Unification](https://mlsanity.com/paper/2601.20742/) (2026)
- [Adaptive Protein Tokenization](https://mlsanity.com/paper/2602.06418/) (2026)
- [Learning to Theorize the World from Observation](https://mlsanity.com/paper/2605.03413/) (2026)
- [Soft Tail-dropping for Adaptive Visual Tokenization](https://mlsanity.com/paper/2601.14246/) (2026)
- [AdaTok: Self-Budgeting Image Tokenization with Quality-Preserving Dynamic Tokens](https://mlsanity.com/paper/2606.07185/) (2026)
- [Structure over Pixels: Learning Variable-Length Visual Programs](https://mlsanity.com/paper/2605.27696/) (2026)
- [ChannelTok: Efficient Flexible-Length Vision Tokenization](https://mlsanity.com/paper/2606.04461/) (2026)
- [Adaptive Tokenisation Via Temporal Redundancy Masking And Latent Inpainting](https://mlsanity.com/paper/2606.06158/) (2026)
- [Semantically Steerable Image Tokenization](https://mlsanity.com/paper/2610.15515/) (2026)

## Abstract (arXiv)

According to Algorithmic Information Theory (AIT) -- Intelligent representations compress data into the shortest possible program that can reconstruct its content, exhibiting low Kolmogorov Complexity (KC). In contrast, most visual representation learning systems use fixed-length representations for all inputs, ignoring variations in complexity or familiarity. Recent adaptive tokenization methods address this by allocating variable-length representations but typically require test-time search over multiple encodings to find the most predictive one. Inspired by Kolmogorov Complexity principles, we propose a single-pass adaptive tokenizer, KARL, which predicts the appropriate number of tokens for an image in a single forward pass, halting once its approximate KC is reached. The token count serves as a proxy for the minimum description length. KARL's training procedure closely resembles the Upside-Down Reinforcement Learning paradigm, as it learns to conditionally predict token halting based on a desired reconstruction quality. KARL matches the performance of recent adaptive tokenizers while operating in a single pass. We present scaling laws for KARL, analyzing the role of encoder/decoder size, continuous vs. discrete tokenization and more. Additionally, we offer a conceptual study drawing an analogy between Adaptive Image Tokenization and Algorithmic Information Theory, examining the predicted image complexity (KC) across axes such as structure vs. noise and in- vs. out-of-distribution familiarity -- revealing alignment with human intuition.