Zoea

Zoea's latest heuristics completely overcome the combinatorial explosion problem in inductive programming. This opens the door to large programs that are guaranteed to work, produced from test cases in seconds and without needing a supercomputer, LLM or a single neural network.

All programming languages are composed of a set of elements including keywords, operators, variables and so on. These can be combined, according to the rules of a grammar, to form statements, control structures, functions and complete programs.

Now, the grammar doesn't just describe one program but rather every possible program, that could ever be written - no matter how large or complex. This means that there are an enormous number of possible ways in which even the smallest programs can be put together. Whilst this is a good thing in terms of the expressiveness and versatility of the language, it makes generating programs very difficult, since there are literally too many options.

It is a fundamental tenet of computer science that it is impossible to determine the output of any non-trivial program without running it. This means that any approach which aims to produce software from a specification, such as inductive programming, is obliged to search a space of candidate solutions. The problem is that the size of this space quickly becomes astronomical, as program size increases. This problem is called the combinatorial explosion.

Before Zoea, virtually no effort had been expended - and zero progress had been made - in addressing this problem over the last fifty years. Amazingly, generations of computer scientists have spent entire careers conducting research on inductive programming, while behaving as though the biggest problem in the field either didn't exist or was basically unsolvable. In reality, there was only ever one significant problem in inductive programming - it's just that virtually nobody ever worked on it.

When we started Zoea, we strongly suspected that a solution does exist so we decided to address the problem head on. This meant we spent years devising and evaluating different heuristics before publishing a single result.

The first big breakthrough came with instruction subsets, which can reduce the size of the search space by up to 50 orders of magnitude. This doesn't make the problem 50 times smaller but rather 500 million, million, million, million, million, million, million, million times smaller. This was a huge improvement and it does allow larger programs to be produced but unfortunately it was still not nearly enough. To really overcome the combinatorial explosion we had to achieve a similar level of reduction again, on top of this.

That wasn't asking much. Despite being incredibly simple, no-one even came close to discovering instruction subsets in the entire history of computing. The odds of making another breakthrough of a similar magnitude were long, to say the least.

Instruction subsets inspired a number of related heuristics and the next two (instruction digrams and type signatures) managed to knock off another 100 million, between them. These were certainly useful results but not a game changer.

Our most recent heuristics are based on another very simple idea: in this case, measuring the probability of instructions in solutions. To do this, we take a very large sample of human code and literally count the number of times that each instruction occurs. We also count the total number of all instructions. This allows us to calculate a probability score for each instruction by dividing instruction count by the total. Probabilities are always between 0 and 1.

When we plot the instruction probabilities on a chart we get a Zipfian distribution - a few instructions are used frequently while most are hardly ever used. This is the same pattern you see for words in natural languages and for lots of other things, like patterns in whale songs, notes in music, the populations of cities, TV ratings, people's salaries, etc. - but nobody really knows why. This was the pattern we expected to see. So far so good.

Once we had the probabilities for each instruction we could also calculate a probability value for partial or complete solutions. To do this we simply multiply all of the instruction probabilities found in the solution, including duplicates. This still gives us a number between 0 and 1 but typically the probability for a solution is a lot smaller than the probability for a single instruction.

The big surprise here was that the probabilities for human code are much higher than the average we would expect, for random programs of the same length. This means that there are many strange, non-human-like programs that could exist, with large numbers of uncommon instructions and solution probabilities lower than any human code. It also means that we can avoid these completely, simply by using the lowest solution probability that we encountered in human code as a threshold - for each program size. In other words, solution probability has all the makings of a promising heuristic.

The approach was tested by measuring the actual size of the search space achieved using the probability thresholds, for each program size, and comparing these to the search space sizes obtained using instruction subsets. The results were also cross-validated by using part of the sample for 'training' (producing the probabilities and thresholds) and the rest for testing.

We were expecting instruction and solution probabilities to work well but were completely blown away by the results. The new heuristics also reduce the search space size by tens of orders of magnitude and this is in addition to what we achieve with instruction subsets. For example, with programs containing 40 instructions, we get another 30 orders of magnitude on top of the 50 orders of magnitude for instruction subsets. This gives an actual search space size of less than 10 billion, which might seem like a lot, but is actually peanuts for Zoea.

What's even more surprising is that the rate of search space size growth seems to flatten off with increasing program size. This means that for size 50 we should get a reduction of over 100 orders of magnitude - with even bigger numbers for larger programs. Also, the actual search space size looks like it will never get much larger than 10 billion, for even the biggest programs. This is nothing short of a complete solution to the combinatorial explosion problem for inductive programming. Full details can be found in our latest research paper on arxiv.org.

Search is an important technique in AI and in lots of other domains. However, any such use of search is often impacted by similar combinatorial problems. The fact that Zoea can totally overcome this problem in inductive programming, using simple and almost generic heuristics, strongly suggests that this work may have much broader applicability.

We still have other heuristics we would like to evaluate and we will probably be able to reduce some of these numbers still further. The thing is that now we no longer need to.