# Memory-Efficient Activation Checkpointing with Sliding Window and Hirschberg's Algorithm for 0/1 Knapsack Solving in PyTorch

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 17 of its 35 references that are in the map.
- First posted on arXiv 9 Aug 2026.

## Builds on (most cited first, 17 of 17)

- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness](https://mlsanity.com/paper/2205.14135/) (2022)
- [Megatron-LM: Training Multi-Billion Parameter Language Models Using Model Parallelism](https://mlsanity.com/paper/1909.08053/) (2019)
- [Reformer: The Efficient Transformer](https://mlsanity.com/paper/2001.04451/) (2020)
- [ZeRO: Memory Optimizations Toward Training Trillion Parameter Models](https://mlsanity.com/paper/1910.02054/) (2019)
- [Training Deep Nets with Sublinear Memory Cost](https://mlsanity.com/paper/1604.06174/) (2016)
- [ZeRO-Offload: Democratizing Billion-Scale Model Training](https://mlsanity.com/paper/2101.06840/) (2021)
- [Reducing Activation Recomputation in Large Transformer Models](https://mlsanity.com/paper/2205.05198/) (2022)
- [The Reversible Residual Network: Backpropagation Without Storing Activations](https://mlsanity.com/paper/1707.04585/) (2017)
- [Checkmate: Breaking the Memory Wall with Optimal Tensor Rematerialization](https://mlsanity.com/paper/1910.02653/) (2019)
- [Memory-Efficient Backpropagation Through Time](https://mlsanity.com/paper/1606.03401/) (2016)
- [Torch.fx: Practical Program Capture and Transformation for Deep Learning in Python](https://mlsanity.com/paper/2112.08429/) (2021)
- [Optimal checkpointing for heterogeneous chains: how to train deep neural networks with limited memory](https://mlsanity.com/paper/1911.13214/) (2019)
- [A Graph Theoretic Framework of Recomputation Algorithms for Memory-Efficient Backpropagation](https://mlsanity.com/paper/1905.11722/) (2019)
- [A Survey on Memory-Efficient Transformer-Based Model Training in AI for Science](https://mlsanity.com/paper/2501.11847/) (2025)
- [XEngine: Optimal Tensor Rematerialization for Neural Networks in Heterogeneous Environments](https://mlsanity.com/paper/2212.09290/) (2022)
- [Speeding Hirschberg Algorithm for Sequence Alignment](https://mlsanity.com/paper/2204.12801/) (2022)

## Abstract (arXiv)

Activation checkpointing minimizes the runtime of neural networks under a given memory budget, by selecting which intermediate tensors to store and which to recompute. PyTorch solves this as a 0/1 knapsack problem, where operations from a joint forward-backward computation graph are items with a memory cost (weight) and a runtime saving (value). The default solver, dpknapsack, allocates a full dynamic programming (DP) table of shape (n+1) × (W+1), where n is the number of operations and W is the quantized memory budget. This method is resource-hungry and crashes at n = 100 items on a machine with 64 GB RAM. In this paper, we introduce dpknapsackslidinghirschberg, which combines the sliding window trick and Hirschberg's algorithm to reduce peak memory from O(nW) to O(W) while preserving the exact optimal solution. Our experiments show successful knapsack execution at n = 2000, where dpknapsack fails at n = 100, a 20× increase in computable problem size. In addition, our benchmarks show a consistent 25-28% runtime speedup over dpknapsack. The implementation is merged into PyTorch and released in version 2.10.