PrefixAgent: An LLM-Powered Design Framework for Efficient Prefix Adder Optimization

Technical Summary: PrefixAgent

Problem Statement
Prefix adders are fundamental arithmetic circuits in digital systems, yet their design space grows exponentially with bit-width, making exhaustive exploration impractical. Traditional design methodologies rely on regular structures (e.g., Kogge–Stone, Brent–Kung) or manual optimization, which often fail to balance area, delay, and power under diverse timing constraints and non-uniform input arrival times. While machine learning approaches (RL, VAE, MCTS) have been proposed to automate this process, they suffer from poor generalization, scalability issues due to extensive retraining requirements for new scenarios, and inefficiency in exploring large action spaces. Furthermore, existing Large Language Model (LLM) applications in circuit design face two critical limitations: (1) the inability to efficiently reason about complex graphs with more than 20 nodes, and (2) a lack of high-quality, interpretable training data for fine-tuning models on specific optimization tasks.

Methodology
The paper proposes PrefixAgent, an LLM-powered design framework that addresses these challenges through a two-phase decomposition and tool-integrated reasoning (TIR) paradigm.

1. Two-Phase Decomposition:

   • Phase I (Backbone Optimization): Instead of generating a full prefix graph directly, the framework decomposes the problem into "backbone synthesis" and "local structure refinement." The backbone is defined as the subgraph computing the carry for the most significant bit (MSB). This reduces the design space from a product of Catalan numbers to a single Catalan number, significantly simplifying the complexity. The LLM iteratively refines an initial serial backbone structure by performing "regroup" operations (reorganizing subtrees) to optimize the grouping pattern.
   • Phase II (Local Structure Refinement): Once an optimized backbone is established, a full prefix adder is constructed by adding auxiliary nodes. The LLM then performs local structural refinements (e.g., level optimization, fanout reduction, node cloning) guided by feedback from physical implementation tools to resolve timing violations.

2. Tool-Integrated Reasoning (TIR):
   PrefixAgent employs function calling to allow the Large Reasoning Model (LRM) to delegate precise structural modifications to external tools. The LLM focuses on high-level decision-making (identifying what to optimize and where), while external tools execute the modifications and provide feedback (e.g., timing-annotated S-expressions, physical metrics). This bridges the gap between high-level reasoning and algorithmic precision.

3. E-Graph Based Data Generation:
   To address the scarcity of high-quality training data, the authors utilize e-graphs and equality saturation. They define a domain-specific intermediate language (BackboneLang) to represent backbone structures as S-expressions. By applying associativity rewrite rules within an e-graph, they systematically explore the solution space. The framework extracts optimized backbone candidates using a timing-aware cost function and utilizes the e-graph explainer to generate interpretable rewrite trajectories. These trajectories serve as the ground truth for synthesizing Chain-of-Thought (CoT) reasoning data, which is used to fine-tune the LRM.

Key Contributions

• PrefixAgent Framework: The first LLM-based approach capable of scaling prefix adder optimization to 64-bit designs, outperforming commercial tools.
• Novel Design Perspective: A decomposition strategy separating backbone generation from local refinement, enabling efficient reasoning and zero-deficiency adder synthesis.
• Data Generation Paradigm: A systematic method using e-graphs to generate large-scale, high-quality, and interpretable optimization trajectories for fine-tuning LRMs, overcoming data scarcity in circuit design.
• Tool-Integrated Reasoning: An architecture where the LLM acts as a controller invoking external tools for execution, ensuring structural validity and physical feasibility.

Experimental Results
Experiments were conducted using the QwQ-32B model fine-tuned on the generated dataset, evaluated under both uniform and non-uniform input arrival time profiles using the NanGate45 library and OpenROAD flow.

• Performance: PrefixAgent synthesizes prefix adders with smaller areas than baseline methods (including DP, MCTS, RL, VAE, and PrefixGPT) in nearly all configurations. The area advantage widens significantly at larger bit-widths (e.g., up to 11.3% reduction at 64-bit compared to the best baseline).
• Generalization: The framework demonstrates strong generalization, achieving superior results on unseen bit-widths (e.g., 54-bit) and non-uniform arrival profiles not present in the training set.
• Efficiency: PrefixAgent achieves over a 10× speedup compared to search-based baselines (MCTS, RL, VAE) because it avoids retraining for each new scenario and performs targeted optimizations guided by the LRM.
• Commercial Flow: When evaluated under a commercial physical design flow (32nm technology), PrefixAgent-generated adders maintained smaller areas compared to commercial synthesis tools.
• Ablation Studies: Results confirm the necessity of Phase II refinement, the superiority of the Enhanced Prefix Representation (EPR) over grid/adjacency-list encodings for LLM reasoning, and the critical role of CoT reasoning in achieving high-quality results.

Significance
The paper claims that PrefixAgent represents a significant step forward in automating arithmetic circuit design. By decomposing the complex design task into manageable subproblems and leveraging e-graphs for high-quality data generation, it overcomes the scalability and generalization limitations of previous ML-based methods. The framework demonstrates that LLMs, when properly guided by tool integration and fine-tuned on interpretable reasoning trajectories, can effectively navigate complex design spaces to outperform both traditional heuristics and commercial EDA tools, particularly for large-scale designs. The authors suggest that this data generation paradigm and decomposition strategy can be extended to other datapath optimization tasks, such as multiplier optimization.