Requential Coding: Pushing the Limits of Model Compression with Self-Generated Training Data
Shikai Qiu, Marc Finzi, Yujia Zheng, Kun Zhang, Andrew Gordon Wilson
Abstract
Compression is fundamental to intelligence. A model that can represent its training data as a short code has discovered regularities that enable generalization. Large neural networks may learn functions far simpler than their parameter counts suggest, but it is challenging to construct codes that realize this simplicity. Parameter-based methods such as quantization produce code lengths that scale with model size, insensitive to how much information the parameters store. Prequential coding bypasses this issue by compressing the training trajectory, but codes the exact data sequence regardless of how much the model learns, yielding large codes when the data has high entropy. We introduce requential coding, where a teacher model selects training samples drawn from the student's own distribution. The student's code records only these selections, which cost bits only where teacher and student disagree. The resulting code length is independent of parameter count and data entropy, and often orders of magnitude shorter than the prequential counterpart, with an advantage that grows with scale. This compression sheds light on phenomena inaccessible to prior compressors. Holding loss fixed, larger models and ensembles compress to much smaller sizes despite more parameters. Plugged into a PAC-Bayes bound, the requential code yields state-of-the-art generalization guarantees for billion-parameter LLMs, outperforming bounds built on aggressive post-training quantization even granted zero error. The bound tightens with scale in the compute-optimal regime, as models become increasingly compressible relative to dataset size. The same code predicts that models gradually overfit when trained for multiple epochs. It also isolates the learnable information in a dataset from its unpredictable, random content, revealing that lower-entropy text holds far more learnable structure than higher-entropy image data.
AI Impact Assessments
(1 model)Scientific Impact Assessment: Requential Coding
1. Core Contribution
The paper introduces requential coding, a model compression method that fundamentally decouples code length from both parameter count and data entropy—two quantities that inflate existing compression approaches. The key insight is elegant: instead of coding the exact training data (prequential coding) or the parameters directly (quantization/pruning), the student model generates its own candidate training samples, and the teacher model selects among them. Only the selection indices are transmitted, costing bits proportional to the KL divergence between teacher and student distributions—which is small when they agree. This is achieved through relative entropy coding (REC), where shared randomness between encoder and decoder means only the accepted proposal index needs transmission.
The decomposition in Eq. (1) clearly illustrates why prequential coding is wasteful: it pays data entropy even after the model stops learning. Requential coding eliminates this term entirely by making the training data self-generated, and also avoids paying the full approximation error by encoding only incremental teacher-student disagreements.
2. Methodological Rigor
The theoretical foundations are solid. The code length bound (Theorem A.2) is carefully derived with explicit constants, and Appendix B provides a thorough concentration analysis showing the realized code length stays close to its conditional mean. The martingale decomposition (Proposition B.1) properly handles the complication that REC selections alter subsequent training dynamics.
The method is a legitimate lossless compression scheme with well-defined encoder/decoder protocols. The paper is honest about practical limitations: actual encoding via ORC requires exponentially many proposals in KL, and the block-size tradeoff (Figure 10) transparently illustrates this cost. The distinction between evaluating code length (cheap) and actually transmitting (expensive) is clearly stated.
The experimental comparisons are somewhat favorable to requential coding by design: the PTQ baseline is an idealized lossless 4-bit quantization that assumes zero quantization error, making the requential code's superiority more impressive. However, the comparison against the prequential heuristic (which isn't a valid code) is appropriate, as the paper clearly labels it as non-rigorous.
3. Potential Impact
Generalization theory: The most significant impact is in PAC-Bayes generalization bounds. Achieving state-of-the-art non-vacuous bounds for billion-parameter LLMs that tighten with scale in the compute-optimal regime is a landmark result. The power-law decay of bits-per-parameter (N^{-0.46} for CIFAR-5M, N^{-0.15} for FineWeb) suggests the certified generalization gap vanishes with scale—providing theoretical backing for the empirical success of scaling laws.
Understanding scaling: The demonstration that larger models compress to fewer bits at fixed loss (Figure 5) directly addresses a fundamental tension in deep learning theory: why overparameterized models generalize. This was previously argued heuristically but never demonstrated with a valid compression scheme at this scale.
Data characterization: The epiplexity application (Figure 9) provides a principled way to compare datasets by learnable information content, separating structure from entropy—potentially useful for data selection in pre-training.
Multi-epoch overfitting: The ability to predict gradual overfitting under data repetition (Figure 8) connects compression to a practical training concern.
4. Timeliness & Relevance
This work is highly timely. As LLMs scale to hundreds of billions of parameters, the gap between empirical generalization success and theoretical understanding has widened. The previous state-of-the-art (Finzi et al., 2025) relied on GPTQ quantization for PAC-Bayes bounds, and this paper demonstrates that beating even the lossless idealization of 4-bit PTQ is possible. The compute-optimal scaling regime (D=20N) is precisely the regime practitioners operate in, making these results directly relevant.
5. Strengths
6. Limitations
7. Additional Observations
The connection between compression and generalization is not new (MDL, PAC-Bayes), but the contribution of a compressor that actually works well at scale is what has been missing. This paper fills that gap convincingly. The writing is exceptionally clear, with the decomposition of prequential code length (Eq. 1) and Figure 1 providing immediate intuition. The use of GPT 5.5 for calculations in Appendix B is noted transparently.
Generated Jul 14, 2026
Comparison History (55)
Paper 1 introduces a fundamentally novel compression paradigm (requential coding) that addresses core limitations of both parameter-based and prequential methods. Its independence from parameter count and data entropy is a conceptual breakthrough with broad implications: explaining generalization, overfitting dynamics, learnable-vs-random information, and scaling laws. It also achieves SOTA generalization bounds. Paper 2 is a solid, valuable application of PAC-Bayes bounds to RLVR, but is more incremental and domain-specific. Paper 1's foundational insights about compression and intelligence offer wider cross-field impact and greater methodological novelty.
Paper 1 introduces a highly novel compression framework (requential coding) that changes how code length depends on parameter count and data entropy, enabling new empirical insights and state-of-the-art PAC-Bayes generalization bounds for billion-parameter LLMs—timely and broadly relevant to scaling laws, compression, and theory. Its impact spans learning theory, practical model evaluation, and understanding overfitting/compressibility at scale. Paper 2 is impactful for ML privacy/robustness, offering a compelling reframing and a new training regime, but its scope is narrower (primarily vision MIAs) and less broadly foundational than Paper 1’s theory+scaling implications.
Paper 1 introduces a genuinely novel compression method with broad theoretical implications, connecting compression to generalization, model scaling, and information theory. Its state-of-the-art PAC-Bayes bounds for billion-parameter LLMs and insights into overfitting and learnable information have wide-reaching relevance across ML theory. Paper 2 addresses an important problem (hallucination via verified reasoning) with rigorous formal methods, but its evaluation is narrow (n=120), the approach is complex to deploy at scale, and impact is more domain-specific. Paper 1's fundamental contributions and cross-cutting theoretical significance give it broader potential impact.
Paper 2 is more likely to have higher scientific impact: it introduces a broadly applicable, theoretically grounded compression framework (requential coding) that yields parameter-count- and data-entropy–independent code lengths, enables new empirical insights about scaling/overfitting, and produces state-of-the-art PAC-Bayes generalization guarantees for billion-parameter LLMs. This bridges information theory, learning theory, and practical LLM analysis, with potential downstream influence on generalization evaluation, dataset characterization, and scaling-law understanding. Paper 1 is novel and practically promising for reasoning RL, but is narrower in scope and may be more sensitive to training/inference setup specifics.
Paper 2 introduces a fundamentally new compression paradigm (requential coding) with strong theoretical leverage: parameter- and data-entropy–independent code lengths, scale-dependent insights, and direct integration into PAC-Bayes bounds yielding state-of-the-art generalization guarantees for billion-parameter LLMs. Its implications span learning theory, generalization, compression, scaling laws, and dataset analysis, with high timeliness for understanding large-model behavior. Paper 1 is novel and practically useful for controllable generation, but its impact is narrower (primarily generative modeling) and more empirical/interface-focused than theory-shifting.
Paper 2 offers a fundamental theoretical breakthrough in machine learning, addressing core challenges in model compression and generalization bounds for billion-parameter LLMs. While Paper 1 presents an impressive, highly applied tool for spatial biology, Paper 2's 'requential coding' introduces a novel paradigm that decouples code length from parameter count. This provides state-of-the-art PAC-Bayes guarantees and insights into deep learning phenomena like overfitting and data entropy. Its foundational nature gives it a broader potential impact across all disciplines utilizing AI, making its scientific footprint potentially larger.
Paper 2 introduces a fundamentally new compression principle (requential coding) that changes how model complexity and generalization are quantified, with implications spanning ML theory (PAC-Bayes bounds), scaling laws, dataset structure, and practical evaluation of LLMs. Its claims are broadly applicable across architectures and modalities and are highly timely given the focus on scaling and guarantees for billion-parameter models. Paper 1 is impactful for operational subseasonal forecasting, but it is more domain-specific and largely an applied calibration/bias-correction advance rather than a cross-field conceptual breakthrough.
Paper 1 demonstrates higher potential impact due to its profound cross-disciplinary applicability and immediate real-world results. By scaling evaluation-driven discovery loops, it generated novel, state-of-the-art solutions across 21 problems in six diverse domains, including concrete improvements to LASSO and quantum circuits. While Paper 2 offers significant theoretical advancements in LLM compression and generalization bounds, Paper 1 provides a highly timely, practical framework that acts as a force multiplier for automated scientific discovery, promising to rapidly accelerate research across numerous fields.
Paper 1 offers a fundamental theoretical breakthrough in AI, solving long-standing challenges in model compression and generalization bounds for billion-parameter LLMs. Its domain-agnostic approach provides profound insights into scaling laws, overfitting, and data entropy across all deep learning fields. While Paper 2 presents highly valuable clinical applications, Paper 1's contributions to the underlying mechanics of modern AI will likely drive broader, cross-disciplinary methodological shifts and foundational advancements.
Paper 1 offers a notably novel compression/coding framework (requential coding) that decouples code length from parameter count and data entropy, with strong theoretical integration (PAC-Bayes) and demonstrated scalability to billion-parameter LLMs. Its implications span generalization theory, scaling laws, overfitting diagnostics, and dataset structure analysis—broad, timely, and likely reusable across many model families. Paper 2 is innovative for diffusion expert composition via factor-wise routing and shows promising ARC-AGI gains, but appears narrower in scope (discrete diffusion + specific compositional setting) and its impact may depend on broader adoption of that paradigm.