CAPSkip: Cancellation-Aware Prefix Skipping for Selective Backpropagation
Organizations: Yonsei University · Sooil Development · NCreate
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 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).
Figures & tables
| stage (ms/step) | forward | selector | gather | backward | optimizer |
|---|---|---|---|---|---|
| dense | 2.77 | – | – | 6.97 | 0.22 |
| CAPSkip, reusing execution | 2.70 | 0.12 | 0.60 | 4.66 | 0.22 |
| seed | dense 103 ep | dense 59 ep | CAPSkip 103 ep | CAPSkip dense 59 | CAPSkip dense 103 | rows bwd (%) |
| 17 | 87.07 | 86.94 | 87.24 | 34.9 | ||
| 29 | 87.29 | 87.07 | 87.34 | 35.1 | ||
| 43 | 87.39 | 86.99 | 87.16 | 34.8 | ||
| mean [95% CI] | 87.25 | 87.00 | 87.25 | [+0.08, +0.42] | [-0.51, +0.51] | |
| train time (s) | 1541 | 883 | 887–890 |
| arm | rows bwd | dense margin (pp) | time / top-1 vs CAPSkip 103 ep | margin contrast (pp) |
|---|---|---|---|---|
| CAPSkip | 35% | [+0.07, +0.42] | – | – |
| Selective-Backprop, same execution | 33.9% | [-0.55, -0.22] | 0.919 / [-1.08, -0.34] | [+0.29, +0.97] |
| InfoBatch ( ) | 100% | [-0.22, +0.05] | 1.077 / [-0.44, -0.14] | [+0.29, +0.37] |
| random + rescale | 100% | [-0.23, +0.23] | 1.077 / [-0.65, +0.25] | [-0.13, +0.61] |
| InfoBatch weighted CAPSkip | 37.6% | [+0.02, +0.56] | 0.647 / [-0.97, +0.36] | [-0.49, +0.40] |
| epochs | time ratio | test diff (pp) |
|---|---|---|
| 100 | 0.926 [0.900, 0.954] | [-0.72, +0.43] |
| 120 | 0.928 [0.920, 0.936] | [-0.92, +0.16] |
| 140 | 0.927 [0.925, 0.929] | [-0.30, +0.30] |
| 160 | 0.920 [0.913, 0.926] | [-0.69, +0.35] |
| 200 | 0.918 [0.915, 0.921] | [-0.24, +0.13] |
| arm | vs InfoBatch: time / test (pp) | bar passed | removal | |
|---|---|---|---|---|
| one machine per seed | unweighted CAPSkip inside IB | 0.918 [0.908, 0.929] / [-0.86, -0.19] | no | 0.508 |
| weighted CAPSkip inside IB | 0.924 [0.915, 0.934] / [-0.26, +0.19] | yes | 0.503 | |
| weighted, up-weighted rows excluded | 1.048 [1.037, 1.060] / [-0.37, +0.49] | no (time) | 0.401 | |
| IB first half, CAPSkip second half | 1.084 [1.076, 1.092] / [-0.12, +0.69] | no (time) | 0.367 | |
| single machine | weighted CAPSkip inside IB | 0.910 [0.908, 0.912] / [-0.45, +0.17] | no (acc.) | – |
| same, masked-loss execution | 1.016 [1.015, 1.018] / [-1.02, +0.43] | no | 0.502 |
| 0.09 | 0.848 |
| 0.15 | 0.810 |
| 0.25 | 0.763 |
| 0.4 | 0.695 |
| 0.6 | 0.631 |
| 1.0 | 0.610 |
Backpropagation
Backpropagation computes neural-network gradients by propagating errors backward through layers, enabling end-to-end training.
See all 48 papers