FACT: Learning Governing Abstractions Behind Integer Sequences

Integer sequences are of central importance to the modeling of concepts admitting complete finitary descriptions. We introduce a novel view on the learning of such concepts and lay down a set of benchmarking tasks aimed at conceptual understanding by machine learning models. These tasks indirectly assess model ability to abstract, and challenge them to reason both interpolatively and extrapolatively from the knowledge gained by observing representative examples. To further aid research in knowledge representation and reasoning, we present FACT, the Finitary Abstraction Comprehension Toolkit. The toolkit surrounds a large dataset of integer sequences comprising both organic and synthetic entries, a library for data pre-processing and generation, a set of model performance evaluation tools, and a collection of baseline model implementations, enabling the making of the future advancements with ease.


Introduction
Ordered lists of integers are the natural representation form for all fundamentally discrete abstractions. These arise when encountering evolutions of discrete-time phenomena, finite symmetries of visual patterns, or algorithmic progressions, where they describe the development of consecutive states of a system, automorphisms of R 2 , or program listings, respectively. Sequences of integers are also the representation of choice when linearising structured information for analysis, data compression, and communication, with often-appearing datapoints tending to be encoded in the simplest or shortest form. Testifying to their utility to accurately represent abstractions, completion and extrapolation tasks on integer sequences are a frequent part of general human intelligence and aptitude testing ( [42,31]).
It is the aim and the hope for machine learning models to identify straightforward universal abstractions explaining the training data, rather than to memorise a plethora of small classes of exemplars and interpolate when given previously unseen input. The discovery and internalisation of governing concepts, or simply the learning of underlying rules, thus sits at the centre of artificial intelligence research.
We note that many concepts may be uniquely represented by a sequence of integers naturally (e.g. the squares of the natural numbers determine the polynomial n 2 ; 123, 312, 231, 132, 321, 213 encodes Figure 1: An illustration of an example conceptual learning programme applied to four separate instances: a toy recursive digit-counting sequence, the symmetries of an equilateral triangle, the evolution of an idealised rabbit population as described in [34], and the electron configurations across shells and sub-shells of an atom. In each instance, the raw data is comprehended in its original modality and then turned into an integer sequence. Then, a prior for the rule that applies is formulated. As more samples are observed, the rule is iteratively generalised until the governing abstraction has been fully revealed. the symmetries of a triangle), while others (such as the rotations of objects in scene) require a continuous space for a proper, scalable description. We recognise integer sequences as a general form for description of concepts completely representable with finite precision (finite in their nature; finitary) and put them at the centre of our study.
To discern the learning and understanding of these discrete abstractions from the learning of their representations in various modalities, we introduce a rich dataset of integer sequences together with a compendium of corresponding tasks that are innately related to integer sequences and well-suited to assess the levels of human-like understanding exhibited by machine learning models. Focusing solely on integer sequences, we thus set the concepts being learned apart from virtually all complexity stemming from the learning of a representation, making the learning process less resource-intensive and the interpretation of evaluation results more straightforward. An example learning programme making this distinction and proceeding to high-level abstractions is pictured in Figure 1.
Modern machine learning methods have been shown to posses the ability to comprehend (or at least pattern-match) convoluted concepts appearing in various data modalities, especially by the means of using deep learning to construct informative representations of the entities studied. In spite of working with number sequences, we take a step away from symbolic regression (which has so far dominated the notion of understanding in the area) and, tending to the trend, employ instead a multi-faceted approach in which sequences are characterised by their properties and relations to other sequences, rather than by explanatory symbolic formulas that are more readily interpretable by humans. We expand on the relationship of our work to symbolic regression in Appendix F.
Aiming at the comprehension of abstractions behind concrete representations of finitary phenomena, we unlock a new mode for evaluation of the quality of the abstractions learned. A guess, or an estimate, of the rule behind an integer sequence, which further leads to correct predictions of the sequence's elements on previously unseen inputs, is arguably more desirable than an estimate that describes the sequence well only for inputs known in training. The fundamentally algorithmic nature of the problem of learning finitary abstractions thus makes the problem of extrapolative generalisation well-defined, and allows us to consider extrapolative generalisation performance as a criterion for model assessment.
Our contributions are: • the introduction of a large dataset of integer sequences comprising data from both organic and synthetic sources and curated for subsequent use in tasks challenging models to develop understanding of the concepts determining the data (Section 2, [5]), • complementing the above, a utility library (FACTLIB [6]) for integer sequence data processing and generation, • the introduction of a variety of tasks designed to evaluate the model comprehension of conceptual patterns in integer sequences with a clearly established order of difficulty (Section 3), • a battery of evaluation metrics tailored to the above tasks to appropriately assess model performance and track progress in this sub-area of knowledge representation and reasoning, and • a collection of baseline models, both classical and neural, implemented to facilitate seamless experimentation (Section 4, [4]).

Dataset
As a part of FACT, we introduce a dataset consisting of over 3.6 million integer sequences. The structure-giving starting point for the dataset was the data made available by the Online Encyclopedia of Integer Sequences ( [39]). The OEIS is an organically grown comprehensive reference on noteworthy sequences of integers, compiled over decades to aid work in mathematical sciences. We have reviewed the OEIS4 data, set apart a suitable subset of 341,000 entries, and processed it specifically for use in machine learning, in line with the license requirements. Each entry of the dataset is now annotated by up to 18 features conveying the information about the nature, properties, and purpose of the sequence. In Figure 4, we give an overview of the result of this processing step. A full discourse on the extensive curation, refining, and automated annotation effort undertaken can be found in Appendix A.
With the encyclopedia entries aimed at a human reader, we observed that many covered their respective categories only very sparsely, relying on the associated natural language descriptions and the human ability to abstract to make the categorical connection. Our initial experiments with the baseline models (cf. Section 4) further confirmed that much of the data did not reach the critical mass of information necessary for reliable use in machine learning applications. We hence systematically extended the dataset by synthetically generated sequence branches while abiding by the structure and nature of the stem encyclopedia entries and providing carefully engineered automatic annotations wherever possible.

Synthetic Generation
Our principal inspirations were the notions of Kolmogorov complexity and Solomonoff probability [33,20,41]. Starting on the level of categories (cf. Figure 4), we defined a context-free grammar G c for each category c, and then used G c to generate ever longer formulas, which were in turn used to generate the sequences. This was done abiding by the notion that the growing length of formulas reflects itself in increasing complexity of rules and therefore generated sequences. An example grammar, used for the production of polynomial formulas, is given in Figure 3.
For each category, a total of 500K synthetic sequences have been generated. The length of the formulas used to generate these sequences was continuously increased following a logarithmic schedule, thereby favouring shorter formulas while still ensuring the presence of sequences from longer formulas. We give all details of our generation procedure for each sequence category in Appendix B.
The combined result of the OEIS curation and the dataset extension process is therefore a large dataset seamlessly integrated into FACT and easily extensible by FACTLIB, if required by more complex tasks or larger applications. The categories in the FACT dataset. It is composed of synthetic and OEIS entries. Each group in the synthetic part consists of 500,000 sequences, whereas the sizes of the OEIS groups vary. Dotted regions represent the main categories identified in the dataset. Ellipses define the sub-categories from our processing step in OEIS. Red dots mark groups that are augmented with synthetic data (and used in our benchmarking setup).
C o n s t P o s → 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 Figure 3: The context-free grammar used for the synthesis of formulas used for the generation of Polynomial sequences. N Const denotes a number constant, T denotes a term, and N denotes the root non-terminal for the polynomial expression.

Benchmark
Based on the dataset of the previous section, we propose a set of benchmarking tasks and evaluation metrics to assess a wide range of methods for their understanding of governing concepts behind evolutions of integer sequences.

Motivation
Consider the initial segment 0, 2, 4, 6, 8, . . . of a sequence and assume we are tasked with proposing reasonable candidates for the number that follows 8.
How could we go about evaluating the quality of our suggestions?
In the spirit of symbolic regression, we may choose to insist that there must be a single formula that produces the members of the sequence in order. But, even under such condition, for every suggested continuation integer there exists a degree-8 polynomial accommodating the continued sequence. This is despite the fact that a human would intuitively be most likely to suggest 10 as a reasonable continuation, perhaps even justifying it by the observation that the first 5 elements of the sequence follow the pattern of (2n) n≥0 .
As described in Section 2, we have therefore set the generation methods of the synthetic part of our dataset to explicitly apply the parsimony principle by varying the length of generative formulas to control the complexity of the resulting sequences. Data generated in this manner is guaranteed to encompass sequences coming from rules of varying degrees of complexity by design, rather than by chance.
The focus on preferring shorter rules over longer ones would, however, be too artificial if employed alone. Consider the initial segment 1, 1, 2, 3, 5, . . . . While it is tempting to promptly claim that the numbers come from the Fibonacci sequence and that 8 should follow, an answer arising more naturally in the context of chemistry is 9, as the continued sequence represents the count of all possible n-carbon alkanes.
Hence, striding ahead of the symbolic regression under Occam's razor, we add a processed part of the OEIS dataset into our evaluation procedures as an indicator of the sequences' appeal across a multitude of scientific disciplines. Note that this is an improvement made in addition rather than in contrast to the principles for synthetic sequence generation, as many of the real-world sequences collected in OEIS do indeed obey straightforward rules.

Structure
As motivated in Section 3.1, for each benchmarking task we provide two evaluation sets: one for synthetic data and one for OEIS data. Our benchmark thus pushes for the design of machine learning models that identify simple concepts and rules (evaluation on synthetic data) but still retains enough of cross-domain generality to have practical impact in different disciplines (evaluation on OEIS). The benchmark consists of tasks with an established order of difficulty over two dimensions: the task type and scope. We distinguish between the tasks of sequence classification, sequence similarity, next sequence part prediction, sequence continuation, and sequence unmasking -each detailed below.
In addition, we perform each task to the extent of two different scopes: within and across categories. The case of performing the task within categories is the simpler of the two setups, since the category from which the sequence originates is known in advance, and this information is thus also available at the time models are designed. Nevertheless, our baselines (cf. Section 4) are oblivious to this information and instead treat the category scope as if nothing was known about the data.
In our particular benchmarking setup, our dataset is split into four parts, namely the training, validation, synthetic test, and organic test sets. The training and validation sets consist of only synthetic sequences. The size ratios between training, validation, synthetic testing, and OEIS testing datasets are 9:1:1:1. For convenience and future reference, we make this divided-up data available as separate datasets. Nevertheless, the FACT dataset is also available in one piece, allowing users to choose their own splits or supplement their own data generated by FACTLIB, according to their needs.

Task Types
In this section we present 5 types of tasks in order of difficulty, for which we take the upper bound on the difficulty of the task instances comprising the given task. For example: Every instance of sequence continuation belongs to the set of sequence unmasking instances. But, for every instance of sequence continuation (except for the trivial one where we only begin with one number) there is an instance of unmasking that is harder. Such an instance can be formed by further asking to unmask a sequence element somewhere in the initial segment provided for continuation. Hence, the upper bound on the difficulty of sequence unmasking is strictly higher than the upper bound on the difficulty of sequence continuation.

Sequence Classification
The simplest task type in our benchmark is classifying in which category the sequence belongs. The chief goal of this task is to evaluate whether models can distinguish and identify general patterns in sequences, both across and within different categories. Note that category membership may not necessarily be unique. For example, a sequence can be bounded, but also periodic. For this task we use all categories that possess a synthetic counterpart within our dataset. Each sample consists of an array of integer numbers for the given sequence class. We distinguish between two task sub-types and give their objectives: • One-vs-Rest (OvR). Obj. to identify whether the sequence belongs to a specified category or not. For this case, we provide a balanced dataset in each category. This is a binary classification task, and as such, we use accuracy as the evaluation metric.
• Multiclass classification. Obj. to predict, for every sequence, all categories to which it belongs. The performance is measured with the macro average F1 score (i.e. the mean of individual per-class F1 scores) due to inherent imbalances in our dataset.

Sequence Similarity
The similarity task aims to assess model ability to represent sequences in a way that reflects their similarities in type (e.g. agreeing on category membership) or properties (such as being periodic or unbounded) in the spirit of [24]. The objective is to embed sequences into an embedding space such that sequences belonging to the same category are closer to one another than to sequences of categories to whom they do not belong. We evaluate using • the Recall@k score, where the k candidates for a sequence s are proposed by sampling k sequences from each category and then ordering the category labels according to the distance of the carrier points from s; and • the top-k root mean squared error -the root mean squared error (RMSE) across the top k similarity candidates. Given k predictions of a model {ŷ i } i∈{1,...,k} and ground truth y, we define the top-k RMSE as min i∈{1,...,k} RMSE(y,ŷ i ). In other words, given all generated predictions we report the RMSE of the prediction closest to the ground truth.
Our choice of evaluation metrics is grounded in the observation that sequences generated from similar simple rules often eventually diverge, and that to a large extent. This task generalises sequence classification.

Next Sequence-Part Prediction
As seen in natural language processing [10], asking a model to decide whether two sentences follow one another can be beneficial for testing of whether a model understands its inputs. Given two contiguous sub-sequences s 1 and s 2 , the objective of the next sequence-part prediction (NSPP) task is to determine whether the sub-sequence s 2 is a valid continuation of s 1 . We create a balanced dataset for this task, by using all categories of our dataset that have a synthetic counterpart. NSPP is then simply a binary classification task and the performance is measured by prediction accuracy. This task is strictly more difficult than the similarity task, since it demands that the model not only understands the key properties of the sequence but also possesses the ability to discern unlikely or unfeasible combinations of sequence parts from the feasible ones.

Sequence Continuation
The fourth task type in our difficulty hierarchy is to suggest the next entry in a given sequence s. This task is extrapolative in its nature, and is meant to challenge model understanding beyond making a binary decision between externally provided suggestions. As such, this task demands better understanding of the rules governing sequences than next sequence-part prediction -hence it's placement above NSPP in the difficulty hierarchy. We distinguish two sub-types of this task, namely the single-shot and multi-shot continuations, differing only in the number of candidates the model is expected to provide for the continuation. We use the root mean squared logarithmic error (RMSLE) and top-k RMSE for each of the sub-types, respectively.

Sequence Element Unmasking
At the apex of our complexity hierarchy is the task of unmasking marked elements of a provided sequence. The sequence continuation task can be viewed as a special case of unmasking, where only the last element is masked. We consider only multi-shot unmasking and choose top-k RMSE as the evaluation metric.

Baseline model performance
We run extensive experiments on the proposed benchmark as a starting point for further research. We consider classical machine learning methods as well as large neural networks. The experiments in this section highlight the feasibility of learning many different patterns in integer sequences, but also some of the limitations of the existing methods.

Models
To provide baselines for model performance on the above tasks, we use a total of 24 different models across our benchmarking tasks, namely 4 neural models (dense, recurrent, and convolutional networks, and transformers), 9 classical classifiers (k-nearest neighbours, Gaussian naive Bayes, linear support vector machine, decision tree, random forest, gradient boosting, AdaBoost, XG Boost, dummy classifier), and 11 standard regressors (k-nearest neighbours, linear regressor, ridge regressor, lasso regressor, Elastic Net, single decision tree, random forest, gradient boosting, AdaBoost, dummy regressor).
We give details on their implementations and hyperparameter settings in Appendix C.

Results
A simple overview of the performance of the baseline models can be found in Table 1. A comprehensive, detailed listing of our results, including results of evaluations on the category level, can be found in Appendix D.

Metric Interpretation
The macro-averaged F1-scores for the sequence classification task in Table 1 suggest that even the best-performing models have an average score of little over 0.5. The F1 score of 0.5 can be achieved   Table 1: An overview of the results for all tasks, evaluated across the whole dataset. MLP, RNN, and CNN stand for multi-layer perceptron, recurrent neural network, and convolutional neural network. Emphasis and emphasis mark the best performing models for the OEIS and synthetic data, respectively. For F1 score and binary accuracy, higher is better. For RMSLE and top-5-RMSE, lower is better.
in many ways, but would for example correspond to a precision-recall performance of 0.5 − 0.5.
In the next sequence-part prediction, the RNNs appear to be nearing the perfect accuracy score of 1.0, though some room for improvement remains to be seen in the case of the organic dataset. The root mean squared logarithmic errors of 0.578 (best OEIS performance) and 0.395 (best synthetic performance) that appear in the results for the continuation task correspond to uniform difference of logarithms of the same magnitude. In contrast, the two respective worst performances among the baselines models correspond to uniform difference between logarithms of 0.923, 0.877.
The top-5 root mean squared errors are more straightforward to interpret. One would arrive at RMSE between initial sequence segments s 1 , s 2 if s 1 were larger or smaller than s 2 by exactly 5 in every one of its elements. Top-5-RMSEs of 0.267, 0.270 for the sequence similarity task therefore correspond to mean uniform difference of the same magnitude in every element when comparing the true sequence to the best fit from among the top 5 results of the similarity search. The same metric is used for the unmasking task. In the light of the distribution of the elements of the sequences considered covering values from 0 to several million, the performances of baseline models, especially in the similarity task, appear to be remarkably strong.

Comparative Analysis
Reviewing the results of Table 1 and further Appendix D, we note that even just the performance of baseline models on the synthetic dataset is often quite strong in absolute terms. We also notice a general trend among all models to perform better on synthetic data than on the organic OEIS sets. This is not unexpected, since the OEIS data is highly varied and comes from a large variety of sources, whereas the synthetic data is generated according to a strict, uniform procedure, thus having a more regular distribution. Nevertheless, we observe that training on synthetic data alone still yields solid performance on the organic dataset across all models.
In the classification task, RNNs and random forests achieve the best results across all categories. Unsurprisingly, RNNs very accurately identify bounded and increasing sequences, while random forests lead for modulo, prime, exponential and trigonometric sets. RNNs also show a consistent lead for the next sequence-part prediction. Transformers and CNNs dominate the results for similarity under the top-k accuracy, with the exception of organic periodic functions, which are best handled by recurrent networks. Transformers alone lead in the same task when evaluating by top-k RMSLE, and likewise for convolutional networks in the unmaskingtask .
The best performances for the continuation task are almost evenly split between recurrent networks and transformers, where RNNs lead for polynomial, exponential, trigonometric, and periodic sequences (transformers being the worst performers). Transformers yield the best results modulo, prime, bounded, increasing, and all sequences together.
We lay out our expectations for model performance on this benchmark, also in relation to human ability, in Appendix E.

Related Work
There has recently been a noticeable movement in neural network research towards understanding how DNNs learn to abstract. On the side of investigation, traditional architectures were analysed by [21] in terms of the emergence of knowledge across the network, a well-defined metric for the generalisation ability of neural networks was introduced in [11], and a methodology to assess knowledge representation in deep neural networks trained for object recognition in computer vision was proposed in [18]. The increasing interest in the learning of abstractions also prompted the incorporation of relevant inductive biases into deep neural architectures and training curricula, as was seen in concept acquisition [46,14], with the introduction of the neural state machine [16] in computer vision, and causal abstraction analysis [2,3,13] in natural language inference. Further, efforts have already begun to assess the capability of models to perform abstracting visual reasoning [47, 1, 48, 7].
A common, classical, and still challenging instance of abstraction learning in the context of number sequences is the task of symbolic regression. A number of genetic programming models and purposespecific datasets have been proposed in the field in its over 30 years of existence, and a systematising benchmark, SRBench [22], was recently introduced. It combines 130 smaller numerical datasets, both organically grown and synthetically generated, with the PMLB [26], and comes with an evaluation of a range of symbolic regression models using a newly-proposed metric. The inherent focus of the task on interpretability makes it suitable for industrial use but leads to challenges in identification of prevailing generative concepts, as two sequences originating from two distinct instances of the same rule may be best fitted by two formulas completely different in their nature.
Focusing on integer sequences, the Online Encyclopedia of Integer Sequences (OEIS) was presented in [39]. The entries of the encyclopedia come from both individual human contributors and automated mechanisms for the invention of "interesting" sequences [8]. It was used for sequence classification combining heuristics and machine learning methods in [45], for the sequence continuation task by fully-connected neural networks in [30], for digit-level sequence term regression to highlight the computational limits of neural networks in [25], and for the learning of mathematical properties of integers for use in natural language processing by training OEIS-sequence embeddings in [32]. The latest version, OEISv4, is the most comprehensive source of annotated information on integer sequences, containing over 300,000 entries. The dataset has further seen use in the emergent sub-area of deep symbolic regression [23,29,9,19].
Our experience shows that the OEIS data is too sparse and too closely tailored to the needs of human reader to be useful for training of machine learning models for integer sequence comprehension. It can still, however, serve as an interesting proxy of "usefulness" (such as in [8]) in model evaluation when appropriately filtered and pre-processed for that purpose.
6 Avenues for Future Work The carrying advantage of the focus on integer sequences instead of other -potentially richer -input modalities is that we can directly interpret the performance scores of individual models as their ability to comprehend sequence-giving abstractions, and have the confidence that no model performance has been hampered by its insufficient understanding of the input representation. Here, while the models we evaluated appear to show some level of understanding of patterns underlying integer sequences, there is still significant room for improvement, especially in multi-class classification, sequence continuation across all classes, and sequence unmasking.
The results of Section 4 were all produced for a "static" mode of operation, in which all of the query data (e.g. the sequence to classify or a sequence prefix to continue) was provided to the model upfront and as a whole. A mode of operation occurring perhaps more naturally in most practical scenarios is that in which the model is active in its learning and interacts with an oracle, polling for information until it is confident that it can provide and answer. Such interactive variants can be readily formulated for all tasks in Section 3.3, but require a more sophisticated set of evaluation metrics that takes into consideration the amount of information the model requested before producing an answer. We believe that this setup deserves attention as it can provide valuable insights into model reasoning, and we aim to tackle it in our future work.

Conclusion
Integer sequences frequently arise as the natural representation form for finitary phenomena. Focusing on integer sequences allows us to directly address the problem of learning abstractions and removes the otherwise necessary overhead of learning modality-specific representations.
The benchmarking toolkit for integer sequences presented in this work is by design general in its purpose, aimed at fundamental understanding due to its use of integers as primitive representations, and hierarchically encompasses many of the tasks that have previously appeared isolated in the literature.
It is our hope that our work will help attract attention to the challenges of designing models that perceive logical relationships ruling over the training corpora and reason during inference, thus helping to facilitate future advancements on the frontiers of general artificial intelligence. [

A OEIS Processing
The On-Line Encyclopedia of Integer Sequences [35], OEIS for short, is an online dataset of integer sequences. Founded in 1996 by Neil Sloane the dataset was since then steadily expanded by amateur and professional mathematicians as well. In 18 columns the dataset provides information about various properties of those sequences. The 18 column names are briefly explained in Appendix A. We worked with an offline version of the OEIS dataset which contains 342 304 sequences. On a content level they range from well known like A000045, Fibonacci numbers: with F (0) = 0 and F (1) = 1, over simple ones like, A000004: the zero sequence and complex ones like A339123: number of 2-connected multigraphs with n edges and rooted at two indistinguishable vertices and have no decomposition into parallel components rooted at the two distinguished vertices, to quite creative ones like A001049: numbered stops in Manhattan on the Lexington Avenue subway. A detailed summary can be found in [39].
Field Names In this section we give a brief explanation of the 18 fields in the OEIS dataset. This is based on the style sheet provided by OEIS [37].
• oeis_id A unique 6 digit number preceded by an "A". For example A005735

• identification
This refers to the ID the given sequence had in one of the books A Handbook of Integer Sequences [38] (M followed by a 4-digit number) or The Encyclopedia of Integer Sequences [40] (N followed by a 4-digit number).

• value_list
A list of comma separated integers. The actual sequence of interest. Depending on the sequence in question the length of this list can vary by some orders of magnitude. For example A058445 contains only one element while the value list of A175320 has a length of 1 578 727.

• name
A brief explanation of the sequence. Sometimes, when possible, this already contains an easy-to-use formula to generate the sequence. For example A005843 has the name The nonnegative even numbers: a(n) = 2n.
• comments Further general details and side-notes about the sequence that would make the name too long. Here we often can find alternative formulas to generate the sequence or different places in all of mathematics where this sequence pops up. For example one of the comments of sequence A000045, the Fibonacci Numbers, is "Also the number of independent vertex sets and vertex covers in the (n-2)-path graph." • detailed_references References to journal papers and books that can not be linked in the "links" field.

• links
References to material which can be accessed online. References to other sequences in the dataset which are related in some way.

• keywords
Keywords from a short set of possibilities. For example nonn is used for sequences that have no negative values currently in their respective value_list field. • offset_a Index of the first element in the value_list. For example A005843, the aforementioned sequence of "The nonnegative even numbers: a(n) = 2n.", has an offset_a of 0 because the first element is calculated by a(0) = 2 * 0, i.e. the index is 0.

• offset_b
Index of the first element that has an absolute value larger than 1.

• author
Name of the original contributor and date of first contribution.

• extensions_and_errors
Used to claim credit for additions to the entry that can't be properly acknowledged in other fields.

A.1 Characteristics
In this section, we introduce some other characteristics of the dataset that required preprocessing and extensions.
• NULL Values Not every sequence contains information in every of the 18 columns. Table 2 shows the number of valid entries per column in the dataset. We say an entry is valid if it is not NULL. When programming classification methods these invalid entries have to be taken into consideration. Of course this can be a limitation for the meaningfulness of such classification methods. For example we can not check whether the formulas field contains a Fibonacci-Like formula when it is NULL. However, the fact that the field is NULL can also be a hint that no known closed formula exists (otherwise someone would probably contribute it to the OEIS).

• Sequence lengths
Since it is harder to calculate elements for some sequences than for others, the length of the value_list shows a high variance. Figure 5 shows the distribution of sequence lengths Keyword Occurrences  base  39097  bref  739  cofr  2866  cons  11454  core  178  dead  1684  dumb  99  easy  79148  eigen  430  fini  6594  frac  7050  full  5494  hard  7137  hear  162  less  2683  look  2829  more  20107  mult  2120  nice  6891  nonn  321805  obsc  120  sign  18480  tabf  6442  tabl  20248  unkn  32  walk  4285  word  749  Table 3: Number of occurrences of each keyword over two different scales. As we can see there is a substantial number of sequences with short sequence lengths (say less than 30). Short sequence lengths can pose a problem to classification methods that need more elements for some mathematical calculations. For example we can fit a polynomial of degree 20 to 21 datapoints, but then we can not validate the result on additional datapoints. • Keyword counts Table 3 shows the number of occurrences of each of the 27 possible keywords. Again, for a full description of what each keyword means see the corresponding Wiki page from OEIS [36]. In order to group similar sequences from OEIS together we create categories and decide for each sequence whether they belong into this category or not. Since for some sequences it is not immediately clear whether they belong to a given category or not, we relaxed the requirement of this binary classification to a finer graduated classification. To this end, we have 5 different levels of membership, represented by integers 0 through 4. These values indicate how confident our classification is, as seen in the following table: 0 Does likely not belong in this category 1 More likely than not does not belong in this category 2 Inconclusive 3 More likely than not belongs in this category 4 Does likely belong in this category In this chapter we introduce and explain methods we used to define categories and create the associated labels for membership. Neither our selection of categories nor the different Classification Methods are exhaustive, therefore we implemented an easy to use framework which enables a fast creation of new categories. This framework is explained in the following Section A.3.

A.3 The Annotator Class
We implemented the Annotator Class which lets a user create new categories of sequences. Each instance of the Annotator Class is responsible for one category. As depicted in Figure 6 each Annotator is linked to an Aggregator and one or more Classification Methods (see Sections A.4 and A.5 below). The Annotator is responsible for running all its Classification Methods for each sequence, providing the Aggregator with results and storing the 5-Level membership results for future use.

A.4 Aggregator
An Aggregator, as the name suggests, aggregates the results from the Classification Methods and returns a 5-Level membership value.

A.5 Classification Methods
Classification Methods are functions which take all the information about a sequence (i.e. all the fields described in Section A) as an input and return results of some test which are then further processed by the Aggregator.
Note, all Classification Methods have to check whether the fields which have to be accessed by the test do exist for the given sequence, i.e. the field is not empty or NULL.
As we will see in the following subsections, a Classification Method can be something as simple as searching for a given word in the name of the sequence or more complex like doing some advanced calculations based on the value. However, Classification Methods should be designed to have a rather short runtime per sequence since the same function has to run on all sequences in the dataset. As a rule of thumb, when a test takes one second per sequence the total runtime on the current dataset will be about 4 days. Intuitively this is the discrete signal analog of repeatedly taking the derivative of a polynomial until we end up with the constant 0 function. By counting the number of iterations, we get the degree a fitting polynomial would need to have, which we can then use for Polynomial Interpolation.

• Polynomial Interpolation
We used the SymPy [43] library to perform symbolic polynomial interpolation with the degree calculated by Newton's Divided Difference Method. This allows us to fit a polynomial of degree n to the first n + 1 values of the sequence and use the remaining values to calculate the error between the fitted polynomial and the actual values. Of course we need to assert that there are enough values, which were not used during interpolation, to be able to calculate a meaningful error. In cases where the error between the fitted polynomial and the actual values is 0 and we have enough values, we conclude that the sequence in question indeed has a polynomial form.

• Exponentials
To detect exponential sequences, such as A000244, Powers of 3, or A007689, a(n) = 2 n + 3 n , directly from their values a i we first calculate the sequence of quotients q. Each element of q is the quotient of two subsequent elements of the original sequence: (1) Purely exponential sequences, like Powers of 3, produce a constant-valued q. In our example q i = 1/3 for all i. Such sequences pass this test immediately. Sequences that are dominated by an exponential like A006127, a(n) = 2 n + n, produce a sequence of quotient that approaches a constant value. In this example we get We approximate the limit of q by checking the very last values of it that can be calculated from the given data. If the last 30 elements are all within some threshold range of the final value we conclude that the sequence probably is dominated by an exponential function.

• Primality
Using SymPy again, we tested which sequences can be interpreted as the application of the above classes of functions to prime numbers. The way we implemented this test was limited to numbers smaller than 2 64 (or about 10 19 ).

• Boundedness
Testing the absolute values of the sequence elements for boundedness by different values, is an easy but insightful series of tests.

• Palindrome
This test checks whether all elements in a sequence are palindromic, i.e. if all values are numbers that are the same when read from left to right as well as from right to left. Trivially this is true for all sequences that contain only values smaller than 10 since all single-digit numbers are palindromic (i.e. 7 is the same number when read from either direction).
The results from this test depend on the base of the number system used to display the values of the sequence. For example 12321 is palindromic in base 10 but in base 2 it is not: 12321 10 = 11000000100001 2 .

• Periodicity
We tested whether a sequence has a repeating part up to a maximal period length of 10 000 elements. To pass the test a sequence needs to have at least 3 full periods in the value_list.
String Search Since most of the fields in the dataset are populated by plain text, one of the easiest methods to get information about a sequence is the search for specific words or strings within a given fields. This method can be a reliable indicator whether a sequence does belong to a category, for example performing a string search of the word prime on the name of A098682, Smallest prime larger than n n , can serve as a good indicator that A098682 indeed is at least in some way related to prime numbers. However, the opposite conclusion is harder to draw, is a sequence truly unrelated to prime numbers just because it is not mentioned in the name or comments?

Regular Expressions
Due to the similarity with the well known Fibonacci Sequence (A000045), we call sequences with formulas that are matched by above regular expression Fibonacci-Like.

B Synthetic Generation
In this section we explain the steps followed to create synthetic sequences.
From the identified categories (cf. fig. 2) in the OEIS database, we have elected a significant and representative subset and augmented their organic entries with synthetic data. For each category, a total of 500K synthetic sequences have been generated. The sequences were generated with logaritmically increasing length of the generating formula. This way, most of the sequencesgenerating expressions are relatively short (motivated by Kolmogorov complexity, cf. Section 2), but longer sequences remain playing a significant role in the dataset. In the following, we provide information how synthetic extensions of each sequence category are created using context-free grammars. Typically, the "logical" terminals in our grammars are {V ar, Const} and the non-terminals {Add, Sub, M ult, N Const, P ow}. N Const is defined as the non-terminal which represents the number constants with multiple digits. The reason why we consider it a non-terminal is that we count the length of polynomial based on the number of non-terminals only.
Polynomial The context-free grammar for polynomials is defined as: Exponential Context-free grammar of exponentials group is defined as: Prime In this group, we introduce a non terminal P rime(x), which evaluated at value x ∈ {1, 2, ...} returns the i th prime number. That is, P rime(1) = 2, P rime(2) = 3, P rime(3) = 5, and so on. This way we inject in our sequences prior knowledge about prime numbers. More concretely, the context free grammar is defined as: Periodic Periodic group makes use of the previous grammars, but it also has a non terminal that is added in the root of the grammar, which makes the whole sequence repeat only the first few k numbers. More concretely, we can phrase this as a grammar too, by adding primitive P eriodic as a root of the grammar Finite Finite is a simple group where we only create a list of finite numbers. They are created the same way by using previous rules but they are cut at a specific place randomly.
Increasing The next three groups are meta-categories, for which no specific grammar is used, but the property is inferred afterwards. If the sequence generated is monotonically increasing, then it is labelled as increasing.
Bounded If the sequence is bounded by a number, then it is labelled as bounded. For example sin(pi * x) is bounded.
Unique If all numbers in the sequence are distinct, then it is marked as unique. We generate at least first 500 numbers of the sequence to check this property. Of course, this may not be the case for the numbers appearing later in the sequence.

B.1 Hosting and Maintenance of the Dataset
The dataset is available through the ETH Research Collection and is directly accessible with DOI 10.3929/ethz-b-000562705 [5]. The ETH Research Collection guarantees minimal data retention period of 10 years. The presence of the dataset will be maintained by the D-ITET DISCO and ISG groups. Members of DISCO will also be responsible for the maintenance of the dataset in response to queries or any errors found and reported -please email fact@ethz.ch to do so.

C Baseline Models
To provide baselines for model performance on the above tasks, we use a total of 24 different models across our bench-marking tasks, namely 4 neural models, 9 classical classifiers, and 11 standard regressors. The following sections describe the architecture of these models. For consistency, we used the random seed 1234 wherever it could be specified.

C.1.3 Convolutional Neural Network
Here we used a simple stack containing a convolutional layer with kernel size 2, 10 filters and a pooling-layer of size 2, with unit strides. The network was composed of three of these stacks, terminating in a dense layer with the same activation as above. The hyperparameter-tuning focused on filter and kernel size: filters ∈ [1, 5, 10], kernel size ∈ [2,4,6], stack depth ∈ [2, 3]

C.1.4 Transformer
We followed the transformer architecture of [44] with only the normalisation layers excluded. We use six transformer blocks for the encoder and three for the decoder decoder. Each multi-headed attention unit consists of 20 attention heads and the output dimension of the embedding and feed-forward layers is 12. We focused on the number of attention heads as well as the embedding dimension in our grid search: heads ∈ [5,10,20,40], embedding dimension ∈ [3, 6, 12, 24].   For our tasks in static mode we used binary-crossentropy as a loss for classification and mean squared logarithmic error for regression.

C.3.2 Flexible Contrastive Loss
In dynamic mode we went for a contrastive loss described in the following formula: where d is the euclidean distance between two sequences in the embedding space and α is the margindistance which penalises dissimilar pairs only if their distance d is inside its radius. The goal of this loss is to embed similar sequences near each other in terms of the euclidean distance and different ones further away. The parameter λ functions as a measurement of similarity. In each dynamic task we define this measurement differently. In sequence similarity, λ is the indicator function between two classes. In sequence continuation, λ is the fraction between the first n similar numbers of two sequences and its total length, whereas in sequence unmasking λ is the fraction of masked entries in a sequence paired with its unmasked counterpart. With this approach we seek to build an embedding space that learns to differentiate different sequences according to our tasks given.

C.4 Hosting and Maintenance of the Benchmarking Baseline Models
The bechmarking baseline models are available through the ETH Research Collection and are directly accessible through DOI 10.3929/ethz-b-000565644 [4]. The ETH Research Collection guarantees minimal data retention period of 10 years. The presence of the models will be maintained by the D-ITET DISCO and ISG groups. Members of DISCO will also be responsible for the maintenance of the models in response to queries or any errors found and reported -please email fact@ethz.ch to do so.     Table 7: The accuracy results for the sequence similarity task, evaluated both within categories and across the whole dataset. Emphasis and emphasis mark the best performing models for the OEIS and synthetic data, respectively. For binary accuracy, higher is better.   Table 9: The top-k RMSE results for the sequence similarity and unmasking tasks, evaluated both within categories and across the whole dataset. Emphasis and emphasis mark the best performing models for the OEIS and synthetic data, respectively. The masking probability is 0.25. For top-k-RMSE, lower is better.

E Expectations on Model Performance
We believe that our the baseline classifier performance can be vastly improved on and shifted towards the region of 0.8 to 0.9. We would expect tailored models to have near-perfect performance on the next part prediction task, RMSLEs of below 0.3 (corresponding to 0.3 uniform sequence element logarithm difference) in the continuation task, and top-5-RMSEs in the similarity and unmasking tasks of below 0.1 and 1.0, respectively.
Especially in the sequence similarity task, which is essentially a database lookup task, we would hope that the top-k-RMSE performance on the synthetic test set could be brought to essentially zero. The OEIS dataset, however, contains many sequences that belong to the categories used for the experiments run in Section 4 but are very different from what one would achieve by procedural generation as per Appendix B. We therefore do not think it feasible for the currently known architectures could achieve near-perfect results on this set, but see this as a natural challenge for architectures yet to be proposed.
An argument could be made that a human, if faced with the task of even just identifying the category of many of the sequences in OEIS, would struggle greatly and perhaps soon resort to guesswork. The existence of Online Encyclopedia of Integer Sequences alone is a proof of that understanding integer sequences for what they are is, in practice, very often beyond the computational abilities of humans and demands thorough, encyclopedic knowledge instead. By extension, one could be tempted to claim that our effort goes in the wrong direction with respect to the general motivation of artificial intelligence research, as the problem we are considering is much more difficult than what one would consider the natural baseline for intelligence -human performance -can reliably handle. This dilemma of "turning the tables in the Turing test" was popularised and partially answered in [28]. Let us just simply invoke the argument of the Turing test "in the limit", in which the human participant would have enough time and resources to develop a mechanism that would allow him to begin answering the trial's questions at computer-level speeds. Then, the apparent difficulty of our benchmark is no longer in contrast with the common conception of intelligence, and furthermore, the development of such a mechanism is precisely something we hope will be facilitated by the benchmark presented in this paper.
The utility of our benchmark, however, can be seen even when disregarding this somewhat philosophical challenge. The existence of OEIS as an online service proves demand for a system that "understands" sequences, and perhaps continues them, fills their gaps, and suggests similar sequences on top of immediately identifying which category the sequence belongs to. Our benchmark can thus be viewed as a sort of "CodeSearchNet [17] for sequences", built to aid the development of models that can satisfy this demand.

F Relationship to Symbolic Regression
One can notice that contemporary symbolic regression methods could be deemed suitable for performing the unmasking task, or at least its easier variant -the continuation task. We emphasise that the aim of the FACT toolkit is not to address these tasks as challenges, but instead to provide tools for research on the learning of finitary abstractions.
With this motivation in mind, there seems to be little evidence that classical symbolic regression methods manage to abstract any high-level descriptive information about the data they fit in their regression process. Indeed, many of the methods used for symbolic regression perform systematic searches of hypothesis space of potential formulas. While perhaps guided by sound empirical search methods and well-founded heuristics, they do not learn, and they do not learn to abstract anything about the nature of the sequences they regress. Further, many of these methods make precisely the assumptions of simplicity of the underlying generative rule we make in our generative process, which would render their baseline evaluation results vacuous. As such, we have therefore decided against their inclusion in this work, and believe that while state-of-the-art symbolic regression methods may play a role as performance contenders for future studies leveraging FACT, they would be difficult to interpret as natural baselines for finitary abstraction learning.
PROMPT: [Continue the following sequence: ] 0, 1, 3, 6, 2, 7, 13, 20, 12, 21 GPT-3 DAVINCI: The sequence is made up of numbers that follow the pattern of adding the two most recent numbers together. This pattern is known as a Fibonacci sequence. GPT-3 DAVINCI: The sequence appears to be a list of powers of two, with the exception of the third number.
BASELINE TRANSFORMER: Too big, the sequence was not included TRUE (ASSUMING MERSENNE PRIMES): Prime, or rather, primes p such that 2 p − 1 is a prime.
Here we observe that the GPT-3 is sometimes right, but sometimes just assumes a sequence based on its popularity, or misses crucial detail.

H Datasheets for Datasets
For the dataset documentation we used the recommended documentation framework "Datasheets for Datasets" [12].

H.1 Motivation
For what purpose was the dataset created? To advance research in comprehension of finitary abstractions.
Who created the dataset? The dataset is a combination of the efforts of contributors to the Online Encyclopedia of Integer Sequences and our own systematic synthetic data generation effort. All those who contributed, directly and indirectly, are given credit in Acknowledgements. We will aim to keep acknowledgements in our GitHub repository up-to-date as the work on the dataset continues in the future.

H.2 Composition
What do the instances that comprise the dataset represent (e.g., documents, photos, people, countries)? Are there multiple types of instances (e.g., movies, users, and ratings; people and interactions between them; nodes and edges)? The dataset consists of integer sequences -or rather, initial segments of integer sequences, and in most cases also annotations that allow for their automatic continuation if necessary.
How many instances are there in total (of each type, if appropriate)? See Section 2. Short answer: About 3.6 million.
Does the dataset contain all possible instances or is it a sample (not necessarily random) of instances from a larger set? It is a well-structured of a larger set as there are infinitely many integer sequences.
What data does each instance consist of? "Raw" data (e.g., unprocessed text or images) or features? Annotated entries pointing to integer sequences.
Is there a label or target associated with each instance? If so, please provide a description [Yes] All labels and targets are described in Section 3 and further Appendix A.
Is any information missing from individual instances? If so, please provide a description, explaining why this information is missing (e.g., because it was unavailable). This does not include intentionally removed information, but might include, e.g., redacted text. We have used 10:1:1 ratio of our synthetic training, synthetic testing, and organic testing sets in the benchmarking setup. Data split in the fashion is separately available through the ETH Research Collection, see [5].
Are there any errors, sources of noise, or redundancies in the dataset? [No] Is the dataset self-contained, or does it link to or otherwise rely on external resources (e.g., websites, tweets, other datasets)? The dataset is self-contained, there are no restrictions associated with any of the external resources that might apply to a future user.