o3'ten gpt-5.6'ya ve ötesine ilerlemeyi takip etmek için tek bir soru

Bir gradyan akışının dışbükey bir fonksiyon üzerindeki yolu, birim Öklid topu içinde kalma kısıtıyla birlikte n boyutunda ne kadar uzun olabilir?

^ İşte bu, 2 yıldır AI'ın ilerlemesini test etmek için kullandığım soru. İfade etmesi ürkütücü derecede basit, ancak çözmesi bir o kadar da zor. 168 dakikalık düşünme süresinde, GPT-5.6 bu soruda yayınlanmış SOTA'yı (en son teknolojiyi) şimdiye kadar hiçbir modelin yapamadığı şekilde önemli ölçüde geçmeyi başardı. Ama kendimi kaptırıyorum, önce soru hakkında biraz düşünelim, literatürü gözden geçirelim ve ardından o3'ten gpt-5.6'ya olan ilerlemenin nasıl olduğunu tartışalım.

1. SOTA

Safça biri şöyle diyebilir: "gradyan inişinin boyuttan bağımsız bir yakınsama hızı vardır -bu yüzden birçok parametreli problemler için kullanılması heyecan vericidir!- yani muhtemelen böyle bir akışın uzunluğu da boyuttan bağımsız olmalı?" Eh, bazen saf yaklaşımlar tamamen yanlış olabilir. Başlangıç olarak: bu tür eğriler doğrultulabilir (yani, boyut bağımlılığını bir kenara bırakırsak, sonlu uzunlukta) mı??? Bunu kanıtlamak bile kolay değil ve aslında Nesterov'un hızlandırılmış gradyan inişi için YANLIŞ (bkz. bu makale, @ErnestRyu'ya ait, tamamı gpt-5.5 ile yapılmış).

Peki bu soru hakkında tam olarak ne biliniyor? Manselli ve Pucci'nin 1991 tarihli güzel bir makalesi var, bu tür eğrilerin gerçekten de doğrultulabilir olduğunu ve ayrıca uzunluklarının en fazla n^O(n) olduğunu gösteriyor. Evet, doğru okudunuz, boyutta üstel olmaktan bile daha kötü, bu 35 yıl öncesinin en iyi sınırı!! Bu arada bu makale, bu tür eğrilerin "kendini daraltan" (self-contracted) olarak adlandırıldığına da işaret ediyor, yani her zaman geleceklerine yaklaşıyorlar (eğri üzerinde t zamanında herhangi bir nokta alın, o zaman s<t için dist(x(s), x(t)) artmayandır; aşağıdaki resme bakın).

Peki ya alt sınırlar, yani gerçekten uzun bir kendini daraltan eğri oluşturmak? Dışbükey optimizasyon literatüründe bakılacak standart bir şey, kötü koşullandırılmış bir ikinci dereceden denklem olacaktır, x_1^2 + büyük_sbt\x_2^2 + daha_büyük_sbt\x_3^2 + ... gibi. Mesele şu ki, gradyan inişi önce en büyük_sbt'ye sahip yön boyunca neredeyse düz gidecek, sonra ikinci_en_büyük_sbt yönünde gidecek ve bu böyle devam edecek (aşağıdaki resme bakın). Yani yolun toplam uzunluğu kabaca n olacak ve yol, yarıçapı sqrt(n) olan bir topun içinde bulunan bir hiperküpün içinde yer alacak, bu yüzden yeniden ölçeklendirerek sqrt(n) uzunluğunda bir kendini daraltan eğri elde ederiz.

İşte bu kadar. Yayınlanmış SOTA bu: üst sınır n^O(n) ve alt sınır sqrt(n). Bu kadar basit ve doğal bir soru için oldukça büyük bir boşluk!!!

Bir kendini daraltan eğrinin tanımı

sqrt(n) uzunluğunda bir kendini daraltan eğri

2. İnsanlar tarafından yayınlanmamış çalışma

Bu soruyu 8 yıl önce harika işbirlikçilerim Omer Angel, Tomas Merchan Rodriguez ve Fedja Nazarov ile düşünmüştüm. Oldukça fazla ilerleme kaydetmeyi başardık ve cevabın gerçekten de boyutta üstel olduğunu belirledik!! Spesifik olarak, sqrt(2)^n'lik bir alt sınır ve 4^n'lik bir üst sınırımız vardı. Bu tahminleri içeren makale düzgün bir şekilde yazılmış ve neredeyse on yıldır dropbox klasörümde duruyor, kısmen bu sınırların daha da iyileştirilebileceğini bildiğimiz için. Ve gerçekten de Tomas ve Fedja daha fazla ilerleme kaydettiler, önce alt sınırı 2^n'ye yükselttiler ve ayrıca üst sınırı 2.29...^n'ye iyileştirdiler. Problemi kendi kavrayışımın, sqrt(2)^n'den biraz daha iyi bir alt sınır ve 4^n'lik bir üst sınır seviyesinde kaldığını belirteyim (aslında, AI bu konuda ilerleme kaydetmeye başlayana kadar 2^n ve 2.29^n'yi unutmuştum ... aşağıda daha fazlası).

3. AI ilerlemesi

o3, soruyu anlayan ilk AI modeliydi. Evet, bu cümleyi doğru okudunuz. Belki unuttunuz, ancak iki yıl önce bir AI'nın bu tür aldatıcı derecede basit soruları ANLAYABİLECEĞi, bırakın çözmeyi, net bile değildi. Özellikle o3, sorunun aslında kendini daraltan eğrilerle ilgili olduğunu görebiliyor ve bu soruda SOTA'nın ne olduğunu biliyordu. O zamanlar çok ama çok etkilenmiştim.

Ama sonra işler karmaşıklaştı ve GPT-5 serisi modellerin gelişiyle bu soruyu bir uyarı hikayesi olarak kullandım: bu yılın Şubat ayına kadar, LLM'lerin matematikteki ilerlemesi üzerine yaptığım konuşmalarda bu soruyu LLM'lere SORMAMANIZ gereken bir soru örneği olarak verirdim. Nedeni, GPT-5 ve hatta GPT-5.2/5.4'ün karmaşık cevaplar VERMEYE çalışması, ancak bunların bir yerinde her zaman yanlışlık olması ve bunları kontrol etmek için çok zaman harcanmasıydı. Bu yüzden, LLM'lerle matematikte zaman kaybetmemek için sorulacak doğru seviyede soruyu bilmek gerektiğine dair iyi bir örnekti.

Bu durum GPT-5.5 ile değişti ve birdenbire, çok sayıda gidiş geliş ve uzman yönlendirmesiyle Mark Sellke, 2^n alt sınır yapısını yeniden keşfetmeyi başardı (ki bu beni ŞAŞIRTTI, kısmen Tomer ve Fedja'nın bunu zaten bildiğini unutmuştum 😅). Öte yandan, üst sınır konusunda hiç şans yoktu.

Ve şimdi GPT-5.6 geliyor ve AI'nın ilerlemesi tam anlamıyla görünür hale geliyor:

• GPT-5.6-pro, 2^n alt sınırını TEK SEFERDE çözüyor. Tek seferlik çözümü burada görebilirsiniz (80 dakikalık düşünme): https://chatgpt.com/s/t_6a50cb2a29488191b643ecb2426df87d
• GPT-5.6-pro, 4^n üst sınırını TEK SEFERDE çözüyor ve aslında bunu Düşünce Zincirinde (CoT) çok hızlı bir şekilde yapıyor ve düşünmesinin sonunda 2.31...^n'lik bir üst sınır üretiyor. Fedja'nın 2.29...^n'sine tam olarak yetişemiyor (ve aslında 2.31...^n stratejisi yeni fikirler olmadan daha fazla iyileştirilemez - aslında Fedja'nın kendisi 2018'deki bir MathOverflow gönderisinde şunu belirtmişti: "[2.31.. için] argüman biraz dağınıklaşıyor ve bu yolun en uygun tahmine götürmeyeceği açık"). Yine de oldukça etkileyici ve sorun üzerinde ciddi olarak çalıştığım dönemde kişisel olarak anladığımın ötesinde. Tek seferlik çözümü burada görebilirsiniz, 88 dakikalık düşünme ile tamamlandı: https://chatgpt.com/share/6a50764e-3eec-83ea-97e6-3d1f30c07b64

3. Gelecek için bir meydan okuma

Bu hikaye şu anda hala insanları kazanan olarak görüyor. İnsanlar için 2.29'a karşı makineler için 2.31. Doğal olarak, varsayım, kendini daraltan eğrilerin 2^n'den daha uzun olamayacağı yönünde (ki bu, 2^n alt sınırı göz önüne alındığında en uygun cevap olacaktır). Bunu kanıtlamak çok zor görünüyor ve GPT-5.6'nın yeteneklerinin ötesinde. AI'nın ilerlemesini takip etmek için bu soruyu daha ne kadar kullanabileceğim? 6 aydan daha az olabileceğinden şüpheleniyorum ...

Not: Yukarıdaki yazıyı ChatGPT'ye kopyalayıp yapıştırdım ve bunun için illüstrasyonlar hazırlamasını istedim. Buradaki resim koleksiyonu, bu sorgudan tek seferde elde edildi.