Pith. sign in

REVIEW 3 major objections 4 minor 36 references

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

T0 review · 3 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read The paper presents a knapsack solver for activation checkpointing that reduces peak memory from O(nW) to O(W) while preserving the exact optimal solution, enabling 20x larger problems and a 25-28% runtime speedup.

desk verdict Known algorithm, real shipped implementation; memory win is solid, exactness spec needs one sentence. read the letter →

arxiv 2608.08740 v1 pith:GG7KTTDJ submitted 2026-08-09 cs.LG

Jędrzej Maczan This is my paper · ORCID
classification cs.LG
keywords activationcheckpointing0/1knapsackdynamicprogrammingHirschberg'salgorithmslidingwindowmemoryefficiencyPyTorch
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper presents dp_knapsack_sliding_hirschberg, a new solver for the 0/1 knapsack problem that PyTorch uses to decide which activation tensors to store during training. The solver combines the sliding-window trick, which keeps only two rows of the dynamic-programming table, with Hirschberg's divide-and-conquer algorithm, which recovers the exact item selection from those rows. This reduces peak memory from O(nW) to O(W) while preserving the optimal solution, allowing PyTorch to plan memory for 20x larger computation graphs (n=2000 instead of n=100) on a 64 GB machine. Benchmarks also show a consistent 25-28% runtime speedup over PyTorch's default dp_knapsack. The implementation is merged into PyTorch 2.10.

What carries the argument

The central object is a combined algorithm: a sliding-window dynamic program that computes a value profile (best total value for every capacity up to c) for a range of items while holding only two rows of the DP table, and Hirschberg's divide-and-conquer that splits the item range in half, computes forward and backward profiles L and R, picks the split k* = argmax_k (L[k] + R[c-k]), and recurses on the two subproblems (left with capacity k*, right with c-k*). An explicit LIFO stack replaces the call stack to avoid overflow for large n. The sliding window supplies the O(W) memory bound; Hirschberg's method supplies the exact reconstruction at a log-factor time cost.

What would settle it

Run the solver on small random knapsack instances (n up to 50) with a known optimal value from a full-table DP; any discrepancy between the two outputs would falsify the exactness claim. More targeted: include an instance where the optimal selection uses strictly less than the full capacity, and check whether the solver's split formula still recovers it; or inspect the DP row initialization to see whether it uses zeros (at-most semantics) or -infinity (exact semantics).

Watch

Extended reading notes

Core claim

The central claim is that the knapsack problem inside activation memory planning can be solved exactly in O(W) space by combining two standard techniques: a sliding window over the DP rows for computing optimal values, and Hirschberg's divide-and-conquer for reconstructing the chosen items. The paper's key formula is the split c* = argmax_k (P1[k] + P2[c-k]) between the left and right halves' value profiles, which lets the solver recurse on smaller subproblems without ever storing the full DP table. The paper demonstrates that this solver handles n=2,000 operations with 58.4 GB peak memory, whereas the default solver crashes at n=100 with a 304 GB table, and that it matches the optimal solution exactly while greedy heuristics deviate by up to 7.4%. In short, the paper claims that exactness and memory efficiency are not in conflict here: the bottleneck was the solver's table, not the problem.

Load-bearing premise

The algorithm's correctness depends on the sliding-window DP returning best values for 'at most capacity' rather than 'exactly capacity'; if it returns exact-capacity values, the split formula can miss optimal solutions with unused capacity, and the paper never states which it uses.

Editorial extensions

If this is right

  • PyTorch can now run activation checkpointing for much larger graphs: up to n=2,000 operations on a 64 GB machine, a 20x increase over the n=100 limit of the default solver.
  • The O(W) memory bound means that as computation graphs grow, the solver's memory use scales with the budget, not with the number of operations, making memory planning feasible for long-sequence and wide-model training.
  • For typical activation-planning sizes, the solver is 25-28% faster than the default dp_knapsack despite its higher asymptotic time complexity, because it uses fixed buffers and cache-friendly memory access.
  • The solver remains exact: it produces the same optimal selection as a full DP table, unlike greedy heuristics that can be up to 7.4% suboptimal.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The same sliding-window plus Hirschberg pattern could be applied to other DP problems in compilers and runtimes (e.g., optimal segmentation or sequence alignment) where only the final optimal value profile is needed, potentially yielding similar memory savings.
  • The 25-28% speedup is instance- and hardware-specific; on very large W or different memory hierarchies, the O(nW log n) asymptotic overhead might overtake the constant-factor gains, so performance claims should be re-tested before generalizing.
  • The 'at-most capacity' versus 'exact capacity' semantics is a subtle correctness trap; future implementations or forks should pin down and test this semantic explicitly to guarantee exactness.
  • A further memory reduction to sublinear space is theoretically possible (e.g., using more advanced divide-and-conquer or bit-parallel methods), but O(W) is likely sufficient for practical activation budgets.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 4 minor

Summary. The paper proposes dp_knapsack_sliding_hirschberg, a memory-efficient exact solver for the 0/1 knapsack problem underlying PyTorch's activation checkpointing planner. It combines a sliding-window DP (two-row buffers) with Hirschberg's divide-and-conquer recursion to recover the optimal item selection using O(W) memory instead of the O(nW) table of the existing dp_knapsack. The authors report successful execution at n=2000 where the baseline OOMs at n=100, claim a 25–28% runtime speedup over dp_knapsack, and state the implementation is merged into PyTorch 2.10.

Significance. If the correctness and performance claims hold, the contribution is practically valuable: activation checkpointing at compile time currently hits a memory wall for large graphs, and replacing an O(nW)-space DP with an O(W)-space exact solver directly extends the feasible problem size. The algorithmic ingredients are standard and the paper contains no fitted parameters or circular derivations; the use of external baselines (dp_knapsack, ilp_knapsack, greedy_knapsack) is appropriate. The claimed PyTorch merge, if accurate, is a strong external validation. However, the paper's central exactness claim rests on an unspecified profile semantics, and the asymptotic time analysis is incorrect, so the write-up needs substantial revision before the claims are established.

major comments (3)
  1. [§3, Algorithm 1 (lines 8–9)] The split formula c* = argmax_k (P1[k] + P2[c−k]) is valid only if SLIDINGWINDOWDP returns at-most-capacity profiles, i.e., P[s] is the best value using total weight at most s. The manuscript never defines this semantics, and the base-case comments do not disambiguate it. Under exact-capacity semantics the formula misses optimal solutions with unused capacity. A minimal counterexample is a left half with one item (w=1, v=10), a right half with one item (w=2, v=10), and capacity c=10: the optimum value 20 uses total weight 3, but exact-capacity profiles give P1[k] finite only for k∈{0,1} and P2[j] finite only for j∈{0,2}, so no split yields P1[k]+P2[10−k]=20. Please specify the profile semantics explicitly in pseudocode and give a proof that the combined profile equals the optimum under that semantics.
  2. [§3 (Space/Time) and §5] The stated time complexity O(nW log n) is not supported by Algorithm 1. At recursion level l there are 2^l subproblems, each with about n/2^l items, and the capacities of the subproblems at that level sum to W because each split partitions the parent capacity. Each node performs two sliding-window passes costing O((n/2^l) · c_node), so the total work at level l is O((n/2^l) W), and summing over log n levels gives O(nW), not O(nW log n). The claim in §5 that the new solver has worse asymptotic time than dp_knapsack (O(nW log n) vs. O(nW)) should be corrected; the recurrence gives the same asymptotic time up to a constant factor.
  3. [§4, Table 1 and Figure 2] The claimed 'consistent 25–28% runtime speedup' is not fully supported by the reported numbers: the speedup is about 21% at n=10, and at n=100 the baseline dp_knapsack OOMs, so no comparison is possible there. The statement that the three exact solvers 'produce the exact, optimal solution at every size' is likewise only verified for n≤50, where dp_knapsack and ilp_knapsack are available as references; no exactness check is reported for n=100 or for the n=2000 memory experiment. Please qualify the speedup claim and describe how exactness was verified at each size.
minor comments (4)
  1. [§4, paragraph after Table 1] The sentence 'as a rule of thumb we recommend ilp_knapsack when SciPy is available, ilp_knapsack when exact solutions don't matter' presumably should refer to greedy_knapsack in the second clause; otherwise the recommendation is contradictory.
  2. [§4, memory accounting] The text says the DP table shrinks from ~304 GB to ~6 GB at n=100, but §3 states that four row buffers of size W+1 are used; with W≈3.8×10^8 and 8-byte entries, four buffers alone would be ~12.2 GB. Please clarify whether the buffers are two or four, what numeric type is used, and how the 58.4 GB peak at n=2000 is obtained.
  3. [Algorithm 1, line 9] The comment 'P2 accessed in reverse' is misleading: the code indexes P2 normally as P2[c−k] rather than iterating the array backwards. Removing or rephrasing the comment would avoid confusion.
  4. [§2, references] The reference 'Bellman et al., 1957' appears to attribute Dynamic Programming to multiple authors; the standard citation is Bellman (1957).

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the solver's exactness and memory gains are supported by standard published algorithms and by comparisons against independent exact baselines.

full rationale

The paper's derivation chain is self-contained: Algorithm 1 combines the sliding-window DP and Hirschberg's divide-and-conquer algorithm, both attributed to external standard references (Cormen et al. 2022; Hirschberg 1975), and the claimed O(W) peak memory follows directly from the two-row buffer construction plus a stack of O(log n) frames. The central claims are validated empirically against dp_knapsack and ilp_knapsack, which are independent exact solvers, rather than against quantities fitted from the method's own outputs. The citation to the PyTorch 2.10 release notes concerns shipping status, not a load-bearing algorithmic premise, and does not substitute for the external benchmark evidence. The reviewer-noted ambiguity about whether SLIDINGWINDOWDP returns at-most-capacity or exact-capacity profiles is a specification/proof gap: the paper's stated recurrence T[i][c] = max(T[i-1][c], T[i-1][c-w_i] + v_i) is the standard at-most-capacity form, and the concern is about an unspecified implementation detail, not about a conclusion being equivalent to its input by construction. No fitted parameter is renamed as a prediction, and no self-citation chain forces the stated result, so the appropriate finding is no significant circularity.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The central claim rests on standard knapsack DP correctness, Hirschberg's divide-and-conquer lemma, and the knapsack formulation of activation checkpointing. No free parameters are fitted; the benchmark inputs are synthetic and under-specified but are not fitted to a target result. No new entities are introduced.

assumptions (3)
  • standard math The 0/1 knapsack DP recurrence T[i][c] = max(T[i-1][c], T[i-1][c-w_i]+v_i) correctly computes optimal values.
    Invoked for the SLIDINGWINDOWDP subroutine in Algorithm 1; standard textbook result, not proved.
  • standard math Hirschberg's split formula c* = argmax_k(P1[k]+P2[c-k]) recovers the optimal solution when P1 and P2 are 'at most capacity' DP rows.
    Known from Hirschberg (1975) and competitive programming adaptation (Ciobanu 2016); the paper relies on it without proof and does not specify the profile semantic.
  • domain assumption Activation checkpointing decisions in torch.compile can be modeled as a 0/1 knapsack.
    Assumed from prior PyTorch work (PyTorch Team 2025); the paper does not re-derive this.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Memory-Efficient Activation Checkpointing with Sliding Window and Hirschberg's Algorithm for 0/1 Knapsack Solving in PyTorch." pith.science (2026). https://pith.science/paper/GG7KTTDJ

@misc{pith2026260808740,
  author       = {Pith},
  title        = {Pith review of: Memory-Efficient Activation Checkpointing with Sliding Window and Hirschberg's Algorithm for 0/1 Knapsack Solving in PyTorch},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/GG7KTTDJ}},
  note         = {Machine review of arXiv:2608.08740}
}
abstract

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, dp_knapsack, allocates a full dynamic programming (DP) table of shape $(n+1) \times (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 dp_knapsack_sliding_hirschberg, 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 dp_knapsack fails at $n = 100$, a 20$\times$ increase in computable problem size. In addition, our benchmarks show a consistent 25-28\% runtime speedup over dp_knapsack. The implementation is merged into PyTorch and released in version 2.10.

Figures

Figures reproduced from arXiv: 2608.08740 by the authors.

Figure 1
Figure 1. DP Hirschberg with sliding-window. The item set is split in the mid [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗
Figure 2
Figure 2. Left: mean solver runtime versus n. Right: greedy_knapsack leaves an instance-dependent optimality gap of up to 7.4%, whereas the exact solvers (dp_knapsack, ilp_knapsack, dp_knapsack_sliding_hirschberg) all reach the optimum. 5 Discussion and Related Work dp_knapsack fails when n is large - with long sequence lengths, wide graphs, or full model graph captures in torch.compile (Shoeybi et al., 2019; Narayanan et al.… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

36 extracted references · 18 canonical work pages

  1. [1]

    PyTorch 2.10.0 Release Notes , howpublished =

    work page

  2. [2]

    2016 , eprint=

    Training Deep Nets with Sublinear Memory Cost , author=. 2016 , eprint=

    2016

  3. [3]

    Hirschberg, D. S. , title =. Commun. ACM , month = jun, pages =. 1975 , issue_date =. doi:10.1145/360825.360861 , abstract =

    arXiv 1975

  4. [4]

    Codeforces bciobanu comment suggesting

    Ciobanu, Bogdan , year =. Codeforces bciobanu comment suggesting

    work page

  5. [5]

    CoRR , volume =

    Marisa Kirisame and Steven Lyubomirsky and Altan Haan and Jennifer Brennan and Mike He and Jared Roesch and Tianqi Chen and Zachary Tatlock , title =. CoRR , volume =. 2020 , url =. 2006.09616 , timestamp =

    arXiv 2020

  6. [6]

    Neural Information Processing Systems , year=

    Efficient Combination of Rematerialization and Offloading for Training DNNs , author=. Neural Information Processing Systems , year=

    work page

  7. [7]

    2019 , eprint=

    Optimal checkpointing for heterogeneous chains: how to train deep neural networks with limited memory , author=. 2019 , eprint=

    work page 2019

  8. [8]

    2020 , eprint=

    Checkmate: Breaking the Memory Wall with Optimal Tensor Rematerialization , author=. 2020 , eprint=

    work page 2020

Show all 36 references
  1. [9]

    2004 , publisher =

    Knapsack Problems , author =. 2004 , publisher =

    2004

  2. [10]

    Introduction to algorithms , author=

  3. [11]

    2022 , eprint=

    Speeding Hirschberg Algorithm for Sequence Alignment , author=. 2022 , eprint=

    2022

  4. [12]

    2025 , eprint=

    Universal Hirschberg for Width Bounded Dynamic Programs , author=. 2025 , eprint=

    2025

  5. [13]

    2022 , issue_date =

    Schuler, Manuela and Membarth, Richard and Slusallek, Philipp , title =. 2022 , issue_date =. doi:10.1145/3568956 , journal =

    2022 doi

  6. [14]

    Memory-Efficient Backpropagation Through Time , journal =

    Audrunas Gruslys and R. Memory-Efficient Backpropagation Through Time , journal =. 2016 , url =. 1606.03401 , timestamp =

    2016 arXiv

  7. [15]

    Transcending Runtime-Memory Tradeoffs in Checkpointing by being Fusion Aware , url =

    He, Horace and Yu, Shangdi , booktitle =. Transcending Runtime-Memory Tradeoffs in Checkpointing by being Fusion Aware , url =

  8. [16]

    2025 , howpublished =

    Current and New Activation Checkpointing Techniques in PyTorch , author =. 2025 , howpublished =

    2025

  9. [17]

    A survey on memory-efficient transformer-based model training in AI for science , volume=

    Tian, Kaiyuan and Qiao, Linbo and Liu, Baihui and Jiang, Gongqingjian and Li, Shanshan and Li, Dongsheng , year=. A survey on memory-efficient transformer-based model training in AI for science , volume=. Frontiers of Computer Science , publisher=. doi:10.1007/s11704-025-50302...

    doi

  10. [18]

    2025 , howpublished =

    2025

  11. [19]

    1990 , publisher=

    Knapsack Problems: Algorithms and Computer Implementations , author=. 1990 , publisher=

    1990

  12. [20]

    Optimization Methods and Software , volume =

    Andreas Griewank , title =. Optimization Methods and Software , volume =. 1992 , publisher =

    1992

  13. [21]

    2000 , issue_date =

    Griewank, Andreas and Walther, Andrea , title =. 2000 , issue_date =. doi:10.1145/347837.347846 , journal =

    2000

  14. [22]

    2017 , eprint=

    The Reversible Residual Network: Backpropagation Without Storing Activations , author=. 2017 , eprint=

    2017

  15. [23]

    2020 , eprint=

    Reformer: The Efficient Transformer , author=. 2020 , eprint=

    2020

  16. [24]

    2022 , eprint=

    Reducing Activation Recomputation in Large Transformer Models , author=. 2022 , eprint=

    2022

  17. [25]

    Efficient Rematerialization for Deep Networks , url =

    Kumar, Ravi and Purohit, Manish and Svitkina, Zoya and Vee, Erik and Wang, Joshua , booktitle =. Efficient Rematerialization for Deep Networks , url =

  18. [26]

    2019 , eprint=

    A Graph Theoretic Framework of Recomputation Algorithms for Memory-Efficient Backpropagation , author=. 2019 , eprint=

    2019

  19. [27]

    2022 , eprint=

    FlashAttention: Fast and Memory-Efficient Exact Attention with IO-Awareness , author=. 2022 , eprint=

    2022

  20. [28]

    2020 , eprint=

    ZeRO: Memory Optimizations Toward Training Trillion Parameter Models , author=. 2020 , eprint=

    2020

  21. [29]

    2020 , isbn =

    Rasley, Jeff and Rajbhandari, Samyam and Ruwase, Olatunji and He, Yuxiong , title =. 2020 , isbn =. doi:10.1145/3394486.3406703 , booktitle =

    2020

  22. [30]

    CoRR , volume =

    Jie Ren and Samyam Rajbhandari and Reza Yazdani Aminabadi and Olatunji Ruwase and Shuangyan Yang and Minjia Zhang and Dong Li and Yuxiong He , title =. CoRR , volume =. 2021 , url =. 2101.06840 , timestamp =

    2021 arXiv

  23. [31]

    CoRR , volume =

    Mohammad Shoeybi and Mostofa Patwary and Raul Puri and Patrick LeGresley and Jared Casper and Bryan Catanzaro , title =. CoRR , volume =. 2019 , url =. 1909.08053 , timestamp =

    2019 arXiv

  24. [32]

    CoRR , volume =

    Deepak Narayanan and Mohammad Shoeybi and Jared Casper and Patrick LeGresley and Mostofa Patwary and Vijay Korthikanti and Dmitri Vainbrand and Prethvi Kashinkunti and Julie Bernauer and Bryan Catanzaro and Amar Phanishayee and Matei Zaharia , title =. CoRR , volume =. 2021 , ...

    2021 arXiv

  25. [33]

    PyTorch: An Imperative Style, High-Performance Deep Learning Library , journal =

    Adam Paszke and Sam Gross and Francisco Massa and Adam Lerer and James Bradbury and Gregory Chanan and Trevor Killeen and Zeming Lin and Natalia Gimelshein and Luca Antiga and Alban Desmaison and Andreas K. PyTorch: An Imperative Style, High-Performance Deep Learning Library ,...

    2019 arXiv

  26. [34]

    Reed and Zachary DeVito and Horace He and Ansley Ussery and Jason Ansel , title =

    James K. Reed and Zachary DeVito and Horace He and Ansley Ussery and Jason Ansel , title =. CoRR , volume =. 2021 , url =. 2112.08429 , timestamp =

    2021 arXiv

  27. [35]

    1957 , publisher=

    Dynamic Programming , author=. 1957 , publisher=

    1957

  28. [36]

    A Minimal Algorithm for the 0-1 Knapsack Problem , urldate =

    David Pisinger , journal =. A Minimal Algorithm for the 0-1 Knapsack Problem , urldate =

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.