OR-Agent: Bridging Evolutionary Search and Structured Research for Automated Algorithm Discovery

1. Problem Statement

Automating scientific discovery in complex, experiment-driven domains (such as Operations Research and simulation-based control) presents a challenge that current Large Language Model (LLM) approaches struggle to address. Existing methods typically rely on:

• Simple Mutation/Crossover: Iterative program generation via random mutations or crossover, lacking structured memory or long-term planning.
• Linear Workflows: Single-shot generation or shallow refinement loops that fail to mimic the non-linear nature of human research (branching hypotheses, backtracking, and deep local refinement).
• Population Ruin: In evolutionary search, a single "good" but brittle solution often dominates the population, causing diversity loss and invalidating the search space.
• Lack of Environment Interaction: Many systems fail to perform iterative debugging and environment probing, leading to wasted compute on avoidable execution errors.

The paper posits that effective automated discovery requires a framework that integrates structured hypothesis management, systematic backtracking, and principled reflection within a rich experimental environment.

2. Methodology: The OR-Agent Framework

OR-Agent is a configurable multi-agent system designed to emulate the scientific research workflow. It treats research ideas and programs as artifacts to be iteratively evolved, evaluated, and refined.

A. Multi-Agent Architecture

The system consists of specialized agents with distinct responsibilities:

• OR Agent: Manages global configuration and coordinates Lead Agents.
• Lead Agent: Acts as the principal investigator for a research round. It selects parent solutions, manages the research tree, and decides on expansion, backtracking, or termination.
• Idea Agent: Generates and refines high-level solution ideas based on the research tree and accumulated reflections.
• Code Agent: Translates ideas into executable code and handles iterative debugging.
• Experiment Agent: Executes experiments in complex environments (e.g., simulators), diagnoses failures, and summarizes findings.
• Solution Database: A persistent, shared repository storing all evaluated programs, metadata, and feedback to prevent "population ruin" and ensure diversity.

B. Tree-Structured Research Workflow

Unlike flat evolutionary loops, OR-Agent organizes research as a dynamically evolving tree:

• Nodes: Represent concrete research hypotheses (idea + code + experimental evidence).
• Edges: Represent derivation relationships (refinement or variation).
• Traversal: The Lead Agent uses a greedy policy (selecting the best unfinished leaf) to expand the tree.
• Coordinated Idea Generation: Instead of generating child ideas independently (which leads to redundancy), the Idea Agent generates a set of distinct child ideas in a single pass, ensuring broader coverage of the design space.
• Control Mechanisms: Users can control the "shape" of the tree (depth vs. breadth) to balance exploration (wide tree) and exploitation (deep tree).

C. Iterative Experimentation & Environment Probing

The Experiment Agent performs a closed-loop refinement process for each candidate:

1. Diagnosis: Identifies execution errors, performance bottlenecks, or safety violations.
2. Refinement: Applies bounded code updates, parameter tuning, or logic micro-refinements.
3. Callback Instrumentation: In complex environments (like cooperative driving), the agent can dynamically modify callbacks to expose intermediate system states (e.g., lane-change attempts, congestion levels), allowing for root-cause analysis rather than just observing final scores.
4. Reversion: Implements "soft" (LLM-reasoned) and "hard" (system-enforced) reversion to restore the best-performing configuration if recent changes degrade performance.

D. Hierarchical Reflection System

OR-Agent introduces a reflection mechanism modeled after optimization dynamics:

• Short-term Reflections (Verbal Gradients): Immediate feedback from single experiment steps guiding micro-updates.
• Experiment Summaries (Batch-Averaged Gradients): Compressed insights from a full refinement trajectory of a single node.
• Long-term Reflections (Verbal Momentum): Cross-solution patterns distilled by the Lead Agent to guide future research directions.
• Memory Compression: Older signals are compressed or decayed (semantic weight decay) to manage context windows while preserving salient insights.

3. Key Contributions

1. Structured Tree-Based Workflow: A novel framework that explicitly models branching hypothesis exploration and systematic backtracking, moving beyond simple mutation-crossover loops.
2. Evolutionary-Systematic Ideation: Unifies evolutionary selection of starting points with coordinated, multi-directional idea generation to reduce redundancy and improve design space coverage.
3. Hierarchical Reflection as Semantic Optimizer: A principled mechanism mapping natural language reflections to optimization concepts (gradients, momentum, weight decay) to govern research dynamics.
4. Environment-Aware Refinement: An iterative experimentation loop with dynamic callback instrumentation, enabling deep diagnosis of failure modes in complex simulators.
5. Diversity-Preserving Database: A persistent solution database that mitigates "population ruin" by maintaining a diverse set of evolutionary starting points.

4. Experimental Results

The authors evaluated OR-Agent on 12 classical combinatorial optimization problems (e.g., TSP, CVRP, BPP, MKP) and a complex cooperative driving simulation (SUMO).

• Classical OR Benchmarks:
  • OR-Agent achieved an average normalized score of 0.924, significantly outperforming strong baselines like FunSearch (0.323), AEL (0.477), EoH (0.582), and ReEvo (0.492).
  • It achieved the highest or near-highest scores on 10 out of 12 specific problem variants.
• Cooperative Driving (SUMO):
  • Under constrained runtime, OR-Agent scored 48.00, vastly surpassing the best baseline (16.10).
  • With extended runtime, it discovered a solution (90.24) that outperformed the SUMO default driving model (85.25), achieving higher efficiency and smoothness with zero collisions.
  • Baseline methods often converged to conservative, low-speed strategies (local optima), while OR-Agent escaped these traps through structured exploration.
• Ablation Studies:
  • Thinking Depth: A balanced tree depth yielded superior performance compared to excessively deep (low diversity) or shallow (low refinement) configurations.
  • Memory Compression: No explicit compression performed best, suggesting that aggressive compression may remove critical high-level signals, though moderate compression (400 words) performed worst, indicating a non-linear relationship between compression and performance.

5. Significance

• Paradigm Shift: OR-Agent moves the field from "generating code" to "conducting research." It formalizes the scientific method (hypothesis, experiment, reflection, backtracking) into an automated agent framework.
• Robustness in Complex Environments: By integrating iterative debugging and environment probing (callbacks), it handles the "messiness" of real-world simulations where single-pass generation fails.
• Generalizability: The framework is modular and configurable, allowing adaptation to heterogeneous problem structures, evaluation protocols, and exploration strategies.
• Scientific Infrastructure: It provides a reproducible, inspectable infrastructure for AI-assisted scientific discovery, offering a blueprint for how LLMs can act as collaborative researchers rather than just code generators.

In conclusion, OR-Agent demonstrates that combining evolutionary search with structured, tree-based research workflows and hierarchical reflection mechanisms leads to superior algorithm discovery in both theoretical and complex simulation-based domains.