Search papers, labs, and topics across Lattice.
The paper introduces BehaveSim, a novel code similarity metric that assesses algorithmic similarity by comparing problem-solving trajectories (PSTrajs) extracted from code execution. BehaveSim uses dynamic time warping (DTW) to quantify the alignment between these PSTrajs, effectively capturing algorithmic logic beyond syntactic variations or output equivalence. Experiments demonstrate that integrating BehaveSim into LLM-AAD frameworks enhances behavioral diversity and improves performance on algorithm design tasks, while also enabling behavior-based clustering for algorithm analysis.
Current code similarity metrics miss the forest for the trees, but BehaveSim finally captures *algorithmic* similarity by comparing problem-solving trajectories, unlocking better LLM-based algorithm design and analysis.
The rise of Large Language Model-based Automated Algorithm Design (LLM-AAD) has transformed algorithm development by autonomously generating code implementations of expert-level algorithms. Unlike traditional expert-driven algorithm development, in the LLM-AAD paradigm, the main design principle behind an algorithm is often implicitly embedded in the generated code. Therefore, assessing algorithmic similarity directly from code, distinguishing genuine algorithmic innovation from mere syntactic variation, becomes essential. While various code similarity metrics exist, they fail to capture algorithmic similarity, as they focus on surface-level syntax or output equivalence rather than the underlying algorithmic logic. We propose BehaveSim, a novel method to measure algorithmic similarity through the lens of problem-solving behavior as a sequence of intermediate solutions produced during execution, dubbed as problem-solving trajectories (PSTrajs). By quantifying the alignment between PSTrajs using dynamic time warping (DTW), BehaveSim distinguishes algorithms with divergent logic despite syntactic or output-level similarities. We demonstrate its utility in two key applications: (i) Enhancing LLM-AAD: Integrating BehaveSim into existing LLM-AAD frameworks (e.g., FunSearch, EoH) promotes behavioral diversity, significantly improving performance on three AAD tasks. (ii) Algorithm analysis: BehaveSim clusters generated algorithms by behavior, enabling systematic analysis of problem-solving strategies--a crucial tool for the growing ecosystem of AI-generated algorithms. Data and code of this work are open-sourced at https://github.com/RayZhhh/behavesim.
