When More Memory Fails: Hidden Feasibility Holes in Dynamic Tensor Rematerialization

Dynamic Tensor Rematerialization (DTR) trains neural networks under a memory budget by evicting tensors and recomputing them on demand. A natural expectation is that a budget large enough to complete training stays sufficient when it is increased. Using DTR's reference simulator, simrd, to replay the public DTR training traces, we show that this expectation fails. We call the exceptions feasibility holes: memory budgets at which an eviction policy runs out of memory although both a smaller and a larger budget complete, a form of non-monotone feasibility. Under a written sweep protocol with dated amendments, a 0.01-step budget grid shows no such hole for DTR on any of six confirmatory traces, although unresolved timeouts prevent it from establishing monotonicity. Finer sampling finds holes on InceptionV4 (three regions) and U-Net (two regions), in addition to one on the ResNet-32 development trace. Every hole is reproduced by three repeats and by unmodified simrd. For one InceptionV4 pair (0.2343 versus 0.235 of peak memory) we trace the failure to individual allocations. The larger budget avoids one eviction at an operator where the smaller budget was 173,479 bytes short. The extra data it carries forward forces a later eviction of a tensor needed three operators afterwards, and rebuilding that tensor triggers a recomputation cascade that cannot fit. Keeping that one tensor resident under the same budget prevents the failure. The two simple score changes we tested do not remove holes across traces; both add failing budgets on some traces. All results are from simulation, with no allocator model; behaviour on GPU hardware is untested.