用执行轨迹判断代码相似性,区分真创新与表面变化。
Rethinking Code Similarity for Automated Algorithm Design with LLMs
- 通过程序执行中的中间解序列衡量算法行为相似性
- 在三个自动算法设计任务中显著提升性能
- 适合研究AI生成算法逻辑差异的学者
基于大语言模型的自动算法设计(LLM-AAD)已能自主生成专家级算法代码,但其核心设计思想常隐含于代码中。现有代码相似性度量多关注语法或输出结果,难以捕捉底层算法逻辑差异。本文提出BehaveSim,从问题求解行为角度出发,将执行过程中的中间解序列视为问题求解轨迹(PSTrajs),利用动态时间规整(DTW)量化轨迹对齐程度,从而区分逻辑迥异但语法或输出相似的算法。实验表明,将BehaveSim集成至FunSearch、EoH等框架可显著提升行为多样性,改善三个AAD任务表现;同时支持对生成算法按行为聚类,便于系统分析求解策略。数据与代码已在https://github.com/RayZhhh/behavesim开放。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品;中文卡片由大模型生成,请以原文为准。