Uma única pergunta para acompanhar o progresso do o3 ao gpt-5.6 e além

Qual pode ser o comprimento do caminho de um fluxo gradiente em uma função convexa, dada a restrição de que ele permanece dentro da bola euclidiana unitária em dimensão n?

^ essa é a pergunta que venho usando há 2 anos para testar o progresso da IA. É incrivelmente simples de enunciar, mas terrivelmente difícil de resolver. Em 168 minutos de raciocínio, o GPT-5.6 conseguiu superar significativamente o estado da arte publicado sobre essa questão, de uma forma que nenhum outro modelo conseguiu até agora. Mas estou me adiantando, vamos primeiro pensar um pouco sobre a pergunta, revisar a literatura e depois discutir como foi o progresso do o3 para o GPT-5.6.

1. Estado da Arte

Ingenuamente, alguém poderia dizer: "bem, a descida do gradiente tem uma taxa de convergência que é independente da dimensão – é por isso que é empolgante usá-la para problemas com muitos parâmetros! – então, provavelmente, o comprimento de tal fluxo também deveria ser independente da dimensão?". Bem, às vezes, intuições ingênuas podem estar completamente erradas. Para começar: essas curvas são sequer retificáveis (ou seja, de comprimento finito, sem falar da dependência da dimensão)??? Isso nem é fácil de provar e, na verdade, é FALSO para a descida do gradiente acelerada de Nesterov (veja este artigo de @ErnestRyu, tudo feito com o GPT-5.5).

Ok, então o que se sabe exatamente sobre essa questão? Bem, existe um belo artigo de 1991 de Manselli e Pucci que mostra que tais curvas são de fato retificáveis e, além disso, seu comprimento é no máximo n^O(n). Sim, você leu corretamente, ainda pior que exponencial na dimensão, essa é a melhor cota de 35 anos atrás!! A propósito, este artigo também aponta que tais curvas são o que chamamos de "autocontraídas", ou seja, elas estão sempre se aproximando do seu futuro (pegue qualquer ponto na curva no tempo t, então dist(x(s), x(t)) é não crescente para s<t; veja a ilustração abaixo).

Agora, e quanto aos limites inferiores, ou seja, construir uma curva autocontraída realmente longa? Algo padrão a se observar na literatura de otimização convexa seria uma quadrática mal condicionada, algo como x_1^2 + cst_grande\x_2^2 + cst_ainda_maior\x_3^2 + ... O ponto é que a descida do gradiente primeiro irá quase em linha reta ao longo da direção com a maior constante, depois irá na direção da segunda maior constante, e assim por diante (veja a ilustração abaixo). Portanto, o comprimento total do caminho será aproximadamente n, e o caminho está contido no hipercubo, que está contido em uma bola de raio sqrt(n), então, por reescalonamento, obtemos uma curva autocontraída de comprimento sqrt(n).

É isso. Esse é o estado da arte publicado: limite superior de n^O(n) e limite inferior de sqrt(n). Que lacuna enorme para uma questão tão simples e natural!!!

Definição de uma curva autocontraída

Uma curva autocontraída de comprimento sqrt(n)

2. Trabalho não publicado por humanos

Pensei sobre essa questão há 8 anos com colaboradores incríveis: Omer Angel, Tomas Merchan Rodriguez e Fedja Nazarov. Conseguimos avançar bastante e estabelecemos que a resposta é de fato exponencial na dimensão!! Especificamente, tínhamos um limite inferior de sqrt(2)^n e um limite superior de 4^n. O artigo com essas estimativas está bem escrito e está na minha pasta do Dropbox há quase uma década, em parte porque sabíamos que esses limites poderiam ser melhorados ainda mais. E, de fato, Tomas e Fedja progrediram mais, primeiro elevando o limite inferior para 2^n e também melhorando o limite superior para 2.29...^n. Note que meu próprio entendimento do problema ficou no limite inferior ligeiramente melhor que sqrt(2)^n e no limite superior de 4^n (na verdade, eu tinha esquecido os 2^n e os 2.29^n até a IA começar a progredir nisso... mais abaixo).

3. Progresso da IA

O o3 foi o primeiro modelo de IA a sequer entender a questão. Sim, você leu essa frase corretamente. Talvez você tenha esquecido, mas há dois anos não estava claro se uma IA conseguiria ENTENDER perguntas tão enganosamente simples, muito menos resolvê-las. Em particular, o o3 conseguia ver que a questão era, na verdade, sobre curvas autocontraídas e sabia qual era o estado da arte nessa questão. Fiquei extremamente impressionado na época.

Mas então as coisas ficaram complicadas, e com a chegada da série de modelos GPT-5, usei essa questão como um conto de advertência: até fevereiro deste ano, eu a apresentava em palestras sobre o progresso dos LLMs em matemática como um exemplo de pergunta que NÃO se deve fazer aos LLMs. A razão é que o GPT-5 ou mesmo o GPT-5.2/5.4 TENTAVAM dar respostas complicadas, mas invariavelmente estavam errados em algum ponto, e perdia-se muito tempo verificando-as. Portanto, era um bom exemplo de que, para não perder tempo com LLMs em matemática, é preciso saber o nível certo de pergunta a fazer.

Isso mudou com o GPT-5.5 e, de repente, com muita ida e volta e prompting especializado, Mark Sellke conseguiu redescobrir a construção do limite inferior de 2^n (o que me CHOCU, em parte porque eu tinha esquecido que Tomer e Fedja já sabiam disso 😅). Por outro lado, nenhuma sorte no limite superior.

E agora chega o GPT-5.6, e o progresso da IA fica totalmente visível:

• O GPT-5.6-pro resolve o limite inferior de 2^n DE PRIMEIRA. Você pode ver a resolução aqui (80 minutos de raciocínio): https://chatgpt.com/s/t_6a50cb2a29488191b643ecb2426df87d
• O GPT-5.6-pro resolve o limite superior de 4^n DE PRIMEIRA, e, na verdade, faz isso muito rapidamente em sua Cadeia de Pensamento (CoT) e, ao final de seu raciocínio, produz um limite superior de 2.31...^n. Não chega a igualar os 2.29...^n de Fedja (e, na verdade, a estratégia de 2.31...^n não pode ser melhorada sem novas ideias – aliás, o próprio Fedja notou isso em uma publicação no MathOverflow em 2018: "[para 2.31..] o argumento fica um tanto confuso e fica claro que essa abordagem não levará à estimativa ideal"). Ainda assim, é muito impressionante e além do que eu pessoalmente entendia sobre o problema quando trabalhei seriamente nele. Você pode ver a resolução aqui, feita em 88 minutos de raciocínio: https://chatgpt.com/share/6a50764e-3eec-83ea-97e6-3d1f30c07b64

3. Um desafio para o futuro

Esta história ainda tem os humanos como vencedores. 2.29 para humanos contra 2.31 para máquinas. Naturalmente, a conjectura é que curvas autocontraídas não podem ser mais longas que 2^n (o que seria, então, a resposta ótima, dado o limite inferior de 2^n). Isso parece muito difícil de provar e está além das capacidades do GPT-5.6. Por quanto tempo conseguirei usar essa questão para acompanhar o progresso da IA? Suspeito que pode ser menos de 6 meses...

PS: Copiei e colei o post acima no ChatGPT e pedi para ele criar ilustrações. O conjunto de imagens aqui foi obtido de uma única tentativa a partir dessa consulta.