💻 computer science

The Machine Proposes. The Proof Disposes: Neuro-Symbolic Synthesis of Formally Verified Markov Usage Models from Natural Language Requirements

This paper introduces Neuro-Symbolic MBST, a framework that automates the synthesis of formally verified Markov usage models from natural language requirements by integrating L* learning, grammar-constrained LLMs, and convex optimization, thereby achieving high-fidelity fault detection and coverage that significantly outperforms pure-neural baselines while eliminating manual modeling bottlenecks for safety-critical systems.

Original authors: Nathan Ginting

Published 2026-07-28

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Nathan Ginting

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are trying to teach a robot how to drive a car or navigate a website. To do this safely, you need a map of every possible move the robot can make. In the world of software testing, this map is called a "usage model." It's like a flowchart that shows every state the system can be in (like "braking" or "shopping cart full") and the probability of moving from one state to another (like "80% chance the user clicks 'buy'").

For decades, experts have used these maps to run "statistical tests." Instead of just checking if the code works once, they use the map to simulate thousands of random journeys through the system. If the map is accurate, the tests will find hidden bugs that only appear in rare, tricky situations. However, there's a huge problem: drawing these maps by hand is slow, boring, and prone to human error. It's like trying to draw a detailed map of a whole city while blindfolded. Recently, we've had a new tool: Artificial Intelligence (AI) that can read text and guess what the map should look like. But here's the catch: AI is great at guessing the shape of the map, but it's terrible at getting the numbers right. It might draw a road that doesn't exist, or say there's a 150% chance of rain (which is impossible). This paper asks: Can we combine the AI's creativity with a strict mathematical "rulebook" to build a perfect map automatically?

The paper, titled "The Machine Proposes. The Proof Disposes," introduces a new system called NeSy-MBST. Think of it as a team-up between a creative writer and a strict math teacher. The "writer" is a Large Language Model (LLM), an AI that reads natural language requirements (like "the user should be able to add items to the cart") and proposes a draft map of the system. The "math teacher" is a symbolic solver, a computer program that checks the draft against the laws of mathematics.

Here is how the team works together:

The Proposal: The AI reads the requirements and sketches out the states and transitions. It's fast and understands human language well.
The Proof: The math teacher immediately checks the sketch. Did the AI invent a transition that is physically impossible? Did it forget a step? The teacher says, "No, that road doesn't exist," or "You missed a turn."
The Fix: The AI gets the feedback, fixes the map, and tries again.
The Numbers: Once the map shape is perfect, the math teacher takes over to assign the probabilities. Instead of the AI guessing numbers (which often leads to errors), the teacher uses a "convex optimizer" to calculate the exact probabilities so that they add up to 100% correctly and reflect real-world usage.

The researchers tested this system on two types of challenges: an autonomous vehicle (a self-driving car system) and two e-commerce websites (a user shopping page and an admin dashboard). They compared their new "team-up" system against using just the AI alone and against traditional manual methods.

The results were impressive. When using just the AI, the system missed about half of the important paths and made errors in the map structure. But with the NeSy-MBST team-up, the system achieved a score of 0.9125 on a scale where 0.90 is the safety threshold required for critical systems like self-driving cars. This means the AI alone wasn't good enough, but the team-up passed the safety test.

Specifically, the new system managed to cover 85.7% of the possible transitions (the paths the system can take), whereas the AI-only version only covered 50%. This is a massive 35.7 percentage-point gain. In plain English, the new system found a much wider variety of potential bugs because it didn't miss the "dead ends" or "impossible roads" that the AI alone kept hallucinating.

The paper also looked at how well the system got the numbers right. It used a metric called Jensen–Shannon divergence to measure how close the AI's probability guesses were to the real math. The new system achieved a score of 0.012, which is extremely close to perfect, while the AI-only version was much further off at 0.157. This proves that the math teacher successfully fixed the AI's bad math.

The researchers ran a special experiment called an "ablation study" to see which part of the team was doing the heavy lifting. They found that the symbolic verification loop (the math teacher checking the map structure) was the main reason the system found so many more paths. The convex optimizer (the math teacher doing the probability calculations) was the main reason the numbers were so accurate. The closed-loop feedback (where the system learns from running tests) helped a little bit, but the core magic was in the initial team-up.

In conclusion, this paper suggests that we don't have to choose between the speed of AI and the safety of human experts. By letting the AI propose ideas and a strict mathematical system verify and correct them, we can build software testing maps that are both fast to create and safe enough for critical systems. The authors note that while this works very well for the systems they tested (up to 42 states), more work is needed to see if it scales to massive, complex industrial systems. But for now, they have shown that "The Machine Proposes" is a great start, as long as "The Proof Disposes" of any mistakes before the final map is used.

Technical Summary: Neuro-Symbolic Synthesis of Formally Verified Markov Usage Models

1. Problem Statement

The primary bottleneck preventing the widespread adoption of Model-Based Statistical Testing (MBST) beyond safety-critical niches is the manual construction of Markov chain usage models. These models are essential for shifting testing objectives from absolute code coverage to statistical inference regarding expected field quality. However, translating ambiguous, unstructured natural language requirements into verified state-transition topologies and mathematically consistent probability matrices requires significant formal methods expertise.

While Large Language Models (LLMs) have demonstrated syntactic extraction capabilities, purely neural approaches suffer from four critical limitations when applied to MBST:

Stochastic Volatility & Hallucination: LLMs may omit critical edge cases, construct impossible transitions, or violate system invariants, leading to invalid test cases.
Calibration Failure: LLMs struggle with precise numerical reasoning, often failing to satisfy the strict row-stochastic constraints ( $\sum_j p_{ij} = 1$ ) and complex multi-variable constraints required for valid Markov chains.
State-Space Explosion: LLMs operating within finite context windows cannot effectively track or generate highly concurrent, multi-stream transition models without losing structural coherence.
Semantic-Feasibility Divergence: LLMs excel at semantic progress but frequently violate physical and logical feasibility constraints (e.g., executing a checkout transition with an empty cart), generating paths that are semantically logical but physically unexecutable.

Existing literature lacks an end-to-end evaluation of whether automated model construction can preserve the structural and probabilistic properties necessary for MBST's fault-detection guarantees.

2. Methodology: The NeSy-MBST Framework

The paper introduces Neuro-Symbolic Model-Based Statistical Testing (NeSy-MBST), a hybrid framework that decouples semantic parsing from mathematical constraint resolution. The architecture integrates five tightly coupled stages:

A. Progress-Feasibility Dual-Memory Architecture

The system partitions model construction into two complementary memory systems:

Neural Progress Memory: A fine-tuned LLM parses natural language requirements to draft a semantic flow graph (the "what"), capturing intended behavioral topologies.
Symbolic Feasibility Memory: A rule-based engine enforces strict logical invariants, preconditions, and transition guards (the "how"), validating every candidate transition before admission.

B. Active Automata Learning via $L^*$ with LLM Oracles

The framework employs a specialized variant of the $L^*$ active automata learning algorithm to discover the state space.

Membership Queries: The algorithm queries a grammar-constrained LLM oracle (restricted to outputs: Yes, No, Unsure) to determine if a candidate input sequence is accepted.
Equivalence Queries: The current hypothesis automaton is tested against the actual System Under Test (SUT). Divergences yield counterexamples used to refine the hypothesis.
Escalation: If the LLM returns "Unsure," the query is escalated to human experts or SUT runtime execution, ensuring the learning loop never incorporates unverified information.

C. Path-Dependent Hierarchical Modeling

To address path-dependency without combinatorial explosion, NeSy-MBST uses a two-tiered hierarchy:

Upper Tree Structure: Frequent, path-dependent sequences are modeled as a higher-order Markov chain embedded in a tree.
Lower Markov Model: Infrequent or exception pathways are modeled using standard first-order Markov chains.

D. Mathematical Constraint Optimization

Instead of asking the LLM to generate numerical probabilities directly, the framework offloads this to a symbolic solver:

Constraint Extraction: The LLM extracts comparative relationships (e.g., $P(\text{checkout}|\text{cart}) > P(\text{browse}|\text{cart})$ ) from requirements.
Convex Optimization: A convex programming engine (SLSQP) solves for the transition probability matrix $P$ that satisfies all extracted constraints, row-stochasticity, and domain-specific bounds while maximizing entropy to avoid unjustified bias.

E. Closed-Loop Model Adaptation

The framework treats the usage model as a living artifact. Runtime telemetry (execution logs, coverage metrics, failure data) is fed back to the modeling engine. The LLM analyzes divergences between predicted and observed behavior, and the symbolic solver recalibrates probabilities, ensuring the model converges toward real-world usage patterns.

3. Key Contributions

NeSy-MBST Framework: A novel architecture combining $L^*$ active learning, grammar-constrained LLM oracles, symbolic solvers, and closed-loop feedback to automate usage model synthesis.
Formal Verification of LLM Output: The introduction of a symbolic verification loop that detects structural violations (unreachable states, missing self-loops) and triggers targeted re-prompting, converting a recall-limited generation problem into a verification-guided completion problem.
Orthogonal Decomposition of Errors: The paper establishes that structural completeness (topology) and probabilistic calibration (weights) are orthogonal properties, addressed separately by the symbolic loop and the convex optimizer, respectively.
Empirical Validation: A comprehensive evaluation on an Autonomous Vehicle (AV) CPS benchmark and two e-commerce specifications, comparing NeSy-MBST against purely neural baselines and traditional manual approaches.

4. Experimental Results

Evaluated on an AV CPS benchmark (9 states, 13 transitions) and e-commerce models (up to 42 states, 218 transitions), NeSy-MBST achieved the following:

Extraction Accuracy (RQ1): Achieved a system-level F1 score of 0.9125, exceeding the 0.90 safety-critical threshold. This represents a 39.1% improvement over the best GPT-4o baseline (Hybrid SMF) and a 14.8% improvement over the strongest single-model baseline (Claude 3.5 Sonnet).
Fault-Detection Coverage (RQ2): Achieved 85.7% transition coverage, a 35.7 percentage-point gain over the pure-neural baseline (50%). This suggests a significant increase in the diversity of fault-revealing paths.
Probabilistic Calibration (RQ3): Achieved a Jensen–Shannon Divergence (JSD) of 0.012 (vs. 0.157 for the pure-neural baseline), confirming that the convex optimizer preserves operational test-allocation fidelity. The normalized Frobenius distance was 0.0654, indicating high structural similarity to the reference distribution.
Efficiency: Generated full model-coverage test suites in under six minutes for models with up to 42 states.
Ablation Study (RQ4):
- The Symbolic Loop was identified as the primary driver for structural completeness (increasing transition F1 from 0.78 to 0.96).
- The Convex Optimizer was shown to govern probabilistic calibration without altering structural metrics.
- Closed-loop feedback provided marginal improvements in distributional fidelity, primarily valuable for long-term test campaigns.

5. Significance and Claims

The paper claims that NeSy-MBST eliminates the manual modeling bottleneck without compromising the statistical rigor demanded by safety-critical Cyber-Physical Systems (CPS).

Bridging the Gap: The results demonstrate that neuro-symbolic integration can achieve the structural fidelity (F1 $\ge$ 0.90) and probabilistic calibration required for MBST, which purely neural approaches fail to guarantee.
Fault-Detection Proxy: While the study did not measure direct defect detection rates against a seeded fault corpus, the paper argues that the observed 35.7% increase in transition coverage is a strong proxy for fault detection, consistent with the 25–40% improvements reported in industrial MBT deployment literature.
Engineering Standard: The authors propose that LLM augmentation of formal test-model generation should transition from a research curiosity to a standard engineering practice, provided two conditions are met: (1) LLMs operate under structural constraints (grammar-constrained output, symbolic verification) to prevent hallucination, and (2) numerical parameters are assigned by certified solvers, not the LLM directly.

The paper concludes that this approach makes rigorous statistical testing accessible to broader software development practices, moving it beyond specialist safety-critical teams, while acknowledging that future work is needed to validate these findings on larger-scale industrial systems and with diverse requirement styles.