SuperARC: a test for artificial superintelligence based on compressed modelling, recursive prediction and problem complexity

Assessing the capabilities of frontier LLM models

Since the inception of LLMs, these systems have been associated with human intellectual capabilities related to language that range from mastering composition to retrieving contextual data and even generating novel ‘ideas’52. However, beyond seemingly arbitrary intelligence tests, questions related to intelligence remain, because intelligence is traditionally not well defined, with the intelligence tests performed remaining rather arbitrary or human-centric and lacking a clear linear progression of difficulty levels. Here, we approach both as a single problem and within a quantifiable framework, providing a formal approach to a form of intelligence based on algorithmic information.

While, in principle, LLMs have been shown to be theoretically capable of Turing-complete computation53,54, this is achieved when they are augmented with external memory and appropriate decoding mechanisms54. In practice, the models we evaluate operate with standard autoregressive decoding and finite context windows, which do not constitute Turing-complete systems.

Some have claimed that LLMs, and specifically ChatGPT, have the potential to revolutionise technological interaction through accurate understanding across conversational interfaces55. These attributions and capabilities of LLMs have been tested in a variety of ways, from semantic comprehension evaluations in traditional Chinese medicine (TCM), through structured multiple choice and true/false questions56, ASCII art57, to answering open questions and using LLMs as judges of the precision and correctness of the answers provided by other models58. Exhaustive and detailed tests have been performed that focus on tasks that require a grasp of a broad context, such as quantitative investing and medical diagnoses59, to mention only two.

Researchers have called into question these supposed understanding capacities, claiming that a lack of novelty and an abundance of hallucinations is formal and/or informal proof of a lack of comprehension ability60,61. When evaluating the intelligence and comprehension capacities of LLMs, some limitations of existing works should be highlighted:

1.

All of them contain an element of subjectivity. Measurements of understanding rely on a human or LLM judge, where a type of definition of innovation, usability, and correctness is used, which could be human-centric or dependent on the context.

2.

All evaluations use (mostly) text to provide a context for the questions formulated; hence, there are no questions that purely test understanding beyond textual correlations.

3.

The test used may take for granted that, since LLMs are trained with intelligent sources of information, this confers some intelligence on the models themselves and thus their comprehension/understanding capacities.

4.

LLMs and other AI systems are not self-driven and, as such, cannot be reasoning agents on their own; they only act upon being triggered and prompted by humans, otherwise they do not possess any internal states (e.g., activity when not prompted).

Other researchers, following a more abstract and formal approach, incline to the view that a test of intelligence in LLMs, which could imply comprehension, understanding, and prediction, might rely on exposing and training LLMs on highly complex datasets, and testing how well the LLMs could apply learned knowledge to unrelated but complex tasks (like predicting the next chess move) and reasoning tasks. They claim that information at the ‘edge of chaos’, a state between non-chaotic and chaotic behaviour in dynamical systems, is more likely to help LLMs manifest intelligence62. Suspicions that current AI is mimicking intelligence rather than displaying it have been reported and substantiated before61,63,64. Thus, proposing a test that can address those concerns is very relevant.

Compression as comprehension about (and as part of) the world

The formal equivalence between prediction and compression in the Sup Inf using martingales provides a theoretical foundation for understanding intelligence in terms of the generalisation of computational capabilities (due to universality and invariance).

In the context of designing a test for intelligence, such an equivalence suggests that an agent’s ability to abstract (e.g., through feature selection and model compression) and to plan (e.g., through prediction, counterfactual analysis, and simulations) are fundamentally interconnected aspects of intelligence involved in scientific or mathematical creativity. More specifically:

recursive/computable compression and decompression: seen as the summarisation or abstraction of main features (or feature selection) that can be simulated in reverse (decompression), and in contrast to simple statistical pattern-matching or statistical compression;

process (algorithmic or symbolic) regression and prediction: formally established by AIT as equivalent to compression by way of optimal/universal simulation65,66,67 through the concept of algorithmic randomness and martingales (betting strategies)68,69,70 (see Sup Inf); or universal (Solomonoff) induction8,9,20 (see also pseudocode 1).

An agent that can devise or find a model that can compress a set of phenomena that, when uncompressed, generates this set faithfully (and beyond statistical compression) is necessarily able to comprehend it at some level6. That is, a set of phenomena that is compressible by an agent into some first principles, or into a succinct model that when uncompressed, reconstructs, describes, and can also simulate future states of the originally described set of phenomena, needs to be comprehensible by that agent6; otherwise, we would have an agent that does not comprehend the phenomena at the same time that can devise formal theories that can explain them into (fewer) first principles and (better) predict future events, which seems to go against a common-sense understanding of ‘comprehension’: on the one hand, this necessarily indicates at least some type of comprehension, e.g., a scientific or mathematical one; on the other hand, an agent that can only mimic, copy-paste, describe, or depict the phenomena at the same time that comprehending them contradicts any conception of ‘an agent able to understand something at a deeper level beyond mere appearance’. From both scenarios, we find that abstraction and prediction arise as necessary conditions for comprehension, particularly those intrinsic to the process of devising novel scientific or mathematical theories. As introduced in Section 1, instead of covering all the sufficient conditions for all types of human intelligence (including those for which compression may seem unrelated), here we constrain our study to this type of comprehension—crucial to scientific knowledge and mathematical creativity. In this regard, compression necessarily plays a defining, encompassing role that is mathematically grounded and empirically feasible, as we explain in the paragraphs below.

It is important to clarify possible misinterpretations of the meaning of the word “compression” used in our framework. In machine learning and cognitive science, feature selection involves identifying the most relevant variables or attributes that contribute to predictive modelling. This summarisation process reduces the dimensionality71, focusing on the most informative aspects of the data. It is, of course, a compression approach, but just a part of the one we intend to refer to. In our framework, beyond finding crucial features, attributes, or aspects, (algorithmic) compression into a model refers to other “mechanistic” relationships that are less descriptive in nature, while also guaranteeing that a model does not compromise performance. It involves reducing the complexity of the model, but often leads to a more effective generalisation and greater efficiency72. Model abstraction through effective recursive/algorithmic compression allows simulation of various scenarios when the model captures its main features, that is, its most important patterns for prediction are captured as a necessary condition for outcome prediction. Then, model selection happens when each outcome is compared against each time-step observation, hence updating the belief model, instantiating, and enabling ‘planning’.

‘Compression as comprehension’ is thus also tied to pragmatic characteristics such as its utility and feasibility. For example, a compressed model in the form of a mathematical theory or a set of equations, such as a set of laws of physics, is only sound if it allows one to predict the future state of a physical system in “a shorter time than the time taken by the actual unfolding of the phenomenon”6. Comprehension only takes place if one can understand real-world phenomena to computationally “outrun” reality at some sufficiently higher level—see also computational irreducibility in ref. 73.

Such a process of understanding or comprehension into formal-theoretical or computational capabilities is demonstrated in the context of the scientific discovery itself. Real-world phenomena that have the appearance of being random or unexpected become a topic of interest for research, analysis, and future development (if successful) of a more comprehensive model or theory that is then able to compress the apparent noise-like phenomena by allowing one to explain these and to predict other unfoldings from it. In this way, science moves in an iterative pace of converting something that is currently considered “irreducibly complex” or unexpected into something that becomes comprehensible by theoretical means that allows computational predictions6. For example, consider Newtonian mechanics and general relativity in physics. The former has represented a highly successful compression of observational data, e.g., celestial motion. However, to account for anomalies like the precession of Mercury’s orbit, “requires a stream of regular adjustments” or corrective patches, which basically increase the complexity of the explanations of those anomalies to a level similar to that of describing the anomalies themselves. General relativity then provided a superior, more compact, and elegant set of field equations that not only subsumes the previous phenomena that Newtonian mechanics successfully accounted for, but also explains these and other “anomalies” in a more compressed form than before. In fact, the continued success of the scientific method in more compact and elegant mathematical theories corroborates the conclusion that comprehension necessarily involves compression of natural phenomena6.

We know from AIT that once one can sufficiently approach universally optimal compression (i.e. approximate the actual values of algorithmic complexity), any necessary increase in complexity (of the phenomena already explained along with those to be explained) is proved to require a novel theory that is (entirely or at least a proper part of it) irreducible to the old one, like when one needs to find a new axiom. From the algorithmic coding theorem (ACT)10,11, the minimisation of such an irreducibly larger quantity of complexity also corresponds to the best inference method (such as the case when one employs abductive reasoning) for the new theory (or e.g., the new axiom) one can devise from a yet unexplainable phenomenon. As discussed in the Supplementary Information, we argue that these two features are central to tackling the problem of AGI and ASI.

The invariant and universal properties of algorithmic information imply that compression is more than a complexity index that might be correlated to abstraction and prediction. In fact, optimal compression is only achieved by the best formal-theoretic methods proven across the whole landscape of algorithms and methods one may attempt to apply, regardless of the type of agent applying them. Optimal compression is one such task that subsumes any other task—formalisable into an algorithm or a mathematical method that can be computationally implemented—an agent may perform in order to create a new theory that predicts new phenomena. Unlike directly equating compression/prediction to intelligence74 or straightforwardly applying the ACT like in other universal induction-based methods, we propose that compression is a necessary and fundamental condition for comprehension if it is achieved through (and as a product of) the interaction between the AI agents being evaluated, the evaluator agents (including the methods, frameworks and metrics we formalise), and the external real world whose process may affect and be affected by the other two entities. For example, notice that this implies that the ACT itself becomes a constituting knowledge that the evaluator agents may devise by formalising a new mathematical theory, obtaining such a formal-theoretic knowledge after the experience (i.e., after the interactions take place). As explained in the Sup Inf, this is a distinctive characteristic of Algorithmic Information Dynamics (AID)27,28,29,75 upon which our proposed framework is based.

As presented before in refs. 6,76, the remarkable features of AIT77,78 discussed in the present section seem to underpin the apparently unreasonable effectiveness of algorithmic complexity79 and computation73 in explaining the natural world, including cognition, and in advancing science as the practice of finding or synthesising models that can explain and predict natural phenomena and the world. Thus, by putting forward a formal and more objective approach to measuring general intelligence, we propose in the section “SuperARC testing framework” a test for ASI and AGI based on AID and AIT, namely SuperARC, that specifically tests recently strongly associated features with intelligence in the context of discussions of AGI30,31,32,80,81,82,83,84,85. While human intelligence includes many other abilities to perform a myriad of tasks, here we chose to focus on abstraction, explanation, and prediction related to building new formal theories and to scientific creativity. Those are the ones for which we have computational methods and a solid theoretical foundation that has proved the universal and agnostic properties that a testing framework for general intelligence should aim at, particularly if one wants to tackle the distinction between narrow AI and AGI (see Supplementary Information).

SuperARC testing framework

Based on the theoretical background presented in the Supplementary Information, we ground our framework on the following aspects:

intelligence necessarily involves the ability to create (i.e., through abduction from the experience) or enact (i.e., through prediction from future interactions) a computational generative model that effectively explains any given data while losing the least amount of information as possible;

and greater intelligence corresponds to performing prediction and abduction as close to the optimal solution as possible while maximising the compression of the generative model.

As a metric for (general or super-)intelligence, designing tests that measure these abilities can lead to a more nuanced and computationally grounded understanding of intelligence that is applicable to biological (e.g., animal), human cognition, and computational intelligence. This can establish a universal approach to measuring the capabilities of intelligent systems, serving as both a theoretical and a practical upper bound for the highest possible levels of compression, such as model abstraction and prediction, which are believed to be fundamental features of intelligence.

As discussed and elaborated in the Supplementary Information, using algorithmic complexity as a measure of model compactness (i.e., compression, conciseness or summarisation) and optimal prediction provides an agnostic quantitative metric, as its value corresponds to the shortest possible programme capable of correctly reproducing (via decompression) a given dataset, and its optimal prediction value is governed by algorithmic probability. First, unlike standard tests that assess intelligence based on predefined ‘correct’ answers—inevitably influenced by subjective notions of correctness—we shift the focus to identifying the shortest possible explanation for a given dataset, an explanation that is proven to be sufficient for predicting not only the given dataset but also future outcomes. In this context, correctness is understood purely as the ability to reproduce exactly the same original data (i.e., losslessly). Secondly, an agnostic method aims to achieve measurable quantities as independent of human biases as possible, including those high-order biases in the scientific practice, such as when one chooses to employ one formal theory instead of another in order to model certain phenomena (see the section “Compression as comprehension about (and as part of) the world”).

Beyond a measure of a single-purpose compression task (as discussed and unpacked in the Sup Inf), the SuperARC test is a proposal to capture the potential future trajectories leading to hybrid neurosymbolic systems more capable of the abstraction and planning, deemed central to what has been conceived of AGI and ASI18,31,32, one that may take into account statistical pattern matching, but favours symbolic regression and programme synthesis as a test of intelligence based on optimal inference rather than statistical ‘reasoning’. The test proposed expands current efforts to characterise AGI, such as the abstraction and reasoning corpus (ARC) challenge30, which have been suspected to be ‘hackable’ from test result leaks because the test data set is fixed (even if part of it is concealed but prone to be leaked). Unlike recent results in the ARC-AGI test, our results find a similar lower performance than that reported in a recent mathematical benchmark test86, with the advantage that our proposed test does not require the selection of human mathematical problems, and the test problems can be dynamically generated with test elements introduced cheaply and efficiently. Although this new test may require the selection of objects and elements such as sequences, unlike the original ARC challenge tests, this selection can be based mainly on quantitative measures of complexity and less on human selection.

These features are crucial in avoiding biases introduced by the datasets, such as benchmark contamination, when evaluating the performance of an AI algorithm. Given that one would be trying to measure the ability of the learning algorithm to predict phenomena whose type or class was not the one of the data it was trained for in the first place, this is especially the case in zero-shot learning scenarios, where any small leakage of data with information about the (upcoming and irreducibly new) test to be performed makes a big difference in the score. Due to the mathematical properties in AIT discussed in the Supplementary Information, SuperARC avoids human-centric and other cognitive biases because lower (algorithmic) complexity (higher compression, or equivalently, higher algorithmic probability) of a model is proven to indicate better overall prediction capabilities, regardless of the nature of the new phenomena or the type of data on which one is trying to measure the generalisation capabilities of the AI algorithm. For example, even if one can update the benchmark test in practice with a new type of task to be performed, this possibility itself assumes that a new type of task might be known to us, rendering the test inherently prone to contamination. Following from the properties of algorithmic probability, SuperARC quantifies prediction in new contexts and potentially different scenarios without the need for a new type of task, distinct data, or posterior apprehension of previously unknown phenomena.

The role of SuperARC in distinguishing algorithmic from statistical prediction

While prediction is fundamental to both human-centric and algorithmic benchmarks, the nature of what is being predicted differs fundamentally. Human-centric benchmarks evaluate whether models can predict outputs that humans would generate given specific inputs, which is a task solvable through statistical pattern matching over human-generated corpora. This is because, as models are increasingly trained on datasets that cover more of human knowledge, performance on these benchmarks asymptotically approaches data memorisation rather than genuine understanding.

SuperARC, by contrast, evaluates whether models can induce the algorithmic structure that underlie the sequences, i.e., that can find the minimal programme that generates the observed data. This capability is irreducible to pattern matching because:

Infinite hypothesis space: Unlike human-centric tasks with finite answer sets, algorithmic induction in principle searches over an infinite space of possible programmes, and thus possible formal theories;

Distribution shift immunity: Novel algorithmic patterns (new combinations of primitives) are fundamentally out-of-distribution, requiring genuine abductive reasoning, such as when one devises a new axiom;

Compression-prediction duality: The theorem proven in Sup Inf establishes that the success of predictions is equivalent to compression over the algorithmic space, which subsumes the statistical space, although the equivalence does not require statistical evaluation or success.

As shown by our results, we argue that such a theoretical difference uncovers a practical consequence: models can simultaneously improve on human benchmarks while regressing on algorithmic reasoning. This divergence should be impossible if both algorithmic prediction and statistical prediction were supposed to measure the same underlying predictive capability, and therefore SuperARC provides empirical evidence that captures a distinct and arguably more fundamental aspect of intelligence.

CTM and BDM: A neurosymbolic approach to Superintelligence benchmarking

The SuperARC framework accommodates any type of data as input-output pairs, requiring only a complexity-based metric to be predefined. To achieve this, in addition to approximate methods to algorithmic complexity, such as LZW and ZIP, which are more closely related to Shannon Entropy51, we use the Block Decomposition Method (BDM) as our gold-standard approach to algorithmic compression that goes beyond statistical compression or statistical pattern-matching35. Using the principles of both classical and algorithmic information theories, BDM combines the calculation of the global Shannon Entropy rate of the object with local estimations of the algorithmic complexity of smaller blocks into which the object is decomposed, for which values are found in a pre-computed database of direct approximations of algorithmic probability. By combining both statistical and algorithmic inference methods, one way to think of BDM is by depicting it as a Deep Learning Transformer, which aims to build a predictor that maximises the probability of being correct in explaining the data by looking for long-range and short-range correlations. The difference, in this case, is that long-range correlations are covered by Shannon Entropy (not fundamentally different from Transformers), but short-term correlations are estimated using the principles of algorithmic probability through the ACT29,33,34,87 (see Supplementary Information). See the discussion on the limitations of BDM below. In this manner, BDM is based on combining the best capabilities of Shannon entropy-type metrics to find patterns (e.g., block entropy rate88) with universal (Solomonoff) induction-based approaches (such as the minimum description length21) through algorithmic complexity, and thus deals with uncertainty in an optimal Bayesian fashion based on the principles of algorithmic probability20. BDM improves upon Shannon entropy and LZW compression, which are limited to detecting only statistical regularities, that is, pure pattern-matching approaches. In fact, BDM subsumes these methods, and therefore one can only do better in capturing structure than statistical compression algorithms, as BDM detects both regular statistical patterns and recursive ones with causal generative signatures35,51,88 (see also Supplementary Information). By recursive, we mean exactly those that are not statistical in nature (e.g., the digits of the mathematical constant π do not display any statistical patterns, but it is recursive).

The BDM relies on the following assumptions:

1.

In the case of small enough objects, their algorithmic complexity can be approximated using an exhaustive search (sometimes guided, e.g., with AID).

2.

For larger objects, breaking them into smaller parts allows for the approximation of the overall complexity by summing the complexity of individual blocks, with a correction factor to account for interactions between the blocks.

3.

For every other length, values of Shannon entropy rates are calculated and combined with the previous values by using the same principles of information theory.

Formally, let x be a string divided into blocks xi, with x = x1 ⊕ x2 ⊕ ⋯ ⊕ xn, where ⊕ denotes a concatenation operator. The BDM complexity of a string x, denoted by BDM(x), is given by

$$\,{{{\rm{BDM}}}}(x)={\sum }_{i=1}^{n}{{{\rm{CTM}}}}\,({x}_{i})+\log {m}_{i}$$

(9)

where:

CTM(xi) is the algorithmic complexity approximation for block xi, derived from the coding theorem method (CTM).

\(\log {m}_{i}\) is a correction factor accounting for the multiplicity mi of how many times the block xi appears.

For a generalised version of BDM holding for any encodable object (see ref. 88).

The coding theorem method (CTM) is a method based on the ACT12,28 and Supplementary Information, which connects probability to complexity, randomness, and prediction29,33,34,87; and the ACT underlies the universal induction-based methods applied to Artificial Intelligence. CTM works by searching for all the formal-theoretic explanations (models or programmes) for an object that are shorter than the object itself35, in order to calculate the ratio of those explanations of a particular object with all the explanations found for any object. From the value obtained for each of these ratios, one can approximate the algorithmic probability of an object, and thereby its algorithmic complexity via the ACT, so that a list of these pre-computed probability values is built, which in turn can be used to approximate the universal distribution34.

On the one hand, CTM provides an approximation to algorithmic probabilityP(s) by connecting the empirical frequency of occurrence of an object produced by a random computer programme with its algorithmic complexityK(s) and also keeps track of the set of programmes that generated the original object (see Supplementary Information). On the other hand, BDM offers a method to map the micro-programmes produced by CTM to their corresponding pieces from the larger object, to explain by decomposing the original object into smaller blocks for which micro-programmes have been found by CTM with a correction factor for block interactions (e.g., repetitions). While CTM operates by brute force and thus is only effective for small programmes/models, BDM leverages the pre-computed distributions that can be queried in linear time and stitches together longer explanations from small computer programmes according to the rules of information theory to guide the search for the best sequence of programmes explaining larger objects, thereby constituting a method that approximates the optimal causal explanation of the objects. BDM also allows massive parallelisation because objects with low complexity (i.e., higher causal impact at the global level) are the most frequent according to algorithmic probability and therefore are exponentially more frequent, counteracting their intractability35.

With limited computational resources, because of the limitations from the CTM, BDM behaves exactly like algorithmic complexity at the local scale and exactly like entropy at global scales35,51,88. In principle, with unbounded computational resources, all the algorithmic generative models at any scale would be known/computed. As a consequence, BDM would return the optimal value given by algorithmic complexity, and therefore would achieve optimal compression in the general case. In addition, for the particular cases in which the conditions for optimal statistical compression (like those discussed in the Sup Inf) are met, BDM is also proved to perform as optimally as entropy does because, at the local scales, algorithmic complexity already encompasses and subsumes entropy, and at the global scale, BDM converges to entropy via the CTM. Therefore:

in practice, BDM always performs equally or better than entropy;

BDM through CTM converges to algorithmic complexity in the limit, outperforming any statistical compression method;

both in principle and in practice, BDM remains sensitive to underlying structures even for objects with maximal Shannon entropy.

Following from the fundamental properties of AIT (discussed in the Supplementary Information), such as universality, invariance, maximality, and optimal prediction, BDM offers a ‘principled’ alternative in comparison to statistical measures. It is currently the only viable and computable approximation to algorithmic complexity grounded in AIT beyond statistical compression algorithms.

Thus, BDM is a hybrid neurosymbolic89 method that combines statistical machine learning and symbolic regression, and prediction that can be applied to inverse problems in causality25,26. BDM can be thought of as a quintessential type of neural network transformer (as in self-attention), where it estimates the local (short-range) causality through algorithmic complexity while computing long-range correlations through Shannon entropy guaranteed convergence (worst case)88. Such a benchmarking method has already been reported in applications to data summarisation71 and in various fields ranging from cell and molecular biology to genetics25,90 to biosignatures50,91,92.

BDM is an approximation to algorithmic complexity and probability, with its known limitations that demand explicit discussion. BDM’s complexity estimates depend on choices of block size for decomposition, with different block sizes potentially yielding different rankings of sequence complexity. As mentioned above, this limitation occurs because of limited computational resources, since in the asymptotic theoretical limit, the algorithmic complexity could be approximated across any coarse-graining scale. For the short range or smaller blocks, BDM uses a precomputed table of short programmes (or equivalently, Turing machines with a few limited number of states) for which the Busy Beaver values are known, and therefore one can solve the halting problem. In the long range or for the largest block sizes possible, BDM upscales those actual algorithmic complexity values via Shannon (block) entropy. Therefore, due to limited computational resources, the resulting BDM value may inherit the same limitations of entropy in the long-range scenario. In addition, the empirical application of the method’s reliance on decomposing sequences into overlapping or non-overlapping blocks means that patterns spanning boundaries between blocks may not be captured optimally, potentially underestimating complexity for sequences with long-range dependencies. These are fundamental characteristics of practical computable approximations to algorithmic complexity or algorithmic probability, which remain uncomputable in the general case.

Despite these limitations, our use of BDM is justified for reasons that directly address concerns about result interpretation: first, the models we evaluate fail predominantly on short sequences where BDM’s approximation is most accurate and where the gap between estimated and actual algorithmic complexity values is minimal; secondly, our conclusions do not depend on fine-grained complexity distinctions but on coarse patterns (models fail across broad complexity ranges rather than at specific threshold values where approximation errors might matter); thirdly, our neurosymbolic baseline employs actual programme synthesis through systematic enumeration rather than BDM estimation, yet reaches qualitatively similar conclusions. While future work comparing alternative complexity metrics may uncover or highlight other aspects or discrepancies, we argue that the robustness of LLM failures across these multiple lines of evidence suggests our core findings about inadequate algorithmic reasoning in current models remain sound regardless of specific approximation method choices.

Applicability of CTM and BDM to abstraction and planning in machine learning

BDM with CTM can be applied both as a reference and as a direct generative model. This is because it provides a fundamental complexity-based value estimation that can guide and evaluate other predictive and learning approaches, but also serves as a stand-alone predictive system.

CTM helps identify the set of candidate underlying generative mechanisms and provides a set of models from which it can actively predict future values by running it further into the future providing a set of projections. CTM forecasting requires an iterative refinement process in which multiple possible generative programmes are tested and updated. CTM can help select the most likely programme candidates by favouring those with lower complexity in accordance with the principles of algorithmic probability.

In a predictive task, multiple candidate programmes generated by CTM are evaluated against new observations, discarding those that are not consistent with the new data while retaining the set of shortest valid programmes that do. Planning requires CTM as the algorithmic mechanism to iteratively refine predictions from projections. CTM serves as a criterion for model selection—helping identify which approach best maintains parsimony and explanatory power—rather than functioning as a decision-making agent of its own.

BDM then stitches multiple programmes that can explain longer pieces of data and larger objects by using the rules of classical information theory, serving as a reference point to compare different models based on how well they align with the inherent complexity of the data. By breaking down an object into smaller pieces and estimating their individual algorithmic complexity using CTM, BDM provides a tighter recursive upper bound to traditional pattern matching. BDM leverages, therefore, both algorithmic and classical information theory as a proxy for deeper connections to causality, allowing it to indicate how predictable a time series or integer sequence is. Both CTM and BDM combined can benchmark different models on the basis of how efficiently they approximate the set of the best explanatory and generating mechanisms.

The way BDM approaches uncertainty is to update the belief at time t of an object s (e.g., an integer sequence), and choose a (small) programme \({p}^{{\prime} }\) to explain for the next digit i ∈ si−1 deviating from the previous hypothesis p; or in case we do not have (or we cannot obtain) such a programme for this observation, we combine smaller programmes p″ to explain observation of digit i ∈ si at index t + 1. In this manner, the ability of BDM to capture both local and global patterns in a time series or integer sequence makes it a powerful tool for approximating complexity and enabling prediction, aligning with the principles of algorithmic probability and Levin’s universal distribution.

BDM shows some fundamental similarities but in pure form to “Attention is All You Need” algorithms and LLM’s by assigning different weights to different parts of an object focusing both on short-range and long-range correlations where the short-range is recursively correlated hence based on causally generated models for that patch of data unlike LLMs and other ML approaches that rely only on Shannon-entropy-based correlations or basic pattern-matching that BDM only uses for its long-range correlations. BDM is therefore a proper generalisation of the short- and long-range capabilities that gave LLMs their particular advantage in language35. Together with CTM as a universal generator33, the CTM/BDM combination represents a model of models of languages, where languages are all computer languages, and a superset of LLMs themselves.

As mentioned above, a limitation of CTM is that running CTM to approximate model compression and achieve optimal prediction is computationally very expensive. If there were infinite resources, CTM would perform perfect recursive compression and provide the most optimal answer to any computable question given an observation. However, even with access to infinite resources, there are no theoretical or practical guarantees of LLM convergence to any optimal answer. In practice, LLMs are currently more expensive in applications where approaches like CTM could deliver better results (such as for this benchmark, empirically proven to better characterise questions and predict answers encoded in the form of binary sequences) without spending billions of USD in training giant neural systems like LLMs. However, our point is that one does not need to pick one over the other, as they can be combined to provide the best approximation to both an optimal and efficient path to an answer under time and resource restrictions. In this regard, CTM/BDM is a resource-bounded approximation to optimal inference that combines pure forms of each side (neuro-based on classical statistics, and symbolic-based on optimal theory). The CTM/BDM combo represents the purest form of neurosymbolic computation with no extra steps.

In the framework we propose, CTM and BDM are used as a benchmark to evaluate model performance and as a representative of a Universal AI9 method capable of ASI8. They can be applied to test both:

compression as model abstraction: The BDM can approximate the algorithmic complexity of a time series by decomposing it into smaller subsequences (blocks), computing the complexity of each block using CTM, and summing up the block results. This serves as a measure of the recursivity of the time series, but also serves as a method to find generating mechanisms (a set of algorithms that produce each past and possible future element/token of an object, in particular, a time series).

prediction as planning: Using the BDM complexity as a proxy for the time series’ regularity, one can infer the predictability of future values. Lower BDM complexity implies a simpler underlying structure, which can help in forecasting future elements of the series—which is similar to how algorithmic probability and universal distribution can be used for predictive modelling. (See Sup Inf). This is related to planning, because once several programme pathways are identified, one can verify each against the next token and update the programme set (by discarding those programmes that did not fit the next token) while keeping the shortest programme criterion.

A method for measuring comprehension via algorithmic probability

BDM is a divide-and-conquer method that extends the power of a CTM that approximates local estimations of algorithmic complexity via the theory of algorithmic probability, a foundational result established in AIT (see Supplementary Information). The method consists of finding the sequence of computer programmes that can generate the original piece of data—each programme represents a hypothesis or model for the time series and a sequence of datasets that can be interpreted as time series, binary and non-binary—providing a closer connection to complexity (or irreducible information content) than previous attempts based on statistical regularities such as popular lossless compression schemes35.

Based on AIT, we measure comprehension of LLMs (see the section “Compression as comprehension about (and as part of) the world”) with a test designed to assess the model’s ability to generate code or mathematical models/formulae that compress sequences of increasing complexity. Non-binary sequences are categorised into three levels of complexity (Low, Medium, and High) representing datasets that exhibit simple, intricate, and random patterns, respectively. Binary sequences, on the other hand, are classified as either random or what we call ‘climber strings, low-complexity strings as defined in the following section. Thus, a pragmatic compression-as-comprehension test is designed and applied to various LLM models and versions, encompassing test elements of diverse complexity classes that can be understood and compared individually and collectively.

Algorithm 1

Pseudo-code for SuperARC framework

Require

1:  • Dlow, Dmedium, Dhigh (datasets of any type with low, medium, and high complexities with sizes given as \(\left|\cdot \right|\). These are needed to ensure complexity diversity, but the choice of three groups is arbitrary and can be changed by the user.);

  • enc (encoding chosen to put the datasets in a common format);

  • \({{{\mathcal{M}}}}\) (complexity metric used to qualify the datasets and quantify the complexities of the models created by LLMs);

  • \({{{\mathcal{T}}}}\)(test formula to evaluate a candidate model).

2: \({c}_{{{{\mathcal{M}}}}}\Leftarrow\) an array containing binary values.

3: \(Au{x}_{{{{\mathcal{M}}}}}\Leftarrow\) an array containing auxiliary values.

4: \(Al{l}_{{{{\mathcal{M}}}}}\Leftarrow\) an array containing complexity values.

5: for k ∈ {low, medium, high} do

6:  Dk,encoded ⇐ encoding of Dk using enc (the UTF-8 or ASCII binary representation of strings or a binary representation of integers, for example).

7:  for j ∈ {1, 2, . . . , ∣Dk,encoded∣} do

8:   Rk,j ⇐ the response obtained from prompting a LLM model to write a programme to reproduce the jth element of Dk,encoded.

9:  ck,j ⇐ a binary variable indicating if the output obtained after running Rk,j is correct (equal to the input dataset) or not.

10:  \({{{\mathcal{M}}}}({R}_{k,j})\Leftarrow\) the complexity of Rk,j according to \({{{\mathcal{M}}}}\).

11:  ak,j ⇐ a vector with real-valued variables representing the result of applying auxiliary functions to Rk,j.

12:   Append ck,j to \({c}_{{{{\mathcal{M}}}}}\).

13:   Append \({{{\mathcal{M}}}}({R}_{k,j})\) to \(Al{l}_{{{{\mathcal{M}}}}}\).

14:   Append ak,j to \(Au{x}_{{{{\mathcal{M}}}}}\).

15:  end for

16: end for

17: \({{{\mathcal{T}}}}({c}_{{{{\mathcal{M}}}}},Al{l}_{{{{\mathcal{M}}}}},Au{x}_{{{{\mathcal{M}}}}})\Leftarrow\) the test score for the candidate model.

In other words, the SuperARC framework assesses how the LLM model is able to generate an algorithm \({{{\mathcal{A}}}}\) such that, when applied to the input data set τ, it is able to compress this input by learning its features and producing a compressed representation ∂. Then, by inverting such an algorithm and obtaining the algorithm \({{{{\mathcal{A}}}}}^{-1}\), the inputs τ are obtained losslessly with minimal complexity of the combined algorithms according to a complexity metric \({{{\mathcal{M}}}}\). From AIT, we have that universal induction indicates the best way to predict future elements of a sequence as favouring the simplest (i.e., the least complex) hypothesis or explanation—which aligns with the concept of Occam’s razor, as discussed in the Supplementary Information. By minimising the complexity of the description of the data (\({{{\mathcal{M}}}}\left({{{{\mathcal{A}}}}}^{-1}\circ {{{\mathcal{A}}}}\right)\)), the theory effectively formalises prediction (\({{{{\mathcal{A}}}}}^{-1}\circ {{{\mathcal{A}}}}:\{\tau \to \partial \to \tau \}\)). In this manner, the framework can be described as the pseudo-code in Algorithm 1 for which the LLM is presented with the following task:

$$\begin{array}{rcl}{{{{\rm{minimize}}}}}_{{{{\mathcal{A}}}},{{{{\mathcal{A}}}}}^{-1}} & & {{{\mathcal{M}}}}\left({{{{\mathcal{A}}}}}^{-1}\circ {{{\mathcal{A}}}}\right)\hfill\\ & & \,{{{\rm{subject\; to}}}}\,{{{{\mathcal{A}}}}}^{-1}\circ {{{\mathcal{A}}}}:\{\tau \to \partial \to \tau \}\end{array}$$

(10)

It is important to clarify that the encoding enc in Algorithm 1 does restrict the analysis. For example, different data types could be encoded as vectors obtained in the latent space of a given deep neural network. As long as the encoder algorithm is known and common to all the input data, the framework can be applied because of the theorems in AIT. In particular, the information non-increase theorem 10 indicates that, for any computable function f, the inequality K(f(x))≤K(x) + K(f) + O(1) holds. Therefore, once f is fixed for all data sets considered, K(f) becomes an additive constant that does not affect the analysis when K(x) is used to investigate the value of K(f(x)). In other words, the encoding is not important as long as it is known and kept fixed during the analysis.

It should also be noticed that CTM/BDM is not purely a brute-force approach35. Although CTM alone would be a brute-force approach that seeks the shortest computer programmes explaining the data, BDM is not (see the section “CTM and BDM: A neurosymbolic approach to Superintelligence benchmarking”). CTM/BDM operates by exploiting the best of both worlds35, operating at the fine balance between what traditional machine learning and deep learning approaches implement, while also combining it with optimal Bayesian causal inference51 or algorithmic deconvolution26. As further discussed and explained in the Sup Inf, we have called this approach algorithmic information dynamics (AID)27,28,29.

In order to present a quantitative implementation of a test following the SuperARC framework, an exploratory analysis is needed. This will be described in the next section, “ Design of experiments”.

Design of experiments

To evaluate how LLM models can be assessed within the SuperARC framework, we consider datasets composed of non-binary and binary sequences. It is worth highlighting that this choice is not mandatory, and all data should be encoded consistently. Different encodings may lead to different BDM values and thus other benchmarks may favour one type/structure of data or the other. Nevertheless, as BDM is an approximation to algorithmic complexity, AIT guarantees that algorithmic probability converges to the optimal solution in the asymptotic limit (if enough computational resources are provided).

Although prompting has been shown to considerably impact the performance of LLMs in a code generation task93,94, we use the simplest possible prompt to avoid providing additional information to the LLM, which could bias its output (even if towards better codes). Also, for the same reasons, we performed zero-shot learning tasks.

The non-binary sequences of integers used in the questions were divided into three levels of complexity, as indicated in the previous subsection. Intuitively, the complexity levels could be explained as follows:

1.

Low complexity: Sequences of digits or integers whose pattern is easily recognisable by a person and highly compressible. They have low CTM/BDM values.

2.

Medium complexity: Sequences of digit integers generated recursively with longer formulas than those in the simpler set. They have intermediate CTM/BDM values.

3.

High complexity: Random-looking sequences of digits or integers. They have high CTM/BDM values.

The following experiments were carried out:

Next-digit prediction task with binary and non-binary sequences: We prompted LLMs specialising in time series forecasting to predict the digits of non-binary sequences of increasing complexity of two types. The first type are random binary sequences according to increasing CTM/BDM, and the second type are called ‘climbers’. – Climbers are strings that, when sorted by algorithmic probability in descending order (highest to lowest probability), or algorithmic complexity in ascending order (lowest to highest randomness), these binary sequences are longer than strings in their same complexity group, defined as strings with the same or very close complexity values as measured by BDM but of significantly longer length than them. This means that for these strings, their complexity is definitely not driven by string length only but by (simple) their internal structure, aligning with an intuitive understanding of simplicity vs. randomness in sequence structure34. In other words, these are strings that clearly correspond to lower randomness values because they show lower complexity estimations compared to shorter strings in the vicinity. For example, the sequence 0101010101… up to a certain finite size n is clearly less algorithmically random and therefore more algorithmically probable than any other more random-looking string, short or long of the same size n, and therefore such a patterned sequence must appear earlier in a complexity hierarchy if BDM works correctly. So, knowing these are highly structured strings with high algorithmic probability, we tested whether LLMs would identify them by producing short models and better predictions for them compared to others. – Free-form generation task with binary and non-binary sequences: We challenged advanced language models, including GPT-4o, GPT-o1, Claude 3.5 Sonnet, GPT-4o-mini, Grok, o1-mini, Qwen, and DeepSeek, to generate models, algorithms, formulas, or Python scripts capable of reproducing specific target sequences. – Code generation task with non-binary sequences: An answer was requested to generate source code that would produce sequences of numbers using prompts of the following type:

“With no additional explanations or comments or notes, write the code in {} programming language to produce the sequence [sequence].

A full list of all sequences can be found in the Supplementary Information. Each prompt was submitted with varying values for the temperature parameter: [1, 0.7, 0.5, 0.2, 0.001], allowing for a comparison of its effect on the quality of the outputs.

Each prompt was formulated in such a way that it was expected that the LLM would return the code generating the defined sequences in the following programming languages: ArnoldC, C++, Python, Mathematica, Matlab, R, and JavaScript. After the codes were generated, they were executed, and their performance was compared.

Code and free-form generation tasks

Code generation in different programming languages was performed exclusively using non-binary sequences of increasing complexity and was run only by ChatGPT. In contrast, free-form generation was conducted using both non-binary and binary sequences and prompted to a list of the most prominent LLMs. Depending on the case, the following processing steps were applied according to Algorithm 1:

For the jth element of Dk,encoded, k ∈ {low, medium, high}, the output code (able to reproduce these elements) provided by the LLM model was Rk,j. Then, for these, after being logically evaluated to ensure that they produced the expected results, the following functions were applied.

Next-digit prediction task

For the next-digit prediction task, we used binary and non-binary sequences. We compared results obtained with different LLMs specialising in time series forecasting to predict values in the sequences used in our experiments. The models used included Chronos, TimeGPT-1, and Lag-Llama. Our criteria for selecting these models can be summarised as follows:

1.

researchers reported very high-quality predictions in zero-shot tasks, i.e., in time series never seen before;

2.

they were compared to traditional machine learning models, showing superior results;

3.

they are reported to capture dynamics in real-world datasets rather than relying on simple statistical patterns;

4.

authors advocate for the superiority of LLM architectures in time-series forecasting;

We split our sequences into several segments, using the models described to predict the remaining portions, which correspond to 10%, 25%, 50%, and 75% of the sequence. This approach divided the sequence into a ‘root’ and a ‘target’. For instance, given the sequence [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] and a prediction of 25%, the ‘root’ (the context provided to the prediction model) would be [1, 2, 3, 4, 5, 6, 7, 8], with the ‘target’ [9, 10] expected to be predicted. An asymptotic distribution of test results φ1, …, φn for growing n where ∣s∣ = n should provide some insight into the generalisation of the capabilities of the LLMs to scale their reported abilities, if any.

We employed three methods to measure the accuracy of the predicted target:

1: Sort similarity: This measures how many elements in the target sequence were predicted correctly, with their order being considered.

2: General similarity: This measures the correctness of predicted elements, without considering their order.

3: Levenshtein: This measures the Levenshtein distance between the expected and predicted sequences after converting them to strings.