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).
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
Table 1: Execution cost, CIFAR-100 ResNet-18-GN, B=128 , b=0.09 . Top: per-step stage times (ms) on an RTX 5090 from an epoch-60 training state (kept fraction ≈0.69 ). Bottom: whole-step and whole-run time ratios to dense on the same GPU; overhead = ratio −(1+2kˉ)/3 .
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
+0.30
+0.17
34.9
29
87.29
87.07
87.34
+0.27
+0.05
35.1
43
87.39
86.99
87.16
+0.17
−0.23
34.8
mean [95% CI]
87.25
87.00
87.25
+0.25 [+0.08, +0.42]
−0.00 [-0.51, +0.51]
train time (s)
1541
883
887–890
Table 2: DeiT-S fine-tuned on CIFAR-100 (test top-1, %). Approximate time matching: CAPSkip at 103 epochs vs dense at 59 epochs (primary). Rows back-propagated are a percentage of forwarded rows. Means in the last row are computed from the per-seed values.
arm
rows bwd
dense margin (pp)
time / top-1 vs CAPSkip 103 ep
margin contrast (pp)
CAPSkip
≈ 35%
+0.24 [+0.07, +0.42]
–
–
Selective-Backprop, same execution
33.9%
−0.39 [-0.55, -0.22]
0.919 / −0.71 [-1.08, -0.34]
+0.63 [+0.29, +0.97]
InfoBatch ( r=0.5 )
100%
−0.09 [-0.22, +0.05]
1.077 / −0.29 [-0.44, -0.14]
+0.33 [+0.29, +0.37]
random + rescale
100%
+0.00 [-0.23, +0.23]
1.077 / −0.20 [-0.65, +0.25]
+0.24 [-0.13, +0.61]
InfoBatch → weighted CAPSkip
37.6%
+0.29 [+0.02, +0.56]
0.647 / −0.31 [-0.97, +0.36]
−0.05 [-0.49, +0.40]
Table 3: DeiT-S controls ( n=3 , 103 epochs each). Dense margin is accuracy minus the dense running-maximum envelope, linearly interpolated at each arm’s own runtime using 30/59/80/103-epoch dense runs. The last column compares these margins, not accuracies at one common time. CAPSkip’s interpolated margin is +0.24 pp, distinct from the direct dense59 contrast of +0.25 pp. Rows bwd is a percentage of forwarded rows.
epochs
time ratio
test diff (pp)
100
0.926 [0.900, 0.954]
−0.15 [-0.72, +0.43]
120
0.928 [0.920, 0.936]
−0.38 [-0.92, +0.16]
140
0.927 [0.925, 0.929]
−0.00 [-0.30, +0.30]
160
0.920 [0.913, 0.926]
−0.17 [-0.69, +0.35]
200
0.918 [0.915, 0.921]
−0.06 [-0.24, +0.13]
Table 4: ResNet-18-GN trained from scratch on CIFAR-100, CAPSkip ( b=0.09 ) vs dense, RTX 4090, seeds 2–6 ( n=5 ). Left: equal epochs. Right: test time-to-accuracy over the 100–200-epoch frontier.
arm
vs InfoBatch: time / test (pp)
bar passed
removal
one machine per seed
unweighted CAPSkip inside IB
0.918 [0.908, 0.929] / −0.52 [-0.86, -0.19]
no
0.508
weighted CAPSkip inside IB
0.924 [0.915, 0.934] / −0.04 [-0.26, +0.19]
yes
0.503
weighted, up-weighted rows excluded
1.048 [1.037, 1.060] / +0.06 [-0.37, +0.49]
no (time)
0.401
IB first half, CAPSkip second half
1.084 [1.076, 1.092] / +0.29 [-0.12, +0.69]
no (time)
0.367
single machine
weighted CAPSkip inside IB
0.910 [0.908, 0.912] / −0.14 [-0.45, +0.17]
no (acc.)
–
same, masked-loss execution
1.016 [1.015, 1.018] / −0.30 [-1.02, +0.43]
no
0.502
Table 5: InfoBatch composition, CIFAR-100 ResNet-18-GN, 200 epochs, n=5 unless noted. Time ratio / test difference vs InfoBatch on the same machine. Removal =1− rows back-propagated /45,000 per epoch, averaged over epochs, taken from the first experiment’s runs.
b
kˉ
0.09
0.848
0.15
0.810
0.25
0.763
0.4
0.695
0.6
0.631
1.0
0.610
Table 6: Left: kept fraction kˉ (rows back-propagated / forwarded, mean over a 30-epoch run, seed 1, RTX 4090) vs budget b . Right: re-weighting of the dropped candidates at b=1.0 (warm-up of 3 epochs, CAPSkip off in the last 12.5%), mean final validation accuracy at 200 epochs over seeds 2–4, and training time on rented RTX 5090 machines.