Na semana passada, o GPT-5.6 e o Claude Fable aparentemente resolveram uma questão teórica em aberto em comunicações sem fio que foi intensamente estudada entre 2000 e os anos 2010 e na qual trabalhei brevemente como um ansioso estudante de doutorado de primeiro ano. A resposta finalmente chegou, talvez porque eu tenha sido um dos últimos a fazer a pergunta e o primeiro a pedir que as máquinas a resolvessem 😊
O resultado: você envia N bits através de um canal sem fio gaussiano N×N, e o receptor precisa recuperar todos exatamente. Sabe-se desde os anos 2000 que isso é teoricamente possível em termos de informação quando a relação sinal-ruído é de pelo menos 2 log N. Mas o único método conhecido para alcançar isso era um algoritmo de busca exponencial. Agora existe a prova de que um algoritmo simples, de tempo polinomial, funciona no exato mesmo limiar.
Deixa eu contar um pouco mais sobre isso.
Em 2009, trabalhei no meu primeiro artigo com Alex Dimakis (@AlexGDimakis), que logo depois se tornou meu orientador de doutorado (não por causa daquele artigo):
O artigo estava entre muitas tentativas de oferecer uma solução em tempo polinomial para a detecção MIMO.
O que é detecção MIMO, você pergunta?
Um transmissor envia um vetor de N bits através de um canal sem fio com N antenas transmissoras e N antenas receptoras. O canal mistura todos os bits e adiciona ruído. O receptor, que conhece a matriz do canal, precisa descobrir quais bits foram enviados.
O receptor ótimo em erro de bloco, também conhecido como detector de máxima verossimilhança (ML), resolve exatamente esse problema encontrando o vetor mais provável que poderia ter sido enviado, dado o sinal recebido. Nesse caso, a detecção ML se resume a resolver este problema fundamental de mínimos quadrados discretos:
Infelizmente, como todos os bons problemas da vida… a detecção ML é NP-difícil.
Mas não somos pessimistas da teoria da computação, e canais sem fio não são pior caso — eles são aleatórios — e a comunidade vinha trabalhando na seguinte questão desde o início dos anos 2000:
Quando recuperar os bits transmitidos é estatisticamente possível, conseguimos fazer isso em tempo polinomial?
Não fizemos muito progresso nessa questão naquele artigo de 2010 acima e, apesar de muito trabalho na área, o problema permaneceu em aberto, pelo que entendi, desde 2001… ou seja, UM QUARTO DE SÉCULO, para soar mais dramático.
Até a semana passada. E a resposta final é:
SIM! Sempre que a detecção perfeita é estatisticamente possível, você consegue fazer isso em tempo polinomial.
MIMO resolvido; pronto.
Mas quem se importa? Já volto a isso.
Estou anexando o artigo e passei mais de 5 dias indo e voltando com os modelos para simplificar as provas e a exposição (que originalmente era um desastre absoluto), um processo que levou muito, muito mais tempo do que a prova inicial que o GPT produziu (que levou cerca de 30 minutos). A prova é longa, mas relativamente elementar. Verifiquei tudo e, até onde minha capacidade de revisão alcança, está correta.
Agora deixa eu falar um pouco mais sobre o problema e sua história, e por que acho que vale a pena escrever sobre isso mesmo que a área tenha seguido em frente desse canto específico da teoria de detecção MIMO.
O problema
Então você transmite um vetor binário x em {±1}^N e recebe
y=SNRNHx+w{\bf y} = \sqrt{\frac{SNR}{N}}{\bf H}{\bf x}+{\bf w}
onde H é N×N e tanto H quanto w têm entradas iid N(0,1), todas independentes. O receptor conhece H e as estatísticas do ruído, mas não w, e quer recuperar x a partir de y. A solução ótima em erro de bloco para o problema de recuperação é igual a
A propósito, essa otimização também aparece sob diferentes disfarces: detecção MIMO, detecção multiusuário CDMA, mínimos quadrados inteiros, vetor mais próximo em um reticulado, etc. etc.
E quando SNR = ∞ (ou seja, ruído efetivo 0), o problema se torna trivial: a matriz do canal H é invertível com probabilidade 1, então você a inverte e recupera o x exato com inv(H)*y. No outro extremo, quando SNR = 0, não há nada que você possa detectar do ruído, e a detecção ML falha.
Mas em algum lugar entre 0 e infinito, a detecção ML funciona, e funciona precisamente em SNR = 2 log N. Isso significa que resolver o problema de otimização acima permite recuperar perfeitamente todos os bits da sequência de N bits transmitida com probabilidade tendendo a 1, e abaixo disso (até termos aditivos de loglogN) a probabilidade de recuperação do bloco tende a 0.
Então, acima de 2logN, o sinal transmitido é um ótimo do problema de otimização ML, mas resolvê-lo parece exigir uma busca exaustiva sobre todas as sequências possíveis de N bits. Então a questão que nos importa agora é:
Um algoritmo de tempo polinomial consegue recuperar o x transmitido quando o ML é bem-sucedido?
**
Uma breve história com um pouquinho de drama
A questão da solubilidade do problema de mínimos quadrados inteiros é pelo menos tão antiga quanto 1989, quando Verdú provou que ele é NP-difícil no caso geral. Mas NP-dificuldade é uma afirmação de pior caso, e nossas instâncias não são assim.
Hassibi e Vikalo em 2001 foram os primeiros — pelo que sei — a argumentar que há esperança de uma solução de caso médio em tempo polinomial. O algoritmo que eles analisaram era um método popular na época, o Sphere Decoder (SD), que remonta a Fincke e Pohst em 1985. O Sphere Decoder era de particular interesse porque 1) é um algoritmo ML exato, ou seja, sempre retorna o minimizador, e 2) parecia ser muito mais rápido do que o tempo exponencial na prática.
Então a esperança era que alguém pudesse provar que o SD roda em tempo polinomial. Foi o que H&V articularam no artigo deles: derivaram uma fórmula para a complexidade esperada do Sphere Decoder, calculada sobre a média do canal e do ruído, e mostraram que ela parece polinomial. Se isso fosse verdade, a questão estaria resolvida. Parecia um resultado incrível.
Então Jaldén e Ottersten, em 2005, mostraram que a interpretação assintótica não estava exatamente correta: para qualquer SNR fixo, não importa o quão grande, a complexidade esperada do sphere decoding é, na verdade, exponencial na dimensão do problema.
Então, já que o exato e rápido não estava funcionando, a área gastou um esforço considerável trabalhando em aproximações para o problema de otimização ML. Relaxações semidefinidas com garantias de aproximação e condições de aperto em SNR alto, mas sem limiar nítido. Busca local por inversão de bits parecia igualar o ML em simulações, mas sem provas completas de atingir o limiar de recuperação do ML. A literatura de AMP caracterizou rigorosamente o erro por bit, em SNR fixo, onde a recuperação de bloco não é possível. A física estatística produziu métodos de tempo polinomial que foram previstos para acompanhar o ML exato usando argumentos de nível de réplicas, mas, pelo que entendi, sem prova. E o artigo com Babak e Alex de 2010 acima analisou um método MCMC provando que, após a mistura, a distribuição estacionária coloca massa não-desprezível na solução correta, mas não provou nada sobre o tempo de mistura, que é a parte difícil.
Em todos esses anos, me parece, exatamente um método de tempo polinomial veio com garantias rigorosas de recuperação de bloco em qualquer escala de SNR: a box relaxation, em 2020, que recupera o bloco quando o SNR escala como 4 log N e, comprovadamente, não abaixo. Paralelamente, é interessante que as ferramentas probabilísticas necessárias para analisar tal técnica amadureceram no final dos anos 2010, ou seja, na maior parte, depois que a comunidade já tinha seguido em frente e se dispersado.
E desde então… não houve muita atividade.
Para resumir a história, a lacuna entre o que o ML alcança e o que qualquer método de tempo polinomial poderia alcançar comprovadamente nunca foi fechada.
**
O que o GPT e o Claude fizeram e como conseguimos uma prova que eu, Dimitris, consigo verificar?
Motivado pelos recentes irracionais sucessos dos modelos de fronteira em tarefas matemáticas difíceis, decidi voltar aos problemas que me assombravam como estudante de pós-graduação (eu costumava trabalhar com teoria da informação e codificação) e começar a apontar a Estrela da Morte para eles. É exatamente assim que se sente ao fazer perguntas matemáticas difíceis e ver o GPT resolvê-las em zero shot:
GIF
Mas eu sabia que havia um pequeno problema. Mesmo se eu recebesse uma resposta completa para qualquer pergunta que fizesse, eu ficaria travado na necessidade de verificá-la se quisesse compartilhá-la mais amplamente. Primeiro, porque não quero me envergonhar se ela estiver errada, e segundo, porque compartilhar é o principal motivo pelo qual fazemos perguntas e fazemos ciência de qualquer forma.
Então, decidi escolher o que parecia ser uma das questões mais ambiciosas que me incomodaram no início do meu doutorado, e uma que era limpa de formular e ainda estava em aberto. Então, perguntei ao GPT-5.6 e ao Claude Fable 5 quando a detecção MIMO ML pode ser resolvida em tempo polinomial.
Ambos produziram provas para algoritmos diferentes, afirmando com confiança que não há lacuna! Existe um algoritmo de tempo polinomial que funciona com SNR acima de 2 log N, igualando exatamente (até termos aditivos de loglog, mas quem se importa) o limiar de recuperação do ML.
Mas havia um pequeno problema 😊 O algoritmo do GPT era uma variante de AMP. E eu odeio AMP, com paixão, porque não consigo, de jeito nenhum, entender nenhuma de suas análises. Então pedi a ele que tentasse reprovar o mesmo resultado, se possível, para um algoritmo mais simples. De fato, o GPT produziu outro algoritmo que também achei contraintuitivo, e um que nunca tinha visto ser usado antes!
Fable, por outro lado, surgiu com algo que eu realmente gostei:
LMMSE com sinal, seguido de inversões de bits gulosas. Um algoritmo que foi introduzido no passado e realmente usado na prática.
Mas havia outro problema! Segundo o GPT, a prova do Fable estava majoritariamente errada… mas era recuperável. Então decidi ficar com o algoritmo que o Fable sugeriu e pedi ao GPT que pegasse a prova do Fable e a corrigisse. E ele corrigiu!
Mas havia ainda outro problema: essa nova prova era ILEGÍVEL: uma parede de notação, variáveis apontando para variáveis que apontam para razões de variáveis que definem outras variáveis, maquinário exótico de análise de matrizes e probabilidade, coisas adjacentes a Marchenko–Pastur que me dão urticária, e outras coisas lindas.
Então, por cerca de 4 a 5 dias, fiquei indo e voltando entre os dois modelos e pedindo que me dessem o conjunto de passos mais idiota possível para cada um dos grandes componentes necessários para que a prova funcionasse. Disse explicitamente a eles que tudo bem se os limites e constantes piorassem, DESDE QUE o limiar de 2 log N se mantivesse, tudo em nome da simplicidade.
Tudo o que eu queria era uma prova que um velho dinossauro com pouca capacidade de atenção conseguisse digerir sem chorar.
Na verdade, pedi ao GPT e ao Claude que compartilhassem comigo as mensagens em que eu mais estava reclamando, kkkk
Minha favorita:
Por que insisti em passos super simples? Porque eu queria verificar isso eu mesmo, de ponta a ponta. E não, não quero usar o Lean — isso NÃO resolve meu problema. Verificação formal só move o nível de abstração para outro lugar!! Você ainda precisa verificar se o inglês de um lema se traduz fielmente para o Lean, que é uma linguagem que eu não entendo.
É, esquece. Eu não gosto do Lean, desculpa.
Mas eu entendo álgebra linear básica e probabilidade, e confio em mim mesmo para verificar tais passos. Então é nesse nível que eu exijo a prova.
Depois disso, levei vários dias de prompting, prompting e mais prompting, com os modelos simplificando os argumentos uns dos outros, enquanto eu continuava reclamando e rejeitando qualquer coisa que não conseguisse acompanhar.
E no final funcionou! Acabamos com uma prova que eu entendo completamente e que agora verifiquei linha por linha.
Provar a coisa levou 30 minutos e torná-la verificável por mim levou uns 5 dias. É uma proporção meio insana, mas é o que é. E o resultado: um algoritmo simples funciona sempre que a máxima verossimilhança funciona, em tempo polinomial. Não há lacuna computacional-estatística nesse problema.
BOOM!
**
Qual é a visão geral da prova?
O algoritmo é quase constrangedoramente simples. Mas por que isso funciona? LMMSE seguido de arredondamento te deixa, em termos de distância de Hamming, a uma fração desprezível do sinal transmitido, ou seja, a o(N) da verdade.
Então, a inversão gulosa de bits não pode travar porque os ganhos de descida por passo (ou seja, o quanto o custo melhora) são governados por quantidades gaussianas, e sua concentração uniforme estabelece que todo vetor que não é a solução verdadeira dentro de uma certa bola oferece uma inversão de bits estritamente melhoradora de tamanho garantido. Ou seja, não importa o que você faça, você definitivamente melhora por uma quantidade afastada de zero.
No entanto, melhorar o custo a cada passo guloso não significa que a distância de Hamming até a verdade melhora a cada passo. Na verdade, ela pode piorar temporariamente. Mas não muito, porque a função de custo cresce conforme você aumenta a distância de Hamming da verdade. Ou seja, qualquer ponto suficientemente distante custa muito mais do que onde o algoritmo começou, e um caminho cujo custo só diminui nunca pode chegar lá. O guloso pode vagar pela bola de distância de Hamming, mas está limitado por uma "barreira de custo" que mantém seu caminho dentro de uma bola.
Então 1) cada passo melhora o custo por uma quantidade afastada de zero e 2) o custo inicial não está muito acima do ótimo. Portanto, a execução gulosa precisa eventualmente parar, e dividindo uma quantidade pela outra, obtemos o número de passos necessários, que é NlogN.
Além disso, o guloso não pode terminar em nenhum lugar exceto na solução verdadeira: em qualquer outro ponto dentro da bola, alguma inversão de bits ainda oferece melhoria, e o algoritmo não pode parar ali. O único lugar possível para parar é o vetor transmitido.
Aqui está uma bela representação visual do argumento-chave
**
Isso importa?
A comunidade de comunicações sem fio seguiu em frente, e eu também. Mas essa era uma questão genuinamente importante. Posso especular o que esse resultado teria significado por volta de 2010: um prêmio de melhor artigo no ISIT ou na CommSoc/IT Society, e talvez entrevistas no MIT, em Berkeley e em Stanford. Diria com confiança que, como estudante de doutorado, isso teria sido um resultado de santo graal, e o auge da minha curta carreira em teoria da informação.
Mas… a área em grande parte seguiu em frente😊
Existe uma tonelada de problemas como esse que costumavam importar e nos quais comunidades inteiras passaram décadas. Então, aos poucos, deixaram de importar conforme os campos de pesquisa avançaram, e ficaram em aberto e abandonados, não porque fossem impossíveis, mas porque as pessoas aos poucos deixaram de se importar.
Então, quando as pessoas dizem "problema de N anos resolvido por IA", eu tentaria interpretar o que isso realmente significa.
Mas há algo incrivelmente legal em tudo isso: você pode voltar àqueles problemas pelos quais se importava quando criança e apontar a Estrela da Morte para eles. Questões que resistiram à força total de uma comunidade de pesquisa inteira e que agora estão sentadas quietas e indefesas, em um canto abandonado do universo das publicações, esperando a Estrela da Morte atirar nelas; e o custo disso é US$ 200/mês.
Tempos loucos..
De qualquer forma, vou postar o rascunho atual no arXiv, mas não sei se vou submeter a algum veículo (nem sei qual seria o mais adequado agora). Também não quero fazer ninguém perder tempo. Mas se você ler e encontrar um erro, adoraria saber. 😊
E então agora sabemos:
A detecção MIMO ML é fácil sempre que é possível!
Viva…
**
Adendo
Algo útil de se notar sobre a prova acima: nenhuma matemática nova foi inventada.
Nenhuma desigualdade, técnica ou objeto matemático novo que não existisse em 2010. A prova é longa, mas é básica, então sua dificuldade não é conceitual, mas sim relacionada ao esforço necessário para compor vinte páginas de passos padrão na granularidade certa e no momento certo para que todos se encaixem perfeitamente.
Acho que se levarmos esse pensamento um passo adiante, ele meio que define uma classe de problemas cuja solução exige zero matemática nova, mas apenas a montagem de ideias conhecidas unidas por longas sequências de mais tokens ou tempo do que qualquer um jamais esteve disposto a gastar. Esses problemas vão cair rapidamente para a IA, porque tentar um monte de coisas até algo clicar é exatamente o que a IA faz de incrível. E talvez "ninguém tentou o que já era conhecido por tempo suficiente" descreva muito mais problemas em aberto do que imaginamos.
Dando continuidade a isso, aqui vai um experimento mental: suponha que você pudesse levar o GPT-5.6 ou o Fable de volta a 2005, com os mesmos FLOPs de RL, mas com dados de pré-treinamento que só existiam até então. Eles ainda resolveriam o problema?
Não sei, é difícil rodar o contrafactual, mas mesmo que muitas das ferramentas provavelmente existissem em 2005, a "atração" para a técnica que o modelo "sente como certa" pode depender fortemente da popularidade de um determinado método e do nosso instinto coletivo, tal como registrado na frequência com que uma ideia é usada em um contexto particular. O pré-treinamento de 2005 poderia potencialmente ter dificuldades, não por falta de FLOPs de RL, mas por falta de atração do pré-treinamento para o conjunto certo de ideias. O que implica que esses modelos são algo muito mais interessante do que oráculos matemáticos da verdade. Talvez devêssemos pensá-los como destilações dos nossos instintos acumulados, ainda mais afiados por RL.
Um último pensamento e encerro com isto:
Suponha que eu pudesse viajar no tempo e dizer ao meu eu ansioso de 2009 "Irmão, relaxa, você vai estar envolvido em resolver a solubilidade da detecção MIMO ML daqui a 17 anos" e nada mais. Meu eu do passado teria absolutamente enlouquecido e, tentando descobrir como chegaria a isso, teria tirado a única conclusão razoável na época: que eu devia ter permanecido na teoria da informação pelos próximos quinze anos, provavelmente ralando em detecção MIMO, ou no melhor cenário, em otimização inteira, e que em algum lugar, de alguma forma, por volta do ano de 2026, os mínimos quadrados binários finalmente cedem sob o peso do meu intelecto tremendo.
Droga… o orgulho a priori que eu teria sentido.
Se ao menos o pequeno Dimitris soubesse que a distância de Hamming entre os bits daquele universo e o nosso atual é gigantesca, e por isso temos as descobertas de outra coisa chamada ML para agradecer…
