TL;DR
BehaveSim is a novel metric that measures algorithmic similarity by comparing "problem-solving trajectories"—the sequence of intermediate steps an algorithm takes—rather than just analyzing code syntax or final outputs. By integrating this behavioral lens into Large Language Model (LLM)-based automated design, researchers have significantly improved the performance and diversity of AI-generated algorithms for complex optimization tasks.
The Bottleneck in AI-Generated Algorithms
We are entering the era of Large Language Model-based Automated Algorithm Design (LLM-AAD). Instead of relying solely on human experts to write algorithms, researchers are using LLMs to iteratively propose and refine code. However, a major bottleneck has emerged in this paradigm: how do we know if a newly generated piece of code represents a genuinely new idea?
Existing code similarity metrics generally fall into two inadequate camps:
- Static Metrics: These evaluate the text (tokens) or structure (Abstract Syntax Trees) of the code. They fail when a tiny syntactic change fundamentally alters the logic while keeping the code 99% identical.
- Output Metrics: These check if two programs produce the same final result. They fail because completely different strategies (like Bubble Sort vs. Quick Sort) can produce the identical sorted list, masking their unique underlying "behaviors."
Without a reliable way to distinguish genuine logical innovation from mere syntactic "re-skinning," LLM search processes often get stuck in local optima. They end up repeatedly generating minor variations of the same mediocre strategy rather than exploring new logical pathways.
Introducing BehaveSim: Measuring the Trajectory
To solve this, the authors introduce BehaveSim, a metric that shifts the focus from the static code itself to the Problem-Solving Trajectory (PSTraj).
- PSTraj: For any iterative algorithm (such as a Traveling Salesman Problem solver adding one city at a time), BehaveSim records the sequence of intermediate solutions produced during execution.
- Dynamic Time Warping (DTW): Because different algorithms might solve a problem at different speeds or in a different number of steps, BehaveSim uses DTW to align and compare these trajectories. This allows the metric to recognize that two algorithms are "behaving" similarly even if one is more efficient than the other.
A single-word change in a prompt—like switching argmin to argmax—can lead to a "behavioral flip" that static analysis misses entirely. BehaveSim captures this by mapping the divergent problem-solving trajectories.
Integration into LLM-AAD Frameworks
The authors integrated BehaveSim into two state-of-the-art LLM-AAD frameworks to prove its utility:
- FunSearch + BehaveSim: Uses behavioral similarity to manage "islands" of diverse algorithms, ensuring the LLM explores distinctly different logical neighborhoods.
- EoH + BehaveSim: Uses behavioral novelty as a secondary objective to guide the evolutionary search toward entirely unexplored strategies.
Key Insights and Results
The researchers evaluated BehaveSim using a curated similarity benchmark and three complex Automated Algorithm Design (AAD) tasks: the Admissible Set Problem (ASP), the Traveling Salesman Problem (TSP), and the Circle Packing Problem (CPP). Testing was conducted against standard FunSearch and EoH using GPT-5-Nano (via API).
1. Behavioral Diversity Drives Better Performance The most striking insight is that explicitly rewarding behavioral diversity (rather than just code diversity) helps the LLM find higher-quality solutions. It prevents the "echo chamber" effect where the model keeps refining the same flawed logic. In the TSP task, FunSearch+BehaveSim achieved a relative gap to the optimum of 17.37%, a significant improvement over the 25.22% achieved by the original FunSearch.
2. Consistent Superiority Across Tasks Across all three tasks (ASP, TSP, CPP), the BehaveSim-integrated versions consistently outperformed their original counterparts in both the "Top-1" and "Top-10" algorithm categories.
3. Flawless Metric Accuracy on Edge Cases On "Type-3" algorithm pairs (different code syntax, but identical behavior), BehaveSim achieved a perfect similarity score of 1.0. In contrast, traditional metrics like BLEU (0.42) and AST (0.76) incorrectly suggested the algorithms were quite different.
4. A Tool for "AI-Phylogeny" Beyond optimization, BehaveSim allows researchers to cluster AI-generated algorithms into "families" based on their strategy. This provides a powerful way to interpret how an LLM is solving a problem, turning the "black box" of generated code into a navigable map of distinct problem-solving strategies.
Limitations and Future Work
While BehaveSim represents a major step forward, the authors note a few limitations:
- Iterative Scope: Currently, BehaveSim is designed for algorithms that progressively refine solutions. It may be less effective for "one-shot" algorithms that produce a result in a single, non-observable step.
- Computational Overhead: Measuring behavior requires executing the code, which is naturally slower than static analysis. The authors suggest using trajectory truncation or sampling to mitigate this cost.
- Future Dimensions: Future iterations could incorporate time and space complexity as additional dimensions of similarity, helping to distinguish between efficient and inefficient implementations of the exact same logic.
Summary updated