Requential Coding: Measuring Model Compressibility by Coding Data Instead of Parameters

Beyond reducing the memory footprint and costs for deployment, the extent to which a probabilistic model can be compressed is central to understanding generalization, model selection, and dataset selection. Yet with parameter-based compression methods (quantization, pruning, low-rank training) the code length scales with model size and is insensitive to how much information the model actually learned. Prequential coding sidesteps the parameter ceiling by encoding the dataset through the learning process, but its code length includes the entropy of the data. We introduce requential coding, a model coding scheme that is unconstrained by model size and does not pay for the data entropy: synthetic training samples are drawn from a teacher distribution and communicated relative to the student's current predictions via relative entropy coding, so the code length equals the cumulative teacher-student KL along the training trajectory. The resulting compressibility measure behaves qualitatively differently from parameter-based codes. The code length to reach a fixed target loss decreases with model and ensemble size, evidence that a more flexible model can be far simpler than its parameter count implies. Plugged into a PAC-Bayes bound, requential coding produces non-vacuous generalization guarantees that improve with scale and beat even the lossless idealization of the 4-bit GPTQ baseline that previously gave state-of-the-art bounds on compute-optimal LLMs. The same code length predicts overfitting in data-constrained training and tracks intuitive ordering of dataset complexity across CIFAR-5M, OpenWebText, and FineWeb.