Single-pass Adaptive Image Tokenization for Minimum Program Search

TL;DR

KARL is a single-forward-pass adaptive image tokenizer that predicts the number of tokens an image needs alongside the token values themselves, halting once the approximate Kolmogorov complexity of the image (under a target reconstruction quality ε) is reached. It contrasts with Matryoshka-style adaptive tokenizers (which require subset-constrained nested encodings and multi-decoder passes) and ALIT-style recurrent tokenizers (which iterate encoder-decoder loops until quality is met). The training procedure is framed as Upside-Down RL: condition on a target quality ε and budget T, learn to predict the smallest t ≤ T that achieves ε. The paper accompanies the algorithm with scaling laws (encoder/decoder size, continuous vs discrete tokens) and an Algorithmic-Information-Theory framing of predicted token-count as image complexity, finding it correlates with structure-vs-noise and in- vs. out-of-distribution familiarity.

Key claims

A single forward pass can produce a variable-length tokenization that matches the reconstruction quality of multi-pass adaptive tokenizers (Matryoshka, ALIT) at the same token count [Abstract, Fig. 1].
Token count predicted by KARL is a usable proxy for Kolmogorov Complexity / Minimum Description Length of the input image at a chosen reconstruction quality [§1, Fig. 1].
Training is cast as Upside-Down RL: the network is conditioned on a desired-quality ε and an input-token budget T, and learns to predict per-token halting probabilities such that the realized t-token reconstruction hits ε [Abstract, §3].
Predicted complexity tracks human intuition along two axes: structured images need fewer tokens than noise; in-distribution images need fewer tokens than out-of-distribution ones [§5, conceptual study].
Scaling laws are reported across encoder size, decoder size, and continuous vs discrete tokenization choices; the paper presents these as design knobs rather than a single recommended configuration [Abstract, §4].
Reference inference settings: 256-token input budget, default reconstruction-quality target ε = 0.05 (configurable; lower for fine detail, higher for token economy) [released code, README].

Method

A ViT encoder takes the image plus T learnable query tokens (the “register” / budget tokens) and produces, in one forward pass, both (a) the latent values for those tokens and (b) per-position halting predictions conditioned on the target reconstruction quality ε. The minimum t ≤ T whose cumulative halting prediction crosses threshold becomes the realized token count; the first t tokens are then decoded back to pixels by a ViT decoder. Training conditions the encoder on (ε, T) inputs and supervises both the reconstruction at the predicted t and the halting head — analogous to Upside-Down RL’s “condition on reward, predict action that achieves it.” Unlike Matryoshka tokenizers, KARL does not enforce that the t-token encoding is a prefix/subset of the (t+1)-token encoding; unlike ALIT, it does not run an iterative encode-decode loop at inference. The released code defaults to input_token_budget=256 and desired_reconstruction_quality=0.05, with knobs to tighten quality at the cost of more tokens.

Results

The paper reports head-to-heads with Matryoshka adaptive tokenizers and ALIT on standard reconstruction benchmarks (ImageNet at 256²), arguing parity in reconstruction-vs-token-count Pareto while needing only a single forward pass. Detailed FID / rFID numbers are in Tables 1–3 of the paper; the headline framing is that the single-pass design is not a quality regression versus the multi-pass adaptive baselines it competes with. Scaling-law plots are presented across encoder/decoder size and continuous vs discrete latents. The conceptual-study section visualizes predicted token-count as an image-complexity scalar across a structure-vs-noise sweep and an OOD sweep, showing monotone alignment with the intended notion of KC.

Why it’s interesting

KARL is the upstream, adaptive-length sibling to the same author’s later End-to-End Training for Unified Tokenization and Latent Denoising (UNITE): same lab (Duggal/Isola at MIT), same insistence that the tokenizer is where the leverage is, but two orthogonal axes — KARL asks “how many tokens does this image deserve,” UNITE asks “should the tokenizer and denoiser share weights.” Read together they sketch a position: the tokenizer is a learned program-search procedure, not a fixed-rate compressor. KARL also contrasts with TC-AE: Unlocking Token Capacity for Deep Compression Autoencoders, which fixes the token count but redistributes the compression across the encoder via staged bottlenecks — TC-AE keeps a fixed budget and protects semantic structure inside it; KARL keeps semantic structure and lets the budget vary per image. The “predicted token count = image complexity” framing also gives Luma a cheap, training-free complexity scalar that’s useful for data curation, hard-example mining, and adaptive compute scheduling for generation — an angle the Diffusion training efficiency concept page already tracks from the encoder-noise-floor side (Unified Latents (UL): How to train your latents) and the token-count-scaling side (TC-AE: Unlocking Token Capacity for Deep Compression Autoencoders).