Towards a Measure of Algorithm Similarity

• URL: http://arxiv.org/abs/2510.27063v1
• Date: Fri, 31 Oct 2025 00:20:54 GMT
• Title: Towards a Measure of Algorithm Similarity
• Abstract summary: Given two algorithms for the same problem, can we determine whether they are meaningfully different?<n>We introduce EMOC: An Evaluation-Memory-Operation-Complexity framework that embeds algorithm implementations into a feature space suitable for downstream tasks.<n>We compile PACD, a curated dataset of verified Python implementations across three problems, and show that EMOC features support clustering and classification of algorithm types, detection of near-duplicates, and quantification of diversity in LLM-generated programs.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Given two algorithms for the same problem, can we determine whether they are meaningfully different? In full generality, the question is uncomputable, and empirically it is muddied by competing notions of similarity. Yet, in many applications (such as clone detection or program synthesis) a pragmatic and consistent similarity metric is necessary. We review existing equivalence and similarity notions and introduce EMOC: An Evaluation-Memory-Operations-Complexity framework that embeds algorithm implementations into a feature space suitable for downstream tasks. We compile PACD, a curated dataset of verified Python implementations across three problems, and show that EMOC features support clustering and classification of algorithm types, detection of near-duplicates, and quantification of diversity in LLM-generated programs. Code, data, and utilities for computing EMOC embeddings are released to facilitate reproducibility and future work on algorithm similarity.

Related papers

• Early Discoveries of Algorithmist I: Promise of Provable Algorithm Synthesis at Scale [9.349595533902479]
  Algorithmist is an autonomous researcher agent on top of GitHub Copilot.<n>We evaluate it on research-level tasks in private data analysis and clustering.<n>Results suggest a new paradigm in which LLM systems generate research-paper-quality algorithmic artifacts tailored to each dataset and deployment setting.
  arXiv  Detail & Related papers  (2026-03-23T04:06:55Z)
• Rethinking Code Similarity for Automated Algorithm Design with LLMs [16.918736214353814]
  Large Language Model-based Automated Algorithm Design (LLM-AAD) has transformed algorithm development by autonomously generating code implementations of expert-level algorithms.<n>We propose BehaveSim, a novel method to measure algorithmic similarity through the lens of problem-solving behavior.<n>By quantifying the alignment between PSTrajs using dynamic time warping (DTW), BehaveSim distinguishes algorithms with divergent logic despite syntactic or output-level similarities.
  arXiv  Detail & Related papers  (2026-03-03T09:25:53Z)
• Memetic collaborative approaches for finding balanced incomplete block designs [0.0]
  The balanced incomplete block design (BIBD) problem is a difficult problem with a large number of symmetries. We propose a dual (integer) problem representation that serves as an alternative to the classical binary formulation of the problem.
  arXiv  Detail & Related papers  (2024-11-04T16:41:18Z)
• A Parametrizable Algorithm for Distributed Approximate Similarity Search with Arbitrary Distances [0.5030361857850012]
  We propose PDASC (Parametrizable Distributed Approximate Similarity Search with Clustering), a novel Approximate Nearest Neighbour search algorithm.<n>We show that PDASC is suitable for operating in distributed data environments and for handling datasets defined in different topologies.
  arXiv  Detail & Related papers  (2024-05-22T16:19:52Z)
• Multi-Dimensional Ability Diagnosis for Machine Learning Algorithms [88.93372675846123]
  We propose a task-agnostic evaluation framework Camilla for evaluating machine learning algorithms. We use cognitive diagnosis assumptions and neural networks to learn the complex interactions among algorithms, samples and the skills of each sample. In our experiments, Camilla outperforms state-of-the-art baselines on the metric reliability, rank consistency and rank stability.
  arXiv  Detail & Related papers  (2023-07-14T03:15:56Z)
• Provably Efficient Representation Learning with Tractable Planning in Low-Rank POMDP [81.00800920928621]
  We study representation learning in partially observable Markov Decision Processes (POMDPs) We first present an algorithm for decodable POMDPs that combines maximum likelihood estimation (MLE) and optimism in the face of uncertainty (OFU) We then show how to adapt this algorithm to also work in the broader class of $gamma$-observable POMDPs.
  arXiv  Detail & Related papers  (2023-06-21T16:04:03Z)
• Encoding of data sets and algorithms [0.0]
  In many high-impact applications, it is important to ensure the quality of output of a machine learning algorithm. We have initiated a mathematically rigorous theory to decide which models are close to each other in terms of certain metrics. A given threshold metric acting on this grid will express the nearness (or statistical distance) from each algorithm and data set of interest to any given application.
  arXiv  Detail & Related papers  (2023-03-02T05:29:27Z)
• An algorithm for clustering with confidence-based must-link and cannot-link constraints [0.0]
  We introduce the PCCC (Pairwise-Confidence-Constraints-Clustering) algorithm. The PCCC algorithm iteratively assigns objects to clusters while accounting for the information provided on the pairs of objects. Unlike existing algorithms, our algorithm scales to large-scale instances with up to 60,000 objects, 100 clusters, and millions of cannot-link constraints.
  arXiv  Detail & Related papers  (2022-12-29T19:21:33Z)
• Efficient Approximate Kernel Based Spike Sequence Classification [56.2938724367661]
  Machine learning models, such as SVM, require a definition of distance/similarity between pairs of sequences. Exact methods yield better classification performance, but they pose high computational costs. We propose a series of ways to improve the performance of the approximate kernel in order to enhance its predictive performance.
  arXiv  Detail & Related papers  (2022-09-11T22:44:19Z)
• Sublinear Time Approximation of Text Similarity Matrices [50.73398637380375]
  We introduce a generalization of the popular Nystr"om method to the indefinite setting. Our algorithm can be applied to any similarity matrix and runs in sublinear time in the size of the matrix. We show that our method, along with a simple variant of CUR decomposition, performs very well in approximating a variety of similarity matrices.
  arXiv  Detail & Related papers  (2021-12-17T17:04:34Z)
• Scalable Intervention Target Estimation in Linear Models [52.60799340056917]
  Current approaches to causal structure learning either work with known intervention targets or use hypothesis testing to discover the unknown intervention targets. This paper proposes a scalable and efficient algorithm that consistently identifies all intervention targets. The proposed algorithm can be used to also update a given observational Markov equivalence class into the interventional Markov equivalence class.
  arXiv  Detail & Related papers  (2021-11-15T03:16:56Z)
• Selection-Expansion: A Unifying Framework for Motion-Planning and Diversity Search Algorithms [69.87173070473717]
  We investigate the properties of two diversity search algorithms, the Novelty Search and the Goal Exploration Process algorithms. The relation to MP algorithms reveals that the smoothness, or lack of smoothness of the mapping between the policy parameter space and the outcome space plays a key role in the search efficiency.
  arXiv  Detail & Related papers  (2021-04-10T13:52:27Z)
• Identifying Co-Adaptation of Algorithmic and Implementational Innovations in Deep Reinforcement Learning: A Taxonomy and Case Study of Inference-based Algorithms [15.338931971492288]
  We focus on a series of inference-based actor-critic algorithms to decouple their algorithmic innovations and implementation decisions. We identify substantial performance drops whenever implementation details are mismatched for algorithmic choices. Results show which implementation details are co-adapted and co-evolved with algorithms.
  arXiv  Detail & Related papers  (2021-03-31T17:55:20Z)
• A Systematic Characterization of Sampling Algorithms for Open-ended Language Generation [71.31905141672529]
  We study the widely adopted ancestral sampling algorithms for auto-regressive language models. We identify three key properties that are shared among them: entropy reduction, order preservation, and slope preservation. We find that the set of sampling algorithms that satisfies these properties performs on par with the existing sampling algorithms.
  arXiv  Detail & Related papers  (2020-09-15T17:28:42Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.