Deterministic Regime Switching and Feasibility Inversion in Dynamic Tensor Rematerialization

Mahesh Reddy Pagadala authored the paper Deterministic Regime Switching and Feasibility Inversion in Dynamic Tensor Rematerialization (arXiv:2609.31250), submitted on September 25, 2026. The study identifies fine-grained, deterministic instability in Dynamic Tensor Rematerialization (DTR), an online eviction policy for memory-constrained deep neural network (DNN) training.

Key findings include: Regime Switching: On LSTM traces, memory budgets differing by only 0.10% of peak memory can select between fast and slow execution regimes with overhead differences up to 7.3x, driven by repeated re-eviction of the same storages. Feasibility Inversion: On ResNet-32 traces, the system exhibits non-monotonic feasibility, being feasible at 0.101, infeasible (Out of Memory) across 0.102–0.106, and feasible again from 0.107. This is caused by a fully pinned recursive rematerialization frontier exceeding the budget. * Root Causes: The instability is linked to the joint size-staleness scoring term in the eviction heuristic, representing distinct budget-sensitive pathologies rather than a single mechanism.

This material reports an empirical study of Dynamic Tensor Rematerialization (DTR), an online eviction/rematerialization policy used to keep deep neural network training within tight memory budgets. Using the reference DTR simulator (simrd) and public execution traces, the authors show that DTR can exhibit fine-grained, deterministic instability: on an LSTM trace, memory budgets that differ by only about 0.10% of unconstrained peak memory can select qualitatively different execution regimes, including fast versus slow behavior. The central insight is that DTR’s behavior is not smoothly monotonic in available memory; small budget perturbations can change eviction and rematerialization decisions in ways that cascade into large differences in runtime or feasibility.

A related phenomenon, feasibility inversion, suggests that the usual assumption “more memory is always better” may fail for this policy. Because DTR makes online decisions based on the current memory state, a slightly larger budget can alter the sequence of evictions and recomputations enough to make a workload less performant—or even infeasible—compared with a nearby smaller budget. This is especially concerning because the effect is described as deterministic rather than stochastic, implying that the instability is structural to the policy and trace interaction rather than measurement noise.

The work matters because memory-constrained DNN training increasingly relies on automated memory management, autotuning, and reproducible benchmarking. If a well-behaved-looking policy can produce discontinuous regime switches under tiny resource changes, then systems that tune memory budgets, schedule workloads, or compare configurations need to account for local sensitivity, non-monotonicity, and path dependence. The results provide a concrete cautionary case for compiler and runtime designers: robust memory policies may require sensitivity-aware search, hysteresis or smoothing mechanisms, and more careful validation across nearby resource settings rather than relying on coarse-grained budget sweeps.