TL;DR
ParEVO is a novel framework that synthesizes high-performance parallel code for highly complex, irregular data structures like sparse graphs and unbalanced trees. By combining domain-specific fine-tuning on high-level algorithmic primitives with an Evolutionary Coding Agent (ECA) driven by real-machine execution feedback, ParEVO achieves an average 107× speedup on the ParEval benchmark and matches or outperforms expert human-written baselines.
What Problem Does This Paper Address?
While parallelizing "regular" workloads (like dense matrix multiplication) is well-supported by mature libraries, writing parallel code for irregular data structures—such as sparse graphs, non-uniform meshes, and unbalanced trees—remains a grand challenge in High-Performance Computing (HPC). Irregular algorithms feature unpredictable memory access patterns and dynamic workloads that make static load balancing ineffective, requiring sophisticated techniques like work-stealing and lock-free synchronization.
Current Large Language Models (LLMs) fail catastrophically in this domain due to a strong "sequential bias." When tasked with parallelizing irregular code, they often naively wrap sequential loops in basic parallel directives (like #pragma omp parallel for), ignoring data races, or introduce coarse-grained locks that serialize execution, making the parallel code slower than its sequential counterpart.
Methods
ParEVO tackles this challenge through a two-pronged approach: aligning the level of programming abstraction and introducing an evolutionary refinement loop.
- High-Level Abstraction Alignment: Instead of forcing LLMs to write error-prone, low-level threading primitives, ParEVO trains models to target high-level functional primitives (e.g.,
map,reduce,filter,scan) from ParlayLib (for C++) and RPB (for Rust). These primitives encapsulate complex scheduling and work-stealing logic, making the code structurally safer and easier for the LLM's token-local reasoning capabilities to generate correctly. - Evolutionary Coding Agent (ECA): To bridge the "last mile" of correctness and performance, ParEVO deploys a population-based evolutionary search over Abstract Syntax Trees (ASTs). Crucially, it rejects the unreliable "LLM-as-a-judge" paradigm. Instead, it uses deterministic external compilers, sanitizers (like ThreadSanitizer), and hardware profilers as adversarial critics to compute a strict fitness function based on runtime correctness and execution speed. It utilizes MAP-Elites to maintain structural diversity (code complexity and edit distance) in the program population, preventing the agent from getting trapped in local optima.
Datasets
The authors curated and utilized several datasets for training and evaluation:
- Parlay-Instruct Corpus: A newly introduced synthetic dataset containing 13,820 verified parallel coding tasks. It was generated via a "Teacher-Student-Critic" pipeline that mutated 593 human-authored "golden" seed examples and filtered them using a ground-truth compiler oracle.
- Performance Optimization Dataset: A collection of 20 challenging graph problems from the DMOJ competitive programming platform, used to extract high-quality optimization trajectories.
- Evaluation Suites: The framework was rigorously evaluated against the ParEval benchmark, expert human baselines from PBBSBench (C++) and RPB (Rust), and a held-out test set of competitive programming problems from DMOJ.
Key Insights and Ideas
- The Power of the Right IR: LLM parallel code generation depends heavily on the abstraction level of the target intermediate representation. High-level functional primitives eliminate the need for explicit state-tracking and synchronization management, aligning beautifully with Transformer architectures.
- The "Alignment Tax" Trade-off: Fine-tuning models on safe parallel primitives introduces a distinct correctness-speedup trade-off. Fine-tuned models generate significantly safer code (higher Pass@1 rates) but sometimes sacrifice peak performance because they conservatively avoid risky, fine-grained atomic operations in favor of stable, high-level primitives.
- Compilers as Adversarial Critics: Concurrency bugs are notoriously latent. By executing candidates multiple times on massive inputs (up to 10 million vertices) under sanitizers, ParEVO forces data races to manifest as observable failures, providing a rigorous empirical filter that text-based LLM reflection cannot replicate.
Key Results
- Massive Speedups: On the ParEval benchmark, ParEVO achieved an average 107× speedup over sequential baselines, outperforming state-of-the-art commercial models like GPT-5-Thinking and Gemini-3-Pro.
- Graph Problem Mastery: ParEVO delivered a robust 13.6× speedup on highly complex irregular graph problems.
- Beating Human Experts: When evaluated against expert human-written code, ParEVO matched or exceeded performance, achieving a remarkable 4.1× speedup on the highly irregular Maximal Independent Set (MIS) kernel in Rust by discovering a superior parallel strategy.
- Strong Scaling: The synthesized code demonstrated excellent strong scaling on multi-core architectures up to 64 cores, particularly on regular kernels like the Discrete Fourier Transform (DFT).
Limitations and Future Work
- Architectural Scope: ParEVO is currently optimized exclusively for shared-memory multicore architectures. It does not yet handle distributed-memory paradigms (like MPI), where communication latency and data partitioning introduce entirely different optimization constraints.
- Inference Latency: The evolutionary agent trades test-time compute for execution-time efficiency. Compiling and profiling multiple candidates iteratively is computationally expensive, though the authors argue this cost is well-amortized for HPC kernels run trillions of times in production.
- Geometric Hallucinations: In unfamiliar algorithmic domains with specialized logic (e.g., computational geometry), the fine-tuned models occasionally suffered from "confident hallucinations," such as calling non-existent library functions. The authors plan to integrate formal verification tools into the loop to mitigate these semantic errors.
Summary updated