Path Independent Equilibrium Models Can Better Exploit Test-Time Computation
Authors: Cem Anil
Ashwini Pokle
Kaiqu Liang
Johannes Treutlein
Yuhuai Wu
Shaojie Bai
J Zico Kolter
Roger Baker Grosse
Venue: NeurIPS 2022 Accept (2022)
Keywords: equilibrium models
attractor networks
test time compute
out of distribution generalization

Abstract: Designing networks capable of attaining better performance with an increased inference budget is important to facilitate generalization to harder problem instances. Recent efforts have shown promising results in this direction by making use of depth-wise recurrent networks. In this work, we reproduce the performance of the prior art using a broader class of architectures called equilibrium models, and find that stronger generalization performance on harder examples (which require more iterations of inference to get correct) strongly correlates with the path independence of the system—its ability to converge to the same attractor (or limit cycle) regardless of initialization, given enough computation. Experimental interventions made to promote path independence result in improved generalization on harder (and thus more compute-hungry) problem instances, while those that penalize it degrade this ability. Path independence analyses are also useful on a per-example basis: for equilibrium models that have good in-distribution performance, path independence on out-of-distribution samples strongly correlates with accuracy.  Thus, considering equilibrium models and path independence jointly leads to a valuable new viewpoint under which we can study the generalization performance of these networks on hard problem instances.

Path Independent Equilibrium Models Can Better Exploit Test-Time Computation
Cem Anil
Ashwini Pokle
Kaiqu Liang
Johannes Treutlein 1,4
Yuhuai Wu
Shaojie Bai
Zico Kolter2.6
Roger Grosse
University of Toronto and Vector Institute Camegiie Mellon University PPrinetonn University
University of California, Berkeley "Stanford University and Google Research fanilcem, rgrosse &css. toronto... edu k12471@pp x12471@prince Sprinceton.eee {apokle, shaojieb, zkolter)@cs cmu edu yuhuai@google.com com johameestrrattleeeebeexeeeee edu
"oosch Center for Al
Abstract
Designing networks capable of attaining better performance with increased in- ference budget important to facilitate generalization to harder problem instances. Recent efforts have shown promising results in this direction by making use of depth-wise recurrent networks. We show that a broad class of architectures named equilibrium models display strong upwards generalization, and find that stronger performance on harder examples (which require more iterations of inference to get correct) strongly correlates with the path independence of the system-its ten- dency to converge to the same steady-state behaviour regardless of initialization, given enough computation. Experimental interventions made promote path in- dependence result in improved generalization on harder problem instances, while those that penalize degrade this ability. Path independence analyses are also use- ful on per-example basis: for equilibrium models that have good in-distribution performance, path independence on out-of-distributi samples strongly correlates with accuracy. Our results help explain why equilibrium models are capable of strong upwards generalization and motivates future work that harnesses path inde- pendence general modelling principle to facilitate scalable test-time usage.
1 Introduction
One of the main challenges limiting the practical applicability of modern deep learning systems the ability to generalize outside the training distribution [Koh et al., 2021]. One particularly important type of out-of-distributio (OOD) generalization is upwards generalization, the ability to generalize to more difficult problem instances than those encountered training time [Selsam et al., 2018, Bansal et al., 2022, Schwarzschild et al., 2021b, Nye et al., 2021]. Often, good performance on more difficult instances will require a larger amount of test-time computation, so a natural question arises: how computation to achieve better accuracy?
design neural net architectures which can reliably exploit additional test-time
Equilibrium models, broad class of architectures whose outputs are the fixed points of learned dynamical systems, are particularly suited to meet this challenge. Closely related to weight-tied recurrent models networks that apply the same fixed neural network module repeatedly to hidden- layer activations equilibrium models are capable of adapting their compute budget based on the input they are given. Under what conditions, if any, this input-dependent ability to scale-up test- time compute actually lead to upwards generalization?
Eqqual contribution. Correspondence anilcem@es dot.ooooooooooduuu and wooke@@ssccm..coo
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Path independent model
Path dependent model
0.5
0.0
Dim
11.
2
20
Iterations
40
80
0..
pim
20
80 Iterations +
60
0 Dim 1
100
120
Figure I: Trajectories of path independent models converge the same hidden state for given input, regardless of initialization, whereas the trajectories of path dependent models depend on initialization. Here, we display five trajectories with different initializations obtained from path independent (left) and path dependent model (right) on the prefix-sum task, projected onto two random directions.
We argue that key determiner of whether a learned model can exploit additional test-time computa- tion is whether the dynamical system corresponding the model is path independent; that is, whether the learned model's 's hidden layer activations converge to the same asymptotic behaviour (i.e. fixed point or limit cycle), regardless of the initialization of the system. For example, a simple integrator Tt-1 = + is clearly not path independent, as its final state depends on the imitial state and the number of iterations run; conversely, the system It+1 (#: + 1)/2 is path independent, as will converge to the solution
T - oc regardless of the initial condition of xp. Path indepen- dence closely related to the concept of global stability from control theory (see Section for more).
Intuitively, path independent systems can more easily take advantage of additional test-time iterations than path dependent ones. For instance, gradient descent applied to a convex objective path independent, and correspondingly when confronted with a more ill-conditioned problem instance, one can compensate by increasing the number of iterations. Conversely. weather simulation path dependent, and extending the simulation won't 't yield more accurate predictions of given day s weather. Based on this intuition, we hypothesize that path independence of learned model is key determiner of whether it can take advantage of an increased test-time iteration budget when generalizing harder problem instances:
Path Independence Hypothesis: Models which successfully fit the training distri- bution with path independent function are better able to exploit more test-time iterations to achieve higher accuracy, compared to those which fit the training dis- tribution with a meth-dependent function.
We first introduce a metric for measuring the path independence of a learned model, the Asymptotic Alignment (AA) score. On wide range of tasks including sequence prediction, visual reasoning, image classification, continuous optimization and graph regression, we show that model's AA score strongly correlated with performance when far more iterations are used test time than at training time. In general, we find that path independent models increase their performance monotonically with the number test-time iterations, whereas path dependent models degrade when the number of test time iterations exceeds those at training time. We find that input injection and implicit updates improve both the path independence and the accuracy. Furthermore, we perform an experimental manipulation by introducing regularizers which directly promote or punish path independence. We find that these manipulations, while increasing or decreasing the AA score, also have the corresponding effect on accuracy.
2 Background
Equilibrium Models Equilibrium models treat computing internal representations as a fixed-point finding problem. [McClelland and Rumelhart, 1989, Liao et al., 2018, Bai et al., 2019] Concretely, letting n= and fw IR + R stand for an input and the equilibrium model function (or
Code will be released along with the paper

---

"cell") parametrized by w E R respectively, equilibrium models aim to solve for the fixed point =² E IR. that satisfies x" (z 2²). The cell fn might represent anything from fully connected layer to a transformer block [ (Vaswani et al., 2017]. We emphasize that fw directly depends on the input z; following existing literature, we refer to this as input injection. The outcome of the fixed point finding process might depend on the initial fixed point guess. To make this dependency explicit, we define the function FIX: - Xnz + R= that maps an input æ and an initial guess for the fixed point 2o to an output that satisfies the fixed point equation FIX,,, f.. (I, zo) ;= fw FIX,, (æz, zo)). The behaviour of FIX depends on the solver that's used to find fixed points.
The most straightforward approach to solve for fixed- points is the fixed point iteration method, which recursively applies the function fw on the internal representations x (i.e. ž(+1 fw,(x, 21)). If certain conditions are satisfied (such as the fixed iterations being globally contractive more general conditions are discussed below), this procedure converges' to a fixed point: z" = fw(2r >*). As solving for fixed points exactly is expensive, fixed point iterations are often terminated after fixed number of steps or when the norm of the difference between subsequent iterates falls below a pre- selected threshold. The model weights can be updated using gradients computed via backpropagating through the full forward computational graph.
If one commits to using fixed point iterations as the root solver, then the output x" of equilib- rium models can be interpreted as the infinite-depth limit of an input-injected, weight- sied model f (ax ==) = -im f (xx, zo) where the notation f(r) stands for n repeated applications of f on its own output, and Zo stands for the fixed point initialization.
Implicit Training of Equilibrium Models Different training algorithms for equilibrium models can be derived by considering their implicit nature. Bai et al. [2019] solve for fixed points explicitly using black-box root finders, such as Broyden's 's method [Broyden, 1965] or Anderson acceleration [Anderson, 1965]. In order to avoid explicitly differentiating through the root-finding procedure, they utilize implicit differentiation to compute gradients.* 4 Concretely, letting Iw (z, x) = fw (x, x) = for fixed point 2", the Jacobian of z with respect to the equilibrium model weights can be given by:
dz = - dw
-- (0) (ar, =²)
-1 0. (xc, =*)
Oz
Inverting a Jacobian matrix can become computationally expensive. Recent works [Geng et al., 202 la, Fung et al., 2021] have shown that the inverse-Jacobian term in Bq. (1) can be replaced with an identity matrix i.e. Jacobian-free or an approximate inverse-Jacobian [Geng et al., 2021b] without affecting the final performance. This approximation makes the backward pass inexpensive and lightweight. Equilibrium models have been shown to achieve state-of- the-tr performance on various tasks including language modelling [Bai et al., 2019], image recognition, semantic segmentation [Bai et al., 2020], object detection [Wang et al., 2020], and graph modeling [Gu et al., 2020, Liu et al., 2021a].
Equilibrium Models vs. Depthwise Recurrent Models Both equilibrium models and input-injected depthwise recurrent (i.e. weight-tied, fixed-depth) networks leverage weight-tying i.e. they apply the same transformation at each layer, fud fw Vi. The two models differ in the ultimate aim of the forward pass: while depthwise recurrent models compute a (weight-tied) -ied) fixed depth computation (which may or may not approach a fixed point), the stated goal of equilibrium models is explicitly to find a fixed point. Weight- tied fixed depth networks by definition require backpropagation through an explicit stack of layers. Equilibrium models, however, directly solve for fixed points using (potentially black-box solvers during the forward pass and may be trained using implicit differentiation.
Convergence As alluded above, in order to guarantee convergence to a unique fixed point, it suffices for the cell of the equilibrium model to be contractive over its input domain' (i.e. the singular values of its Jacobian all lie below 1). Previous work has leveraged I Lipschitz constrained cells to ensure contractivity [Revay et al., 2020]. Other approaches for ensuring global convergence exist: the monotone equilibrium model architecture guarantees global convergence by utilizing an equilibrium model parametrization that bears similarities to solutions to a particular form of monotone operator
Divergence is also a possible outcome, rendering the output of equilibrium models unusable. "Bai al. [2019] use the term Deep Equilibrium Models (DEQ) to refer implicitly trained equilibrium models. To keep things more general, we categorize "explicitly trained" networks (i.e. with fixed point iterations and backpropagation) under the umbrella of equilibrium models as well. 'This is known as the Banach fixed- exed-point theorem.
3

---

The term splitting problem [Winston and Kolter, 2020]. Unrestricted equilibrium models aren't 't constrained enough guarantee convergence: they can easily express globally divergent vector fields that prohibit the existence of fixed points. It is, therefore, interesting that they can (and often) learn path independent solutions. Also note that the "infinite-depth weight tied network" interpretation of equilibrium models is less general than the implicit formulation presented above, as the latter admits unstable fixed points as well.
Terminology and Abbreviations We use the term "equilibrium models" to refer to the general class of networks that explicitly solve for fixed point in the forward pass. We use the term 'solver' refer to the use of black-box box root finders like Anderson acceleration to find fixed points of an implicitly trained equilibrium model. These networks can use implicit gradients computed via implicit function theorem (IFT), Jacobian- backward pass, or with an approximation of inverse- 'unroll' refers to equílibrium models that use regular fixed-point iterations to compute the equilibrium point. We use the abbreviation 'bp' to refer to backpropagation gradients, and 'inj" to refer to input injection. The term pprorressive net' refers to the deep thinking networks trained with progressive training as proposed by Bansal et al. [2022]. We use 'PI' and 'non-PI' to refer to path independent and path dependent networks, respectively.
Upwards Generalization with Equilibrium Models
In this section, we establish that equilibrium models are capable of strong upwards generalization. To study the effects of test time computation, it is useful to consider tasks with an explicit difficulty parameter, so that the learned models can be tested on more difficult instances which require large number of iterations to solve correctly. We focus on multiple algorithmic generalization tasks: prefix sum and mazes by Sehwarzschild et al. [2021a,b], blurry MNIST, matrix inversion and edge copy by Du et al. [2022]. Taken together, these tasks cover wide range of problems from different domains, namely sequence prediction, visual reasoning, image classification, continuous optimization and graph regression. To maintain clarity and focus, we run our detailed analysis on the prefix sum and mazes tasks, and provide complementary results for the remaining tasks in the Supplementary Material (SM).
Tasks Prefix-sum is a gepuencc-to-sequeeee bits, and is trained to output, for each bit, the parity of all of the bits received since the beginning of the sequence until the current bit. We train on 10,000 unique 32-bit binary strings, and report results on binary strings of other lengths. The mazes task is also an image-to-imag task, where the input is a three-channe RGB image. The 'start' and 'finish' positions are marked by red and a green square respectively; walls are marked in black. The output the optimal path in the maze that connects these two points without passing through the walls. We train on 50,000 small mazes of size 9 x 9, and report upward generalization results on larger mazes. Instances of each of these problems, as well as additional image classification and continuous optimization results can be found in the supplementary material. Blurry MNIST [Liang et al.] is a robustness-to-corrpppi to-coruptioonn task: one has to learn to do MNIST classification from lightly blurred images and generalize zero-shot to highly blurred ones. In the matrix inversion task [Du et al., 2022], the goal is to learn to invert 10 x 10 matrices in a way that generalizes to matrices that have worse condition number than those observed during training. Edge copy [Du et al., 2022] is a simple graph regression tasks that requires learning to output the input edge features, in a way that generalizes to larger graph sizes. Note that the training and test data in the latter two tasks are generated with noise added on- the-hhf-fy, as done by Du et al. [2022].
task whereby the network is given sequence of 0-1
Strong Upward Generalization Fig. 2a shows that equilibrium models demonstrate very strong upward generalization performance compared to non weight-tied fixed-depth models. Moreover, Fig. 2b shows that increasing inference depth consistently improves performance perfommnce--espciilly on harder problem instances.
Path Independence
Having intuitively motivated the idea of path independence in Sec. 1, we now define it formally: we say that the computation performed by a recurrent operator computing function fw on an input æ path independent if it converges to the same limiting behavior regardless of the current state 2,. As special case, if the computation is convergent, this property is equivalent to the existence of unique fixed point zn such that f (ar, 20) = z" for any 2p. However, our definition allows for other behaviors such as limit cycles (see See. 7).

---

OOD Generalization on Mazes
Accuracy curves by Pl Score
1.0
0.999
Path Independence Score
Bit-wise accuracy
0.9
0.9
Accuracy
solver + Ift
0.8
0.25
progressive
0.7
non-weight tied no
0.01
0.6
1e-05
0.5
9 13
25 31
59
100
200
300
400
500
Dimension Maze
Iteration
(a)
(b)
Figure 2: (left) Strong upward generalization on mazes by PI models. Models were trained on 9 x sized mazes and tested for upward generalization on larger mazes. y-axis uses probit transformation. (right) PI models better able make use of additional test-time computation. We trained models with varying number of training-time iterations, learning rate and weight norm application. Bit-wise accuracies are evaluated and averaged over different string-lengths.
Some architectures guarantee the path independence property (see Sec. 2). However, most common DEQ architectures-and the ones we use throughout this paper-have the expressive power to learn multiple fixed points per input. Since it is unclear whether architectures enforcing the contraction property lose expressiveness [Bai et al., 2021], we focus our investigation on unrestricted architectures.
Pl networks represent a different model for computation than standard red--forwrrd networks: instead of learning entire computational graph to map inputs to outputs, they only have to learn where to stop. We dedicate the rest of the paper on exploring the Path Independence Hypothesis- the idea that models which successfully fit the training distribution with path independent function better able to exploit more test-time iterations to achieve higher accuracy, compared to those which fit the training distribution with a path-dependent function.
Before establishing a connection between path independence and out-of-distribution generalization, first describe two architectural components that necessary conditions for achieving path independence. Afterward, we describe a metric to quantify how path-independens a trained network is.
4.1 Architectural Components Necessary for Path Independence
Past work has observed that weight lying and inpul injection are both crucial for upwards generaliza- tion [Bansal et al., 2022]. We observe that both architectural components are also necessary for a learned model to be PI. Without weight tying, the network is constrained have fixed forward depth, so it is meaningless to talk about the limiting behavior in large depth. Input injection ensures that the equilibrium point depends on the input despite having an "infinite depth". Without input injection, a PI network would necessarily forget the input; hence, any model which successfully fits the training distribution must be path dependent.
Interestingly, both architectural motifs are also key components of deep equilibrium models [Bai al., 2019]; in that work, the motivation function theorem (IFT) - a concept closely related to path independence, since the premise of the IFT gradient estimator is that only the final hidden state matters, the path taken to get there. It striking that two separate lines of work would converge on the same architectural motifs, one motivated by generalization and the other by variant of path independence.
to enable efficient gradient estimation via the implicit
Reproducing the results of Bansal al. [2022], in Fig. 2a we show upward generalization performance using both equilibrium models and progressive nets [Bansal et al., 2022] and the lack thereof using non-input-injected networks. For the remainder of this paper, we focus on architectures with both input injection and weight tying.
*Our definition also admits non-ing con-input-ijjeed models to be path independent if they re representing constant functions (i.e. input independent). We don't consider such cases in analyses.
5

---

Algorithm
Asymptotic Alignment Score
Path Independence Interventions
Input:
A batched input
operator fw
22
0.98
Initialize:
22
Define:
h(y1, 3/2)
1/
V/ 2
Accuracy
1///
ll
2
0.5
Compute
FLX fm
[ 22
Z1
# Interchange and reinitialize iterates
0.02
baseline mixed init random
Compute
FLX,5
22
allinment penalty
return averago(h (M =1),
Init random depth
0.25
0.5
0.99 Path Independence Score
0.75
Figure 3: (left) AA Score Algorithm: We provide the algorithm for simple illustrative case of two inputs. In practice, we consider larger batches. (right) Promoting path independence improves generalization in the prefix sum task: Interventions that are designed to promote path independence (initializing fixed points with random noise or running the fixed point solver with stochastic budget) improves generalization. Conversely, those that hurt path independence (penalty term that directly penalizes fixed point alignment) leads to poorer generalization.
4.2 Quantifying Path Independence
We propose simple metric quantify path independence based on the directional alignment of the fixed points computed with the same input, but different initializations. We name this metric the Asymptotic Alignment (AA) score. Pseudocode compute the metric is given in Alg. 1. The AA score is the average cosine similarity between the fixed points obtained with the training time initialization (often simply the zero vector) and the fixed points obtained when one initializes the solver using the fixed points computed on different inputs. Higher AA scores (with being the highest value) imply higher degrees of path independence. In Sec. we show strong correlation between path independence and accuracy using the AA score.
The AA score is cheap to compute, is reliable indicator of path independence (see below), and is unitless, meaning that networks obtained from different training runs can be compared on equal footing. See the supplementary material for other metrics we've considered for quantifying path independence and why we found AA score to be preferable.
Stress-testing the AA score To stress-test the extent to which the AA score really measures path independence, we search for adversarial initializations that are optimized to result distinct fixed points, hence low AA values. (Unlike adversarial examples, this attack is not constrained to an e-ball.) We use the L--FGS [Liu and Nocedal, 1989] optimizer, and repeat the search multiple times starting from different fixed point initializations. We include pseudocode in the supplementary material.
Results of the adversarial stress test can be seen in Tab. The results corroborate that the AA score is indeed a reliable measure of path independence; while isn't It possible to find adversarial initializations for high AA score networks (indicating high path independence), low AA score networks can easily be adversarially initialized to be steered away from the original fixed point estimate.
Path Independence Correlates with Upward Generalization
Is path independence (as measured by the AA score) strong predictor of upwards generalization? We took the trained networks from See. 3, computed their average AA scores on in- and out-of- distribution splits and inspected whether the AA scores are correlated with upward generalization.

---

Model
Task
AA
Accuracy (%)
Attacked AA 1
Attacked Acc. (%)
Non-PI network
Maze
0.32
87.12
0.09
Pl network
Maze
1.00
100
1.00
100
Non-PI network
Prefix sum
0.62
66.66
0.18
Pl network
Prefix sum
0.99
100
0.99
100
Table Stress-testing the AA Scores: AA scores for vs non-PI networks computed on 13 13 mazes and 64 bit prefix sum. Attacked AA refers to the cosine similarity between the fixed point from zero initialization and an adversarial initialization. Non-PI networks can easily steered away from the initial fixed point estimate through adversarial initializations but it is difficult to do so for PI networks with high AA scores.
Prefix Sum
Mazes
broyden
unroll bр wnorm unroll ift
0.99
progressive net wnorm
0.99
unroll (shallow) + hp wnorm
unroll bp unroll ift
Accuracy
0.93
Accuracy
progressive net
0.9
unroll (challow) bp feedforward
feodforward Injection
0.5
0.5
unroll backprop
0.07
unroll IFT
anderson + IFT
0.25 0.5
0.9
0.99 0.999
0.15
0.75
0.99
Path Independence Score
Path Independence Score
(a) Prefix Sum
(b) Mazes
Figure 4: High AA architecture and a task, the reported numbers are averaged over problem instances of different dimensions. We apply the probit transformation along both axes, following Miller et al. [2021]. Accuracies and AA scores are capped at 0.999 for compatibility with the probit transform.
correlate with good upward generalization. For a given choice of an
On prefix sum experiments, we varied 1) network depth, 2) whether or not weight norm (wnorm) [Salimans and Kingma, 2016] used not," learning rate (one of [0.01, 0.001, 0.0001]), 4) forward solver (fixed point iterations or Anderson acceleration [Anderson, 1965], and 5) the gradient estimator (backprop or implicit gradients). On the maze experiments, varied 1) network depth, 2) use of weight norm, 3) forward solver (fixed point iterations or Broyden solver [Broyden, 1965]), and 5) the gradient estimator (backprop or implicit gradients).
Fig. displays our findings. We evaluated performance on a mixture of in- and OOD validation data; results individual data splits be found in the supplementary material. The results show a strong correlation between AA score and accuracy when the inference depth large enough. This shows that PI networks allow for scaling test-time compute to improve test-time accuracy (see also Fig. 2b). The in-distribution validation performance non-PI networks degrades with deeper in- ference depths. Unsurprisingly, these networks generalize poorly harder problem instances that require deeper inference depths (i.e. problem instances that provably require at least given number of layers handle). Further results the BlurryMNIST, matrix inversion and edge copy tasks be found in Supplementary Material H. and J.
Bai [2019] report that weight norm helps stabilize training of DEQ models.
"Note that the deep equilibrium model (DEQ) setup [Bai et al., 2019] correspond to using a root solver (such Anderson) for the forward pass and implicit gradients for the backward pass.
7

---

Experimental Manipulations of Path Independence
The previous section demonstrates a strong correlation between path independence and the ability to exploit additional test-time iterations. Unfortunately, we can't 't make a causal claim based on these studies: the observed effect could have been due to unobserved confounder. In this section, we in- tervene directly on path independence by imposing regularizers which directly encourage or penalize path independence. We find that interventions designed to promote path independence also improve generalization, while interventions designed to reduce path independence also hurt generalization.
6.1 Promoting Path Independence via Randomized Forward Passes
A straightforward way encourage path independence is simply initialize the hidden states with random noise during training. To this end, we experimented with initializing the hidden states with zeros on half of the examples in the batch, and with standard Gaussian noise on the rest of the examples. The reason to include the zero-initializations at training time is that we initialize from zeros at test time- not including this initialization during traning time causes distribution shift.
Another way to promote path independence is simply running the forward solver with randomized compute budgets/depths during training time. While path independent solution can be expected to be robust against this intervention, a path dependent one will fail.
We took the training configurations of the 12 prefix-sum networks described in Sec. 5 that use fixed point iterations in their forward pass, and backpropagation gradient their backward pass, and retrained them separately with the aforementioned mixed initialization and randomized depth strategies without modifying any other experimental conditions. As can be seen in Fig. 3, the interventions lead to strong test-time path independent neural networks, while also reliably improving in- and out-of-distribution validation accuracy. We especially emphasize that shallow networks trained with mixed initialization actually remain far from having high AA scores using the training- time forward pass conditions due to lack of convergence. However, since the mixed initialization strategy results in path independent networks, scaling up test-time compute budget leads to high AA scores, and therefore high upwards generalization.
6.2 Penalizing Path Independence via the Fixed Point Alignment Penalty
Does an intervention that results in less path independence also result in poorer upwards general- ization? Like in the mixed initialization experiment, we retrained the 12 unroll + backpropagation networks with additional auxiliary loss term that penalizes the dot product between the fixed points computed from the same input, but different initializations sampled from standard Gaussian noise. Fig. 3 shows that this intervention succeeded in pushing the AA scores down, while also keeping the accuracy on the same trend line.
Disambiguating Convergence and Path Independence
Is convergence necessary for path independence? We answer this statement in the negative, and show that neither training-time convergence nor test-time convergence is required for path independence. Instead convergence to the same limiting behavior regardless of initialization is important.
Training Time Convergence We consider two implicitly trained equilibrium models trained on the mazes task-ant trained with implicit gradients computed via implicit function theorem (IFT), and the other trained with an approximation of the (inverse) Jacobian, called phantom gradients [Geng et al., 2021b]. We report the values of residuals (i.e., fl (x, x) = l|]2), AA scores and accuracies observed for in- and -o------diriiutiionnnnn data for mazes Tab. 2. We observe that DEQs trained with phantom gradients have higher values of in-distribution residuals but are path independent, as indicated by their high AA scores, and show strong upward generalization as indicated by their good accuracy.
The innttaliiiiiiiiniionn intervention described in Sec. 6.1 also leads to separation between training- time convergence and path independence. We found that it is possible to train very shallow (i.e., layer) unrolled networks that, while being very far from converging during training and attaining poor in-distribution generalization, are able to converge and achieve perfect performance when run for many more iterations during test time. Details are provided in the supplementary material.

---

Residual 4
AA score
Accuracy (%) 1
Model
In-dist
OOD
In-dist
OOD
In-dist
OOD
DEQ (phantom grad.)
11.83
0.016
0.96
0.99
99.96
99.88
DEQ (IFT)
1.4
0.011
0.99
0.99
99.99
100
Table 2: Training-ting time convergence is not needed for path independence: models might show poor training-time convergence (as shown by high values of residuals) but still be path independent. Residual, AA score, and Accuracy for DEQ trained with IFT vs phantom gradients. In-distribution (In-dist) results were computed
9 mazes, and OOD results were computed on 25 25 mazes.
Residuals steps 13x13
Instance Path Independence vs. Correctness
correct predictions
Food Puine
3000
2500
Example Count
10
Reaiduals
2000
1500
10
500
50
100
150
200
0.2
0.4
0.6
1.0
Stepa
Path Independence Score
(b)
Figure 5: (Left) Different solvers display differing asymptotic behaviours but still achieve good upwards generalization. Here, the network has an adversarial AA score of 0.99, and achieves accuracy of 99.98% (fixed point iterations) and 99.97% (Broyden solver) respectively on the mazes task; (Right) Per-instance path independence is highly correlated with correctness of predictions for prefix sum task.
Test Time Convergence From Tab, 2, one might conclude that test time convergence is important for path independence. However, show that this connection is not necessary, and convergence the same fixed point is not a required condition for path independence. We study test time convergence properties of an unrolled weight-tied input-injected network trained with backpropagation under different solvers. This network highly path independent using either the Broyden solver or fixed point iterations, as indicated by its high AA scores (0.99) on both in- and out-of-distribution data. We visualize the values of test-time residuals with fixed point iterations and Broyden's 's method in Fig. 5a. Both these solvers converge different limit cycles but still show good upward generalization.
Path Independence on a Per-Example Level
The connection between path independence and prediction correctness also largely holds on a per- instance basis. Using the prefix-sum networks trained with the mixod-initialization strategy (the most performant group of networks our intervention experiments). we plotted the distribution of per-instance fixed point alignment scores, colored by whether the prediction on that instance rect or not Figure 5b. This suggests that path independence can used as valuable sanity-check to determine whether prediction is correct not without the need for any label data, both in- and out-of-distribution. We provide a more in-depth per-instance analysis in the supplementary material.
9 Related Work
There is long line of research on neural networks that can adapt their computational budget based on the complexity of the task they are learning to solve-akin to the intrinsic mechanism humans to reason and solve problems. Schmidhuber [2012] introduced self-delimiting neural networks which

---

are a type of recurrent neural networks (RNNs) that adapt their compute based on the output of special "halt" neuron. Adaptive computation time (ACT) [Graves, 2016a] also uses the output of a sigmoidal halting unit to determine the termination condition of an RNN, but it avoids long "thinking" time by explicitly penalizing it. Subsequent works have successfully applied variants of ACT in image classification and object detection [Figurnov et al., 2017], visual reasoning [Eyzaguirre and Soto, 2020]. Transformers [Vaswani et al., 2017] for language modelling [Dehghani et al., 2019, Elbayad et al., 2020a, Liu et al., 202 and recognizing textual entailment [Neumann et al., 2016]. PonderNet [Banino et al., 2021] [] reformulates the halting policy of ACT as a probabilistic model, and adds regularization term in the loss objective encourage exploration. With these additions, PonderNet can extrapolate to more difficult examples on the parity task, first proposed by Graves [2016b]: in vector with entries of O, -1, and output for odd number of ones, and 0 otherwise. In this work, we do not optimize or penalize the network for the number of computational steps. Our main goal is understand the underlying mechanism that results in scalable generalization of equilibrium models on harder problem instances. Our current work is closely related to previous work by Schwarzschild et al. [2021b] and [Bansal et al., 2022] that propose architectural choices and training mechanisms that enable weight tied networks to generalize on harder problem instances. We relate these papers' contributions to ours in Section 4.1.
Another family of models with the property of adaptive inference compute budget is early exit networks [Teerapitaaannon et al., 2016, Laskaridis et al., 2021]. These networks have multiple additional "exit" prediction heads along their depth. At inference time, the result that satisfies an exit policy is selected as the prediction output. This approach of designing adaptive networks has been adapted both in natural language processing [Schwartz. et al., 2020, Soldaini and Moschitti, 2020, Elbayad et al., 2020b, Zhou et al., 2020, Liu et al., 2020] and vision [Li et al., 2017, Wang et al., 2018, 88, Xing et al., 2020, Kouris et al., 2021]. Most of these architectures have complex sub-modules that are trained in multiple stages, and require complex exit policies. In contrast, equilibrium models have simple architecture, and can use root solvers to efficiently solve for the fixed point at inference.
More complex transformer-based language models like GPT-3 also struggle to generalize well on simple algorithmic tasks like addition [Brown et al., 2020]. Recent work by Nye et al. [2021] shows that transformers can be trained to perform well algorithmic tasks and generalize on OOD data by emitting the intermediate steps of an algorithm to a buffer called "scratchpad". Using a scratchpad enables the model to revisit its errors and correct them.
Path independence is closely related to the concept of global stability and global convergence in control theory and optimization. This concept is somewhat overloaded, as it sometimes requires convergence to a single point [Slotine et al., 1991] I]. and sometimes implies the system convergent everywhere, even if to different points [Wang et al., 2003, Sriperumbudur and Lanckriet, 2009]. We thus choose the term path independence to refer specifically to the fact that the system will converge to the same limiting behavior (whatever that might be) regardless of the initial state of the system.
10 Conclusion
Being able to attain better levels of performance using a larger inference-time compute budget is a feat that eludes most standard deep learning architectures. This is especially relevant for tasks that require upwards generalization, ie., the ability to generalize from easy problem instances to hard ones. We show that equilibrium models are capable of displaying upwards generalization by exploiting scalable test-time compute. We link this to a phenomenon we call path independence: the tendency of an equilibrium network to converge to the same limiting behavior given an input, regardless of the initial conditions. We investigate this phenomenon through careful experiments and verify that path independent networks indeed generalize well on harder problem instances by exploiting more test time compute. Moreover, interventions on training conditions that promote path independence also improve upwards generalization, while those that penalize hurt this capability. Our findings suggest that path independent equilibrium models are promising direction towards building general purpose learning systems whose test-time performance improves with more compute.
10

---

11 Acknowledgements
AP is supported by grant from the Bosch Center for Artificial Intelligence. JT acknowledges support from the Center on Long-Term Risk Fund. CA is supported by NSERC Canada Graduate School Doc- torate scholarship.
References
Donald G Anderson. Iterative procedures for nonlinear integral equations. Journal of the ACM (JACM), 12(4))547-560, 1965. (Cited on 3, 7)
Jimmy Lei Ba, Jamie Ryan Kiros, and Geoffrey Hinton. Layer normalization. arXiv preprint arXiv: 1607.06400 2016. (Cited on 15, 27, 28)
Shaojie Bai, J. Zico Kolter, and Vladlen Koltun. Deep equilibrium models. In Neural Information Processing Systems, 2019. (Cited on 2, 7,
Shaojie Bai, Vladlen Koltun, and Zico Kolter. Multiscale deep equilibrium models. In Neural
Information Processing Systems, 2020. (Cited on 3)
Shaojie Bai, Vladlen Koltun, and J. Zico Kolter. Stabilizing equilibrium models by jacobian regular- ization. In ICML, 2021. (Cited on 5)
Andrea Banino, Jan Balaguer, and Charles Blundell. Pondernet: Learning ponder. arXiv preprint arXiv:2107.05407, 2021. (Cited on 10)
Arpit Bansal, Avi Schwarzschild, Fitan Borgnia, Zeyad Emam, Furong Huang, Micah Goldblum, and Tom Goldstein. End-to-end algorithm synthesis with recurrent networks: Logical extrapolation without overthinking. arXiv preprint arXiv:2202.05820. 2022. (Cited on 1, 4, 5, 10, 17, 18)
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D) Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models few-shot learners. Advances in neural information processing systems, 13:1877-1901, 2020. (Cited on 10)
Charles G Broyden. A class of methods for solving nonlinear simultaneous equations. Mathematics of Computation, 1965. (Cited on 3, 7, 18, 20)
Mostafa Dehghani, Stephan Gouws, Oriol Vinyals, Jakob Uszkoreit, and Lukasz Kaiser. Universal transformers. 2019. URL https://openreeveww newt/edttidii net./ppff.dd--Hyad...8..... (Cited 10)
Yilun Du, Shuang Li, Joshua Tenenbaum, and Igor Mordatch. Learning iterative reasoning through energy minimization. In International Conference on Machine Learning, pages 5570-5582. PMLR, 2022. (Cited 4, 27, 28)
Maha Elbayad, Jiatao Gu, Edouard Grave, and Michael Auli. Depth-adaptive transformer. In International Conference on Learning Representations, 2020a. URL https: //operree//pe..ieer. (Cited on 10)
Maha Elbayad, Jiatao Gu, Edouard Grave, and Michael Auli. Depth-adaptive transformer. ArXiv, htts/1900.1073... 2020b. (Cited on 10)
Cristobal Eyzaguirre and Alvaro Soto. Differentiable adaptive computation time for visual reasoning. In Proceedings of the ieeelcvf conference computer vision and pattern recognition, pages 12817- 12825, 2020. (Cited on 10)
Michael Figurnov, Maxwell Collins, Yukun Zhu, Li Zhang, Jonathan Huang, Dmitry Vetrov, and Ruslan Salakhutdinov. Spatially adaptive computation time for residual networks. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 1039-1048, 2017. (Cited on 10)
Samy Wu Fung, Howard Heaton, Qiuwei Li, Daniel McKenzie, Stanley Osher, and Wotao Yin. Fixed point networks: Implicit depth models with jacobian-fres free backprop. arXiv e-prints, pages arXiv- 2103, 2021. (Cited on 3)
11

---

Zhengyang Geng, Meng- Hao Guo, Hongxu Chen, Xia Li, Ke Wei, and Zhouchen Lin. Is attention better than matrix decomposition? In International Conference on Learning Representations (ICI.R), 2021a. (Cited on 3)
Zhengyang Geng, Xin- Yu Zhang, Shaojie Bai, Yisen Wang, and Zhouchen Lin. On training implicit models. Advances in Neural Information Processing Systems, 34, 2021b. (Cited on 3, 8) 0.988,
Alex Graves. Adaptive computation time for recurrent neural networks. CoRR, 2016a. URL http: /arxiv. org/abs/1003 08983. (Cited on 10)
Alex Graves. Adaptive computation time for recurrent neural networks. 1603.0000088833 2016b. (Cited on 10)
arXiv preprint
Fangda Gu, Heng Chang, Wenwu Zhu, Somayeh Sojoudi, and Laurent El Ghaoui. Implicit graph neural networks. Advances in Neural Information Processing Systems, 33:11984 1188-1199999 2020. (Cited on 3)
Weihua Hu, Bowen Liu, Joseph Gomes, Marinka Zitmik, Percy Liang, Vijay Pande, and Jure Leskovec. Strategies for pre-training graph neural networks. arXiv preprint arXiv: 2019. (Cited on 29)
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint 1rXiv:1412.6980 2014. (Cited on 17, 18)
Pang Wei Koh, Shiori Sagawa, Henrik Marklund, Sang Michael Xie, Marvin Zhang, Akshay Bal- subramani, Weihua Hu, Michihiro Yasunaga, Richard Lanas Phillips, Irena Gao, et al. Wilds: benchmark of in-the-wild distribution shifts. In International Conference on Machine Learning, pages 5637-5664. PMLR, 2021. (Cited on 1)
Zico Kolter, David Duvenaud, and Matthew Johnson. Tutorial: Deep implicit layers-neural odes, deep equilibirum models, and beyond, 2020. (Cited on 17, 20)
Alexandros Kouris, Stylianos I Venieris, Stefanos Laskaridis, and Nicholas D Lane. Multi-exit semantic segmentation networks. arXiv preprint arXiv:2106.03522 2021. (Cited on 10)
Stefanos Laskaridis, Alexandros Kouris, and Nicholas D Lane. Adaptive inference through early-exit networks: Design, challenges and directions. In Proceedings of the 5th International Workshop on Embedded and Mobile Deep Learning, pages 1-6, 2021. (Cited on 10)
Xiaoxiao Li, Ziwei Liu, Ping Luo, Chen Change Loy, and Xiaoou Tang. Not all pixels are equal: Difficulty-wware semantic segmentation via deep layer cascade. In Proceedings of the IEFE conference on computer vision and pattern recognition, pages 3193-3202, 2017. (Cited on 10)
Kaiqu Liang, Cem Anil, Yuhuai Wu, and Roger Grosse, Out-of-distriiuttin generalization with deep equilibrium models. Uncertainty and Robustness in Deep Learning, ICML 2021. (Cited on 4, 25)
Renjie Liao, Yuwen Xiong, Ethan Fetaya, Lisa Zhang, KiJung Yoon, Xaq Pitkow, Raquel Urtasun, and Richard Zemel. Reviving and improving recurrent prooppropagation. In International Conference on Machine Learning, pages 3082-3091. PMLR, 2018. (Cited on 2)
Dong C Liu and Jorge Nocedal. On the limited memory bfgs method for large scale optimization. Mathematical programming, 55())50335528, 1989. (Cited on 6, 18, 19)
Juncheng Liu, Kenji Kawaguchi, Bryan Hooi, Yiwei Wang, and X. Xiao. Eignn: Efficient infinite- depth graph neural networks. In NewrIPS, 2021a. (Cited on 3)
Weijie Liu, Peng Zhou, Zhe Zhao, Zhiruo Wang, Haotang Deng, and Qi Ju. Fastbert: a self-distillngg bert with adaptive inference time. arXiv preprint wxXiv:2004002174 2020. (Cited on 10)
Yijin Liu, Fandong Meng, Jie Zhou, Yufeng Chen, and Jinan Xu. Faster depth-adaptive transformers. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 13424-13432, 2021b. (Cited on 10)
James McClelland and David Rumelhart. Explorations paraltel distributed processing: handbook of models, programs, and exercises. MIT press, 1989. (Cited on 2)
12

---

John P Miller, Rohan Taori, Aditi Raghunathan, Shiori Sagawa, Pang Wei Koh, Vaishaal Shankar, Percy Liang, Yair Carmon, and Ludwig Schmidt. Accuracy on the line: on the strong correlation between out-of-distribution and in-distribution generalization. In International Conference on Machine Learning, pages 7721-7735. PMLR, 2021. (Cited on 7)
Mark Neumann, Pontus Stenetorp, and Sebastian Riedel. Learning to reason with adaptive computa- tion, arXiv preprint arXiv: 1610.07647, 2016. (Cited on 10)
Maxwell Nye, Anders Johan Andreassen, Guy Gur-Ari, Henryk Michalewski, Jacob Austin, David Bieber, David Dohan, Aitor Lewkowyez, Maarten Bosma, David Luan, al. Show your work: Scratchpads for intermediate computation with language models. arXiv preprint arXiv:2112.00114, 2021. (Cited on 1, 10)
Max Revay, Ruigang Wang, and Ian R Manchester. Lipschitz bounded equilibrium networks. arXiv:2010.01732, 2020. (Cited on 3)
Tim Salimans and Diederik P. Kingma. Weight normalization: A simple reparameterization to accelerate training of deep neural networks. CoRR, abs/1602.07868, 2016. URL http:://axiit org/abs/1602 07868. (Cited 7, 17, 18, 19, 20)
Jürgen Schmidhuber. Self-delimiting neural networks. arXiv preprint arXiv:1210.0118, 2012. (Cited
9)
Roy Schwartz, Gabriel Stanovsky, Swabha Swayamdipta, Jesse Dodge, and Noah A Smith. The right tool for the job: Matching model and instance complexities. arXiv preprint arXiv:200.004453, 2020. (Cited on 10)
Avi Schwarzschild, Eitan Borgnia, Arjun Gupta, Arpit Bansal, Zeyad Emam, Furong Huang, Micah Goldblum, and Tom Goldstein. Datasets for studying generalization from easy to hard examples. arXiv preprini arXiv:2108 11X0:2008..0011,, 2021a. (Cited on 4, 17, 18)
Avi Schwarzschild, Eitan Borgnia, Arjun Gupta, Furong Huang, Uzi Vishkin, Micah Goldblum, and Tom Goldstein. Can you learn an algorithm? generalizing from easy hard problems with recurrent networks. Advances in Neural Information Processing Systems, 34, 2021b. (Cited on I, 4, 10, 19)
Daniel Selsam, Matthew Lamm, Benedikt Bünz, Percy Liang, Leonardo de Moura, and David Dill. Learning a sat solver from single-bit supervision. arXiv preprint arXiv:1802.03699 2018. (Cited on 1)
Jean-Jacques E Slotine, Weiping Li, et al. Applied nonlinear control, volume 199, Prentice hall Englewood Cliffs, NJ, 1991. (Cited on 10)
Luca Soldaini and Alessandro Moschitti. The cascade transformer: an application for efficient answer sentence selection. CoRR, fals/2005.02534 2020. URL petttps://artii ptrg/abs//000 02534. (Cited on 10)
Bharath K Sriperumbudur and Gert RG Lanckriet. On the convergence of the concave-convex procedure. In Nips, volume 9, pages 1759-1767. Citeseer, 2009. (Cited on 10)
Surat Teerapittayanon, Bradley McDanel, and Hsiang- Tsung Kung. Branchynet: Fast inference via early exiting from deep neural networks. In 2016 23rd International Conference on Pattern Recognition (ICPR), pages 2464 2469. IEEE, 2016. (Cited on 10)
Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Lukasz Kaiser, and Illia Polosukhin. Attention is all you need. Neural Information Processing Systems, 2017. (Cited on 3, 10)
Qing-Guo Wang, Tong Heng Lee, and Chong Lin. Global stability of limit cycles. In Relay Feedback, pages 57-83. Springer, 2003. (Cited on 10)
Tiancai Wang, Xiangyu Zhang, and Jian Sun. Implicit feature pyramid network for object detection. arXiv preprint arXh::2012.13562 2020. (Cited on 3)
13

---

Xin Wang, Fisher Yu, Zi-Yi Dou, Trevor Darrell, and Joseph E Gonzalez. Skipnet: Learning dynamic routing convolutional networks, In Proceedings of the European Conference Computer Vision (ECCV), pages 409-424, 2018. (Cited on 10)
Ezra Winston and J Zico Kolter. Monotone operator equilibrium networks. arXiv preprint arXiv:2006.08591, 2020. (Cited on 4)
Yuxin Wu and Kaiming He. Group normalization. In Proceedings of the European conference on computer vision (ECCV), pages 3 19, 2018. (Cited on 18)
Qunliang Xing, Mai Xu, Tianyi Li, and Zhenyu Guan. Early exit or not: Resource-efficient blind quality enhancement for compressed images. In European Conference on Computer Vision, pages 275-292. Springer, 2020. (Cited on 10)
Wangchunshu Zhou, Canwen Xu, Tao Ge, Julian McAuley, Xu, and Furu Wei. Bert loses patience: Fast and robust inference with early exit. Advances in Neural Information Processing Systems, 33: 18330-1834 18341, 2020. (Cited 10)
14


Reviews:
[{"review_id": "cYf9xCaEnSD", "reviewer": "Reviewer_hf7z", "summary": "This paper studies the path independence of equilibrium models, which refers to the fact that a system will converge to the same limiting behavior regardless of the initial state. It hypothesizes that the path independence strongly correlates with generalization performance on harder examples, and then it experimentally verifies the hypothesizes. This paper also introduces a metric for measuring the path independence of a learned model, called FPA score. It also experimentally verifies that FPA strongly correlates with model accuracy on out-of-distribution samples.", "questions": "1. In Sec 4.1, the paper says, weight tying and input injection are both necessary for a learned model to be PI. However, according to the definition of path independence in L36-38:\nWe thus choose the term path independence to refer specifically to the fact that the system will converge to the same limiting behavior (\\textbf{whatever that might be}) regardless of the initial state of the system. \n\nPI doesn't need the limiting behavior to be meaningful. Without input injection, the limiting output would be a representation independent of the input, but it still satisfies the definition of path independence. As a result, I don't agree with the statement.\n\n2. Wrong references: (L93-95) Recent works [Geng et al., 2021a,b, Fung et al., 2021] have shown that the inverse-Jacobian term in Eq. (1) can be replaced with an identity matrix without affecting the final performance of DEQs.\n\nWhat the author describes is the work of Fung et al., not of Geng et al., 2021a,b. Geng et al., 2021b uses unrolling-based estimates of the inverse-Jacobian as a replacement, not an identity matrix. And I am a little confused why the author cites Geng et al., 2021a here. ", "limitations": "No.\n\nThe author writes: (L727-737 in the Appendix) While the necessity of additional test-time compute is obvious for prefix sum and mazes, it’s less clear for perception-like tasks like image classification.\nIn my opinion, the stopping criterion used by DEQ itself is a signal to measure the necessity. To be specific, DEQ sets a stopping tolerance, once the error/relative error goes below it, the solver stops iterating. Maybe the iteration step taken by the solver can be used to decide if additional test-time computation is needed. ", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n1. Adaptive computational budget is an interesting problem and worth studying. \n\nWeaknesses:\nMy main concerns about this paper concentrate on the paper writing. I have difficulty understating the following points: \n\n1. Algorithm 1 doesn't coincide with the language description. There is neither a fixed point equation nor a root-solving process. \nAlso, since FPA seems to be a random metric, can the author show the variance introduced by different inputs?\n\n2. In Figure 5 (a), where is the comparison between different solvers? Does unroll mean fixed point iteration?\n\n3. L143-144, However, our definition allows for other behaviors such as limit cycles (see Section 7).\nHowever, when I turn to Sec. 7, I don't find anything related to other behaviors except convergence to a fixed point. \n\n4. I cannot understand what this means: \n(L34-36) However, the term “global stability” is slightly overloaded, as it sometimes refers to the actual convergence, sometimes requires convergence to a single point, and sometimes just implies the system is convergent everywhere, even if to different points. \n\nCould you please explain what the three cases refer to?\n\n5. I cannot understand the caption of Figure 2: \nBlue and grey dotted lines indicate in-distribution data and harder problem instances, respectively.\nThen why do they fill 0 to 1 ?\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "acoQhVPJODk", "reviewer": "Reviewer_VRFp", "summary": "This submission hypothesizes that there is a strong correlation between generalization and the so-called path independence (PI)--essentially positing that the state given the input and weights should be ``stable''. The authors make three major contributions:\n\n1. They show that PI networks (typically deep equilibrium models) exhibit better upwards generalization when compared to non-PI models.\n2. They propose a simple-to-compute metric, called the Fixed Point Alignment (FPA) score, to measure the level of path independence. They further demonstrate that FPA is highly correlated with upwards generalization.\n3. To further test the validity of the path independence hypothesis, the authors design an experiment to adversarially intervene the training of PI models, and show that FPA is a robust metric for path independence.", "questions": "1. As alluded to above, do these PI models generalize as well if they are challenged with a task with, say, only 90% baseline accuracy?\n\n2. Although the authors argue that there is no need for convergence in Section 7, I find it contradictory with the proposed FPA, which is clearly a measure of convergence. If, say, the model converges to a limit cycle, how does FPA detect it? ", "limitations": "A major limitation of the submission is that the authors focus exclusively on the PI hypothesis for deep equilibrium models. However, PI is a quite general statement and, if true, should hold for non-deep equilibrium models as well. Figuring out a framework to incorporate the non-deep equilibrium models thus presents an interesting direction.", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "In my opinion, this is a well-written paper with clear contributions. The authors have clearly laid out the thesis and nicely demonstrated the empirical evidence. The proposed FPA is intuitive and easy to compute, which might present an interesting metric to practitioners.\n\nOn the other hand, as a purely empirical work, I feel like we need more extensive experiments to conclude the validity of the proposals. The authors chose a benchmark dataset by Schwarzschild et al, which seems relatively easy and hence does not suffice to substantiate the PI hypothesis. In particular, it seems easy to get to essentially perfect accuracy on the proposed tasks, which poses the question that if these PI models would generalize as well if they are challenged with a task with, say, only 90% baseline accuracy?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "VqG__tPmOW5", "reviewer": "Reviewer_4wU9", "summary": "This paper proposes the concept of 'path independence'. It proposes FPA score to measure the 'path independence' of a network, and shows that the FPA score is correlated with the upward generalization ability of equilibrium networks. The claims are supported by experimental results.", "questions": "1. Please correct me if there is any misunderstanding, but I do not understand the meaning of involving $x_2,z_2,z_2'$ in Algorithm 1. It seems to me that the algorithm only needs $z_1'$ in the followed steps, and the computation of $z_1'$ is not affected by $x_2,z_2$.\n2. To show that FPA score is a valid measure for path independence, the authors compare the FPA and attacked FPA in table 1. However, this result is not promising enough. First, this table only shows two cases (PI and non-PI), but FPA score is a continuous measure. Two instances cannot show whether the FPA score is a valid measure as a continuous number. Second, for the non-PI network, the gap between the FPA score and attacked FPA score is large. Such a large gap makes it even harder to see how good FPA is as a measure for path independence. Especially, for non-PI networks, what does it mean if one has a higher FPA score than another? It is important to explain this.\n3. In Figure 7 (b), the figure also indicates that when FPA score is less than 1, the correctness of the non-PI network is NOT always positively correlated with the FPA score.\n4. Figure 7 (a) shows the residuals given by the two different solvers are different. However, this number is not rigorous enough to support the show that different solvers converge to different fixed points. It is better to directly compute the RELATIVE difference between the solutions given by two different solvers. Besides, to claim that this network is path independent, it will be more promising to show that its ATTACKED FPA score is close to 1, instead of the non-attached FPA score.", "limitations": " ", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\n1. The paper is easy to follow and clear.\n2. The phenomenon is interesting. The problem setting is potentially useful in practice.\n\nWeakness:\n\n1. All the claims are only supported by experiments, without any theoretical justifications.\n2. The experiments are not rigorous enough.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "AE565YlhMdj", "reviewer": "Reviewer_nzeU", "summary": "Deep equilibrium models (DEQs) are built from layers that solve fixed point equations. Two interesting features of DEQs are:\n(1) Layers of DEQs in their most general form may have no solutions, a unique solution, many solutions, countably infinitely solutions, or uncountable infinitely many solutions, and (2) test-time computational budget may be chosen in a DEQ by trading off accuracy versus budget in the fixed point solver. \n\nThe authors empirically find that a certain measure of path independence (how independent the output of a DEQ layer is of initialisation) correlates well with the ability of the DEQ to utilise an increased test-time budget for benefit. ", "questions": "- I do not understand FPA. Can you help me understand Algorithm 1? Let me summarise my understanding:\n    1. Do one pass through f with an initial state z=0 for two different inputs, x1 and x2. This gives z1' and z2' respectively.\n    2. Compute a second pass for (x1, z1'), giving z2''.\n    3. Compute the cosine similarity between z2'' and z1'.\nAccording to the notation used, no fixed points of any function are ever actually computed in Algorithm 1. As far as I can tell, z2' is never used, and z2 is only used to compute z2'? Perhaps my confusion is related to the comment \"Interchange and reinitialize fixed points\". \n- After clarifying my understanding of FPA, can you explain why this is a useful measure? \n- What is the motivation for seeking adversarial examples in the z-space? Does this represent a trimmed-down real life scenario? I can't imagine an adversary ever having access to the initial state of the fixed point solver.\n- The first sentence in line 250. Why is this true? Won't the learned networks depend on the random initialisation? I don't think this statement is true in general. A counter-example is if the network is a contraction, then under mild conditions a reasonable fixed point solver (e.g. forward iteration) will converge to the unique equilibrium. So the network's output will not depend on the initialisation.\n- Figure 7 caption and legend. What does \"Fixed point solver\" mean? Is this naive fixed point iteration? What does \"residuals\" mean? The equation on line 296 is not easy to read. previously f had two arguments, z and x. Here it only has one argument? Does this maybe mean ||f (x, z) - z||_2, which would indicate how close we are to a fixed point? Then is it true to say that if the residual is not close to zero, a fixed point has not been obtained? Then the first sentence of the caption in figure 7 is misleading, because in the case of naive fixed point iteration, a fixed point was not found?", "limitations": "The techniques discussed here are suitably general and do not have an application in mind.", "rating": 4, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- It is unknown how the number of solutions that a DEQ layer admits interacts with the performance of a system. It is also unknown how to make best use of the fact that DEQs have a test-time computational budget. It is great to see research that attempts to show that path independent networks generalise well when they are able to exploit more computational budget at test time.\n- I like the idea of the interventions performed in section 6. The execution is mostly great too, conditioned on some of my concerns detailed in the weaknesses and questions.\n\nWeaknesses\n- I did not enjoy the discussion about the fixed point iteration method at the start of section 2. The authors describe the fixed point iteration method, but not conditions under which it converges to a fixed point. More worrying is the implicit language which seems to say that it does converge to a fixed point (.e.g until it converges to a fixed point). A mention of contraction properties or Banach's fixed point theorem would be nice here, if fixed point iteration is to be discussed. This is later mentioned in footnote 2.\n    - The weight tying view (mentioned around line 100 and elsewhere) is only valid if the DEQ can be interpreted as an infinite depth network. A sufficient condition is contraction/Banach's fixed point theorem, but in general, a fixed point condition cannot be interpreted as an infinite depth network with weight tying. Other works talk about other sufficient conditions.\n- I do not understand the motivation for algorithm 1, nor do I see how it is a relevant metric. See Questions below.\n- There is limited discussion and no mathematical theory about *why* the Path Independence Hypothesis might be true and how FPA relates to the hypothesis.\n- I have several other concerns (which may be more to do with clarity than actual technical issues), detailed in questions below. If these are technical issues, they are in my opinion very significant ones. If they are clarity issues, then they are still significant and need to be addressed before this work is suitable for publication.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept