Filling in the convex hull

Nestor Guillen (like many, many others) wrote a blog post reflecting on recent progress in getting AI systems to prove results in pure mathematics: Happy those able to know the causes of things. It contains a nice analogy that may or may not be correct, which is also discussed with nicer pictures in another blog post reflecting on, etc., etc., by Álvaro Lozano-Robledo: What should we tell our students?.

Consider the entirety of truths of pure mathematics as some sort of geometrical space. The truths so far proved by humans form a subspace, presumably in some handwavy sense a nice compact one.

In many, many cases, proving a mathematical theorem is mostly a matter of combining clever ideas already had by other people. Actually carrying out the combination may still be difficult and/or impressive intellectual work, but any reasonable observer would say: well, the real contribution here is recognizing that you can combine the ideas of Smith, Jones and Ali so solve this problem. Guillen suggests that this is a bit like taking some points in that discovered-so-far subset of the space of mathematical truths, and adding a new point that's a convex combination of them: a point on the line joining them or the plane through them or whatever.

By repeatedly doing this you may arrive at a lot of new points, but there is a sense in which your progress will necessarily be limited: every point you can form in this way will, by definition, be part of the so-called convex hull of the set of points you started with, the set of all convex combinations of points in that set. You can think of the process as "filling in the holes". Here are a couple of illustrative images from Lozano's post:

Now, of course, what Guillen and Lozano are suggesting is that today's AI systems, even the best ones, are only "filling in the convex hull". They may possibly be suggesting that any plausible AI systems that work in basically the same way will also only ever be good at "filling in the convex hull". I think these are interesting hypotheses and worth thinking about some more. We could call the first the Weak Convex Hull Hypothesis and the second the Strong Convex Hull Hypothesis; in what follows I'll mostly be engaging in vague handwaving and will just talk about "the" Convex Hull Hypothesis.

Convex parrots

The CHH obviously somewhat resembles an earlier thing that people have said about LLMs, the Stochastic Parrot Hypothesis. (Wikipedia; the original paper by Gebru, Bender, McMillan-Major, and Mitchell.) Although one still hears people saying smugly that of course LLMs are just statistical text predictors that regurgitate a mashup of their input, I think this critique has become visibly less credible as today's AI systems have produced (among other things) proofs of mathematical theorems that hundreds of very gifted humans have laboured long and hard on but not been able to find. But the CHH version of this critique seems less blatantly at odds with reality, and it has some of the same implications as the SPH does.

Is the CHH true?

CHH seems kinda-plausible for two reasons. First, the thing at the core of today's AI systems really is a statistical token-predictor trained using a vast pile of human-written text. Second, it does seem like even the most impressive things these systems have done could reasonably be described as "filling in the convex hull". Third, it also seems like almost all human discovery/invention/creativity could also be described that way. (This last observation, if correct, makes CHH more plausible and simultaneously less damning.)

The first was pretty much also the argument for the SPH, which I consider thoroughly discredited by now. There are a couple of difficulties with its premises: LLMs are not purely trained on human-generated material any more (for instance, RLVR involves a large body of computer-generated training data, and RLVR is plausibly responsible for a lot of recent progress in LLM performance in software development and mathematics), nor is their training all about token-prediction (for instance, RLHF tries instead to train them to do things humans judge to be good, though I think much more of their training is token-prediction than anything like RLHF). And it's not so obvious that one can't build something with a really good token-predictor at its core that does genuinely new things. (Consider neural-network-based computer go players. They're trained to do something a bit like "predict the next move". But what's happening is that the neural network alone is being trained to predict what the neural net plus a load of tree-searching produces, and to whatever extent that works it produces something smarter than whatever you trained it on.) But, still, it feels like there's something to this argument. If you put vast effort into training something to reproduce its training data, you should expect what it does to at least rhyme with reproducing its training data.

The second is at least somewhat an empirical question, and actually I don't know for sure that it's true. But e.g. my understanding is that the Navier-Stokes proof, while very impressive and absolutely the sort of thing that would win a human mathematician the Fields Medal, is doing something that fits into a broad approach already laid down by human mathematicians. I would be very interested in the opinions of anyone who's looked deeply at the more impressive results in OpenAI's recent dump of hundreds of proofs.

The third is also somewhat an empirical question, and resolving it with real confidence would require examining everything ever created by humans. But I am fairly sure of the following things:

• It's commonly said that first-rate mathematicians, engineers, etc., typically have a small set of "tricks" they're extremely good at applying and at finding possible applications for, and their impressive output comes from repeated application of these.
• Advice on How To Be Creative often includes something along the lines of "try bringing disparate ideas together and see what comes out". (Arguably such advice is aimed at people who aren't very creative. On the other hand, I'm fairly sure at least some of it is obtained by looking at what actually-creative people do.)
• A lot of what's widely regarded as first-rate creative work doesn't involve going beyond the bounds of the sort of thing that's been done before. Bach's fugues and Beethoven's symphonies are wonderful pieces of music, they have plenty of good ideas in them, but people were writing fugues well before Bach and writing symphonies well before Beethoven (I think he was the first person to make the third movement have a scherzo rather than a minuet, but that hardly feels like Outside The Convex Hull).
• Things that feel like big advances often have smaller antecedents. Consider Einstein's special theory of relativity. This was a huge conceptual advance. Time as just one coordinate! Different notions of time for different observers! Time and space getting "mixed up" for observers travelling at different speeds! Well, yes, but also no. The idea of time as a fourth dimension had been around for decades, both in handwavy popular discourse and in actual mathematics. The equations describing how things get transformed at different speeds were due to Lorentz and Poincaré, though they weren't interpreted the way Einstein interpreted them. If we'd had AIs like today's back in the early 20th century and they'd got there before Einstein, I'm pretty sure today's critics would have had no hesitation about claiming that they were just remixing d'Alembert and Lagrange and Lorentz and Poincaré.

If it's true, does it matter?

Let me first of all make the obvious remark that in the doomiest scenarios we can imagine we have much worse problems than anything to do with stifling human creativity. So let's assume arguendo that those scenarios don't play out. (That's more likely if for some reason the AIs never get too much smarter than humans, so while making that assumption we should think that more likely than we otherwise would.)

We might reasonably worry about the following scenario:

• LLMs get incredibly good at filling in the convex hull.
• Creative humans generally get their start by finding good bits of convex hull to fill in.
• With LLMs doing this much more effectively than humans can, we have less motivation to do it ourselves, less opportunity to impress others by doing it or get paid for doing it, etc.
• Humans largely stop learning to be creative, and in particular much less often develop the ability to push beyond the convex hull.
• LLMs never get as good at extending the convex hull as humans were, and humans are doing it much less than they used to.
• The overall rate of expansion of knowledge and understanding decreases.

We might, a bit more disreputably, feel

• that if AI systems are only "filling in the convex hull" then we are still importantly superior to them, we have real creativity when they don't, there's still a need for us, yay humanity, boo AI; or
• that if AI systems are only "filling in the convex hull" then we have licence to be unimpressed by what they achieve; or
• that if AI systems are only "filling in the convex hull" then the real credit for what they do should go to the humans who provided the previous points they took a convex combination of, and the AI boosters who ask us to be impressed by the AIs are just trying to steal credit from those humans.

I'll deal with these first.

• There are certainly things we (or at least some of us) do better than today's AI systems. Humanity is not yet obsolete, whether or not it will be so one day. If you want to say "yay humanity" or "boo AI" about this, you should feel free to do so.
  • Of course we have no guarantee that this will remain true. Even if some highly abstract argument suggesting that nothing at all like today's AI systems will ever do more than filling in the convex hull, we already have good evidence that being very good at filling in the convex hull can achieve impressive things, and I would not want to bet that it can't in particular come up with better ways of building or training AI systems that make them more genuinely creative.
• You can be impressed or unimpressed by anything you want. The purpose of being impressed or not is (I guess) to adjust our expectations of whoever or whatever did the thing. If something shows its ability to prove mathematical theorems that top human mathematicians had trouble with, then I will expect it to go on being effective at doing that and other things sufficiently like it.
• When a human being puts together other human beings' ideas in an unexpected way and thereby achieves something no one had been able to do before, we typically give credit to the predecessors and to the innovator. I don't see any reason why we shouldn't have the same attitude to AI systems.

So, what about the nightmare scenario? I genuinely don't know. I think it depends on how much progress (of whatever sort we might care about) depends on "genuinely" new ideas that aren't "just" slightly perturbed convex combinations of existing ones. Which brings me to ...

A wrinkle: convex combinations plus noise

Slightly perturbed convex combinations, I just said. After all, when you bring someone else's ideas together to do something new, you are adding something. What happens to that repeated-convex-combinations model of (AI or human) progress if we allow for a bit of noise?

Here is a small set of starting points in 3d space, along with 10,000 points produced as follows: construct 100 random convex combinations of existing points on the convex hull of what we currently have, then add them to the set; repeat 100 times. Obviously this process never goes beyond the original convex hull.

Now suppose that when we construct each new point we add a bit of noise. Let's say spherically-symmetrical Gaussian noise, with standard deviation 1% of the length of the edges of that cube. Here's what we get:

The convex hull at the end of this process is now about 11% bigger in volume than the original convex hull. Make it 100k points rather than 10k and we get this:

That's 23% bigger than the original convex hull. I think the lopsidedness is a path-dependent thing: once you start getting more expansion on one side, more of the points on the convex hull are over there and you will keep sampling from them.

I took four points at a time for my convex combinations so that even without noise we could get points in the interior of the cube as well as on the outside. Using fewer means more of a tendency for new points to be on or near the convex hull, and hence more expansion. Here's what we get with 100k points, noise s.d. 1% of original side length, and taking just two at a time:

The scale is different here because the final convex hull is larger. This one is 3x the volume of the original.

Exactly how this process behaves depends on exactly how we select points to combine. If we do the same process that produced the last image, except that we pick points completely at random from the ones we have already, we get this, whose volume is only 9% higher than that of the original hull:

If we maintain a set of "particularly extreme" points in the convex hull, namely those furthest out in a somewhat-uniform set of 128 directions, and then mostly pick points from that set to combine two of, we get this, whose volume is about 6x that of the original convex hull.

I think it is obvious that any variant of this process will, if we give it long enough, end up filling all of space. (I don't claim that the same is true for the thing this is an analogy for.)

Tentative conclusion: if the filling-in-the-hull process introduces any novelty at all (which it seems hard to argue it can't, whether it's humans or LLMs doing it) then this process can in fact expand the bounds of knowledge beyond the original convex hull, perhaps by a lot. It seems pretty plausible to me that something like this is in fact the main way in which human knowledge and understanding have grown in convex-hull-expanding ways.

So, in particular, while the scenario laid out above would be bad for human creativity, and demoralizing, and arguably put too much power in the hands of whoever owns the best AIs, and so forth, I think it probably wouldn't put an end to the growth of knowledge and understanding.

1. You might prefer to replace "truths of pure mathematics" with something more concrete like "theorems of ZFC".
2. I definitely don't mean "compact" in the mathematical sense here, and in fact taking it that way would lead to another variation on the same analogy, but I think a less fruitful one.
3. "Concavities" might be a better word.
4. Picky mathematicians may notice that the thing drawn in the second image isn't actually the convex hull of the original blob, but I don't think that's deliberate -- though the difference has maybe a little connection with a point I'll be making later.
5. Actual idea-space is much higher-dimensional. One consequence of this (pointed out to me by Oscar Cunningham) is that if you start with something spiky and pass to its convex hull, the ratio of volumes of the two can plausibly be much larger in higher dimensions than in lower. (Though obviously it can be arbitrarily small in any dimension > 1.)
6. So that we don't end up with almost all our points clustered in the middle. This is somewhat representative of what actual scientists, engineers, artists, etc., do: the more excitingly innovative and creative something else is, the more it will get imitated and mined for ideas.