CAPSkip: Cancellation-Aware Prefix Skipping for Selective Backpropagation

Abstract

Per-step selective back-propagation forwards every example of a mini-batch but back-propagates only some of them. Most rules rank examples by loss or gradient magnitude, but such scalar scores ignore cancellation between per-example gradients: the gradient removed by a set can be much smaller than its individual magnitudes suggest. We introduce CAPSkip (Cancellation-Aware Prefix Skipping). Among the examples the model already classifies correctly, CAPSkip skips the longest prefix, in increasing order of last-layer gradient norm, whose vector sum stays within a relative budget $b$ of the batch's last-layer gradient. In exact arithmetic this bounds the change of the raw final-layer gradient, using rank-one contributions already available from the forward pass; the bound does not extend to deeper layers, optimizer updates, or the training trajectory. Because the cumulative distortion is not monotone in the prefix length, CAPSkip scans all prefixes; a factorised Gram matrix makes the scan cheap and keeps it on the device. With activation reuse and selected-row backward, CAPSkip fine-tunes DeiT-S on CIFAR-100 for 103 epochs in 0.576x the time of 103-epoch dense training, and is +0.25 pp [+0.08, +0.42] above an approximately time-matched 59-epoch dense run (n=3).