지난주에 GPT-5.6과 Claude Fable이 무선 통신 분야의 공개된 이론적 질문 하나를 해결한 것으로 보입니다. 이 문제는 2000년부터 2010년대까지 집중적으로 연구되었고, 저도 불안한 1년차 박사 과정 학생 시절에 잠시 다루었던 문제입니다. 마침내 답이 도착했습니다. 아마도 제가 그 질문을 던진 마지막 몇 명 중 하나였고, 기계에게 그 문제를 풀도록 프롬프트를 입력한 최초의 사람이었기 때문일 것입니다 😊
결과: N 비트를 N×N 가우시안 무선 채널을 통해 보내면, 수신기는 그 모든 비트를 정확히 복구해야 합니다. 2000년대부터 신호 대 잡음비가 최소 2 log N일 때 정보 이론적으로 그렇게 할 수 있다는 것이 알려져 있었습니다. 그러나 그 경계에 도달하는 유일한 알려진 방법은 지수적 탐색 알고리즘이었습니다. 이제 단순한 다항 시간 알고리즘이 정확히 같은 임계값에서 성공한다는 증명이 나왔습니다.
이에 대해 조금 더 이야기해 보겠습니다.
2009년에 저는 Alex Dimakis(@AlexGDimakis)와 함께 첫 논문을 작업했습니다. 그는 곧 제 박사 지도교수가 되었습니다(그 논문 때문은 아니지만요):
그 논문은 MIMO 검출에 대한 다항 시간 해법을 제시하려는 많은 시도 중 하나였습니다.
MIMO 검출이 무엇이냐고요?
송신기는 N 비트의 벡터를 N개의 송신 안테나와 N개의 수신 안테나로 구성된 무선 채널을 통해 보냅니다. 채널은 비트들을 모두 섞고 잡음을 더합니다. 채널 행렬을 알고 있는 수신기는 어떤 비트가 전송되었는지 알아내야 합니다.
블록 오류 최적 수신기, 즉 최대우도(ML) 검출기는 수신된 신호가 주어졌을 때 전송되었을 가능성이 가장 높은 벡터를 찾아 정확히 이 문제를 해결합니다. 이 경우 ML 검출은 다음과 같은 기본적인 이산 최소 제곱 문제를 푸는 것으로 귀결됩니다:
불행하게도, 인생의 모든 좋은 문제들이 그렇듯… ML 검출은 NP-난해입니다.
그래도 우리는 TCS 비관론자가 아니고, 무선 채널은 최악의 경우가 아니라 무작위적입니다. 그리고 학계는 2000년대 초반부터 다음 질문을 연구해 왔습니다:
전송된 비트를 통계적으로 복구하는 것이 가능할 때, 다항 시간 안에 할 수 있을까?
우리는 위의 2010년 논문에서 그 질문에 큰 진전을 이루지 못했고, 그 분야의 많은 연구에도 불구하고 그 문제는 제가 이해하기로는 2001년 이후 계속 열려 있었습니다… 더 극적으로 말하면 무려 사반세기 동안이요.
지난주까지는요. 그리고 최종 답은 이렇게 나왔습니다:
네! 완벽한 검출이 통계적으로 가능할 때마다, 다항 시간 안에 할 수 있습니다.
MIMO 해결됨. 끝.
하지만 누가 신경 쓸까요? 잠시 후에 다시 돌아오겠습니다.
논문을 첨부합니다. 저는 증명과 설명을 단순화하기 위해 모델들과 5일 이상 왔다 갔다 했습니다(원래는 완전히 엉망이었습니다). 이 과정은 GPT가 만든 초기 증명(약 30분 정도 걸렸습니다)보다 훨씬 더 오래 걸렸습니다. 증명은 길지만 비교적 기초적인 수준입니다. 저는 모든 것을 검증했고, 최선을 다해 증명을 확인한 결과 맞습니다.
이제 문제와 그 역사에 대해 좀 더 이야기하고, 이 분야가 MIMO 검출 이론의 이 특정 부분에서 이미 나아갔음에도 왜 이 글을 쓸 가치가 있다고 생각하는지 말씀드리겠습니다.
문제 설정
이진 벡터 x in {±1}^N을 전송하고, 다음을 수신합니다:
y=SNRNHx+w{\bf y} = \sqrt{\frac{SNR}{N}}{\bf H}{\bf x}+{\bf w}
여기서 H는 N×N이고 H와 w 모두 iid N(0,1) 항목을 가지며 모두 독립입니다. 수신기는 H와 잡음 통계를 알지만 w는 모르며, y에서 x를 복구하려고 합니다. 복구 문제에 대한 블록 오류 최적 해법은 다음과 같습니다:
참고로 이 최적화는 다른 형태로도 나타납니다: MIMO 검출, CDMA 다중 사용자 검출, 정수 최소 제곱, 격자에서 가장 가까운 벡터 등등.
SNR = ∞(즉, 유효 잡음 0)일 때 문제는 사소해집니다: 채널 행렬 H는 확률 1로 역행렬이 존재하므로, 역행렬을 구해 inv(H)*y로 정확한 x를 복구합니다. 다른 극단인 SNR = 0에서는 잡음에서 검출할 수 있는 것이 없으며 ML 검출은 실패합니다.
그러나 0과 무한대 사이 어딘가에서 ML 검출은 성공하며, 정확히 SNR = 2 log N에서 성공합니다. 이는 위의 최적화 문제를 푸는 것이 전송된 N비트 시퀀스의 모든 비트를 확률 1로 완벽하게 복구할 수 있게 해주며, 그 아래(로그로그 N 항까지의 덧셈 기준)에서는 블록 복구 확률이 0으로 수렴한다는 것을 의미합니다.
2logN 이상에서는 전송된 신호가 ML 최적화 문제의 최적점이지만, 그것을 푸는 것은 가능한 모든 N비트 시퀀스에 대한 완전 탐색이 필요한 것처럼 보입니다. 그래서 지금 우리가 관심을 갖는 질문은:
ML이 성공할 때 다항 시간 알고리즘이 전송된 x를 복구할 수 있을까?
**
약간의 드라마가 있는 간단한 역사
정수 최소 제곱 문제의 해결 가능성에 대한 질문은 적어도 1989년으로 거슬러 올라갑니다. 그때 Verdú가 일반적인 경우 NP-난해임을 증명했습니다. 그러나 NP-난해성은 최악의 경우에 대한 진술이며, 우리의 사례는 그렇지 않습니다.
Hassibi와 Vikalo는 2001년에 제가 아는 한 평균적인 경우에 대한 다항 시간 해법의 가능성이 있다고 최초로 주장했습니다. 그들이 분석한 알고리즘은 당시 인기 있던 방법인 구체 디코더(Sphere Decoder, SD)로, Fincke와 Pohst의 1985년 연구로 거슬러 올라갑니다. 구체 디코더는 특히 관심을 받았는데, 1) 정확한 ML 알고리즘이므로 항상 최소화값을 출력하고 2) 실제로는 지수 시간보다 훨씬 빠른 것처럼 보였기 때문입니다.
그래서 구체 디코더가 다항 시간에 실행된다는 것을 실제로 증명할 수 있을 것이라는 희망이 있었습니다. 이것이 H&V가 그들의 논문에서 밝힌 내용입니다: 그들은 채널과 잡음에 대해 평균화한 구체 디코더의 예상 복잡도에 대한 공식을 유도했고 그것이 다항식처럼 보인다는 것을 보여주었습니다. 그것이 사실이라면 그 질문은 해결된 것이었습니다. 그것은 믿기 어려운 결과처럼 보였습니다.
그런 다음 2005년에 Jaldén과 Ottersten은 점근적 해석이 완전히 정확하지 않다는 것을 보여주었습니다: 어떤 고정된 SNR에서도, 아무리 크더라도, 구체 디코딩의 예상 복잡도는 실제로 문제 차원에서 지수적입니다.
따라서 정확하고 빠른 방법이 통하지 않았기 때문에, 학계는 ML 최적화 문제에 대한 근사에 상당한 노력을 기울였습니다. 근사 보장이 있는 반정부호 이완(Semidefinite relaxations)과 높은 SNR에서의 엄밀성 조건이 있었지만 날카로운 임계값은 없었습니다. 비트 플립 지역 탐색은 시뮬레이션에서 ML과 일치하는 것처럼 보였지만 ML 복구 임계값과 일치한다는 완전한 증명은 없었습니다. AMP 문헌은 블록 복구가 불가능한 고정 SNR에서 비트당 오류를 엄밀하게 특성화했습니다. 통계 물리학은 복제(replica) 수준의 논증을 사용하여 정확한 ML을 추적할 것으로 예측된 다항 시간 방법을 생산했지만, 제가 이해하는 한 증명은 없었습니다. 그리고 위의 Babak 및 Alex와의 2010년 논문은 MCMC 방법을 분석하여 혼합 후 정상 분포가 올바른 해에 0이 아닌 질량을 둔다는 것을 증명했지만, 어려운 부분인 혼합 시간에 대해서는 아무것도 증명하지 못했습니다.
그 모든 세월 동안, 제가 보기에는 정확히 하나의 다항 시간 방법만이 임의의 SNR 척도에서 엄밀한 블록 복구 보장과 함께 등장했습니다: 2020년의 박스 이완(box relaxation)은 SNR이 4 log N처럼 커질 때 블록을 복구하고 그 이하에서는 복구하지 못함을 증명했습니다. 덧붙이자면, 그러한 기법을 분석하는 데 필요한 확률론적 도구가 2010년대 후반에 성숙했다는 점은 흥미롭습니다. 대부분 학계가 이미 다른 곳으로 옮겨가 흩어진 이후였기 때문입니다.
그리고 그 이후로… 활동이 많지 않았습니다.
요약하자면, ML이 달성하는 것과 다항 시간 방법이 증명 가능하게 달성할 수 있는 것 사이의 격차는 결코 좁혀지지 않았습니다.
**
GPT와 Claude는 무엇을 했고, 어떻게 제가(Dimitris) 검증할 수 있는 증명을 얻었나?
최근 프런티어 모델들이 어려운 수학 문제에서 보여준 비현실적인 성공들에 동기부여를 받아, 저는 대학원 시절 저를 괴롭히던 문제들(정보 및 부호 이론을 연구했었습니다)로 돌아가 그 문제들에 데스 스타를 겨누기 시작했습니다. 어려운 수학 질문을 하고 GPT가 제로샷으로 풀어내는 것이 정확히 이런 느낌입니다:
GIF
하지만 문제가 하나 있다는 것을 알고 있었습니다. 질문에 대한 완전한 답을 받는다 해도, 더 널리 공유하려면 그것을 검증해야 하는 병목에 직면하게 됩니다. 하나는, 그것이 틀린 것으로 판명되면 창피해지고 싶지 않기 때문이고, 둘째는 공유가 우리가 질문을 하고 과학을 하는 주요 이유이기 때문입니다.
그래서 저는 박사 과정 초반에 저를 괴롭혔던 가장 야심 찬 질문 중 하나이면서도 깔끔하게 서술할 수 있고 여전히 열려 있는 문제를 고르기로 했습니다. 그래서 GPT-5.6과 Claude Fable 5에게 ML MIMO 검출이 언제 다항 시간에 해결될 수 있는지 물었습니다.
두 모델 모두 서로 다른 알고리즘에 대한 증명을 만들어내며 격차가 없다고 자신 있게 말했습니다! SNR이 2 log N 이상일 때 성공하는 다항 시간 알고리즘이 있으며, 이는 ML 복구 임계값과 정확히 일치합니다(로그로그 항까지의 덧셈 차이는 있지만 누가 신경 쓰겠어요).
하지만 작은 문제가 있었습니다 😊 GPT의 알고리즘은 AMP 변형이었습니다. 그리고 저는 AMP를 몹시 싫어합니다. 그 분석을 도저히 이해할 수 없기 때문입니다. 그래서 가능하다면 더 단순한 알고리즘으로 같은 결과를 다시 증명해 보라고 말했습니다. 실제로 GPT는 제가 직관에 반한다고 느끼고, 이전에 사용된 적이 없는 또 다른 알고리즘을 만들어냈습니다!
반면에 Fable은 제가 정말 마음에 드는 것을 제안했습니다:
부호 있는 LMMSE(signed LMMSE), 그 다음 탐욕적 비트 플립(greedy bit flips). 과거에 소개되어 실제로 사용된 적이 있는 알고리즘입니다.
하지만 또 다른 문제가 있었습니다! GPT에 따르면 Fable의 증명은 대부분 틀렸지만.. 구제할 수 있다는 것입니다. 그래서 저는 Fable이 제안한 알고리즘을 유지하기로 하고, GPT에게 Fable의 증명을 가져다가 고쳐 달라고 요청했습니다. 그리고 해냈습니다!
하지만 또 다른 문제가 있었습니다. 이 새로운 증명은 읽을 수 없을 정도로 난해했습니다: 표기법의 벽, 변수를 가리키는 변수가 다른 변수를 정의하는 변수의 비율을 가리키고, 이국적인 행렬 분석과 확률 기법, 두드러기를 일으키는 Marchenko–Pastur 관련 것들, 그리고 다른 아름다운 것들로 가득 차 있었습니다.
그래서 약 4~5일 동안 두 모델 사이를 오가며 증명에 필요한 각각의 큰 구성 요소에 대해 가장 단순한 단계 세트를 달라고 요청했습니다. 2 log N 임계값만 유지된다면 경계와 상수가 나빠져도 괜찮다고 명시적으로 말했습니다. 오직 단순함을 위해서였습니다.
제가 원한 것은 주의 집중 시간이 짧은 늙은 공룡이 울지 않고 소화할 수 있는 증명이었습니다.
실제로 GPT와 Claude에게 제가 가장 투덜거렸던 메시지를 공유해 달라고 요청했습니다. ㅋㅋ
제가 가장 좋아하는 것:
왜 매우 단순한 단계를 고집했을까요? 직접 끝까지 검증하고 싶었기 때문입니다. 그리고 아닙니다. Lean을 사용하고 싶지 않습니다. 그것은 제 문제를 해결하지 못합니다! 형식 검증은 추상화 수준을 다른 곳으로 옮길 뿐입니다!! 보조 정리의 영어가 Lean으로 충실히 번역되는지 여전히 검증해야 하는데, 저는 그 언어를 이해하지 못합니다.
네, 잊어버리세요. 저는 Lean을 좋아하지 않습니다. 죄송합니다.
하지만 저는 기본적인 선형대수와 확률론은 이해하고, 그런 단계를 스스로 검증할 수 있다고 믿습니다. 그래서 그것이 제가 요구하는 증명의 수준입니다.
그 후 며칠 동안 계속해서 프롬프트를 입력하고 또 입력하고 또 입력하면서, 모델들이 서로의 논증을 단순화하는 동안 저는 계속 불평하고 이해할 수 없는 것은 모두 거절했습니다.
그리고 결국 성공했습니다! 완전히 이해할 수 있고, 이제 줄 단위로 확인한 증명을 얻었습니다.
문제를 증명하는 데는 30분이 걸렸고, 제가 검증할 수 있게 만드는 데는 약 5일이 걸렸습니다. 다소 말도 안 되는 비율이지만, 그런가 보다 했습니다. 그리고 결과는: 최대우도가 작동할 때마다 단순한 알고리즘이 다항 시간에 작동한다는 것입니다. 이 문제에는 계산-통계적 격차가 없습니다.
BOOM!
**
증명의 높은 수준 개요는 무엇인가?
알고리즘은 거의 부끄러울 정도로 단순합니다. 하지만 왜 작동할까요? LMMSE 후 반올림을 하면 해밍 거리 기준으로 전송된 신호에서 0으로 수렴하는 비율, 즉 진실에서 o(N) 이내에 도달합니다.
그런 다음, 탐욕적 비트 플립은 멈출 수 없습니다. 각 단계의 하강 이득(즉, 비용이 얼마나 개선되는지)이 가우시안 양에 의해 지배되고, 그 균일한 집중은 특정 공 안의 모든 정답이 아닌 벡터가 보장된 크기의 엄격한 개선 비트 플립을 제공한다는 것을 확립합니다. 즉, 무엇을 하든 0에서 멀리 떨어진 양만큼 확실히 개선됩니다.
그러나 모든 탐욕 단계에서 비용을 개선하는 것이 진실과의 해밍 거리가 매 단계마다 개선된다는 것을 의미하지는 않습니다. 실제로 일시적으로 더 나빠질 수 있습니다. 하지만 훨씬 나빠지지는 않습니다. 비용 함수는 진실과의 해밍 거리가 증가함에 따라 커지기 때문입니다. 즉, 충분히 멀리 떨어진 어떤 지점도 알고리즘이 시작한 지점보다 훨씬 더 많은 비용이 들고, 비용이 감소하는 경로는 결코 거기에 갈 수 없습니다. 탐욕 알고리즘은 해밍 거리 공 안을 돌아다닐 수 있지만, 경로를 공 안에 가두는 "비용 장벽"에 묶여 있습니다.
따라서 1) 각 단계는 0에서 멀리 떨어진 양만큼 비용을 개선하고 2) 시작 비용은 최적값보다 훨씬 높지 않습니다. 따라서 탐욕 실행은 결국 멈춰야 하며, 두 양을 서로 나누면 필요한 단계 수인 NlogN이 나옵니다.
더욱이, 탐욕 알고리즘은 정답 외에는 어디에서도 끝날 수 없습니다. 공 안의 다른 모든 지점에서는 어떤 비트 플립이 여전히 개선을 제공하며, 알고리즘은 거기서 멈추는 것이 허용되지 않기 때문입니다. 멈출 수 있는 유일한 곳은 전송된 벡터입니다.
핵심 논증을 멋지게 시각화한 그림이 있습니다:
중요한가?
무선 통신 학계는 이미 다음 주제로 나아갔고 저도 마찬가지입니다. 하지만 이것은 진정으로 중요한 질문이었습니다. 이 결과가 2010년경에 나왔다면 어떤 의미가 있었을지 추측할 수 있습니다: ISIT 또는 CommSoc/IT Society 최우수 논문상, 그리고 아마도 MIT, 버클리, 스탠퍼드에서의 인터뷰. 박사 과정 학생으로서 그것은 결과의 성배와도 같았고, 제 짧은 정보 이론 경력의 하이라이트였을 것이라고 자신 있게 말할 수 있습니다.
그런데.. 학계는 대부분 이미 다른 곳으로 옮겨갔습니다 😊
이처럼 한때 중요했고 전체 학계가 수십 년을 매달렸던 문제가 엄청나게 많습니다. 그러다 연구 분야가 나아가면서 천천히 중요하지 않게 되었고, 불가능해서가 아니라 사람들이 서서히 관심을 잃었기 때문에 열린 채로 남겨졌습니다.
그래서 사람들이 "N년 된 문제가 AI에 의해 해결되었다"고 말할 때, 저는 그것이 무엇을 의미하는지 해석하려고 노력할 것입니다.
하지만 이 모든 것에는 엄청나게 멋진 점이 있습니다: 이제 어린 시절에 관심을 가졌던 그 문제들로 돌아가서 데스 스타를 겨눌 수 있습니다. 한때 전체 연구 커뮤니티의 모든 힘에 맞서 버텼던 질문들이 이제는 문헌 우주의 버려진 구석에서 조용히 무방비 상태로 앉아 데스 스타가 발사되기를 기다리고 있습니다. 그리고 그 비용은 한 달에 200달러입니다.
미친 시대입니다..
어쨌든, 현재 초안을 arXiv에 게시할 예정이지만, 학술지에 제출할지는 확실하지 않습니다(지금 적절한 학술지가 무엇인지도 확실하지 않습니다). 누군가의 시간을 낭비하고 싶지도 않습니다. 하지만 읽어보고 오류를 발견하시면 알려주시면 감사하겠습니다. 😊
이제 우리는 이것을 압니다:
MIMO ML 검출은 가능할 때마다 쉽습니다!
만세…
**
부록
위 증명에 대해 주목할 만한 점이 하나 있습니다: 새로운 수학이 발명되지 않았습니다.
2010년에 존재하지 않았던 새로운 부등식, 기법 또는 수학적 대상이 없습니다. 증명은 길지만 기초적이며, 그 어려움은 개념적이라기보다는 적절한 세분성과 적절한 시기에 20페이지의 표준 단계를 구성하여 완벽하게 맞물리게 하는 데 필요한 노력과 관련이 있습니다.
이 생각을 한 걸음 더 나아가면, 해결에 새로운 수학이 전혀 필요하지 않고 알려진 아이디어를 누구도 기꺼이 쓰려 하지 않을 만큼 긴 토큰이나 시간에 걸쳐 함께 엮는 것만 필요한 문제들의 한 부류를 정의하게 된다고 생각합니다. 많은 것을 시도해보다가 뭔가 맞는 것이 나올 때까지 하는 것은 정확히 AI가 엄청나게 잘하는 일이기 때문에, 이 문제들은 빠르게 AI에게 무너질 것입니다. 그리고 아마도 "알려진 것들을 충분히 오래 시도한 사람이 아무도 없었다"는 것이 우리가 생각하는 것보다 훨씬 더 많은 열린 문제를 설명할지도 모릅니다.
이어서 하나의 사고 실험을 해보겠습니다: GPT-5.6이나 Fable을 2005년으로 데려갈 수 있다고 가정해 보세요. 동일한 RL 플롭스(FLOPs), 하지만 그때까지 존재했던 사전학습 데이터만 있다면 말입니다. 그들은 여전히 문제를 풀 수 있을까요?
모르겠습니다. 반사실을 실행하기는 어렵지만, 많은 도구들이 아마 2005년에 존재했을지라도 모델이 "맞다고 느끼는" 기법을 선택하게 만드는 "끌림"은 특정 방법의 인기와 특정 맥락에서 아이디어가 사용된 빈도에 기록된 우리의 집단적 직관에 크게 의존할 수 있습니다. 2005년 사전학습 모델은 RL 플롭스 부족이 아니라 올바른 아이디어 집합으로의 사전학습 끌림 부족으로 어려움을 겪을 수 있습니다. 이는 이러한 모델들이 단순한 수학적 진리의 신탁보다 훨씬 더 흥미로운 것임을 암시합니다. 우리는 그것들을 RL에 의해 더욱 날카로워진 우리의 축적된 직관의 증류(distillation)로 생각해야 할지도 모릅니다.
마지막 생각 하나로 마무리하겠습니다:
제가 시간을 거슬러 2009년의 불안한 제 자신에게 "형, 진정해. 너는 17년 후에 ML MIMO 검출의 해결 가능성을 해결하는 데 관여하게 될 거야"라고 말할 수 있다고 가정해 보세요. 다른 것은 아무것도 없이요. 과거의 나는 완전히 정신이 나갔을 것이고, 어떻게 그렇게 되었는지 알아내려고 그때 유일하게 합리적인 결론을 내렸을 것입니다: 나는 앞으로 15년 동안 정보 이론에 남아, 아마도 MIMO 검출에 매달렸거나, 좋게 봐줘야 정수 최적화를 했을 것이고, 어딘가에서 어떻게든 2026년쯤에는 이진 최소 제곱이 마침내 나의 엄청난 지성의 무게 아래 무너질 것이라고요.
젠장… 그때 느꼈을 선험적 자부심이란.
어린 Dimitris가 그 우주의 비트와 현재 우리 우주의 비트 사이의 해밍 거리가 엄청나다는 것을 알았다면, 그리고 그 차이에 대해 우리가 감사해야 할 것은 ML이라고 불리는 또 다른 것의 돌파구 덕분이라는 것을 알았다면…
