Late-Query Algebraic Checkpointing and Arbitrary Matrix-Product Outputs

Exact checkpointing has two distinct costs: recomputing discarded information and combining early data with a query unavailable at commit time. We separate them using mixed derivatives of bounded-arity analytic circuits. For a bilinear target, any $M$-scalar checkpoint removes only an output component of dimension at most $M$, leaving a quotient tensor. Its ordinary rank is the exact late multiplication cost in the saturated bilinear model. For matrix multiplication, we evaluate this cost over all $q$-dimensional linear output spaces: ${\mathrm{PMM}}_n^{\star }(q)=n^{\omega (\gamma /2,1,\gamma /2)+o(1)},q=n^{\gamma +o(1)}\ge 1,0\le \gamma \le 2,$ for ordinary, border, and asymptotic rank. A uniform version implies that a fixed saving in the late-work exponent requires storage of at least $n^2-n^{2-\epsilon +o(1)}$ scalars; saving any fixed fraction of full-output storage cannot improve that exponent. An explicit residual ReLU construction makes a readout gradient of unnormalized symmetric InfoNCE recover a matrix product. Beyond its fixed-key storage lower bound, constant-score key perturbations expose an independent early–late matrix product. The full late-key gradient family therefore has optimal late exponent $\omega$, regardless of checkpoint capacity. This separates storage-limited recomputation from genuinely query-dependent arithmetic.