Advancing Automated Algorithm Design via Evolutionary Stagewise Design with LLMs

This paper introduces EvoStage, a novel evolutionary paradigm that leverages large language models with a stagewise, multi-agent approach and real-time feedback to overcome the limitations of black-box modeling, successfully generating algorithm designs that outperform both human experts and existing methods in complex industrial tasks like chip placement and black-box optimization.

The Gist

Imagine you are trying to teach a brilliant but inexperienced apprentice how to build the perfect engine for a race car.

The Old Way (Traditional & Previous AI Methods):
In the past, you would give the apprentice a blank blueprint and say, "Build me an engine. Here is a list of rules." They would build something, you'd test it, and it would explode. You'd say, "Bad engine." They would try again, and it would catch fire. You'd say, "Worse engine."

This is how most current AI methods work. They treat the problem as a "Black Box." The AI (the apprentice) guesses a whole design, gets a single score at the very end (like "0 out of 10"), and has no idea why it failed. It's like guessing the combination to a safe by trying random numbers until the door opens. If the door takes hours to open (which is true for complex industrial problems like chip design), the AI runs out of time and money before it ever finds the right combination. It often "hallucinates" (makes up) solutions that look logical on paper but fail in reality.

The New Way (EvoStage):
This paper introduces EvoStage, a new way of teaching the AI. Instead of asking the apprentice to build the whole engine at once, you break the job down into small, manageable steps, like a video game with levels.

Here is how EvoStage works, using a few creative analogies:

1. The "Level-Up" Strategy (Stagewise Design)

Imagine the AI isn't trying to build the whole car at once. Instead, it plays a game with levels:

• Level 1: Just build the frame. (Did it hold together? Yes/No.)
• Level 2: Now add the wheels. (Do they spin? Yes/No.)
• Level 3: Now add the engine. (Does it start?)

At the end of every level, the AI gets immediate feedback. "Good job on the frame, but the wheels are too heavy." This feedback helps the AI understand why something is wrong before it wastes time building the rest of the car. This stops the AI from guessing wildly and helps it learn the "rules of the game" much faster.

2. The "Team of Specialists" (Multi-Agent System)

In the old days, one AI tried to do everything: design the engine, the brakes, the tires, and the paint. That's too much for one brain.

EvoStage hires a team:

• The Architect (Coordinator): This AI looks at the progress so far and says, "Okay, the frame is good, but we need to make the engine lighter for the next step."
• The Specialists (Coders): One AI designs the engine, another designs the brakes, another designs the tires. They only focus on their specific job, making them much better at it.

This teamwork ensures that the engine fits the brakes, and the brakes fit the frame, without anyone getting overwhelmed.

3. The "Zoom In / Zoom Out" View (Global-Local Perspective)

Sometimes, if you only focus on making the engine perfect (Local), you might forget that the car needs to be aerodynamic (Global). You could build a Ferrari engine in a boxy truck body.

EvoStage uses two types of thinking:

• Local Thinking: "Let's tweak this one screw to make the engine run smoother."
• Global Thinking: "Let's step back and look at the whole car. Maybe we need a completely different shape for the body to make this engine work better."

By switching between zooming in on details and zooming out to see the big picture, the AI avoids getting stuck in a "local trap" (a solution that is good but not the best).

The Real-World Results: Chip Placement

The authors tested this on a very hard problem: Chip Placement. Imagine trying to fit millions of tiny Lego blocks (transistors) onto a tiny Lego board (a computer chip) so that the wires connecting them are as short as possible. If the wires are too long, the chip is slow and hot.

• The Challenge: Humans are experts at this, but it takes them years of trial and error.
• The Result: EvoStage didn't just beat the human experts; it beat them in a fraction of the time.
  • On standard tests, it found better designs than the best human-designed algorithms.
  • On a real commercial 3D chip (a complex, real-world product), it improved the efficiency by 52% and reduced the wire length by 9%. That is a massive improvement in the world of chip manufacturing.

Why This Matters

Think of EvoStage as a super-efficient project manager for AI.

• It doesn't just guess; it learns step-by-step.
• It doesn't work alone; it coordinates a team.
• It doesn't just look at the details; it keeps the big picture in mind.

This allows AI to solve incredibly complex, expensive, and real-world problems (like designing chips, discovering new drugs, or optimizing materials) without needing millions of dollars in testing budgets. It turns AI from a "lucky guesser" into a "skilled craftsman."

Technical Summary

1. Problem Statement

The paper addresses the limitations of Automated Algorithm Design (AAD) in complex, real-world industrial scenarios. While Large Language Models (LLMs) have shown promise in generating algorithms, current state-of-the-art methods (e.g., FunSearch, AlphaEvolve, EoH) rely on a black-box modeling approach. This approach presents significant challenges in industrial settings:

• Limited Evaluation Budgets: Industrial problems (e.g., chip placement, drug discovery) often have expensive evaluation costs (hours per run), making the "trial-and-error" nature of black-box evolution infeasible.
• Hallucinations and Lack of Mechanism Awareness: Black-box methods provide LLMs only with a final performance score. Without intermediate feedback, LLMs lack awareness of the target problem's intrinsic mechanisms, leading to "hallucinated" designs that are logically coherent but practically incorrect.
• Data Scarcity & Case Variance: Unlike well-studied academic problems, industrial cases often lack high-quality pre-training data and exhibit significant variations between instances, causing LLMs to apply mismatched knowledge.
• Local Optima: Existing methods often struggle to balance local component optimization with global algorithm performance, leading to convergence on suboptimal solutions.

2. Methodology: EvoStage

The authors propose Evolutionary Stagewise Algorithm Design (EvoStage), a novel paradigm that bridges the gap between rigorous industrial demands and LLM capabilities. It integrates evolutionary algorithms with a multi-stage, multi-agent framework.

Core Components:

1. Stagewise Design (The Core Paradigm):

   • Inspired by Chain-of-Thought (CoT) reasoning, EvoStage decomposes a complex algorithm design task into a sequence of manageable stages.
   • Instead of generating a full algorithm at once, the LLM designs the algorithm stage-by-stage.
   • Real-time Intermediate Feedback: After each stage, the system provides the LLM with execution outcomes (e.g., wirelength, overflow, intermediate statistics). This grounds the LLM in the actual optimization process, allowing it to correct design directions and update its domain understanding dynamically, thereby reducing hallucinations.

2. Multi-Agent System:

   • To reduce the design space and ensure consistency, the system employs specialized agents:
     • Coordinator Agent: Reflects on intermediate information from previous stages and generates specific goals/guidance for the next stage.
     • Coder Agents: Multiple agents, each responsible for designing a specific algorithm component (heuristic) based on the coordinator's guidance.
   • This specialization prevents LLMs from generating grammatically incorrect or overly complex code when handling diverse tasks simultaneously.

3. Global-Local Perspective Mechanism:

   • To prevent the system from getting stuck in local optima (over-optimizing subtasks), EvoStage employs two types of operators analogous to "fast and slow thinking":
     • Local Perspective (Stagewise-Design): Iteratively refines specific components stage-by-stage using intermediate feedback.
     • Global Perspective:
       • Global-Explore: Prompts the LLM to generate a completely new multi-stage heuristic in one shot based on diverse references to escape local optima.
       • Global-Enhance: Prompts the LLM to refine an existing high-performing heuristic in one shot.
   • These operators are applied sequentially to balance exploration and exploitation.

4. Evolutionary Framework:

   • Maintains a population of algorithms (multi-stage heuristics).
   • Uses selection strategies to provide references for reproduction, ensuring the LLM focuses on promising designs rather than failed attempts.

3. Key Contributions

• Novel Paradigm: Introduction of EvoStage, the first framework to apply evolutionary stagewise design with intermediate feedback for LLM-based algorithm design in industrial scenarios.
• Mitigation of Hallucinations: By grounding LLMs in real-time execution feedback, the method significantly reduces hallucinations compared to black-box approaches.
• Multi-Agent Coordination: A novel architecture separating the "reflection/guidance" (Coordinator) from "implementation" (Coder) tasks to improve code quality and design consistency.
• Global-Local Balance: A mechanism to simultaneously optimize subtasks and the global algorithm structure, avoiding local optima.
• Broad Applicability: Demonstrated success across two distinct optimization domains: Gradient-based optimization (Adam optimizer for chip placement) and Black-box optimization (Acquisition functions for Bayesian Optimization).

4. Experimental Results

The authors evaluated EvoStage on open-source benchmarks and a real-world commercial 3D chip placement tool.

A. Chip Placement (Gradient-Based Optimization)

• Task: Designing learning rate and optimization step schedules for the Adam optimizer in Global Placement (GP).
• Benchmarks: ISPD 2005 and ICCAD 2015.
• Results:
  • EvoStage achieved historically state-of-the-art (SOTA) Half-Perimeter Wirelength (HPWL) results on every tested chip case within only 25 evaluations.
  • It outperformed human-expert designs (DREAMPlace, Xplace) and existing LLM methods (AlphaEvolve, EoH).
  • Pass Rate: EvoStage achieved a significantly higher "Pass Rate" (legal code that meets overflow constraints) compared to black-box methods, which often failed to generate valid code.
• Commercial Deployment: Applied to a commercial-grade 3D chip placement tool.
  • 9.24% improvement in HPWL on the logic die.
  • 52.21% improvement in optimization iterations (efficiency).

B. Black-Box Optimization (Bayesian Optimization)

• Task: Designing acquisition functions for Bayesian Optimization (BO).
• Benchmarks: Synthetic functions (Ackley, Rastrigin, etc.) and Neural Architecture Search (NAS) problems.
• Results:
  • EvoStage outperformed standard acquisition functions (UCB, EI) and other LLM-based methods (EoH, AlphaEvolve) across all benchmarks.
  • Achieved 100% Pass Rate on several cases, demonstrating superior code generation reliability.
  • Showed significant efficiency gains even when compared against methods with larger sampling budgets.

5. Significance

• Industrial Viability: EvoStage proves that automated algorithm design is feasible in high-stakes, low-budget industrial scenarios where traditional evolutionary methods fail due to evaluation costs.
• Productivity Leap: The ability to surpass human-expert designs in chip placement (a task requiring years of expertise) suggests a massive potential for elevating human productivity in engineering and scientific discovery.
• New LLM Application: It expands the utility of LLMs beyond chatbots and coding assistants to autonomous scientific discovery and system optimization, specifically addressing the "No Free Lunch" theorem by adapting to specific problem instances online.
• Future Direction: The work highlights the potential of "Stagewise Design" as a generalizable framework for solving complex, multi-step reasoning problems where intermediate feedback is available, paving the way for Level 4 agentic systems.