Understanding AI through the algorithms they compute

Midway through the 20th century, the study of computer algorithms took a major leap forward with the development of computability theory and models like Turing machines. Invented by Alan Turing to formalize what it means for a problem to be computable, Turing machines are simple abstract models of computation that use algorithms – step-by-step instructions used to solve a problem — to process information. An algorithm can be as simple as following a recipe to bake a cake, or as complex as Dijkstra’s algorithm, which finds the shortest path between nodes in a graph. These theoretical breakthroughs laid the groundwork for the systematic study of algorithms we see today.

These advances led to the birth of computational complexity theory; a subfield focused on quantifying the resources, such as time and memory, required to implement an algorithm. Computational complexity theory provided a foundation from which to study problems based on their inherent difficulty, introducing a structured way to classify problems into complexity classes. Scientists could then identify which problems are solvable with specific models of computation.

Yet, as we enter the modern era of AI with large language models (LLMs), a new paradox emerges: Modern AI models are undeniably powerful models of computation, but we currently lack a systematic theoretical framework to understand their computational complexity. Unlike traditional algorithms, whose behavior can be precisely analyzed within the well-defined hierarchies of computational complexity, AI models learn complex functions from unstructured data that are often challenging to characterize in formal and principled terms.

Algorithms as a window into AI capabilities

In a new publication in Nature Machine Intelligence today, we sourced inspiration from the foundations of theoretical computer science to bridge modern AI computation with the decades-old tradition of studying the complexity of algorithms. Studying what modern AI can compute through algorithms offers a clear, systematic way to assess their capabilities, including the correctness and efficiency of their problem-solving strategies.

A leading approach within computational complexity for formalizing algorithms as models of computation is by using circuits. In circuit complexity theory, algorithms are represented as computable circuit models, where a step-by-step algorithm is implemented by traversing that circuit. One common domain of computable circuit models is in computing arithmetic expressions. These expressions can be represented as a circuit (or a directed acyclic graph), where arithmetic operations are computed as one traverses through various operations, like summation and multiplication.

Importantly, algorithmic complexity can be explicitly quantified in these circuit models of computation by studying their structure, such as circuit depth — a concept devised by Charles Bennett at IBM Research. By incrementally testing AI models on their ability to compute circuit problems of varying complexity, we can probe and quantify the algorithmic limitations of AI systems.

In an era in which frontier AI models with emergent reasoning capabilities are abundant, it is ever more important to systematically understand the capabilities of these AI models. Recent work has illustrated that large reasoning models (LRMs), which produce step-by-step chains of thought prior to converging on an answer, have led to an overall improvement in benchmark studies. Despite this improvement in benchmark performance, the actual “reasoning steps” these models exhibit are at best challenging to verify, and often at worst, incorrect and non-sensical. Indeed, if LRMs produce correct answers to benchmark tasks through incorrect thought processes, this suggests a potentially dangerous illusion of their understanding that could mask serious flaws in their capabilities.

One solution is to evaluate the performance of these frontier AI systems on algorithms – problems of known complexity with verifiable outputs and intermediate steps. This would help clarify their computational abilities, while placing them on equal footing with other foundational models of computation that have helped to shape modern computing. Importing the tools and concepts from circuit complexity theory enables the systematic and algorithmic analysis of otherwise opaque modern AI systems. This approach would serve to not only demystify their internal reasoning, but also provide a rigorous framework for the benchmarks that guide future architectural innovations.

The convergence of theoretical computer science and cutting-edge AI yields a powerful intersection, where the tools of complexity theory offer a structured way to analyze and interpret AI systems through the precise language of algorithms. This growing synergy has the potential to not only deepen our understanding of current models, but also offers a principled foundation and blueprint for building more capable, efficient, and trustworthy AI systems in the future.