Global Lyapunov functions: a long-standing open problem in mathematics, with symbolic transformers

Summary

This paper presents a method using sequence-to-sequence transformers to find Lyapunov functions for dynamical systems, mainly polynomial systems. Even though it illustrates some new advances in LLMs in solving mathematical problems, the reviewer doubts the mechanism and the necessity of using large models such as transformers to learn Lyapunov functions for simple polynomial systems, as well as the fairness of the comparisons made in the paper. This work could be a very interesting and good workshop paper to show the advances of LLMs, but the reviewer doesn't think there are significant academic contributions to the math community.

Strengths

This paper finds a way to explore or show the capacity of transformers, or LLMs in general, to solve existing mathematical problems, that is, finding the Lyapunov functions for nonlinear dynamical systems in this paper. Also, the backward data generation method is interesting.

Weaknesses

Even though the authors tried to make the story interesting and appealing, it seems that a deeper understanding on Lyapunov stability analysis is needed when improving this paper in the future. For example, Lyapunov functions are useful for providing stability guarantees for equilibrium points for dynamical systems, but there are no such equilibrium points in the three-body problem (line 29). Please see the introduction of chapter 3, Lyapunov stability in 'Nonlinear systems' by Khalil, H. K., one of the references of this work. Moreover, it seems that the authors didn't understand the stability concept fully when writing this paper. In line 27, they stated that the goal is "discovering the Lyapunov functions that control the global stability of dynamical systems", while in Def. 3.2, they had the definition of 'stable'. Stable and globally stable are different, which should be precise as an academic paper. Also, that's different from asymptotically stable. Meanwhile, 'control' is definitely not the correct wording here. Last but not least, finding a Lyapunov function (candidate) for a nonlinear system is not a very hard problem now, even for high-dimensional (polynomial) systems, but how to verify it is indeed a valid Lyapunov function satisfying the Lyapunov conditions is the bottleneck, which is difficult to address for non-polynomial or high-dimensional systems. As shown in the paper ['Neural Lyapunov Control'](https://papers.nips.cc/paper_files/paper/2019/hash/2647c1dba23bc0e0f9cdf75339e120d2-Abstract.html), one can easily use a one-hidden feedforward neural network with 6 hidden neurons to learn a Lyapunov function for many 2- or higher-dimensional nonlinear systems which are not necessary to be polynomials. That said, the results shown in this work are not impressive at all, and the Lyapunov function candidates they found using transformers still lack correctness, which needs to be verified against the Lyapunov conditions, given a new nonlinear system.

Questions

There are quite a couple of interesting questions that can be asked: 1. It's pretty shocking and interesting to see that the authors called SOSTOOLS which was proposed and developed more than two decades ago. Similar to the basic Lyapunov analysis explained above, it seems that the authors were unclear about the latest development of the toolbox or numerical methods for finding Lyapunov functions for nonlinear systems. Even in this year's HSCC conference, there are two tool papers on finding Lyapunov functions for general nonlinear systems: [FOSSIL 2.0](https://dl.acm.org/doi/10.1145/3641513.3651398) and [LyZNet](https://dl.acm.org/doi/10.1145/3641513.3650134). Both of them can handle the non-polynomial cases. The authors did a comparison with FOSSIL, but they claimed that they just achieved <5% accuracy. I don't think they give the toolbox a fair enough try. 2. With bullet point #1 being said, this transformer method needs a very long training time and an extremely large amount of data. However, with the aforementioned two toolboxes, for some systems, including the simple polynomial systems shown in Appendix C, valid Lyapunov functions can be found within a few seconds, and they are formally verified with SMT solvers. The same for SOSTOOLS, the obtained Lyapunov functions are guaranteed to be valid ones. On the contrary, the performances of the proposed method on some datasets are not satisfactory, such as Table 2 and Table 5. 3. Either in the control and system community or in the applied mathematics community, people barely solve Lyapunov functions by hand, the same as adding two very large numbers. The comparison with so-called 'human mathematicians' is not reasonable. 4. In line 189, '$e^i$ are diverse enough to span all of $\mathcal{H}_x$ '. When is it 'diverse' enough to span the space? 5. It's not surprising to see that after adding some data from forward datasets to the backward ones, the performances are much better. It's very likely that there are some issues with the backward datasets, while the forward datasets are guaranteed to be correct with SOS.

Rating

3

Confidence

5

Soundness

2

Presentation

2

Contribution

1

Limitations

The fairness of the comparisons and the correctness of the learned Lyapuonv functions, as discussed above. Also, even though the authors claimed that their methods worked well with non-polynomial system, the comparisons and examples are mainly for polynomial systems.

Summary

In this paper, the authors propose a new method of generating synthetic training samples from random solutions, i.e. Lyapunov functions for dynamical systems in the forms of ordinary differential equations. They demonstrate that the sequence-to-sequence transformer training on such data can produce Lyapunov functions better than both existing algorithmic solvers and humans. More speficially, for polynomial systems, the method proposed in the paper can find Lyapunov functions for 10.1% of the randomly generated polynomial systems where the state-of-art algorithm can only find 0.7%, furthermore, the method can produce a Lyapunov function for 12,7% of randomly generated non-polynomial systems.

Strengths

The problem of Lyapunov function problem is an important problem. The performance of the method proposed in the paper is impressive and promising.

Weaknesses

The novelty of the data generating methods, those described in Sec. 5, is not clearly stated and explained. Currently, it reads as if the results are obtained accidentally.

Questions

It is not clear how the forward and backward generation methods are different from what proposed in the past, for example those in Lample & Charton (2019), Prajna et al., 2002, and Prajna et al., 2005.

Rating

5

Confidence

4

Soundness

3

Presentation

3

Contribution

3

Limitations

As I have pointed out, the paper does clearly describe the difference between what it proposes to some of existing methods, thus make it quite difficult to see the main reasons for the rather remarkable experiments results.

Summary

This paper trains a transformer to predict Lapunov functions for both polynomial and nonpolynompial dynamical systems. They generate a dataset combining "forward-generated" problems — solutions discovered from existing solvers on randomly generated problems — with "backward-generated" problems — problems generated by generating a random solution, and then building a function solved by the solution. The trained transformer achieves great performance. On a test dataset of randomly generated problems, it solves 12% of problems, compared to 1% solved by the state of the art solver. In addition, the model solves 84% of 75 problems in the FSOTOOLS dataset where human experts only solved 9.33%.

Strengths

- The paper is well-written, and clearly described, so that I could understand it even without having previously encountered Lyapunov functions. - The related work section is good - The dataset generation is very carefully described, and lots of important design decisions are included. There is even more detail in the Appendix. Despite not being an expert, it seems like the authors really know what they're doing, and have rigorously tested different interesting choices of what to include in the dataset. - The results are really cool! The authors test out of domain generalization well, by showing performance on a randomly generated dataset. Indeed, some of the models evaluated were only trained using "ground truth" solver solutions from a different randomly generated dataset. But the model gets 10x higher performance than the ground truth solver on this random dataset. - The big question for papers like this is how well the models generalize out side the train set. Due to the difficult nature of the problem, it's hard to have really good test sets, but the authors are aware of the importance of this, and do lots of OOD generalization tests of their systems, and report positive results. - Again, the authors are quite thorough with their documentation and evaluation of their system. The paper feels very polished and professional and the results are impressive. - Progress on this problem could lead to other work using deep learning for mathematics.

Weaknesses

1. The algorithmic approach is not new — training a transformer to do math problems that a large dataset can be generated for — but this is okay given the careful effort needed and given to the dataset creation process, and the importance and performance of the problem achieved. 2. I find all the different dataset variants included to be a bit confusing. The paper could be easier to read with a reduced the number of variants presented in the main section of the paper. 3. I think the discussion section goes a little far in making suggestions about LLM reasoning ability given success on this dataset. The sentences are true, but it's not necessarily true that performance here is equivalent to reasoning. the transformers are probably doing sometihng more like "intuition" given the amount of data they are seeing and the quickness at which they generate an answer.

Questions

1. findylap solves the same number of problems as SOSTOOLs, right? 2. aren't the other forward datasets also datasets that SOSTOOLS can solve, since its used to generate them? if so, what decision went into the characteristics of the test set over those used for training? 3. are the polynomial systems for FSOSTOOLS homogenous, nonhomogenous, etc? I'm not an expert on the math at all, but those adjectives were used for the train set. I'm trying to understand, because the performance on the test set is the main way of knowing how good a ML model is. but if the test set is too similar to the train set, then the results aren't as meaningful. of course, you have the results on the "random systems" dataset. 4. One idea could be to try to do some sort of expert iteration with your model: use it as the base solver when generating a forward dataset, and use newly solved problems (since it's better at solving than `findylap` on the random systems dataset) to further fine-tune the model. this probably isn't that useful for increasing performance, but it would be a really cool proof of concept to see the performance keep going up on the random systems dataset with some iterations! 5. Is there a real-world (or "real math") application of finding Lyapunov functions? for example, maybe there are some applications. What kind of things do the existing tools get used for, and how might this model be used as a superior version?

Rating

8

Confidence

3

Soundness

4

Presentation

4

Contribution

4

Limitations

The limitations are addressed well in the discussion section.

Summary

This study addresses the problem of designing the Lyapunov function of dynamical systems via learning. The existence of the Lyapunov function is a sufficient condition of the dynamical system's stability. However, its design is not established except for systems with sum-of-square polynomials. The Authors propose a novel dataset construction framework on which Transformer models can be trained. Extensive experiments demonstrate that Transformer models successfully learn to design Lyapunov functions on several types of datasets with moderate generalization ability across datasets. It is also shown that the injection of out-distribution samples in the training set significantly boosts the success rate. Yet restricted to small systems, this study suggests that the learning approach is a promising direction for addressing hard problems of symbolic mathematics.

Strengths

- This study clearly presents the problem and the approach. Overall, the writing is clean and accessible to diverse readers. - A novel backward dataset generation algorithm is proposed to train Transformer models for Lyapunov function design. - The experiments validate the proposed approach from various aspects. Particularly, the generalization across datasets is tested well.

Weaknesses

I appreciate the overall contributions of this study. I'd like to raise two weaknesses, one for the methodology (backward generation) and one for the experiments. **Major comments** Backward generation. While the Author claims that the backward generation is the key innovation, the explanation of the generation process is very limited in the main text. I understand the restriction of pages, but it would be better to elaborate on the method a little more to give intuition to the readers. While the details are presented in Appendix A.2, it mainly provides the procedures, and the rationale is not much given. I was not able to fully understand the procedures either because of the unclarity of several notations (see Minor comments below). Plus, many mapping and transformations appear, but their intention and necessity are unclear to me. I encourage the authors to discuss the range of the Lyapunov function and $f$ covered by the proposed generation method and whether this is large enough or not, including, if any, the important class of functions that cannot be covered for now. As for the experiments, assuming a practical use, it is important to know whether the Lyapunov function given by Transformers is really the Lyapunov function of the targeted system, and if not, whether this is because of a simple failure or the existence of such function. Discussion and experiments seem missing in this part. **Minor comments** *(Markdown math rendering somehow fails in the first item below, so I wrote it in a bit tricky way.)* - Some notations are unclear and inconsistent. For example, vectors $\mathbf{z}$ and $\mathbf{z}_{j}^{i}$ are in bold font, while other vectors such as $x$ are not. The subscript notations $A$ [line 177] and $B$ in Eq. (10) are not defined. Assuming that it refers to the $i$-th entry of vector and $C$ is $D$, the first term of the equation in [line 177] appears to be a scalar while the second term is a vector. The Authors may represent a vector by $E$ in the first term, but still, this is a row vector while the second term is a column vector. $A = (\nabla V)_i(x)$ $B = (\nabla V(x))_{\tau_2(i)}$ $C = (\nabla V)_i(x)$ $D = (\nabla V(x))_i$ $E = (h_{\pi(i)})_i$ - Forward/backward methods and Forward/backward generations are both used. I recommend that the Authors keep terminology consistent. - [line 183] and the is --> and there is - [line 224] .In -> . In - [line 489] What does $Id$ mean (the identity map?)? - [line 492] "$g$ is positive" souds a bit wierd as $g$ is a function. - [line 489] Written $g= 1$ but $g$ is supposed to be a function. - [Eq. 10] Does $\mathbf{e}^i_j$ refers to the $j$-th entry of $\mathbf{e}^i$? Then, it should be unbold as it is a scalar. I also encourage the Authors to include more related works that exploit Transformers to address hard math problems. **Shortest Vector Problem (a series of works by the same group)** - "SALSA: Attacking Lattice Cryptography with Transformers," Emily Wenger, Mingjie Chen, François Charton, Kristin Lauter **Gröbner basis computation** - "Learning to Compute Gröbner Bases," Hiroshi Kera, Yuki Ishihara, Yuta Kambe, Tristan Vaccon, Kazuhiro Yokoyama If not restricted to Transformers, **Detection of terminal singularity** - "Machine learning detects terminal singularities," Tom Coates, Alexander M. Kasprzyk, Sara Veneziale **Integer programming** - "Machine Learning for Cutting Planes in Integer Programming: A Survey," Arnaud Deza, Elias B. Khalil

Questions

I'd like the Authors to answer the weaknesses raised above. Plus, - What do the "pre-defined set of increasing functions" and "pre-defined set of bounded-functions" refer to at [lines 479, 485]?

Rating

6

Confidence

4

Soundness

3

Presentation

2

Contribution

3

Limitations

Limitations are adequately presented. For the potential improvements, see Weakness and Questions.

Post-rebuttal

Thanks for the responses and the newly added experiments. After reviewing them, I remain unconvinced by the comparisons and the supporting arguments presented. Additionally, the references provided in the responses are difficult to locate and follow in their current format. I personally still do not see significant contributions to the community (at least in my community). - As I stated in my previous comments, finding Lyapunov function candidates for nonlinear systems is not hard. We can use neural networks or other methods to find one (candidate) easily. The critical issue lies in guaranteeing the correctness of these functions. The proposed method cannot address this problem. As the authors themselves stated, the outputs of the transformer model still require formal verification via SOS or SMT solvers, if one needs to ensure their correctness. In addition, for the neural network method in the “Neural Lyapunov Control” paper, I believe that modifying the neural network structure slightly and removing the feedback control component u should yield better accuracy. The claim that the accuracy should be as low as suggested is questionable, especially since FOSSIL is built on this framework, and the case without control input should be easier to solve for low-dimensional systems. - I also strongly doubt the claim that it can be used to find a Lyapunov function "for any system". The results are unlikely to generalize to arbitrary nonlinear systems. The systems must likely fall within the categories represented in the training dataset, given the generalization limitations of neural networks. Moreover, I struggle to envision a scenario where generating a Lyapunov function in a rapid, "plug-and-play" manner would be necessary. - Furthermore, the authors argued that the proposed method has better performance in finding global Lyapunov functions. This raises the question of why finding a global Lyapunov function is more important (than the other two). In which practical scenarios, such as robotics or power systems, do we need the global Lyapunov function? It’s better to further clarify the significance of this contribution further. - While it is true that exercises in control theory courses or publications often involve finding Lyapunov functions by hand, all of them are in a particular structure and definitely not any general nonlinear systems. Given that this paper aims to solve a mathematical problem using machine learning methods, it is crucial that it be written with rigor, as the authors themselves acknowledge. In my opinion, the current version is not ready for publication, and I would like to keep my score unchanged.

Response to rebuttal

Thank the authors for providing detailed response to all the questions. I will also increase my score to 5.