OpenAI заявила о более быстром преобразовании Фурье, критик называет его галактическим

Автор блога argmin разбирает один из результатов в большой пачке математических статей, которую OpenAI выложила, по его словам, «на прошлой неделе». В файле main.pdf утверждается, что получено более быстрое преобразование Фурье: логарифмический множитель в оценке числа операций, как пишет автор, чуть-чуть меньше, чем у стандартного быстрого преобразования Фурье (БПФ).

Для контекста автор напоминает, как устроено БПФ, придуманное Джеймсом Кули и Джоном Тьюки в 1965 году. Наивное вычисление преобразования длины n требует порядка n^2 арифметических операций. БПФ рекурсивно делит задачу пополам и укладывается менее чем в 5 n log2 n операций. При n = 1000 это выигрыш примерно в 20 раз (около 50 тысяч операций вместо миллиона), при n = 1 000 000, в 10 000 раз. Нижним разумным пределом автор называет n операций, поскольку результат нужно хотя бы записать; БПФ медленнее этого предела в 5·log2(n) раз, то есть примерно в 200 раз при n в триллион.

Само исследование автор, по его словам, не читал. Он «скормил» статью ChatGPT и провёл с чат-ботом сеанс поиска информации, спросив, что тот думает о собственном результате; заодно утверждает, что и в OpenAI статью никто не читал. Вывод: более быстрого БПФ, пригодного на практике, он не нашёл.

Главный довод, алгоритм «галактический». Этим термином Ричард Липтон и Кен Реган называют алгоритмы с немыслимо большими скрытыми константами. В нотации O-большое (big-O) асимптотика не различает n и 10^80 n, а 10^80, примерно число атомов в известной Вселенной. По оценке автора, константа C в результате OpenAI составляет порядка 10^100 при N = 10^12, так что даже при n = 10^100 классическое БПФ было бы быстрее примерно в 10^99 раз. Формально результат асимптотически быстрее, но выигрыш наступает лишь при невообразимо большом n.

Второй довод, модель вычислений. По описанию автора, она использует точную комплексную арифметику: числа с произвольной точностью, модули которых растут быстрее любого полинома от n, перемножаются за одну операцию. Если хранить такие числа в битах, память была бы экспоненциальной от длины входа; таких компьютеров не существует. Поэтому, даже если теорема в main.pdf верна («никто не знает, и мне всё равно»), она не решает исходную задачу, найти более быстрое БПФ на реальных машинах.

Автор напоминает, что ограничения на скорость БПФ известны давно. В 1973 году Жак Моргенштерн доказал: если коэффициенты в вычислении ограничены по модулю, быстрее ½ n log n преобразование Фурье не получить. Сорок лет спустя Нир Айлон показал, что быстрее n log n без сильной численной нестабильности не выйдет. Новый результат, по мнению автора, не прорыв, а курьёз того, что специалисты по информатике плохо формализуют свои проектные спецификации.

То же, по его словам, можно сказать и о других «больших» результатах пачки. Пример, галактический алгоритм умножения матриц за O(n^2.25) операций: конструкция в статье не позволяет даже оценить скрытую константу, и ни одним запросом автору не удалось заставить модель OpenAI назвать оценку C. Если бы статьи были написаны существенно лучше, считает автор, они попали бы на самые престижные конференции по теоретической информатике (STOC или FOCS), а статья про умножение матриц, вероятно, получила бы награды. Но, подчёркивает он, к реальным компьютерам всё это отношения не имеет: в теоретической информатике, по его оценке, не поощряется запуск алгоритмов, а ИИ лишь автоматизирует худшие привычки этой культуры.

Текст написан в язвительной авторской манере: это блог-мнение, а не нейтральная экспертиза, и автор прямо иронизирует над собственным методом проверки.

Ключевые факты

• OpenAI в пачке математических статей (файл main.pdf) заявила о более быстром преобразовании Фурье: логарифмический множитель, по описанию автора блога argmin, чуть меньше, чем у стандартного БПФ.
• Автор называет алгоритм галактическим: оценка константы C порядка 10^100 при N = 10^12, и даже при n = 10^100 классическое БПФ быстрее примерно в 10^99 раз.
• Модель вычислений предполагает точную комплексную арифметику с числами растущей величины за одну операцию, чего на реальных компьютерах нет.
• Давние границы известны: Моргенштерн (1973) показал нижнюю границу ½ n log n при ограниченных коэффициентах, Айлон, n log n без сильной численной нестабильности.
• Автор статью не читал, а расспросил о ней ChatGPT; сам разбор, язвительное мнение, а не независимая экспертиза доказательств.

Почему это важно

БПФ, один из базовых алгоритмов обработки сигналов, и заявление о его ускорении звучит громко. Разбор показывает, чем «теоретически быстрее» отличается от «быстрее на практике»: по описанию автора, результат асимптотически лучше классического БПФ, но выигрыш возможен только при невообразимо большом n и в модели, не похожей на реальные компьютеры. Это показательный пример того, как заявление о прорыве в большой публикации ИИ-компании нужно читать с учётом констант и модели вычислений.

Кому это важно

Инженерам и исследователям, работающим с обработкой сигналов и численными методами, чтобы понимать, что практический инструмент, судя по разбору, не изменился. Читателям, которые следят за математическими публикациями OpenAI, как пример критического прочтения. Преподавателям и студентам, как краткий ликбез по БПФ, нотации O-большое и понятию галактических алгоритмов.

Как это применить

Для практики из текста следует немногое: по оценке автора, более быстрого БПФ, которое можно запустить на реальной машине, в работе OpenAI нет, и вычислять преобразования по-прежнему стоит стандартными реализациями. Полезнее другое: перед тем как радоваться заявленному ускорению, смотрите на скрытую константу и на модель вычислений, допускает ли она операции, невозможные на настоящих компьютерах. Данных о цене, лицензии или готовой реализации в источнике нет.

Можно ли доверять

Это авторское мнение в личном блоге, написанное иронично. Автор в тексте не назван. Он прямо говорит, что саму статью не читал, а задавал вопросы ChatGPT, поэтому оценка константы и выводы о модели вычислений, его трактовка, а не независимая проверка доказательств. Показатели вроде 10^100 и 10^99 в исходном тексте переданы с утерянной вёрсткой степеней, и оценку константы автор даёт как приблизительную. Ответа OpenAI в материале нет, верна ли сама теорема, автор не знает. Исторические ссылки (Кули и Тьюки, Моргенштерн, Айлон, Липтон и Реган) в тексте приведены без деталей.

Риски и подводные камни

Не стоит считать, что заявление OpenAI опровергнуто: автор оспаривает практическую значимость и модель вычислений, а не доказывает ошибку в теореме, истинность результата он оставляет открытой. Не стоит и принимать резкие обобщения о теоретической информатике и ИИ-«мусоре» за установленные факты: это его оценка. Наконец, число 10^100, приблизительная оценка константы, а в материале не приведены сама формула заявленной границы и порог n, начиная с которого алгоритм становится быстрее.

«Этот новый результат OpenAI, скорее не математический прорыв, а курьёз того, что специалисты по информатике плохо формализуют свои проектные спецификации.»

— автор блога argmin