# A Graph Theoretic Framework of Recomputation Algorithms for Memory-Efficient Backpropagation

arXiv: https://arxiv.org/abs/1905.11722 · HTML: https://mlsanity.com/paper/1905.11722/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 28 May 2019.

## Built on by (most cited first, 11 of 11)

- [FlashFFTConv: Efficient Convolutions for Long Sequences with Tensor Cores](https://mlsanity.com/paper/2311.05908/) (2023)
- [On-device Training: A First Overview on Existing Systems](https://mlsanity.com/paper/2212.00824/) (2022)
- [End-to-End Training Induces Information Bottleneck through Layer-Role Differentiation: A Comparative Analysis with Layer-wise Training](https://mlsanity.com/paper/2402.09050/) (2024)
- [Survey on Large Scale Neural Network Training](https://mlsanity.com/paper/2202.10435/) (2022)
- [Rockmate: an Efficient, Fast, Automatic and Generic Tool for Re-materialization in PyTorch](https://mlsanity.com/paper/2307.01236/) (2023)
- [FedDCT: Federated Learning of Large Convolutional Neural Networks on Resource Constrained Devices using Divide and Collaborative Training](https://mlsanity.com/paper/2211.10948/) (2022)
- [XEngine: Optimal Tensor Rematerialization for Neural Networks in Heterogeneous Environments](https://mlsanity.com/paper/2212.09290/) (2022)
- [Front Contribution instead of Back Propagation](https://mlsanity.com/paper/2106.05569/) (2021)
- [Moccasin: Efficient Tensor Rematerialization for Neural Networks](https://mlsanity.com/paper/2304.14463/) (2023)
- [FetusMapV2: Enhanced Fetal Pose Estimation in 3D Ultrasound](https://mlsanity.com/paper/2310.19293/) (2023)
- [Memory-Efficient Activation Checkpointing with Sliding Window and Hirschberg's Algorithm for 0/1 Knapsack Solving in PyTorch](https://mlsanity.com/paper/2608.08740/) (2026)

## Abstract (arXiv)

Recomputation algorithms collectively refer to a family of methods that aims to reduce the memory consumption of the backpropagation by selectively discarding the intermediate results of the forward propagation and recomputing the discarded results as needed. In this paper, we will propose a novel and efficient recomputation method that can be applied to a wider range of neural nets than previous methods. We use the language of graph theory to formalize the general recomputation problem of minimizing the computational overhead under a fixed memory budget constraint, and provide a dynamic programming solution to the problem. Our method can reduce the peak memory consumption on various benchmark networks by 36%~81%, which outperforms the reduction achieved by other methods.