Uniform-block and binomial checkpoint schedules preserve reverse adjoints with stated costs

If $T=0$, both schedules return the supplied pair $(x_0,{\bar{x}}_0)$ unchanged. For $T\ge 1$ in uniform mode, deterministic replay from any block start $x_a$ reproduces the original $x_{a+1},\dots ,x_b$: the first replayed transition starts from the identical $x_a$, and induction applies each same map $F_j$ to the same preceding state. Thus the recorded local tape at step $\mathrm{\ell }$ has the same primitive inputs as the original forward trajectory, so its reverse rule is the same one used by the full tape. Processing blocks and then their steps in decreasing order is exactly reverse transition order; [F2] gives the same terminal and initial cotangents.

A block of length $r$ has replay prefix lengths $r-1,r-2,\dots ,0$ before its $r$ recorded local evaluations. Therefore its additional unrecorded evaluations total ${\sum }_{j=0}^{r-1}j=r(r-1)\mathrm{/}2$. The number of blocks is $s=\lceil T\mathrm{/}q\rceil \le m$, each $r_{\mathrm{\ell }}\le q$, so the sum is at most $mq(q-1)\mathrm{/}2$. The checkpoint indices are $0,q,\dots ,(s-1)q<T$; $T\mathrm{/}q\le m$, so $s=\lceil T\mathrm{/}q\rceil \le m$. The initial forward pass uses $T$ unrecorded evaluations; the displayed additional count concerns the subsequent block replays. Only those states, one live state, and one local tape are retained.

In binomial mode the recurrence and boundary values give $C(d,t)=\left(\genfrac{}{}{0px}{}{d+t}{d}\right)$: the binomial coefficients have the same boundary values and Pascal recurrence, so induction on $d+t$ identifies them. For $d,t\ge 1$, write $A=C(d,t-1)$, $B=C(d-1,t)$, so $C(d,t)=A+B$. If $N\ge 2$, $L=\min (N-1,A)$ satisfies $1\le L<N$; if $L=N-1$, then $R=1\le B$, and otherwise $L=A$ and $R=N-A\le B$. Thus both recursive capacities hold and both child lengths are strictly less than $N$; the recursion terminates at $N=1$ or $N=0$.

Induct on $N$. For $N=0$, the recursive procedure returns the unchanged cotangent. For $N=1$, deterministic evaluation records the exact transition inputs and its reverse rule returns the exact input cotangent. For $N\ge 2$, midpoint replay produces the exact $x_{a+L}$ by [F3]. By induction the right child returns the exact cotangent at that midpoint, and the left child returns the exact cotangent at $x_a$. Every split partitions its steps into disjoint left and right intervals, processed in reverse order, so every step is recorded and reversed once. In particular the unique recorded evaluation of $F_T$ writes its exact scalar output into $y$; no other leaf changes $y$. Thus the top-level return has the same terminal value and initial cotangent as the ordinary reverse sweep.

At a split, the saved starting state occupies one slot while the right child uses at most $d-1$ further slots and one live primal state. Once that child returns only its cotangent, the saved start is restored into the live state and its slot released; the left tail call has all $d$ slots available. The leaves use no snapshots, so induction bounds the peak snapshot count by $d$. No recursive terminal vectors are retained; only the scalar output register survives the leaf for $F_T$. A step in a right child has at most $t$ replays by induction. A step in the left child is replayed once at the current split and then at most $t-1$ times in that child, hence at most $t$ times total. Each step also has one recorded forward and one reverse call, giving work at most $\widehat{W}+\bar{W}+tW$. Each child decreases $d+t$ by one, so even without eliminating tail frames there are at most $d+t+1$ active frames, each holding only a fixed number of scalar indices and flags. The cotangent buffer is reused, and the one-step tape, local scratch, scalar output and frame records are included in $G$. The saved states and one live primal state use at most $(d+1)R_s$ entries, giving storage at most $G+(d+1)R_s$.