Deep Equilibrium Models

Introduction

Most modern feedforward deep networks are built on the core concept of layers. In the forward pass, each network consists of a stack of some $L$ transformations, where $L$ is the depth of the network. To update these networks, the backward passes rely on backpropagating through the same $L$ layers via the chain rule, which typically necessitates that we store the intermediate values of these layers. The value for $L$ is usually a hyperparameter and is picked by model designers (e.g., ResNet-101 ). Among the many applications of deep networks, sequence modeling has witnessed continuous advances in model architectures. Specifically, while recurrent networks have long been the dominant model for sequences , deep feedforward architectures based on temporal convolutions and self-attention have (re-)emerged to claim superior performance on a variety of sequence prediction tasks.

In very general terms, a deep feedforward sequence model can be written as the following iteration:

where $i$ is the layer index; $\mathbf{z}_{1:T}^{[i]}$ is the hidden sequence of length $T$ at layer $i$; $\mathbf{x}_{1:T}$ is the input sequence (i.e., we are choosing to explicitly model skip connections, for reasons we explain later); and $f^{[i]}_{\theta}$ is some nonlinear transformation which typically enforces causality (i.e., future time points cannot influence past ones). Our paper derives its motivation from surprising recent works that employ the same transformation in each layer (known as weight tying, with $f^{[i]}_{\theta}=f_{\theta},\forall i$) and still achieve results competitive with the state-of-the-art . This raises an interesting question: If the same transformation is applied at each layer of a deep network, what is the limit of this process, and how do we model it?

In this paper, we propose a new approach to “deep” modeling that addresses this question. Specifically, we introduce the deep equilibirum model (DEQ), a method that directly computes the fixed point $\mathbf{z}^{\star}_{1:T}$ of a nonlinear transformation, i.e., the solution to the nonlinear system

This solution corresponds to the eventual hidden layer values of an infinite depth network. But instead of finding this value by iterating the model, we propose to directly (and in practice, more quickly) solve for the equilibrium via any black-box root-finding method. Importantly, we show that DEQ can directly differentiate through the fixed point equations via implicit differentation, which does not require storing any intermediate activation values. In other words, we can backpropagate through the infinite-depth network while using only constant memory, equivalent to a single layer’s activations.

After developing the generic DEQ approach, we study in detail the instantiation of DEQ via two feedforward sequence models: trellis networks (weight-tied temporal convolutions) and memory-augmented universal transformers (weight-tied multi-head self-attention) , both of which have obtained state-of-the-art performance (SOTA) on various sequence tasks. We show how both the forward and backward passes can be implemented efficiently via quasi-Newton methods. Finally, we demonstrate via experiments on large-scale high-dimensional sequence modeling benchmarks (e.g., WikiText-103 language modeling) that, despite only using constant memory, DEQ can attain modeling accuracy on par with (or even slightly better than) corresponding layer-based networks. We believe that DEQ offers a novel perspective on the analysis of sequential data.

Background

An important factor that limits the development of high-capacity networks is limited memory on hardware devices used for training. To address this issue, proposes gradient checkpointing that reduces an $L$-layer network’s memory requirement to $O(\sqrt{L})$ at the cost of extra forward passes (i.e., extra computations). Alternatively, develop reversible networks, where each layer’s activations can be reconstructed from the next layer during backpropagation to reduce memory requirements. DEQs reduce memory consumption to a constant (i.e., independent of network “depth”) by directly differentiating through the equilibrium point and thus circumventing the construction and maintenance of “layers”.

Some prior works have studied continuous views of deep networks. proposes a biologically inspired equilibrium propagation framework for an energy-based model whose prediction is the fixed-point of the energy dynamics at its local minimum. model deep ResNets by black-box ODE solvers in forward and backward passes (as if the network has smaller “layer steps”) given the start- and end-points of a dynamical system. For deep sequence models, consider the RNN as a dynamical system to investigate its stability properties.

Our work takes a further step in the direction of the aforementioned areas. While some of the prior work has primarily focused on the analysis of residual architectures or small symmetric-weight energy-based models, our work is not predicated on any specific type of interlayer transformation. We show that DEQs can be easily instantiated via two very different sequence learning architectures. More fundamentally, unlike ODE-based methods, which use the adjoint system to backpropagate through the entire latent trajectory, the DEQ model solves directly for sequence-level equilibria via a quasi-Newton method and backpropagates directly through this fixed point, without regard for the solution path that brought it there. Moreover, while ODE-based models were verified on numerical experiments and MNIST classification, computation and numerical stability issues challenge their application to large-scale problems. In comparison, we demonstrate the applicability of DEQs on realistic high-dimensional sequence tasks with competitive performance, while enjoying similar constant-memory benefits as .

The DEQ model can be viewed as an infinitely deep network, but interestingly can also be viewed as a single-layer network, with the caveat that the layer is defined implicitly: the output $\mathbf{z}^{\star}_{1:T}$ is defined as the value which solves some non-linear equation. There has been a growing interest in implicit layers in recent years , but the precise formulation of the DEQ is quite different, and our current models represent the largest-scale practical application of implicit layers in deep learning of which we are aware. Concurrent work also looks at such implicit layers in a broad sense and focuses on training small models via Lagrangian methods; a combination of these approaches with the DEQ model is a promising avenue for future work.

Another thread of work on implicit layers traces back to some of the original papers on recurrent networks trained via recurrent backpropagation (RBP) . Recent work has re-examined RBP and established an implicit, constant-memory variant based on conjugate gradient and Neumann series. A number of related papers also enforce fixed point conditions within RNN architectures . Whereas the DEQ model shares similarities with the RBP approach, some major differences involve: 1) the explicit use of equilibrium as a replacement for depth in general networks, along with our proof of the universality of these models to replace depth; 2) the use of the approach in methods outside of fixed-input RNNs (i.e., same input vector $x_{t}$ for all $t$), especially the compatibility with SOTA architectures; and 3) the scalability of the DEQ model to practical tasks where it achieves results on par with the current SOTA, whereas RBP has typically been applied in small-scale settings.

The Deep Equilibrium Sequence Model

We broadly consider the class of weight-tied deep sequence models (with passthrough connections from the input to each layer), which consist of the update

We note that this model encapsulates classes such as the trellis network and the universal transformer (which is typically not written with passthrough connections, but this is a trivial modification). Such weight-tying is generally considered to come with four major benefits: 1) it acts as a form of regularization that stabilizes training and supports generalization; 2) it significantly reduces the model size; 3) it is trivial to show that any deep network can be represented by a weight-tied deep network of equal depth and only a linear increase in width (see Appendix C); and 4) the network can be unrolled to any depth, typically with improved feature abstractions as depth increases . However, in practice almost all such models (and deep nets in general) are stacked, trained and evaluated by unrolling a pre-determined, fixed number of layers. One reason is the limited memory on training hardware: the models need to store intermediate hidden units for backpropagation and thus cannot be trained beyond a certain depth that depends on the available memory.

In principle, the network could have infinite depth. This is attained in the limit of unrolling a weight-tied model for an ever higher number of layers. What is the limit of this process? In practice, for certain classes of $f_{\theta}$ (discussed later), we hypothesize and observe that such weight-tied models tend to converge to a fixed point as depth increases towards infinity (see Appendix D for empirical evidence). In other words, as each layer refines the previous one by combining temporal features across the sequence, increasing depth towards infinity brings “diminishing returns”: each additional layer has a smaller and smaller contribution until the network reaches an equilibrium:

We introduce the deep equilibrium model (DEQ) which, instead of iteratively stacking $f_{\theta}$, directly solves for and differentiates through the equilibrium state.

Unlike a conventional network where the output is the activations from the $L^{\text{th}}$ layer, the output of a DEQ is the equilibrium point itself. Therefore, the forward evaluation could be any procedure that solves for this equilibrium point. Conventional deep sequence networks, if they converge to an equilibrium, can be considered a form of fixed-point iterations:

One can alternatively use other methods that provide faster convergence guarantees. For notational convenience, we define $g_{\theta}$ and rewrite Eq. (4) as g_{\theta}(\mathbf{z}_{1:T}^{\star};\mathbf{x}_{1:T})=f_{\theta}\big{(}\mathbf{z}_{1:T}^{\star};\mathbf{x}_{1:T}\big{)}-\mathbf{z}_{1:T}^{\star}\rightarrow 0. The equilibrium state $\mathbf{z}_{1:T}^{\star}$ is thus the root of $g_{\theta}$, which we can find more easily with Newton’s method or quasi-Newton methods (e.g., Broyden’s method ):

where $B$ is the Jacobian inverse (or its low-rank approximation) at $\mathbf{z}_{1:T}^{[i]}$, and $\alpha$ is the step size. But generally, one can exploit any black-box root-finding algorithm to solve for the equilibrium point in the forward pass, given an initial estimate $\mathbf{z}_{1:T}^{}$ (which we set to $\mathbf{0}$): $\mathbf{z}_{1:T}^{\star}=\mathsf{RootFind}(g_{\theta};\mathbf{x}_{1:T})$

1.2 Backward Pass

A major problem with using a black-box $\mathsf{RootFind}$ is that we are no longer able to rely on explicit backpropagation through the exact operations in the forward pass. While one can certainly fix an algorithm (say Newton’s method) to obtain the equilibrium, and then store and backpropagate through all the Newton iterations, we provide below an alternative procedure that is much simpler, requires constant memory, and assumes no knowledge of the black-box $\mathsf{RootFind}$.

Then the loss gradient w.r.t. $(\cdot)$ (for instance, $\theta$ or $\mathbf{x}_{1:T}$) is

where J_{g_{\theta}}^{-1}\big{|}_{\mathbf{x}} is the inverse Jacobian of $g_{\theta}$ evaluated at $\mathbf{x}$.

The proof is provided in Appendix A. The insight provided by Theorem 1 is at the core of our method and its various benefits. Importantly, the backward gradient through the “infinite” stacking can be represented as one step of matrix multiplication that involves the Jacobian at equlibrium. For instance, an SGD update step on model parameters $\theta$ would be

Note that this result is independent of the root-finding algorithm we choose or the internal structure of the transformation $f_{\theta}$, and thus does not require any storage of the intermediate hidden states, which is necessary for backpropagation in conventional deep networks.

1.3 Accelerating DEQ by Approximating the Inverse Jacobian

One challenge of enforcing the forward and backward passes described in Sections 3.1.1 and 3.1.2 is the cost of computing the exact inverse Jacobian $J_{g_{\theta}}^{-1}$ at every intermediate Newton iteration. We propose to address this using Broyden’s method , a quasi-Newton approach that makes low-rank updates to approximate $J_{g_{\theta}}^{-1}$ via the Sherman-Morrison formula :

where $\Delta\mathbf{z}^{[i+1]}=\mathbf{z}_{1:T}^{[i+1]}-\mathbf{z}_{1:T}^{[i]}$ and $\Delta g_{\theta}^{[i+1]}=g_{\theta}(\mathbf{z}_{1:T}^{[i+1]};\mathbf{x}_{1:T})-g_{\theta}(\mathbf{z}_{1:T}^{[i]};\mathbf{x}_{1:T})$. Initially, we set $B_{g_{\theta}}^{}=-I$ and the Broyden iterations are stopped when either the norm of $g_{\theta}^{[i]}$ falls below a tolerance $\varepsilon$ or when the maximum number of iterations is reached. This lets us avoid the cubic cost induced by the inverse operation.

where the first term (a vector-Jacobian product) can be efficiently computed via autograd packages (e.g., PyTorch ) for any $\mathbf{x}$, without explicitly writing out the Jacobian matrix. Such linear systems can generally be solved by any indirect methods that leverage fast matrix-vector products; we thus propose to also rely on Broyden’s method (other indirect methods would also suffice) to solve for Eq. (11) and directly backpropagate through the equilibrium by Theorem 1 in the backward pass.

2 Properties of Deep Equilibrium Models

Section 3.1 develops a sequence model that, while still based on the deep learning philosophy, is quite different from other approaches in the field, as its output is agnostic to the choice of the $\mathsf{RootFind}$ algorithm in the forward pass. We now discuss some implications of the DEQ approach.

An important benefit of DEQ is its extreme memory efficiency. As outlined in Section 3.1.3, since we are able to use any root-finding algorithm for both the forward and backward passes (e.g., Broyden’s method ), a DEQ only needs to store $\mathbf{z}_{1:T}^{\star}$ (the equilibrium sequence), $\mathbf{x}_{1:T}$ (input-related, layer-independent variables), and $f_{\theta}$ for the backward pass. Note that as we only need the vector-Jacobian product (with dimension $N\times Td$, where $N$ is the minibatch size) in Eq. (11), we never need to explicitly construct the Jacobian J_{g_{\theta}}^{\top}\big{|}_{\mathbf{z}_{1:T}^{\star}}, which could be prohibitively large on long and high-dimensional sequences (with dimension $N\times(Td)^{2}$). Compared to other deep networks, DEQs therefore offer a constant-memory alternative that enables models that previously required multiple GPUs and other implementation-based techniques (e.g., half-precision or gradient checkpointing ) to fit easily into a single GPU.

Our analysis in Sections 3.1.1, 3.1.2, and 3.1.3 is independent of the choice of $f_{\theta}$, and the same kind of memory benefit is present regardless of the type of $f_{\theta}$. However, to find the equilibrium in a reliable and efficient manner, generally $f_{\theta}$ needs to be stable and constrained. The two instantiations we provide in Section 4 are examples of stable transformations. (The gated activation in TrellisNet and layer normalization in the transformer constrain the output ranges.)

A natural question arises: if one DEQ is good, can we get additional benefits by “stacking” DEQs (with potentially different classes of transformations)? The answer, somewhat surprisingly, is no, as evidenced by the following theorem, which is proved in Appendix B. The theorem essentially shows that stacking multiple DEQs does not create extra representational power over a single DEQ.

where $[\cdot]_{[:,-d:]}$ denotes the last $d$ feature dimensions of $[\cdot]$.

Instantiations of DEQ

While the forward and backward analyses of DEQ do not depend on the internal structure of $f_{\theta}$, in this section we briefly highlight two examples of $f_{\theta}$ as specific instantiations of DEQ. Both models (TrellisNet and self-attention ) achieve state-of-the-art results on various sequence modeling benchmarks. Importantly, through these two very different models and their properties, we illustrate the compatibility of the DEQ approach with all three major families of existing deep sequence networks: transformers, RNNs, and temporal convolutional networks (TCNs).

We briefly introduce the trellis network (TrellisNet) here and refer interested readers to for a detailed description. Generally, TrellisNet is a TCN with two modifications. First, a linear transformation of the original input sequence $\mathbf{x}_{1:T}$ is added to the convolutional outputs at all layers. Second, the convolutional kernel weights are tied across the depth of the network (i.e., TrellisNet is a weight-tied TCN). Thus we can write TrellisNet with convolutional kernel size $k$, dilation $s$, and nonlinearity $\psi$ in DEQ form as

where $\mathbf{u}_{-(k-1)s:}$ is typically: 1) the last $(k-1)s$ elements of the previous sequence’s output (if using history padding ); or 2) simply zero-padding. $[\cdot,\cdot]$ means concatenation along the temporal dimension. Following , we use the LSTM gated activation for $\psi$.

At a high level, multi-head self-attention transformers are very different from most deep networks. Instead of convolutions or recurrence, a self-attention layer maps the input into $Q$ (query), $K$ (key), and $V$ (value) and computes the attention score between time-steps $t_{i}$ and $t_{j}$ as $[QK^{\top}]_{i,j}$. This attention score is then normalized via softmax and multiplied with the $V$ sequence to produce the output. Since the transformer is order-invariant, prior work proposed to add positional embeddings (PE) to the self-attention operation. Following this design, further proposed the universal transformer, which “recurrently stacks” the transformer’s self-attention and transition function block $\phi$ through a number of layers. Referring readers to for more details, we write a weight-tied transformer in the DEQ form as

Figure 1 provides a generic comparison between these conventional weight-tied deep networks and the DEQ approach, highlighting the constant memory requirements of the latter.

Experiments

We evaluate DEQ on both synthetic stress tests and realistic large-scale language modeling (where complex long-term temporal dependencies are involved). We use the two aforementioned instantiations of $f_{\theta}$ in DEQ. On both WikiText-103 (which contains $>$100M words and a vocabulary size of $>$260K) and the smaller Penn Treebank corpus (where stronger regularizations are needed for conventional deep nets) for word-level language modeling, we show that DEQ achieves competitive (or better) performance even when compared to SOTA methods (of the same model size, both weight-tied and not) while using significantly less memory. We provide a more detailed introduction of the tasks and datasets in Appendix F.

Both instantiations of DEQ use Broyden’s method to avoid direct computation of the inverse Jacobian, as described in Section 3.1.3. We note that the use of DEQ implicitly introduces a new “hyperparameter” – the stopping criterion for Broyden iterations. During training, we set this tolerance $\varepsilon$ of forward and backward passes to $\varepsilon=\sqrt{T}\cdot 10^{-5}$ and $\sqrt{T}\cdot 10^{-8}$, respectively. At inference, we relax the tolerance to $\varepsilon=\sqrt{T}\cdot 10^{-2}$ (or we can use a smaller maximum iteration limit for Broyden’s method; see discussions later). For the DEQ-TrellisNet instantiation, we roughly follow the settings of . For DEQ-Transformers, we employ the relative positional embedding , with sequences of length 150 at both training and inference on the WikiText-103 dataset. Implementations and pretrained models can be found at https://github.com/locuslab/deq.

1 Copy Memory Task

The goal of the copy memory task is simple: to explicitly test a sequence model’s ability to exactly memorize elements across a long period of time (see Appendix F). As shown in Table 1, DEQ demonstrates good memory retention over relatively long sequences (${T=400}$), with substantially better results than recurrent architectures such as LSTM/GRU (consistent with the findings in ).

2 Large-Scale Language Modeling

One issue encountered in prior works that take a continuous view of deep networks is the challenge of scaling these approaches to real, high-dimensional, large-scale datasets. In this subsection, we evaluate the DEQ approach on some large-scale language datasets and investigate its effectiveness as a practical “implicit-depth” sequence model.

Following the set of hyperparameters used by for TrellisNet, we evaluate the DEQ-TrellisNet instantiation on word-level language modeling with the PTB corpus. Note that without an explicit notion of “layer”, we do not add auxiliary losses, as was done in . As shown in Table 2, when trained from scratch, the DEQ-TrellisNet achieves a test perplexity on par with the original deeply supervised TrellisNet.

On the much larger scale WT103 corpus (about 100x larger than PTB), the DEQ-TrellisNet achieves better test perplexity than the original deep TrellisNet. For the Transformer instantiation, we follow the design of the Transformer-XL model . We specifically compare to a “medium” Transformer-XL model (the largest released model that can fit on GPUs) and a “small” Transformer-XL model, while noting that the largest Transformer-XL network has massive memory requirements (due in part to very wide hidden features, batch sizes, and training-time sequence lengths, which would not be decreased by a DEQ) and can only be trained on TPUs . In Table 3, we show that the DEQs yield competitive performance, outperforming prior SOTA approaches such as on similar model sizes while consuming much less memory during training.

For conventional deep networks with $L$ layers, the training memory complexity is $O(L)$ since all intermediate activations are stored for backpropagation. In comparison, DEQs have an $O(1)$ (i.e., constant) memory footprint due to the root-finding formulation. We benchmark the reduced memory consumption in the last column of Tables 2 and 3, with controlled sequence lengths and batch sizes for fairness. On both instantiations, the DEQ approach leads to an over 80% (up to 88%) reduction in memory consumption by the model (excluding word embeddings, which are orthogonal to the comparison here). Moreover, we empirically verify (using a 70-layer TrellisNet) that DEQ consumes even less memory than gradient checkpointing , a popular technique that reduces the memory required to train a layer-based model to $O(\sqrt{L})$. Note that the DEQ’s memory footprint remains competitive even when compared with baselines that are not weight-tied (a reduction of over 60%), with similar or better accuracy.

To train DEQ models, it is critical to ensure that the model is stable, such that the equilibrium state can be reliably approximated via quasi-Newton methods. While we found that the most commonly used initialization schemes with small values (around 0) suffice, it is generally important to make sure that DEQ starts with a small operator norm in the weight matrices. For both DEQ-TrellisNet and DEQ-Transformer, we observe that they are not sensitive to any specific initialization scheme since non-linearities such as $\sigma$/$\tanh$ and LayerNorm also help make $f_{\theta}$ contractive (and stable). We initialize the parameters of $f_{\theta}$ by sampling from $\mathcal{N}(0,0.05)$.

The deep equilibrium model does not have “layers”. One factor that affects computation time in DEQs is the number of Broyden iterations in forward/backward passes, where each forward Broyden step evaluates $f_{\theta}$ once, and a backward step computes a vector-Jacobian product. We find that in general the number of Broyden iterations gradually increases with training epochs (Figure 2, left, where the $y$-axis is computed by $\frac{\text{Total Broyden Iterations}}{\text{Sequence Length}}$), an observation similar to the one reported for training Neural ODEs . One factor contributing to this phenomenon could be that the training pushes the operator norm of $J_{f_{\theta}}$ to larger values, making the fixed point harder to solve. Meanwhile, the backward pass requires much fewer iterations than the forward, primarily due to the simplicity of the linear system in Eq. (11). We also find that DEQs can almost always converge to the sequence-level fixed point, much more efficiently than original weight-tied transformers (Figure 2, right). Note that after 12 epochs, deeply stacked self-attention tends to oscillate around the fixed point, while DEQs exhibit stable convergence with the quasi-Newton method.

Unlike conventional deep networks that come with a fixed number $L$ of layers, the runtime of DEQ depends strongly on the number of Broyden steps to reach the equilibrium. Therefore, it’s challenging to fairly compare the runtimes of implicit-depth models like DEQ with those of corresponding weight-tied deep networks (e.g., using higher depth necessarily takes longer to run). Ideally, the values of $\varepsilon$ should be as small as possible so as to ensure that the analytical gradients from Theorem 1 are accurate. However, we empirically observe that using a higher $\varepsilon$ or a lower iteration limit allows the DEQ to be trained and evaluated much faster with only a small degradation in performance. For instance, generally we find $\varepsilon<0.1$ or an iteration limit of 30 (on sequence length 75) to be sufficient for competitive performance. Figure 3 visualizes this tradeoff on a medium DEQ-Transformer (without adaptive embedding). Note that accuracy quickly diverges when tolerance $\varepsilon$ is too large (Figure 3, left), suggesting that a poor estimate of the equilibrium can hurt DEQ performances. Table 4 provides approximate runtimes for competitive-accuracy DEQs on WikiText-103. DEQs are typically slower than layer-based deep networks.

Additional empirical remarks as well as training tips are provided in Appendix E.

Conclusion

Deep networks have predominantly taken the form of stacks of layers. We propose the deep equilibrium approach (DEQ), which models temporal data by directly solving for the sequence-level fixed point and optimizing this equilibrium for better representations. DEQ needs only $O(1)$ memory at training time, is agnostic to the choice of the root solver in the forward pass, and is sufficiently versatile to subsume drastically different architectural choices. Our experiments have shown that DEQs have good temporal memory retention, are able to scale to realistic, large-scale sequence tasks, and perform competitively with, or slightly outperform, SOTA methods. Overall, we believe that the DEQ approach provides an interesting and practical new perspective on designing and optimizing sequence models.

References

Appendix A Backward Pass of the Deep Equilibrium Model

One of the core benefits of the DEQ approach comes from its analytical backward gradient at equilibrium. In this section, we provide a proof to Theorem 1 (which we restate here).

Then the loss gradient w.r.t. $(\cdot)$ (for instance, $\theta$ or $\mathbf{x}_{1:T}$) is

where J_{g_{\theta}}^{-1}\big{|}_{\mathbf{x}} is the inverse Jacobian of $g_{\theta}$ evaluated at $\mathbf{x}$.

We first write out the equilibrium sequence condition: $f_{\theta}(\mathbf{z}_{1:T}^{\star};\mathbf{x}_{1:T})=\mathbf{z}_{1:T}^{\star}$. By implicitly differentiating two sides of this condition with respect to $(\cdot)$:

Since $g_{\theta}(\mathbf{z}_{1:T}^{\star})=f_{\theta}(\mathbf{z}_{1:T}^{\star};\mathbf{x}_{1:T})-\mathbf{z}_{1:T}^{\star}$, we have

Appendix B Sufficiency of a Single DEQ “Layer”

A hypothetical extension to the DEQ idea follows from the “deep” philosophy: if one DEQ works so well, why don’t we stack multiple DEQ modules with different parameters $f_{\theta^{[i]}}$ ($i=1,2,\dots$)? We (re-)state and prove the following theorem, which demonstrates the universality of the DEQ model (i.e., sufficiency of exactly one DEQ “layer”).

where $[\cdot]_{[:,-d:]}$ denotes the last $d$ feature dimensions of $[\cdot]$.

Then $\mathbf{w}_{1:T}^{\star}=\begin{bmatrix}\mathbf{z}_{1:T}^{\star}\\ \mathbf{z}_{1:T}^{\star}\end{bmatrix}$ is a fixed point of $\Gamma_{\Theta}(\cdot;\mathbf{x}_{1:T})$, which completes the proof. ∎

Appendix C Universality of Weight-tied, Input-injected Networks

Although the DEQ model corresponds to an infinite-depth network, as mentioned above it applies only to the specific case of weight-tied, input-injected infinite-depth models. This seems at first glance a substantial restriction over traditional deep networks, which have no requirement that the weights at each layer be identical. However, as we show below, this is not an actual restriction on the representational capacity from a mathematical point of view. Specifically, any deep network can be represented as a deep weight-tied network with no increase in depth and only a linear increase in the size of the hidden layer. This argument is equivalent to that presented in the TrellisNet work [8, Theorem 1], but we include it here in a slightly simpler and more general form. We emphasize that in practice we do not use the sparse structure below to construct the weight-tied layers for DEQ, but instead just use dense matrices $W_{z}$ and $W_{x}$. However, the theorem below is important in establishing that there is no notable representational loss.

(Universality of Weight-tied Deep Networks) Consider a traditional $L$-layer deep network defined by the relation

where $\mathbf{z}^{[i]}$ denotes the hidden features at depth $i$, $W^{[i]}$, $\mathbf{b}^{[i]}$ are parameters of the network, $\sigma^{[i]}$ is the non-linearity at depth $i$, and $\mathbf{x}$ is the original input. Then the same network can be represented by a weight-tied, input-injected network of equivalent depth

The proof is constructive: we build the weight-tied network equivalent to the original network by contructing the relevant matrices using a simple “shift” operation. In particular, we define the network parameters as

It is clear from inspection that after $L$ applications of the layer, i.e.,

Thus the weight-tied network computes all the same terms as the original network, using the same depth as the original network, and with a hidden unit size that is just the sum of the individual hidden unit sizes in the original network. This establises the claim of the theorem. ∎

Appendix D Empirical Convergence of Weight-tied Deep Nets

As mentioned in Section 3, one motivation for optimizing the sequence-level equilibrium comes from our empirical observations that, starting at some point of the deep stacking, weight-tied deep networks begin to converge to a fixed point. We show in Figure 4 the convergence of trained layer-based TrellisNet (weight-tied temporal convolutions) and universal transformer (weight-tied self-attention) on randomly selected test samples of different lengths $T=$100, 200, 400 and 800. In both cases, we see a tendency of the activations to converge. Notably, for transformers, we find stacked iterations usually lead to a oscillatory behavior on the plots (Figure 4), with values fluctuating around the actual fixed point (which we empirically verify can be found much more easily with Newton or quasi-Newton methods).

In practice, due to limited computation, we usually set the number of layers to a predetermined number (e.g., 60 layers) and rarely reach the inference depths analyzed in Figure 4. Moreover, in the specific case of transformers, stablizes the training of deep transformers (64-layer) on character-level language modeling with the help of various strong auxiliary losses at intermediate layers. In a certain sense, the addition of auxiliary losses have a similar effect as solving for equilibrium: we want intermediate-level hidden units to be both close to the target and as stable as possible (without drastic interlayer differences).

Appendix E More Remarks on DEQ

While the DEQ approach does not preclude specific architectural choices of $f_{\theta}$ (which means techniques such as layer normalization or weight normalization can work as is), it is not clear how certain regularizations such as auxiliary losses could be applied on DEQ, since there are no more “layers”. For dropout , we follow the practice of , which adapts the RNN variational dropout scheme to feedforward networks by applying the same mask at all levels. We empirically find that adding dropout makes the quasi-Newton methods slower to converge (i.e., inference-time equilibria are easier to find without the presence of noisy zeros). Since the weights of $f_{\theta}$ (and thus its operator norm) are directly related to the stability of root-finding, we observe that weight normalization typically finds more stable parameters and slows down the growth of forward/backward Broyden’s iterations (as described in Figure 2).

Not all sequences in a minibatch converge to the equilibrium with the same number of iterations. However, with standard batched CUDA operations, the sequences that converge faster essentially need to “wait” for the slower ones. Though we empirically find such imbalance to be relatively small in scale, it could mean an inefficient GPU utilization at times.

Instead of training the DEQ from scratch, empirically we find that one can accelerate the DEQ training by pretraining a shallow weight-tied stack of $f_{\theta}$ (e.g., 2 layers), and using the resulting parameters to initialize the DEQ. In general, a shallow model plateaus at much lower accuracy than corresponding DEQs or deeper weight-tied networks. However, given the very small number of layers, a shallow model offers a memory- and computation-efficient starting point for DEQ training.

On extremely long sequences (e.g., $T>1000$), the forward-pass fixed points can be challenging to solve accurately (especially at the start of the training) even with the help of the root-finding methods. Therefore, in practice, we suggest breaking these long sequences into a few subsequences when needed (recall that the forward pass can be any black-box root-finder). Moreover, with the help of Theorem 1, such subsequence technique can be used in the backward pass as well (where we solve for Eq. (11)). For instance, on a sequence $\mathbf{z}_{1:T}^{\star}=\begin{bmatrix}\mathbf{z}_{1:(T/2)}^{\star}&\mathbf{z}_{(T/2):T}^{\star}\end{bmatrix}$:

where terms (A) and (B) require one evaluation of $f_{\theta}(\mathbf{z}_{(T/2):T}^{\star};[\mathbf{x}_{(T/2):T},\mathbf{z}_{1:(T/2)}^{\star}])$ and term (C) requires one evaluation of $f_{\theta}(\mathbf{z}_{1:(T/2)}^{\star};\mathbf{x}_{1:(T/2)})$. Hence, the memory cost is equivalent to that of applying $f_{\theta}$ once on the entire $\mathbf{z}_{1:T}^{\star}$ (but with the subsequences’ equilibrium likely easier to optimize).

Appendix F Task Descriptions

We briefly introduce the three sequence prediction tasks/datasets that we employ to evaluate the DEQ approach in Section 5.

The copy memory task is a small but challenging synthetic stress test that has been frequently used in prior work to test a sequence model’s memory retention ability . In this task, each sequence $\mathbf{x}_{1:(T+20)}$ is 1-dimensional and has length $T+20$, with $\mathbf{x}_{1:10}$ randomly selected from integers $1,2,\dots,8$ (with repetition). The rest of the input elements are all filled with zeros, except for the $\mathbf{x}_{T+10}=9$. The goal of this task is to produce $\mathbf{y}_{1:(T+20)}$ such that $\mathbf{y}_{1:T+10}=\mathbf{0}$ and $\mathbf{y}_{T+11:T+20}=\mathbf{x}_{1:10}$. In other words, a sequence model trained on this task is expected to “recall” the first 10 elements of the sequence once it sees the delimiter $\mathbf{x}_{T+10}=9$, and copy them to the end of the sequence. We generate 20K training samples and 2K testing samples. In prior works, have shown that RNNs generally struggle with the task, especially when $T>100$, whereas feedforward models tend to have better memory.

The Penn Treebank (PTB) corpus is a commonly used dataset for character- and word-level language modeling. When used for word-level language modeling, PTB contains about 888K words at training, with a vocabulary size of 10,000. As this is a comparatively small language corpus (with punctuations and capitalization removed), prior work has shown that well-designed regularizations are required for best results .

The training corpus of WikiText-103 (WT103) is about 110 times larger than PTB, with a vocabulary size over 260K. In general, this dataset is considered much more realistic than many others because it contains many rare words and retains punctuation, numbers, and capitalization from the original Wikipedia articles. WT103 is thus used to evaluate how well a sequence model scales to long sequences from a large vocabulary. This dataset has been frequently used in recent work with high-capacity sequence models .