Requential Coding: Pushing the Limits of Model Compression with Self-Generated Training Data

Source: arXiv:2607.11883 · Published 2026-07-13 · By Shikai Qiu, Marc Finzi, Yujia Zheng, Kun Zhang, Andrew Gordon Wilson

TL;DR

This paper introduces requential coding, a novel technique for compressing neural network models by encoding training trajectories via self-generated synthetic data selected by a teacher model. Unlike prior parameter-focused methods (e.g., quantization) whose code lengths scale with model size and fail to capture how much information the model actually stores, or prequential coding that encodes the full training data trajectory regardless of learnability, requential coding records only the teacher's selections of student-generated samples, incurring bits only where teacher and student disagree. This leads to code lengths independent of parameter count and data entropy, often orders of magnitude smaller than prequential codes, especially at large scale. The authors demonstrate that larger models and ensembles compress to smaller sizes at fixed loss, revealing that scale improves compressibility and generalization. Plugged into PAC-Bayes theory, the requential code yields state-of-the-art generalization bounds for billion-parameter language models, outperforming previous bounds based on 4-bit post-training quantization and tightening with scale in the compute-optimal regime. The technique also isolates learnable information from noisy dataset entropy and predicts gradual overfitting under repeated training. Overall, requential coding offers a principled, scalable compression method illuminating deep learning generalization with practical theoretical guarantees.

Key findings

• The requential code length is bounded by the cumulative teacher-student KL divergence, typically much smaller than prequential code lengths dominated by dataset entropy (Fig 4).
• On OpenWebText, CIFAR-5M, and FineWeb datasets with 100M-parameter transformers, requential coding reduces model code size by 1-2 orders of magnitude versus prequential coding at similar loss.
• Larger models can be compressed to fewer bits than smaller models at fixed loss despite having more parameters, breaking the 1 bit/parameter floor typical for quantization (Fig 5).
• Ensembling multiple models (up to 8) further reduces the compressed code size for the same loss (Fig 6).
• Using requential coding plugged into PAC-Bayes bounds yields generalization guarantees that improve with increasing model size, matching and improving test loss trends (Fig 7).
• The requential bound outperforms an idealized lossless 4-bit post-training quantization baseline, especially under compute-optimal training (Fig 7 middle).
• Compression per parameter decays as a power law with model size, predicting the generalization gap vanishes asymptotically (Fig 7 right).
• Teacher smoothing and iso-loss projection techniques reduce the code length further without harming final loss (Fig 4).

Threat model

n/a — This work targets general model compression and theoretical understanding of generalization, not adversarial threat detection or defense scenarios.

Methodology — deep read

The paper addresses the challenge of compressing large neural network models to reflect the true amount of learned information rather than parameter count or raw data entropy. Prior methods fall into two categories: parameter-based compression (e.g., pruning, quantization) which compress model weights but scale with model size regardless of learned information, and prequential coding which sequentially encodes the exact training data batches given models but includes irreducible data entropy and large approximation error contributions.

Requential coding improves upon this by having a student model Pt generate training samples from its own distribution and a teacher Qt select a subset of these samples to train on. Instead of encoding the exact data batch, the encoded message records which candidate sample the teacher accepts. This acceptance is performed via relative entropy coding (REC), a compression primitive that encodes a sample from a target distribution Q relative to a proposal distribution P using shared randomness between encoder and decoder. REC enables encoding indices of proposed samples such that the accepted sample distribution matches the teacher's.

The protocol is as follows: both encoder and decoder initialize the student model P0 and share a pseudorandom number generator (PRNG) seed s. At training step t, encoder generates an indexed sequence of candidate samples Y_t^(i) from Pt using the PRNG. The teacher model Qt evaluates these candidates and chooses an accepted sample X_t that is marginally distributed as Qt. REC encodes the acceptance index i*_t into a prefix-free code m_t with expected length close to KL(Qt || Pt). The decoder decodes m_t and regenerates X_t from Pt and the PRNG, then both sides update Pt+1 by training on X_t using a deterministic update rule G (e.g., gradient descent). Repeating this T times produces a code (m_0,...,m_{T-1}) representing the final student model PT.

The teacher sequence is often constructed by training a model on real data with similar architecture/hyperparameters to the student, ensuring low KL divergence between Qt and Pt at each step. Teacher smoothing with exponential moving averages and iso-loss projection (periodic teacher resets matching student performance) further reduce code length.

The code length is provably bounded by the cumulative sum of KL divergences at each step plus small logarithmic factors. Unlike prequential coding which must encode exact data sequences with entropy H(X_t), requential coding only encodes bits where the teacher distribution departs from the student's.

The authors benchmarked requential coding versus prequential coding and parameter quantization on 100M-parameter transformers trained on text (OpenWebText, FineWeb) and image (CIFAR-5M) datasets. The evaluation measured model loss vs code length curves, computing the approximate KL-based code length by simulating teacher-student trajectories. They also evaluated scale effects by training a range of model sizes and ensembles.

They plugged the resulting code lengths into PAC-Bayes bounds to certify generalization guarantees for large autoregressive language models. This involved using existing theoretical bounds connecting compressed code length and empirical risk to expected risk, and comparing against idealized post-training quantization baselines.

The authors provide pseudocode and source code for the requential encode/decode processes, REC implementation details, teacher design heuristics, and full hyperparameter settings for reproducibility. Some limitations include computational overhead (approx. 2.33x training FLOPs) and slow encoding times depending on REC implementation. The method relies on access to a teacher trained on real data, which is not transmitted but impacts evaluation.

Technical innovations

• Requential coding compresses a model by encoding only teacher selections from synthetic student-generated samples via relative entropy coding, making code length independent of parameter count and data entropy.
• Use of shared pseudorandom proposal sequences and REC enables efficient communication of training sample indices with expected length bounded by KL divergence between teacher and student at each step.
• Teacher smoothing and iso-loss projection reduce teacher-student divergences, significantly shortening code length without loss in performance.
• Demonstration that requential coding provides a valid lossless compression scheme of distilled models enabling principled PAC-Bayes generalization bounds tighter than prior quantization-based approaches.

Datasets

• OpenWebText — 2B tokens — public internet text corpus
• FineWeb — 2B tokens — filtered large web text dataset
• CIFAR-5M — 5 million images tokens — preprocessed CIFAR dataset

Baselines vs proposed

• Prequential coding: code length per token ~10-100x larger than requential coding at equivalent loss (Fig 4)
• Post-training quantization (PTQ) 4-bit: compressed size ~1 bit/parameter, requential code beats this, e.g., reaches ~0.15 bits/parameter for 108+ parameter models (Fig 5,7)
• Prequential heuristic: non-rigorous estimate lies above requential code length curve (Fig 4)
• At fixed loss, larger models: requential code length drops even as parameter count grows by orders of magnitude (Fig 5)
• Larger ensembles reduce code length at fixed loss compared to single models despite increasing total parameters (Fig 6)

Figures from the paper

Figures are reproduced from the source paper for academic discussion. Original copyright: the paper authors. See arXiv:2607.11883.

Fig 3: Iso-loss projection.

Limitations

• Computational overhead: approximately 2.33× training FLOPs required to evaluate code lengths due to teacher and student forward-backward passes.
• Encoding time can be prohibitively slow in practice due to the need for many proposals in REC; practical implementations must trade off code length vs encoding speed.
• Teacher models are required and must be trained on real data, which may limit applicability when such teachers are unavailable.
• Method primarily evaluated on distillation compression; compressing models not trained via distillation requires additional steps and may not be lossless.
• Experiments focus on autoregressive transformer architectures and selected datasets; generalization to other model families or tasks is not explored.
• No adversarial evaluation of worst-case compressibility or robustness to distribution shifts beyond the considered datasets.

Open questions / follow-ons

• Can requential coding be adapted or optimized for non-distilled models to achieve similar compressibility?
• How can teacher sequences be better designed or learned automatically to minimize code length further?
• What are practical encoding/decoding speed-up methods for REC to enable real-world model transmission?
• Can the approach generalize effectively beyond autoregressive transformers to other architectures and modalities?

Why it matters for bot defense

For bot-defense and CAPTCHA practitioners, requential coding provides a new lens on model compression that directly measures how much meaningful information is learned versus memorized noise. Understanding the compressibility of large models at scale with this method can inform model selection and training strategies that optimize generalization and robustness, potentially reducing attack surfaces from overly memorize-prone models. Moreover, the framework’s ability to isolate learnable data structure from random content could guide data curation to improve model robustness against adversarial or synthetic inputs often encountered in bot detection contexts. While implemeting requential coding directly in CAPTCHA systems may be computationally intensive currently, its theoretical insights into scaling laws and generalization bounds could inspire more efficient defenses that leverage inherent compressibility properties.

Cite

@article{arxiv2607_11883,
  title={ Requential Coding: Pushing the Limits of Model Compression with Self-Generated Training Data },
  author={ Shikai Qiu and Marc Finzi and Yujia Zheng and Kun Zhang and Andrew Gordon Wilson },
  journal={arXiv preprint arXiv:2607.11883},
  year={ 2026 },
  url={https://arxiv.org/abs/2607.11883}
}

Read the full paper

• arXiv:2607.11883 (abstract)
• arXiv:2607.11883 (PDF)