Research map / Learning theory and algorithms / Combinatorial and search optimization
Cirbo: A New Tool for Boolean Circuit Analysis and Synthesis
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.
Presents Cirbo, an open-source Python tool for Boolean circuit analysis (SAT-based checks, miters), synthesis (presynthesized blocks, SAT-based, hybrid), and minimization, which won the IWLS 2024 Programming Contest with size reductions up to 83% over 2023 best circuits.
Problem
Circuit analysis (satisfiability, equivalence checking) and circuit synthesis/minimization of Boolean functions, where practical circuit sizes for symmetric and arithmetic functions have been heavily optimized but remain improvable.
Approach
An integrated Python toolkit combining SAT-based subcircuit minimization, a database of near-optimal small circuits, and hybrid synthesis (presynthesized arithmetic blocks plus SAT-synthesized final blocks) for XAIG/AIG circuits.
Key results
- Circuit for modulo8 (ex33) reduced from 1182 to 250 AIG gates (78.85%) and from 1158 to 190 XAIG gates (83.59%) versus the 2023 best.
- Average size reduction of about 12% relative to the best 2023 circuits, and the tool won the IWLS 2024 Programming Contest.
- MAJ_15 XAIG circuit reduced from 68 to 48 gates (29.41%) and SORT_15 from 114 to 73 (35.96%) relative to IWLS 2023 best.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use Cirbo 2024 instead of the IWLS 2023 best circuit | Boolean circuit synthesis in AIG · modulo8 | circuit size: 1182 -> 250; 78.85% | Helped |
| Use Cirbo 2024 instead of the IWLS 2023 best circuit | Boolean circuit synthesis in XAIG · modulo8 | circuit size: 1158 -> 190; 83.59% | Helped |
| Use Cirbo 2024 instead of the IWLS 2023 best circuit | Boolean circuit synthesis in AIG · square12 | circuit size: 1319 -> 476; 63.91% | Helped |
| Use Cirbo 2024 instead of the IWLS 2023 best circuit | Boolean circuit synthesis in XAIG · square12 | circuit size: 1284 -> 324; 74.77% | Helped |
| Use Cirbo 2024 instead of the IWLS 2023 best circuit | Boolean circuit synthesis in AIG · div8 | circuit size: 317 -> 176; 44.48% | Helped |
| Use Cirbo 2024 instead of the IWLS 2023 best circuit | Boolean circuit synthesis in XAIG · div8 | circuit size: 306 -> 142; 53.59% | Helped |
| Use Cirbo 2024 instead of the IWLS 2023 best circuit | Boolean circuit synthesis in XAIG · sort15 | circuit size: 114 -> 73; 35.96% | Helped |
| Use Cirbo 2024 instead of the IWLS 2023 best circuit | Boolean circuit synthesis in AIG · maj15 | circuit size: 68 -> 68; 0% | No clear effect |
| Use Cirbo 2024 instead of the IWLS 2023 best circuit | Boolean circuit synthesis in XAIG · maj15 | circuit size: 68 -> 48; 29.41% | Helped |
| Use the hybrid approach: sum the inputs, SAT-synthesize the output function, then minimize the composition | MAJ_n circuit synthesis · MAJ_15 (XAIG) | circuit size: 68 -> 48; 29% | Helped |
| Use the hybrid approach: sum the inputs, SAT-synthesize the output function, then minimize the composition | SORT_n circuit synthesis · SORT_15 (XAIG) | circuit size: 114 -> 73; 35% | Helped |
| Apply Cirbo 2024 minimization rather than the IWLS 2023 best circuit | XAIG neuron circuit · ex29 | circuit size: 644 -> 587; 8% | Helped |
Surprising findings
- For some neuron benchmarks, combining the tool with ABC and CIOPS was needed to achieve further gains, indicating no single tool dominates across datasets.
Limitations
- Exhaustive analysis of functions (monotone/symmetric checks) is only practical for small numbers of inputs.
- SAT-based synthesis is practical only for small input counts (around n <= 10).
- For some AIG functions with three inputs and three outputs, optimality is not proven due to SAT solver difficulty.
Experimental setup
Datasets: IWLS 2024 Programming Contest benchmarks IWLS 2023 benchmarks LogicNets neuron benchmarks
Benchmarks: IWLS 2024 Programming Contest benchmarks (ex33, ex96, ex88, ex65, ex39, ex36, ex20, ex25) MAJ_n and SORT_n circuits neuron benchmarks
Metrics: circuit size (number of AND/XOR gates) percent size reduction
Baselines: ABC mockturtle CLI CIOPS IWLS 2023 best circuits
Builds on: ABC pysat CIOPS Tseitin transformation
Closest papers by meaning
- Retrieval-Guided Reinforcement Learning for Boolean Circuit Minimization (ICLR 2024 · similarity 0.85)
- Rethinking Circuit Completeness in Language Models: AND, OR, and ADDER Gates (NeurIPS 2025 · similarity 0.85)
- GPU-Accelerated Synthesis of Mixed-Boolean Arithmetic: Beyond Caching (NeurIPS 2026 · similarity 0.85)
- Towards Next-Generation Logic Synthesis: A Scalable Neural Circuit Generation Framework (NeurIPS 2024 · similarity 0.84)
- A Circuit Domain Generalization Framework for Efficient Logic Synthesis in Chip Design (ICML 2024 · similarity 0.84)
- An And-Sum Circuit with Signed Edges That Is More Succinct than SDD (AAAI 2025 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.