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 O⁢(n⁢min⁡{d,α}).

Let’s see how ChatGPT 4o (May 2024) does:

GPT-4o: the circle graph MIS question, opening answer, and citation.
Figure 1: This is me asking GPT-4o, some years ago. It knows about my algorithm! However, it hallucinates a hilarious reference for it that doesn’t exist. It also gave absolute garbage if I asked how the algorithm worked.

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:

GPT-4.5: the question, opening attribution, and complexity claims.
Figure 2: GPT-4.5 seems to just not know about my algorithm, how galling. It correctly mentions Valiente’s algorithm (which isn’t a hallucination!), but gives a slightly sloppy time complexity.

Let’s try ChatGPT 4.1, which was released in April 2025 (yes, weirdly after ChatGPT 4.1):

GPT-4.1: the question and first paragraph of its answer.
Figure 3: Hilariously, GPT-4.1 gives a nonsense time complexity, hallucinated references, and highly insultingly, doesn’t mention my algorithm at all!

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:

o3: the question and the enlarged year, authors, and running-time columns of its algorithm comparison table through the 2010 result.
Figure 4: OK, so GPT-o3 gives a detailed, correct answer. Wow. EXCEPT, it still hallucinates an extra author on my paper. I have published a different paper with Lelait, but he was not a co-author on this paper. Still not perfect, tysk tysk.

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:

GPT-5 Thinking: the question, output-sensitive bound and definitions, and weighted comparison.
Figure 5: GPT-5 Thinking answers perfectly. It distinguishes variants, gives explains time complexities correctly. Cool.

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:

GPT-5.6 Sol excerpt combining its bound with Nash-Gregg and giving a balanced-regime example with n to the five-fourths time instead of n to the three-halves.

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:

Astra 6.2 theorem combining output-sensitive, arboricity-sensitive, and three-gap algorithms, followed by a corollary describing truly subquadratic regimes.

What a time, and what a funny time to write this, on Riemann Hypothesis day.