How to sketch a learning algorithm
2026-04-08 • Machine Learning
Machine Learning
AI summaryⓘ
The authors study how removing parts of the training data affects AI model behavior, which is important for understanding and controlling models. They propose a method that, after some initial work, can quickly predict how a model would perform if certain data were left out, with very small error. Their approach relies on a property called "stability," which they argue is realistic for powerful models. They tested this on a small model named microgpt and provide their code for others to try. The technique uses advanced math involving derivatives to efficiently approximate these model changes.
data deletionstabilitydeep learningautomatic differentiationarithmetic circuitsmodel interpretabilitymicrogptprecomputationhigher-order derivativessketching
Authors
Sam Gunn
Abstract
How does the choice of training data influence an AI model? This question is of central importance to interpretability, privacy, and basic science. At its core is the data deletion problem: after a reasonable amount of precomputation, quickly predict how the model would behave in a given situation if a given subset of training data had been excluded from the learning algorithm. We present a data deletion scheme capable of predicting model outputs with vanishing error $\varepsilon$ in the deep learning setting. Our precomputation and prediction algorithms are only $\mathrm{poly}(1/\varepsilon)$ factors slower than regular training and inference, respectively. The storage requirements are those of $\mathrm{poly}(1/\varepsilon)$ models. Our proof is based on an assumption that we call "stability." In contrast to the assumptions made by prior work, stability appears to be fully compatible with learning powerful AI models. In support of this, we show that stability is satisfied in a minimal set of experiments with microgpt. Our code is available at https://github.com/SamSpo1/microgpt-sketch. At a technical level, our work is based on a new method for locally sketching an arithmetic circuit by computing higher-order derivatives in random complex directions. Forward-mode automatic differentiation allows cheap computation of these derivatives.