# Moccasin: Efficient Tensor Rematerialization for Neural Networks

**Authors:** Burak Bartan, Haoming Li, Harris Teague, Christopher Lott, Bistra Dilkina  
**arXiv:** [2304.14463](https://arxiv.org/abs/2304.14463)  
**Date:** 2023-04-27  
**Summary page:** https://www.summarizepaper.com/en/paper/2304.14463v1/

## Key points

- Deployment and training of neural networks on edge computing devices present challenges due to low memory nature of these devices
- Tensor rematerialization or recompute is used to address high memory requirements for neural network training and inference
- MOCCASIN is a new constraint programming formulation that minimizes execution time of compute graphs subject to a memory budget
- MOCCASIN has only O(n) integer variables, which is a significant improvement over recent literature that proposes formulations with O(n^2) Boolean variables
- Retention interval formulation for rematerialization simplifies problem formulation greatly by defining output retention intervals for each node in the computation graph
- Parameter Cv defines the maximum number of times a node v can be computed in the final sequence, and this simple complexity reduction retains solution quality even for very small values of Cv
- MOCCASIN is up to an order of magnitude faster than recent work, especially for large-scale graphs
- Empirical results demonstrate MOCCASIN's effectiveness compared to other recent works while highlighting its scalability to larger graphs.

## Summary

The deployment and training of neural networks on edge computing devices present various challenges, with the low memory nature of these devices being one of the most significant limiting factors. To address high memory requirements for neural network training and inference, tensor rematerialization or recompute is often used. In this paper titled "MOCCASIN: Efficient Tensor Rematerialization for Neural Networks," the authors consider the problem of execution time minimization of compute graphs subject to a memory budget. The authors introduce MOCCASIN, a new constraint programming formulation that addresses the high memory requirements for neural network training and inference. MOCCASIN has only O(n) integer variables, where n is the number of nodes in the compute graph, which is a significant improvement over recent literature that proposes formulations with O(n^2) Boolean variables. The authors demonstrate through numerical studies that their approach is up to an order of magnitude faster than recent work, especially for large-scale graphs. One key contribution of this paper is introducing retention interval formulation for rematerialization. This concept simplifies problem formulation greatly by defining output retention intervals for each node in the computation graph. Additionally, they introduce parameter Cv that defines the maximum number of times a node v can be computed in the final sequence. They demonstrate empirically that this simple complexity reduction retains solution quality even for very small values of Cv. The authors also provide a comparison between their solution speed and CHECKMATE's solution speed while demonstrating equivalence between solutions. Furthermore, they show how different local memory limits impact solution speed and final solution value. Overall, MOCCASIN provides an efficient way to address high memory requirements when deploying large neural network models on edge computing devices. The retention interval formulation introduced in this paper simplifies problem formulation significantly while retaining solution quality even with reduced complexity. The empirical results presented in this paper demonstrate MOCCASIN's effectiveness compared to other recent works while highlighting its scalability to larger graphs.