Formal-Verification-Guided Bayesian Optimization for Non-Intrusive Last-Mile Coverage Closure

arXiv:2610.17449 · cs.AR, cs.LG · Submitted 2026-10-12 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: Today's paper: "Formal-Verification-Guided Bayesian Optimization for Non-Intrusive Last-Mile Coverage Closure".

Jane: The gist The integrated diagnosis-and-search workflow characterizes the integrated diagnosis-and-search workflow; it does not isolate the causal contributions of difficulty classification, policy routing, and post-cleanup BO.

Tom: First, who's behind it and why it matters.

Title and authors: Jane: So this paper is called "Formal-Verification-Guided Bayesian Optimization for Non-Intrusive Last-Mile Coverage Closure," and the authors are from Texas A andM University. Would someone say that out loud?

Tom: Yeah, it’s a long title, but the main idea is that they’re not trying to invent new test goals or assertions; they are sticking to an existing coverage plan and closing those gaps with targeted search.

Lu: They start by building a common initial coverage database from unmodified CRV regressions, then they extract the residual bins—the targets that are still unhit—and then they map each target to executable testbench controls using AST/COI analysis.

Meng: So they take the residual bins you already have and use that structural analysis to find exactly which knobs can influence them.

Lalam: And after that, they compare continued CRV, reduced-space random search, and reduced-space Bayesian optimization under the same twenty simulation budget.

Jane: That’s a very concrete comparison because it shows how this new workflow stacks up against existing techniques when you only have a fixed budget.

Tom: They also remove targets only if formal verification provides complete unreachability proofs, which acts as a powerful filter before the next stage of optimization begins.

Lu: After that, they classify the targets they keep into groups based on whether they are constraint-heavy or temporal-heavy, and then run a group-specific Bayesian optimization policy.

The paper's summary: Jane: So what are the specific improvements they suggest? It seems like their main enhancement is using formal verification as a targeted diagnostic oracle inside the closure loop.

Tom: That’s right, they use formal verification for two roles: first, reachability triage, where it asks if a target is provably unreachable under your current design and environment assumptions before you spend simulation budget on it.

Lu: And the second role is difficulty diagnosis, where for reachable hard cases, formal artifacts like witness structure or enabling-condition patterns give clues about whether the blocker is a narrow conjunction of value constraints or a long sequential dependency.

Meng: So instead of just guessing which part of your design is causing the issue, you get formal hints on whether it’s a simple constraint problem or something more complex that needs a lot of time.

Lalam: They then assign difficulty scores based on temporal and constraint knobs to label targets as TemporalHeavy or ConstraintHeavy.

Jane: This leads to their difficulty-conditioned Bayesian optimization acquisition function, where the term Bdiff (x) is set to zero for Constraint-heavy and inconclusive targets, but it’s active for TemporalHeavy ones.

Tom: And they use that term to condition the UCB acquisition function by adding a difficulty-conditioned term Bdiff (x) which is min(zero point three, 0.08nt (x)) only for TemporalHeavy targets and zero otherwise.

Lu: The objective function being optimized is J(x, b) equals one point zero H plus zero point three S plus zero point two F minus zero point zero naught one C minus Iinvalid where F is set based on formal analysis.

Meng: That objective function seems designed to heavily reward targets that can be hit by simulation or are formally reachable quickly, which makes sense for a production environment where you want high-quality results efficiently.

The paper's improvements: Jane: So to wrap up the paper "Formal-Verification-Guided Bayesian Optimization for Non-Intrusive Last-Mile Coverage Closure," they show that this workflow improves last-mile closure on two OpenTitan IPs while preserving their mature UVM environments.

Tom: The results show that in those audited post-cleanup runs, the twenty newly covered bins comprised three direct and seventeen collateral hits for AES, and ninety-three Entropy Source bins comprised seventeen direct and seventy-six collateral hits for that IP.

Lu: And the final raw coverage figures are two hundred sixty-one/two hundred seventy-one forty-nine point three one percent for AES and two thousand two hundred ten/two thousand two hundred seventy-seven forty-nine point zero six percent for the Entropy Source.

Meng: And that translates to ninety-seven point zero three percent effective coverage, which is a real win when you're working with a fixed simulation budget.

Lalam: What this means for us is that this diagnosis-and-search workflow is a systematic way to improve closure on these specific chips without needing to run massive, unconstrained BO runs over the full unreduced space.

Jane: It really shows that integrating formal verification into the loop gives you better last-mile closure on these OpenTitan IPs while keeping those mature UVM environments intact.

Tom: Yeah, it's a structured approach that moves from broad mapping to focused optimization based on what's formally possible.

Lu: I think the key part is using that linkage map derived from AST parsing and cone of influence tracing instead of treating the whole knob space as a black box.

Meng: Because every simulation run costs time, reducing the number of knobs you search over makes a huge difference in terms of deployment cost for us.

Lalam: So they're not inventing new testbench control logic; they're just using existing ones to find the path to the target condition.

Conclusion: Tom: So we've just talked about how this workflow uses formal verification to guide Bayesian optimization to close coverage gaps on OpenTitan IPs without rewriting tests.

Jane: Exactly, and the results show a solid improvement in last-mile closure on those chips while keeping the existing UVM environments intact.

Lu: The final raw coverage figures are two hundred sixty-one/two hundred seventy-one forty-nine point three one percent for AES and two thousand two hundred ten/two thousand two hundred seventy-seven forty-nine point zero six percent for the Entropy Source.

CHENGJIA LIU, PRIYADARSI MISHRA, DAVID KEBO HOUNGNINOU, MICHAEL QUINN, AAKASH TYAGI, JIANG HU

Texas A&M University

cs.AR, cs.LG

Submitted: 2026-10-12

Updated: 2026-10-12

Comments: 21 pages, 3 figures, 7 tables. Accepted for publication in ACM Transactions on Design Automation of Electronic Systems (TODAES)

Code: https://github.com/chipsalliance/verible

License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/

The gist: The gist The integrated diagnosis-and-search workflow characterizes the integrated diagnosis-and-search workflow; it does not isolate the causal contributions of difficulty classification, policy

Key concepts

Integrated Diagnosis-and-Search Workflow
This is a non-intrusive process that closes pre-defined coverage bins by mapping residual targets to existing testbench knobs. It uses abstract syntax tree (AST) parsing and cone-of-influence (COI) tracing to create a structural linkage map, which significantly prunes the search space for targeted stimulus generation without adding new control logic.
Formal Verification Oracle
Formal verification is used inside the loop for two purposes: reachability triage and difficulty diagnosis. First, it checks if a target is provably unreachable under current assumptions. Second, for reachable hard cases, it provides artifacts like witness structure or depth to diagnose whether the blocker is a narrow set of value constraints or a long sequential dependency.
Difficulty Classification
Targets are classified as TemporalHeavy or ConstraintHeavy based on scoring functions that consider metrics like witness depth, temporal-event counts, and the number of target-linked knobs. This classification informs the Bayesian Optimization by adjusting the acquisition function to focus search efforts on targets with specific characteristics.
Difficulty-Conditioned Acquisition Function
The Bayesian Optimization uses an acquisition function modified by a difficulty term (Bdiff). This term is zero for ConstraintHeavy and inconclusive targets, but non-zero for TemporalHeavy targets, guiding the optimization process to prioritize exploring those specific types of difficult cases.

Terminology

Summary

The gist The integrated diagnosis-and-search workflow characterizes the integrated diagnosis-and-search workflow; it does not isolate the causal contributions of difficulty classification, policy routing, and post-cleanup BO.

How it works

The workflow is a non-intrusive process that closes pre-defined bins in an existing, human-authored functional coverage model by mapping residual targets to existing testbench knobs using abstract-syntax-tree (AST) parsing and cone-of-influence (COI) tracing<ref:2610.17449#pg4> The workflow first uses abstract-syntax-tree (AST) parsing and cone-of-influence (COI) tracing to map each residual target to existing testbench knobs<ref:2610.17449#pg4> This structural linkage information, although potentially complex to extract reliably for all scenarios, can significantly prune the search space for targeted stimulus generation compared to treating the entire knob configuration space as a black box<ref:2610.17449#pg4>. The output is a per-target linkage map of existing testbench knobs with plausible structural paths to the target condition, defining the reduced search space used downstream without introducing new testbench control logic<ref:2610.17449#pg4>.

How it works (Continued)

The workflow proceeds through several stages:

  1. build a common initial coverage database from the unmodified CRV regressions<ref:2610.17449#pg4>

  2. extract the residual bins<ref:2610.17449#pg4>

  3. map each target to executable testbench controls with AST/COI analysis<ref:2610.17449#pg4>

  4. compare continued CRV, reduced-space random search, and reducedspace BO under the same 20-simulation budget<ref:2610.17449#pg4>

  5. remove only targets supported by complete unreachability proofs<ref:2610.17449#pg4>

  6. classify retained targets as constraint-heavy, temporal-heavy, or inconclusive<ref:2610.17449#pg4>

  7. run the corresponding group-specific BO policy<ref:2610.17449#pg4>

  8. audit every numerator change against simulator coverage feedback<ref:2610.17449#pg4>.

How it works (Continued)

Formal verification is used as a targeted diagnostic oracle inside the closure loop, serving two roles: reachability triage and difficulty diagnosis<ref:2610.17449#pg6> Its first role is reachability triage: after the first-pass search and before second-stage simulation budget is spent on a residual case, the formal engine is asked whether the target is provably unreachable under the current design and environment assumptions<ref:2610.17449#pg6>. Its second role is difficulty diagnosis: for reachable hard cases, formal artifacts such as witness structure, depth, or enabling-condition patterns can provide clues about whether the dominant blocker is a narrow conjunction of value constraints or a long sequential dependency<ref:2610.17449#pg6>.

How it works (Continued)

The difficulty classification assigns scores based on temporal and constraint knobs to label targets as TemporalHeavy or ConstraintHeavy<ref:2610.17449#pg10> The scoring functions are defined as sT = 1[d > Dt] + 1[e > Et] + M + Kt, and sC = P + Kc + 1[d ≤ Dt], where d, e, M, P, Kt, and Kc denote specific metrics related to witness depth, temporal-event count (with missing values mapped to zero), signal-name hit count across sampled hierarchical names (M), predicate count (P), and the numbers of target-linked knobs categorized as temporal and constraint respectively<ref:2610.17449#pg10>.

How it works (Continued)

The Bayesian Optimization uses a difficulty-conditioned acquisition function, defined by Eq. (2): a(x) = μ(x) + βτu(x) + 0.25N (x) + 0.10D(x) + Bdiff (x) + Badj(x) + ε (x)<ref:2610.17449#pg10>. The difficulty-conditioned term is Bdiff (x) = min(0.3, 0.08nt (x)) for a TemporalHeavy target and zero for ConstraintHeavy and inconclusive targets<ref:2610.17449#pg10>.

How it works (Continued)

The objective function being optimized is J (x, b) = 1.0H + 0.3S + 0.2F − 0.001C − Iinvalid<ref:2610.17449#pg10>. The term F is set based on formal analysis, where F = 1 when simulator coverage feedback records the target hit, F = 0.5 when reachability is established without witness depth, and otherwise F = 1/(1+dw/20)<ref:2610.17449#pg10>.

How it works (Continued)

The final execution order is fixed: initial CRV history → residual extraction → AST/COI reduction → matched first-pass search → complete-proof-only cleanup → residual difficulty grouping → group-specific BO<ref:2610.17449#pg4>. The first-pass BO result is the pre-cleanup numerator baseline, and cleanup may reduce only the effective denominator<ref:2610.17449#pg4>.

How it works (Continued)

The results show that in the audited post-cleanup runs, the 20 AES newly covered bins comprised 3 direct and 17 collateral hits, while the 93 Entropy Source newly covered bins comprised 17 direct and 76 collateral hits<ref:2610.17449#pg6>.

How it works (Continued)

The final raw coverage is therefore 261/271 (96.31%) for AES and 2210/2277 (97.06%) for Entropy Source; final effective coverage is 261/269 (97.03%) and 2210/2267 (97.49%)

How it works (Continued)

The results support a bounded observation: in these audited fixed-budget runs, the diagnosis-andsearch workflow improved last-mile closure on the two evaluated OpenTitan IPs while preserving their mature UVM environments<ref:2610.17449#pg4>.

How it works (Continued)

The evaluation covers two OpenTitan IPs, one cluster configuration, no controlled BO run over the full unreduced space, and no matched default-BO control after the same formal cleanup<ref:2610.17449#pg19>.

How it works (Continued)

Future work will extend the evaluation to additional DUTs, add replicated sensitivity trials, and establish a shared benchmark for controlled cross-framework comparison<ref:2610.17449#pg4>.

How it works (Continued)

The workflow pseudocode, property-generation rules, schemas, parameters, assumptions, and audited case data support independent reimplementation<ref:2610.17449#pg4>.

How it works (Continued)

The final raw coverage is therefore 261/271 (96.31%) for AES and 2210/2277 (97.06%) for Entropy Source; final effective coverage is 261/269 (97.03%) and 2210/2267 (97.49).

Improvements for AI systems

  1. Bold header: AST/COI-guided Testbench Knob Mapping

This capability allows for mapping each residual target to existing testbench knobs using AST parsing and cone-of-influence (COI) tracing, enabling a systematic pruning of the search space by linking coverage targets to structural influences in the RTL and testbench.

  1. Bold header: Formal Reachability Triage

The system can perform formal reachability diagnosis by asking if a target is provably unreachable under the current design and environment assumptions, thereby removing targets that are not reachable from the search queue before spending simulation budget on them.

  1. Bold header: Difficulty-Conditioned Bayesian Optimization

The optimization engine can employ a difficulty-conditioned UCB acquisition function, where the term Bdiff (x) = min(0.3, 0.08nt (x)) for a TemporalHeavy target and zero for ConstraintHeavy and inconclusive targets, to route search policies based on formal difficulty labels (Constraint-heavy or temporal-heavy).

Sources

Related papers