Verifying Neural Networks with Reinforcement Learning

Conference: NeurIPS 2026
arXiv: 2609.34553
Area: Reinforcement Learning
Keywords: neural network verification, branch-and-bound, heuristic reweighting, dual-successor reinforcement learning, graph neural networks

TL;DR

Rsb uses graph-structured observations and actor-critic learning to reweight Fsb neuron-branching scores without replacing verification logic, increasing solved problems from 148 to 165 among 600 challenging test instances, although inconsistencies in rewards, feature masks, and some statistics need to be distinguished from the performance gains.

Background & Motivation

Formal neural network verification does not merely check a collection of test inputs: it determines whether any input within a specified set violates an output property. Branch-and-bound (BaB) first computes bounds through abstraction; when those bounds cannot rule out a counterexample, it fixes an unstable neuron's status more precisely and creates two subproblems. For a ReLU, instability means that its pre-activation interval crosses zero, requiring active and inactive cases. Bounding provides the proof mechanism, whereas branching determines how much search that proof requires; these roles should not be conflated.

Fsb scores candidate neurons according to potential bound improvements and is widely used in mature verifiers. Its weakness is not an absence of expert knowledge, but the mismatch between local bound improvement and the size of the subsequent search tree: one split may remove only a local uncertainty, while another stabilizes several downstream neurons. Learning a replacement scorer from scratch risks discarding existing heuristic knowledge and must accommodate changing network sizes, shrinking candidate sets, and expensive verification interactions.

The paper therefore learns corrections to existing scores rather than rebuilding the verifier. A GNN captures structural relationships, local interval features reflect the current property and branching constraints, and a policy changes candidate priorities using feedback from subsequent search. Core Idea: let learning decide which neuron to split first to reduce search, leave property judgments to the existing sound verifier, and account for both successors of each split during value learning.

Method

Overall Architecture

The inputs are a network, input constraints, an output property, and accumulated branching constraints; the output remains the original verifier's property judgment rather than an actor classification. For a subproblem not resolved by bounding, Rsb constructs candidate observations, generates weights, multiplies them elementwise with Fsb scores, and splits the highest-scoring neuron. Both children are still processed by the existing bounding and queue-management procedures.

Training and verification inference must be separated. The GCN is first pretrained with Fsb score supervision, after which the actor and twin critics learn from dual-successor verification experiences. At test time, weights are frozen without per-network fine-tuning, and neither critics nor rewards determine property validity. Solid arrows below denote verification data flow; dashed arrows denote training supervision or parameter updates.

%%{init: {'flowchart': {'rankSpacing': 24, 'nodeSpacing': 28, 'padding': 6, 'wrappingWidth': 400}}}%%
flowchart TD
    I["Network, property<br/>current split constraints"] --> A["Structure-Enhanced<br/>Observations"]
    S["Fsb scores<br/>GCN pretraining supervision only"] -.-> A
    A --> B["Variable-Length<br/>Score Reweighting"]
    H["Current Fsb scores"] --> B
    B --> D["Original verifier<br/>split and bound both children"]
    D -->|Unresolved subproblems| A
    D --> O["Proof, counterexample,<br/>or unresolved budget exhaustion"]
    D -.->|Training reward and both successors| C["Dual-Successor<br/>Value Learning"]
    C -.->|Actor updates during training only| B

The three designs correspond, in order, to observations, actions, and value learning. The original verifier is retained scaffolding, not a new proof module introduced by this paper. The policy can change which neuron is selected, but cannot declare an unresolved subproblem proved.

Key Designs

1. Structure-Enhanced Observations: combine current intervals with neuron relationships

Different input domains or output properties can produce different hidden-layer intervals even for the same network, so a cached static topology embedding alone cannot represent the verification state. The paper models every neuron as a graph node and network connections as edges, using pre-activation lower and upper bounds, bias, and a binary mask as raw features. The GCN regresses Fsb scores on unstable neurons with a mean-squared-error pretraining objective, and the resulting candidate embeddings are supplied to the policy. This is not actor supervision with optimal branching labels; it first lets structural representations absorb an existing heuristic's signal.

Raw features have only 4 dimensions, whereas structural embeddings are wider. The paper projects raw features to the embedding width, concatenates them with GCN embeddings, and projects the concatenation again so that local intervals are not overwhelmed by a high-dimensional structural representation. The final policy input retains only current unstable candidates, supporting changing network and candidate-set sizes. However, the GCN graph contains all neurons, so this does not establish that all computation is confined to a candidate-only subgraph.

A naming inconsistency matters for reproduction: the worked example explicitly defines the mask as 1 for unstable and 0 for stable, and Appendix Table 3 calls it an unstable mask; §4 and §5.1 instead describe branching history or branching status. Stability and previous branching are not generally the same variable, so these descriptions should not be silently merged. This note uses the neutral term “binary neuron mask” and records both definitions; without implementation evidence, its actual semantics cannot be determined. It must also be distinguished from training masks indicating whether successor search continues.

2. Variable-Length Score Reweighting: retain Fsb knowledge while changing priorities

The actor uses a PointerNet-style encoder–decoder rather than a fixed-dimensional output layer. The encoder reads candidate observations, and a decoder query attends to candidate reference vectors to produce weights. The appendix additionally specifies an LSTM, attention glimpses, logits clipped to plus or minus 10, and a softmax over admissible candidates. The selected neuron's features become the next decoder state, allowing subsequent decisions to incorporate earlier selections. The pointer mechanism can still score the remaining candidates when their number shrinks.

The executed neuron selection is:

\[ n^{*}=\arg\max_{n\in\mathcal{N}_{u}}\omega_n a_n. \]

Here \(\omega_n\) is the original heuristic score and \(a_n\) is the actor weight. Attention neither replaces the verification score outright nor represents a neuron's probability of satisfying the property: priority is determined by the product. This can suppress a locally high-scoring candidate with expensive descendants while retaining Fsb's expert estimate of current bounds. The experiments specifically evaluate Fsb reweighting; proposed compatibility with other heuristics is not empirical evidence that every heuristic benefits.

Both critics also use PointerNet-style structures with independent parameters and initialize their decoders from the actor's current decoder state. The main text describes Q-values for candidates, while the appendix emphasizes scalar outputs for branch-child pairs. The established role is to evaluate future branching returns, not to produce a property proof. The appendix uses twin Q-networks and pessimistic targets to mitigate overestimation, with slowly averaged target-network updates.

Changing split order preserves coverage of the original problem by its two children and does not change bounding soundness. The paper's soundness/completeness argument assumes the underlying BaB logic is preserved and all necessary branches are explored; it does not guarantee termination within a finite budget. Under the 120-second limit, a timeout is unresolved, not evidence that the property is invalid. SAT requires a counterexample from the underlying verifier, and UNSAT requires sound exclusion or proof.

3. Dual-Successor Value Learning: account for the search cost of both children

A conventional trajectory transition often stores a current state, action, reward, and one next state. A BaB split instead creates positive and negative successors, and proving a property usually requires excluding both rather than following one randomly chosen child as a proxy for the entire workload. Rsb therefore stores both successor observations and their masks in the same replay transition so that value targets include both sides that still require search. This adaptation to a search tree should not be described as an ordinary single-successor rollout.

The following conceptual target explains the mechanism of Eq. 10; it is not a verbatim reconstruction of the damaged formula in the cache:

\[ y_t=r_t+\gamma\left(c_{+}V_{\mathrm{target}}(o_{+})+c_{-}V_{\mathrm{target}}(o_{-})\right). \]

Here \(c_{+},c_{-}\) are 1 for an unresolved child and 0 otherwise, and \(V_{\mathrm{target}}\) is expected target-critic value under the policy. The text after Eq. 10 likewise states that a zero mask means a solved child with no future value. Earlier experience descriptions call these termination masks without making the convention clear. Reproduction must therefore establish whether the implementation uses continuation or termination masks, rather than mechanically substituting a “1 means terminal” convention.

The reward discrepancy is more substantial. §4 Eq. 8 and its explanation give +1 for each resolved child and claim that maximizing discounted return is equivalent to minimizing generated subproblems. Algorithm 2 line 11 and §5.3 instead use the negative number of unresolved children. Appendix C.1 only adds normalization by a fixed maximum number of visited subproblems, while Appendix B gives generic actor-critic objectives; neither resolves the relationship between the reward descriptions.

Independent analysis shows that, even with exactly two children per split, resolved-child count and negative unresolved-child count merely differ by a constant 2 at a single step. Policies change the number of splits and the discounted horizon, so equivalence of the cumulative objectives does not follow. In a simplified complete binary UNSAT tree without additional early termination, extra splits also increase the number of terminal leaves. This note therefore retains the stated intention of penalizing future search workload, but does not treat the positive-reward equivalence as an established theorem or silently repair the authors' equation.

A Worked Example

For the small network in Fig. 1, whenever \(x_1\in[-2,2]\) and \(x_2\in[-1,1]\), the verifier aims to prove \(y_1>y_2\). The initial abstraction leaves three unstable ReLUs: \(n_{11},n_{21},n_{22}\). This example illustrates priority changes; it is not an average experimental effect.

Initial Fsb scores are 0.3, 0.5, and 0.1, respectively, so Fsb first splits \(n_{21}\). Its negative child is excluded immediately, while its positive child remains unresolved. A subsequent split on \(n_{11}\) completes the proof, requiring two splits and four branch children in total.

Rsb assigns weights 0.6, 0.3, and 0.1, producing products 0.18, 0.15, and 0.01 and prioritizing \(n_{11}\). Both children are resolved by the original bounding procedure in this example, so one split and two children suffice. The actor does not declare the network safer; it moves forward a split that constrains several downstream neurons, after which the same verification logic establishes the result.

Training experiences also differ: the first choice leaves one child requiring additional search, whereas both children of the second have no future search cost. A dual-successor target expresses this difference. Sampling only a resolved child could make the first choice appear as good as the second.

Loss & Training

The critics learn values by minimizing squared error against dual-successor Bellman targets, while the actor maximizes critic-estimated action value:

\[ \mathcal{L}_{\pi}(\psi)=\mathbb{E}_{o\sim\mathcal{D},\,a\sim\pi_{\psi}(\cdot\mid o)}[-Q_{\phi}(o,a)]. \]

The appendix calls this a SAC variant retaining off-policy reuse and twin Q-networks. The stated actor objective has no explicit entropy term of standard maximum-entropy SAC, so a temperature parameter or entropy loss should not be supplied solely from the algorithm citation.

The authors generate 480,960 FNN verification instances, remove instances for which PGD finds counterexamples, and then use LiRPA to remove easy-to-prove instances, leaving 14,454 challenging training problems. Failure to find a counterexample with an attack does not prove UNSAT: these filters enrich the set for nontrivial branching rather than provide a new complete decision procedure. Training runs for 100,000 episodes and takes several days on a single GPU.

GCN pretraining uses two layers, hidden width 128, ReLU, Adam with learning rate \(3\times10^{-4}\), 5 epochs, and batch size 512. RL uses AdamW, actor and critic learning rates of \(4\times10^{-4}\), discount \(\gamma=0.99\), replay capacity \(10^5\), batch size 512, and accumulation over 8 minibatches.

There are 2 critic updates per policy update, with target averaging coefficient \(10^{-4}\). The first \(10^3\) environment steps use heuristic warm-up; the appendix also permits optimization when the buffer becomes half full and occasionally inserts heuristic actions afterward. At test time, weights are frozen and one policy is shared by all instances, with no test-time critic updates or per-network adaptation.

Key Experimental Results

Main Results

The test set has 200 challenging instances each for FNN, CNN, and Sigmoid networks, totaling 600. The latter two network groups are absent from training. FNN tests share network architectures with training but use different properties, so they should not be described as generalization to wholly new networks. All heuristics are integrated into NeuralSAT and run on a 32-core Threadripper, 128 GB RAM, and an RTX 4090, with a 120-second limit per instance.

The following results come from Table 2. Time and branch statistics are restricted to the subset solved by at least one method, not unconditional totals over all 600 instances. Branch counts are in millions.

Benchmark	Method	Solved	Time (seconds)	Branches (millions)
FNN	Polarity	1	6064.32	170.81
FNN	Upb	23	4359.36	27.17
FNN	Fsb	43	2679.00	6.65
FNN	Rsb	50	2051.94	1.86
CNN	Polarity	0	8662.55	583.01
CNN	Upb	71	2387.48	1.73
CNN	Fsb	71	2295.89	1.81
CNN	Rsb	72	2419.58	1.69
Sigmoid	Polarity	10	6027.70	62.98
Sigmoid	Upb	39	3963.69	8.59
Sigmoid	Fsb	34	4336.73	8.99
Sigmoid	Rsb	43	3450.80	5.14

Summing this table gives 165 solved instances for Rsb versus 148 for Fsb: 17 more, or approximately 11.5%. Branch counts decrease from 17.45M to 8.69M, approximately 50.2% fewer. These percentages are calculated in this note from the table; the paper summarizes them as 11% and 50%.

Upb's table entries sum to \(23+71+39=133\), but §6.2 states a total of 110. That number also equals its CNN-plus-Sigmoid total. The paper does not confirm the source of the error, so this note preserves the table entries and explicitly records the discrepancy rather than using 110 as the all-benchmark total.

Ablation Study

The paper provides no module-ablation table removing the GCN, raw features, reweighting, or dual-successor training. The following summarizes statistical and efficiency analyses from §6.4, not causal ablations. The five runs vary benchmark-generation seeds and should not be relabeled as five training seeds.

Analysis	Rsb	Comparison	Evidence and scope
Median solved count over five runs	150	Fsb 140; Upb 125	Fig. 5 / §6.4; distinct from Table 2's 165
Decision time per step	About 0.11 seconds	Fsb and Upb about 0.13 seconds	Approximate text values with differing workloads
Example active-subproblem batch	32	64	An illustration of scoring workload, not fixed settings
Median branch-count order	About \(10^4\)	Fsb about \(10^4\)	Rsb distribution is lower and tighter; not total branches
Solved count on unseen networks	115	Fsb 105; Upb 110	CNN and Sigmoid combined, not the entire test set
Independent module contributions	Not reported	Not reported	Contributions of GCN, reweighting, and dual successors cannot be isolated

Key Findings

• Gains concentrate on FNN and Sigmoid, with 7 and 9 additional solved instances, respectively; CNN gains only 1. This supports transfer across the tested architectures, not universal generalization across sizes or activation functions.
• CNN runtime is 2419.58 seconds for Rsb versus 2295.89 seconds for Fsb, despite somewhat fewer branches. The method is therefore not faster on every benchmark, and a smaller search tree does not guarantee lower wall-clock time.
• Lower per-step decision time is attributed to smaller queues and scoring batches, not to neural inference having zero cost. No controlled experiment establishes that Rsb remains faster at a fixed identical subproblem batch size.
• The authors report distributional stability across five runs but provide no formal significance test or confidence interval. Statistical analysis should not be upgraded to proof of statistical significance.

Highlights & Insights

• Separate learning from proof: a poor policy primarily changes computational workload rather than acquiring the authority to accept or reject a property. This interface suits learning-augmented solvers with explicit soundness boundaries.
• Learn corrections instead of replacing everything: Fsb already encodes expert judgments about bound improvement, and reweighting preserves that reference. The transferable idea is to learn state-dependent heuristic preferences, not merely a more elaborate static scorer.
• A search tree is not a trajectory: both children in proof-oriented search may consume resources. Experience structures and value backups should match how work actually expands rather than reuse single-successor training without modification.

Limitations & Future Work

• Reward signs, cumulative-objective equivalence, and mask semantics remain unresolved, limiting objective reproducibility. Implementations, return definitions, and complete stopping conditions should be released, together with checks connecting optimized returns to branch counts.
• Missing module ablations prevent attribution of the final gains. Matched-instance, matched-budget tests could separately remove structural embeddings, raw-feature projection, Fsb multiplication, and dual-successor backups.
• Challenging-instance filtering targets branching performance but does not represent average gains across general verification workloads. The paper notes that 2473 of 2700 regular-track VNN-COMP'25 instances needed no branching or very few steps; deployment evaluation should also cover the full distribution.
• Training takes days, with no quantified amortization and limited coverage of large modern networks. Learned-policy inference and graph-processing overheads with additional candidates require separate measurement.
• Input-space branching and online adaptation during verification are future directions proposed by the authors, not demonstrated results. Online adaptation should retain the boundary that prevents learned outputs from directly replacing the proof kernel.

Related Work & Insights

• vs Fsb / Upb: Fsb estimates bound improvement, while Upb approximates it more cheaply; Rsb learns weights on Fsb scores. CNN results reinforce the need to evaluate solved count, branch count, and runtime together rather than relying on one metric.
• vs the GNN branching heuristic of Lu and Kumar: both exploit structural learning, while this paper additionally emphasizes existing-score corrections and long-term value learning. That GNN method is not directly compared in the result table, so comprehensive superiority under matched conditions is not established.
• vs tighter abstractions, cutting planes, and stability-oriented training: these improve bounds or reduce unstable candidates, whereas Rsb improves split selection, making them complementary in principle. Actual combined benefits require experiments rather than being implied by interface compatibility.
• vs one-shot GNN guidance for SAT: one-shot guidance chiefly reduces repeated model calls, whereas the policy here uses current intervals and search state. Reusing structural encodings while updating state features is worth exploring after separately profiling graph encoding and scoring costs.

Rating

• Novelty: 4/5 — The combination of heuristic reweighting and dual-successor value learning is clear, although learned branching has precedents.
• Experimental Thoroughness: 3/5 — There are 600 challenging instances and cross-architecture analyses, but module ablations, objective validation, and complete cost analysis are missing.
• Writing Quality: 2/5 — The main workflow is understandable, but inconsistencies in rewards, masks, Upb totals, and generalization wording hinder precise reproduction.
• Value: 4/5 — The results show that learning can improve search efficiency in a mature verifier without taking over proof logic.