How many gates above the proven minimum does Yosys/ABC use for 4-input logic?

What it found

The exact minimum 2-input gate count of every 4-input Boolean function (222 NPN classes, by SAT) against what Yosys/ABC returns on 884 sampled functions. The default flow is exactly optimal on only 34% and averages 1.19 gates above the minimum (max 4); the best of seven scripts per function reaches 38%. A heavier resyn2 script is worse (1.72), and the count changes with which negated or permuted form of the same function is synthesised. One Yosys version, generic gates, 4 inputs only. Preliminary.

A figure from its own output

Paper, code and results

• README and method
• Experiments and results
• Code
• Tests

More in LLM chip design loops

• Does the ABC synthesis script matter as much as the written RTL structure for adder and multiplier area and depth?Sweeps five ABC scripts over five adder and eight multiplier structures (all proved equivalent): the script moves cells×depth by up to 1.75× for one adder, while all eight multiplier structures score identically (stylised, generic-gate).
• Does the order or naming of equivalent Verilog change what Yosys and ABC synthesise?Whether equivalent Verilog that differs only in wire names, statement order or the order of added operands synthesises to the same size: names and statement order never change cells×depth, operand order does for one carry-select adder (up to 1.43×, a 17% better result than the earlier sweep's best; stylised).
• Do the blocks of a carry-select adder share a + b independently when every chain gets its own operand order?Tests whether carry-select blocks share a+b independently under mixed per-chain operand orders: the set of sharing blocks predicts Yosys's adder count in 400 of 400 random variants and fixes the cells x depth score (8 sets, one score each per ABC script); the cost is not additive across blocks (stylised, Yosys 0.33).
• Which Yosys pass makes the operand order of a + b + constant change the synthesised adder?Finds the Yosys pass behind chip-abc-order's operand-order effect: opt_merge shares a+b between the two carry-select sums only when both are written with a and b first (4 of 36 operand orders); removing it widens the spread (up to 3.2×), so it was hiding variation. One adder, stylised.
• Does letting Yosys share a common a + b make adders smaller under every ABC script?Tests whether letting Yosys share a common a + b shrinks adders: fewer cells in 54 of 55 design/script pairs but often deeper; stylised, Yosys 0.33.
• Does writing the shared a + b sum of a carry-select adder explicitly change what Yosys and ABC synthesise?Writing the shared a + b sum of a carry-select adder by hand (explicitly, or as an incrementer) gives the same netlist Yosys already finds; attaching the constant to b first defeats the sharing and is 17-22% smaller under ABC's optimising scripts (stylised, Yosys 0.33).

All 40 LLM chip design loops projects →

Other research topics

Proper scoring & elicitation28Effort & peer prediction9Verification games & slashing19Detection & tolerances14Markets as routers13Prediction-market design9Paying contributors8Decentralised training systems23Digital twins & sim-to-real164LLM chip design loops40Robot manufacturing loops53Ambient AI assistant46Self-replicating manufacturing34Simulation-first design64Engineered clothing45Task-specific AI accelerators40Algorithmic chip-design loops42Open-source purpose-built robots44The software-engineering loop43Adversarial human imitation41Open-source residential construction41Autonomous multi-angle capture34Sensing, imaging and 3D31Energy supply and dense energy storage39Robot societies among people31Agentic co-design of low-cost robots27Laundry-hanging robots25Machine learning on qualitative data23Robots on the building site27Civilizations & group psychology1History & human sciences1

Produced with AI assistance (Claude). Results are from the code in this repository and are simulated or stylised unless the abstract says otherwise; nothing here implies affiliation with or endorsement by any lab, researcher or company cited. MIT licensed.