🤖 machine learning

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

This paper introduces a memory-efficient activation checkpointing solver for PyTorch that combines sliding window and Hirschberg's algorithms to reduce peak memory usage from $O(nW)$ to $O(W)$ , enabling the solution of significantly larger 0/1 knapsack problems with a 25-28% runtime speedup and subsequent integration into PyTorch 2.10.

Original authors: Jędrzej Maczan

Published 2026-08-11

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Jędrzej Maczan

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to bake the world's most delicious, complex cake, but you only have a tiny, cramped kitchen. You have a recipe that requires you to keep track of every single ingredient you've mixed, every temperature change, and every whisking motion so you can perfectly reverse the process later to see how the cake turned out. The problem is, your kitchen counter (your computer's memory) is too small to hold all those notes. If you try to write everything down, the counter overflows, and you have to stop baking. This is the daily struggle for scientists training massive artificial intelligence models. They need to remember a lot of steps to teach the AI, but their computers run out of space. To solve this, they use a clever trick called "activation checkpointing." Instead of writing down every single step, they pick the most important ones to save and agree to re-do the less important ones later. It's like deciding which photos to keep in a small photo album and which ones you can afford to take again if you forget them. The goal is to fit the whole cake-baking process into that tiny kitchen without losing the recipe's magic.

For a long time, the computer program PyTorch, which many AI scientists use to build these models, had a specific way of deciding which steps to save. It treated the decision like a classic puzzle called the "0/1 Knapsack Problem." Imagine you are a hiker with a backpack that can only hold a certain weight. You have a list of items, each with a weight and a value (how much it helps you). You want to pick the items that give you the most value without breaking your backpack. PyTorch's default method for solving this was like trying to write down every possible combination of items on a giant sheet of paper. While this method was perfect and found the absolute best answer, the sheet of paper got so huge that the computer's memory would explode, causing the program to crash. The researchers found that if they had just 100 items to choose from, the paper needed was so big it required 304 gigabytes of space, which is way more than the 64 gigabytes available on their machine. It was a perfect solution that simply couldn't fit in the room.

In this paper, the author introduces a new, smarter way to solve this puzzle, which they call dp_knapsack_sliding_hirschberg. Instead of trying to write down the entire giant sheet of paper at once, they use a "sliding window" trick. Imagine you are reading a long book, but you only have a small magnifying glass that can show you two pages at a time. You slide the glass down the book, looking at two pages, then the next two, and so on. This way, you only need to hold two pages in your mind at any moment, saving a massive amount of mental space. However, just looking at two pages isn't enough to remember the whole story; you need to know which specific items to pick. To fix this, they combine the sliding window with an old, clever strategy called "Hirschberg's algorithm." Think of this as a "divide and conquer" game. Instead of trying to solve the whole backpack problem at once, they split the list of items in half. They solve the left half, then the right half, and then figure out how to combine the two best solutions. They do this recursively, breaking the problem down into smaller and smaller pieces until they can solve it easily, all while only using a tiny amount of memory.

The results of this new method are impressive. The author tested it on a computer with 64 gigabytes of RAM. While the old method crashed when trying to solve a problem with just 100 items, the new method successfully solved a problem with 2,000 items, using a peak of 58.4 gigabytes of memory. This means the computer can now handle a problem that is 20 times larger than before without running out of space. Furthermore, the new method isn't just a memory saver; it's also faster. In their tests, it ran 25% to 28% faster than the old method. The author measured this by running the same puzzle 1,000 times on a specific machine and found that the new solver consistently beat the old one in speed. Crucially, unlike some other "quick fix" methods that guess the answer and might be slightly wrong, this new method still finds the exact, perfect solution every time. It is as accurate as the old method but much more efficient.

The paper confirms that this new approach is not just a theory; it has been successfully merged into the PyTorch software and is available in version 2.10. The author shows that by using this combination of sliding windows and divide-and-conquer, they can solve the memory bottleneck that was stopping AI models from growing larger. They don't claim this is the only way to solve the problem, nor do they suggest it works for every single type of computer puzzle, but for the specific task of deciding which AI steps to save, it is a proven, exact, and highly efficient upgrade. The paper rules out the idea that the old method is sufficient for large models, showing clearly that it fails when the number of items gets too high. Instead, they offer a solution that keeps the perfect accuracy of the old way while removing the memory crash, allowing scientists to bake bigger, more complex AI cakes in their tiny kitchens.

Technical Summary: Memory-Efficient Activation Checkpointing with Sliding Window and Hirschberg's Algorithm

Problem Statement
Activation checkpointing is a critical technique for minimizing the runtime of neural networks under strict memory budgets by selectively storing intermediate tensors and recomputing others. In PyTorch, the torch.compile framework models the decision of which operations to save versus recompute as a 0/1 knapsack problem. The default solver, dp_knapsack, employs standard dynamic programming (DP) requiring a full 2D table of shape $(n + 1) \times (W + 1)$ , where $n$ is the number of operations and $W$ is the quantized memory budget.

The author identifies a critical scalability bottleneck: the default solver's memory complexity is $O(nW)$. Empirical testing demonstrates that this approach becomes infeasible for modern deep learning graphs; specifically, the solver triggers an out-of-memory (OOM) crash on a 64 GB machine when $n$ reaches just 100 items. This limitation prevents the optimization of large-scale models with long sequence lengths or wide computation graphs.

Methodology
To address the memory bottleneck while preserving the exact optimal solution, the paper introduces dp_knapsack_sliding_hirschberg. This solver integrates two algorithmic optimizations:

Sliding Window Trick: Instead of maintaining the full DP table, the method stores only two rows at a time. This reduces the space complexity for computing the optimal value from $O(nW)$ to $O(W)$ .
Hirschberg's Algorithm: Since the sliding window optimization discards the intermediate rows needed for backtracking (item selection), the author incorporates Hirschberg's divide-and-conquer strategy. The algorithm recursively splits the item set into halves, computes the DP profiles for each half using the sliding window, and determines the optimal capacity split ( $k^*$ ) that maximizes the total value. It then recurses on the subproblems to recover the exact set of items to save.

To prevent stack overflow during recursion for large $n$ , the implementation utilizes an explicit LIFO stack rather than recursive function calls. The algorithm operates with a space complexity of $O(W + n)$ and a time complexity of $O(nW \log n)$ .

Key Contributions

Algorithmic Integration: The successful combination of the sliding window technique and Hirschberg's algorithm into a production-ready knapsack solver for PyTorch.
Implementation: The solver has been merged into the PyTorch codebase and released in version 2.10.
Empirical Validation: A comprehensive benchmark comparing the new solver against the default dp_knapsack, an ILP-based solver (ilp_knapsack), and a greedy heuristic (greedy_knapsack).

Results
The evaluation was conducted on synthetic instances mirroring real activation memory planning scenarios, using a machine with 64 GB RAM and an AMD Ryzen 7 9800X3D processor.

Memory Efficiency: The new solver runs at $n = 2,000$ with a peak memory usage of 58.4 GB. In contrast, the default solver fails at $n = 100$ . This represents a 20× increase in the computable problem size. At $n=100$ , the memory footprint of the DP table was reduced from approximately 304 GB (default) to ~6 GB (new solver).
Runtime Performance: Despite the theoretical time complexity increase ( $O(nW \log n)$ vs. $O(nW)$), the new solver demonstrated a consistent 25–28% runtime speedup over the default dp_knapsack. The author attributes this to optimized memory access patterns and the use of fixed-size buffers.
Optimality: Like the default solver, dp_knapsack_sliding_hirschberg produces the exact, optimal solution. This distinguishes it from greedy_knapsack, which was found to be up to 7.4% suboptimal.

Significance and Claims
The paper claims that dp_knapsack_sliding_hirschberg resolves the memory bottleneck inherent in PyTorch's default activation checkpointing solver without sacrificing solution optimality. By enabling the optimization of significantly larger computation graphs (up to 20× larger in terms of operation count) and providing a runtime speedup, the method is presented as a substantial improvement to the PyTorch ecosystem.

The author recommends the new solver as the default choice for large or memory-constrained graphs where exact solutions are required and SciPy (needed for ilp_knapsack) is unavailable. The work is positioned as a practical application of standard textbook techniques (sliding window) and classic algorithms (Hirschberg) to solve a specific, high-impact engineering challenge in modern deep learning compilers.

Technical Summary: Memory-Efficient Activation Checkpointing with Sliding Window and Hirschberg's Algorithm

More like this