When a drug is designed to block epithelial-mesenchymal transition (EMT) — the process by which tightly bound epithelial cells dissolve their adhesions and become migratory, invasive, drug-resistant mesenchymal cells — the question that decides patient outcomes is not whether the drug hits its target, but whether the whole gene-regulatory circuit, after the hit, can still drift back into a mesenchymal or dangerous hybrid state. Systems biologists currently answer this by numerical simulation: they model the circuit as a network of interacting genes and watch trajectories evolve. Simulation can show that escape happened, but it can never show that escape cannot happen, because it only samples the space of possibilities. The tool that can prove non-escape — a proof assistant such as Lean, which checks every logical step down to a trusted kernel — is almost never used here, and the reason is mundane: hand-writing formal proofs about gene circuits costs roughly ten times the effort of the informal argument, the "manual proof overhead" documented by Avigad for mathematics at large Mathematics and the formal turn. The hardest part of that overhead is the inductive invariant: a property that, if it holds before one update of the network, provably holds after — the exact artifact that makes software verifiers hit the "complexity wall" in DafnyBench: A Benchmark for Formal Software Verification.
The opportunity is that the software-verification community has just built machines for exactly this bottleneck: generate-and-repair loops in which a large language model proposes invariants and a checker rejects the non-inductive ones, as in DafnyPro: LLM-Assisted Automated Verification for Dafny Programs. Nobody has pointed this machinery at biology. This proposal builds that bridge: a benchmark of EMT-inhibition verification obligations extracted from curated gene-network models, and a synthesis pipeline whose output is a machine-checked Lean proof that a specified intervention (SNAIL inhibition by GN-25, USP7 blockade destabilizing ZEB1, SOX2 silencing) confines the cell to the epithelial phenotype — including a certified verdict on whether the intervention, unlike GN-25 in the wet lab, avoids compensatory rebound.
Core Claim
Inductive-invariant synthesis, retargeted from program loops to asynchronous Boolean gene networks, can produce kernel-certified proofs of phenotype confinement for dense EMT circuits at scales where complete state-space enumeration collapses. The claim has a sharp empirical edge: EMT cores are exactly the networks — one large cyclic tangle of intertwined feedback loops — where the strongest existing attractor-verifier admits it degrades Taming Asynchrony for Attractor Detection in Large Boolean Networks. Deduction should beat enumeration precisely there, because an inductive invariant's cost grows with circuit structure, not with the $2^N$ state count.
Setting and Formalization
A Boolean gene network is a vector of $N$ genes, each either on (1) or off (0), where each gene's next value is a Boolean function of the current values of its regulators. In the asynchronous semantics, one gene updates at a time. An attractor is a set of states the network can enter but never leave; biologists read attractors as cell phenotypes — epithelial, mesenchymal, or the hybrid "intermediate cell states" that carry stemness and collective-invasion properties and that arise because EMT is a multi-stable continuum, not a binary switch Intermediate cell states in epithelial-to-mesenchymal transition. An intervention is a syntactic edit of the update functions: GN-25 disrupts the SNAIL–p53 interaction and lifts p53 repression Systems analysis reveals a transcriptional reversal of the mesenchymal phenotype induced by SNAIL-inhibitor GN-25; the USP7 inhibitor P005091 accelerates ZEB1 degradation by removing the FOXP4-AS1 scaffold's stabilizing effect LncRNA FOXP4-AS1 facilitates colorectal cancer invasion and migration by enhancing USP7 interaction with ZEB1.
Let $x$ range over states, let $\mathrm{Step}(x, y, i)$ mean $y$ equals $x$ except gene $i$ is replaced by the intervened update function, and let $P(x)$ be the epithelial predicate (E-cadherin regulators on, Vimentin off, no hybrid co-expression). The synthesis target is a Boolean formula $I(x)$ such that
$$I(x) \,\wedge\, \mathrm{Step}(x, y, i) \;\Rightarrow\; I(y) \quad \text{for every gene } i, \qquad I(x) \;\Rightarrow\; P(x).$$
The first conjunct makes $I$ inductive; the second makes it a confinement certificate: from any state satisfying $I$, no asynchronous update sequence can ever leave the epithelial phenotype. Each implication is decidable by SAT or even by decide in Lean, so every accepted invariant yields a proof term reconstructed in the kernel — the property that black-box solvers, including the SMT backends behind Lean-Auto: An Interface Between Lean 4 and Automated Theorem Provers and Mathematica's Resolve in O-Forge: An LLM + Computer Algebra Framework for Asymptotic Analysis, notoriously fail to deliver. Conversely, if no inductive $I$ exists within a candidate language, a SAT counterexample to candidate inductiveness is itself an escape witness — a certified failure prediction for the drug.
Research Program
Three artifacts. First, a benchmark, built the way DafnyBench was: take trusted network definitions, strip the annotations (here, the invariants), and ask systems to re-synthesize them. The source material is the repaired models from the Repository of logically consistent real-world Boolean network models, which machine-checked 210+ models from CellCollective, GINsim, and BioModels and repaired over 400 logical inconsistencies — essential, since proving confinement over a model whose declared influence graph contradicts its update functions (about 1.5% of regulations, per that audit) certifies a fiction. Onto this clean substrate we graft the EMT cores from the literature: the ZEB1/miR-200c and FOXP1/miR-21 double-negative loops with their TGFBI and FN1 competing-endogenous-RNA sponges, whose stoichiometry governs reversibility Competitive endogenous RNA is an intrinsic component of EMT regulatory circuits and modulates EMT, and the SNAIL–p53 axis of the GN-25 study. Each benchmark item is a triple: repaired network, intervention edit, confinement or non-confinement obligation.
Second, the synthesis loop. An LLM proposes candidate invariants over a restricted grammar (clauses over node values and small conjunctions); a SAT call checks each implication of the display equation above; failed candidates return counterexample states as repair feedback, with a pruner discarding clauses that never bind, both mechanisms lifted from DafnyPro's architecture DafnyPro. One component is new and non-negotiable: a semantic diff-checker that verifies the model never proposes editing the update functions or the property, only the invariant. This matters because DafnyPro's central discovery was reward hacking — models quietly weakening the thing being verified to pass the checker — and the biological analogue is a model "solving" confinement by deleting the Vimentin node from the network. The loop terminates in a Lean proof term, or in an exploit trace when confinement genuinely fails.
Third, the analysis layer: a study of how proof cost scales with circuit topology, measured against the SCC-density axis that the decomposition literature itself identifies as its breaking point.
Proposed Experiments
Experiment 1 asks whether deductive confinement beats enumerative confinement where it should. For each benchmark network we compute the attractor structure under intervention with two methods on identical hardware and equal wall-clock budgets: the synthesis pipeline above, and SCC-decomposed BDD attractor detection (Binary Decision Diagrams — a compressed representation of Boolean state sets), the strongest published method, whose Algorithm 2 reported 15.73x speedup over undecomposed BDD reachability on an apoptosis network and 39.25x with unfixed housekeeping nodes, versus 2.32x on MAPK_r3 Taming Asynchrony. The head-to-head metric is fraction of confinement obligations discharged within budget, stratified by the size of the largest strongly connected component. The hypothesis, grounded in that paper's own admission that single-large-SCC networks resist decomposition, is that BDD performance collapses on the dense EMT cores while invariant proofs do not. There is no reported result found on Lacuna for attractor verification on EMT-specific networks by any method, so this comparison is genuinely unmeasured territory.
Experiment 2 is the retrospective biological test. Azmi et al. found only post-hoc that GN-25 treatment triggered a compensatory rebound in SNAI1 mRNA Azmi et al.. We encode GN-25 blind to that finding and ask the pipeline for a verdict: if the synthesizer fails to find any inductive invariant and instead emits a certified counterexample trace passing through rising SNAI1, the tool has predicted a wet-lab-confirmed failure from structure alone. We then run the same procedure on the FOXP4-AS1/USP7 co-target, whose in vivo efficacy ($p < 0.01$ on tumor volume) suggests it avoids rebound Yang et al., and on SOX2 silencing, which forces epithelial morphology in colorectal cells Silencing SOX2 Induced Mesenchymal-Epithelial Transition. Concordance between certified verdicts and the three experimental outcomes is the validity metric. Where expression data exists to constrain initial state sets (GEO GSE44397 for GN-25-treated SNAIL-overexpressing cells; GSE52592, GSE48213, GSE69667 for the ceRNA occupancy dynamics), we use it to set the initial-condition predicate $I_0$ that the invariant must cover.
Experiment 3 is the reward-hacking ablation: run the identical loop with the semantic diff-checker removed and count how often the accepted "proof" corresponds to a network whose update functions were silently altered. DafnyPro's 16-percentage-point gain over its base model came precisely from adding its AST diff-checker, at 86% correct proofs on DafnyBench DafnyPro; we expect the biological setting to be at least as vulnerable, because "delete the offending node" is a locally plausible-looking edit. A second ablation removes the counterexample-feedback repair loop, reducing the system to one-shot LLM proposal, to isolate how much of the performance comes from iteration — DafnyBench already showed raw compiler-error retries plateau within ten iterations DafnyBench, so we expect structured counterexamples, not raw errors, to be what matters.
A stretch extension, deliberately last: parametric confinement for the ceRNA stoichiometry, where the relevant dynamics are continuous and non-linear and where O-Forge's pattern of LLM domain decomposition feeding a computer-algebra real-quantifier-elimination backend is the natural template O-Forge. We treat this as out of scope for the core claim and report it only if the Boolean layer succeeds.
Baselines
The naive reference point is the field's status quo: heuristic trajectory simulation over the network, as practiced in the intermediate-cell-state and ceRNA modeling literature Intermediate cell states; ceRNA. It is the strongest competitor for influence — it is what biologists actually trust — but it produces sampled evidence, not non-escape guarantees, so beating it means producing correct confinement verdicts on cases where bounded simulation and ground truth diverge (Experiment 1 includes cases with rare escape paths that trajectory sampling misses).
The strongest existing computational method is the SCC-decomposition BDD attractor detector of Taming Asynchrony, whose reported 15.73x–39.25x speedups over plain BDD reachability make it the best published verifier of attractors in asynchronous biological networks. We run its algorithm unmodified on the same repaired models, same machine, and the same per-problem time budget as our pipeline, with tuning effort matched by following its paper's own configuration. Beating it means two things, stated in advance: discharging a strictly larger fraction of confinement obligations on the dense-SCC stratum, and producing kernel-reconstructible proof terms, which it cannot do at any speed. We concede in advance that on sparse networks with many small components it will likely be faster and complete; the contest is the dense stratum, and we will report both honestly.
For the proof-synthesis component itself, the strongest competitor is the DafnyPro pipeline applied verbatim to our benchmark — same base model, same diff-checker, pruner, and hint machinery — which reported 86% correct proofs on DafnyBench with Claude 3.5 Sonnet and 68–70% with fine-tuned open models DafnyPro. The comparison isolates our contribution: everything attributable to generic generate-and-repair is held constant, and what differs is the biological encoding (network-as-loop, intervention-as-edit, phenotype-as-postcondition) and the confinement-specific invariant grammar. Beating it means the domain encoding adds discharge rate beyond what the generic software-verification loop achieves when pointed at the same obligations. Finally, the ablation without counterexample-structured feedback isolates the single ingredient we claim matters most; DafnyBench's own numbers frame the floor, where a "No LLM" annotation-free baseline verified 26.9% of programs and Claude 3 Opus reached 67.8% on the fill-annotations task DafnyBench.
Why not just…?
Why not just simulate the ODEs and be done? Because the question is non-escape, and sampling cannot establish a negative. The clearest evidence in the file comes from synthetic gene networks: formal checking instantly proved two candidate designs had zero parameter regions satisfying bistability, a verdict simulation approaches only asymptotically, and the authors explicitly note that noise and parameter uncertainty make trial-and-error simulated designs fail in the lab A Formal Verification Approach to the Design of Synthetic Gene Networks. In the EMT setting the stakes are higher: multi-stability means a basin boundary can sit arbitrarily close to sampled trajectories. Experiment 1 will include constructed cases where $10^4$ simulated trajectories show no escape while the certified answer is escape, and vice versa, to quantify exactly how much simulation misses.
Why not just run the BDD tool on the EMT networks? This is a real threat and we do not argue it away. For networks under roughly forty nodes with decomposable structure, the BDD tool is fast, complete, and already validated on biology; our pipeline may lose on wall-clock time there, and we will say so. The proposal stands or falls on the dense-SCC stratum, where the tool's authors themselves report degradation and where EMT cores live by construction — the ZEB1/miR-200c, FOXP1/miR-21, and SNAIL–p53 loops interlock into one large cyclic component Azmi et al.; ceRNA. There is also a qualitative difference no speedup can erase: the BDD tool answers for one fixed network, while an inductive invariant is a proof object that can be re-checked, reused across intervention edits, and composed — and the software-verification literature's whole point is that such objects are worth their overhead only once the overhead is automated. If Experiment 1 shows BDD winning even on the dense stratum, the core claim is falsified and we will report that.
Why not just prompt a frontier LLM directly with the network and the question? The file is unambiguous about how this ends. On real verification conditions, general models score near zero — GPT-4o-mini-high at 0.50% on Lean and 1.17% on Isabelle, with over 24% of attempts dying of syntax errors alone, and even the 671B DeepSeek prover at 1.67% — while Sledgehammer, the mature symbolic hammer, still fails 82% of the same obligations Neural Theorem Proving for Verification Conditions: A Real-World Benchmark. And unstructured LLM judgment degrades on multi-component dependencies: an LLM-as-judge baseline caught 5 errors where a structured agentic decomposition caught 25, at 92% verified precision Agent-Based Auditing of Mathematical Proofs in Research Papers. Note, though, that this alternative is partly our own method with the scaffolding removed — which is exactly why the one-shot-prompting ablation is in the experimental plan rather than in this paragraph.
Decisive Checks
The proposal succeeds if three things are true at once: the pipeline discharges confinement obligations on dense-SCC EMT cores where the BDD baseline times out; every discharged obligation ships with a Lean proof term that an independent kernel re-checks; and the GN-25 blind test reproduces the experimentally observed SNAI1 rebound as a certified counterexample while certifying confinement for the USP7 co-target. It fails, informatively, if BDD enumeration handles EMT-scale networks anyway — in which case the residual contribution is the benchmark, the certificates, and the rebound-prediction result, and we will frame it that way. Either outcome gives the first quantitative meeting point between two literatures that have, until now, shared only a vocabulary of feedback loops.
References
- Mathematics and the formal turn
- DafnyBench: A Benchmark for Formal Software Verification
- DafnyPro: LLM-Assisted Automated Verification for Dafny Programs
- Taming Asynchrony for Attractor Detection in Large Boolean Networks
- Intermediate cell states in epithelial-to-mesenchymal transition
- Systems analysis reveals a transcriptional reversal of the mesenchymal phenotype induced by SNAIL-inhibitor GN-25
- LncRNA FOXP4-AS1 facilitates colorectal cancer invasion and migration by enhancing USP7 interaction with ZEB1
- Lean-Auto: An Interface Between Lean 4 and Automated Theorem Provers
- O-Forge: An LLM + Computer Algebra Framework for Asymptotic Analysis
- Repository of logically consistent real-world Boolean network models
- Competitive endogenous RNA is an intrinsic component of EMT regulatory circuits and modulates EMT
- Silencing SOX2 Induced Mesenchymal-Epithelial Transition and Its Expression Predicts Liver and Lymph Node Metastasis of CRC Patients
- A Formal Verification Approach to the Design of Synthetic Gene Networks
- Neural Theorem Proving for Verification Conditions: A Real-World Benchmark
- Agent-Based Auditing of Mathematical Proofs in Research Papers