Algorithmic Information Dynamics of Learning: A Certified, Differentiable Complexity Controller for Grokking
Abstract
Algorithmic Information Dynamics (AID) studies systems by perturbing them and measuring changes in algorithmic complexity, but its usual estimator, the Block Decomposition Method, is piecewise constant, restricting the calculus to finite differences. We use KCDMsF, a certified, differentiable estimator, to bring the calculus into learning dynamics: grokking, where a complexity order parameter is known but has not been made to act. As a transient loss kick, the estimator becomes a controller that accelerates grokking in Levin's description-length--versus-time sense, within a data-dependent Occam boundary whose finite-size trend, fc∼ln p/p, is consistent with a coupon-collector interpretation. Ablations show that a complexity gate matches a train-loss gate in rescuing failing seeds with 27% less intervention; among the tested signals, only map complexity marks the transition's completion; the certified prior and the per-parameter ∇ K attribution are both fungible (a uniform-prior sensor makes bit-identical gate decisions, and random supports match ∇ K-selected ones above a sparsity threshold); and direct field perturbation shows a nucleation-like response to the Occam field (no linear regime is resolved over the probed amplitudes, so these measurements do not justify a fluctuation--dissipation surrogate), with a finite-field response growing by orders of magnitude toward the phase-transition. These measurements account for the empirically tuned staircase: bang--bang pulses, stall-fired and released on yield, whose iteration plausibly builds the response it exploits. The kick transfers to sparse parity and to a transformer; a sustained weight-space loss fails. The algorithmic estimator's distinct contribution is timing (when to fire and when to release), not attribution.
Related
- On a Closed-Loop Controller for the Coevolutionary Model of Actions and Opinions via Broadcasting Information
- Certified Inference and Training for Deep Equilibrium Networks: A Continuation Framework with Polynomial Complexity Guarantees
- Pay Only for Disagreement: Certified No-Regression Verdicts for Model Updates with Matching Label-Complexity Bounds
- Improved Gradient Complexity for Quasi-Newton Proximal Extragradient Methods via Certified Curvature Reuse
- Certified Bayesian optimal experimental design: from Expected Information Gain to Signal-to-Noise Ratio
BibTeX
@misc{ozelim2026algorithmic,
title = {{Algorithmic Information Dynamics of Learning: A Certified, Differentiable Complexity Controller for Grokking}},
author = {Luan Ozelim and Abicumaran Uthamacumaran and Hector Zenil},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.13197},
eprint = {2609.13197},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.13197},
note = {CC BY-NC-SA 4.0},
}
RIS
TY - UNPB
TI - Algorithmic Information Dynamics of Learning: A Certified, Differentiable Complexity Controller for Grokking
AU - Luan Ozelim
AU - Abicumaran Uthamacumaran
AU - Hector Zenil
PY - 2026
DA - 2026/09/15
PB - arXiv
DO - 10.48550/arxiv.2609.13197
UR - https://arxiv.org/abs/2609.13197
AB - Algorithmic Information Dynamics (AID) studies systems by perturbing them and measuring changes in algorithmic complexity, but its usual estimator, the Block Decomposition Method, is piecewise constant, restricting the calculus to finite differences. We use K^CDM_sF, a certified, differentiable estimator, to bring the calculus into learning dynamics: grokking, where a complexity order parameter is known but has not been made to act. As a transient loss kick, the estimator becomes a controller that accelerates grokking in Levin's description-length--versus-time sense, within a data-dependent Occam boundary whose finite-size trend, f_c∼ln p/p, is consistent with a coupon-collector interpretation. Ablations show that a complexity gate matches a train-loss gate in rescuing failing seeds with 27% less intervention; among the tested signals, only map complexity marks the transition's completion; the certified prior and the per-parameter ∇ K attribution are both fungible (a uniform-prior sensor makes bit-identical gate decisions, and random supports match ∇ K-selected ones above a sparsity threshold); and direct field perturbation shows a nucleation-like response to the Occam field (no linear regime is resolved over the probed amplitudes, so these measurements do not justify a fluctuation--dissipation surrogate), with a finite-field response growing by orders of magnitude toward the phase-transition. These measurements account for the empirically tuned staircase: bang--bang pulses, stall-fired and released on yield, whose iteration plausibly builds the response it exploits. The kick transfers to sparse parity and to a transformer; a sustained weight-space loss fails. The algorithmic estimator's distinct contribution is timing (when to fire and when to release), not attribution.
ER -