요약
오픈AI의 더 빠른 푸리에 변환은 돌파구가 아니라 계산 모델의 허점을 파고든 결과라는 비판입니다.
벤 레크트가 자신의 블로그 arg min에 쓴 글입니다. 오픈AI가 대량으로 공개한 수학 논문 가운데 표준 FFT(고속 푸리에 변환)보다 점근적으로 빠르다는 결과를 두고, 실제 컴퓨터에서는 아무 의미가 없다고 지적했습니다.
왜 중요한가
- 이론상 더 빠르다는 주장이 실제 계산 속도와는 전혀 다를 수 있음을 보여 줍니다.
- AI가 이런 형식의 논문을 쉽게 만들어 내면서 실용과 동떨어진 이론 연구 관행이 더 커질 수 있다고 경고합니다.
핵심 내용
- 숨은 상수가 워낙 커서 입력 길이가 10^100이어도 기존 쿨리-튜키 FFT가 10^99배 빠르다고 했습니다.
- 이런 은하적 알고리즘(입력이 천문학적으로 커야 이득이 나는 알고리즘)은 빅오 표기가 상수를 감추는 점을 악용한다고 봤습니다.
- 정밀도 제한 없는 복소수 연산을 가정하지만, 그 수는 실제 컴퓨터에 저장조차 어려울 만큼 커진다고 했습니다.
- 계수 크기를 제한하면 ½ n log n보다 빠를 수 없다는 1973년 증명이 이미 있었다고 짚었습니다.
- O(n^2.25)라는 오픈AI의 행렬 곱셈 결과도 상수를 추정조차 할 수 없는 같은 부류라고 했습니다.
HN 반응
- 이론 학회는 원래 실용 알고리즘을 겨루는 곳이 아니라는 반론과, 실용성이 없다면 관심을 둘 이유가 없다는 반박이 맞섰습니다.
- 암호학에 쓰이는 유한체(원소가 유한한 수 체계)에서도 성립한다는 옹호와, 큰 정수 연산을 한 번에 끝난다고 치면 무엇이든 빨라진다는 풍자가 나왔습니다.
관점부터 틀린 글입니다. "slopository"라는 새 용어는 처음 들어봤고 기꺼이 인정하겠습니다. 하지만 이론가들에게 악의를 드러낸 저자는 짚고 넘어가야겠습니다. STOC/FOCS/SODA 같은 학회는 "실용적인 알고리즘을 하는 곳"이 아닙니다. 그런 걸 원하면 ESA, ALENEX, VLDB/SIGMOD 같은, 그런 연구를 싣는 응용 쪽 학회에 가면 됩니다. 실험을 안 한다는 이유로 이론을 싸잡아 깎아내리는 건 공정하지 않다고 봅니다. 이론가들은 수학자이고, 상수이기만 하다면 빅오 안에 터무니없는 상수가 들어 있어도 괜찮으니까요.
추신. 저는 이런 입장이면서 동시에 Ben이 대단한 사람이라고 생각할 수도 있습니다.
이론가로서 말씀드리면, 은하급(galactic) 상수에 "신경 쓰지 않는다"는 말은 어느 정도 맞습니다. 저는 철학적인 이유로 계산의 구조에 관심이 있습니다. 하지만 계산 모델만큼은 정말 신경 씁니다.
다르게 말하면, 빅오 안의 상수는 사실 상수가 아닙니다. 무엇을 상수 시간 연산으로 가정하느냐에 따라 달라지니까요.
빅오 상수에 대해 깨달은 게 있습니다. 현실에서 상수 시간은 잘해야 로그이고, 실제로는 세제곱근에 더 가깝다는 것입니다.
단순한 생각입니다. 가장 기본적인 일인 숫자 "n"을 읽는 것부터 자릿수에 달려 있으니 로그입니다.
그런데 대부분의 알고리즘에서 "n"은 데이터 집합의 크기를 가리킵니다. 이 집합은 보통 어떤 메모리에 저장되고, 메모리는 3차원 공간에 놓인 작은 셀들의 물리적인 배열입니다. 그 셀에 접근한다는 건 배열을 가로질러 간다는 뜻이고, 도달하는 데 걸리는 시간은 거리에 비례합니다. 용량은 거리의 세제곱에 따라 늘어나므로, 데이터를 가져오는 시간은 n의 세제곱근에 비례합니다.
제 결론은 이렇습니다. 복잡도가 세제곱근보다 낮은 수준으로 내려가면 수학적 추상화가 무너지기 시작하고, 실제 기계, 특히 캐시 구조를 고려해야 합니다.
아니요, 리스트를 만드는 경우가 아니라면 메모리 읽기는 주소 거리에 좌우되지 않습니다.
보통의 메모리는 리스트가 아닙니다. O(1)에 읽을 수 있는 평평한 공간입니다.
이론상으로는 그렇습니다. 실제로는 캐시가 여러 단계로 있고, 캐시에서 읽는 것이 메인 메모리에서 읽는 것보다 훨씬, 훨씬 빠릅니다.
그래서 자료구조 전체가 캐시 안에 들어가고 그걸 반복해서 순회한다면, 더 크고 넓게 퍼져 있는 구조보다 처리 속도가 훨씬 빠릅니다.
페이징, 할당/해제, 어쩌면 가비지 컬렉션도 고려해야 합니다.
이 모든 걸 따지고 나면, n이 늘 백만 정도보다 크지 않은 이상 빅오 추정치는 크게 오해를 부르는 일반화가 될 수 있습니다.
n이 작을 때는 한참 어긋날 수 있습니다.
말하는 건 "주소 거리"가 아니라 물리적 거리입니다.
그리고 일반적인 경우에 메모리 읽기는 거리에 좌우됩니다. 그래서 이런 말이 나오는 겁니다.
애초에 캐시 단계가 있는 이유가 바로 이겁니다. 계층은 계속 이어집니다. L1, L2, RAM, 벽장 속에 처박아 둔 회전 디스크 덩어리, 어딘가에 있는 "클라우드"까지요. 코어 가까이에 넣을 수 있는 저장 용량에는 한계가 있습니다. 더 많이 담으려면 물리적으로 더 커지고, 물리적으로 더 멀어집니다.
물론 한 단계 안에서는 상수 시간처럼 느껴질 수 있습니다. 하지만 그건 그 단계에서 가장 좋은 경우를 가장 나쁜 경우에 맞춰 느리게 만들어 놨기 때문입니다. 접근 시간이 계단식으로 끊기는 건 이 절충을 연속적으로 관리하는 시스템을 우리가 설계하지 못해서 생기는 현상이지, 근본적인 법칙이 아닙니다.
캐시가 빠른 이유는 코어와 물리적으로 가까워서가 아닙니다. 물론 가까운 것도 중요하지만, 캐시가 정적(static)이라는 사실, 즉 (사실상) 플립플롭으로 만들어졌다는 사실만큼은 아닙니다.
DRAM을 CPU에서 10cm 떨어뜨려 놓고 정적 RAM을 50cm 떨어뜨려 놓고 컴퓨터를 만들어도, 정적 RAM의 접근 시간이 DRAM보다 훨씬 짧을 겁니다.
그러면 모든 RAM을 정적으로 만들면 되지 않느냐고요? 비트당 비용이 더 비싸고, 에너지도 더 먹고, 실리콘 면적도 훨씬 더 많이 차지하기 때문입니다.
은하급 알고리즘을 이야기하는 시점에서 우리는 이미 컴퓨터 한 대에 들어갈 만한 영역을 한참 벗어났습니다. 그런 알고리즘 중에는 데이터를 이 태양계 안에 담기도 어려울 만큼 큰 n에서야 비로소 빨라지기 시작하는 것도 있습니다. 그 규모에서는 RAM 종류의 차이는 의미가 없습니다. 그쯤 되면 "메모리 주소 X를 읽는 데 걸리는 시간"은 거의 "X까지 빛이 도달하는 데 걸리는 시간"과 같고, 이는 거의 "X까지의 거리"와 같으며, 이 거리는 세제곱근으로 늘어납니다. (물리적 한계를 따지면 이상한 이유로 아마 제곱근이겠지만요.)
충분히 큰 메모리라면 읽기 속도는 주소 거리에 좌우됩니다. 적어도 읽은 데이터가 전달되는 속도가 유한하기 때문입니다.
인접한 셀을 순차적으로 읽는 건 파이프라인으로 처리되므로 처리량은 주소 거리에 좌우되지 않을 수 있습니다. 하지만 다른 주소에서 새 순차 읽기 흐름을 시작할 때의 지연 시간은, 아주 큰 메모리라면 주소에 따라 달라질 수밖에 없습니다. 예를 들어 랙 크기 정도만 돼도 랙의 한쪽 구석에서 반대쪽 구석까지 신호가 전파되는 데 메모리 클럭에 비해 오랜 시간이 걸리니까요.
제가 알기로는 극한에서는(그러니까 블랙홀이 생기기 전까지는) 정보 밀도가 부피가 아니라 표면적에 비례하니 제곱근입니다. 그리고 그 정도 밀도라면 시간 지연도 따져야 할 테고요...
"정보 밀도"는 비율입니다. 정보의 양을 그것이 저장된 길이, 면적, 부피로 나눈 값이니 "비례해서 늘어나는" 게 아닙니다.
충분히 많은 양의 정보는 그것이 저장된 부피에 비례해서 늘어납니다.
정보를 저장한 셀에 접근할 수 있어야 하므로, 정보 밀도는 보통 두 방향으로는 높고 세 번째 방향으로는 낮습니다.
그래서 면적당 정보 밀도와 부피당 정보 밀도를 구분하는 게 유용합니다. 면적당 밀도는 자기 헤드의 크기나 포토리소그래피 공정의 해상도 같은 것으로 정해지고, 부피당 밀도는 면적당 밀도와 어떤 층의 두께로 정해집니다. 이 두께는 테이프나 디스크, 집적회로 패키지의 강도를 충분히 확보하는 것 같은 기계적 고려로 정해지는 게 보통입니다.
말씀드렸듯이 정보량이 충분히 커지면 HDD를 가득 채운 랙이나 자기 테이프 로봇 라이브러리처럼 부피당 정보 밀도가 거의 일정해집니다.
네, 말을 잘못했습니다. 어쨌든 제가 전문가는 아니지만, 제가 이해하기로 최대 밀도에서는 한 영역의 정보가 그 영역의 부피에 비례하지 않고, 그 영역이 만드는 사건의 지평선의 표면적에 비례합니다(적어도 슈바르츠실트 블랙홀의 경우에는요). 이게 틀렸습니까?
말씀하신 정보량은 제가 말하는 정보량보다 한참 낮습니다. 빅오는 극한에 관한 것인데, 물리적 한계를 끌어들여 밀도에 한계가 있다고 말할 거라면 끝까지 가는 편이 낫습니다. 극한은 n -> 10^18이 아니라 n -> 무한대입니다. 정보를 계속 더하면서 세제곱 비례를 유지할 수는 없습니다.
문제의 OpenAI 논문 일부를 포함해 몇몇 계산 모델은 다중 테이프 튜링 기계 모델로 작업해서 이 문제를 피합니다. 무한한 테이프 전체를 옮기는 에너지 비용에 대해서는 시비를 걸 수도 있겠죠(다중 테이프이고, 통신이 제한된 코드에서는 헤드들이 서로 가까이 있어야 하니까요). 그래도 이 기계들은 상당히 강한 의미에서 정말로 지역적(local)입니다.
기사를 곱씹어 보다가 정수 행렬 곱셈이 아마 O(n^2)일 거라는 생각이 들었어요. 은하급 상수도 필요 없이요. 다만 단위 비용 정수 연산이 필요해요.
먼저 어떤 중간 계산 결과도 b-1을 넘지 않도록 충분히 큰 밑 b를 찾아요(행렬을 한 번 훑으면 될 거예요). 그런 다음 왼쪽 행렬의 각 행을 하나의 큰 값 A_i = sum_k a_ik * b^k로 인코딩하고, 오른쪽 행렬의 각 열을 B_j = sum_k b_kj * b^(n-k)로 인코딩해요. A와 B를 명시적으로 계산하는 데는 O(n^2)번의 정수 연산이 들고요.
이제 답을 원소 하나씩 뽑아내요. A_i * B_j에는 여러 항이 있는데, 그중에 sum_k a_ik * b_kj * b^n이 있어요. 다른 항들은 모두 b의 거듭제곱이 달라요. 그래서 b^(n-1)로 정수 나눗셈을 하고 나머지를 버린 다음 그 결과를 b로 나눈 나머지를 구하면 (a*b)_ij가 나와요. 출력 원소 하나당 정수 곱셈 한 번과 divmod 두 번이 드는 셈이죠. 문제 해결이에요. 이걸로 FOCS에 논문 낼 수 있을까요?
물론 이건 엄청난 편법이에요. OpenAI의 최신, 최고 은하급 정수 곱셈 알고리즘을 쓴다 해도, 조금이라도 현실적인 컴퓨터 모델에서는 점근적으로 평범한 고등학교식 행렬 곱셈 알고리즘보다 느릴 거예요.
OpenAI 논문들에도 제 것만큼 터무니없는 편법이 들어 있을지 궁금하네요 :)
(교훈은 정확한 수학이 꽤 강력하다는 거예요. 그리고 정밀도 비트 수에 대해 선형보다 작은 시간에 하는 정확한 수학은 성능을 슬쩍 훔쳐 오기에 아주 좋은 방법이고요.)
멋지네요. 저도 비슷한 편법으로 선형 시간 정렬 알고리즘을 만들 수 없을까 생각해 보고 있었어요. 혹시 좋은 생각 있으세요?
자연스러운 정수 연산으로는 아무것도 못 떠올렸어요. 아주 징그러운 꼼수는 매우 부자연스러운 정수 연산을 쓰면 떠올릴 수 있지만, 그건 이런 종류의 편법에 넣기에도 너무 지저분하게 느껴져요. 부자연스러운 정수 연산을 단위 비용으로 쓸 수 있다고 허용하는 순간 그냥 포기하는 게 나아요. 정수 하나로 억지로 욱여넣을 수 있는 입력이라면 말 그대로 어떤 연산이든 상수 시간에 할 수 있으니까요.
알고리즘 이론가들이 실제 성능에 관심이 없다면, 우리가 왜 그들이 하는 일에 관심을 가져야 하죠? 그냥 자기들끼리 하는 이상한 게임이고, 다른 사람에게는 아무 흥미도 없잖아요.
더 많은 "은하급" 알고리즘을 내놓기보다는, 이렇게 쉽게 악용되지 않는 빅오 대체물을 만들고 이론가들이 그 게임을 하도록 설득하는 편이 더 쓸모 있을 것 같은데요.
관심을 가져야 하는 이유가 있습니다. 16세기 피에르 드 페르마의 모듈러 산술 연구도 다른 이론가들을 빼고는 "아무에게도 흥미 없는" 일이었지만, 20세기에 현대 암호학에서 빛을 봤습니다.
이론을 하는 일은 현실 문제에 깊이 파묻혀 있을 때는 상상조차 못 할 곳까지 한계를 밀어붙일 기회를 줍니다. 그리고 어떤 것이 (비실용적이더라도) 가능하다는 걸 증명하면 더 나은 알고리즘을 찾으려는 동기가 생기고, 다른 사람들을 끌어들일 수도 있습니다.
예를 들어 여기 첫 번째 그래프를 보세요. http://klotza.blogspot.com/2016/06/the-fall-of-twin-prime-gap.html
이 대목을 보면요.
"1973년에 자크 모르겐슈테른은 계산에 쓰이는 복소수 계수의 크기가 유계여야 한다는 조건을 달면 푸리에 변환을 ½ n log n보다 빠르게 할 수 없음을 증명했다"
이게 수학적 한계보다 더 빠른 알고리즘을 만들도록 사람들에게 영감을 줄 거라고는 도저히 생각하기 어렵습니다...
저는 순수수학에 아무 불만이 없고, 그쪽에서 훈련을 받았습니다. 하지만 이론 컴퓨터과학(순수수학과는 별개로)에 돈을 대는 사람들 대부분은 그 연구가 더 현실적인 계산 모델에 뒷받침되고 있다고 가정할 가능성이 충분하다고 봅니다.
순수수학으로 연구비를 받는 사람 대부분은 아마 암호학처럼 실용적인 것과 어떻게든 관련이 있다거나 도움이 될 수 있다고 거짓말을 하거나 진실을 부풀릴 겁니다. 그게 실제로 사실일 필요는 없어요. 그럴듯하게 느껴지기만 하면 되니까요.
로봇공학 연구 중에 수색 구조에 쓰일 수 있고 소방관이 불을 끄는 데 도움이 될지도 모른다고 하는 것들이랑 똑같네요.
복소수를 부동소수점으로 표현하는 경우에도 이게 적용되나요? 그건 비가산 무한이 아니잖아요.
네, 적용됩니다. 이건 "선형 알고리즘"에 적용되는데, 선형 알고리즘이란 기본적으로 이런 형태의 함수입니다.
여기서 각 ti는 앞의 t 변수들, 입력 x 변수들, 또는 상수들의 선형 결합입니다.
비용 모델은 수행한 덧셈의 횟수일 뿐입니다.
OpenAI의 알고리즘은 소수 위수 유한체에서도 작동합니다. 이런 FFT는 암호학 곳곳에서 쓰입니다. 그러니 그 결과는 분명히 쓸모없지 않고, 현실적인 계산 모델에서도 작동합니다.
그 암시에는 동의하지 않습니다. 모듈러 산술은 훨씬 더 명백하게 쓸모가 있고, 그때도 그랬을 겁니다(페르마에게 은하급 알고리즘이라는 개념을 설명했다고 가정하더라도요). 추상적인 수학 구조라서 새로운 상황에서 다시 등장할 가능성이 높기 때문입니다.
그건 극도로 비효율적인 사고방식이라고 생각합니다. 몇 세기 뒤에 쓸모가 생길지 모른다는 극히 희박한 가능성에 시간을 쓰면서, 지금 당장 확실히 쓸모 있다고 아는 문제에 쓸 수 있었던 시간을 포기하는 건 이상한 거래입니다.
HN에 댓글 다는 데 시간을 쓰는 건 몇 세기 뒤에 쓸모 있는 수학적 결과를 낼 가능성이 그보다 더 낮은데, 그래도 지금 여기 계시잖아요.
좋아요, 그럼 다른 방향으로 이야기해 보죠.
다른 사람들이 무엇에 시간과 에너지를 쓰고 싶어 하는지를 통제하려는 건 거의 완전히 불가능하고, 그래서 시간 낭비입니다.
연구비를 쥐고 있는 단 하나의 손 같은 건 없습니다. 이론이 현실에서 구현되는 길도 하나뿐이 아닙니다.
무엇을 연구"해야" 하는지 이야기하는 건 좋게 봐줘도 오만입니다.
맞는 말이지만, 지금 이야기하는 건 무엇을 연구해야 하느냐가 아니라 무엇에 연구비를 대야 하느냐입니다.
그들이 하는 일에 신경 쓰지 않으셔도 됩니다. 다만 빅오 표기법에는 쓸모 있는 성질이 있고, 특히 복잡도 클래스를 정의할 수 있게 해 주는 유용한 정의라서, 알고리즘을 분석하는 데 일반적으로 아주 유용한 도구가 되었습니다.
우리가 가진 '실용적인' 알고리즘 지식 상당 부분도 일부는 이론의 진전에서 나왔습니다.
기사의 논점은 빅오 표기법이 유용한지가 아니라, 특정 빅오 안의 n이 의미 있는지입니다. 이 경우 알고리즘의 주장은 임의로 큰 수를 곱하는 데 n log n보다 빠르게 할 수 있다는 것인데, 여기서 n은 곱하는 수의 크기입니다. 하지만 이 결과는 임의로 큰 복소수를 곱하는 비용을 그 n에 포함하지 않을 때만 성립합니다. 그 복소수들은 상수 시간에 곱할 수 있다고 가정하니까요.