Incrementally-Computable Neural Networks: Efficient Inference for
  Dynamic Inputs
Deep learning often faces the challenge of efficiently processing dynamic
inputs, such as sensor data or user inputs. For example, an AI writing
assistant is required to update its suggestions in real time as a document is
edited. Re-running the model each time is expensive, even with compression
techniques like knowledge distillation, pruning, or quantization. Instead, we
take an incremental computing approach, looking to reuse calculations as the
inputs change. However, the dense connectivity of conventional architectures
poses a major obstacle to incremental computation, as even minor input changes
cascade through the network and restrict information reuse. To address this, we
use vector quantization to discretize intermediate values in the network, which
filters out noisy and unnecessary modifications to hidden neurons, facilitating
the reuse of their values. We apply this approach to the transformers
architecture, creating an efficient incremental inference algorithm with
complexity proportional to the fraction of the modified inputs. Our experiments
with adapting the OPT-125M pre-trained language model demonstrate comparable
accuracy on document classification while requiring 12.1X (median) fewer
operations for processing sequences of atomic edits.
Or Sharir, Anima Anandkumar
# Incrementally-Computable Neural Networks:

###### Abstract

Deep learning often faces the challenge of efficiently processing dynamic inputs, such as sensor data or user inputs. For example, an AI writing assistant is required to update its suggestions in real time as a document is edited. Re-running the model each time is expensive, even with compression techniques like knowledge distillation, pruning, or quantization. Instead, we take an _incremental computing_ approach, looking to reuse calculations as the inputs change. However, the dense connectivity of conventional architectures poses a major obstacle to incremental computation, as even minor input changes cascade through the network and restrict information reuse. To address this, we use _vector quantization_ to discretize intermediate values in the network, which filters out noisy and unnecessary modifications to hidden neurons, facilitating the reuse of their values. We apply this approach to the transformers architecture, creating an efficient incremental inference algorithm with complexity proportional to the fraction of the modified inputs. Our experiments with adapting the OPT-125M pre-trained language model demonstrate comparable accuracy on document classification while requiring 12.1X (median) fewer operations for processing sequences of atomic edits.

## 1 Introduction

Large language models (LLMs) based on the transformers architecture (Vaswani et al., 2017; Devlin et al., 2019; Radford et al., 2019; Brown et al., 2020) have revolutionized the entire natural language processing field, achieving remarkable results on a wide range of tasks, including text classification, question answering, document retrieval and many others. Increasingly, LLMs aid in the writing process itself, analyzing and proposing suggestions as documents are edited (Shi et al., 2022; Ippolito et al., 2022), both in online and offline settings. In the online case, LLMs must react in real time as a document is edited, word-by-word. In the offline case, there is a preexisting history of revisions waiting in the queue for processing. Even though the difference between each revision is often small - just a single word in the online setting - today's LLMs process each revision from scratch, wasting a lot of computational resources.

An ideal deep-learning model should be able to leverage the similarity between two revisions and reuse information as much as possible. Such an approach is known as _incremental computing_. Usually, incremental computing is solved by examining the dependency graph of the computational operations and tracking which nodes are affected by modified inputs. The prototypical example is a software build system, tracking which source files have changed and recompiling just the files that depend on them. However, most deep learning architectures, and specifically transformers, are structured such that nearly all neurons depend on nearly all inputs, as illustrated in fig. 0(a). Having a _densely connected_ architecture was proven to be a crucial aspect for producing highly expressive models (Sharir and Shashua, 2018; Levine et al., 2017; Cohen et al., 2018). But this same property also poses a challenge for reusing calculations.
We propose to augment transformers with discrete operations, namely, vector quantization (VQ) (van den Oord et al., 2017), to inhibit superfluous effects on the intermediate values in the network. By only allowing for meaningful effects to propagate, VQ paves the path to incrementally computable neural networks, as illustrated in fig. 1b. In sec. 3, we describe our complete algorithm for incremental computation of Vector-Quantized Transformers, or VQT for short, with a runtime complexity proportional to the edit distance of the documents.

We demonstrate our approach in sec. 4 by adapting the OPT-125M pre-trained language model (Zhang et al., 2022) and distilling it to its analog VQ-OPT model, followed by fine-tuning on document classification task (IMDB (Maas et al., 2011)), on which it obtains comparable accuracy to the original OPT-125M model. To measure the runtime performance on processing real-world edits, we scraped Wikipedia edit histories. Unlike the plain OPT, VQ-OPT requires 12.1X (median) fewer arithmetic operations for online processing of a sequence of atomic edits (replace / insert / delete a single token). For offline processing of two complete revisions, we observe a more modest 4.7X reduction on average, as expected when modifying larger chunks of the document as opposed to atomic edits.

## 2 Related Works

**Model compression** is the primary approach for efficient inference. Knowledge distillation (Buciluundefined et al., 2006; Hinton et al., 2015; Sanh et al., 2020) trains a smaller "student" network to imitate the outputs of a larger "teacher" network. Pruning (Han et al., 2015, 2016) and tensor factorizations (Yu et al., 2017; Hsu et al., 2022) can be used to find sparse and low-rank representation, respectively, of the network's weights. Weight and activation quantization (Gholami et al., 2021) can be used to reduce the memory footprint and communication costs, which can be crucial for running extreme LLMs (\(>\)1B parameters) on a single GPU or even edge devices. Combined, they can be very effective, but they do not leverage the vast redundancy found in the editing process.

**Sparse computation** is a form of selective computation where computation is applied according to some sparse activation mask (Ren et al., 2018; Pan et al., 2018; Cavigelli et al., 2017; Parger et al., 2022; Chen et al., 2023). Most related to this paper are works that utilize temporal redundancy in video frames. The general approach is to compute the delta between consecutive activation maps, truncate small values, and then only operate on the remaining sparse values while also trying to account for the loss in numerical precision. A similar approach was also used for accelerating generative image editing (Li et al., 2022). While sharing some similarities to our approach, the cited methods focus on a different domain (vision), with different assumptions (gradual pixel change, locality), using a different underlying architecture (convolutional), and resulting in approximate

Figure 1: In conventional architectures **(a)**, reusing calculations is challenging as modifying even a single input coordinates affects most of the network. We propose vector-quantized networks **(b)** to filter insignificant output perturbations and enable activation reusability.
(as opposed to exact) inference, which makes direct comparison nontrivial. Swapping words can cause abrupt and non-local (though often sparse) effects on the document, very different from the gradual and local nature of video consecutive frames. Furthermore, our work handles the insertion and deletion of words, akin to shifting pixels around in a non-uniform pattern, while the cited works mostly assume the camera is static. Nevertheless, future work could investigate the transfer of VQT to the vision domain and allow for a more direct comparison.

**Vector Quantization**(Gray, 1984) has been widely used in machine learning for various means, but never for incremental computing. Denote with \(C\in\mathbb{R}^{q\times d}\) a codebook of \(q\)\(d\)-dimensional vectors, then vector quantization is typically defined as \(VQ(\mathbf{x})=C_{\operatorname*{argmin}_{i}d(\mathbf{x},C_{i},.),:}\) for some distance metric \(d(\cdot,\cdot)\). VQ is a discrete operation, both with respect to its parameters, i.e., the codebook, and with respect to its input, meaning its derivatives are zero almost everywhere. However, several methods have been proposed for defining a "pseudo-derivative", e.g., via the straight-through estimator (van den Oord et al., 2017), which enables embedding vector quantization into deep learning models and training them with any gradient descent optimizer. Such methods were employed to define variational auto-encoders with discrete hidden variables (van den Oord et al., 2017), learn a shared latent space for images and text (Gu et al., 2022; Yu et al., 2022), compress audio (Zeghidour et al., 2021), as well as to improve generalization in transformers (Liu et al., 2022, 2021). To the best of our knowledge, our work is the first usage of VQ for improving the efficiency at inference time.

## 3 Method

To support the incremental computation of transformers, we propose two simple modifications to the self-attention layer in the transformers architecture: (i) Append a VQ layer the self-attention outputs the outputs, and (ii) replace the softmax normalization of the attention matrix with any element-wise non-linearity. This amounts to the following vector-quantized self-attention operation:

\[O=\operatorname{VQ}(\sigma(QK^{T})V), \tag{1}\]

where \(Q,K,\) and \(V\) are the query, key, and value matrices, respectively, \(\sigma\) is the non-linear element-wise activation (e.g., a GELU), and VQ the VQ module applied on every row separately. For multi-head self-attention, the VQ layer takes as input the concatenation of all attention heads, followed by an additional linear layer to mix the heads. It was recently proposed Hua et al. (2022); Ma et al. (2022) that using such an element-wise non-linearity has comparable performance to softmax while being easier to optimize on the hardware level. Here, we employ it for numerical stability, because though reusing calculations with softmax is mathematically possible, numerically it can lead to a significant loss of precision.

Using the above module, we can now present how we can reuse calculations. As discussed in the introductions, there are two settings of interest, online editing, operating on one small change at a time, and offline batch processing, operating on a batch of revisions. To simplify the presentation, we will present our algorithm for the offline setting, where the online setting is equivalent to a batch of size 2 and keeping a cache for the first input. Furthermore, we first assume the only valid edit operations are token replacements, and will handle the token insertion and deletion in subsection 3.3.

We reuse calculations in two steps. First, we describe a compressed format for storing the quantized activations, leveraging the redundancy in the quantized intermediate values of similar revisions. Second, we show how this compressed format can be directly manipulated to efficiently implement any operation in the VQ Transformer.

### Compressing Vector-Quantized Activations

The intermediate values in the transformer can typically be described as a 3D tensor \(X\in\mathbb{R}^{b\times n\times d}\), where \(b,n,\) and \(d\) denoted the batch size, sequence length, and hidden dimension, respectively. Since we assume \(X\) is vector-quantized1, each hidden vector in any batch and sequence location is matched against some codebook matrix \(C\in\mathbb{R}^{q\times d}\), represent the unique vectors found in \(X\). This means we can represent it more compactly with an indices matrix \(P\in\{1,\dots,q\}^{b\times n}\) pointing to the codebook vectors, i.e., \(X_{ijk}=C_{P_{ijk}}\). We emphasize that \(C\) is not the same as the codebook in the VQ layer
itself, but rather the representation of the unique sets of vectors in \(X\). It could have both fewer vectors than in VQ as well as more, depending on the sequence of operations up to this point.

If we also assume the edit distance between revisions is small, i.e., few tokens were replaced per revision, then the indices in \(P\) should agree on most sequence locations across the batch dimension. This has two implications. First, \(q=O(n+b)\) since the number of unique indices cannot be more than the length of any row plus the few indices that are different per row. Second, at any sequence location across the batch dimension, most indices should be the same, meaning we can further compress \(P\) through a sparse representation. Namely, at any sequence location pick the most frequent index, resulting in a base set of indices per location, and then store only the coordinates in \(P\) which differ from the base. This sparse representation has an \(O(n+b)\) storage complexity. In total, we get an \(O((n+b)d)\) storage complexity, and since typically \(b=O(n)\) as well, it reduces to just \(O(nd)\) down from \(O(bnd)\) for the dense representation of \(X\). The entire compression scheme is illustrated in fig.2.

### Efficient Operations Over the Compressed Format

Having a compressed representation only helps if we can efficiently operate over it. The most common type of operation in transformers can be broadly described as a _identical per-location vector operation_, i.e., any vector-valued operation that is applied on each location separately. Formally, they can be written as \(Y=F(X)\) such that \(Y_{ij:}=f(X_{ij:})\) for some \(f:\mathbb{R}^{d}\rightarrow\mathbb{R}^{d}\), and it has an \(O(bn\operatorname{cost}(f))\) complexity. This includes normalization layers, linear layers, scaling by a constant, activation functions, and others. In most common configurations, they together constitute more than 70% of the total floating-point operations in the forward pass, and for extreme models like GPT3 (Brown et al., 2020) it is over 97%. Fortunately, we map this operation very efficiently to our compressed format. If \(X\) is represented by \((P,C)\), following the same notations as before, then \(Y\) is equivalent to \((P,F(C))\), i.e., operating only on the codebook matrix while keeping the indices unchanged. This relation holds because

\[Y_{ij:}=f(X_{ij:})=f(C_{P_{ij}:}=f(C)_{P_{ij}:}. \tag{2}\]

Thus, the complexity of applying per-location operations on our compressed format is mere \(O(q\operatorname{cost}(f))=O(n\operatorname{cost}(f))\), i.e., reducing the dependency on the batch size.

For other operations not covered by the above, e.g., self-attention and residual connections, we can show similar improved efficiency, but we defer their description to app. A. In the same appendix, we also explain how the cost of the VQ layer itself could be reduced during inference. In total, we can show that any batch operation in the network can be computed with an equivalent complexity to processing a single document (up to constants). Of course, this analysis depends on the assumption that the VQ layer can indeed converge to a solution during training that maximizes the redundancy found in the input. We demonstrate in our experiments in sec.4 that indeed this method can attain significant computational savings in practice.

Figure 2: Illustration of the compression scheme of the vector-quantized activations through our VQ-Transformer network.
### Supporting Token Insertion and Deletion

Previously, we assumed for simplicity that the only valid edit operations are replacing tokens, keeping the total number of tokens in a document fixed. The main issue with inserting or deleting tokens is the effect it has on the positional embeddings, effectively shifting them around the edit locations. If we were to use conventional positional embeddings, then inserting a token would lead to nearly all token representations to be different between two revisions, and so little opportunity for reusability.

Our solution is training with a _sampled_ absolute positional embedding. During training, instead of using a contiguous range of positional indices (Vaswani et al., 2017), we sample per document a random ordered subset of the maximum number of positional embeddings. So instead of always assigning positions \(1,2,3,4\) to the first 4 tokens, we sample \(p_{1}<p_{2}<p_{3}<p_{4}\), and use those values to fetch their respective vectors from the positional embedding matrix.

In essence, we are training the absolute positional embedding to be relational, forcing the network to only leverage the order between positions and not their absolute value. The benefit of such a scheme is that we can now spread the initial positions, allowing for gaps in between tokens, so new tokens could be inserted with suitable positions. We can further use the attention mask matrix to ensure other tokens do not attend to the pad locations, thus ensuring that each prediction is self-consistent and independent of the other revision in the batch.

For the online setting, every so often might require reindexing the positional values after the initial gaps are filled, akin to defragmentation. As long as it does not happen too often, the expected speedup will remain effective. To ensure this is the case, we can use a very large pool of positional embedding vectors, e.g., on the order of 100X more than the maximal sequence length. It is reasonable to train with such a large number of positional vectors due to the well-known coupon collector problem. See app. B for further discussion.

For the offline batch setting, we do not need as much overhead. We can simply align all revisions by introducing pad tokens for missing or misaligned tokens, and then assign a contiguous range of positions according to the longest document including padding.

## 4 Experiments

We demonstrate our method by training a decoder transformer model following the OPT (Zhang et al., 2022) family of models. Since training large language models from scratch is expensive, we opt instead to use knowledge distillation to adapt the base OPT 125M parameters model to fit our architecture. We follow the procedure of Sanh et al. (2020). We keep all the parameters of the original model while adding the VQ layers in each self-attention module and changing softmax to GELU (Hendrycks and Gimpel, 2020).

We specifically use multi-head VQ, i.e., each vector is split into smaller chunks and each is matched against a codebook of 64 vectors, thus the effective codebook is of size \(64^{\text{heads}}\). For the pseudo-gradient, we use a variant of the Gumbel-Softmax estimator (Jang et al., 2017).

During training, we use the sampled positional embedding scheme of sec. 3.3, where we initialize the larger positional embedding matrix from the original by simply repeating each positional embedding to match the new size.

For distillation, we use the Pile (Gao et al., 2020), which constitutes a large subset of the corpus used to train OPT. Unlike Zhang et al. (2022), we used the raw corpus without extra filtering and deduplication steps. We trained for 100K iterations, using 16384 tokens per iteration with a max sequence length of 2048, 5K iterations of linear warm-up to a learning rate of 5e-4, followed by a cosine decay to 5e-5.

As an alternative to our incremental computing approach, we also distilled OPT to a smaller OPT model with 6 instead of 12 layers, following the same initialization as Sanh et al. (2020) and training using the same method as above (though Sanh et al. (2020) trained their distilled models for longer).

After the initial distillation phase, we fine-tuned our VQ-OPT model, the original OPT, and our DistilOPT model on sentiment analysis using the IMDB reviews dataset. It was chosen as it operates over relatively long documents, and as it could represent tasks relevant to a hypothetical writing assistant. We present the results in table 1, and we included the reported results of RoBERTa (Liu
et al., 2019; Ding et al., 2021) as a reference. As can be seen, both VQ-OPT and DistilOPT attain comparable results to the original OPT, demonstrating that our proposed approach can retain most of the capacity of the original OPT, with VQ-OPT retaining 95-97% of the accuracy of OPT-125M, depending on the number of VQ heads (i.e., codebook size).

Finally, we measure the runtime complexity for processing edits in a document. We examine the offline case of processing an entirely new revision of a document and the online case of atomic edits. We also examine the case of atomic edits happening in the first 5% of tokens for a more fair comparison to OPT-125M and DistilOPT which do not explicitly leverage the redundancy found in edited documents. For every case, we have collected 500 pairs of consecutive revisions from the edit history of Wikipedia articles. The articles were selected from the list of featured articles that also had a long history of revisions, and the specific revisions were randomly sampled from the set of revisions having at least 1536 tokens and no more than 2048. We chose revisions of specific lengths to ensure they will fit within all architectures as well as reduce the effect of variable sequence length on the complexity estimation. Revisions with purely metadata changes, as well as revisions that were later reverted (often due to malicious editing), were pruned from the histories.

We focus on the VQ-OPT with 2 heads, as it retains as much as 95% of the accuracy of OPT-125M while providing the most computational benefits. We measured the theoretical arithmetic operations required for the forward pass assuming the previous revision was already processed. We present the ratio of arithmetic operations for the original OPT to VQ-OPT as the theoretical speedup under ideal implementation. For the offline case where we process two complete revisions, we observe that on average the theoretical speedup is 4X. However, a closer examination reveals that the theoretical speedup is simply proportional to the fraction of the modified tokens, i.e., changing fewer words results in more opportunity to reuse calculations, as presented in figure 3.

To simulate the online case where a user edits a document word-by-word, we pick a random modified location in a given pair of revisions and keep all the changes up to that point in the document and ignore all that came after it. Here we see that the median theoretical speedup is 12.1X, and that there is a correlation between the relative location of the edit and the theoretical speedup. Our results for the online case are presented in figure 4.

In both the online and offline cases it is important to keep in mind that for DistilOPT is limited to just a 2X improvement over OPT-125M.

\begin{table}
\begin{tabular}{l c c} \hline \hline
**Model** & \multicolumn{2}{c}{**IMDB**} \\ \hline  & Accuracy & F1 \\ \hline RoBERTa & 95.3 & 95.0 \\ OPT-125M & 94.4 & 94.5 \\ DistilOPT & 92.4 & 92.3 \\ VQ-OPT (h=2) & 90.3 & 90.4 \\ VQ-OPT (h=4) & 91.6 & 91.6 \\ \hline \hline \end{tabular}
\end{table}
Table 1: Accuracy and F1 on the IMDB document classification dataset. \(h\) denotes the number of heads in each VQ layer.

\begin{table}
\begin{tabular}{l c c c} \hline \hline
**Model** & Atomic & Entire Revision & First 5\% \\ \hline OPT-125M & 1X & 1X & 1X \\ DistilOPT & 2X & 2X & 2X \\ VQ-OPT (h=2) & 12.1X & 4.7X & 4.8X \\ VQ-OPT (h=4) & 5.2X & 2.5X & 2.2X \\ \hline \hline \end{tabular}
\end{table}
Table 2: Theoretical speedups for processing sequence of edits to documents, based on measuring relative reduction in arithmetic operations on subset of 500 random edits (either atomic or whole revisions) scraped from English Wikipedia.
## 5 Discussion

We proposed the first incremental computable transformer model, attaining significant computational savings while performing comparably to its target pre-trained model.

Nevertheless, we wish the emphasize some of the limitations of these early findings. It is well known that as language models grow, their behavior can change in a non-linear way (Brown et al., 2020). Namely, it is well-documented that post-training quantization of very large language models (\(\geq\)6B) is more difficult due to the presence of activation outliers (Xiao et al., 2022). Testing our method on such scales could reveal similar challenges, though some of the proposed solutions could be applicable to our case. Furthermore, while the fundamental assumption of our approach is that minor input modifications should not typically result in massive modifications in the computational graph, it is trivial to imagine pathological edge cases where that assumption would not hold. It is thus crucial to further experiment on a wide variety of NLP tasks and assess the runtime complexity per task.

Figure 4: Relative reduction in arithmetic operations for online processing of atomic edits (logarithmic scale). Each point corresponds to the processing of a single atomic edit at a given normalized location. 12.1X is the median reduction in cost.

Figure 3: Relative reduction in arithmetic operations for offline processing of two complete revisions. Each point corresponds to 2 consecutive revisions in a Wikipedia edit history with respect to the fraction of modified tokens, i.e., edit distance, demonstrating complexity is proportional to edit distance. 4.7X is the median reduction.
Regardless of the above limitations, incremental computation sets a completely new path to efficient inference, which was under-explored in the machine learning community. While this paper has focused on its application to natural language, the same method is highly relevant to many other domains, including different modalities (video, genes), as well as settings (e.g., agent-environment interaction loop). We plan to explore these avenues in future works.

## Acknowledgments

The authors would like to thank Devin Chotzen-Hartzell for his contributions to preliminary experiments and initial code for scraping Wikipedia edit histories.
