Complexity-based code embeddings

AI summary

Overview

Research area: machine learning for code intelligence, dynamic program analysis, and algorithmic classification. Technical level: Intermediate. This paper proposes a method for turning source code into numerical embeddings by profiling how programs behave on different inputs and fitting complexity functions to runtime metrics.

What This Paper Is About

The paper addresses algorithmic classification: given a code snippet, identify which programming techniques or algorithms it uses. Instead of analyzing code statically, the authors execute programs on multiple inputs, measure resource usage such as CPU cycles, instructions, branches, cache-related events, and page faults, and convert how those metrics scale with input size into numeric embeddings. These embeddings are then used with tree-based classifiers to label Codeforces programming solutions.

Key Contributions

1. A generic dynamic code embedding method based on r-Complexity, a revised complexity model that gives finer-grained feedback than classic Big-O notation.
2. A discretized fitting procedure that estimates Big r-Theta complexity classes for multiple runtime metrics, producing interpretable quadruples: feature type, feature configuration, intercept, and r-value.
3. An end-to-end data pipeline that crawls Codeforces solutions, compiles C++ programs, runs them against synthetic inputs, profiles them with Linux perf, and aggregates the results into code embeddings.
4. Empirical validation showing that simple tree-based models, especially XGBoost, achieve strong classification performance on multi-label algorithm classification without requiring assumptions about program structure.

Main Findings

• Dynamic complexity signatures are discriminative. Runtime metrics and their estimated complexity classes provide enough signal to distinguish between algorithmic techniques such as strings, implementation, greedy, brute force, dynamic programming, graphs, binary search, math, sortings, and shortest paths.
• XGBoost leads multi-label classification. The XGBoost model achieves an average F1-score of around 90% on an 11-class multi-label dataset built from real Codeforces submissions.
• Binary math/non-math classification is highly accurate. A decision tree classifier reaches 96% accuracy, while a random forest classifier reaches 97% accuracy on the math/non-math task.
• Tree ensembles outperform neural networks. Custom neural networks, deep neural networks, and convolutional networks were trained on the same data but performed worse than simple decision tree, random forest, and XGBoost classifiers.
• Embeddings are compact and metric-driven. Each program is represented as a 36-dimensional vector, built from nine profiling metrics, each summarized by four complexity-related parameters.
• Rare classes remain harder. Recall is lower for classes with few examples, such as divide and conquer, binary search, dynamic programming, and sortings, even when precision is high.
• Architecture affects raw metrics. The embeddings depend on the architecture used for profiling, though the general complexity class may remain stable across similar architectures.

Methodology in Plain English

The researchers run each program many times with different input sizes. While the program runs, they use the Linux perf profiler to record hardware and software events, such as branch misses, executed instructions, CPU cycles, context switches, page faults, and task-clock time. For each metric, they observe how the measured value grows as input size increases. They then try to match that growth pattern to a set of candidate complexity forms: logarithmic, log-logarithmic, polynomial, fractional power, exponential, and factorial. Each match gives a compact description of the metric’s complexity, including the type of curve, a configuration parameter, an intercept, and an r-value. Concatenating these descriptions across all metrics produces the final code embedding. Finally, standard machine learning classifiers are trained on these embeddings to predict algorithm labels.

Why This Matters

Impact on research: this work shows that dynamic profiling and complexity estimation can serve as an alternative or complement to static code embeddings, AST-based models, and graph neural networks. It also contributes a large profiling dataset and a reusable pipeline for studying runtime behavior at scale.

Real-world applications:

• Automated tagging and search of code repositories by algorithmic technique.
• Programming education tools that give feedback on what approach a student solution uses.
• Plagiarism and similarity detection based on runtime behavior rather than surface syntax.
• Performance analysis and optimization support by identifying complexity patterns in submitted code.

Industry relevance: the method is relevant to developer tooling, competitive programming platforms, code search engines, CI performance monitoring, and malware or vulnerability analysis where runtime behavior adds signal beyond static source inspection.

Future Directions

1. Expand synthetic input generation and the TheInputsCodeforces dataset to cover more problems and produce more representative evaluations.
2. Reduce architecture dependence by normalizing metrics or learning mappings between profiling results from different hardware.
3. Improve recall on rare algorithm classes through better class balancing, threshold tuning, or additional targeted metrics.
4. Combine dynamic complexity embeddings with static or graph-based code representations for richer hybrid models.
5. Scale the pipeline to more executors, more languages, and broader programming domains beyond competitive programming.

Target Audience

This paper benefits machine learning researchers working on code representation learning, software engineering researchers interested in program analysis and algorithmic classification, competitive programming and educational technology developers, and industry practitioners building code search, code tagging, or developer assistance tools.

Authors’ abstract

This paper presents a generic method for transforming the source code of various algorithms to numerical embeddings, by dynamically analysing the behaviour of computer programs against different inputs and by tailoring multiple generic complexity functions for the analysed metrics. The used algorithms embeddings are based on r-Complexity . Using the proposed code embeddings, we present an implementation of the XGBoost algorithm that achieves an average F1-score on a multi-label dataset with 11 classes, built using real-world code snippets submitted for programming competitions on the Codeforces platform.