Deterministic Regime Switching and Feasibility Inversion in Dynamic Tensor Rematerialization

1 Introduction

• DTR already has reported deep recursive rematerialization and prototype OOMs or hangs, so this paper’s contribution is their fine-grained deterministic budget characterization, not their first observation.The paper also provides an allocation-level mechanism for one behavior and an ablation localizing another.Source: §1 · p. 1
• The authors report a combination of deterministic fine-grained regime switching, non-monotone feasibility, an allocation-level OOM mechanism, broad re-eviction, and ablation evidence implicating the joint size-staleness term.The novelty claim is qualified by the stated search scope across DTR, Checkmate, Coop, MegTaiChi, T-Control, and their immediate citations.Source: §1 · p. 1
• Budgets separated by 0.001 select LSTM overheads of ~1.38× versus ~8.78-10.10×, while a ResNet-32 run switches from feasible to OOM and back as budget increases.The LSTM slow regime re-evicts broadly across the working set; the ResNet OOM occurs when a fully pinned recursive frontier exceeds the budget after evictable storage is exhausted.Source: §1 · p. 1

2 Background

• DTR evicts the resident tensor with the lowest compute/(size × staleness) score when memory is exhausted.The tested variants remove staleness, size, or both from the score.Source: §2 · p. 2
• simrd replays pre-recorded execution traces, capturing tensor operations, sizes, and compute costs without a GPU.The evaluated runtime is RuntimeV2EagerOptimized, which supports DTR’s region-aware features.Source: §2 · p. 2
• Overhead is (model compute + recomputation) / model compute, with 1.0 indicating no recomputation; budget ratio divides the memory cap by unconstrained peak memory.A run that exhausts memory raises MemoryError and is reported as OOM, distinct from exceeding a recomputation ceiling.Source: §2 · p. 2

3.1 Experimental setup and reproducibility

• The simulator replays public artefact traces in fresh runtimes, and the ResNet OOM band was also reproduced in independent OS processes.The package includes scripts, instrumentation, exact commands, and raw per-point results; results were reproduced on Python 3.11 and 3.13.Source: §3.1 · p. 2

3.2 Models and baselines

• LSTM is recurrent with a 5,595 MB unconstrained peak, whereas ResNet-32 is feedforward with residual connections and a 10,061 MB peak.Their single-op bottlenecks are 69.4 MB (1.2% of peak) for LSTM and 539.5 MB (5.4% of peak) for ResNet-32.Source: §3.2 · p. 2

3.3 LSTM: deterministic overhead regime switching

• Three repeats at each reported LSTM budget were identical to four decimal places, with no observed variation.The evaluated configuration was deterministic for the tested traces and settings.Source: §3.3 · p. 2
• Table 1 reports selected LSTM overhead points from a 0.001-step sweep, with identical repeats and adjacent-budget transitions including 0.266→0.265 and 0.265→0.264.The 0.266→0.265 step is 0.10% of unconstrained peak memory.Source: Table 1 · p. 2, §3.3 · p. 2

3.4 LSTM slow-regime mechanism: broad working-set re-eviction

• At adjacent LSTM budgets 0.265 and 0.264, distinct evicted-storage counts remain 5,233 vs 5,236, while total evictions rise 6.2×.The fast-regime set is fully contained in the slow-regime set (Jaccard 0.999), indicating repeated re-eviction rather than expansion to new storages.Source: §3.4 · p. 3, Table 2 · p. 3
• The most re-evicted storage rises from 5 to 24 evictions, while the top 10 storages account for under 1% in both regimes.Collateral rematerialization is 0.0% in both regimes, providing no evidence of deep rebuild chains in this LSTM case.Source: §3.4 · p. 3

3.5 Ablations: the joint size-staleness term

• Across the same five LSTM budgets, only full DTR alternates; all three ablations remain within a narrow overhead band.Removing either size or staleness eliminates switching in this tested window, implicating their joint presence without establishing the score-level causal path.Source: §3.5 · p. 3, Table 3 · p. 3

3.6 ResNet-32: deterministic feasibility inversion

• Overhead rises from 2.077× at 0.107 to 3.212× at 0.111 and 3.330× at 0.116, then falls back as budget increases.The sweep shows non-monotone, piecewise-constant overhead.Source: §3.6 · p. 3, Figure 1 · p. 4
• ResNet-32 is feasible at ratios 0.100–0.101, OOM across 0.102–0.106, and feasible again from 0.107.The complete sweep covers contiguous bands, with all points deterministic over three repeats.Source: §3.6 · pp. 3–4, Table 4 · p. 4

3.7 ResNet-32 OOM mechanism: a fully pinned recursive frontier

• At ratio 0.104, the pinned frontier plus a pending 179.8 MB allocation exceeds the budget after the evictable pool is empty.The failure occurs while materialising x7977: 889.8 MB is pinned and the request raises total memory to 1069.6 MB, 23.2 MB above the 1046.4 MB budget.Source: §3.7 · p. 4, Figure 2 · p. 5
• For the same tensor x7977, ratio 0.104 reaches depth 118 with 889.8 MB pinned and OOMs, while 0.107 reaches depth 30 with 575.1 MB pinned and completes.Run-level maximum frontier depth is non-monotone (8, 118, 30), but the 0.101 maximum occurs at a different tensor.Source: §3.7 · p. 4, Table 5 · p. 5

• The LSTM slow regime is broad working-set re-eviction, whereas the ResNet OOM is a deep, fully pinned recursive frontier.Source: §3.8 · p. 5
• Budget-dependent victim selection may be an upstream cause shared by both pathologies, but this remains un demonstrated.Source: §3.8 · p. 5
• LSTM RecursionError at very low budgets is a plausible third manifestation of frontier depth, but stack exhaustion is partly an implementation property.The paper treats this observation as suggestive only.Source: §3.8 · p. 5

• DTR [6] already reports deep recursive rematerialization and prototype OOMs and hangs, so thrashing and OOM themselves are known.Source: §4 · p. 5
• The reported addition is fine-grained deterministic structure between coarse grid points: overhead regime switching, feasibility inversion, an allocation-level frontier mechanism, and ablation localisation.Source: §4 · p. 5
• T-Control targets eviction of structurally important tensors and uses coarser budget increments; Coop [9] and MegTaiChi address fragmentation and allocation.T-Control's score also retains size and staleness.Source: §4 · p. 5
• Belady's anomaly is presented as a structural analogy for non-monotone behaviour under a non-stack policy, not as an equivalent phenomenon.The paper notes that the objects differ: recomputation and lock lifetimes versus paging.Source: §4 · p. 5
• A systematic review is required before making a literature-wide novelty claim.Source: §4 · p. 5

Evaluation grids

• Fine budget sweeps near high-pressure regions are needed because coarse grids can miss narrow transitions and make comparisons depend on sampled points.The resolution should be reported.Source: §5 · p. 6

Feasibility-boundary search

• Bisection cannot reliably identify the global minimum feasible budget in the observed non-monotone ResNet interval; linear scans are a safe local-boundary default.The authors make no universal claim about all rematerialization systems.Source: §5 · p. 6

Heuristic design

• Separating memory-release criteria from recomputation-risk ranking is a candidate heuristic direction, not a validated result.The LSTM ablation implicates the joint size-staleness term, while ResNet shows that dropping size can harm reclamation under tight pressure.Source: §5 · p. 6

Demonstrated

• Demonstrated findings on the tested simulator and traces include deterministic LSTM overhead switching, ResNet-32 feasibility inversion, the pinned-frontier OOM mechanism, broad LSTM re-eviction, and identical repeats.The OOM occurs when the pinned frontier exceeds budget with the evictable pool empty.Source: §6 · p. 6

Supported but incomplete

• Earlier victim history is supported as a source of divergent ResNet frontiers only at the allocation and frontier level, not through individual score comparisons.The mechanism tracing is therefore incomplete.Source: §6 · p. 6

Hypothesised

• A shared upstream size-staleness or victim-order mechanism for the LSTM and ResNet pathologies remains hypothesized.A decoupled policy removing instability without harming feasibility is also hypothesized.Source: §6 · p. 6

Unknown

• Whether these findings reproduce in production PyTorch/GPU DTR with real allocators and asynchronous execution is unknown and the primary open risk.The authors identify this as the priority for follow-up.Source: §6 · p. 6

7 Conclusion

• On the reference DTR simulator, small budget changes deterministically switch LSTM overhead regimes and produce a ResNet-32 feasible→OOM→feasible inversion.LSTM's slow regime involves broad re-eviction; the ResNet OOM occurs when a fully pinned recursive rematerialization frontier exceeds the budget after evictable storage is exhausted.Source: §7 · p. 6