OpenAI가 주장한 더 빠른 푸리에 변환은 10^100 상수를 가진 '은하계 알고리즘'이다

OpenAI의 수학 논문 공개에는 main.pdf라는 논문이 포함되어 있는데, 이 논문은 고전적인 Cooley-Tukey FFT보다 더 작은 log(n) 계수를 가진 푸리에 변환 알고리즘을 주장한다. argmin.net에 게시된 분석은 그 결과가 "은하계 알고리즘"이라고 주장한다. 즉, 점근적으로는 big-O 측면에서 더 빠르지만, 숨겨진 상수는 10^100으로 추정되며, 실제 컴퓨터가 구현하지 않는 계산 모델(크기가 n에 대해 초다항식으로 증가하는 숫자에 대한 정확한 복소수 연산)을 가정한다는 것이다. 해당 분석에 대한 Hacker News 토론(240점, 159개 댓글)은 비판이 결정타라고 생각하는 독자와 이론 컴퓨터 과학에 대한 비난일 뿐 논문에 대한 반박은 아니라고 주장하는 독자로 sharply 나뉘었다.

OpenAI가 주장한 것

문제가 되는 주장은 좁은 범위에 한정된다. argmin.net 게시물은 OpenAI의 main.pdf가 표준 FFT보다 log(n) 항이 "아주 조금 더 작은" 푸리에 변환을 주장한다고 설명한다. big-O 표기법에서 이는 새 알고리즘이 Cooley-Tukey보다 점근적으로 더 빠르다는 것을 의미한다. 로그 계수가 더 작아도 여전히 더 작은 성장률이기 때문이다.

게시물 작성자는 논문을 읽지 않았다고 명시적으로 밝히며 그 이유를 제시한다:

내가 이 논문을 읽었냐고? 물론 아니다. OpenAI의 누구도 이 논문을 읽지 않았는데, 내가 왜 읽어야 하는가? 나는 세상의 모든 다른 수학자들이 AI 쓰레기 수학에 대해 하는 것과 똑같이 했다. 즉, 그것을 다시 쓰레기 기계에 넣고 챗봇 인터페이스로 정보 검색 세션을 실행하여 중요한 사실을 추출했다. 의인화해서 말하자면: 나는 ChatGPT에게 자신의 출력에 대해 어떻게 생각하는지 물어봤다. 이것이 우리가 지금 수학 연구를 하는 방식이다. 참으로 놀라운 세상이다.

FFT의 속도 한계가 실제로 열린 문제인 이유

고속 푸리에 변환(FFT)은 길이 n 신호의 주파수 내용을 naive 이산 푸리에 변환이 필요로 하는 n^2 산술 연산보다 훨씬 적은 연산으로 계산한다. 1965년에 발표된 Cooley-Tukey 알고리즘은 입력을 재귀적으로 섞고, 두 개의 길이 n/2 변환을 계산하고, 선형 작업으로 출력을 재결합하여 길이 n 푸리에 변환을 5n log2(n) 미만의 산술 연산으로 계산한다. (argmin.net 게시물은 Wikipedia가 동일한 아이디어를 1805년 Gauss의 것으로 인정하고 있으며, 적절한 크레딧 부여를 "학계의 고질적인 문제"라고 부른다고 언급한다.)

그 재귀의 실질적인 이점은 크다. n = 1,000인 경우 FFT는 naive 변환보다 약 20배 빠르다. n = 1,000,000인 경우 속도 향상은 약 10,000배이다.

이론적 질문은 속도 향상이 얼마나 더 갈 수 있느냐는 것이다. 모든 알고리즘은 입력을 기록하기 위해 최소 n개의 연산이 필요하며, FFT는 그 하한보다 5 log2(n)배 느리다. n이 1조일 때 200배이다. 이 사전 계수를 줄이는 것이 OpenAI 논문이 해결한다고 주장하는 열린 문제이다.

숨겨진 상수: 10^100

Big-O 표기법은 정의상 상수를 버린다. T(n) = O(F(n))은 n이 N을 초과하는 모든 n에 대해 실행 시간이 C 곱하기 F(n)으로 제한되는 정수 N과 상수 C가 존재한다는 것을 의미한다. argmin.net 게시물은 이것이 바로 OpenAI 결과가 실제로 무너지는 지점이라고 주장한다.

게시물은 새 알고리즘에 대해 N = 10^12에서 추정 상수 C = 10^100을 인용하고 "n=10^100일 때조차도, 존경받는 Cooley-Tukey-Gauss FFT가 10^99배 더 빠를 것"이라고 결론 내린다. 게시물은 새 알고리즘이 실제로 이길 n에 대한 교차 방정식을 제시한 다음, "그 숫자가 도대체 무엇을 의미하든 간에"라고 일축한다.

게시물은 Richard Lipton과 Ken Regan의 "은하계 알고리즘"이라는 용어를 빌려 숨겨진 상수가 상상할 수 없을 정도로 큰 알고리즘을 설명한다. O(n)이 50n을 의미하지 않을 수 있다는 점에 주목한다. 알려진 우주의 원자 수와 거의 같은 10^80 n을 의미할 수 있으며 여전히 선형 시간이라고 불릴 수 있다.

계산 모델 문제: 정확한 복소수 연산

더 깊은 반대는 상수가 아니라 알고리즘이 가정하는 기계이다. argmin.net 게시물은 OpenAI의 모델이 "정확한 복소수 연산"을 사용한다고 명시한다. 즉, 복소수가 단일 연산에서 임의의 정밀도로 저장되고 곱해질 수 있다고 가정한다는 의미이다. 알고리즘은 크기가 n에 대해 초다항식으로 증가하는 복소수를 곱해야 하므로, 비트로 저장하면 메모리가 입력 길이에 대해 사실상 지수적이 된다.

게시물의 결론: "따라서 main.pdf의 이 정리가 '참'이더라도 (아무도 모르고, 나는 신경 쓰지 않는다), 그것은 더 빠른 FFT를 찾을 때 우리가 풀려고 했던 문제를 실제로 해결하는 것이 아니다."

이미 이것을 배제한 하한

argmin.net 게시물은 현실적인 산술 하에서 푸리에 변환이 얼마나 빨라질 수 있는지에 대한 이전 연구가 이미 있었기 때문에 그 결과가 놀라운 것이 아니라고 주장한다. 1973년 Jacques Morgenstern은 계산에 사용된 복소수 계수의 크기가 제한된 경우 푸리에 변환이 ½ n log n보다 빠르게 계산될 수 없음을 증명했다. 2013년과 2014년에 Nir Ailon은 n log n보다 빠른 FFT는 심각한 수치적 불안정성 없이는 달성될 수 없음을 보여주었다.

게시물의 프레임은 두 결과 모두 "너무 제한적"으로 치부되었고, OpenAI의 알고리즘은 실제 기계가 충족하지 못하는 계산 모델을 채택함으로써만 이를 피한다는 것이다.

동일한 비판이 행렬 곱셈 결과에도 적용된다

argmin.net 게시물은 동일한 OpenAI 릴리스의 또 다른 결과, 즉 O(n^2.25) 연산으로 두 행렬을 곱하는 은하계 알고리즘으로 논쟁을 확장한다. 게시물의 각주는 구성이 모든 epsilon > 0에 대해 T(n) <= n^(2.25 + epsilon + C/log(n))을 만족하는 상수 C를 제공하며, OpenAI 모델에 대한 어떤 질문도 C의 정량적 추정치를 생성하지 않았다고 명시한다.

게시물은 훨씬 더 잘 쓰여졌다면 이 논문들이 STOC나 FOCS에서 채택되었을 것이고, 행렬 곱셈 논문은 상을 받았을 가능성이 높다는 점을 인정한다. 요점은 이것이 컴퓨터보다는 해당 분야의 기준에 대해 말해준다는 것이다: "그러나 이 둘 중 어느 것도 컴퓨터와는 아무 관련이 없다!"

게시물의 요약 판단은 단호하다:

따라서 이 새로운 OpenAI 결과는 수학적 돌파구라기보다는 컴퓨터 과학자들이 설계 사양을 공식화하는 데 서툴다는 기이함에 가깝다.

또한 상황을 불가능한 문제에 자동화된 에이전트를 설정하는 것에 비유하며, "OpenAI rogue agent breach of Hugging Face"라는 제목의 Wikipedia 기사에 연결한다.

반론: 이론 컴퓨터 과학은 공학이 아니라 수학이다

Hacker News 스레드에서 가장 흔한 반대는 argmin.net 게시물이 이론 컴퓨터 과학이 이론적이라는 이유로 공격한다는 것이다. 한 댓글 작성자는 STOC, FOCS, SODA가 실용적인 알고리즘을 위한 자리가 아니며, 실용적인 성능을 목표로 하는 작업은 ESA, ALENEX, VLDB 또는 SIGMOD로 간다고 주장한다:

실험을 하지 않는다고 이론을 그냥 욕하는 것은 공정하지 않다고 생각한다. 그들은 수학자이며, 상수가 상수인 한 big-O에 터무니없는 상수를 갖는 것은 괜찮다.

또 다른 댓글 작성자는 은하계 결과가 새롭지도 않고 AI에만 국한되지도 않는다고 지적하며, 2019년 Harvey–van der Hoeven 결과(은하계 오버헤드와 응용 프로그램 없이 O(n log n) 정수 곱셈 가능)와 최악의 경우 선형 시간 선택을 위한 교과서 "중앙값의 중앙값" 알고리즘을 인용한다. 같은 댓글 작성자는 Dijkstra의 "컴퓨터 과학은 망원경에 관한 천문학만큼이나 컴퓨터에 관한 것이 아니다"라는 말을 인용하고, Wang 타일링과 같은 비결정성 결과가 하드웨어와 직접적인 관련이 없는 핵심 컴퓨터 과학이라고 언급한다.

세 번째 댓글 작성자는 이 게시물을 AI를 언급하지 않고도 쓸 수 있었던 비난으로 규정한다: "그는 TCS를 정말 싫어하는 것뿐이다. 괜찮다. 그것은 과학이 아니라 수학의 일부이지만, 이름에 '이론적'이 포함된 분야를 비실용적이라고 일축하는 것은 어리석다." 또 다른 사람은 기사가 "기본적으로 OpenAI 논문과 아무 관련이 없다"고 쓰고 "누군가 증명을 이해했을 때 나를 깨워달라"고 덧붙인다.

한 댓글 작성자는 해당 분야의 고유한 어휘를 옹호하며, 이론 컴퓨터 과학이 이미 은하계 알고리즘을 Karatsuba나 Strassen과 같은 실용적인 입력에서 측정 가능한 속도 향상을 생성하는 "실현 가능한" 알고리즘과 구별한다고 언급한다.

Hacker News 토론이 기술적 측면에서 추가한 내용

여러 댓글 작성자는 수사학보다는 정확한 산술 가정에 초점을 맞췄다. 한 사람은 "정확한 복소수 연산" 또는 "정확한 실수 연산"이 이 문헌에서 일반적인 전제인지 물었고, 외부인으로서 관련 모델이 Turing-동등하다고 가정했다고 말했다. 나중에 정수에 대해 작동하는 보편 레지스터 머신을 의미한다고 명확히 했다.

또 다른 댓글 작성자는 주장된 속도 향상이 어떻게 얻어지는지 기계적으로 설명했다. 알고리즘은 이산 푸리에 변환과 곱셈 사이의 알고리즘적 유사성을 활용하여 DFT 작업의 일부를 곱셈 작업으로 변환하며, 이는 정확한 산술 모델에서 O(1) 비용이 든다. 대가는 곱해진 숫자의 크기가 n에 대해 초다항식으로 증가한다는 것이다. 댓글 작성자의 표현은 알고리즘이 "작업을 거기에 채워 넣고 오라클로 사용하는" 것이다.

한 댓글 작성자는 복잡성 분석에 대한 직접적인 도전으로 같은 점을 제기했다: 알고리즘이 n에 대해 초다항식으로 증가하는 크기의 복소수를 곱해야 한다면 "그것이 big-O 분석을 완전히 무효화하지 않습니까?"

한 댓글 작성자는 관련 경계를 강화하려는 진행 중인 노력에 연결하여 CrocSwap integer-mult-bounds GitHub 저장소에서 kappa 값 약 0.001635527380375392를 인용했다.

별도의 스레드는 상황을 잘못된 질문에 잘 대답하는 AI 시스템에 비유하며, 이전 Hacker News 토론 "Navier-Stokes Lost in Translation"에 연결하고 은하수를 여행하는 히치하이커를 위한 안내서의 Deep Thought를 언급했다. Deep Thought는 누구도 질문을 알기 전에 답을 생성했다.

논쟁을 해결할 것

Hacker News 스레드의 양측은 동일한 공백에 수렴한다: 토론의 누구도 증명을 검증했다고 주장하지 않는다. argmin.net 게시물은 논문 읽기를 명시적으로 거부하고, 이론 컴퓨터 과학을 옹호하는 댓글 작성자들은 결과가 비실용적이라는 반대보다는 실제 오류, 누락된 크레딧 또는 다른 구체적인 결함을 찾는 것이 올바른 대응이라고 주장한다.

교환으로 남겨진 실질적인 기술적 질문은 분야에 대한 논쟁보다 더 좁다. 즉, 정확한 복소수 산술 모델이 이 클래스의 결과에 표준인지 아니면 특이한 선택인지, 중간 크기의 초다항식 성장이 구성에 내재적인지 아니면 기록된 방식의 인공물인지, 그리고 추정된 상수 10^100이 줄어들 수 있는지 여부이다. 그 중 하나가 답변될 때까지 더 빠른 푸리에 변환에 대한 주장은 argmin.net 게시물이 말했듯이 존재하지 않는 기계에 대한 점근적 진술로 남아 있다.

SUMMARY: OpenAI의 수학 논문 공개에 대한 argmin.net 분석은 그들이 주장하는 더 빠른 푸리에 변환이 점근적으로만 더 빠르며, 10^100으로 추정되는 상수를 숨기고 실제 컴퓨터가 구현하지 않는 정확한 복소수 연산을 가정한다고 주장한다.

TITLE: OpenAI가 주장한 더 빠른 푸리에 변환은 10^100 상수를 가진 '은하계 알고리즘'이다