We sincerely thank you for your insightful, and positive feedback.

On Weaknesses

• More experiments in the main paper: Due to the strict page limit, we moved many experimental details and additional results to the appendix. We will revise the main text to include a more detailed discussion of our key experimental findings (e.g., from Figure 5) to better support our theoretical claims within the main paper.

• Significance and Originality: While the importance of LV regularization was known heuristically, our work provides the first rigorous, information-theoretic proof that explains why this holds for VQ-VAEs, and that the generalization gap is independent of the decoder. We also agree it is a limitation that the bound in Theorem 3 is not immediately computable, but we see its main value as a theoretical tool that proves the existence of a well-behaved, asymptotically vanishing bound, paving the way for future work on practical estimators.

Moreover, grounded in this rigorous theory, our analysis has direct practical implications. These include the importance of encoder design under a decoder‑independent bound, the theoretical justification of KL regularization, and insights regarding data‑dependent priors. For further details, please see our response to Reviewer qLsN (Q1). As also stated in our response to Reviewer qLsN (Q1), using a data‑dependent prior not only makes the bound theoretically evaluable but also leads to improved model performance numerically in practice. These implications follow from a formal theory, and we believe they provide important guidance for VQ‑s. We plan to add a new Practical Implications paragraph immediately before Sec. 6 to communicate the contribution of this paper more clearly to the community.

On Questions

Q1: On the detailed explanation of the supersample setting

A. We apologize that our explanation was confusing. Let us clarify the construction step-by-step:

• Supersample $\tilde{X}$: We start with a matrix $\tilde{X}$ of size $n\times 2$, containing $2n$ i.i.d. data points from the data distribution $\mathcal{D}$. Each row $m$ contains a pair of data points: $(\tilde{X}\_{m,0}, \tilde{X}\_{m,1})$.
• Random Index $U$: We generate a random binary vector $U = (U_1, \ldots, U_{n})$, where each $U_{m} \in {0,1}$.
• Training Set $\tilde{X}_U$: The training set consists of $n$ samples. For each row $m$, we select exactly one sample from $\tilde{X}$ using the index $U_m$. Therefore, the training set is $\tilde{X}\_U = (\tilde{X}\_{1,U_1}, \tilde{X}\_{2,U_2}, \ldots, \tilde{X}\_{n,U_n})$. This is a set of $n$ data points.
• Loss Matrix $l_{0}(W, \tilde{X})$: After training a model parameter $W$ on $\tilde{X}\_{U}$, we evaluate its loss on all $2n$ data points in the original supersample matrix $\tilde{X}$. The notation $l_{0}(W, \tilde{X})=((l_0(W,\tilde{X}\_{1,0}),l_0(W,\tilde{X}\_{1,1})),\dots,(l_0(W,\tilde{X}\_{n,0}),l_0(W,\tilde{X}\_{n,1})))^\top$ represents the resulting $n \times 2$ matrix of loss values.

The confusion may have arisen from the distinction between the training set (which has $n$ points) and the matrix on which the final loss is evaluated (which has $2n$ points). We will revise Section 2.3 to make this process much clearer.

Q2: On the notation for $\tilde{J}$ and $\bar{J}$

A. We will change $\bar{J}$ to a more distinctive symbol, such as $\breve{J}$ throughout the paper to improve readability. Thank you for this excellent suggestion.

Q3: On typos

A. Thank you very much for catching these typos. We will correct "insufficiently underexplored" to "insufficiently explored" and fix "that enabling" in the revised manuscript.

Dear authors, I have checked my updated rating and I confirm that it is still at 5. However, it can only be seen by PCs, SACs and other reviewers at the moment. I believe this should be the same with the ratings of other reviewers.

Edit: I just saw that reviewer qLsN clarified this for you. I thank them for being quicker in answering this question than me! Apologies for the delay, I missed the notification of the authors' answer.

We sincerely thank you for taking the time to review our paper.

On Weaknesses and Lack of Practical Contributions

We understand your main concern is that our theoretical work does not offer meaningful practical contributions. We respectfully disagree and believe this is due to our failure to clearly articulate the implications of our findings. Our work provides not just theoretical justifications for existing practices, but also concrete, actionable guidelines for model design that are supported by both our theory and new empirical evidence.

We summarize these practical contributions as follows:

1. A Clear Guideline on Encoder vs. Decoder Design

Our central results, Theorems 2, 3, and 4, show that the generalization gap is independent of the decoder's complexity and is instead governed by the complexity of the encoder and the latent variables (LVs). This provides a clear design guideline: to improve generalization, one should focus on the complexity of the encoder's architecture and its regularization since the decoder's capacity has little impact on generalization. This finding is also empirically supported by our experiments in Figures 2, 4, and 6.

Furthermore, our analysis reveals a crucial distinction between the roles of the latent space dimension $d\_z$ and the codebook size $K$. While their contribution to generalization might seem similar at first glance, our theory clarifies a fundamental difference. From a theoretical viewpoint, increasing the latent dimensionality $d\_z$ enlarges the generalization bound, whereas the bound does not depend on the codebook size $K$. This follows from Theorem 4 (see Line 332), which depends explicitly on $d\_z$ but is independent of $K$. Consistently, our Appendix experiments indicate that enlarging $K$ has little effect on the generalization error.

2. Insight into Prior Design

Lemma 2 suggests that the optimal prior to minimize the empirical KL divergence is an empirical marginal distribution estimated from the training data, which is analogous to mixture priors like VampPrior. This provides theoretical insight into the choice of priors. Our Lemma 2 also suggest that data-dependent priors are beneficial in the unsupervised VQ-VAE context. Motivated by this, we conducted a new experiment where we replaced the standard uniform prior in SQ-VAE with a practical approximation of a data-dependent prior (a moving average of latent usage). The results below show this theoretically-motivated change consistently improves test loss, providing direct evidence that our theory can guide the development of better-performing models.

Table 1: Test loss

We will add this discussion and the supporting data to Appendix G in the final manuscript to provide this valuable perspective to readers.

3. A Diagnostic Framework for Decoder Expressiveness

Our theory clarifies the decoder's exact role. Since Test Error ≈ Training Loss + Generalization Gap, and we prove the decoder does not affect the gap, its primary role is to minimize the training loss. This yields a diagnostic strategy: a decoder is "sufficiently expressive" when further increasing its capacity no longer significantly reduces training loss. At this point, our theory proves that focus must shift to the encoder.

To verify this, we conducted an additional experiment. The results confirmed that for larger sample sizes ($n\geq 1000$), increasing decoder complexity consistently reduces training loss, while the generalization gap remains flat (see Figure 2.). This provides empirical support for our theoretical framework. Let us refer our response to Q.3 of Reviewer nKXf for further details.

Train Loss vs Number of Residual Blocks (MNIST)

This demonstrates how our theoretical insights, while focused on the generalization gap, can inform a practical framework for reasoning about the entire model architecture. We will add this discussion and the supporting data to Appendix G.4 in the final manuscript to provide this valuable perspective to readers.

4. A Theoretical Justification for Existing Practices

Finally, our Theorems 2 and 5 provide a theoretical justification for using KL divergence as a regularization term. While KL regularization appears naturally in variational Bayes, it was previously unclear if it truly functions as a regularizer for generalization and data generation. Our research is the first to provide a formal justification for this widely used practice.

Our Revisions

To make these contributions undeniable, we will add a dedicated "Practical Implications" section to the paper to explicitly state these points. We hope these clarifications and our detailed plan for revision will convince you of the value of our work and merit a higher rating.

Reviewer qLsN

We sincerely thank you for your insightful feedback.

Q1: On the lack of direct practical implications

A. While our work does not propose a new algorithm, its primary goal is to provide a rigorous theoretical foundation with direct consequences for practitioners. Our analysis yields several key insights that explain and justify existing practices in VQ-VAE training:

• Importance of Encoder Design: Our central results (Theorems 2, 3, 4) show the generalization gap is independent of decoder complexity and is instead governed by the encoder and latent variables (LVs). This provides a clear guideline: to improve generalization, focus on the encoder's architecture and regularization since the decoder's capacity has little impact on generalization. This is empirically supported by our experiments (Figures 2, 4, 6).

• Justification for KL Regularization: Our Theorems 2 and 5 provide a theoretical justification for using KL divergence as a regularization term. While KL regularization appears naturally in variational Bayes, it was previously unclear if it truly functions as a regularizer for generalization and data generation. Our research is the first to provide a formal justification for this widely used practice.

• Insight into Prior Design: Lemma 2 suggests the optimal prior is an empirical marginal distribution from the training data, analogous to mixture priors like VampPrior, offering theoretical insight into prior choice.

To make these practical implications more explicit for the reader, we will add a summary of these points to our conclusion (Section 6).

Regarding the potential benefits of prior design: We would like to clarify that our analysis shows how a data-dependent prior can improve generalization performance. In this respect, our theoretical findings are in line with the results of Sefidgaran et al. (2023), who demonstrated that incorporating a data-dependent prior as a regularization term during training improves supervised learning performance under a decoder-independent bound. Motivated by their findings, we conducted additional experiments to evaluate the practical utility of data-dependent priors within our framework. While standard SQ-VAE employs a uniform prior, we implemented a learned prior using a moving average over latent variables during training, effectively approximating a data-dependent prior as suggested by Sefidgaran et al. (2023).

The experimental results, shown below, indicate that the data-dependent prior consistently improved test loss compared to the baseline SQ-VAE across four benchmark datasets. These results provide evidence that such priors are not only theoretically justified but also practically beneficial for training the models of unsupervised learning.

Table 1: Test loss

Q2: On choosing to increase latent dimension $d_z$ vs. codebook size $K$

A. From a theoretical viewpoint, increasing the latent dimensionality $d_z$ enlarges the generalization bound, whereas the bound does not depend on the codebook size $K$. This follows from Theorem 4 (see Line 332): under suitable assumptions, the uniform convergence bound is independent of $K$ while depending explicitly on $d_z$. Consistently, our Appendix experiments indicate that enlarging $K$ has little effect on the generalization error.

Importantly, these observations concern generalization (the generalization gap), not the overall performance, which is related to minimizing the training loss on the training set. As we also noted in our response to Q7, the fact that the bound does not depend on $K$ does not imply that $K$ is irrelevant to how small the training error can become. In practice, $K$ can influence representational capacity and optimization dynamics. A careful analysis of how $K$ affects actual performance (beyond the generalization bound) is therefore outside the present theory and is an important direction for further work. We will clarify this distinction in the paper.

Q3: On including reconstruction error in Figure 2

A. Based on your suggestion, we have run this analysis and, following your suggestion, we will add a new plot for the training loss to Figure 2 in the final version of the paper. Since the NeurIPS rebuttal policy prohibits including updated figures via external links, we present the results in the table below for your convenience.

Train Loss vs Number of Residual Blocks (MNIST)

As shown in the table, for larger sample sizes ($n\geq1000$), the training loss consistently decreases as the decoder complexity (number of Residual Blocks; RB) increases. This confirms that a more expressive decoder better fits the training data. For the small sample size setting ($n=250$), this trend is not observed, and the loss is noisy. We attribute this to the high variance inherent in training on very limited data, where a more complex model can be harder to optimize stably.

Critically, even as the training loss decreases with decoder complexity (for $n\geq1000$), the generalization gap shown in Figure 2 of our main paper remains largely unaffected. This finding more strongly supports our central claim: a more powerful decoder can reduce training error, but it does not contribute to reducing the generalization gap.

Q4: On the implications of the first KL term's behavior in Figure 2.

A. This KL term, $\mathrm{KL}(Q_{J,U}\|P)/n$, is related to the mutual information between the training data and the latent representation (see lines 231-232, and 240) and reflects how much information the encoder memorizes from the data.

The fact that this term does not converge to zero as $n$ increases is evidence that the model is learning meaningfully. If this value were to converge to zero, it would imply that the encoder has not captured any information from the training data.

This non-converging behavior of the empirical KL term is a known issue in IT-based analysis. In fact, this challenge motivated us to introduce the novel permutation-symmetric setting in Section 4, which leads to our Theorem 3, a bound asymptotically converging to zero without this term (see lines 261-268). Therefore, the behavior of this KL term highlights a limitation of the standard supersample setting (and Theorem 2) and underscores the novelty and importance of our more advanced result in Theorem 3.

Q5: On the novelty of the 2-Wasserstein distance bound compared to prior work

A. Our result is novel in providing guarantees from an information-theoretic perspective for the VQ-VAE framework where the encoder and decoder are trained jointly.

• Comparison with [1, 2]: [1] is in the context of causal inference and [2] addresses the classical $k$-means setting, whereas our work targets modern, non-linear generative models. Our bound also uniquely connects the data generation performance to the KL regularization term.

• Comparison with [3]: [3] focuses on task-driven settings, whereas our analysis is purely unsupervised. We will add this discussion to the paper to clarify our contribution's uniqueness.

To clarify the uniqueness of our contribution, we will cite these references and add a discussion comparing them with our work in Section 5 or Appendix B.2.

Q6: Practical implications of two-stage prior design

A. Theorem 5 provides the following implication for two-stage prior strategies. In this process, at the first stage, the encoder produces the latent distribution $q(J∣S)$, and at the second stage, an autoregressive model (e.g., a Transformer) is assumed to learn the prior distribution $\pi(J)$. Our theory explains that, if the objective of the second stage is trained so as to minimise the KL divergence $\mathrm{KL}(q(J∣S)∥\pi(J))$, then the upper bound of Theorem 5 is reduced, thereby improving data-generation performance. Meanwhile, the theory also suggests that the prior distribution $\pi(J)$ should be data-independent, and thus methods that avoid the strong data dependence observed in the Vamp-prior are preferable.

Q7: On the validity of focusing only on the generalization gap, not overall performance

A. Our claim is not that overall performance is independent of the decoder, but specifically that the generalization gap component is. We explicitly state that an expressive decoder is required for low training error (lines 182-185), which is essential for final performance. The core contribution is proving that the gap component can be bounded independently of the decoder. We will re-emphasize this distinction in the conclusion to avoid misunderstanding.

Reviewer nKXf

We sincerely thank you for your insightful feedback.

On Weaknesses

1. Regarding Looseness of the Bounds

We agree that the derived bounds are not numerically tight. However, our work is intended as a first step toward tight bounds for unsupervised learning models such as VAEs. As discussed in the Introduction, information‑theoretic bounds in supervised learning can become non‑vacuous by leveraging algorithmic information. In contrast, for unsupervised learning —particularly VAEs— our contribution is, to the best of our knowledge, the first to incorporate algorithmic structure (latent variables) into generalization bounds.

Our primary goal was not to provide a tight estimator of the generalization gap, but to use the bounds to reveal structural dependencies of generalization in VQ‑VAEs. Even if numerically loose (and potentially vacuous in some regimes), the bounds provide practically relevant insights. In particular, the key structural conclusion—that the generalization gap is independent of the decoder—follows from our analysis regardless of the bound’s absolute value. Additional practical implications and supporting experiments are provided in the following. We will add brief clarifications in the revised manuscript.

Finally, we respectfully mention that, among our results, only Theorem 4 is asymptotic; the others are non‑asymptotic and explicitly leverage algorithmic information.

2. Regarding Actionable Strategies

We respectfully argue that our theory does provide actionable guidance, not by proposing a new algorithm, but by establishing a clear theoretical framework that justifies, explains, and guides high-level design decisions. Our analysis yields several key insights:

• Importance of Encoder Design: Our central results, Theorems 2, 3, and 4, show that the generalization gap is independent of the decoder's complexity and is instead governed by the complexity of the encoder and the latent variables (LVs). This provides a clear design guideline: to improve generalization, one should focus on the complexity of the encoder's architecture and its regularization since the decoder's capacity has little impact on generalization. This finding is also empirically supported by our experiments in Figures 2, 4, and 6.

• Justification for KL Regularization: The use of KL divergence as a regularization term on LVs is a common practice in variational Bayes for unsupervised learning, including VAEs. However, it was previously unclear whether it is a valid regularizer for generalization in LVs. Our Theorems 2 and 5 provide a first theoretical justification for this widely used practice.

• Insight into Prior Design: Lemma 2 suggests that the optimal prior to minimize the empirical KL divergence is an empirical marginal distribution estimated from the training data, which is analogous to mixture priors like VampPrior. This provides direct theoretical insight into the choice of priors and justifies data-driven approaches.

3. Additional experiments in the respect of Prior Design.

Our theoretical findings are in line with the results of Sefidgaran et al. (2023), who demonstrated that incorporating a data-dependent prior as a regularization term during training improves supervised learning performance under a decoder-independent bound. Motivated by their findings, we conducted additional experiments to evaluate the practical utility of data-dependent priors. Specifically, while standard SQ-VAE employs a uniform prior, we implemented a learned prior using a moving average over latent variables during training, effectively approximating a data-dependent prior as suggested by Sefidgaran et al. (2023).

The experimental results show that, across four benchmark datasets, the data-dependent prior consistently improved test loss compared to the baseline SQ-VAE. These results indicate that such priors are not only theoretically justified but also practically beneficial for training the models of the unsupervised learning. As our primary focus is to provide a learning-theoretic understanding of VQ-VAE, the development of new state-of-the-art algorithms is beyond the current scope and is left for future work.

Table 1: Test loss

4. Regarding Clarity and Intuition

We sincerely apologize that our presentation made the work difficult to follow. To address your valid concerns, we will implement the following concrete changes in the final manuscript:

• We will consolidate the "actionable strategies" discussed above into a new, dedicated "Practical Implications" section just before the conclusion. This will make the takeaways clear and accessible to a broader audience.
• Furthermore, to improve the accessibility of our proofs, we will add high-level proof sketches or outlines at the beginning of each major proof in the appendix.

On Questions

Q1: On experiments correlating complexity with theoretical quantities

A. In fact, Figure 5 in our paper is designed to do exactly this.

• Figure 5 (top row) shows how the two KL terms from our theoretical bound in Theorem 2 change with the number of samples (n). The second KL term (the CMI, which we prove converges) indeed decreases towards zero, while the first KL term (the empirical KL, which we argue does not) remains high.
• Figure 5 (bottom row) shows that both KL terms increase as the codebook size ($K$) grows.

These results directly show that the theoretical quantities in our bounds behave as predicted by our analysis when latent complexity ($K$) and sample size ($n$) are varied. This provides empirical validation for the utility and correctness of our theoretical framework. We will revise the text accompanying Figure 5 to state this connection more explicitly.

Q2: On barriers to applying the method to continuous VAEs

A. The main technical barrier is given as follows, which we mentioned as an important direction for future work.

• Discrete vs. Continuous concentration: Our proofs rely heavily on properties of discrete random variables (the codebook index $J$). For example, throughout the proofs we compute which discrete codebook each input datum is assigned to, and we apply concentration inequalities for each assignment. Therefore, in the continuous case such assignments are not available, and the proof techniques in this paper cannot be applied immediately. One may consider forcibly discretizing the latent variable space in the continuous case, but the resulting discretization error is not negligible and substantially affects the analysis. This is what makes extending our results to the continuous setting difficult.

We will add a more detailed discussion of these barriers to the limitations section (Section 6).

Q3: On determining if a decoder is "sufficiently expressive"

A. While our theory does not offer a prescriptive formula for decoder architecture—a task beyond the scope of current generalization theory—it suggests a conceptual framework for reasoning about when a decoder might be considered "sufficiently expressive."

Our theory fundamentally decouples the components of test error: Test Error = Training Loss + Generalization Gap. We prove that the decoder's complexity does not affect the latter term. This leads to a crucial insight: the decoder's primary role, from a generalization perspective, is to minimize the training loss.

This principle allows one to form a diagnostic strategy. A decoder could be considered "sufficiently expressive" when it is no longer the limiting factor in minimizing the overall test error. In practice, one can monitor the training loss while increasing decoder capacity. If further increases in capacity no longer yield significant reductions in training loss, it suggests the point of diminishing returns may have been reached. At this stage, our theory indicates that additional decoder complexity is unlikely to help the generalization gap, and the focus could then shift to the encoder and LV regularization to reduce the gap.

Our own experimental data is consistent with this line of reasoning. Since the NeurIPS rebuttal policy prohibits including figures via external links, we present the results in the table below for your convenience.

Train Loss vs Number of Residual Blocks (MNIST)

This demonstrates how our theoretical insights, while focused on the generalization gap, can inform a practical framework for reasoning about the entire model architecture. We will add this discussion and the supporting data to Appendix G.4 in the final manuscript to provide this valuable perspective to readers.