Towards a Framework for Learning of Algorithms: The Case of Learned Comparison Sorts

Philipp Kunz, Ilche Georgievski, Marco AielloIJCAI 2024

Abstract

Traditional machine learning approaches often treat algorithms as black boxes, focusing on input-output mappings rather than the underlying procedural logic. This paper introduces a formal framework for learning the "how" of algorithms by representing them as computation graphs over homogeneous algebras. By transforming algorithm synthesis into a supervised classification task via transition algebras, we demonstrate that models can learn to mimic the execution traces of classical comparison sorts. Our findings reveal a significant correlation between an algorithm's structural complexity and its learnability, as well as varying degrees of robustness to data distribution shifts.

Introduction

While deep learning has revolutionized pattern recognition, the ability of neural models to "understand" and replicate algorithmic logic remains limited. Standard architectures like Recurrent Neural Networks (RNNs) or Neural Turing Machines (NTMs) are theoretically Turing-complete but often fail to generalize the underlying solution method. They typically learn to approximate a function rather than the discrete steps of an algorithm. This research addresses the challenge of extracting robust, reusable representations of classical algorithms from execution data.

The Proposed Framework

The core of our approach lies in two conceptual pillars:

1. Computation Graphs and Algebraic Abstraction

Instead of a monolithic memory tape, we model data structures (e.g., arrays, heaps) as "algebras" with predefined operations. An algorithm is represented as a computation graph where nodes correspond to these operations and edges represent decision logic or predicates. This abstraction provides the model with the "rules of the game," allowing it to focus on the logic of using the data structure rather than learning its fundamental properties from scratch.

2. Transition Algebra and Actuators

To facilitate learning, we define a "transition algebra" that maps complex graph traversals into a finite set of functions. This allows us to frame algorithm learning as a supervised classification task. The model predicts an actuator—a tuple containing the next transition function and the next data structure operation. This significantly reduces the state space and makes training more efficient compared to predicting the entire next system state.

Complexity and Learnability

A key insight of this work is the relationship between an algorithm's structural complexity and the difficulty of learning it. We utilize Cyclomatic Complexity (CC), a metric representing the number of linearly independent paths through a program's source code, to quantify this.

Table 1: Complexity metrics for various sorting algorithms, including Cyclomatic Complexity (CC).

As shown in Table 1, algorithms with higher CC values generally present more challenging learning targets. More complex branching logic often leads to lower sensitivity in the learned model, suggesting that structural simplicity is a precursor to robust algorithmic mimicry.

Experimental Results

We evaluated our framework using synthetic execution traces of four sorting algorithms: Insertion Sort, Heap Sort, Quick Sort, and Top-Down Merge Sort. Models were trained on datasets of up to 65,536 samples generated from normal distributions.

Accuracy and Distribution Sensitivity

While the models achieved high accuracy (often >95%) on the training distribution, they exhibited varying degrees of sensitivity to "out-of-distribution" (OOD) data. For instance, shifting the mean ($\mu$) or variance ($\sigma$) of the input values impacted performance.

Table 2: Error rates across different algorithms under distribution shifts.

Table 2 highlights these error rates ($E$). Notably, Quick Sort and Merge Sort demonstrated greater robustness to distribution shifts compared to Insertion and Heap Sort. This suggests that certain algorithmic structures are inherently more generalizable when learned through this framework.

Conclusion and Future Directions

This research demonstrates that by providing models with the right algebraic abstractions, we can move beyond black-box input-output mapping toward true algorithmic learning. However, several challenges remain. Achieving the 100% accuracy required for production-grade software is difficult, as even minor errors can lead to invalid results in large-scale sorting tasks. Future work will focus on learning the data structure operations themselves, improving explainability to infer human-readable code, and optimizing domain-specific algorithms based on observed user behavior patterns.

Summary updated

BibTeX
@inproceedings{kunz2024towards,
  author = {Philipp Kunz and Ilche Georgievski and Marco Aiello},
  title = {{Towards a Framework for Learning of Algorithms: The Case of Learned Comparison Sorts}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}
Figure