ParEVO: Synthesizing Code for Irregular Data: High-Performance Parallelism through Agentic Evolution

Parallelizing code for irregular data structures (sparse graphs, unbalanced trees, non-uniform meshes) is notoriously hard, and current LLMs fail catastrophically on such tasks, generating code riddled with race conditions, deadlocks, and poor scaling. We address this with ParEVO, a framework for synthesizing high-performance parallel algorithms for irregular data, built on three contributions: the Parlay-Instruct Corpus of 13,820 tasks generated via a "Critic-Refine" pipeline that filters for empirically performant uses of Work-Span primitives; specialized DeepSeek, Qwen, and Gemini models fine-tuned to the semantics of the ParlayLib library; and an Evolutionary Coding Agent (ECA) that repairs the "last mile" of correctness using compiler and profiler feedback. On the ParEval benchmark, ParEVO achieves an average 107x speedup and a 13.6x speedup on highly complex irregular graph problems, outperforming commercial models like GPT-5-Thinking and Gemini-3-Pro, while matching expert human-written baselines and reaching up to a 4.1x speedup on kernels such as Maximal Independent Set. This demonstrates that AI-driven agents can effectively navigate the complex landscape of high-performance computing. Source code and datasets are available at https://github.com/WildAlg/ParEVO.

Modern computers get their speed from doing many things at once, splitting a job across dozens of processors working in parallel. But writing software that does this correctly is one of the hardest problems in computing — especially for tasks where the work is unpredictable and uneven, like exploring a sprawling network of connections or searching through a lopsided branching structure. You can't divide such work into neat equal pieces in advance, so some processors sit idle while others are overloaded, and subtle timing errors between them can silently corrupt the results. Today's AI coding assistants fail badly here, producing programs that crash, hang, or run slowly. We built ParEVO, a system that teaches AI to write fast, correct parallel programs for exactly these unruly tasks. It learns from a large library of expert examples, then refines its own code by repeatedly testing it, catching errors, and improving — much like a programmer debugging through trial and error. ParEVO's programs run dramatically faster than those written by leading AI assistants, and on some of the hardest problems they even match or beat code written by human experts. This suggests AI can take on genuinely difficult software engineering, not just routine coding.