Research map / Learning theory and algorithms / Combinatorial and search optimization
Global Lyapunov functions: a long-standing open problem in mathematics, with symbolic transformers
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Generates synthetic stable dynamical systems by backward sampling from random Lyapunov functions and trains sequence-to-sequence transformers to predict global Lyapunov functions, outperforming SOSTOOLS-style solvers and AI baselines on polynomial systems and discovering new Lyapunov functions for non-polynomial systems.
Problem
Finding global Lyapunov functions that certify global stability of dynamical systems, a long-standing open problem with no general algorithm; existing solvers only handle small polynomial systems and AI methods target local/semi-global functions.
Approach
Backward data generation: sample a random Lyapunov function V first, then build a system f = -(h^2 ∇V) + orthogonal term so that ∇V·f ≤ 0 by construction; train transformers on these (system, V) pairs, mixing in a few hundred forward-generated SOS examples to improve out-of-distribution accuracy.
Key results
- PolyMixture (BPoly + 300 FBarr) reaches 84% on FSOSTOOLS versus 15% for findlyap on BPoly test set.
- On random polynomial systems, the best model discovers Lyapunov functions for 11.8% (degree 3) and 10.1% (degree 5) of systems, versus 1.1% and 0.7% for findlyap.
- On non-polynomial systems, the best model finds Lyapunov functions for 12.7% of systems; human master students scored 9.33% on a 75-problem exam.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add 300 FBarr examples to BPoly training data (ablation) | BPoly model · FBarr | accuracy: 35 -> 89 | Helped |
| Add 300 FBarr examples to BPoly training data (ablation) | BPoly model · FLyap | accuracy: 73 -> 83 | Helped |
| Add 100 FLyap examples to BPoly training data (ablation) | BPoly model · FBarr | accuracy: 35 -> 29 | Hurt |
| Fine-tune with 1,000 verified FIntoTheWild predictions (ablation) | PolyMixture model · Poly3 | discovery rate: 11.7 -> 13.5 | Helped |
| Fine-tune with 1,000 verified FIntoTheWild predictions (ablation) | PolyMixture model · FBarr | accuracy: 93 -> 92 | No clear effect |
| Fine-tune with 5,000 FIntoTheWild examples instead of 1,000 (ablation) | PolyMixture model · FBarr | accuracy: 93 -> 85 | Hurt |
| Fine-tune with 5,000 FIntoTheWild examples instead of 1,000 (ablation) | PolyMixture model · Poly3 | discovery rate: 13.5 -> 13.5 | No clear effect |
| Fine-tune with mixed data including FIntoTheWild (ablation) | PolyMixture model · Poly3 | discovery rate: 11.7 -> 10.3 | Hurt |
| Train from scratch with BPoly, FBarr, FLyap, and FIntoTheWild data (ablation) | Transformer · Poly3 | discovery rate: 11.7 -> 12.1 | Helped |
| Train with 5 systems per Lyapunov function rather than 1 (ablation) | BPoly model · FLyap | accuracy: 58 -> 73 | Helped |
| Increase multigen from 5 to 50 (ablation) | BPoly model · FLyap | accuracy: 73 -> 70 | Hurt |
| Use beam size 50 instead of greedy decoding (ablation) | low-performing models · Held-out test sets | accuracy: 7 to 10% | Helped |
Surprising findings
- Adding only 300 forward barrier-function examples to 1M backward examples raises FBarr accuracy from 35% to 89%, despite being 0.03% of training data.
- Generating multiple systems per Lyapunov function (multigen) improves OOD accuracy up to a threshold, after which performance declines.
Limitations
- No benchmark ground truth for stability of non-polynomial systems, since stability is undecidable in general for them
- Only small systems (up to 5 equations for polynomial, 3 for non-polynomial) were studied
- SOS and SMT verifiers time out on some correct solutions, so accuracy may be underestimated
Experimental setup
Datasets: BPoly BNonPoly FBarr FLyap FSOSTOOLS Poly3 Poly5 NonPoly
Benchmarks: BPoly BNonPoly FLyap FBarr FSOSTOOLS Poly3 Poly5 NonPoly
Metrics: accuracy (beam size 1 and 50) fraction of random systems with discovered Lyapunov function SMT and SOS verification timeout rate
Baselines: findlyap Fossil 2 ANLC v2 LyzNet SOSTOOLS
Builds on: SOSTOOLS Lyapunov's stability theory Deep Lyapunov function learning (Lyznet, Fossil 2)
Closest papers by meaning
- Analytical Lyapunov Function Discovery: An RL-based Generative Approach (ICML 2025 · similarity 0.91)
- Learning-enabled Polynomial Lyapunov Function Synthesis via High-Accuracy Counterexample-Guided Framework (CVPR 2025 · similarity 0.88)
- Stability Analysis of Switched Linear Systems with Neural Lyapunov Functions (AAAI 2024 · similarity 0.85)
- Learning Neural Contracting Dynamics: Extended Linearization and Global Guarantees (NeurIPS 2024 · similarity 0.83)
- Lyapunov-stable Neural Control for State and Output Feedback: A Novel Formulation (ICML 2024 · similarity 0.83)
- ODEFormer: Symbolic Regression of Dynamical Systems with Transformers (ICLR 2024 · similarity 0.83)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.