Rethinking Deep Thinking: Stable Learning of Algorithms using Lipschitz Constraints
Authors: Jay Bear
Adam Prugel-Bennett
Jonathon Hare
Venue: NeurIPS 2024 poster (2024)
Keywords: machine learning
iterative algorithms
deep thinking
lipschitz
traveling salesperson problem
contraction mapping
Primary area: deep_learning_architectures
TL;DR: Training machines to learn algorithms that are guaranteed to converge to a solution

Abstract: Iterative algorithms solve problems by taking steps until a solution is reached. Models in the form of Deep Thinking (DT) networks have been demonstrated to learn iterative algorithms in a way that can scale to different sized problems at inference time using recurrent computation and convolutions. However, they are often unstable during training, and have no guarantees of convergence/termination at the solution. This paper addresses the problem of instability by analyzing the growth in intermediate representations, allowing us to build models (referred to as Deep Thinking with Lipschitz Constraints (DT-L)) with many fewer parameters and providing more reliable solutions. Additionally our DT-L formulation provides guarantees of convergence of the learned iterative procedure to a unique solution at inference time. We demonstrate DT-L is capable of robustly learning algorithms which extrapolate to harder problems than in the training set. We benchmark on the traveling salesperson problem to evaluate the capabilities of the modified system in an NP-hard problem where DT fails to learn.

Rethinking Deep Thinking: Stable Learning of Algorithms using Lipschitz Constraints
Jay Bear
Jonathon Hare The University of Southampton, Southampton, UK ajdh1g19,abp1, jsh2) @soton. ac uk
Adam Prügel-Bennett
Abstract
Iterative algorithms solve problems by taking steps until solution is reached. Models in the form of Deep Thinking (DT) networks have been demonstrated to learn iterative algorithms inference time using recurrent computation and convolutions. However, they are often unstable during training, and have no guarantees of convergencellermintiion at the solution. This paper addresses the problem of instability by analyzing the growth in intermediate representations, allowing us build models (referred to as Deep Thinking with Lipschitz Constraints (DT-L)) with many fewer parameters and providing more reliable solutions. Additionally our DT-L formulation provides guarantees of convergence of the learned iterative procedure to unique solution at inference time. We demonstrate DT-L capable of robustly learning algorithms which extrapolate to harder problems than in the training set. We benchmark on the traveling salesperson problem to evaluate the capabilities of the modified system NP-hard problem where DT fails to learn.
way that can scale to different sized problems
Introduction
Iteration is key ingredient in vast number of important algorithms. Incremental progress towards a solution is demonstrated many of these. Well-known examples include insertion sort, gradient descent, and the simplex method. This paper explores models that learn iterative algorithms. We ask questions including: Can deep learning models be used to learn the complex steps of algorithms similar to these? Is there way guarantee solution approximation is reached? Can learn algorithms that extrapolate to larger or harder instances than we train on? In addressing these questions propose model called Deep Thinking with Lipschitz Constraints (DT-L..
Φ (m+
Φ (0)
F
s (m)
(M)
2
H
y
Figure 1: Recurrent-based model architectures for learning algorithms with input and output y- F. G and H are convolutional networks that work on any size input. A scratchpad Φ serves as the working memory during computation. As described in Section the original DT model didn't include recall, denoted by the dotted line. The improved DT-R and our DT-L model include this connection.
Some work towards answering the above questions has occurred recent years. A key approach has been to utilize various forms of a leamned recurrent function to implement 'step' in an iterative algorithm that computes solution to problem. Typically these recurrent functions are combined
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

with learned functions that pre-process the initial input, and post-process the output of the last iteration into the final solution form. Examples of such approaches are the Deep Thinking (DT) networks [18] and Deep Thinking with Recall (DT-R) networks [2] that we build upon in this work (see Figure 1).
There are two key features these models: firstly the use of iteratively updated scratchpad, &b serving as a working memory; and secondly, the construction of the model from convolutional layers enable it scale to arbitrary sized problems. The latter is important because in principle allows training on smaller problems, and then extrapolation at inference time to larger problems [2, 18].
Many challenges still remain with the existing DT and DT-R approaches however, and we aim to address these in this work. Firstly, DT-st networks are quite difficult to train and can be very unstable both during training and inference. The DT-style networks previously demonstrated in the literature are massively overparameterized - we show in Section 3 that model width is inversely related to training stability in existing models, and later demonstrate how this can be addressed (see Section 4). Secondly, existing approaches have no guarantees on the convergence of the learned algorithm: this important because if solution a problem exists, one would hope that an algorithm to solve it would terminate or reach a stable state once the solution has been reached. Section 4 details design approach guarantee convergence within the limits of floating point precision by considering the network in terms of a discrete dynamical system. Our contributions are:
We systematically analyze DT networks and explore why they can be unstable;
we introduce techniques grounded in theory into the DT framework which improve the stability of learning and guarantee convergence at run time. This allows the use of much smaller models to tackle the same problems, and improves extrapolation performance;
we propose our Deep Thinking with Lipschitz Constraints (DT-L) model and perform a comprehensive evaluation and ablation study; and,
show that the approach can be applied to learn to find low-cost tours for range of TSPs, including non- -u--uclidean and asymmetric instances.
2
Related work
Deep Thinking (DT) networks [18] were designed to learn algorithms by using recurrence to induce iterative behavior in such way they could be trained on smaller and simpler examples before extrapolating to larger tests. The networks were used to solve 'Easy-to-Hard problems (consisting of prefix sums, mazes, and chess puzzles [17]) and they could be trained with few iterations on easy problems in such a way that they can solve harder problems by increasing the number of iterations.
DT networks were further improved by Bansal et al. [2] by means of adding 'recall' (which we refer to as DT-R networks) - a mechanism for the recurrent component to have continuous access to the original input. Recall successfully allowed DT-R networks to solve much larger tests than DT networks without recall, while also mitigating overthinking, where if after too many iterations at inference time the predicted solution becomes progressively worse. In addition to recall, Bansal et al. introduced incremental progress training (IPT), a training method which disables gradient tracking for a random number of initial iterations. This prevents the model from learning behaviors based strictly on the number of iterations and instead promotes incremental modification to the internal states.
There exist alternative approaches to producing machines which can learn algorithms. One set of models are Neural Turing Machines (NTMs), which use attention in recurrent system for reading to, and writing from, some external memory [6]. NTMs showed success in learning cell-based copying and repeating tasks which could be applied to unseen inputs. Differentiable Neural Computers (DNCs) operate similarly to NTMs, differing primarily in their method of external memory access [7]. In the NTM, like most RNNs, the amount of compute is directly tied to the input sequence length. Graves [5] proposed a method to adaptively select the compute budget in RNNs. The models studied here are different in the sense that the objective is to extrapolate beyond the training data to harder problem instances as the compute budget is increased, and the input and output is not a sequence.
A second class of models exist where a specific base iterative algorithm is defined, and the parameters of the algorithm, or the problem, are learned. Examples include the reverse diffusion process learned in diffusion models [9], and models which involve optimization using gradient descent iterations

---

within the forward pass to generate an output with certain properties that are difficult to produce directly with neural network, such as permutation equivariance [21]. Our work does not constrain the class of algorithm used directly, other than enforcing that we learn an iterative one.
3 Analysis of Deep Thinking Networks
The main architecture used in pre-existing Deep Thinking networks [2, 18], and our own network, is shown in Figure 1. It takes an input problem instance and generates solution y. The model consists of three convolutional networks F, G and H. The function F responsible for initially pre-processing the input æ into the initial state (0;; function G is the recurrent function that takes the current state, ((m) (plus the original input x in the case of DT-R and our models), produce the next state, cf(m+1), The final state produced by G, after M iterations, denoted ()(M), The function H takes (bM) and produces the predicted output y. Formally
( F(x).
(1)
Φ (m++1) 9 ( .x) Vm E {O..... 10.....M.. M-1] 1}
(2)
y H H(b(()))).
Architecturally these networks are recurrent neural networks. Unlike more commonly used recurrent networks such as LSTMs they are not used to tackle problems with sequential data, but rather the recurrent part used to find a solution through an iterative process. The algorithu that the recurrent network uses, as well as the pre- and post- processing functions are learned through supervised training on example input-solution pairs for a particular problem.
As the networks F, G and H are convolutional neural networks they can work with an arbitrary size input. The solution y is typically the same size as the input æ. The feature of DT and DT-R that excited interest was that, not only could they solve unseen problem instances of the same size as they were trained on (which we call interpolation), but when trained on small problem instances (with relatively small M), they were able to find low cost solutions on much larger problem instances (which we refer to as extrapolation) by increasing M at inference time. Both DT and DTTR suffer from poor stability both in training but particularly at inference time when extrapolating to larger problems. This often lead to overflow errors. This was particularly seen the number of channels in network G is reduced, then DT and DT-R are hard to train with many runs failing to find a solution. We show the reason for this is that there no mechanism to control the change size of the scratchpad representation, (m)) (/ leading to this either overflowing or vanishing during learning.
3.1 Training Stability
In this section we focus on DT-R as this is more stable than the original DT network. We use the spectral norm of the reshaped weights of convolution to capture the expansion or shrinkage in magnitude of the output relative to the input of a sub-network, with a value of meaning that the
Density
0.4
Layer
1
0.2
2
3
0.0
4
0.5
1.0
1.5
2.0
2.5
Spectral Norm
Figure 2: Distribution of spectral norms of reshaped weight matrices for the different convolutional layers in the recurrent part of DT-R. 30 prfix-suum-solingg models with width w 32 were sampled.
Given a convolutional layer with weights shaped (Cout, Con, n),, where n is the number of elements (e.g. the kernel height times width in 2D convolution) we can flatten the weights into a matrix of shape Cous x Can ne; the spectral norm is the largest singular value of this matrix.
3

---

1.00
1.00
1.00
Training Loss
Training Loss
Training
0.50
0.50
0.50
0.00
0.00
0.00
100
150
50
100
150
50
100
150
Epoch
Epoch
Epoch
W 16
64
256
Figure 3: Mean training (cross-entropy) loss each epoch for prefix-sums--olving models of varying width w. For small w training is stable, but not all models converge; larger w has higher chance of models reaching small loss, but the training process has very large spikes in the loss which causes some models to explode. Each curve is measured from different random initialization of the model throughout training, for 10 models of each width
magnitude is constant. In Figure 2, the four convolutional layers that arise after training DT-R on the prefix-sun problem (see Section for description of the problem). We observe that the spectral norms typically greater than one, which can lead to the norm of (fm) growing with each iteration. In turn this can cause the model to overflow when applying the model to a larger input (the extrapolation scenario), where we increase the iteration number M in order to solve the larger instance size. The DT models as described and implemented by Bansal et al. [2] have training behavior which becomes increasingly unpredictable the width w (number of channels in the scratchpad) is reduced. This can be in Figure where the variation in training loss at the end of training over different runs larger in models of smaller width. It is also worth noting that increasing the width result in explosive behavior in loss, including not-a-number (NaN) results, which can be seen in Figure D4.
violin plots to show the distribution of spectral norms for
3.2 Extrapolation Performance
The property of the DT networks that excited our interest was their ability to solve large instances than they were trained (that is, their extrapolative ability). This generalization -ut----distiobution examples is a key challenge for many machine learning algorithms. However, although DTT- can find models that extrapolate, very often the models that are trained extrapolate poorly. We observe models trained on few recurrences may have explosive behavior which only becomes a problem with extrapolative tasks requiring more recurrences.
Both DT and DT-R network used no bias terms in their model [2, 18]. In experimenting with these networks. found that adding bias made these models very unstable. Unfortunately. having biases exacerbates the 'dead cell problem', where some of the convolutional filters would have zero response to all training inputs.
Refinement of the Architecture: Deep Thinking with Lipschitz Constraints
In the previous section we have identified problem faced by DT-R, namely that there is instability in reaching solution through the iteration in Equation (2). To overcome this difficulty we use well known property contraction maps. c - V is mapping of objects, v and w, in a normed vector space V. that is contractive in the sense that
[(((v) c(w))l ||0 w/ll
implying c(-) a Lipschitz function with Lipschitz constant < 1, then the iterations
(m) (m
will converge to a unique solution as a consequence of the Banach fixed-point theorem [1, We can
use this to refine DT-R by engineering the network G(+, x) to be a contraction mapping. Noting that Equation (2) the input is held constant throughout the iteration, we construct ((,, a:) so that has an approximate Lipschitz constant K less than 1.

---

Although any Lipschitz constant less than 1 would guarantee convergence, the nature of the problem solving mechanism we seek learn intuitively means that we do not want fast convergence. This is because the network 9 performs local convolutions with limited receptive field. However, finding good quality solutions often requires a global knowledge. To accumulate such knowledge requires long distance information to accumulate in the scratchpad vector of ((m) over multiple iterations. To allow this to happen we choose the approximate Lipschitz constant associated with & to be less than, but close to
4.1 Constraining the Lipschitz Constant
The primary tool we use to control the Lipschitz constant of G(,, xx) ) is spectral normalization [15]. This is extension of spectral norm regularization, introduced by Yoshida and Miyato [20], but sets the spectral norm of an operator to fixed value rather than penalizing the norm of an operator that differs from predefined value. The method uses a power iteration compute approximation of the spectral norm of an operator, updated after each gradient step. Computation of the spectral norm is costly operation, but it only has to be done at the beginning of the iterative process.
As network G consists of convolutions we divide each convolution kernel weight by the spectral norm plus small constant to ensure the spectral norm is less than one; there is one exception in that the convolution applied to the recall connection æ does not need normalizing - please see Appendix B for full details. In addition to using the spectral norm need make sure all the other transformations carried out by 9 are at most I-Lipschitz. However, to avoid applying constraints to the constant recall connection, concatenation (<)(m) az] with two separate convolutional layers on ((m) and æ respectively whose output combined by element- wise addition. See Appendix A for a rigorous discussion on how the Lipschitz behaviour require is ensured.
replace DT-R's ss method of applying single convolution the
Constraining Activation Functions. To guarantee convergence under the constraints provided, any activation function used in G must be I-Lipschitz. This includes Rectified Linear Units (ReLUs), Exponential Linear Units (ELUs) [4], and tanh, but excludes Gaussian Error Linear Units (GELUs) [8], which have an absolute gradient greater than I around x = V2. Results in the body of this paper use the ELU activation for DT-L networks and the ReLU for DTTR as originally defined. Additional results using ReLU for DT-L and ELU for DT-R can found in Appendix D.2.
Constraining Residual Skip Connections. DT and DT-R use element wessent-wise addition for residual Y applied the
connections recurrent blocks. The sum of two functions e X Y and same input, with Lipschitz constants Ke and Ka respectively results in the upper bound,
[[((zz)) d(x1)) (c(x2) d(xx)))l < (K. Ka)l x22
(6)
for all 21.022 E X. In the case of a standard residual connection, one function is the identity (id(x) = x) and the other is the block of layers B contained in the span of the residual connection. Under our constraints, the identity is 1-Lipschitz and the block of layers Kg-Lipschitz, where Kg E [0, 1). This results in Lipschitz upper bound for the output of + Kg.
As result, residual connections addition between the identity and block of layers increase the Lipschitz constant of the recurrent part even if the layers themselves are I-Lipschitz. A solution to this, which also allows more expression in the model, is make each residual connection parametric linear interpolation between the identity output and the block output
(1 7) id( + + B(r),
E 10
DT-L applics this interpolation to each channel, individually; unconstrained learnable parameter T. exists for each channel in each residual connection, then the residual parameters are set to
Ya a (Tc) where is the logistic function to ensure that 0 v % < 1.
4.2 Additional Modifications
The above changes leads to more stable network, allowing us to make additional modifications and still obtain convergent behaviour with improved performance. Without explicitly controlling the Lipschitz constant, these changes often lead to complete failure of the network to solve the problem. In our final model design apply three extra modifications that lead to consistent improvements:
5

---

1. Batch normalization layers [10] are added for the imput and after each convolution, except for layers in the recurrent block and the final output layer. Empirically this improves performance.
2. A bias term is added to the recall convolution (without the Lipschitz constraint) in G. The bias term is added the recall convolution mitigate the dead cell problem. Since this is a constant addition (along with recall) it does not disrupt the convergence constraints we have put in place (see Appendix A). bias term is also added the final (output) layer and, when batch normalization is not used, to FF.
3. Exponential Linear Unit (ELU) activations [4] are used instead of rectified linear unit (ReLU) activations. This choice is influenced by the desire promote activations staying close to zero [4] throughout iteration, as well as mitigating the effect of the dying ReLU problem [19] where 'dead' activations increase with depth [13]. Artificially deep models like DT are therefore likely to encounter this problem. Using ReLU can also result in rapid rate of convergence, preventing the model from learning complex algorithms for harder tasks (see Appendix D.2).
Our reasoning for not applying batch normalization in the recurrent block follows from Jastrzebski et al. [11] where unsharing batch normalization statisties was necessary to avoid activations exploding. In an architecture where the maximum number of iterations is unknown it appears infeasible to unshare batch normalization statistics for every iteration.
Using these modifications- creating a model we call Deep Thinking with Lipschitz Constraints (DT-L) - greatly improves the stability of training and using these networks. As we will see in Section 5, the new DT-L network allow us to solve the same problems explored by DT and DT-R, but using, in some cases, three orders of magnitude less parameters while achieving high performance and more consistent success rate during training. The increased reliability offered by DT-L allows us to explore many other modifications enabling us to tackle more sophisticated problems. We illustrate this by attempting to find good solutions to one of the most notoriously difficult problems, namely, the traveling salesperson problem (TSP).
5 Results on Easy-to-Hards Problems
In this section, we compare our model (DT-L) against DJT-R Note that DT-R is an improvement of DT by the same authors and has already been shown have better performance [2]. We test on the three problem classes used by Bansal et al. [2] to evaluate DT-R, namely a prefix sum problem, a maze problem and a chess problem.
We have trained and evaluated the models on a range of different Nvidia GPU accelerators from RTX2080Tis to A100s, well as on M3-series Apple Silicon. Memory usage is insignificant compared to available GPU memory. Training time is of the order of 30 minutes for the w = 32 model on the prefix-sum problem using single RTX8000. More details can be found in Appendix E, and code for the experiments can be found at https:// /ttp:///tthbbbbb// com Jay-Bear wethinking-ddeepthiiie
The accuracy given in this section measures the proportion of instances where the network produces the exact correct solution. Note that even if a predicted solution differs from the target by one element (e.g. 1 bit in prefix sums, pixel in mazes) it is considered a failure.
Prefix Sums. The prefix sum problem involves translating string of ones and zero to new string that counts sequences of ones (details are described by Bansal et al. [2]). The problem is simpler than the the maze and chess problem, and considerably faster to run. As consequence we choose this as the main problem to perform a comparative study.
In our experiments we compare the DT-R model to our DT-L model. Both were trained on instances consisting of 32 bits for a maximum of 30 iterations, using IPT with a 0.5. Both models have a width (number of channels) of w 32 (more details about architecture can be found in Appendix B. We found that for this problem there is little change in performance above w = 32 for DT-L. In Figure 4 we show the solution accuracy for 30 randomly-inittalized models of both DT-R and DT-L on the 512-bit test dataset versus the number of iterations (M) to generate those solutions. We measured the performance 10000 randomly generated instances of each problem. The error in

---

the mean is less than 0.5% which is approximately the width of the lines in the figure. As can be seen DT-R struggles consistently find networks that extrapolate to larger problem settings (it only obtains greater than 90% accuracy two out of 30 training runs). In contrast DT-L only fails to reach above 90% accuracy on two out 30 training runs.
100
100
Accuracy (%)
80
(%)
80
80
Accuracy
Model
40
40
40
DER
DEL
0
200
400
600
0
200 400
600 0
200
400
600
Test-Time Iterations (M)
Test-Time Iterations (M)
Test-Time Iterations (M)
DT-R (runs)
DT-L (runs)
Mean
Figure 4: Comparison between Deep Thinking with Recall and Deep Thinking with Lipschitz Constraints on the prefix sums problem. Two left plots show the solution accuracy of inference- time runs on 512-bit problems for 30 individual models each. Each line corresponds the performance of a network trained from scratch with different randomly initial weights. The accuracy is measured on 10000 problem instances. The right plot shows the mean of all 30 for each. Models have channel width of w 32. Shaded areas show 95% confidence intervals.
To emphasize DT-L's performance on smaller widths, we selected w = 32 as the primary width for comparison. We perform ablations on other aspects of the model in Appendix D.2.
Mazes. The mazes problem consists of drawing the correct path for a blank maze, given a starting point and an ending point. Details about the representation of mazes is given in Schwarzschild 17 mazes,
[17] and Bansal et al. [2]. Our tests are performed on models trained on extrapolated to 33 33 mazes. Results from multiple runs and an aggregate can be seen in Figure 5. The maze models defined by Bansal et al. [2] are trained on 9 x mazes. Attempting to train DT-L on mazes of this size resulted in the models often learning trivial solutions which did not extrapolate to larger mazes.
Chess Puzzles. The chess puzzles problem involves identifying the next best move of the current board state. Specifically, the model must learn to classify Is in two cells representing the piece to move and the location to move to, and Os elsewhere. The models are trained on train/validation split of the easiest 600,000 problems, where difficulty is based on Lichess.org rankings (see Schwarzschild et al. [17] for more detail).
This problem in particular can be viewed as different to both the prefix sums and mazes problems in that the difficulty of the problem doesn't 't come from the size. All chess puzzles in this dataset are standard 8 x 8 chess boards. For all tests on the chess dataset [17] we follow the same number of epochs as Bansal al. [2]. Results are shown in Figure 6. DT-L achieves very similar performance to DT-R, seemingly hitting the same apparent ceiling on performance discussed by Bansal et al. [2]. We would like to explore the reasons for this in more detail the future, but we note that at training time the models do not reach 100% accuracy, so it should not be surprise that they do not always extrapolate. possible that the issue arises from the structure of the data and the way interacts with the model architecture.
Benchmarking on Traveling Salesperson
To demonstrate the strength of DT-L. we have formulated the traveling salesperson problem as a differentiable optimization task for the model to solve. This is a significantly more challenging problem than those discussed Section 5. The problem instance æ is now the matrices of "distances" with additional information. For arbitrary distance matrices this is known to be NP-hard. An optimal solution corresponds to a tour (permutation of the cities) such that the sum of distances between neighboring cities is minimized, although we seek only to find low cost tour.
7

---

100
100
100
Accuracy
Model
DER
DEL
0 100
200
300
0
100
200
300
0
100
200
300
Test-Time Iterations (M)
Test-Time Iterations
Test-Time Iterations (M)
DT-R (runs)
DT-L (runs)
Mean
Figure Comparison between Deep Thinking with Recall and Deep Thinking with Lipschitz Constraints on the mazes problem for small models. Two left plots show the solution accuracy of inference- time runs on 33 33 mazes for 14 different models each. The right plot shows the mean of all 14 for each. Models have a channel width of w 32. Shaded areas show 95% confidence intervals.
100
Accuracy (%)
80
Accuracy (%)
80
60
Model
Model
DT-R
DT-R
20
DT-L
20
DT-L
0
50
100
150
0
50
100
150
Test-Time Iterations (M)
Test-Time Iterations (M)
64
16
Figure 6: Comparison between Deep Thinking with Recall and Deep Thinking with Lipschitz Constraints on the chess puzzles problem on models of two different widths, showing the mean accuracy of inference-time runs problems ranked in increasing difficulty between 1,000,000 and 1,100,000. Aggregate of six models, each trained on the easiest 600,000 problems, where shaded areas show 95% confidence intervals.
The solution vector is binary matrix with Is corresponding to the edges that are used in the tour. We constructed the network so that the solution vector would correspond to feasible solution. Unfortunately, in doing involves intermediate representation where the evaluation of the cost is non-trivial, which made the problem of learning an iterative solution very challenging. this, we increased the expressiveness of the scratchpad vectors (f() learn orthogonal transforms that it applied to a part of the scratchpad vector. This considerably improved the performance of the network. Details of the modification used are given Appendix B.I.
overcome
6.1 TSP Results
In Table give the mean tour length for randomly generated instances from two class of problems: symmetric random tours and asymmetric random tours. The DT-L models were trained for each problem class tours of size set of tours on the same size problems) and extrapolative results where we test of problems of size 30 with M 120. For comparison we provide the length random tours, the length of tours generated by the greedy nearest neighbor (NN) algorithm, and the length of tours from a modified version of the NN algorithm which selects the lowest-cost NN tour of all starting points instead of starting from a random point (BNN).
15 with M 45. We show both interpolative results (using new
The results in Table 1 show DT-L's is ability to learn non-trivial algorithms by performing considerably better than random tours. That the results are worse than the nearest neighbor methods should not be surprising, in the asymmetric non-Fuclidean
these amongst the best known algorithms.
The models take approximately hours to train on an RTX2080Ti GPU for 80,000 batches of 64 randomly generated TSPs for both symmetric and asymmetric settings with 15 and M 45.

---

Testing was performed on M3 Apple Silicon with MPS acceleration and takes 3.59ms per n = 15 problem instance for M 45 and 23ms per n 30 problem with M 120.
Table 1: Results for TSP runs on symmetric and asymmetric instances. The results are the mean for 12,800 random instances. For DT-I., M = 45 was used for problem size n = 15 and M 120 for n = 30, where tour lengths are shown in column 2. Column 3 (Random Tours) gives the tour length for random tours, while columns and give the tour lengths for greedy nearest neighbor tours starting from a random point (NN) choosing the lowest NN tour from all starting points (BNN) respectively.
Problem
DT-L
Random Tours
NN Tours
BNN Tours
Symmetric n = 15
3.99 = 0.006
7.5 + 0.01
2.85 + 0.005
2.31 + 0.005
Symmetric n 30
6.02 + 0.007
15.0
3.50 + 0.005
2.72 + 0.004
Asymmetric n = 15
4.66 + 0.008
0.01
2.82 0.006
2.09 + 0.004
Asymmetric n 30
7.7 + 0.01
15.0
3.50 + 0.006
2.53 + 0.004
7 Discussion
Deep Thinking-style architectures provide a new paradigm for using machine learning for general problem solving. The key idea is use recurrent architecture to find solution through multiple iterations. This paper has addressed a major drawback of the published models which is the instability that frequently arises in the iteration steps. Having addressed these problems not only we able to obtain networks that much more reliably solve new problems, but we show that we can run much smaller networks with similar and often better performance. To illustrate the potential of this approach we have tackled notoriously difficult problem, namely TSP.
Deep Thinking approaches attractive because they learn general problem solving strategy that can be used to solve considerably larger instances of the problem than they were trained on. Extrapolation to problems outside the training dataset is an area where traditional machine learning struggles. Clearly, the problems these models extrapolate to are in the same problem class to the training data, but it is noteworthy that the strategies learned for the problem classes have investigated scale in this way. Another interesting feature is that the network learns the problem solving strategy through examples (in the case of TSP is not even shown any low cost solutions). Admittedly, for TSP we needed to construct a network that outputted tours and to get the quality of results we did we introduced a mechanism for learning orthogonal transformation which we then applied to part of the scratchpad vector. However, we did not build in any explicit rules for solving the TSP- so much so that we do not fully understand the algorithm DT-L uses to find low cost tours, particularly in the case of asymmetric non- Euclidean TSP.
Broader impact. Given the ubiquity of iterative algorithms in solving problems, having mech- anism to learn such algorithms opens up lot of possibilities. The advantage of using a recurrent mechanism over a feed-forward architecture that to solve a larger problem we simply needed to run the recurrent loop more often; this is often desirable in the real world because it might be impossible to train on sufficient data that you can guarantee not to need to extrapolate at inference time. Clearly, models of this kind have very many potential applications both in developing new (and potentially improved- - could we learn an algorithm that is significantly faster or more energy efficient than anything currently existing?) algorithms for existing problem classes where we already have solutions, as well as all areas of predictive modelling where we believe the input-output relationship is best captured through potentially-deep recurrent function. Inevitably, some of the potential uses also have the potential for misuse.
Limitations. This work shows theoretically and empirically that it is possible to modify an architec- ture learn recurrent functions with convergence guarantees. The problems we solve are relatively simple however. The performance we obtain, for example, on TSP is far from tate-of--hhe-art but we believe that the contribution is significant as we are able to find a heuristic algorithm running in M- = On log(n)) steps through trial and error, without any explicit inductive bias towards finding what we might consider to be a sensible algorithm. There are also clearly other potential issues with the approach; learnability is significantly improved over previous attempts, but there are still cases

---

where the model fails to learn. The use of convolutions means that the only way to capture long- oong-term (or large distance) dependencies in the data through iteration; this possibly a benefit, but other architectures with different structural biases might work better on certain problems. We believe, in terms of comparison NN and BNN heuristics, this local view of the distance matrix may contribute to the disappointing appearance of the results.
Outlook. This work leaves many open directions for future research. It would be interesting to explore different architectures, such Transformers, and more diverse problem settings. It would also be fascinating to better understand what algorithmss are learned by the model under different settings and whether for example the complexity of the learned algorithm can be controlled.
Acknowledgments and Disclosure of Funding
JB is funded by a Phl) studentship graciously provided by the School of Electronics and Computer Science. JH was supported by the Engineering and Physical Sciences Research Council (EPSRC) International Centre for Spatial Computational Learning [EP/S030069/1], The authors acknowledge the use of the IRIDIS High Performance Computing Facility, and the Southampton-Wo Wolfson AI Research Machine (SWARM) GPU cluster generously funded by the Wolfson Foundation, together with the associated support services at the University of Southampton in the completion of this work.
References
[1] Stefan Banach. Sur les opérations dans les ensembles abstratits et leur applications aux équations intégrales. Fundamenat Mathematicae, 1(3):133 181, 1922.
[2] Arpit Bansal, Avi Schwarzschild, Eitan Borgnia, Zeyad Emam, Furong Huang. Micah Goldblum, and Tom Goldstein. End-to-end algorithm synthesis with recurrent networks: Extrapolation without overthinking. In Koyejo, Mohamed, A. Agarwal, D. Belgrave, K. Cho, and A. Oh, editors, Advances in Neural Information Processing Systems, volume 35, pages 20232-20242. Curran Associates, Inc., 2022. URL https: http:opep//pprooeeddinggeeeeeeee newrips. wttppper.ccpppppppeeeeee hatpppppprrrleeeeeeeeeeeppaaaeee Paper-Coneerereeeeoeeoooooo .df.
Conf
[3] Krzysztof Ciesielski. On Stefan Banach and some of his results. Banach Journal of Math- ematical Analysis, 1(1):1 - 10, 2007. doi: 10.15352/6jm//1240225555 URL https:
//doi.orr/100 1ww.555/////a/222111
[4] Djork-Aréé Clevert, Thomas Unterthiner, and Sepp Hochreiter. Fast and Accurate Deep Network Learning by Exponential Linear Units (ELUss, 2016. URL https://arxiv.org//bbte absrr///ab//11... 07289.
[5] Alex Graves. Adaptive computation time for recurrent neural networks. CoRR, abs/ ab3/1663.,,883 2016. URL http:://rxii... org/ abaaaba//110 08983.
[6] Alex Graves, Greg Wayne, and Ivo Danihelka. Neural turing machines. CoRR, abs/ 1410.5401, 2014. URL http: http://v...g////////aaa/aasse/// 14110.4000
[7] Alex Graves, Greg Wayne, Malcolm Reynolds, Tim Harley, Ivo Danihelka, Agnieszka Grabska- Barwińska, Sergio Gómez Colmenarejo, Edward Grefenstette, Tiago Ramalho, John Agapiou, Adrià Puigdomênech Badia, Karl Moritz Hermann, Yori Zwols, Georg Ostrovski, Adam Cain, Helen King, Christopher Summerfield, Phil Blunsom, Koray Kavukcuoglu, and Demis Hassabis. Hybrid computing using neural network with dynamic external memory. Nature, 538(7626): 471-476, Oct 2016. ISSN 1476-4687. doi: 10. 10.00/// URL https://doi. org/ 10. w0000//aatre20111.1111.1
[8] Dan Hendrycks and Kevin Gimpel. Bridging nonlinearities and stochastic regularizers with gaussian error linear units. CoRR, Abs/1600.00815, 2016. URL http://arxiv. wrg.:.o.ggalloo /bs/s/ 1606. 08415.
[9] Jonathan Ho, Ajay Jain, and Pieter Abbeel. Denoising diffusion probabilistic models. In H. Larochelle, M. Ranzato, R. Hadsell, M.F. Balcan, and H. Lin, editors, Advances in
10

---

Neural Information Processing Systems, volume 33, pages 6840-6851. Curran Associates, Inc., 2020. URL /tLhtttpss///prroooddiggg/// http::///ppproooddnnnnoooopopppp nwwrips......... wc/paper_aaeeeeeeeeeeeeeeeeeeeee saaee__fllesppaper///000 /ppper/p020/ff1ll/ 4efbbceeeeB444f0066//11007000002 pdf..
[10] Sergey loffe and Christian Szegedy. Batch normalization: accelerating deep network training by reducing internal covariate shift. In Proceedings of the 32nd International Conference on International Conference on Machine Learning Volume 37, ICML' 15, page 448-456. JMLR.org, 2015.
[11] Stanistaw Jastrzebski, Devansh Arpit, Nicolas Ballas, Vikas Verma, Tong Che, and Yoshua Bengio. Residual connections encourage iterative inference. In International Conference on Learning Representations, 2018. URL bttttss:/oppnreviieee wwwpppewwwwwweee//eeeeeeeeeeeeee Stt.eeee...eeoooooooeeaaaaaaaaa
[12] Diederik Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference on Learning Representations (ICLR), San Diega, CA, USA, 2015.
[13] Lu Lu, Yeonjong Shin, Yanhui Su, and George Em Karniadakis. Dying ReLU and Initialization: Theory and Numerical Examples. Communicationn in Computational Physics, 2865):6671-1700 June 2020. ISSN 1991-7120 120.. doi: 10.4208/cicp.oo 77208/cccp.o222220-01655 2020-0165. URL http: doi org/ 10. 20044208ccicpp OA 2020-0165.
[14] Gonzalo Mena, David Belanger, Scott Linderman, and Jasper Snoek. Learning Latent Permuta- tions with Gumbel-Sinkhorn Networks. In International Conference on Learning Representa- fions, 2018. URL https: httttp:://pperrviieeee httpiiew.eeeeteeeeeeeeeeeeeeeeee wwt//eeeourrteee .ett:/toruummdddyyy3330-------
[15] Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. Spectral Normaliza- tion for Generative Adversarial Networks, In International Conference on Learning Represen- tations, 2018 URL https: http:p::///eeneevieeeeeeee/o/eoe 1i-1
[16] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Kopf, Edward Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style. high- performance deep learning library. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché- Buc, E. Fox, and R. Garnett, editors, Advances in Neural Information Processing Systems, vol- ume 32. Curran Associates, Inc., 2019. URL https: wew.isssser..... cc/paper_ Paper pdf.
files/ http:///ppppppg0..///////////2t1
[17] 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. CoRR, abs/2108.06011 2021. URL https: / //tpx/aaxivvv///////// org/ wrg//ba///0/000 abw//a//...../////////////a 06011.
[18] Avi Schwarzschild, Eitan Borgnia, Arjun Gupta, Furong Huang, Uzi Vishkin, Micah Goldblum, and Tom Goldstein. Can you learn an algorithm? generalizing from easy to hard problems with recurrent networks. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang, and Wortman Vaughan, editors, Advances in Neural Information Processing Systems, volume 34, pages 6695- 6706. Curran Associates, Inc., 2021. URL https: pttooeeee/poooeeeiiiggg neurips.cc/paper. Paper .df.
[19] Ludovic Trottier, Philippe Giguère, and Brahim Chaib-draa. Parametric Exponential Linear Unit for Deep Convolutional Neural Networks. CoRR, abs/1605.09332 2016. URL http:
//arxiv. perggabs//600/ 09332.
[20] Yuichi Yoshida and Takeru Miyato. Spectral Norm Regularization for Improving the Generaliz- ability of Deep Learning, 2017. URL https:://araat wwwriiiiiooggg//e org/ htsp//bs/1755 10941.
[21] Yan Zhang, Jonathon Hare, and Adam Prugel-Bennett. Deep set prediction networks. In
H. Wallach, H. Larochelle, A. Beygelzimer, d'Alché-Buc, E. Fox, and R. Garnett, edi- tors, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL https: iewproeeeeedinnnn..neeeeeeeee nwwrips.cc/ppnaeee ppaper_filees/ppprr//0// 67794
pdf.

---

A On Being Lipschitz
As discussed in the main paper one of its major contribution is the observation that by making O(-, x))
K K-Lipschitz with K < 1. then the iterative mapping defined in Equation (2) is guaranteed converge to unique solution as a consequence of the Banach fixed-point theorem [1]. To engineer G(,, x) to be K- K-Lipschitz we rely
few well known properties of functions. If X + Z is composition of two Lipschitz mappings A : X - Y and B Y + Z with Lipschitz constant A and KB then
[|C(2)) C(y) = [[((A())) B(A S KE [1A(()) A(v)l KA KB | yll-
(A1)
Thus a sufficient condition to ensure C K K-Lipschitz with < 1 that KA, KB < 1. This trivially generalises to any number of compositions.
In the network ( 2)) the input vector æ is added to & through convolution. However, adding an offset vector to a mapping does not affect the Lipschitz property as if A is K-Lipschitz and e is a constant vector, then the mapping ((xx) A(x) + e satisfies
(A2) Since during every iteration the input vector æ and the convolution filters remain unchanged, the addition of the input æ (which the Deep Thinking with Recall authors termed the recall) does not change the Lipschitz property of the network.
[B) B(y) || = || - A(v)l S K 1 yl
Finally, to ensure the Lipschitz behaviour of the convolutions we note that convolutions are equivalent to applying a matrix, C, to some vector, v.. For a matrix norm ||]] that is compatible with a vector norm ||=]|
||C ell $ |||||
||=|||
(A3)
where there exists a vector where the equality conditions holds. If N = ||C|| then, through the linearity of norms, D (K/N) C will have norm K/N so that the linear mapping D(x) D a is K K-Lipschitz since
K
K |C| x N
[D(x) (D())- |DD( - y)ll
C(( b)1l S N
yll
K x --ll
(A4)
This would be true for any normed vector space with an appropriate compatible matrix norm. In this paper we have used the Eg norm where the compatible matrix norm is the spectral norm (i.e. the largest singular value).
To allow the algorithm being run by network G to accumulate enough information to find a good solution we want the Lipschitz constant, K, of network G to be as close to as possible. the network can find good solution rapidly then it can find scratchpad vector Φ in region where the effective Lipschitz constant less than Indeed, we observed that despite Deep Thinking with Recall most often having Lipschitz constant greater than 1, nevertheless in the few runs where successful network was learned, the growth in the solution [| [mm]]] could be less than Being on the edge of the stable region seems be helpful for the network find good solutions
to hard problems. Consequently, in engineering the network G we attempt to make the Lipschitz
constant for most mapping layers as close to as possible.
B Architecture
In this section we describe the architecture of DT [17], DT-R [2] and our network DT-L. For DT and DT-R the architecture is identical to that described in the original paper. We include a description here to make the comparison with DT-L clearer. The number of channels of the input, æ. varies depending on the problem class. It is for prefix sums, 3 for mazes, 12 for chess and 3 for TSP. Following DT and DT-R, the output vector, y, has two channels. During training this is used to compute a categorical cross-entropy loss, while at inference time this is put into a max function to obtain a binary output.
In all models the convolutions are either 3 (for prefix sum) or x 3 with stride and padding In the figures below the boxes with rounded edges represent convolutions.
12

---

Deep Thinking, In Figure B1 we show the Deep Thinking (DT) model. Note in this case the imput vector a is not given to the network each iteration of g.
-----------------
-.0.0--0000
Figure B1: The DT architecture Schwarzschild et al. [18]. Arrows denote flow from one function to the next with recurrent iterations are denoted by the dashed arrow. Single-lined rounded rectangles denote regular convolutions. Activation functions in square boxes are ReLU.
Deep Thinking with Recall. In Figure B2 we show the architecture for the Deep Thinking with Recall (DT-R) model. In DT-R the network is fed æ every iteration and it is concatenated to the recurrent connection.
0..00-0
Figure B2: The DT-R architecture Bansal al. [2]. Arrows denote flow from one function to next with recurrent iterations are denoted by the dashed arrow. Single-lined rounded rectangles denote regular convolutions. The recall æ is concatenated (i) to the recurrent input. Activation functions in square boxes are ReLU by default, but we experiment with ELU in Appendix D.2.
Deep Thinking with Lipschitz Constraints. The architecture of our model, Deep Thinking with Lipschitz Constraints (DTL) is shown in Figure B3. The convolutions with spectral norms are shown in bold. Following common practice when working with models with skip connections we have also added batch norms (shown as solid black rectangles). These ensure that the tensors going through the network are normalized ensuring that their means are around zero where the non-linearity in the activation functions are strongest. Empirically this lead improved performance as shown by ablation studies.
10-00-0000000000 7 CI000000
Figure B3: Our basic DT-L architecture. Arrows denote flow from function to the next with recurrent iterations are denoted by the dashed arrow. Double-lined rounded rectangles denote convolutions with the Lipschitz constraint applied. Single-lined rounded rectangles regular convolutions. Solid black rectangles denote hatec-nnomatizztion operations. Activation functions ELU by default, but we experiment with ReLU in Appendix D.2. Plus symbols with small indicate weighted summation, with the residual weighted by 1 and main branch by (c.f. Equation (7)). Rather than concatenating the recall into the recurrent input we pre-process it with convolution and then sum with convolved version of the recurrent input.
B.1
TSP Model
Recall that in TSP the input vector æ corresponds to the matrices of distances? The solution y is binary matrix showing which edges we used in the tour. Thus, the cost of the full tour is sum(2 (x: @ y),
Technically these are pseudo- pseudo-distances distances as although they are positive they are not necessarily symmetric and
are not guaranteed to satisfy the triangular inequality.
13

---

where @ denotes element-wise multiplication. This is just the sum the set of edge distances that are used in the tour. This schematically shown below.
0..00
0.33
0.78
0.22
0.57
0.25
70.00
0.00
0.00
0.22
0.00
0.00
0.75
0.00
0.49
0.22
0.39
0.49
0
0
0
1
0.00
0.00
0.00
0.00
0.39
0.00
0.83
0.31
0.00
0.28
0.61
0.56
1
0
0
0
0.00
0.31
0.00
0.00
0.00
0.00
0
0.37
0.18
0.50
0.00
0.78
0.13
0.00
0.00
0.00
0.00
0.00
0.13
0.19
0.61
0.11
0.68
0.00
0.49
0
0.00
0.00
0.11
0.00
0.00
0.00
0.30
0.64
0.82
0.71
0.68
0.00
0
0
0
0
0.30
0.00
0.00
0.00
0.00
0.00
y
The edge matrix y is a matrix with a in each row and each column and zero elsewhere, That is, is a permutation matrix. Unfortunately. not all permutation matrices correspond to legal tours. The only permutations that are allowed correspond irreducible permutation (i.e. those consisting of single cycle of length n, where n is the number of cities) thees are cyclic permutations of order n. This, arises because there are (n 1)! tours (since the starting city is arbitrary) whereas there are n! permutation matrices. The illegal permutations consist of multiple cycles (e.g. for four city problem we might have 1 ++ and ++ 4.). It is however challenging to generate irreducible permutations. To solve this problem we use the fact that the set of permutations of order form an equivalence class [r]] and for any permutation q E S,, (where Sn is the group of all permutations of knoeetsskkown&ae as the symmetric group) then if E [nx] the conjugate q well known result group theory, but means that if we start with an irreducible representation π (e.g. the tour 1 -
[m]. This is
- + 1) then for any permutation matrix q the product q q represents a legal tour. Thus we set up the networks to generate a permutation matrix This used a Cumbel-Sinkhore network [14] as part of network H. Occasionally this would generate solution with fractional edges. To avoid this we added term to the loss function that punished solutions with fractional edges.
Although this procedure guarantees that the solutions correspond to feasible tours, the quality of tours obtained when trained the full network is poor. The problem is that the relationship between the permutations q and the matrices of edges visited y = π q is difficult to learn. To address this problem in the scratch-pad vector we learned three groups of channels & (Φ1, Φ2. m.). The last part m is a single channel which we treat as a matrix from which we compute an orthogonal transformation. To achieve this perform SVD to obtain usv". We discard obtain orthogonal matrix w uv We use this to transform Φ2. This reordering significantly improves the quality of the tours learn. We attribute this to providing the network G with the ability to understand how altering q will change SVD from the PyTorch library [16]. Very occasionally this would fail, in which the training and start again. Although rare this was the one source of failure of the network.
π q and hence the cost of tour. We used a differentiable version of
we terminated
For asymmetric tours obtained improved results by making the input have three channels. The first being the distance matrix and the second the transpose of the distance matrix and the third a matrix that have values of in the upper triangle, 0 along the diagonal and in the low triangle. For convenience the same input was used for symmetric instances, but obviously the transposed distance matrix is equal the distance matrix. In addition, the seratch-pad vector learnt two matrices Φ = (#1, Φ2, m., m2) from which we constructed two orthogonal matrices wi = u.v which we used to apply both column wise and row-wise transformations w w Φ2w
With these modifications we then trained DTT- on randomly generated instances of TSP using a loss function based on the mean cost of single edge in the selected tour. The distances were normalized so the maximum edge is 1. The loss function can be stated as
I Σ (xij - 1) v N
Liour
(B5)
where & 2 is hyperparameter that pushes values not equal to closer to zero, thus preventing solutions with fractional edges.
14

---

Prefix Sums Models
For different widths w, we scale the channels of the convolutional layers in H. (output module) as follows:
Layer
Input Channels
Output Channels
Convolution
w
w
Convolution 2
w max (2, (w/2[)
Convolution 3
max(2, [w/2])
2
This ensures consistency with the w = 400 prefix sums models in [2]. For w = 32, this results in output channels of 32, 16, and 2.
Mazes Models
For different widths w, scale the channels of the convolutional layers in H. (output module) as follows:
Layer
Input Channels
Output Channels
Convolution
W
max (2, 4 ww)
Convolution 2
max max(2, ww)
max (2
Convolution 3
max max(2, (2,4-2)
2
Chess Puzzles Models
For different widths w, we scale the channels of the convolutional layers in H. (output module) as follows:
Layer
Input Channels
Output Channels
Convolution
max 1a-116611 ww)
Convolution
max (2, 16 16,16-1w ww)
2
Convolution
2
C
Training
Unless specified otherwise:
All models use the Adam optimizer [12] with
learning of 0.001,
31 = 0.9, 32 0.999,
weight decay set to 0.0002 and only applied to unconstrained convolutional weights; incremental progress training with a 0.5;
exponential warmup with warmup period of 3;
a multi-step learning rate scheduler where milestones are calculated as a 4 2 ratio of the total number of epochs, with learning rates multiplied by 0.1 at each milestone.
As example, prefix-sume sums-solvingg models trained to 150 epochs. With the given ratio this produces milestones of 80, 120, and 140.
For all models, the end-of-epoch state resulting in the best validation score (accuracy for non-TSP problems, loss for TSP) became the final result of training. This is standard practice training deep learning models.
15

---

C.1 Prefix Sums
Prefix-sums-solving models were trained on 32-bit prefix sums from the EasyToHard dataset [17] for 150 epochs, shuffled and split into 80% training samples, 20% validation samples. Each batch contained 500 samples.
Trained models for ablation studies instead used milestones 4 2: ratio of 150 epochs instead. Models were trained with M 30.
C.2 Mazes
Maze-solving models were trained on 17 x 17 mazes from the EasyToHard dataset [17] for 50 epochs, shuffled and split into 80% training samples, 20% validation samples. Each batch contained 50 samples.
Models were trained with M = 30.
C.3 Chess Puzzles
Chess puzzles models were trained the casiest 600,000 chess instances from the EasyToHard ToHard dataset [17] for 120 epochs, with batch sizes of 300 problem instances. Learning rate scheduling followed the same 8 4: 2 milestone ratio, with multiplier of 0.1. The dataset shuffled and split into 80% training samples, 20% validation samples. Each batch contained 300 samples.
Models were trained with M = 30.
C.4 Traveling Salesperson
Models trained to produce tours for TSP instead stochastic gradient descent (SGD) with learning rate of 0.001, Nesterov momentum of 0.9, and weight decay of 0.0002 (applied only to unconstrained convolutional weights).
The model trained to perform symmetric TSP used IPT with a 0.5, whereas the model trained to perform asymmetric TSP did not use IPT.
Since there no dataset, we chose 1,000 samples be an appropriate size for one epoch. With 80% training samples and 20% validation samples, this produces 800 training batches per epoch and 200 validation samples per epoch. We generate 64 grids of distances per batch.
D Additional Results and Analysis
D.1 DT-R Stability
To show the training instability in more widths for the prefix sums DT-R models, Figure D4 shows extended results from Figure 3.
16

---

1.00
1.00
1.00
Training Loss
Training Loss
Training
0.50
0.50
0.50
0.00
0.00
0.00
100
150
50
100
150
50
100
150
Epoch
Epoch
Epoch
8
16
Training Less
Training Loss
0.75
0.75
0.75
0.25
0.25
0.25
Epoch
Epoch
Epoch
10
64
W
128
256
1.00
Training Loss
0.75
0.50
0.25
0.00
50
100
150
Epoch
512
Figure D4: Extended results of Figure 3. Mean training (cross-entropy) loss at each epoch for seefx-suum--ollvnnee models of varying width w. Each curve measured from different random initialization of the model throughout training, for 10 models of each width. Dotted vertical lines indicate loss becoming NaN or infinite, where model does not recover.
D.2 Ablation Studies
We have performed ablation studies prefix-sums--olvinn models of width 32 and using IPT with a = 1.0. Instead of the 8 4 2 milestone ratio (Appendix C), these models use a 4 1 milestone ratio, meaning the multiplier 0.1 is only applied twice instead of three times.
Activation Function. We perform a study by modifying DT-R to use ELU [4] instead of ReLU. From Figure D5(a) it appears that ELU allows for increased extrapolation performance from DT-R with minimal decay.
Similarly, we perform study by modifying DT-L to use ReLU instead of ELU. It can be seen from Figure D5(b) that, while ReLU results faster convergence, ELU appears to provide overall increased extrapolation performance.
17

---

100
100
Accuracy (%)
80
Accuracy (%)
80
60
60
Model
Model
DER (ReLU)
DEL (ReLU)
DER (ELU)
DEL (ELU)
20
20
300 Test-Time lterations (M)
100
200
100
200
300
Test-Time Iterations (M)
(b)
Figure D5: Mean solution accuracy at different M for (a) instances of DT-R (with ReLU activations) and 5 instances of DT-R (with ELU activations), and for (b) instances of DT-L (with ReLU activations) and instances of DT-L (with ELU activations). All models have width = 32. Extrapolation performance tested on 512-bit prefix sum problem instances. Shaded areas show 95% confidence intervals.
Bias in the Final Layer. DT-R has no bias terms throughout the entire model. We compare this to a version which has bias term in only the final layer of the model.
100
100
Accuracy (%)
80
Accuracy (%)
80
60
60
Model
Model
40
(No Final Bias)
40
Final Bias)
DTR (With Final Blas)
DT- (With Final Bias)
20
20
100
200
300
200
Test-Time Iterations (M)
Test-Time Iterations (M)
(a)
(b)
Figure D6: Mean solution accuracy at different M for (a) instances of DT-R (without final bias term) and 5 instances of DT-R (with final bias term), and for (b) 5 instances of DT-L (without final bias term) and instances of DT-L (with final bias term). All models have width w = 32. Extrapolation performance tested on 512-bit prefix sum problem instances. Shaded areas show 95% confidence intervals.
Batch Normalization. DT-R has no batch normalization layers in the model. We perform a study to measure the impact adding batch normalization DT-R (Figure D7(()), as well as remove from DT-L (Figure D7(b)).
18

---

100
100
Accuracy (%)
80
Accuracy (%%
60
60
Model
Model Batchnorm)
Batchnorm)
DT-R (Batchnorm)
DT-L (Batchnorm)
20
20
200
200
Test-Time Iterations (M)
Test-Time Iterations (M)
(a)
(b)
Figure D7: Mean solution accuracy at different M for (a) 5 instances of DT-R (without batch normalization) and instances of DT-R (with batch normalization), and for (b) instances DT-L (without batch normalization) and 5 instances of DT-L (with batch normalization). All models have width w = 32. Extrapolation performance tested on 512-bit prefix sum problem instances. Shaded areas show 95% confidence intervals.
E
Running Times and Peak Memory Usage
After all experiments had been completed, a modified version of the spectral normalization code was created which caches the normalized weights. This modification gives improved training times.
Table El provides the training times of DT-R and DT-L before this modification (the version used in the experiments). Table E2 provides the training times of DT-L after this modification.
Table E1: Representative training times and peak memory usage for different models. Training time given as hours minutes.
Batch Size
Training Time
Memory
Model
Problem
Epochs
Hardware
Usage
DT-R w 32
Prefix Sums
500
150
RTX8000
00:10
1.25 GB
DT-L w = 32
Prefix Sums
500
150
RTX8000
00:30
1.34 GB
DT-R w 32
Mazes
50
50
RTX8000
03:30
4.30 GB
DT-L w = 32
Mazes
50
50
RTX8000
04:02
4,41 GB
DT-R w 16
Chess Puzzles
300
120
A100
02:55
10.87 GB
DT-L w = 16
Chess Puzzles
300
120
RTX8000
07:36
10.67 GB
Table E2: Representative training times and peak memory usage for different models (using spectral normalized weight caching). Training time given as hours minutes.
Batch Size
Training Time
Memory
Model
Problem
Epochs
Hardware
Usage
DT-L 32
Prefix Sums
500
150
RTX8000
00:19
1.30 GB
DT-L w = 32
Mazes
50
50
RTX8000
03:15
4.42 GB
DT-L w 16
Chess Puzzles
300
120
RTX8000
04:47
10.70 GB
19

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: We claim improvement to existing type of model known Deep Thinking network as a result of careful analysis failure cases. Empirically we show that improved Deep Thinking with Lipschitz Constraints (DT-L) model has better training and extrapolation performance. We also show a theoretical proof of why our proposed changes guarantee convergence of the learned algorithm (and why the earlier approaches did not).
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: We have discussed limitations in some detail and created separate limitations paragraph in Section 7. The approach we develop analytically has relatively few direct limitations as the assumptions are mild. However, even on simple problems we recognise that whilst we have made significant improvements over prior approaches there are still times where the model fails to learn for example.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best
20

---

judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: Sketch- Sketch-proofs and the intuition behind our architectural designs of recurrent function that converges are given in the body of the paper, with more formal proofs in the appendices (Appendix A) and are cross-referenced. All assumptions are clearly stated.
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that it affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: Full details of our model design is given in Appendix B, with training details provided in Appendix C. The main evaluation setup repeats that described by Bansal et al. [2] and Schwarzschild et al. [18] where we use the datasets provided by Schwarzschild et al. [17] for studying easy-to-hard generalisation. Further we provide the code for all models and experiments (as supplementary material during review, and later as a GitHub link).
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
21

---

(c) If the contribution is new model (e.g.. a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome to describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described supplemental material?
Answer: [Yes]
Justification: All code for reproducing experiments is provided (in the supplementary material during review; be moved github later), including code for generating our TSP datasets. As described above we use the open access datasets provided by Schwarzschild et al. [17) for studying easy-to-hard generalization for the main evaluation.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.. cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https: //nips. wwtpcc/ccpgg.puiecoooooooopp wetiic/ggiise/eeee / ssionoolicy) for more details.
The authors should provide instructions on data access and preparation, including how access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: Please Appendix C for full details of the training procedure and Appendix B for problem-specifie model architectures. The broader experimental setting can be found in Section 5 and Section 6.1 of the main paper.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
22

---

7. Experiment Statistical Significance
Question: Does the paper report enror bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: Error bars (confidence intervals) provided where appropriate. Because part the objective of the paper is to demonstrate the improvement in stability the models, in some cases show data from multiple raw runs of the models, thus allowing different cases to be seen.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the enror bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (c.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: All experiments are carried out on commodity hardware, where we used GPU resources that we had available. This is documented in Section and Section 6. with fuller table of exemplar configurations and timings for different experiments in Appendix E.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: / htt///nerriigg mneurips.cm httpscccppublcccbeeeeeeeee ctwpe/tthhiaiileeiiienececmcee ines?
Answer: [Yes]
23

---

Justification: We have studied the code of ethics and can confirm our research conforms to all guidelines. Our research uses no human participants, and the datasets we experiment with are created artificially to control biases. Our research does not pose any immediate security or safety issues, however in body of the paper we recognise that their are potential broader impacts from the approaches we are building. The approaches we develop in the paper are aimed at being more stable and reliable, whilst also potentially using fewer parameters. As such they are promoting positive environmental impact.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: have included a discussion of potential broader impacts in Section Summarising, whilst this work is at the fundamental principles end of the spectrum, see many potential applications from a learning machine that can learn iterative algorithms that extrapolate. Whilst the work does not directly have negative societal impact, it is quite conceivable that an application that does could built using it as the basis.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g., disinformation. generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
Question:
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Answer: [NA]
Justification: The model architectures and datasets as presented offer minimal potential for misuse.
Guidelines:
24

---

The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Are the creators or original owners of assets (c.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Question:
Answer: [Yes]
Justification: Where we have used existing code or implementations these are properly attributed. The datasets [17] we use are referenced in the paper. The papers that develop model architectures [2, 18] we build upon are referenced in the paper.
Guidelines:
The answer NA means that the paper does use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should provided.
assets are released, the license, copyright information, and terms use in the package should be provided. For popular datasets, paperswi paperswithcode. thcode. com/ datasets
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: Our code and TSP dataset generator will be released on github, and are provided in the supplementary material during review.
Guidelines:
The answer NA means that the paper does release new assets.
Researchers should communicate the details the dataset/code/moodel as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
25

---

Answer:
[NA]
Justification:
This work does not involve crowdsourcing or human participants.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: This work does not involve crowdsourcing or human participants.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
26


Reviews:
[{"review_id": "gpRnDDIEof", "reviewer": "Reviewer_ipKY", "summary": "The paper introduces Deep Thinking with Lipschitz Constraints (DT-L), an improved version of the Deep Thinking (DT) networks, designed to enhance the stability and performance of iterative algorithm learning models. The authors address the instability issues inherent in DT networks by analyzing intermediate representation growth and applying Lipschitz constraints. The DT-L model guarantees convergence to a unique solution and demonstrates robustness in learning algorithms that extrapolate to more complex problems. The paper furthermore benchmarks DT-L on the Traveling Salesperson Problem (TSP) as well other than the datasets used in the Deep Thinking models. It compares its performance against existing DT models.", "questions": "- How does the introduction of Lipschitz constraints impact the computational complexity and training time of the DT-L model compared to traditional DT models?\n- Can the proposed DT-L model be extended to other types of iterative algorithms beyond the ones tested in this paper? If so, what modifications would be necessary?\n- Can this applied for transformer architectures like looped transformers?\n- Can the insights gained from this work be applied to improve the interpretability of the learned algorithms, making the decision-making process of the DT-L model more transparent?", "limitations": "None", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Introducing Lipschitz constraints into the DT framework enhances the models' reasoning capabilities. This approach addresses instability issues in training and inference, offering theoretical guarantees for convergence.\n- DT-L demonstrates the ability to scale to larger problems effectively, maintaining stability and performance, which is crucial for real-world applications.\n- The comprehensive evaluation on various problem classes, including prefix sums, mazes, chess puzzles, and TSP, highlights the robustness and versatility of the DT-L model.\n- The paper provides a thorough analysis of the issues with DT networks and clearly explains how the proposed modifications address these problems.", "weaknesses": "- The modifications and theoretical underpinnings of the DT-L model, such as the Lipschitz constraints and orthogonal transformations, add complexity to the model, which might hinder its adoption and understanding by a broader audience.\n- While the DT-L model shows improvement, its performance on the TSP is not impressive, indicating room for further optimization and refinement.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their positive and constructive comments.\n\n### Response to Weaknesses\n\n> *\"The modifications and theoretical underpinnings of the DT-L model, such as\n> the Lipschitz constraints and orthogonal transformations, add complexity to\n> the model, which might hinder its adoption and understanding by a broader\n> audience.\"*\n\nThe main contribution of the paper in our view is that by imposing a Lipschitz constraint the recurrence is guaranteed to converge leading to much more stable training.  We believe that this is conceptually simple enough and provides sufficient benefits that it will be readily adopted by the broader community. However, as you have acknowledged there is complexity to this. The orthogonal transformation is only used for the TSP-solving variant of DT-L.  The complexity of solving TSP and ensuring that the tour constraint is met is sufficiently difficult that whenever tackling TSP some technical complexity is inevitable.  For solving the other problems the orthogonal transformation is not used and the network design was chosen to be as close to that of DT-R that we could make it.\n\n> *\"While the DT-L model shows improvement, its performance on the TSP is not\n> impressive, indicating room for further optimization and refinement.\"*\n\nWe have provided a response to this weakness as part of our response to all reviewers.  We would emphasize that finding an algorithm capable of solving random instances of general TSP is a surprisingly challenging problem.\n\n### Answers to Questions\n\n> *\"How does the introduction of Lipschitz constraints impact the computational\n> complexity and training time of the DT-L model compared to traditional DT\n> models?\"*\n\nThe implementation we have used for spectral normalization computes the spectral\nnorm (from cached power iteration values) and divides the weights by this value\nfor every weight access. This is computationally expensive, but is a simple\naddition to the model with PyTorch's parametrization features. Since the\nsubmission of this paper, a modification to our implementation of spectral\nnormalization allows caching of these weights while maintaining gradient\ninformation. This has allowed a significant improvement to training speed, which\nwe intend to show by adding an entry of improved training time to Table E1 for\neach DT-L model.\n\nWe would also point out that due to the added stability we get by imposing the Lipschitz constraint we are able to tackle the test problems with significantly smaller networks than those used in the DT-R paper.  This provides a considerable improvement in speed making training these networks a lot more efficient than the larger DT-R models.  If we attempt to use smaller versions of the DT-R model we found that the model almost always failed to train properly.\n\nFinally, because of the increased stability we generally only have to train our model once to obtain a working solution. In contrast there are instances where we had to train DT-R over 20 times in order to find a solution that worked.\n\n> *\"Can the proposed DT-L model be extended to other types of iterative\n> algorithms beyond the ones tested in this paper? If so, what modifications\n> would be necessary?\"*\n\nWe believe extensions to other types of problems and implementations are\ntechnically possible, but they go beyond the remit of this paper. In particular we see\nDT-L as being suitable for problems which naturally lend themselves to being\nsolved by repeated convolutions, but extending the architecture to other\nproblems is something we are considering and working towards.\n\n> *\"Can this applied for transformer architectures like looped transformers?\"*\n\nThere are challenges to overcome in adapting transformer architectures to this\napplication. It would be fantastic to see if one can create an iterative\ntransformer with these constraints in the context given by the paper. We have\nbeen giving it some thought, but are not at the point where we have results. A\ntransformer-based version of DT-L is out-of-scope, but this paper provides a\ncritical stepping-stone towards this goal.\n\n> *\"Can the insights gained from this work be applied to improve the\n> interpretability of the learned algorithms, making the decision-making process\n> of the DT-L model more transparent?\"*\n\nThis is a really good question, and something we're looking into.\nWe're currently working on this since we believe guaranteeing uniqueness to a\nsolution (from being a contractive mapping) should improve interpretability, but\nthis is not work for this paper.", "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": "", "extra_scores": {}}, {"review_id": "EUnbVSCPjG", "reviewer": "Reviewer_x7iE", "summary": "The paper addresses the positive feedback issue in the so called Deep Thinking networks, where the inference computation may involve more recurrent computations than encountered in training.  The proposed solution is to normalise the state vector that undergoes the recurrence, i.e. make the mapping contractive, i.e. ensure negative (but just) feedback.", "questions": "Does batch normalisation alone not do a good job of stabilising the feedback?", "limitations": "If I understand this correctly, the proposed normalisation creates vanishing gradient problem, but authors seem to be aware of this and address it by keeping the spectral norm close to 1.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 1, "strengths": "The paper is well written and clear to follow, the proposed method is pretty straight forward and effective.", "weaknesses": "As far as I can tell, it is pretty straight forward control theory stuff for addressing positive feedback.  Nothing wrong with the proposed solution, but I would assume this is such a fundamentally well known issue in any recurrent/feedback system that we can leave this to be addressed by the designer at implementation time with any choice of normalisation.  It is somewhat disappointing that with the proposed method there is still the need for batch normalisation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments.\n\n### Response to Weaknesses\n\n> *\"As far as I can tell, it is pretty straight forward control theory stuff for\n> addressing positive feedback. Nothing wrong with the proposed solution, but I\n> would assume this is such a fundamentally well known issue in any\n> recurrent/feedback system that we can leave this to be addressed by the\n> designer at implementation time with any choice of normalisation. It is\n> somewhat disappointing that with the proposed method there is still the need\n> for batch normalisation.\"*\n\nWe agree that it is well-known that any learned recurrent system can explode or vanish.  The most prominent method for solving this is to have memory cells that are mainly conserved as exemplified by LSTMs and their variants.  This mechanism does not fit the DT architecture.  Imposing a sub-Lipschitz-1 constraint to ensure that the recurrence reaches a unique solution is to the best of our knowledge the first time this has been done in the context of recurrent networks (and certainly in the case of deep thinking networks).  It is, in our experience, somewhat non-trivial to ensure this constraint holds in a network with learnable parameters.  As shown by the previous DT papers, ensuring Lipschitz-1 behavior is not necessary for the models to work, although it makes the model much more fragile (i.e. it often fails to learn).  The contribution of this paper is showing that imposing a Lipschitz constraint cures this problem.  There are a number of unexpected consequences of doing this.  For example, we show we are able to reliably solve the problems with many fewer parameters (often by orders of magnitude).  The added stability makes it far easier to work with these models, to the extent that we were able to get these models to find an algorithm for solving TSP.  Thus, in our view, the paper shows some unexpected consequences of controlling the norm which was not so well known that it had been implemented in previous models.  As discussed below, batch normalization is not used in the recurrent section of the network (network $\\mathcal{G}$) and, in fact, it causes problem when it is added (perhaps illustrating that controlling the norm is less trivial than it may appear).\n\n### Answers to Questions\n\n> *\"Does batch normalization alone not do a good job of stabilising the\n> feedback?\"*\n\nAs stated in the paper, the batch norm is not used in the recurrent\npart of the model. Instead, batch normalization is only used outside of the\nrecurrent part. If the reviewer believes this is unclear in the current version,\nwe can update it to be clearer about where in particular batch normalization is\nused.\n\nOur reasons for not using batch normalization in recurrence follows from\nexisting literature, particularly 'Residual Connections Encourage Iterative\nInference' (Jastrzebski *et al.*, 2018, DOI: 10.48550/arXiv.1710.04773) where\n_unsharing_ batch normalization\nstatistics was necessary to avoid activations exploding. In an architecture\nwhere the maximum number of iterations is unknown (and potentially large in the\ncases of large prefix sum and maze problems), it appears infeasible to unshare\nbatch normalization statistics for every iteration. Nonetheless, we look forward\nto future research that may resolve this issue.  It is also worth mentioning that batch norm does not ensure that the model is constrained to be sub-Lipschitz-1, which is another reason we have not used it.", "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": "", "extra_scores": {}}, {"review_id": "JseNGVVPPN", "reviewer": "Reviewer_9kC6", "summary": "This paper identifies and rectifies an issue with a particular type of iterative neural network called Deep Thinking Networks. The problem arises in exploding latent representations and unstable training routines. The authors of this work propose an update to the architecture where they add Lipschitz constraints to the model. They show three major benefits: (I) The models train more stably/predictably; (II) the inference-time behavior is better as the latent representations converge with iterations of the recurrent model; and (III) this new approach can learn how to solve NP-Hard problems where the old methods fail.", "questions": "1. Can the authors make the clarifications needed to address my first two points in the Weaknesses section?\n1. Have the authors looked at transformer architectures at all? I'm not asking for results to be added to the paper, but I'm curious about how these techniques, which are independent from the parameterization of any given layer in some ways, might apply to modern large model architectures.", "limitations": "Yes, the limitations are adequately addressed.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "1. This paper is original to my knowledge. I am aware of much of the work on Deep Thinking Networks and the issues raised and the solutions proposed in this work are novel.\n1. The quality of the work is high. For the most part the experiments are done well and cover many natural questions that would arise from reading the abstract/intro.\n1. The clarity is good. I think the writing is clear and the results are compelling.\n1. The results are significant for those interested in easy-to-hard generalization. These Deep Thinking Networks have strong extrapolation of toy problems and with the proposed updates to the methods they show strong performance even for TSP solving.", "weaknesses": "1. Clarity: A couple things could be more clear.  \n  i. I think IPT stands for Incremental Progress Training, but I don't see the acronym defined anywhere.  \n  ii. Table 1 the units are unclear. I gather there are tour lengths, but that isn't stated in the table or the caption.  \n  iii. The violin plot in Figure 2 is hard to parse (no harder than any other violin plot). This type of graphic does look nice, but offers little quantitative context. For example, there is no indication of the units/scale of the width of each violin. This is not the right type of plot for a conference paper.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for their support and helpful suggestions, and are glad they are as excited about this direction of research as we are.\n\n### Response to Weaknesses\n\n> *\"Clarity: A couple things could be more clear.\n> i. I think IPT stands for Incremental Progress Training, but I don't see the\n> acronym defined anywhere.\n> ii. Table 1 the units are unclear. I gather there are tour lengths, but that\n> isn't stated in the table or the caption.\n> iii. The violin plot in Figure 2 is hard to parse (no harder than any other\n> violin plot). This type of graphic does look nice, but offers little\n> quantitative context. For example, there is no indication of the units/scale\n> of the width of each violin. This is not the right type of plot for a\n> conference paper.\"*\n\nWe have updated the paper to appropriately define 'incremental progress\ntraining' (IPT) and have updated the caption of Table 1 to specify that the DT-L\ncolumn consists of tour lengths. These were both oversights on our behalf, and\nwe thank the reviewer for pointing these out.\n\nThe violin plot (Figure 2) will be updated with a different graphic which better\nshows the distribution of singular values in reshaped kernel weights, providing\nclearer quantitative insight. We have provided an alternative graphic (Figure\nR1) in the PDF uploaded to the overall rebuttal, and trust that you find this more appropriate? \n\n### Answers to Questions\n\n> *\"Can the authors make the clarifications needed to address my first two\n> points in the Weaknesses section?\"*\n\nSee above.\n\n> *\"Have the authors looked at transformer architectures at all? I'm not asking\n> for results to be added to the paper, but I'm curious about how these\n> techniques, which are independent from the parameterization of any given layer\n> in some ways, might apply to modern large model architectures.\"*\n\nYes, we have considered this. We believe it is a challenging problem that is\nyet to be solved and have started to give it some thought.", "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": "", "extra_scores": {}}, {"review_id": "MnvTMTLcWc", "reviewer": "Reviewer_vZtn", "summary": "To solve the stability of Deep Thinking models, this paper proposes to constrain activation functions to be Lipshitz-1 functions. The original DT and DT-R models have training stability problem, basically because of scale explosion or vanishing. The authors revealed the stability problem, attribute the problem to Lipschitz constants, proposed ways to ensure Lipschitz smoothness, and show the effectiveness of their approach through a few examples used in the original DT paper, as well as include the traveling salesman problem.", "questions": "* In Line 141-142, I don't quite get this comment \"Although any Lipschitz constant less than 1 would guarantee convergence, the nature of the problem solving mechanism we seek to learn intuitively means that we do not want fast convergence.\" Why don't we want faster convergence.\n* In Figure 6 left, it looks like DT-L is worse than DT-R? Why is that? More stability leads to worse performance?\n* What about DT and DT-R for TSP?", "limitations": "The authors cleraly addresses limitations.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "* This paper is clearly written and well motivated. \n* The storyline is very reasonable: identify problems => propose ways to solve the problem => show the approach actually works\n* This approach is mathematically grounded.\n* Experiments are thorough, by running many random seeds and report error bars.", "weaknesses": "* The idea is quite straight-forward (may not be a bad thing, but make technical contributions smaller)\n* In the TSP problems, DT-L's results seem worse than NN Tours and BNN Tours. At least some explanation is warranted. \n* I'm not fully convinced by the significance of this paper. The examples shown in the paper are quite toy. Are there more examples you expect DT-L would work?\n* I'd appreciate more visualizations that can intuitively show the benefits of DT-L over DT/DT-R? Maybe some Figures like in the original DT paper. \n* The title is not very informative. Might be better to mention Lipschitz smoothness in the title.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for taking the time to read the paper and for raising some important points in regards to our submission that we agree should be addressed.\n\n### Response to Weaknesses\n\n> *\"The idea is quite straight-forward (may not be a bad thing, but make\n> technical contributions smaller)\"*\n\nWe believe that imposing a sub-Lipschitz-1 constraint provides guarantees about the behaviour of DT-L architecture that previous models lacked (e.g. we are guaranteed that the recurrence will converge to a unique fixed-point).  We strongly believe this opens up avenues to future improves that would not be possible otherwise.  Finally, if the reviewer was seeking technical innovation we would point to our TSP model that involve a number of novel tricks that we are quite happy about (this is incidental to where we believe the main contribution of the paper lies so we have not emphasized these).\n\n\n> *\"In the TSP problems, DT-L's results seem worse than NN Tours and BNN Tours.\n> At least some explanation is warranted.\"*\n\nWe have responded to this comment in the response to all authors.  We fully agree that further explanation is warranted.  We had understated the difficulty of solving TSP using a convolutional algorithm that only gets to see a small part of the distance matrix.\n\n> *\"I'm not fully convinced by the significance of this paper. The examples\n> shown in the paper are quite toy. Are there more examples you expect DT-L\n> would work?\"*\n\nIn this paper we deliberately chose to make DT-L as close to DT-R as possible to allow easy comparison and to focus attention on the benefits of imposing the sub-Lipschitz-1 constraint.  However, this constraint (with its theoretical underpinnings) allows a whole host of modifications to deep thinking type architectures to be developed that will train robustly.  We attempted to demonstrate this by learning an algorithm to tackle random TSP instances.  We believe (and have strong evidence based on work conducted after submitting this paper) that there is considerable potential to tackle many tasks considered 'real' world.  Given the page constraints of the paper, and a desire not to make this paper any more complicated, we feel going into this is outside the scope of this work.\n\n> *\"I'd appreciate more visualizations that can intuitively show the benefits of\n> DT-L over DT/DT-R? Maybe some Figures like in the original DT paper.\"*\n\nThe main benefits of DT-L are the stability it provides, especially in the case\nof smaller models. The focus is not on the algorithms it may learn or any\nattempt at interpreting them. While these are interesting visualizations to\nproduce, this is not the topic of the paper and we believe including such\nvisualizations may detract from the main contribution.\n\n> *\"The title is not very informative. Might be better to mention Lipschitz\n> smoothness in the title.\"*\n\nWe agree with the reviewer that the title is not very informative, and are\npleased to incorporate the suggestion given by amending the title to\n**Rethinking Deep Thinking: Stable Learning of Algorithms using Lipschitz\nConstraints**.\n\n### Answers to Questions\n\n> *\"In Line 141-142, I don't quite get this comment \"Although any Lipschitz\n> constant less than 1 would guarantee convergence, the nature of the problem\n> solving mechanism we seek to learn intuitively means that we do not want fast\n> convergence.\" Why don't we want faster convergence.\"*\n\nThis is a good question, and something we will clarify in the final version of\nthe paper.\n\nOur reasoning behind promoting slower convergence is to obviate the learning of trivial solutions to the given problem. As the model is trained on simple problems, we need to avoid it finding a simple solution (e.g. a shortcut, or memorisation) that does not generalise to larger problems. We re-emphasize that when we refer to convergence here, we are talking about the run-time convergence of the learned algorithm, not the training convergence (which we clearly do want to be fast and stable - something that our proposed solution also offers).\n\nRecall that we seek a solution using convolutions that only have access in a single iteration to information in a limited field of view.  To obtain good solutions requires information across the whole problem instance.  This is why to solve larger instances we need to run for more iterations.  Thus, allowing the solution to converge slowly (which we achieve by making the Lipschitz constant close to 1) prevents the network finding a sub-optimal solution requiring only local information.\n\n> *\"In Figure 6 left, it looks like DT-L is worse than DT-R? Why is that? More\n> stability leads to worse performance?\"*\n\nIt is intriguing why DT-L performs slightly worse than DT-R on the chess problem and whether we pay a price for stability. It may well be that adding an additional constraint leads to a slight decrease in performance, however, these networks are sufficiently complex that we are reluctant to come to any firm conclusions without a lot of evidence. As an aside, we can easily modify DT-L networks to get better performance than the DT-R network. We have not put in these results as it is not a fair comparison (the network architectures are slightly different). To make a fair comparison we should also optimally modify DT-R, but DT-R is far harder to modify as many modifications lead to networks that don't train at all.\n\n> *\"What about DT and DT-R for TSP?\"*\n\nTSP is such a complex problem that getting the DT-R model to learn (rather than consistently diverge) is a huge challenge.  Of course, there is a huge hyper-parameter space to explore where it is possible that DT-R might work and we will endeavour in the appendix of the final version to add results for DT-R if we are ever able to train it (experiments underway at the moment).  Realistically DT is highly unlikely to ever solve this problem (DT-R dominates DT on almost all problems).", "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": "", "extra_scores": {}}]

Author rebuttal:
We would like to thank all reviewers for their careful reading of the paper and their insightful comments. We are pleased that overall the reviewers found the paper clear, but we will integrate the helpful suggestions that have been made - thanks!  

We have responded to the reviewers individual comments separately, but there were a two general comments made by multiple reviewers that we address here.

**A number of reviewers commented on the performance of TSP.**  A previous criticism of deep thinking papers, one we don't share, is that the problems were cherry picked for the architecture.  We chose TSP as a problem we knew to be notoriously hard, but fitted the requirement of a problem that we could scale up to a large size to create a harder problem.  Any implementation of a TSP solver is challenging because of the tour constraint.  We wanted to demonstrate that DT-L was sufficiently robust that it could find an algorithm for solving TSP.  To increase the challenge we chose non-symmetric (and obviously non-Euclidean) TSP, and additionally we do not provide the optimal solution during training, utilizing only a loss that penalizes tour length.  In this case many of the classic heuristics fail.  For example, k-OPT which is widely used in hill-climbing type solvers are inefficient as they typically involve reversing part of the tour which completely changes the path length.  Other common heuristics used for Euclidean TSP (such as locality of cities) also fail for non-Euclidean problem instances.  Thus, nearest neighbor algorithms actually provide a stiff baseline for this problem.  Note, however, that DT-L has only a local view of the distance matrix as it is using convolutions.  Nearest neighbor in contrast is a constructive algorithm that requires global information of the distance matrix (it has to find the closest city that has not already been included in the tour).  Thus, although the results we obtain on TSP may appear disappointing at first view we believe that the fact that they are considerably better than random tours shows DT-L's ability to learn non-trivial algorithms.  Finally, we should mention that for comparison with previous DT models we have deliberately stuck to the same architecture as DT-R as much as possible (although, admitted we needed to make some modification to get TSP to learn at all).  There are additional modification such as increasing the number of layers in the recurrent section of the network that leads to improved performance on TSP, but we have not included these in the current paper as we believe presenting too many modifications to the network would obscure the main contribution of adding the Lipschitz constraint.  We do agree with the reviewers that a comment on the TSP results would be useful and we will modify our text to include this.

**The reviewers mentioned extending to transformers and other tasks.** We are looking forward to exploring this direction in future work, but this is not the focus of this paper. The ideas presented here are however critical to actually extending deep thinking style _recurrent_ networks to other tasks. Our work also shows what design constraints of the recurrent architecture are required to ensure convergence, leading us to be able to propose new architectures in a principled way in the future. We have expanded more in the responses to individual reviewers.

Meta-review: **Summary:** This paper presents an enhancement to Deep Thinking networks by introducing Lipschitz constraints, leading to the development of the DT-L model. The key contribution is the imposition of a sub-Lipschitz-1 constraint, which guarantees convergence to a unique solution and addresses stability issues that have plagued previous DT models. The authors demonstrate the robustness of DT-L across several tasks, including the Traveling Salesperson Problem, and provide theoretical and empirical support for their claims.

**Strengths:**
- The paper tackles a significant issue in DT networks—training instability—by proposing a theoretically grounded solution in the form of Lipschitz constraints. This addition provides stability and guarantees convergence, addressing a fundamental problem in iterative algorithm learning.
- The authors conduct thorough experiments across various tasks, including TSP, prefix sums, and maze-solving, demonstrating the versatility and robustness of DT-L.
- The paper is well-written, with a clear narrative that connects the identification of the problem to the proposed solution and its validation through experiments.

**Weaknesses:**
- Technical Contribution: Some reviewers noted that while the application of Lipschitz constraints is effective, it may be seen as a straightforward application of well-known control theory concepts. This perception could limit the perceived novelty of the contribution.
- Performance on TSP: The results on the TSP benchmark are not as impressive as expected, with DT-L performing worse than some baseline methods. The authors provided an explanation, but the performance gap remains a concern.
- Evaluation and Generalization: Although the paper includes several experiments, there are concerns about the generalizability of the results. The tasks tested are somewhat toy-like, and it is unclear how DT-L would perform on more complex real-world tasks.

**Unresolved Issues:**
- Comparison with Baselines: The performance of DT-L on TSP was below expectations, and the authors’ explanation, while reasonable, does not fully resolve the concern. A more thorough comparison with DT and DT-R on TSP would strengthen the evaluation.
- Broader Impact: The paper’s focus on stability and convergence is valuable, but the broader impact on more diverse and real-world tasks is not fully explored. Further exploration in future work could address this limitation.

**Conclusion:** The paper provides a significant contribution to the field of iterative algorithm learning by enhancing the stability and convergence of DT networks through Lipschitz constraints. Despite some concerns about the novelty and generalization of the approach, the theoretical guarantees and robust empirical results make this a valuable addition to the literature. The paper is recommended for acceptance, with the expectation that future work will address the unresolved issues and explore broader applications of the proposed method.
Decision: Accept (poster)