OpenAI의 '더 빠른 FFT' 주장, 알고 보니 비현실적 계산 모델의 산물

Who Should Read

AI가 쏟아내는 수학·알고리즘 '돌파구' 주장을 어디까지 믿어야 할지 가늠하고 싶은 백엔드 개발자

Core Mechanics

• FFT는 n²를 5n log n으로 줄였다
  • 1965년 Cooley와 Tukey가 만든 재귀 방식이다.
  • n이 1,000이면 약 20배, n이 100만이면 약 10,000배 빠르다.
• OpenAI 알고리즘은 상수가 은하급이다
  • 추정된 상수 C는 N=10^12일 때 10^100이다.
  • n=10^100이어도 기존 FFT가 10^99배 빠르다고 저자는 쓴다.
• big-O 표기는 상수를 모두 같게 본다
  • O(n)이라도 숨은 상수가 10^80일 수 있다.
  • 그래서 점근적으로 빠르다는 말이 실제로 빠르다는 뜻은 아니다.
• 계산 모델이 실제 컴퓨터와 다르다
  • 이 모델은 복소수를 임의 정밀도로 저장하고 한 번의 연산으로 곱한다고 가정한다.
  • 알고리즘이 쓰는 복소수의 크기는 n에 대해 superpolynomial(다항식보다 빠르게)로 커진다.
• 제약을 걸면 FFT 한계는 이미 증명돼 있다
  • 1973년 Morgenstern은 계수 크기를 제한하면 ½ n log n보다 빠를 수 없음을 증명했다.
  • Nir Ailon은 수치 불안정 없이는 n log n보다 빠를 수 없음을 보였다.

Community Reactions

• 이론 연구를 깎아내렸다는 반론
  • STOC/FOCS는 실용 알고리즘 학회가 아니며 상수가 있는 한 터무니없이 커도 괜찮다는 의견이 있었다.
  • median of medians나 2019년 Harvey–van der Hoeven 곱셈도 쓰이지 않는 은하급이라는 지적이 있었다.
• 저자 비판이 AI와 무관하다는 의견
  • AI를 빼도 같은 결론이 나오는 글이고 저자가 이론 전산학을 싫어할 뿐이라는 의견이 있었다.
  • 이 글은 논문 자체가 아니라 분야 전체를 비판한다는 댓글도 있었다.
• 실용 알고리즘과 은하급 알고리즘은 구분된다는 설명
  • 이론 전산학도 Karatsuba나 Strassen처럼 실제 속도 향상이 있는 feasible 알고리즘과 은하급을 나눠 본다는 댓글이 있었다.
• 작동 원리를 풀어 본 댓글
  • DFT 작업 일부를 곱셈으로 옮기고 정확 산술 모델에서 곱셈을 O(1)로 치는 해킹이라는 해석이 나왔다.
  • 커지는 숫자에 일을 몰아넣어 오라클처럼 쓴다는 설명이다.

How to Apply

• AI가 낸 복잡도 주장은 모델부터 확인하기
  • 오늘 받은 알고리즘 주장에서 연산 비용 가정(정밀도, 숫자 크기)을 먼저 찾아 적어라.
  • 한 번에 곱하는 수가 n에 따라 커지는지 확인하라.
• big-O 옆에 실측 벤치마크 요구하기
  • 성능 개선 PR에는 실제 n 범위에서 측정한 시간을 붙이게 하라.
  • 숨은 상수가 보이지 않으면 점근 표기만으로 채택하지 마라.
• AI 생성 결과는 다른 AI에게 되물어 검증하기
  • 논문이나 증명을 받으면 LLM에게 가정, 상수, 실제 구현 가능성을 뽑게 하라.
  • 그 답은 초안으로만 쓰고 사람이 핵심 가정을 직접 확인하라.

Try It

# Claude나 ChatGPT에 그대로 붙여넣기 (원문 비판 방법의 간이 버전)

아래 알고리즘/논문 주장을 실무 개발자 관점에서 점검해 줘.

{{논문 요약 또는 주장}}

다음 항목으로 답해 줘.
1. 주장하는 복잡도와 big-O 안에 숨은 상수가 있는지, 있다면 크기
2. 점근적 이점이 생기려면 n이 얼마나 커야 하는지
3. 계산 모델의 가정 (숫자 정밀도, 한 번에 곱하는 수의 크기, 정확 산술 여부)
4. 그 가정이 실제 컴퓨터에서 성립하는지
5. 실제 구현·벤치마크가 있는지

모르는 값은 추측하지 말고 '논문에 없음'이라고 써 줘.

이어서 해 볼 것: 같은 질문을 지금 쓰는 라이브러리의 성능 주장에도 던져 보기

Terminology

관련 논문

• The Judge Can Debias Itself: LLM-as-a-Judge가 스스로 편향을 고치게 하는 법

  심사 프롬프트에 편향 경고를 넣거나 스스로 비판시켰더니 21개 중 20개 조합에서 정확도가 올랐다

• 미국 노동시간의 90%는 AI 벤치마크가 제대로 다루지 못하는 일이다

  벤치마크 29개를 직업 과제에 매핑했더니 노동시간 90%가 커버 밖

• Postgres 19, AI 코드 리뷰가 버그를 너무 많이 찾아 출시 연기

  LLM 코드 리뷰가 버그를 쏟아내 Postgres 19가 11월로 밀리고 기능 8~10개가 빠졌다

• StarSkirmish Bench v0.2: LLM이 1시간 만에 짜는 StarCraft 봇 대결

  LLM에게 1시간 동안 StarCraft 봇을 짜게 했더니 GPT-6 Astra가 1위

• 그럴듯한 설명 하나면 멀티모달 LLM 심사위원도 속는다 (JUPE 벤치마크)

  정답은 그대로 두고 설명만 붙였더니 MLLM 심사위원의 오답 거절률이 12.7~13.8%p 떨어졌다

• 신경망은 이미 깔끔하다: polysemanticity의 원인 재해석

  뉴런을 직접 들여다봤더니 대부분 한 가지 역할이 있었다는 주장

• Linus Torvalds의 첫 LLM 보조 패치 시리즈

  Linus가 LLM으로 folio 조회 패치 10개를 만들어 read() 벤치가 10배 빨라졌다

Related Resources

• https://www.argmin.net/p/faster-fourier-transforms
• https://github.com/CrocSwap/integer-mult-bounds
• https://news.ycombinator.com/item?id=49994145
• https://youtu.be/2Op3QLzMgSY?t=30