Semana passada, o GPT-5.6 e o Claude Fable parecem ter resolvido 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 estudante de primeiro ano de doutorado, ansioso. 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 por um canal sem fio Gaussiano N×N, e o receptor precisa recuperar todos eles exatamente. Sabe-se desde os anos 2000 que é possível, em termos de teoria da informação, fazer isso 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 prova de que um algoritmo simples, de tempo polinomial, consegue ter sucesso 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 por um canal sem fio com N antenas transmissoras e N 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 ao encontrar o vetor mais provável de 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 de TCS, 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 a recuperação dos bits transmitidos é estatisticamente possível, conseguimos fazê-la em tempo polinomial?
Não avançamos muito nessa questão naquele artigo de 2010 mencionado acima e, apesar de bastante trabalho na área, o problema permaneceu, até onde entendo, em aberto desde 2001… ou seja, UM QUARTO DE SÉCULO, para soar mais dramático.
Até semana passada. E a resposta final é:
SIM! Sempre que a detecção perfeita é estatisticamente possível, você consegue fazê-la em tempo polinomial.
MIMO resolvido; Pronto.
Mas quem liga? Voltamos a isso já já.
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 ou algo assim). A prova é longa, mas relativamente elementar. Verifiquei tudo e, até onde minha capacidade de revisão alcança, ela está correta.
Agora deixe-me falar um pouco mais sobre o problema e sua história, e por que acho que vale a pena escrever sobre ele mesmo que a área tenha seguido em frente a partir desse canto específico da teoria de detecção MIMO.
A configuração do 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 conhece w, e quer x de volta 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 roupagens: 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 a partir do ruído, e a detecção ML falha.
Mas em algum lugar entre 0 e infinito, a detecção ML tem sucesso, e isso acontece 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 transmitida de N bits 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 por todas as sequências possíveis de N bits. Portanto, a questão que nos importa agora é:
Um algoritmo de tempo polinomial consegue recuperar o x transmitido quando a ML tem sucesso?
**
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.
Hassibi e Vikalo em 2001 foram os primeiros — até onde 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 produz o minimizador, e 2) parecia ser muito mais rápido do que tempo exponencial na prática.
Então a esperança era que alguém pudesse de fato provar que o SD roda em tempo polinomial. Foi o que H&V articularam no artigo deles: eles derivaram uma fórmula para a complexidade esperada do Sphere Decoder, calculando a média sobre o canal e o ruído, e mostraram que ela parece polinomial. Se isso fosse verdade, a questão estava 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 quão grande, a complexidade esperada da decodificação por esfera é de fato exponencial na dimensão do problema.
Então, já que resolver de forma exata e rápida 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 (tightness) em SNR alto, mas sem um limiar nítido. Busca local por inversão de bits parecia igualar a ML em simulações, mas sem provas completas de igualar o limiar de recuperação da 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 a ML exata usando argumentos de nível réplica, mas, até onde entendo, 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 evanescente 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 relaxação de caixa (box relaxation), em 2020, que se mostrou capaz de recuperar o bloco quando a SNR escala como 4 log N e, comprovadamente, não abaixo disso. Aliás, é meio interessante que as ferramentas probabilísticas necessárias para analisar tal técnica tenham amadurecido no final dos anos 2010, o que, na maior parte, foi depois que a comunidade já tinha seguido em frente e se dispersado.
E desde então… não muita atividade.
Então, resumindo a história, a lacuna entre o que a ML alcança e o que qualquer método de tempo polinomial poderia alcançar comprovadamente nunca foi fechada.
**
O que GPT e Claude fizeram e como chegamos a uma prova que eu, Dimitris, consigo verificar?
Motivado pelos recentes irracionais sucessos dos modelos de fronteira em problemas matemáticos 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 fazer perguntas matemáticas difíceis e ver o GPT resolvê-las de primeira:
GIF
Mas eu sabia que havia um pequeno problema. Mesmo se eu recebesse uma resposta completa para qualquer pergunta que fizesse, eu seria limitado pelo gargalo de ter que verificá-la se quisesse compartilhá-la de forma mais ampla. Primeiro, porque não quero passar vergonha se ela estiver errada; e segundo, porque compartilhar é a principal razão pela qual fazemos perguntas e fazemos ciência, de qualquer forma.
Então decidi escolher o que parecia ser uma das perguntas mais ambiciosas que me incomodaram no início do doutorado, e que fosse limpa de enunciar e ainda estivesse 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 tem sucesso com SNR acima de 2 log N, igualando exatamente (até termos aditivos de loglog, mas quem liga) o limiar de recuperação da ML.
Mas havia um pequeno problema 😊 O algoritmo do GPT era uma variante de AMP. E eu odeio AMP, com todas as minhas forças, porque não consigo, de jeito nenhum, entender nenhuma das suas análises. Então pedi que ele 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 vi usado antes!
Fable, por outro lado, surgiu com algo de que gostei muito:
LMMSE com sinal, depois 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 tinha conserto. 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 belezuras.
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 burro possível para cada um dos grandes componentes necessários para que a prova funcionasse. Disse a eles explicitamente que tudo bem se as cotas e constantes piorassem, CONTANTO que o limiar de 2 log N se mantivesse, tudo em nome da simplicidade.
Tudo o que eu queria era uma prova que um dinossauro velho 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 reclamei, kkk
Minha favorita:
Por que eu insistia em passos super simples? Porque eu queria verificar isso eu mesmo, de ponta a ponta. E não, não quero usar Lean; isso NÃO resolve meu problema. Verificação formal apenas move o nível de abstração para outro lugar!! Você ainda precisa verificar se o inglês de um lema é traduzido fielmente para Lean, que é uma língua que eu não entendo.
É, esquece. Não gosto de Lean, desculpa.
Mas eu entendo álgebra linear básica e probabilidade, e confio em mim mesmo para verificar tais passos. Então esse é o nível de prova que exijo.
Foram então 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! Terminamos com uma prova que entendo completamente e que agora verifiquei linha por linha.
Provar a coisa levou 30 minutos e torná-la verificável para 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 coloca você, em termos de distância de Hamming, dentro de uma fração evanescente do sinal transmitido, ou seja, a o(N) da verdade.
Então, a inversão de bits gulosa não pode ficar presa porque os ganhos de descida por passo (ou seja, o quanto o custo melhora) são governados por quantidades Gaussianas, e a concentração uniforme delas 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ê certamente melhora por uma quantidade limitada por uma constante positiva.
No entanto, melhorar o custo a cada passo guloso não significa que a distância de Hamming até a verdade melhore a cada passo. De fato, ela pode piorar temporariamente. Mas não muito pior, porque a função de custo cresce à medida que 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á preso 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 limitada por uma constante positiva, e 2) o custo inicial não está muito acima do ótimo. Portanto, a execução gulosa eventualmente precisa parar, e dividindo as duas quantidades uma pela outra, obtém-se o número de passos necessário, que é NlogN.
Além disso, o guloso não pode terminar em nenhum outro lugar senão na solução verdadeira: em qualquer outro ponto dentro da bola, alguma inversão de bits ainda oferece melhora, e o algoritmo não tem permissão de 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 do ISIT ou da CommSoc/IT Society, e talvez entrevistas em MIT, Berkeley e Stanford. Diria com confiança que, como estudante de doutorado, isso teria sido o santo graal de um resultado, e o auge da minha breve carreira em teoria da informação.
Mas.. a área em grande parte seguiu em frente 😊
Há uma tonelada de problemas assim que costumavam importar e nos quais comunidades inteiras passaram décadas. Então, lentamente, deixaram de importar conforme as áreas de pesquisa evoluíram, e ficaram em aberto e abandonados, não porque fossem impossíveis, mas porque as pessoas lentamente deixaram de se importar.
Então, quando as pessoas dizem "problema de N anos resolvido por IA", eu tentaria interpretar o que isso significa.
Ainda assim, há algo incrivelmente legal em tudo isso: você agora pode voltar àqueles problemas com os quais se importava quando criança e apontar a Estrela da Morte para eles. Questões que resistiam à força total de uma comunidade de pesquisa inteira e que agora estão quietas e indefesas, num canto abandonado do universo da literatura, esperando a Estrela da Morte atirar nelas; e o custo disso é 200$/mês.
Tempos loucos..
De qualquer forma, vou publicar o rascunho atual no arXiv, mas não sei se vou submeter a algum veículo (nem sei qual seria o veículo apropriado agora). Também não quero desperdiçar o tempo de ninguém. Mas se você ler e encontrar algum 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.
Não há novas desigualdades, técnicas ou objetos matemáticos que não existissem 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 mais tempo do que qualquer um jamais esteve disposto a gastar. Esses problemas sucumbirão rapidamente à IA, porque tentar um monte de coisas até algo se encaixar é exatamente o que a IA faz de incrível. E talvez, "ninguém tentou as coisas conhecidas por tempo suficiente" descreva muito mais problemas em aberto do que imaginaríamos.
Dando sequência 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 qual técnica escolher que o modelo "sente como certa" pode depender muito da popularidade de um dado método e do nosso instinto coletivo, tal como registrado na frequência com que uma ideia é usada num 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 de verdade. Talvez devêssemos pensar neles como destilações dos nossos instintos acumulados, ainda mais aprimoradas 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 participar da resolução da solubilidade da detecção MIMO ML daqui a 17 anos", e nada mais. Meu eu do passado teria absolutamente enlouquecido e, tentando descobrir como ele chegaria lá, teria tirado a única conclusão razoável na época: que eu devo ter permanecido na teoria da informação pelos próximos quinze anos, provavelmente moendo em detecção MIMO, ou, no melhor dos cenários, em otimização inteira, e que em algum lugar, de alguma forma, por volta do ano de 2026, mínimos quadrados binários finalmente sucumbiriam ao peso do meu tremendo intelecto.
Caramba… 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 os do nosso atual é gigantesca, e que por isso temos que agradecer aos avanços de outra coisa chamada ML…
