We appreciate the reviewer’s appreciation on the motivation and novelty of a single-pass adaptive tokenizer. The concerns raised relate to (1) lack of theoretical grounding in Algorithmic Information Theory (AIT), (2) writing clarity. We address both below.

---

We revised Section 4 to better articulate the connection between adaptive tokenizers and AIT. We believe earlier writing may have caused confusion, which we have now clarified. Specifically, we include analogies to KC and Solomonoff Induction, particularly the idea of searching for the shortest program.

One key reference, lossy (complexity-constrained) compression has been discussed in seminal work of Kolmogorov Structure Function [1], supporting our theoretical framing.

Section 4: Adaptive Image Tokenization meets AIT

Correlation with KC: KC formalizes the length of the shortest program that reproduces a data instance. In our setting, we approximate this by treating the token count as a proxy for program length—each token encodes structured information. Minimizing tokens while preserving fidelity aligns with minimizing description length, and thus, KC. Let’s understand this analogy in more detail

Formally, the “program” includes both token sequence and decoder. Since the decoder is fixed and shared across samples, its cost can be treated as constant, leaving minimal tokens as shortest program.

Secondly, because exact reproduction is infeasible in deep learning, we define “reproduction” as achieving reconstruction within an error threshold (e.g., ℓ₁ or perceptual loss). This yields a tractable notion of approximate KC, the foundation of our work.

This view parallels the seminal Kolmogorov Structure Function (KSF) [1] (see Example II.4), where KSF(x, α) captures the size of smallest set S containing x such that KC(S) ≤ α. Here, α is a complexity budget, and S "explains" x—analogous to finding the shortest token sequence that reconstructs x within a target loss.

Searching the shortest program— Algorithmic Probability frameworks like Solomonoff Induction (SI) aim to find the shortest program that explains data, assigning higher probability to simpler programs -- by exhaustively enumerating over programs that reproduce the data when decoded by UTM, in increasing order of KC.

Aligning w/ SI, adaptive tokenizers (e.g., ALIT) approximate this search by varying token budgets at test time, incrementally increasing tokens until the reconstruction meets a fidelity threshold. KARL approximates this shortest-program search in a single pass: it predicts the minimal subset of tokens needed to meet a reconstruction constraint avoiding iterative decoding.

---

Next, we revised the Methods section for clarity. We apologize for earlier confusion.

The overall procedure is inspired by Kolmogorov Complexity principles (like invariance w/ additional resources/tokens, token minimization) and the training prodecure aligns with the seminal Upside-Down RL Framework.

Section 3: Kolmogorov-Approximating Representation Learning

Our goal is to learn representations that are both compressed and predictive, thus: (a) minimize reconstruction loss, (b) minimize representation length.

While existing adaptive tokenizers rely on iterative passes at test time to find the minimal tokens for a desired quality, we ask: Can we predict minimality in a single pass?

We introduce KARL, a loss-conditioned adaptive tokenizer that approximates the image’s minimum description length—the fewest tokens needed for a target reconstruction threshold. At test time, KARL takes an image, token budget, and loss threshold, and outputs only the necessary tokens, masking out the rest.

Loss-Conditioned Training of KARL: We define the approximate Kolmogorov Complexity ($ \hat{\text{KC}} $) of an image $ x $ under a reconstruction threshold $ \epsilon $ and a maximum given token budget, $ T $ as:
$

\hat{\text{KC}}_\epsilon(x, T) = \min \left\{ t \leq T \;\middle|\; \mathcal{L}_{\text{rec}}(x, \hat{x}_t) \leq \epsilon \right\}
$

Here, $ \hat{x}_t $ is the reconstruction from the first $ t $ tokens (out of $ T $), and $ \mathrm{L}_{\text{rec}} $ is the reconstruction error. Intuitively, $ \hat{\text{KC}}_\epsilon(x, T) $ represents the smallest token count sufficient to reconstruct $ x $ within error $ \epsilon $, constrained by the budget $ T $. This defines a practical, task-specific approximation of Kolmogorov Complexity.

To encourage learning such minimal programs, we train KARL under the assumption of KC invariance:
$

\hat{\text{KC}}\epsilon(x, T) = \hat{\text{KC}}\epsilon(x, T + \Delta T)
$

That is, increasing the token budget shouldn't change the minimal token count needed for a given $\\epsilon$. Once the model learns the sufficient subset, adding tokens should not alter the representation. This principle guides KARL to mask out unnecessary tokens during training.

Training Procedure: Each training iteration runs the encoder-decoder pipeline twice, reflecting the principle that KC remains invariant once the sufficient token count is found for reconstruction. We now describe the two steps performed in each training iteration:

1. Estimating Image Complexity: Given an input image $ \mathbf{x} $, the model first attempts near-lossless compression using a token budget $ T $, optimizing:

$

\mathcal{L}_{\text{EIC}} = \mathcal{L}_{\text{recon}}(\hat{\mathbf{x}}_T, \mathbf{x}) + \beta \, \mathcal{L}_{\text{quant}}(\mathbf{z}_T)
$

where $ \hat{\mathbf{x}}_T = `Decoder(\Encoder`(\mathbf{x}, T, \epsilon = 0)) $, and $ \beta $ balances quantization. Here, $ \epsilon = 0 $ enforces near-perfect reconstruction. The resulting reconstruction error $ \epsilon_0 = \left| \hat{\mathbf{x}}_T - \mathbf{x} \right| $ defines the target quality for the second run. Sampling $ T $ randomly each iteration yields a batch of triplets {image, token budget $ T $, target error $ \epsilon_0 $} that guide complexity-aware tokenization.

2. Learning to Tokenize at Estimated Complexity: In the second run, given the simulated triplet {\mathbf{x}, T, \epsilon_0 }, the encoder receives an increased token budget $ T + \Delta T $. Conditioned on $ \epsilon_0 $, it outputs both token embeddings and halting probabilities $ \boldsymbol{\omega} \in [0,1]^{T + \Delta T} $, indicating which tokens to retain.

The model is optimized using:

$

\mathcal{L}_{\text{LTC}} = \mathcal{L}_{\text{recon}}(\hat{\mathbf{x}}_{T+\Delta T}, \mathbf{x}) + \beta \, \mathcal{L}_{\text{quant}}(\mathbf{z}_{T+\Delta T}) + \lambda \, \mathcal{L}_{\text{halt}}(\boldsymbol{\omega})
$

where $ \hat{\mathbf{x}}_{T+\Delta T} = `Decoder(\Encoder`(\mathbf{x}, T+\Delta T, \epsilon = \epsilon_0)) $. The encoder is trained to achieve the same recon. quality $ \epsilon_0 $ while identifying which tokens can be masked out. Halted tokens are excluded from self-attention, thus do not contribute to reconstruction.

The halting loss is:

$

\mathcal{L}_{\text{halt}}(\boldsymbol{\omega}) = \text{BCE}(\boldsymbol{\omega}_{0:T}, \mathbf{0}) + \text{BCE}(\boldsymbol{\omega}_{T:T+\Delta T}, \mathbf{1})
$

encouraging $ \omega_i \approx 0 $ for essential tokens $ i < T $ and $ \omega_i \approx 1 $ for surplus tokens $ i \geq T $.

The full training objective is $ \mathcal{L}_{\text{EIC}} + \mathcal{L}_{\text{LTC}} $. This parallels Upside-Down RL, where the first run sets a condition ($ \epsilon_0 $) and the second learns to act under it—akin to reframing RL as supervised learning with reward conditioning.

At inference, only second step is used: given a max token budget & a target error $ \epsilon $, KARL outputs both token embeddings & halting probabilities in a single pass.

---

Clarification regarding T': We believe T' was probably not the best choice of symbol; it's replaced with $ \Delta T $ in the text above. As mentioned earlier, in the Learning to Estimate Complexity step, for each image in the batch, we randomly sample an input token budget $ T $, which results in a $ \epsilon $ error due to lossy compression. Then, for each image, we randomly sample $ \Delta T $ (which is the same as T' in the earlier draft). In the Tokenize at Complexity step, the encoder—conditioned on the $ \epsilon $ obtained in the previous step—is tasked to use only the minimal number of tokens from the new input budget of $ T + \Delta $. We then train the network to mask out the extra $ \Delta T $ tokens, since $ T $ was already sufficient for $ \epsilon $-bounded reconstruction.

---

Regarding Interestingness and Connections to AIT -- Interestingness is deeply rooted in AIT. For example, see Scott Aaronson's blog on "The First Law of Complexodynamics" or Peter Bloem’s slides on Sophistication. Measures like sophistication, logical depth, and KSF [1] are all derivative notions based on Kolmogorov Complexity (KC). While we observed early signs that adaptive tokenizers—especially KARL—could estimate sophistication (via the rate of change in reconstruction quality with respect to token count), the main contribution we emphasize is the novel single-pass adaptive tokenization and its core analogy with KC.

---

Figure 5 query — The left plot uses $ \epsilon = 0 $, targeting perfect reconstruction, so FID at 256 tokens is lower. In contrast, the right plot shows KARL stopping early with $ \epsilon > 0 $, leading to higher FID. We hope this clarifies the difference.

---

Table formatting — Thank you for pointing this out; we will correct it.

We hope the two revised sections address the reviewer’s concerns.

We sincerely thank the reviewer for their response and for confirming that their concerns have been addressed.

The point above made in the rebuttal suggests that the decoder is fixed (which is fine). But naively I would wonder whether a different decoder might also lead to a better program. In any case, the authors have done a nice job with their method.

This is a great insightful question. As noted in the main paper, the decoder is ideally considered part of the program (though amortized across all images). Accordingly, modifying the decoder architecture can overall affect the description length, and thus the approximate Kolmogorov Complexity (KC) of an image under our model. We explore this effect in detail through controlled ablations in Appendix Figures 13 and 14.

That said, consistent with Algorithmic Information Theory—and as discussed around line 315 of the main paper—the invariance theorem suggests that such the decoder change should impact KC estimates by at most an additive constant. This implies that while the absolute KC values may shift, the relative complexity ordering across inputs should remain stable.

Empirically, this is precisely what we observe. As shown in the rightmost plots of Figures 9 and 10, changing the decoder width or depth has minimal effect on the active token count, suggesting that our KC approximation is effectively invariant under decoder variation. Rather the decoder size influenced the reconstruction quality.

We acknowledge that using a much larger decoder (beyond what is feasible in our academic setup) could either potentially reduce the minimal required token count further (as observed in FlexTok paper) or increase the reconstruction quality, but the relative ordering of image complexities should still hold. We hope this clarifies the query.

---

More broadly, we respectfully note that we have thoroughly addressed all reviewer questions, and we appreciate all the reviewers’ recognition of the paper’s contributions—namely:

• The novel problem formulation: introducing the first single-pass adaptive tokenizer,
• Innovative Approach: A loss-conditioned training approach inspired by Kolmogorov Complexity principles and drawing parallels with the Upside-Down RL framework,
• And the strong empirical performance: across both reconstruction and downstream tasks.

Given this, we remain unsure about the rationale behind the current borderline rejection. We would sincerely appreciate any further clarification or suggestions that could help us strengthen the work. We believe the paper offers a meaningful contribution to progressing the scientific study of visual tokenizers, and we are committed to improving it further based on the community’s feedback.

Thanks again, Best Regards!

Thank you again for your response!

Just to highlight, we mainly revised Sections 3 and 4 to make them easier to read and to better emphasize the key components (as thoughtfully suggested by the reviewer). The overall content remains the same or very similar to the original main paper. Our latest version, based on the reviewer's feedback, is already ready and encapsulates all the contents of the rebuttal.

---

We truly appreciate the reviewer's effort in engaging with other reviewers and the Area Chair to arrive at the final rating. As mentioned before, we believe the paper makes significant contributions to the scientific (and still relatively fresh) study of visual tokenizers. We hope these contributions are recognized and not overshadowed or scooped.

We trust that the main paper, along with the rebuttal—which addresses all raised concerns—will be given a fair and thorough evaluation.

Best Regards!

We appreciate the reviewer’s appreciation on the practicality of single-pass adaptive tokenization and our system study of scaling laws.

---

We revised Section 4 to better articulate the connection between adaptive tokenizers and AIT. We believe earlier writing may have caused confusion, which we have now clarified. Specifically, we include analogies to KC and Solomonoff Induction, particularly the idea of searching for the shortest program.

One key reference, lossy (complexity-constrained) compression has been discussed in seminal work of Kolmogorov Structure Function [1], supporting our theoretical framing.

Section 4: Adaptive Image Tokenization meets AIT

Correlation with KC: KC formalizes the length of the shortest program that reproduces a data instance. In our setting, we approximate this by treating the token count as a proxy for program length—each token encodes structured information. Minimizing tokens while preserving fidelity aligns with minimizing description length, and thus, KC. Let’s understand this analogy in more detail

Formally, the “program” includes both token sequence and decoder. Since the decoder is fixed and shared across samples, its cost can be treated as constant, leaving minimal tokens as shortest program.

Secondly, because exact reproduction is infeasible in deep learning, we define “reproduction” as achieving reconstruction within an error threshold (e.g., ℓ₁ or perceptual loss). This yields a tractable notion of approximate KC, the foundation of our work.

This view parallels the seminal Kolmogorov Structure Function (KSF) [1] (see Example II.4), where KSF(x, α) captures the size of smallest set S containing x such that KC(S) ≤ α. Here, α is a complexity budget, and S "explains" x—analogous to finding the shortest token sequence that reconstructs x within a target loss.

Searching the shortest program— Algorithmic Probability frameworks like Solomonoff Induction (SI) aim to find the shortest program that explains data, assigning higher probability to simpler programs -- by exhaustively enumerating over programs that reproduce the data when decoded by UTM, in increasing order of KC.

Aligning w/ SI, adaptive tokenizers (e.g., ALIT) approximate this search by varying token budgets at test time, incrementally increasing tokens until the reconstruction meets a fidelity threshold. KARL approximates this shortest-program search in a single pass: it predicts the minimal subset of tokens needed to meet a reconstruction constraint avoiding iterative decoding.

We have exciting general response regarding the alignment of adaptive visual tokenization and algorithmic information theory, and hope the writing would clarify reviewer's concern regarding the same.

---

Lack of theoretical guarantees about optimality of learned token counts

We respectfully clarify that computing the theoretically optimal number of tokens per data point is inherently intractable—this is a known limitation of Kolmogorov Complexity (KC) and Solomonoff Induction (SI), not specific to our method. Our work aims to approximate KC by treating the minimal number of tokens (under a learned decoder) as a proxy for the shortest program that reproduces an image—an approach, to our knowledge, not previously explored for visual tokenization.

A useful theoretical framing of KARL (like all auto-encoders) is via classical rate-distortion analysis:

$

Z_{\text{optimal}} = \min_Z \left[ -H(X \mid Z) + \lambda D(X, \hat{X}(Z)) \right]
$

• $ H(X \mid Z) $: conditional entropy—uncertainty in $ X $ given $ Z $.
• $ D(X, \hat{X}(Z)) $: reconstruction loss; $ \lambda $ balances compression vs. fidelity.

---

Limited Theoretical Novelty

While the high-level idea—masking out excess tokens given a token budget—may seem straightforward, the proposed method introduces several non-trivial innovations that, in our view, contribute meaningfully to the field.

Theoretical grounding in Kolmogorov Complexity (KC): Our approach is not merely an engineering trick but is guided by foundational principles from Algorithmic Information Theory. In particular, we leverage the invariance property of KC—that KC is an intrinsic property of data and should remain unchanged even when more computational resources (i.e., tokens) are available. This motivates our learning objective: once a minimal token subset sufficient to reconstruct an image is identified, additional tokens should be deemed unnecessary.

Training innovation via loss-conditioned supervision: Naively applying masking during training is non-differentiable and, in our experiments, fails to converge. Common strategies like straight-through estimation or reinforcement learning introduce complexity and instability. In contrast, our method draws inspiration from the Upside-Down Reinforcement Learning framework, enabling a stable two-step procedure within each training iteration: (a) Estimate Complexity — mapping the image to a randomly selected token budget and observing the resulting reconstruction error $ \epsilon $; (b) Tokenize at Learned Complexity — using $ \epsilon $ as a conditioning signal to guide the encoder to mask out redundant tokens from an expanded budget. This enables effective one-shot prediction of a minimal token set for a given reconstruction constraint.

Overall, we believe that combining this theoretical motivation with a stable, practical training strategy for single-pass adaptive tokenization represents a meaningful technical contribution. We are encouraged by the broader response, which found the method novel and interesting, especially in the context of visual tokenization.

We hope this response answers the concern of technical novelty. We apologize it this wasn't clear upfront and we will improve the writing.

---

Evaluation Concerns
We want to clarify that variable token allocation is a central goal of all adaptive tokenizers—not just KARL. For example, ALIT explicitly emphasizes this (Figure 6 of their paper). The key distinction lies in how adaptation is achieved.

KARL predicts when to halt tokenization in a single forward pass, conditioned on a reconstruction threshold. In contrast, methods like ALIT rely on test-time search with multiple encoder-decoder passes, using decoder feedback to iteratively minimize token count. While this allows slightly tighter token estimates, it comes with higher FLOPs and latency.

As a result, ALIT achieves a marginally lower estimated $ \hat{KC} $ than KARL (see Table 2), but at the cost of increased compute. These approaches are complementary and could be combined—for instance, using KARL’s prediction as an efficient initialization for further refinement.

---

Limitations

• FID gap despite strong per-image metrics: KARL performs competitively or better than existing tokenizers on all metrics except the distribution-level metric FID. This may be due to KC-guided training favoring the search for the shortest program per image—optimizing for single-image metrics (LPIPS, SSIM, PSNR, DreamSim)—rather than global distribution alignment. A deeper analysis of this trade-off would be valuable.

• Inability of KC to distinguish noise from structure: As noted in the paper, Kolmogorov Complexity assigns high complexity to both noisy and highly structured images. Higher-order measures such as Sophistication or Logical Depth can make this distinction and form the basis of our proposal for interestingness. However, our current interestingness formulation is a simple delta on KC, not a learned signal.

• General limitation of all adaptive tokenizers: Current methods, including KARL, are constrained to a maximum token budget per image (e.g., 256 tokens for 256×256 images), limiting granularity.

Future Work Exploring the use of learned compressed tokens to train downstream models—such as vision-language models or video models—is a promising and timely direction for further research.

---

Misplaced Content: Thank you for the suggestion. In the latest revision, Section 4 focuses only on the connections to Kolmogorov Complexity and Solomonoff Induction. We will move broader background and references to AIT concepts to the Related Work section.

---

Complexity Analysis

We thank the reviwer for bringing this up. We compared computational complexity in terms of the number of encoder/decoder calls in Table 2, which is architecture-agnostic and avoids confounds like GPU type or precision. For fair comparison, all baselines use the same encoder/decoder architecture.

Here are the requested numbers in terms of Glops and executing time on a single H100 GPU with FP32 precision:

• Encoder GFlops: KARL ≈ One-D-Piece ≈ First iteration of ALIT ≈ 80 GFlops
• ALIT: Requires 8 iterations during training, and ~4 iterations at test time for $ \epsilon = 0.9 $-bounded reconstruction. Each additional ALIT iteration adds ~30 GFlops.
• Decoder GFlops: ALIT and One-D-Piece require multiple decoding passes, each ≈ 80 GFlops.

Wall-clock Time (ms):

• First encoder or decoder pass: ~7 ms
• Each additional ALIT encoder iteration: ~4 ms

---

We hope we have addressed all concerns—through improved writing, citing the strong reference on Kolmogorov Structure Function (KSF), and highlighting the strong analogy between AIT and adaptive tokenization. Additionally, we clarified how our training strategy emerges naturally from KC principles and aligns with the seminal Upside-Down RL framework, which we believe helps address any concerns regarding technical novelty.

Interestingly, we’ve also heard others point out conceptual parallels between our work and the recent interesting H-Net paper on dynamic tokenization for LLMs—both approaches learn when to stop tokenization. We’re grateful for your review and are happy to answer any further questions.

[1] Kolmogorov’s Structure Functions and Model Selection

We sincerely thank the reviewer for their response and for confirming that their concerns have been addressed.

---

We made a figure highlighting the taxonomy of recent adaptive tokenizers in our latest version, however due to neurips restrictions on rebuttal document, we couldn't include it in the rebuttal. Here is a textual description of that figure --

• Adaptive tokenizers can be bucketed into two broad categories (as mentioned in the paper), namely Matryoshka-style (ElasticTok, FlexTok, One-D-Piece) and Recurrent Tokenizers (ALIT).
• Matryoshka-based Tokenizers
  • ❌ Smaller embeddings are constrained as subsets of the larger embedding & hence adding more tokens only refines the initial ones, rather than discovery of new concepts as in ALIT and KARL (for example compare One-D-Piece Figure 1 with ALIT Figure 16). KARL showcases similar properties as ALIT.
  • ❌ Not aligned with the concept of Prefix Kolmogorov Complexity (a key concept in AIT, Universal Turing Machine -- which states a shortest program need not be subset of other programs).
  • ❌ Requires multiple Decoder runs to identify smallest #tokens.
• Recurrent Tokenizers
  • ✅ Kolmogorov Complexity aligned, shortest program or minimal tokens can be found by searching over multiple recurrent iterations.
  • ❌ Requires multiple Encoder & Decoder runs to identify smallest #tokens
• KARL:
  • ✅ Kolmogorov Complexity aligned & inspired.
  • ✅ Single-pass.

We hope this textual description solves your query of explain the differences and advantages between them. We will include the visual version of this taxonomy in the final camera ready version.

---

More information regarding choice of these baselines: We compared against two recent strong state-of-the-art baselines—ALIT (ICLR 2025) and One-D-Piece (2025). Other notable works include Flextok, ElasticTok, (non-adaptive) FlowMo, Titok, and older methods like VAE and VQGAN.

• FlexTok, One-D-Piece and ElasticTok fall under the same Matryoshka-style tokenizers, and since ALIT, One-D-Piece, and Titok all adopt a similar 2-stage GAN-based training pipeline with 2D VQGAN/VAE tokens, we chose One-D-Piece for a fair, apples-to-apples comparison with KARL focusing on our core contributions.

• Furthermore, Flextok models are much large-scale (e.g., trained with REPA-style losses using DINO, which is trained on much broader datasets), making direct comparisons with KARL, ALIT, and One-D-Piece less fair in scope. That said, we can include Flextok results in the final version.

• Numbers for VAE, VQGAN, Titok are same as mentioned in the ALIT paper, and can be simply copied from the ALIT paper.

To the best of our knowledge, these represent the latest adaptive tokenization baselines. If we’ve missed the specific one you're referring to, we’d be very grateful if you could point us to it directly—we’d be happy to evaluate it, either within the remaining time or for the final version.

We hope this helps clarify things, and we’d really appreciate a quick response—especially with the discussion period nearing its end.

We thank the reviewer again for their earlier response and for acknowledging that all previous queries have been resolved (within the NeurIPS rebuttal limit)

Following your response on August 6th, we promptly evaluated an additional baseline and introduced a detailed taxonomy of adaptive tokenizers—examining them from both practical and AIT perspectives—which, to the best of our knowledge, has not been presented before. Drawing on our experience with this topic since its early works, we have also incorporated nearly all state-of-the-art adaptive tokenization baselines, comparing them across a wide range of metrics in a fair and consistent manner.

We would be grateful if the reviewer could clarify the remaining reasons for recommending rejection, as based on the rebuttal response we are not aware of any outstanding concerns. We genuinely believe—also supported by broader feedback—that the paper offers multiple strong contributions and advances the field of visual tokenization in a fresh and meaningful way. We remain committed to improving the paper, and it would be unfortunate if its contributions were overlooked without further clarification.

Best Regards!

Evaluating Generalization to Downstream Tasks

We thank the reviewer for the great suggestion regarding downstream evaluation. We have now conducted a comprehensive set of evaluations. Furthermore, we evaluated both fixed token allocation per image and variable token allocation settings. We are excited to share our findings—

• ALIT is the strongest adaptive tokenizer across most metrics, using a recurrent transformer that incrementally adds tokens—each step incurring extra FLOPs. KARL generally consistently ranks second, followed by the matryoshka-style One-D-Piece. Notably, all three perform comparably, and KARL matches this performance in a single pass, highlighting its promise as a effecient, scalable alternative. A compelling future direction is to combine KARL with ALIT-style recurrent refinement—refining minimal representation with more iterative loops.

• In the tables below, the 256-token column corresponds to the setting where the input token budget is 256 and $ \epsilon = 0.0 $, meaning all tokens are used for lossless reconstruction. As shown across CLIP, Depth, and Semantic Segmentation metrics, the performance drop from $ \epsilon = 0.0 $ to $ \epsilon = 0.03 $ and $ \epsilon = 0.05 $ is minimal—highlighting the benefit of KARL: allowing slight reconstruction loss has little to no impact on downstream performance. As expected, the effect of increasing $ \epsilon $ is especially marginal for coarse tasks like CLIP alignment.

• Note: Compared to KARL and ALIT, One-D-Piece requires 30+ more tokens to achieve $ \epsilon = 0.09 $-bounded reconstructions with similar downstream performance (see Table 2 in the main paper).

Overall, the metrics consistently highlight the significance of KARL—achieving minimal or no drop in performance while operating in a single pass. We hope this addresses the reviewer’s concerns regarding downstream task evaluations, and we would be happy to explore additional tasks upon suggestion.

Evaluating on CLIP Text-Image Downstream Task

Evaluating on Depth Estimation Downstream Task

Evaluating on Semantic Segmenatation

Evaluating on VLM (VQA)

---

Linear Probing Experiments:

We also conducted linear probing by training a single-layer linear classifier on top of the latent tokens produced by KARL and ALIT. Using only the first 32 1D latent tokens, ALIT achieves 44.8% Top-1 classification accuracy on ImageNet-1K, while KARL attains 41.5%. When both the 2D image tokens and the first 32 1D tokens are used, performance improves to 51.6% for ALIT and 45.0% for KARL—surpassing with the non-adaptive Titok tokenizer (48.0%).

This highlights a few key observations:

• As also noted in the ALIT paper, linear probing accuracy improves with more recurrent iterations during training—potentially due to added training FLOPs and hierarchical gradient flow across RNN layers. This may partly explain ALIT’s edge over KARL.
• Investigating how compression or minimality impacts the linear separability of learned representations is a promising direction for future work.
• The One-D-Piece paper reports noticeably lower linear probing accuracy (mid-30s). We suspect this may be due to an incorrect probing setup and will re-run the evaluation in our framework to report corrected numbers in the final draft.

---

Justification for Emphasis on Reconstruction Metrics

One minor comment, we believe reconstruction metrics still remain a valuable indicator of performance. A compact representation that enables near-lossless or low-$ \epsilon $-bounded reconstruction intuitevly will retain the key semantics necessary for most downstream tasks—although requiring different decoding capacities (exciting direction for future work). Moreover, single-image reconstruction metrics also echoes the principles of KC and AIT in general: identifying the shortest program that can reproduce the input data. Finally, we believe thoroughly exploring the connection between compressed representations and downstream performance is a compelling standalone research direction, and is one we are actively interested in.

---

Comparison with More Baselines

We compared against two recent strong baselines—ALIT (ICLR 2025) and One-D-Piece (2025). Other notable works include Flextok, ElasticTok, (non-adaptive) FlowMo, Titok, and older methods like VAE and VQGAN. FlexTok and ElasticTok fall under the Matryoshka-style tokenizers, and since ALIT, One-D-Piece, and Titok all adopt a similar 2-stage GAN-based training pipeline with 2D VQGAN/VAE tokens, we chose them for a fair, apples-to-apples comparison focusing on our core contributions.

Furthermore, Flextok models are much large-scale (e.g., trained with REPA-style losses using DINO, which is trained on much broader datasets), making direct comparisons with KARL, ALIT, and One-D-Piece less fair in scope. That said, based on the reviewer’s request, we will include Flextok results in the final version.

---

Limitations

We apologize for missing the limitations section in hindsight.

• FID gap despite strong per-image metrics: KARL performs competitively or better than existing tokenizers on all metrics except the distribution-level metric FID. This may be due to KC-guided training favoring the search for the shortest program per image—optimizing for single-image metrics (LPIPS etc)—rather than global distribution alignment. A deeper analysis of this trade-off would be valuable.

• Inability of KC to distinguish noise from structure: Kolmogorov Complexity assigns high complexity to both noisy and highly structured images. Higher-order measures such as Sophistication can make this distinction and form the basis of our proposal for interestingness. However, our current interestingness formulation is a simple delta on KC, not a learned signal, also not our main focus.

• General limitation of all adaptive tokenizers: Current methods, including KARL, are constrained to a maximum token budget per image (e.g., 256 tokens for 256×256 images), limiting granularity.

• Future Work: Elaborate study of linear separability or required size of decoder for different downstream tasks.

• Future Work: Exploring the use of learned compressed tokens to train downstream models—such as vision-language models or video models—is a promising and timely direction for further research. As acknowledged by the reviewer, this is challenging due to compute constraints in an academic setting, specially learning both a tokenizer, doing scaling laws at tokenizer levels and then training downsteam tasks all in one paper.

---

Finally, we hope we have addressed all of the reviewer’s concerns. As acknowledged, the paper already includes several key contributions suitable for NeurIPS:
(a) a novel single-pass adaptive tokenizer,
(b) a loss-conditioned training scheme inspired by the seminal Upside-Down RL framework,
(c.) theoretical grounding via Kolmogorov Complexity, and
(d) thorough evaluation—both through scaling laws and now via downstream tasks (thanks to the reviewer).

Thank you again for your review. We believe we’ve addressed all your queries and appreciate your feedback—it has helped us make the paper more complete. As the discussion period is coming to a close, we would be grateful for any follow up comments and rating update. We remain committed to improving the draft based on any additional input.

---

We’d also like to share that we have now evaluated Flextok. Despite being a single-pass method, significantly more efficient at inference, and trained only on ImageNet (while Flextok uses DINO supervision), KARL performs on par with—or better than—Flextok on single-image metrics.

Additionally, we created a figure outlining the taxonomy of recent adaptive tokenizers for the latest version of our paper. However, due to NeurIPS rebuttal constraints, we couldn’t include it in the rebuttal document. We're happy to provide a textual summary here if helpful, though we've omitted it for brevity, as it's already included in the full rebuttal response.

---

Finally, as acknowledged by you earlier, we believe the paper contributes meaningfully to the scientific study of visual tokenizers, with several novel and important elements. We trust that the main submission, along with the rebuttal—which addresses all raised concerns—will receive a fair and thorough evaluation.

Evaluation on Downstream Tasks

Thank you for the great suggestion. We have now thoroughly evaluated KARL on multiple downstream tasks—CLIP alignment, depth estimation, semantic segmentation, vision-language modeling (VLM), and linear probing for classification. Our findings show that KARL performs comparably to other tokenizers while operating in a single pass. Additional insights and detailed results are provided in our response to Reviewer 2QbU.

---

Quantitative Analysis on OOD Datasets

Thank you for the great suggestion. We evaluated the reconstruction performance of KARL, ALIT, and One-D-Piece on three datasets: ImageNet (in-distribution), COCO (moderately OOD), and Wikipedia Images (highly OOD). This revealed an interesting trend:

• KARL's relative performance gap improves as we move further OOD—from ImageNet to COCO to Wikipedia—suggesting that training for minimality may yield more generalizable abstractions, an idea well-grounded in Algorithmic Information Theory (AIT).

Trained on Imagenet, Evaluated on COCO
$

\begin{array}{|c|ccc|ccc|ccc|} \hline *Method** & \text{L1} \times \text{10 (32)↓} & \text{LPIPS (32)↓} & \text{SSIM (32)↑} & \text{L1} \times \text{10 (64)↓} & \text{LPIPS (64)↓} & \text{SSIM (64)↑} & \text{L1} \times \text{10 (256)↓} & \text{LPIPS (256)↓} & \text{SSIM (256)↑} \\ \hline \text{One-D-Piece} & 1.372 & 0.482 & 0.333 & 1.178 & 0.414 & 0.356 & 0.945 & 0.326 & 0.407 \\ \text{ALIT} & 1.163 & 0.419 & 0.339 & 0.984 & 0.357 & 0.383 & 0.737 & 0.272 & 0.464 \\ \text{KARL} & *1.112** & *0.405** & *0.358** & *0.956** & *0.349** & *0.399** & *0.636** & *0.228** & *0.527** \\ \hline \end{array}
$

Trained on Imagenet, Evaluated on Wikipedia Image Dataset (OOD)

$

\begin{array}{|c|ccc|ccc|ccc|} \hline *Method** & \text{L1} \times \text{10 (32)↓} & \text{LPIPS (32)↓} & \text{SSIM (32)↑} & \text{L1} \times \text{10 (64)↓} & \text{LPIPS (64)↓} & \text{SSIM (64)↑} & \text{L1} \times \text{10 (256)↓} & \text{LPIPS (256)↓} & \text{SSIM (256)↑} \\ \hline \text{One-D-Piece} & 1.125 & 0.3122 & 0.4450 & 0.956 & 0.2390 & 0.4725 & 0.747 & 0.1617 & 0.5247 \\ \text{ALIT} & 0.915 & 0.3674 & 0.4638 & 0.767 & 0.3121 & 0.5063 & 0.567 & 0.2394 & 0.5835 \\ \text{KARL} & *0.863** & *0.2507** & *0.4915** & *0.733** & *0.1950** & *0.5325** & *0.485** & *0.1206** & *0.6465** \\ \hline \end{array}
$

---

More Ablations

As acknowleged, we conducted extensive ablations on architectural choices and their effect on learned KC and minimal token counts. This includes variations in encoder/decoder depth and width, continuous vs. discrete tokenization, and quantization codebook size. Thanks to your suggestion, we’ve now also included evaluations on downstream tasks and IID vs. OOD settings. We’re happy to explore additional experiments based on further feedback from the reviewer.

---

Choice of Reconstruction Thresholds During Training and Inference

A key strength of KARL is its principled treatment of reconstruction thresholds. During training, each image is either trained with $ \epsilon = 0.0 $ (lossless) or with a threshold dynamically set by the previous iteration’s reconstruction quality—effectively aligning token allocation with image complexity. This self-regulating mechanism removes the need for manual threshold tuning, a subtle but powerful feature of KARL's training design that we plan to explore further for more tasks, modalities. Basically, each image is trained for its own inherent comoplexity (or value of epsilon).

At inference time, the threshold $ \epsilon $ can be chosen based on the needs of downstream tasks. For example, as shown in our downstream evaluations (see response to Reviewer 2QbU), coarse tasks like CLIP alignment tolerate higher $ \epsilon $ (e.g., 0.5–0.9) with minimal performance drop, while yielding significant token savings.

---

Missing Error Bars

We assume the reviewer refers to error bars across seeds and other sources of randomness, including statistical significance testing. This is a valuable suggestion—we will include such analyses in the final version.

---

We hope our overall contributions—including the novel problem statement of single-pass adaptive tokenization, the loss-conditioned training strategy (inspired by the seminal Upside-Down Reinforcement Learning framework), theoretical grounding in Kolmogorov Complexity and AIT, extensive scaling law analysis, and now, comprehensive downstream evaluations—help address all of your concerns.