0/1 Knapsack Problem in PyTorch

This describes a new PyTorch activation-memory-budget solver that formulates which tensor activations to store versus recompute as a 0/1 knapsack problem: each operation is an item with a memory cost and a runtime-saving value, and the planner must maximize saved runtime within a RAM capacity. The existing dp_knapsack implementation builds a full 2D DP table and then backtracks to choose items, which is correct but allocates O(n * capacity) memory and can fail on realistic models. The piece explains the standard DP table construction and the backtracking step that identifies chosen items.

The new dp_knapsack_sliding_hirschberg combines a sliding-window DP (keeping only two rows) with a Hirschberg-style divide-and-conquer that removes the need for explicit backtracking by recursively splitting the item range using intermediate DP row sums. That reduces peak DP storage from shape (n, capacity) to (2, capacity), yielding about a 20× reduction in peak RAM (author reports solving ~2000 items where the old solver crashed at ~100 on a 64 GB machine) and an informal ~37% runtime speedup. For alternatives, greedy_knapsack favors speed over optimality and ilp_knapsack (SciPy) is much faster and exact. To enable the new solver: set torch._functorch.config.activation_memory_budget_solver to fconfig.dp_knapsack_sliding_hirschberg.