phillip_kerger

I (author of the paper) can't speak for others, but I have no affiliation whatsoever with OpenAI and have not received anything from them (I even pay for my subscription lol). I've thrown this problem at each model with new model releases, and 5.6 was the first one to solve it, so that's my side of that story.

clear specifications for what counts as completing the tasks, and an explicit list of what does not count as completing the task, and clearly stating to not return until the task has been completed. I've had agents run for almost 12h!

I (author of the original post and paper) can add a few things here: 1. My previous approaches with GPT 5.5 were really not very sophisticated in terms of my input. I threw the problem at it, and just kept encouraging it to go iterate through ideas without any success. 2. The approaches that are in the prompt, though they will seem cryptic to someone not in the field, are relatively natural ideas. In fact, the construction that worked was something that even 5.5 initially looked at but was just too weak to see how to make it work. From my view, I would have never gotten this result myself. Imagine you are telling a contractor to build the empire state building, and you say: "You should explore approaches that can include building materials like steel, wood, concrete, or clay, and any combinations of those. You can use arcs, columns, supportive beams, and anything else you can think of to solve load-bearing issues. Do not stop until you've completed a viable plan to construct the empire state building." And then the contractor shows you the finished empire state building using reinforced concrete and steel beams with all kinds of crazy ways of making everything stable; that's kinda how I feel.

I would agree with your take. I (author of the post & paper) learned a ton from working on small parts of problems my PhD advisor was doing a lot of the heavy lifting on, and later also from getting some results that were essentially putting together the right pieces that already existed followed by some deep-in-the-weeds analysis.

Yes, order d is the minimal number of evaluations of gradients needed for the same problem! That has actually been known since 1979 (Nemirovsky and Yudin showed that), and there are methods with the same complexity so this question in the gradient model has been solved for a long time. "because you can approximate a gradient with d function evaluations" was exactly why d^2 made sense as a lower bound for this case! Basically, the lower bound question can also be thought about as "can you do better than approxing a gradient?", so this result says no.