PrefixGPT: Prefix Adder Optimization by a Generative Pre-trained Transformer

AI summary

Overview

Research area: Hardware design automation (electronic design automation) combined with generative machine learning, specifically applying GPT-style generative pre-trained Transformers to digital arithmetic circuit design.

Technical level: Intermediate. The paper assumes some familiarity with digital adder circuits, prefix graphs, and Transformer architectures, but the core ideas are explained with concrete examples.

Scope: Develops a decoder-only Transformer that generates optimized prefix adder topologies from scratch as coordinate sequences, guaranteeing valid designs by construction, and benchmarks it against reinforcement-learning and Monte-Carlo-tree-search baselines on 16-, 24-, 32-, and 48-bit adders.

What This Paper Is About

Designing an optimized prefix adder means searching an exponentially large space of structures that must obey rigid construction rules, and existing AI-based methods do this by incrementally editing an existing design. Because they start from a hand-made circuit such as Sklansky, Kogge-Stone, or Brent-Kung, they inherit an initialization bias: their results change dramatically depending on which starting design they are given, and their edits frequently break the design rules, requiring expensive repair steps.

The paper asks whether a GPT-style model can instead learn the "grammar" of valid prefix adders and generate optimized topologies directly from scratch, so that every generated design is legal by construction and no starting design is needed.

Key Contributions

1. A sequence formulation of prefix adder design. The authors convert a prefix graph into an n×n binary lower-triangular prefix matrix, then scan it to produce a coordinate sequence, reformulating adder optimization as a sequence generation task solvable by GPT-style models.

2. A dynamic legality mask encoding design rules. The input, output, and merge rules of prefix adders are recast as a legality mask that zeroes out infeasible next coordinates at every generation step, so every produced design is valid by construction with no repair step. The mask supports parallel implementation on GPUs.

3. A customized GPT architecture for 2D coordinates. Because standard GPT models handle one-dimensional token sequences, PrefixGPT adds a spatial coordinate embedding with rotary positional embedding (RoPE) applied separately to row and column indices, and a two-head Transformer backbone whose row head and column head predict the next row and column coordinate in sequence.

4. A pre-training plus reinforcement-learning fine-tuning pipeline. The model is pre-trained by self-supervised learning on 1,000,000 randomly synthesized valid coordinate sequences, then fine-tuned with group relative policy optimization (GRPO) plus a best-design retrieval mechanism to optimize area-delay product.

Main Findings

• Best size on all 12 tested size/depth combinations. Across 16-, 24-, 32-, and 48-bit adders with depth limits h, h+1, and h+2 (where h is the minimum possible depth for the given bit-width), PrefixGPT achieved the smallest prefix graph size on all 12 pairs, with a maximum size reduction of 59.1% on the 48-bit task under Kogge-Stone initialization.

• New best area-delay product at 48 bits. PrefixGPT discovered a design with a minimum ADP of 121.3 μm²·ns, a 7.7% improvement over the minimum found by ArithTree and a 15.1% improvement over PrefixRL.

• Large average-ADP reduction. Averaged over all designs, PrefixGPT reached a mean ADP of 91.14 μm²·ns for 32-bit adders and 185.15 μm²·ns for 48-bit adders, representing 71.9% and 79.1% reductions over the mean ADP of ArithTree.

• Better than the generative language-model baseline at 16 bits. PrefixGPT's minimum ADP of 31.13 μm²·ns at 16-bit beat PrefixLLM's 34.01 μm²·ns. PrefixLLM could only be compared using data from its authors and original paper, because it scales only to 16-bit adders and takes over 200 seconds per design.

• Far greater stability. PrefixGPT's standard deviation in ADP was consistently lower than competing methods; at 48-bit it showed a reduction of over 94% compared to ArithTree (25.2 versus 422.2).

• Robustness to initialization. Evaluated with four initializations (Sklansky, Kogge-Stone, Brent-Kung, and random), PrefixGPT was consistent across all of them, whereas ArithTree and PrefixRL fluctuated or failed to find a solution (marked "-" in the tables) under tight depth limits. Under random initialization, PrefixGPT's designs closely matched its own global Pareto frontier and often outperformed the best frontiers of the other methods. In the random setting, PrefixGPT began with no initial design in its database at all.

• Fast generation. PrefixGPT takes approximately 7 ms to generate one design for the 32-bit task.

• Ablations point to pre-training as the main driver. Over 20 repeated 32-bit random optimization runs, removing pre-training lowered final average reward by 31.6% and removing RoPE lowered it by 16.6%. Removing the KL-divergence regularization term and best-design retrieval lowered final average reward by only 1.3% but increased the standard deviation from 0.018 to 0.038 (+110%) at the final iteration.

• The model internalizes design rules. With the legality mask removed after pre-training, the generation legal rate converged to nearly 100% with sufficient training. Attention-score inspection of the column head showed the model focusing on the correct candidate positions in row L_k^c − 1, matching the merge rule — evidence that pre-training goes beyond pattern memorization.

Methodology in Plain English

The authors first change how a prefix adder is written down. Instead of a graph, they use a binary matrix where a 1 at row j and column i means a node connecting bits j through i exists. Reading the 1s from top to bottom, and within each row from the diagonal leftward, turns the whole circuit into a list of (row, column) coordinate pairs — something a language model can generate one token at a time.

The catch is that most coordinate pairs would produce an illegal circuit. So the authors derive, from the three design rules, exactly which coordinates are allowed next given the partial sequence already generated, and build a mask that forces the probability of every other coordinate to zero. Invalid designs simply cannot be sampled.

The model itself is a decoder-only Transformer modified for two-dimensional data. Each coordinate is embedded by applying separate learned embeddings and rotary positional embedding to its row and column parts, then concatenating them into one token. The backbone is a shared decoder of four Transformer layers, followed by a row head (one decoder layer) that predicts the row, and a column head (two decoder layers) that takes both the shared and row hidden states to predict the column — a sensible design, since the legal column depends on the row.

Training happens in two stages. Pre-training uses self-supervised next-coordinate prediction on 1,000,000 valid sequences produced by random walks, teaching the model the grammar of legal adders. Fine-tuning uses reinforcement learning with GRPO: the policy model samples a group of 512 valid adders per iteration, each scored by a reward equal to the negative area-delay product, with a KL-divergence penalty against a frozen copy of the pre-trained model to prevent collapse into degenerate designs. A best-design retrieval mechanism keeps a database of previously generated designs and re-injects the lowest-ADP ones (at most 10% of the batch) into each update. Manual designs can be seeded into this database so the policy learns from them.

Evaluation compares against PrefixRL (deep Q-learning) and ArithTree (Monte Carlo tree search) at four bit-widths with four initializations, running 10 independent trials per combination, each capped at 100,000 candidate design evaluations. Physical area and delay are then measured by synthesizing the designs with the open-source tool ABC using the Nangate45 Open Cell Library.

Why This Matters

Impact on research. The paper argues against refinement-based optimization as the dominant paradigm for structured hardware design. By showing that a generative model can learn a circuit family's construction rules well enough to generate valid designs unassisted, it suggests that the initialization bias and repair overhead plaguing prior RL and MCTS methods can be avoided rather than managed.

Real-world applications.

• General-purpose and AI processors, where adder delay directly affects clock frequency and area directly affects silicon cost.
• Signal processing hardware, including the DSP datapaths cited by the authors as a primary application domain for adders.
• AI accelerator arithmetic units, which the paper names alongside signal processing as a key application.
• Any ASIC or FPGA design flow using standard-cell libraries, since the designs are validated through real synthesis with a commercial-style cell library (Nangate45) rather than only in simulation.

Industry relevance. Adder design is a recurring, manually intensive task in processor and accelerator development. A method that finds smaller and faster circuits than existing automated approaches, runs in roughly 7 ms per design, and does not require a good starting point or a repair flow could shorten design iterations and be more robust to the initial choices engineers make.

Future Directions

• Relaxing the MSP restriction. The authors restrict the more-significant parent of each merge node to be the node just generated, following prior work. They state explicitly that this simplifies the generation task but sacrifices some optimality, and they leave relaxing it as future work.

• Scaling beyond 48 bits. PrefixGPT was pre-trained on sequences up to n = 48 due to GPU memory constraints, even though a pre-trained model can be re-targeted to any smaller bit-width by resetting the end-of-sequence coordinate. Extending to larger widths, such as 64-bit, is a direct open question.

• Applying the framework to other circuit families. The sequence-plus-legality-mask recipe is presented as a general way to encode strict structural design rules, which raises the question of whether it transfers to other arithmetic units or structured circuit topologies beyond adders.

• Understanding and strengthening the pre-training stage. Since removing pre-training caused the largest ablation drop (31.6%), and the model's attention aligns with the merge rule after pre-training, further work could characterize exactly what design knowledge is internalized and how to elicit it more efficiently.

Target Audience

This paper is most useful to researchers and practitioners in electronic design automation and AI-for-hardware, particularly those working on arithmetic circuit optimization, reinforcement learning for design space exploration, or generative models applied to structured domains. Graduate students in computer architecture, VLSI design, or machine learning with an interest in hardware design automation will find the sequence formulation and legality-mask technique instructive. Readers without background in digital arithmetic or Transformer models will need to consult the cited references on prefix adders and GPT architectures first.

Authors’ abstract

Prefix adders are widely used in compute-intensive applications for their high speed. However, designing optimized prefix adders is challenging due to strict design rules and an exponentially large design space. We introduce PrefixGPT, a generative pre-trained Transformer (GPT) that directly generates optimized prefix adders from scratch. Our approach represents an adder's topology as a two-dimensional coordinate sequence and applies a legality mask during generation, ensuring every design is valid by construction. PrefixGPT features a customized decoder-only Transformer architecture. The model is first pre-trained on a corpus of randomly synthesized valid prefix adders to learn design rules and then fine-tuned to navigate the design space for optimized design quality. Compared with existing works, PrefixGPT not only finds a new optimal design with a 7.7% improved area-delay product (ADP) but exhibits superior exploration quality, lowering the average ADP by up to 79.1%. This demonstrates the potential of GPT-style models to first master complex hardware design principles and then apply them for more efficient design optimization.