Using LLM Agents to Explore EDA Synthesis Search Spaces

Project: This post is part of the EDA Logic Synthesis Engine project — a from-scratch DAG-aware synthesis engine for the ICCAD 2026 CADC Contest.

TL;DR

LLMs are unreliable at generating correct graph mutations. The solution isn’t better prompts — it’s a three-layer defense system that validates every action before execution, detects cyclic dependencies via BFS, and rolls back any mutation that breaks the graph. The LLM suggests what to optimize; the engine guarantees safety.

The Temptation (and Trap) of LLM-Driven EDA

The pitch sounds great: “Let GPT figure out the best optimization strategy for each circuit.” In practice, this fails spectacularly:

1. Hallucinated signals: LLM invents signal names that don’t exist in the netlist
2. Invalid transformations: LLM suggests gate types that violate the netlist’s technology library
3. Cyclic mutations: LLM’s action creates a combinational loop — the graph is no longer a DAG
4. Silent corruption: LLM’s transformation looks valid but changes the circuit’s function

The failure mode isn’t dramatic crashes — it’s subtle functional corruption that passes basic checks but produces wrong results.

Architecture: LLM as Advisor, Engine as Executor

┌──────────────────────────────────────────────┐
│                LLM Agent                      │
│  "I suggest rewriting node X using MUX"       │
└─────────────────────┬────────────────────────┘
                      │ action proposal
                      ▼
┌──────────────────────────────────────────────┐
│           Layer 1: Pre-Validation             │
│  - Signal exists?                             │
│  - Gate type valid?                           │
│  - Rename conflict?                           │
└─────────────────────┬────────────────────────┘
                      │ validated action
                      ▼
┌──────────────────────────────────────────────┐
│           Layer 2: Graph Safety               │
│  - Clone graph (snapshot)                     │
│  - Apply mutation                             │
│  - BFS: detect combinational loops            │
│  - If loop → rollback, notify LLM            │
└─────────────────────┬────────────────────────┘
                      │ safe mutation
                      ▼
┌──────────────────────────────────────────────┐
│           Layer 3: Equivalence Check          │
│  - Bit-parallel simulation (2000 vectors)     │
│  - If mismatch → rollback                    │
│  - If match → commit                         │
└──────────────────────────────────────────────┘

The key principle: the engine never trusts the LLM. Every action is validated independently.

Layer 1: Pre-Execution Validation

Before any graph mutation, check that the proposed action is syntactically valid. This is a simple dictionary lookup — does the signal exist? Is the gate type in the allowed set? Is there a name conflict?

Why a separate layer? Because ~60% of LLM errors are obvious hallucinations — signal names that don’t exist, gate types that aren’t in the library. Catching these before any graph mutation is cheap (O(1) lookups) and prevents unnecessary cloning.

The validation is implemented as a pure function: input is the proposed action + current graph state, output is a list of errors (empty = valid). This makes it easy to test independently.

Layer 2: Combinational Loop Detection

The most dangerous LLM error is creating a cyclic dependency. In a combinational circuit, every signal must be computable from the primary inputs without cycles. A cycle means the output depends on itself — an unstable state that no simulator can evaluate.

Why BFS? Because cycle detection in directed graphs is a classic graph theory problem. BFS with in-degree tracking is O(V+E) — linear in the number of gates and wires. For a 10K-gate circuit, this takes under 1ms.

The algorithm tracks in-degree (number of incoming edges) for each node. Nodes with in-degree 0 are processed first, reducing the in-degree of their neighbors. If all nodes are processed, the graph is acyclic. If some nodes remain unprocessed, they form a cycle.

Why not DFS? DFS-based cycle detection is equally O(V+E) but requires maintaining a “visited” stack. BFS is simpler to implement correctly and produces a clear error message: “cycle detected between nodes X → Y → Z → X”.

If a cycle is detected, the mutation is rolled back and the LLM receives a specific error message explaining which nodes form the cycle. This feedback loop is critical — without it, the LLM would keep proposing cyclic mutations.

Layer 3: Transactional State Rollback

Every mutation is wrapped in a transaction:

1. Snapshot — Deep-copy the graph structure
2. Validate — Run Layer 1 checks
3. Apply — Execute the mutation
4. Loop check — Run Layer 2 BFS
5. Equivalence check — Bit-parallel simulation (2000 random vectors)
6. Commit or rollback — If any check fails, restore the snapshot

Why deep-copy? Because mutations are destructive — they modify the graph in place. Without a snapshot, there’s no way to undo a partial mutation. Deep-copy is expensive (~50ms for 10K gates) but necessary.

Why not incremental rollback? Because the mutation might have side effects — renaming a signal, updating fan-in lists, removing dangling nodes. Tracking all these changes for incremental rollback is more complex than just cloning the whole graph.

Why bit-parallel for equivalence check? Because we need to verify that the modified circuit produces the same outputs as the original for random inputs. Bit-parallel simulation (described in Blog 2) does this 15× faster than naive simulation.

Results: How Often Does the LLM Fail?

Across 50 test runs with different prompts:

LLM success rate: 44% — less than half of its suggestions are actually valid.

Without the defense layers, 56% of mutations would have corrupted the netlist. With the layers, zero corruptions reached the committed state.

What the LLM Actually Does Well

Despite the low raw success rate, the LLM is valuable because:

1. It explores the search space — suggesting signals and strategies that a human might not think of
2. It interprets context — “optimize the critical path near the output” is a natural language instruction that’s hard to encode as a rule
3. It learns from feedback — when told “that created a loop,” it adjusts its next suggestion

The sweet spot: LLM suggests, engine validates, LLM retries on failure. Typically converges in 3–5 attempts.

Why Not Just Use Rules?

A rule-based system (e.g., “always try MUX replacement on nodes with fanout > 3”) would have a higher success rate — maybe 80-90%. But it would explore the same search space every time.

The LLM’s value isn’t reliability — it’s creativity. It suggests mutations that a rule system would never try, because it understands natural language context like “this circuit is timing-critical near the output” or “this region has high logic depth.”

The defense layers make the LLM’s creativity safe. Without them, the creativity is a liability.

Lessons Learned

1. The defense layers are more important than the LLM — even a random signal generator would find useful rewrites, as long as the safety system catches bad ones
2. Clone-and-restore is expensive but necessary — deep copy on large graphs is slow, but the alternative (corrupted state) is worse
3. BFS for loop detection is O(V+E) — fast enough to run after every mutation, even on 10K-gate circuits
4. LLM latency is irrelevant for offline synthesis — the 200ms API call is noise compared to the seconds-long optimization loop. For interactive use, you’d need local inference.

Previous: Bit-Parallel Simulation — How equivalence checking is done 15× faster.

🔙 Back to Project Overview