요약
오픈AI가 n log n 아래로 끌어내린 정수 곱셈의 시간 상한을 수백 명이 AI 에이전트로 더 낮추고 있습니다.
Auto Research는 슈퍼(Super)가 만든 대시보드로, AI의 도움을 받은 수학 연구에서 공동체가 낸 개선을 추적합니다. 중심 과제는 오픈AI의 2026년 수학 프리프린트(정식 심사 전에 공개한 논문)가 내놓은 n log n보다 빠른 정수 곱셈입니다.
왜 중요한가
- 수학 난제가 GitHub PR(변경 제안)과 점수판으로 겨루는 공개 대회처럼 굴러가고 있습니다.
- 실패한 실험도 "no new kappa"를 붙인 PR로 공유해 에이전트들이 같은 헛수고를 되풀이하지 않게 합니다.
- 결과는 원 논문의 보조정리에 기댄 조건부라서 완결된 정리나 실제 계산 속도 향상으로 볼 수는 없습니다.
핵심 내용
- 지표 κ는 상한 O(n (log n)^(1−κ))에서 줄인 지수로, 0보다 크면 n log n보다 빠르고 클수록 좋습니다.
- 오픈AI 원 논문의 κ는 2⁻¹⁸²였고, 검토를 마친 기준값은 7.24×10⁻⁴, 열린 제안의 최고치는 1.68×10⁻³입니다.
- 저장소 기여자는 229명이고, 그중 151명이 지난 24시간 안에 첫 PR을 냈습니다.
- 전체 PR 1,412개 가운데 Codex를 썼다고 밝힌 것이 841개, Claude가 284개입니다.
- 페이지에 실린 X 게시물에 따르면 주말엔 몇 분마다 기록이 바뀌었지만 지금은 새 벽에 막혀 진전이 느려졌습니다.
HN 반응
- 복소수 연산을 공짜로 치는 계산 모형의 허점을 이용했다는 비판에, 흔히 쓰는 표준 모형이고 정수 곱셈은 튜링 기계 기준이라는 반론이 맞섰습니다.
- 숫자 올리기에만 매달려 통찰이 빠진다는 우려에는, 에이전트가 E8 같은 엉뚱한 발상을 시도하니 쓸 만한 것은 사람이 나중에 다듬으면 된다는 답이 나왔습니다.
속도가 어디서 빨라지는지 직관적으로 설명한 좋은 글이 혹시 벌써 나왔나요? 예를 들어 고속 푸리에 변환(FFT)은 판데르몽드 행렬에 대칭성과 중복 계산이 많다는 걸 볼 수 있으니, 거기서 속도가 나온다는 걸 알 수 있잖아요.
사이트가 로딩이 한참 걸리네요. 그건 그렇고, 복잡도 이론에는 O(nlogn) 같은 데 사람들이 생각하는 만큼 단단한 벽이 있는 게 아닙니다.
시간과 공간은 언제든 맞바꿀 수 있습니다. 복잡도 이론을 만든 사람이 증명한 블룸의 속도 향상 정리(Blum's speedup theorem)가 바로 이 내용이고, 복잡도 이론의 근본적인 부분입니다.
예를 들어 누군가 nlogn 해법을 내놓으면, 저는 안쪽 루프의 일부를 룩업 테이블로 바꿔 넣을 수 있습니다. 여기서는 공간이 아니라 시간만 재고 있으니 룩업 테이블이 2^n 크기여도 상관없습니다. 그러면 룩업 테이블 조회는 O(1)이니 순식간에 nlogn보다 나은 해법이 됩니다.
그렇다고 이번 결과에 의미가 없다는 얘기는 아닙니다. 다만 사람들이 이 결과에 그렇게까지 놀랄 일은 아니라는 겁니다. 복잡도 이론이니까요. 시간 복잡도가 nlogn이라서 더는 못 내려간다는 식의 단단한 벽은 말 그대로 존재하지 않습니다. 언제든 더 내려갈 수 있습니다. 다만 그러려면 시간 복잡도와 공간 복잡도를 함께 놓고 따져야 합니다.
복잡도 이론을 공부한 지 오래돼서 그런데, 블룸의 속도 향상 정리가 정말 그런 내용인가요? 구글에서 잠깐 찾아보니, 이 정리는 계산 가능한 함수 중에 최적의 프로그램이 존재하지 않는 것이 있다고 말하는 것 같던데요.
예컨대 하한이 n 시간인 문제가 있는데, 알고리즘이 O(n)에 얼마든지 가깝게 다가갈 수는 있어도 실제로 거기에 도달하는 프로그램은 없는 경우입니다. O(n^{1.1})에 돌아가는 프로그램도 있고, O(n^{1.01})에 돌아가는 프로그램도 있고, 이런 식으로 계속되는 거죠.
하지만 그렇다고 단단한 벽이 없다는 뜻은 아닙니다. 모든 프로그램의 실행 시간이 그 벽보다 "크거나 같다"가 아니라 "엄밀히 크다"는 식의 벽이 있다는 뜻일 뿐이죠. 제가 잘못 이해했거나 놓친 따름정리가 있을 수도 있겠지만요.
여담으로, 순수 수학 쪽을 더 공부한 사람으로서 말씀드리면 블룸의 속도 향상 정리는 꽤 직관적입니다. 위상수학을 쓰면 비교적 우아한 증명이 나올 것 같기도 하고요. 블룸의 속도 향상 정리는 본질적으로, 어떤 계산 가능한 함수를 구현하는 프로그램들의 집합이 최대 하계 성질(greatest lower bound property)을 만족하지 않는다는 말입니다. 유리수 집합도 마찬가지입니다. 하한은 있지만 최대 하한은 없는 유리수 부분집합이 존재하죠(q^2 >= 2인 모든 양의 유리수 q의 집합 같은 것). 대충 말씀드리는 거지만, 같은 맥락에서 실행 시간 순서로 만든 위상을 프로그램 집합에 주면 그 집합이 완전 비연결(totally disconnected)이라는 것도 보일 수 있을 것 같습니다.
언제나 그런 건 아니지 않나요? 그 정리는 속도를 높일 수 있는 함수가 존재한다는 얘기지, 모든 함수가 그렇다는 얘기가 아닙니다. 간단한 반례는 튜링 머신에서의 항등 함수입니다. 그냥 HALT/ACCEPT일 뿐이라 더 줄일 방법이 없습니다.
시간과 공간의 맞교환도 무한히 자유롭지 않습니다. 공간을 채우는 데도 시간이 드니까요. 그리고 룩업 테이블은 실행 중에 만들어야 하고, 그렇지 않으면 크기가 유한해서 상수배의 속도 향상밖에 안 됩니다. 아마 위키백과에서 말하는 선형 속도 향상 정리(linear speedup theorem)를 떠올리신 게 아닐까요? https://en.wikipedia.org/wiki/Linear_speedup_theorem
우리가 실제로 찾아낸 몇 안 되는 하한 중 하나가 바로 비교 기반 정렬의 nlogn인데, 이건 좀 아이러니한 예 아닌가요?
게다가 이 주장은 너무 강한 것 같습니다. 이론 전산학(TCS) 하는 사람들이 NP != P라고 믿는다는 것도, 하한이 존재한다고 믿는다는 또 하나의 예잖아요? (이와 관련해, 아직 성과가 썩 크진 않지만 뭐든 하한을 증명하려고 애쓰는 이론 전산학의 큰 부분 자체가, 연구자들이 하한이 존재한다고 믿는다는 걸 보여 주죠. 복잡도 클래스가 서로 다르다는 가설은 전부 그런 예 아닌가요?)
벤 렉트(Ben Recht)가 쓴 좋은 블로그 글이 있습니다. 이런 결과들은 수의 크기나 정밀도에 따라 비용이 늘어나게 하지 않고, 정확한 복소수 연산을 원자적 연산으로 가정해서 이론 전산학의 형식화를 보상 해킹(reward hacking)한 것에 가깝다는 내용입니다. https://www.argmin.net/p/faster-fourier-transforms
수의 곱셈은 본질적으로 합성곱이고 FFT와 밀접하게 연결돼 있으니, "FFT가 하는 일" 상당 부분을 어떻게든 정확한 산술 연산 안에 밀어 넣고 나머지 비용은 그 표현으로 묶고 푸는 데 드는 것만 따로 세는 방식이어도 저는 별로 놀라지 않을 겁니다. 결국 장부 정리의 허점을 이용한 거죠.
이게 은하급 알고리즘(galactic algorithm)이라는 다른 불만은 일단 접어 두고 하는 얘기입니다.
꽤 편향된 블로그 글입니다. 알고리즘을 다룰 때 단위 비용 RAM은 꽤 표준적인 계산 모델입니다. 예를 들어 문자열의 비교 정렬이 O(n log n) 시간이라고 말할 때도 두 문자열을 비교하는 데 단위 비용이 든다고 암묵적으로 가정하고 있죠. 실제로는 문자열을 비교하는 데 문자열 길이에 비례하는 시간이 듭니다. 그게 어이없다고 할 수도 있겠지만, 이 바닥에선 늘 있는 일입니다. 원래의 FFT도 O(n log n) 시간이라고 할 때 단위 비용 곱셈을 가정합니다. 즉 곱셈 O(n log n)번이라는 뜻이죠.
마찬가지로, 네, 은하급 알고리즘이긴 합니다. 하지만 이런 것들도 여전히 의미 있게 받아들여집니다. 점근적으로라도 단위 비용 RAM에서 이게 가능하다는 것 자체가 아무도 예상하지 못한 놀라운 결과입니다.
문자열 비교 모델은 문자열 길이가 리스트 길이보다 훨씬 짧아서 상수로 묶을 수 있는 영역에서 유용합니다. 길이가 제멋대로 늘어나 리스트 길이보다 훨씬 길어질 수 있는 중간 문자열을 만들어 낸다면, 그 모델은 형편없이 망가진(즉 현실을 대표하지 못하는) 모델이 됩니다.
물론 뭐든 퍼즐로 만들 수는 있지만, 그 문제가 어떤 상황을 모델링하는지 따져 보는 게 마땅합니다.
그리고 맞습니다, 이 비판은 오픈AI가 내놓은 이번 결과물만이 아니라 이론 전산학 전반에 더 널리 적용될 수도 있습니다. 사람이 하든 LLM이 하든 보상 해킹인 건 마찬가지입니다.
메모리와 연산을 아우르는 아주 좋은 범용 근사 모델에 대해 합의가 이루어졌나요, 아니면 그 자체가 풀기 어려운 주제인가요?
이 블로그 글은 여러 군데가 눈에 띄게 틀렸습니다. 우선 nlogn보다 빠른 곱셈은 전통적인 멀티테이프 튜링 머신 모델을 쓰는데, 이 모델에는 DFT 결과가 쓰는 것과 같은 요령이 없습니다(DFT 결과도 논문이 덜 읽히는 대가를 치르면 비슷하게 다시 정식화할 수 있습니다).
또 10^-13은 최적화된 수치가 아닙니다. 현재 결과는 거기서 10자릿수쯤 올라온 10^-3 수준이고, 멈출 기미가 거의 없습니다. 상수는 여전히 천문학적이겠지만, nsqrt(log(n))까지 가는 것도 충분히 가능해 보입니다.
그건 지금 방식이 가진 본질적인 한계인가요, 아니면 n(log n)^epsilon도 가능할까요?
그런데 산술 연산을 "원자적"으로 보는 건 이론 전산학에서 표준적인 가정 아닌가요? 비용은 비트 길이에 따라 늘어나고, 비트 수와 상관없이 덧셈이 "상수 시간"이라고 가정하는 건 아닐 텐데요(그러면 이 연습의 의미가 통째로 사라지니까요).
제가 뭔가 놓친 걸 수도 있지만, 그 블로그 글에 나온 내용 중에 딱히 "놀라운" 건 없어 보입니다. 대부분 이론 전산학에서 쓰는 계산 모델이 현실의 컴퓨터 모델과 맞지 않는다는 얘긴데, 그건 알고리즘 분석 첫날 배우는 거 아닌가요? 현실에 더 가까운 걸 원하면 워드 RAM 모델을 쓰면 되고요.
저는 O(1) 시간에 다루는 수가 입력 크기의 어떤 다항식 이하로 제한된다고, 즉 O(log n) 비트라고 가정하는 모델을 좋아합니다. 크기 n짜리 입력에 주소를 매기는 데만도 O(log n) 비트짜리 주소가 필요하니 합리적인 가정이죠.
이 모델에서는 흥미로운 일들을 할 수 있습니다. 정수 집합 질의를 O(log log n)에 처리하는 판 엠데 보아스(van Emde Boas) 자료구조라든가, 크기가 O(log n)인 부분 문제를 룩업 테이블로 바꾸는 요령 같은 것들이요.
알고리즘이 길이가 제멋대로 늘어나는 중간 수나 문자열을 만들지 않는다면 쓸 만한 모델 가정입니다. 그렇지 않으면 상수로 취급하는 그 값이 실제로는 유계(bounded)가 아니니까요.
이번 연구만의 간과인지 이론 전산학 전반의 문제인지는 모르겠습니다. 하지만 어쨌든 근본적인 지적입니다.
이 에이전트 무리의 실시간 게시판은 GitHub PR 시스템입니다. 에이전트들이 막다른 길을 포함한 병렬 연구 결과를 제목 끝에 "(no new kappa)"를 붙여서 쏟아 내고 있어요.
https://github.com/CrocSwap/integer-mult-bounds/pulls
주제에서 벗어난 얘기지만, 이런 Auto Research 프로젝트를 호스팅할 수 있는 프로젝트나 "템플릿" 같은 게 있나요?
배경 설명입니다. https://eu.36kr.com/en/p/4023452816134019
저는 하나도 이해가 안 됩니다. 기여한 내용이 Lean으로 되어 있나요?
오픈AI의 Lean 증명에서 시작해서 그 위에 계속 작업한 건가요?
Lean 증명이 크게 불어나고 있나요, 아니면 증명을 어느 정도 짧게 유지하려고도 하나요?
이 스레드야말로 HN의 가장 좋은 모습이네요. 정말 살아볼 만한 시대입니다!
참여하시는 분들을 탓하려는 건 아니지만, 솔직히 지금이 바로 테렌스 타오가 "바이브 수학(vibemathing)"이라며 우려했던 순간이라고 생각합니다. 오픈AI가 O(N log N)의 벽을 깼다면 의미 있는 사건이고 수학자들을 놀라게 할 만하며, 그게 사실 하한이 아니었다는 귀중한 정보를 얻은 셈입니다. 그런데 이 자동 연구 캠페인에서는 사람들이 숫자를 낮추는 데만 집중하고, 사람이 배울 만한 통찰은 얻지 못하는 게 아닌가 걱정됩니다.
그래프에 달린 인용들을 보세요. 에이전트들이 30차원 기하학이나 E8 같은 엉뚱한 아이디어도 시도하고 있습니다. 이 아이디어 중 어느 하나라도 특별히 성과가 있다면, 사람이 아주 한정된 주의력을 나중에 거기에 쏟아서 수학적 대포로 만들어 낼 수 있습니다. 여기서 얻을 교훈은, 분산된 에이전트 무리가 어려운 문제를 집요하게 파고드는 초기 사례를 지켜보고 있다는 것입니다. 진척도 단순한 지표(kappa 최대화) 하나로 추적할 수 있고요.
그분이 "바이브 수학"이라고 부르는 건 사실 그냥 공학이에요.
엔지니어는 뭔가가 왜 작동하는지 몰라도 그냥 가져다 씁니다.
과학은 나중에 그 이유를 밝혀내려 하고요.
둘 다 가치가 있지만, 과학이 "먼저"여야 한다는 생각은 아무리 좋게 봐도 증거로 뒷받침되지 않습니다.
이런! 우리 토큰을 공짜로 가져가려는 거군요
배경 설명을 더 드리면 아래와 같습니다.
https://nitter.kareem.one/RohanArun/status/2109336015814959200?s=20
(맨 앞 도메인은 정상 작동하는 인스턴스나 필요하면 x.com으로 바꿔서 보세요)
어라, 저더러 "봇처럼 보인다"네요. 제 엄청난 APM 때문인가 봐요.