Research map / Learning theory and algorithms / Combinatorial and search optimization

Algorithm Selection for Word-Level Hardware Model Checking (Student Abstract)

AAAI 2025 · Learning theory and algorithms › Combinatorial and search optimization · approach: Structure and complexity of constraint reasoning · 2 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Builds BTOR2-SELECT, an ML algorithm selection tool for word-level hardware model checking that chooses among hardware and software verifiers (via BTOR2C translation) using pairwise XGBoost classifiers over Bag of Keywords and Bit-Width Aggregation embeddings.

Problem

Choosing the best hardware or software verifier for each word-level BTOR2 hardware model-checking instance, since no single solver dominates across instances.

Approach

Two instance embeddings for BTOR2 (keyword occurrence counts and bit-width sums per keyword) combined with cost-sensitive pairwise XGBoost classifiers, and extending the verifier pool with software verifiers (CBMC, ESBMC) through a BTOR2-to-C translator.

Key results

• BTOR2-SELECT (PWC-BoKW) solved 227 of 288 test instances vs. 201 for the single best solver ABC-PDR (12.9% more) and reduced PAR-2 by about 27.7% (120,484.8 vs. 166,683.4).
• The tool closed around 65% (up to 66.0%) of the VBS-SBS performance gap.
• Software verifiers collectively contributed 27.2% to PWC-BoKW performance by Shapley value.

Measured effects reported in the paper

Surprising findings

• The abstract reports 30.0% more solved instances and 50.2% PAR-2 reduction relative to AVR's PDR, while the body reports 12.9% and 27.7% relative to ABC-PDR; the comparison baselines differ across claims.

Limitations

• Evaluated only on benchmarks without arrays
• Small testing set of 288 instances
• Only four model checkers with multiple configurations in the verifier set

Experimental setup

Datasets: word-level hardware model checking benchmarks (BTOR2, 1441 instances without arrays)

Benchmarks: BTOR2 word-level hardware model checking benchmark test split (288 instances)

Metrics: number of solved instances PAR-2 Shapley value contribution gap closed between SBS and VBS

Baselines: ABC-PDR AVR-PDR single best solver virtual best solver

Builds on: cost-sensitive pairwise classifier BTOR2C Shapley-value portfolio contribution

Closest papers by meaning

• Neural Model Checking (NeurIPS 2024 · similarity 0.85)
• HierSVA: A Synthesis Pipeline, Dataset, and Benchmark for LLM-Driven Hierarchical Hardware Formal Verification (NeurIPS 2026 · similarity 0.83)
• VeriThoughts: Enabling Automated Verilog Code Generation using Reasoning and Formal Verification (NeurIPS 2025 · similarity 0.83)
• Rethinking Optimal Verification Granularity for Compute-Efficient Test-Time Scaling (NeurIPS 2025 · similarity 0.82)
• Variation in Verification: Understanding Verification Dynamics in Large Language Models (ICLR 2026 · similarity 0.82)
• VeriLoC: Line-of-Code Level Prediction of Hardware Design Quality from Verilog Code (NeurIPS 2025 · similarity 0.81)