From the Gutter, Ad Astra
Abstract
I used to use a single question I was an expert in to evaluate each new ChatGPT release for myself. I’ve done this since ChatGPT was just a textbox you had to manually “refresh”. The results used to be comically bad. Then, the results were good, and I painstakingly wrote them up, in this paper. Now, with Astra 6.2, I feel a bit defeated, it pushes far past all the ideas I had. Luckily I kept screen-shots of ChatGPT answering questions about it over the years, so I can share them in this post. It is quite amazing.
1 My Claim To Fame
There is a fairly natural algorithmic question, with many applications (e.g. to speak a bit vaguely: in RNA analysis, compiler optimization, chip-routing, and more), which amounts to finding the largest collection of mututally non-intersecting chords drawn in a circle. Like so:
This problem is usually called finding a maximum independent set in a circle graph. I know this problem well, and indeed, to this day, the best algorithm known to humanity was published by me. Wow, eh?
2 The Hallucination Era, May 2024 - August 2025
Let’s take a look at how various ChatGPT models used to respond to answer when I asked them about this algorithm. All you need to remember is:
-
•
The best known algorithm is due to Nash and Gregg.
-
•
Its time complexity is .
Let’s see how ChatGPT 4o (May 2024) does:
OK, so ChatGPT 4o is pretty terrible. Let’s fast forward a bit to February 2025, and see what ChatGPT 4.5 used to say next:
Let’s try ChatGPT 4.1, which was released in April 2025 (yes, weirdly after ChatGPT 4.1):
OK, and now I still remember the next jump in capabilities. Let’s fast forward a full two-days in April 2025, and ChatGPT o3:
3 The End of Hallucination, August 2025
Let’s jump forward 3 months. It was about this time that ChatGPT stopped hallucinating about my pet algorithm. Here’s GPT 5 in August 2025:
Of course, this isn’t the end of our exciting story. Enter Sol.
4 The Beginning of Abundance, July 2026
In July 2026, GPT 5.6 Sol arrived. Here it is casually devising a new algorithm beating the state-of-the-art:
It also casually proved conditional lower-bounds on the problem. But I digress.
5 Ad Astra, November 2026
Well, now if I ask Astra 6.2, it can spit out all sorts of natural variations, and better algorithms:
What a time, and what a funny time to write this, on Riemann Hypothesis day.