RAG-Enhanced Kernel-Based Heuristic Synthesis (RKHS): A Structured Methodology Using Large Language Models for Hardware Design

Shiva Ahir, Alex Doboli · 2026

Read RAG-Enhanced Kernel-Based Heuristic Synthesis (RKHS): A Structured Methodology Using Large Language Models for Hardware Design by Shiva Ahir, Alex Doboli (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-26153.txt.

Introduction

Ahir and Doboli propose a method for letting large language models build reusable tuning rules for electronic design tools, beyond one-shot code making. Their lookup-based kernel building joins compact rule templates with a refinement loop with self-feedback. Applied to latency-cutting list scheduling in high-level synthesis, a test model shortens average plans by up to eleven percent over a baseline planner with only modest runtime cost. The loop spreads to other design problems.

Catalog record

CREATORShiva Ahir, Alex Doboli
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE19091
LICENSEhttp://creativecommons.org/publicdomain/zero/1.0/
RIGHTSCC0
SOURCEarXiv

Source: https://arxiv.org/abs/2604.26153

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

RAG-Enhanced Kernel-Based Heuristic Synthesis (RKHS): A Structured Methodology Using Large Language Models for Hardware Design Shiva Ahir, Alex Doboli Abstract Heuristic design upholds modern electronic design automation (EDA) tools, yet crafting effective placement, routing, and scheduling strategies entails substantial expertise. We study how large language models (LLMs) can systematically synthesize reusable optimization heuristics beyond one-shot code generation [ 2 , 3 , 4 ] . We propose RAG-Enhanced Kernel-Based Heuristic Synthesis (RKHS) , which integrates retrieval-augmented generation (RAG) [ 1 ] , compact kernel heuristic templates [ 9 , 10 ] , and an LLM-driven refinement loop inspired by iterative self-feedback [ 6 ] . Applied to latency-minimizing list scheduling in high-level synthesis (HLS) [ 11 , 14 ] , a prototype reduces average schedule length by up to 11% over a baseline scheduler with only 1.3 × \times runtime overhead, and the structured retrieval-synthesis loop generalizes to other EDA optimization problems. Introduction Modern EDA relies on handcrafted heuristics to address NP-hard problems in placement, routing, scheduling, and high-level synthesis [ 11 , 14 ] . These heuristics encode expert knowledge about structural patterns and performance–power–area (PPA) trade-offs, but their design is labor-intensive, domain-specific, and difficult to generalize across benchmarks or technology nodes. As design complexity increases, manual heuristic design and refinement become unsustainable. Graph motif mining has been studied in network science to detect recurring subgraph structures and classical scheduling heuristics exploit structural signals such as critical paths and fanout [ 11 , 14 ] . However, prior work does not systematically extract and cluster motifs from training DAGs for reusable heuristic synthesis. RKHS bridges this gap by deterministically mining structural motifs and integrating retrieved motif kernels into LLM-generated priority functions. Most existing approaches treat LLMs as one-shot code generators rather than structured synthesizers of reusable optimization strategies for graph scheduling [ 11 , 14 ] . They lack a principled mechanism to extract structural motifs from prior designs and recombine them into customized priority functions with consistent metric gains. We address this limitation by casting heuristic synthesis as a retrieval-augmented, kernel-based optimization loop, leveraging structural retrieval [ 2 ] and reusable kernels grounded in kernel-method perspectives. 1.1 Proposed Solution We focus on the following question: Can we automatically synthesize optimization heuristics that are executable, interpretable, and transferable across related instances of an EDA problem class? We treat list scheduling as a fixed meta-algorithm , where the key design parameter is the priority function that ranks ready operations. Rather than redesigning the scheduler, we automatically customize this rule for each input graph. In contrast to reinforcement learning or black-box search methods that tune heuristic parameters globally, RKHS explicitly decomposes heuristic synthesis into structural motif retrieval and interpretable template integration. Unlike prior work that generates heuristics directly via one-shot LLM prompting [ 11 , 14 ] , we separate structural retrieval from heuristic synthesis : reusable motifs extracted from existing designs [ 9 , 10 ] guide the construction of a deterministic priority function grounded in kernel-based regularization [ 6 ] . This yields enhanced latency, interpretable scoring rules, and transferability across related designs through retrieval-driven adaptation. 1.2 Problem Formulation We consider latency-minimizing list scheduling for high-level synthesis, a standard precedence-constrained scheduling problem with resource limits [ 11 , 14 ] . The input is a directed acyclic graph (DAG) G=(V,E) where each node v\in V is an operation and each edge (u,v)\in E encodes precedence u\prec v . Each operation has type \tau(v)\in\mathcal{T} and duration d(v)\in\mathbb{N} (often d(v)=1 ). Resource constraints are modeled by capacities R_{t}\in\mathbb{N} for each type t\in\mathcal{T} , limiting the number of type- t operations that can execute per cycle. A schedule is a start-time assignment s:V\rightarrow\mathbb{N} and is feasible if: Precedence: \displaystyle s(v)\geq s(u)+d(u)\qquad\forall(u,v)\in E (1) Resources: \displaystyle\sum_{\begin{subarray}{c}v\in V:\ \tau(v)=t\end{subarray}}\mathbf{1}\{\,s(v)\leq c<s(v)+d(v)\,\}\ \leq\ R_{t}\qquad\forall t\in\mathcal{T},\ \forall c\in\mathbb{N}. (2) The objective is to minimize makespan (latency): L(s)\;=\;\max_{v\in V}\big(s(v)+d(v)\big),\qquad s^{\star}=\operatorname*{arg\,min}_{s\ \text{feasible}}L(s). (3) Baseline (Classical List Scheduling): List scheduling iteratively selects ready operations subject to resource constraints [ 11 , 14 ] . Let \mathrm{pred}(v)=\{u:(u,v)\in E\} . At cycle c , the ready set is \mathcal{R}(c)=\left\{v\in V\setminus\mathcal{S}:\ \forall u\in\mathrm{pred}(v),\ s(u)+d(u)\leq c\right\}, (4) where \mathcal{S} is the set of already scheduled nodes. A list scheduler selects \mathcal{A}(c)\subseteq\mathcal{R}(c) subject to resource limits and assigns s(v)=c for v\in\mathcal{A}(c) . The key design freedom is the priority function \pi(v;\,G,\mathrm{state}) , commonly based on levels, criticality, and fanout [ 11 , 14 ] . Input DAG \displaystyle G=(V,E) types, d(v) , R_{t} Feature / Embedding f(G) crit, fanout, level Kernel Retrieval Top- m by \mathrm{sim}(G,K) LLM Synthesis Prompt = spec + kernels Schedule & Score L(s) , T_{\mathrm{run}} J(H;G) Figure 1: Overview of RKHS including feature extraction, retrieval, LLM synthesis, evaluation. 1.3 RKHS: Solution Overview RKHS is a structured framework for synthesizing priority functions for resource-constrained list scheduling [ 14 , 13 ] . RKHS treats heuristic design as a reusable pattern-learning problem: instead of generating a priority rule from scratch, it retrieves structurally similar scheduling patterns (kernels) distilled from training DAGs and uses them to guide synthesis as explained in Algorithm 1. Each kernel captures two components: (i) a structural signature summarizing recurring motifs and graph statistics (e.g., critical-path summaries, fanout distributions, and reconvergence markers), and (ii) a heuristic template encoding scheduling preferences associated with those structures. Unlike classical kernel methods that operate in feature space, our kernels represent reusable structural scheduling primitives distilled from prior DAGs. The kernel library is constructed from training graphs via deterministic motif extraction and structural clustering (details in Appendix). At inference time, given a new graph G , we compute a deterministic structural embedding and retrieve the most similar kernels. Their structural signatures and templates are provided to the LLM via retrieval-augmented prompting, which synthesizes a compact, deterministic priority function \pi(v) . The synthesized rule is then evaluated using list scheduling under precedence and resource constraints, and refined using latency-based feedback [ 6 ] . The key novelty lies in (1) identifying reusable structural motifs from prior designs and (2) combining multiple retrieved kernel signals during synthesis, enabling priority functions that integrate complementary scheduling cues such as criticality, reconvergence, and resource pressure. 1.4 Similarity and Retrieval Let f(G) denote an embedding of a graph and f(K) the embedding of a kernel signature. We use cosine similarity: \mathrm{sim}(G,K)=\frac{\langle f(G),f(K)\rangle}{\|f(G)\|_{2}\,\|f(K)\|_{2}}. (5) RKHS retrieves top- m kernels: \mathcal{K}_{G}=\mathrm{TopM}_{K\in\mathcal{K}}\ \mathrm{sim}(G,K). (6) 1.5 Heuristic Synthesis Objective RKHS seeks a parameterized heuristic policy H_{\theta} that maps scheduler state and graph context to a priority score: H_{\theta}:\ (\mathrm{state},G,v)\ \mapsto\ \pi(v),\qquad v\in\mathcal{R}(c). (7) The scheduler selects feasible actions greedily by descending priority, following standard list scheduling practice [ 11 , 14 ] : \mathcal{A}(c)=\textsc{SelectFeasible}\big(\mathcal{R}(c),\{\pi(v)\}_{v\in\mathcal{R}(c)},\{R_{t}\}\big). (8) Scoring Function: Each candidate heuristic is evaluated by a score combining latency and runtime with infeasibility penalties: J(H;G)=-L\big(s_{H}(G)\big)-\lambda\,T_{\text{run}}(H,G)-\mu\,\mathbf{[}\text{infeasible}], (9) where s_{H}(G) is the schedule produced by heuristic H on graph G . For a validation set \mathcal{G}_{\mathrm{val}} , we report the mean validation score \bar{J}(H)=\frac{1}{|\mathcal{G}_{\mathrm{val}}|}\sum_{G\in\mathcal{G}_{\mathrm{val}}}J(H;G). (10) Algorithm 1 Algorithm 1: RAG-Enhanced Kernel-Based Heuristic Synthesis. Implementation: GPT-4, |\mathcal{K}|=50 , |\mathcal{G}_{\text{train}}|=200 , |\mathcal{G}_{\text{val}}|=50 , \lambda=0.01 , \mu=5000 , N=3 , m=5 . 1: Training graphs \mathcal{G}_{\mathrm{train}} , kernel library \mathcal{K} , LLM, iterations N , top- m retrieval 2: Best heuristic H^{\star} 3: Initialize history \mathcal{H}\leftarrow\emptyset 4: for i\leftarrow 1 to N

Read the complete text