OpenAI가 주장한 더 빠른 푸리에 변환은 실용 컴퓨터에서 작동하지 않는다

OpenAI가 최근 대량으로 쏟아낸 수학 논문 묶음 가운데 'main.pdf'라는 문서가 기존 고속 푸리에 변환(FFT)보다 점근적으로 빠른 알고리즘을 제시한다고 주장해 화제가 됐다. 위스콘신대 매디슨의 벤 레히트는 자신의 블로그 arg min에서 이 주장을 들여다본 결과, 수학적 돌파구라기보다 형식주의가 현실과 분리되면서 만들어진 인공물에 가깝다고 평가했다.

푸리에 변환은 신호에 어떤 주파수 성분이 얼마나 섞여 있는지 계산하는 도구다. 길이 n인 입력에서 각 주파수마다 내적을 하나씩 계산하는 단순한 방식은 n²번의 연산을 요구한다. 1965년 제임스 쿨리와 존 튜키가 정리한 FFT는 입력을 절반씩 쪼개 재귀적으로 처리하는 방식으로 이 비용을 5n·log₂n 수준까지 떨어뜨린다. n이 1000일 때 단순 계산은 100만 번, FFT는 약 5만 번으로 20배 차이가 나고, n이 100만이면 격차는 1만 배로 벌어진다.

OpenAI 쪽 주장의 핵심은 log n 항의 계수를 줄여 점근적 복잡도를 한 단계 낮췄다는 것이다. 문제는 그 대가로 숨은 상수가 감당할 수 없는 크기가 됐다는 점이다. 레히트가 인용한 추정에 따르면 n이 10¹²일 때 상수 C는 10¹⁰⁰ 수준이며, 이 때문에 n이 10¹⁰⁰에 이르러도 기존 쿨리-튜키 FFT가 10⁹⁹배 더 빠르다.

이런 알고리즘은 리처드 립턴과 켄 리건이 '은하급 알고리즘'이라 부른 부류에 속한다. 빅오 표기에서 O(n)은 50n을 뜻할 수도 있지만 10⁸⁰n을 뜻할 수도 있다. 점근적 가능성을 보여줬다는 이유로 후속 연구를 자극한다는 옹호론도 있지만, 그런 이론이 실용 알고리즘으로 이어진 사례는 저자가 아는 한 없다.

더 빠른 FFT를 찾으려는 시도 자체는 오래됐다. 1973년 자크 모르겐슈테른은 계수의 크기가 제한된 모델에서 n log n의 절반보다 빠른 변환이 불가능하다는 하한을 증명했고, 40여 년 뒤 니르 아일론은 심각한 수치 불안정성을 감수하지 않고서는 n log n보다 빠를 수 없다는 결과를 내놨다. 이번 결과는 그 한계를 계산 모델 자체를 바꿔 우회한 셈이다.

OpenAI 알고리즘은 임의 정밀도의 복소수를 한 번의 연산으로 곱할 수 있다고 가정한다. 게다가 곱하는 복소수의 크기가 n에 대해 초다항식으로 커지기 때문에, 이를 비트로 저장하면 메모리 요구량이 입력 길이에 대해 사실상 지수적으로 늘어난다. 우리가 실제로 쓰는 컴퓨터에는 그런 연산이 없다.

실무 관점에서 이 소식이 바꾸는 것은 없다. 오디오, 통신, 이미지 처리 파이프라인에서 쓰는 FFT는 여전히 쿨리-튜키 계열이고, 검증된 라이브러리 구현을 교체할 이유도 없다. 오히려 얻을 교훈은 논문의 점근 표기만 보고 성능 개선으로 받아들이지 말라는 것이다. 상수 크기와 계산 모델, 수치 안정성까지 확인해야 실제 워크로드에 적용할 수 있다.

레히트는 이 논문을 직접 읽지 않았고, 원문을 챗봇에 다시 넣어 요점을 추출하는 방식으로 검토했다고 스스로 밝혔다. 따라서 정리 자체의 진위는 별도로 검증되지 않았으며, 그가 지적한 핵심은 증명의 참·거짓이 아니라 주장이 풀려는 문제와 실제 컴퓨터 사이의 괴리다.