Networks of repeated neural modules with delayed neighbour coupling need stability guarantees for every number of modules, but delay-dependent criteria certify one network at a time and grow with its size. This paper derives stability and L2-gain certificates of length-independent size for open chains and rings of modules of two alternating types with slope-restricted activations. A local and a transmission delay act independently and are only bounded and continuous. A Lyapunov-Krasovskii functional with fixed integration limits and module-local variables that repeat with the module type reduces the certificate of every chain to one cell of two modules. Local conditions and a single linear matrix inequality of order 96 on this cell, or 104 for the gain, certify global asymptotic stability and a common L2-gain bound for all open chains and all rings with an even number of at least four modules. Up to a margin, the stability inequality is also necessary for the repeated variables to certify every length. All uniform certificates, including certified coupling regions, are verified in exact rational arithmetic. In the numerical study, the certified coupling reaches 92% of an outer bound given by unstable members of the model class for short delays and 79% at the nominal delay bounds. For 16 modules at unit coupling strength, certificates of the same functional computed for that length alone raise the certified delay scale by 2% to 7% in four cases. A single stability problem with 1298 scalar variables thus replaces per-length certification of long chains at little cost.
Figures & tables
Figure 1: Open chain of modules of types 1 and 2. Loops mark the local feedback through At and B1,t , arrows the delayed couplings Ff and Fb , and dashed boxes the cells. In cell order, the certificate matrix is block tridiagonal with the cell blocks Ξ0 and Ξ1 (Lemma 3 ).
Figure 2: (a) Certified region in the (κ,s) plane for (Ff,Fb)=(κG^,−κG^⊤) . The shaded set is the union of the exactly verified rectangles [κ−,κ+]×[0,s] of Corollary 1 and holds for every network in N , and its gray part is certified also for Tab=0 . Markers give the couplings at which unstable members are found for constant delays ( κout ), and the outer staircase through them bounds κsafe from above (Section 4.5 ). (b) Ratio of the certified gain γ^ to the lower bound γlb on the coupling cells of (a) for three delay scales.
Figure 3: Certified bounds τˉ1 on the local delay and τˉ2 on the transmission delay for κ=1 . Each marker, including the diamond for the common delay bound dˉ⋆=15/16 of Section 5.6 , is an exactly verified certificate of Theorem 2 and covers the box between it and the origin. The shaded set is the union of these boxes, and its gray part is certified also for Tab=0 .
Figure 4: (a) Price of uniformity sN⋆/s⋆ for block-central and central certificates. (b) Block-central gain bound γN for I1 relative to γ^ . (c) Wall times at κ=1 and s=1 , median and range of five runs. At N=64 , the construction of the chordal problem exceeds the address-space limit.
I1
I2
I3
γ^2 , Theorem 2
241/50
77/20
667/100
γ^ , Theorem 2
2.196
1.963
2.583
γ^ , Theorem 2 with Tab=0
6.849
7.881
15.621
γ^ , Remark 3
2.115
1.908
–
γlb
1.419
1.346
1.586
γlbtv
1.653
1.525
1.732
Table 1: L2 -gain bounds at s=1 . Upper bounds are rounded up and lower bounds down. The variant of Remark 3 was not computed for I3.
Zhai et al. (2025)
Thm. 1
Rem. 3
Thm. 2
Rem. 3
N
2
2
4
2
all
all
κ=1/2
≥8
21/4
61/16
231/32
17/8
81/32
κ=1
11/2
25/8
7/4
137/32
15/16
33/32
κ=5/4
63/16
39/16
5/4
53/16
21/32
11/16
variables
2544
110
396
136
1298
4862
LMI order
76
28
56
28
96
96
Table 2: Certified common delay bound dˉ⋆ and problem size. Values for one N are verified in double precision and values for all N exactly. The bound 8 is the search limit. The variant of Remark 3 for all N has four LMIs of order 96.
Multi-agent large language model (LLM) systems often rely on verifier and critic agents to suppress hallucinations, but verification is delayed. During this delay, false claims can propagate through the agent network. We model this process as delayed consensus on a graph with grounded corrector nodes. Spectral decomposition by the grounded Laplacian yields a closed-form stability threshold for the verification dose: correction that is too strong or too delayed can turn consensus into oscillation. The most unstable regime occurs when the communication and verification delays coincide; for delay two, the threshold is the inverse golden ratio. The same framework gives a supermodular placement objective and a greedy (1-1/e)-approximation rule for assigning a limited corrector budget to influential nodes. Experiments across five open models confirm the predicted dose-delay oscillations. By contrast, grounded factual answering makes truth an absorbing boundary and eliminates the effect, suggesting that the instability is specific to signed-belief tasks while grounded verification remains stabilizing
Semidefinite programming (SDP) certificates for feedback systems containing deep neural networks (NNs) typically scale with the total number of neurons, whereas small-gain tests are scalable but can be highly conservative. This paper develops a unified and scalable framework for incremental robust stability and performance analysis of feedback interconnections involving high-dimensional NNs and unmodeled dynamics. By combining a structured decomposition of the full-order SDP condition with scalable Lipschitz constant estimation algorithms, we derive reduced verification conditions that certify incremental convergence and incremental ℓ2-gain bounds. The dimensions of the resulting control-analysis linear matrix inequalities (LMIs) depend only on the widths of the last two network layers and are independent of network depth. The framework preserves the coupling between the plant and the NN, with the incremental small-gain condition recovered as a special case. To further reduce conservatism, we develop a multi-round alternating update scheme that iteratively refines the coupling variables while preserving scalability. Numerical experiments show that the proposed framework achieves state-of-the-art incremental ℓ2-gain bounds for large-scale NN feedback systems.
Zichen Wang, Peter Seiler, Geir Dullerud +1
Coordinated Science Laboratory and the Department of Electrical and Computer Engineering, University of Illinois Urbana–Champaign · Department of Electrical Engineering and Computer Science, at the University of Michigan · Electrical and Computer Engineering Department at the University of Minnesota
Existing linear program (LP) and semidefinite program (SDP) relaxations for rectified linear unit (ReLU) neural network (NN) verification yield overly-conservative safety guarantees due to significant relaxation gaps. While the completely positive program (CPP) formulation closes this gap, it is NP-hard to solve. Its cheapest tractable relaxation, the doubly non-negative program (DNN), retains critical constraints as an SDP, but one whose size exceeds the reach of interior-point methods at practical scale. While Burer-Monteiro (BM) factorization has been applied to make SDP-based verification scalable, no such result exists for the strictly tighter DNN formulation. A key obstacle is that additional non-negativity constraints in the DNN cause dual multipliers for optimality certification to be non-unique, making standard certification methods inapplicable. We propose a novel eigenvalue maximization procedure that searches the non-unique multiplier space for a valid certificate, i.e. a global optimality guarantee. Experiments demonstrate that our approach (DNN)2 produces bounds consistently tighter than the standard SDP method, often matching the exact solution, and that our certification procedure confirms global optimality when a valid certificate exists. These results are a key step toward providing tight, certifiable, and computationally scalable verification guarantees needed to deploy neural network controllers and perception modules in safety-critical autonomous systems.
Hanna Jiamei Zhang, Alan Papalia, Michael Everett +1
Departments of Computer Science, Electrical and Computer Engineering, and Mathematics Northeastern University, Boston, MA. · Department of Naval Architecture and Marine Engineering, University of Michigan, Ann Arbor, MI.