🤖 machine learning

Structure over Pixels: Learning Variable-Length Visual Programs

The paper introduces STROP, a discrete visual tokenizer that learns variable-length visual programs to capture structural scene representations by optimizing a dedicated length head through a four-phase curriculum supervised by high-level features, thereby bypassing pixel reconstruction to prioritize compositional structure over texture.

Original authors: Piotr Wyrwiński, Kacper Dobek, Krzysztof Krawiec

Published 2026-05-28

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Piotr Wyrwiński, Kacper Dobek, Krzysztof Krawiec

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to describe a complex scene, like a busy street market, to a friend over a text message. You have two choices:

The Old Way: You send a massive, unedited photo. It's clear, but it takes forever to load and doesn't tell your friend what to look for.
The New Way (STROP): You send a short, variable-length list of keywords. If the scene is just a clear blue sky, you send one word: "Sky." If it's a chaotic market with 20 people, stalls, and animals, you send a longer list: "Stall, Apple, Dog, Child, Hat..."

This paper introduces STROP, a new way for computers to "read" images by turning them into these variable-length lists of keywords (called a "visual program") instead of just compressing pixels.

Here is how it works, using simple analogies:

1. The Problem with Current "Tokenizers"

Most current AI image compressors work like a fixed-size grid. Imagine you have a photo, and the computer forces it into a 64-square grid.

If the photo is a blank white wall, the computer still fills all 64 squares with "white" tokens.
If the photo is a crowded stadium, the computer still only has 64 squares to work with.
It wastes space on empty areas and runs out of space for complex areas. It's like trying to write a novel on a postcard; you either leave out details or cram everything in unreadably.

2. The STROP Solution: A "Smart Script"

STROP treats an image like a script or a recipe that can be short or long depending on the scene.

The Generator (The Writer): It looks at the image and decides, "This scene is simple; I only need 10 words to describe it." Or, "This scene is messy; I need 40 words."
The Interpreter (The Reader): It takes those words and rebuilds the understanding of the image.
The Length Head: This is a special part of the AI that acts like a manager. It looks at the image and immediately says, "Stop writing after token number 15," or "Keep going until token 40." It learns to match the length of the script to the complexity of the scene.

3. How It Learns: The "Four-Phase Curriculum"

The AI didn't just wake up knowing how to do this. The authors taught it using a four-step training camp:

Phase 1 (Random Truncation): The AI is forced to write scripts of random lengths. This teaches it that the most important information must be written first (front-loaded), just like a good headline.
Phase 2 (The Oracle): The computer secretly figures out the "perfect" length for each image by testing different lengths and seeing which one works best. It doesn't tell the AI yet; it just collects the answers.
Phase 3 (Supervised Learning): Now, the AI's "Manager" (the Length Head) is shown the "perfect" answers from Phase 2 and learns to predict them.
Phase 4 (The Handoff): The AI starts using its own predictions instead of the random ones, gradually taking full control.

4. The Secret Sauce: "Feature Distillation"

Most image compressors try to recreate the exact pixels (the colors and textures) of the original photo. STROP ignores the pixels.
Instead, it tries to recreate the "understanding" of the image. It uses a pre-trained "teacher" AI (called DINOv3) that is already very good at recognizing shapes and objects.

Analogy: Imagine you are taking a test. Instead of trying to memorize the exact font and ink color of the textbook (pixels), you try to memorize the concepts and logic the teacher taught you (features). STROP learns to write its "keywords" so that when a smart teacher reads them, they understand the scene perfectly, even if the exact colors aren't perfect.

5. What Did They Find?

Complexity Matches Length: The more objects and details in a picture, the longer the "program" (list of tokens) becomes. Simple scenes get short lists; complex scenes get long lists.
Tokens are "Handles": If you delete a specific token from the list, a specific part of the image disappears or changes. This suggests each token acts like a handle for a specific object or concept (e.g., one token might control the "dog," another the "tree").
Better than the Competition: When tested on standard computer vision tasks (like finding objects or segmenting images), STROP preserved more useful information than other adaptive methods that try to do the same thing.

6. Limitations (The "But...")

The paper is honest about what STROP can't do yet:

It's not a direct dictionary: If you look at the raw list of tokens (e.g., "Token 42, Token 105"), a human or a standard AI can't easily read it. You need the "Interpreter" to translate the list back into something useful. It's like a secret code that only the machine knows how to decode.
Attributes are fuzzy: While the AI is good at figuring out where objects are and how many there are, it struggles to perfectly link specific tokens to specific attributes like "red" or "metal." The connection between the code and the specific color isn't perfectly clear yet.

Summary

STROP is a new way for computers to turn images into variable-length lists of concepts. Instead of forcing every image into a rigid grid, it writes a custom-length "story" for each scene, focusing on the structure and meaning of the image rather than just the raw colors. It learns to stop writing when the scene is fully described, saving space on simple images and using more detail for complex ones.

Technical Summary: Structure over Pixels: Learning Variable-Length Visual Programs

Problem Statement

Current deep neural networks excel at computer vision tasks but produce representations that are often verbose, distributed, and difficult to inspect or validate. While discrete visual tokenizers (DVTs) offer a path toward structural scene descriptions by mapping images to ordered sequences of discrete codes, existing approaches suffer from two primary limitations:

Fixed Program Length: Most DVTs (e.g., VQ-VAE, VQGAN, and recent 1D tokenizers) enforce a fixed spatial grid or a fixed number of latent slots per image. This decouples the "code budget" from the actual visual complexity of the scene, violating principles like Occam's razor and minimum description length.
Pixel-Centric Training: Standard DVTs are typically trained with pixel-level reconstruction losses. This emphasis on fidelity often forces the model to waste capacity on capturing low-level textural characteristics rather than high-level semantic or geometric structure.

Furthermore, existing methods that do allow for variable-length tokenization often rely on post-hoc search, inference-time routing, or discrete sets of pre-trained rates, rather than learning a continuous, per-image sequence length coupled directly to the model and scene content.

Methodology: STROP

The authors propose STROP (Structure over Tokens), a discrete visual tokenizer architecture designed to form structural scene representations while simultaneously learning the optimal length of an image's visual program.

Architecture

STROP comprises five key stages:

Frozen Encoder: A frozen DINOv3 ViT encoder extracts patch-wise features from the input image.
Program Generator: An encoder-only transformer processes the patch features appended with a sequence of learnable query tokens. A causal mask ensures that query tokens attend only to previous queries and source features, generating a raw program sequence $Z_p$ .
Vector Quantization: The raw program is projected into a low-dimensional space and quantized against a fixed codebook ($|CB|=1024$) via nearest-neighbor lookup, producing discrete tokens.
Length Head: A lightweight MLP predicts the active program length ( $\hat{L}$ ) directly from the encoder features. This allows the model to determine how much of the sequence to expose without autoregressive sampling.
Interpreter: A mirrored encoder-only transformer expands the truncated program (prefix of length $\hat{L}$ ) back into a spatial feature grid. This grid is then passed to a convolutional decoder.

Training Objective and Curriculum

Unlike traditional tokenizers, STROP bypasses pixel-level reconstruction gradients for shaping the codebook. Instead, the entire training signal is derived from frozen DINOv3 patch features via feature distillation. The loss function combines latent alignment (cosine similarity and MSE against teacher features), commitment loss, and a diversity regularizer.

To enable adaptive truncation, STROP employs a four-phase curriculum:

Phase 1 (Random Truncation): The model trains on randomly truncated programs to force informative content to be front-loaded into earlier tokens.
Phase 2 (Oracle Estimation): The system estimates "oracle" lengths for each sample by analyzing reconstruction errors and local slopes of the rate-distortion curve.
Phase 3 (Supervised Training): The length head is trained to predict these oracle targets while truncation remains random, ensuring stable learning.
Phase 4 (Handoff): The trained length head is gradually deployed to control truncation, transitioning from random to self-predicted lengths.

At inference, the length head predicts $\hat{L}$ , and the program is hard-truncated to this length before decoding. A detached pixel decoder serves only as an inspection layer, ensuring the codebook is shaped entirely by the quality of higher-level latent representations.

Key Contributions

The paper outlines four concrete contributions:

Variable-Length Visual Programs: STROP supervises per-image program length using local rate–distortion probes and a prefix curriculum, allowing the token count to grow with scene complexity.
Simple Generator–Interpreter Tokenizer: The architecture uses two encoder-only transformers with learned queries to write and read causally ordered VQ codes, guided by DINOv3 feature distillation.
Pixel Probes Without Pixel Training: By using a detached pixel decoder, the method treats reconstructions as an inspection surface, preventing pixel gradients from shaping the codebook and prioritizing representational quality over texture.
Evaluation of Representation and Structure: The authors provide a comprehensive evaluation of rate–quality tradeoffs, downstream dense-prediction performance, and evidence of compositional structure through code reuse and spatial grounding.

Results

Latent Alignment and Compression

STROP achieves strong alignment with frozen DINOv3 features. On the COCO dataset, the DINO-S/STROP-S variant achieves a cosine similarity of 0.855 and $R^2$ of 0.734. The model compresses variable-sized feature tensors into an adaptive sequence of at most 64 discrete codes, achieving worst-case compression ratios ranging from $\sim$ 4,900 $\times$ to $\sim$ 13,100 $\times$ depending on the backbone.

Downstream Performance

When frozen STROP representations are used for downstream tasks via linear probes:

Semantic Segmentation: STROP consistently outperforms off-the-shelf adaptive tokenizers (FlexTok, One-D-Piece) on VOC, COCO-Stuff-27, and ADE20K. For instance, the DINO-B/STROP-S latent representation achieves 67.5 mIoU on VOC, significantly surpassing FlexTok (48.4 mIoU).
Multi-Label Classification: STROP matches or marginally exceeds the frozen DINO teacher and beats FlexTok by roughly 10 mean-mAP points on average.
Depth Estimation: STROP preserves task-relevant content for depth estimation, though it trails the strongest teacher models.

Structural Analysis

Complexity Correlation: Program length correlates strongly with scene complexity. On CLEVR, the active program length shows a Pearson correlation of $r \approx 0.74$ with the ground-truth object count.
Compositional Structure: Token-erasure diagnostics reveal that individual program tokens act as spatially coherent "handles" over the scene. Pairwise token synergies align with semantic regions, suggesting the emergence of a learned visual grammar.
LLM Decoding: Frontier LLMs (Qwen3.5, DeepSeek-V3.1) can decode coarse spatial layouts (object count and positions) from the code sequences but fail to reliably bind tokens to specific attributes (color, material), indicating the codebook exposes layout but not yet fully transparent attribute binding.

Significance and Limitations

The paper claims that STROP demonstrates that variable-length visual programs can be learned end-to-end without post-hoc search, effectively adapting the "code budget" to scene complexity. By decoupling training from pixel reconstruction, the model prioritizes structural and semantic fidelity, resulting in representations that are highly effective for downstream tasks and exhibit signs of compositional structure.

However, the authors remain modest about the current state of the system:

Readability Gap: Direct probes on raw quantized tokens perform worse than probes on the interpreted field, suggesting the program is best viewed as an executable intermediate representation rather than a drop-in linear feature.
Attribute Binding: The codebook does not yet reliably encode discrete attributes (color, material) for language models, limiting its utility as a fully transparent symbolic interface.
Task Specificity: While STROP outperforms baselines on most benchmarks, it lags behind FlexTok on the Cityscapes dataset, likely due to the dense, fine-grained nature of street scenes which may benefit from pixel-aware decoding.

The work positions STROP as a step toward principled structural representations, with future work suggested in scaling codebook capacity, developing program-native probing protocols, and aligning code identities with captioning signals to improve attribute binding.