🤖 machine learning

Quotient Tree Arithmetic: Deferred-Division Computation with Bounded Symbolic Depth and Cross-Subtree Cancellation

Este artigo introduz a Aritmética de Árvore de Quocientes (QTA), um arcabouço computacional que representa valores como pares de quocientes adiados para alcançar aritmética racional exata, profundidade simbólica limitada e cancelamento entre subárvores, reduzindo significavelmente erros numéricos e sobrecarga de memória no treinamento de aprendizado de máquina ao conectar a teoria da localização algébrica com a aritmética IEEE nativa de hardware.

Autores originais: Gregory Magarshak

Publicado 2026-07-28

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Gregory Magarshak

Artigo original sob licença CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta é uma explicação gerada por IA do artigo abaixo. Não foi escrita nem endossada pelos autores. Para precisão técnica, consulte o artigo original. Ler aviso legal completo

Imagine que você está tentando medir o mundo com uma régua que possui uma pequena falha invisível. Por décadas, cientistas e programadores de computador têm usado uma ferramenta de medição padrão chamada "aritmética de ponto flutuante" para fazer cálculos em computadores. Ela é incrivelmente rápida e funciona para quase tudo, desde o cálculo de trajetórias de foguetes até o treinamento da IA que recomenda sua próxima música favorita. Mas ela tem um erro famoso e irritante: não consegue lidar com certos números simples perfeitamente. Se você pedir a um computador para somar 0,1 e 0,2, ele não lhe dará exatamente 0,3; ele lhe dará 0,30000000000000004. É como tentar cortar uma pizza em fatias perfeitas com uma faca cega; eventualmente, as migalhas se acumulam e suas fatias não ficam iguais. Esse erro minúsculo pode causar grandes problemas, como uma IA ficando confusa porque seus cálculos internos se afastam, ou um sistema financeiro perdendo o controle de um centavo.

Para corrigir isso, as pessoas geralmente usam ferramentas "decimais" especiais que são mais lentas, ou usam matemática "simbólica" que é super precisa, mas incrivelmente pesada e lenta, como tentar carregar uma biblioteca em sua mochila apenas para comprar um café. A grande questão sempre foi: Podemos obter a velocidade da régua rápida e falha e a precisão perfeita da ferramenta pesada e lenta ao mesmo tempo? É este o enigma que um novo artigo de Gregory Magarshak tenta resolver. Ele propõe um truque inteligente que transforma a matemática padrão do computador em um sistema de frações perfeitas, mantendo a velocidade do hardware enquanto elimina os pequenos erros que costumam surgir.

O artigo introduz um sistema chamado Aritmética de Par Racional (RPA). Em vez de armazenar um número como 0,3 como um único decimal levemente impreciso, o computador o armazena como um par de números inteiros: um numerador (3) e um denominador (10). Pense nisso como guardar uma receita como "3 xícaras de farinha divididas por 10" em vez de escrever "0,3 xícaras". A mágica acontece porque os computadores modernos são, na verdade, muito bons em lidar com números inteiros perfeitamente, desde que não sejam grandes demais. O artigo aponta que os computadores podem lidar com qualquer número inteiro até cerca de 9 quatrilhões ( $9 \times 10^{15}$ ) sem cometer um único erro. Como a maioria das medições do mundo real (como dinheiro, coordenadas de GPS ou dados científicos) cabe confortavelmente dentro desse enorme intervalo, o computador pode realizar todos os seus cálculos usando esses pares de números inteiros perfeitos.

O sistema funciona adiando a divisão final. Quando você soma ou multiplica esses pares, o computador apenas faz a conta nos números de cima e de baixo separadamente, mantendo a fração "não simplificada" até que ele absolutamente precise mostrar o resultado decimal. Para evitar que os números fiquem grandes demais e bagunçados, o sistema possui uma etapa de "limpeza". Imagine que você tem uma fração como 6/10; a etapa de limpeza a simplifica instantaneamente para 3/5, dividindo ambos pelo seu maior divisor comum. O artigo sugere que os chips de computador deveriam ter um botão especial e super-rápido para realizar essa limpeza instantaneamente, tornando todo o processo quase tão rápido quanto a matemática padrão e falha.

Ainda mais legal, o artigo mostra que esses pares podem ser empilhados uns dentro dos outros, como bonecas russas. Você pode ter uma fração onde o topo ou a base é, por si só, outra fração. Isso cria uma "árvore" de matemática que o computador pode manter em sua memória sem calcular a resposta final imediatamente. Isso é um divisor de águas para o aprendizado profundo (o tipo de IA que alimenta carros autônomos e chatbots). Nesses sistemas de IA, um problema comum é o "gradiente evanescente", onde a matemática fica tão minúscula após muitas camadas de cálculo que ela efetivamente desaparece, fazendo com que a IA pare de aprender. O artigo prova que, como este novo sistema usa números inteiros exatos, a matemática nunca poderá encolher acidentalmente para zero, a menos que seja verdadeiramente zero. É como ter uma escada que nunca perde um degrau, não importa o quão alto você suba.

Os autores também mostram que este método torna os resultados do computador perfeitamente previsíveis. Atualmente, se você rodar o mesmo treinamento de IA em dois tipos diferentes de placas de vídeo, poderá obter resultados ligeiramente diferentes devido à forma como elas lidam com erros de arredondamento. Com este novo sistema, se você seguir os mesmos passos, obterá exatamente a mesma resposta todas as vezes, em qualquer máquina. O artigo não afirma que isso é uma solução mágica para tudo; admite que, para cadeias extremamente longas de multiplicação sem a etapa de "limpeza", os números poderiam ficar grandes demais para o computador lidar. Mas para a maioria dos usos práticos, sugere uma maneira de tornar a computação científica e o treinamento de IA exatos, estáveis e reproduzíveis sem sacrificar muita velocidade. É uma proposta para atualizar o próprio fundamento de como os computadores fazem matemática, transformando um sistema que adivinha em um que sabe.

Resumo Técnico: Aritmética de Árvore de Quocientes (QTA)

Declaração do Problema

A aritmética de ponto flutuante (IEEE 754), embora seja o padrão para computação científica e aprendizado de máquina há décadas, sofre de limitações fundamentais:

Representação Inexata: Valores decimais comuns (ex: 0,1) não podem ser representados exatamente, levando a erros como $0,1 + 0,2 \neq 0,3$ .
Subfluxo (Underflow) e Gradientes Desvanecentes: Valores ínfimos arredondam para zero, causando o problema do gradiente desvanecente em redes neurais profundas, onde os produtos de gradientes colapsam para zero.
Não Determinismo: Os resultados variam entre hardware, versões de compiladores e ordenação de operandos devido a modos de arredondamento e disponibilidade de FMA (Fused Multiply-Add).
Heurísticas de Comparação: Verificações de igualdade exigem tolerâncias $\epsilon$ arbitrárias, que são pouco confiáveis.

Remédios existentes, como bibliotecas de precisão arbitrária (GMP, Decimal), impõem custos severos de desempenho, enquanto a quantização (INT8, FP8) sacrifica a precisão e introduz erros sistemáticos.

Metodologia

O artigo propõe a Aritmética de Par Racional (RPA) e sua extensão, a Aritmética de Árvore de Quocientes (QTA), como um framework unificado para computação exata e quase exata.

1. Aritmética de Par Racional (RPA)

A ideia central baseia-se na Janela de Exatidão Inteira IEEE 754: os floats de precisão dupla IEEE 754 representam todos os inteiros no intervalo $(-2^{53}, 2^{53})$ de forma exata.

Representação: Quantidades de valor real são armazenadas como pares ordenados $(n, d)$ de doubles IEEE, tratados estritamente como inteiros. O valor é $n/d$ , avaliado de forma preguiçosa (lazy).
Aritmética: As operações são realizadas nos componentes inteiros:
- $(a, b) + (c, d) = (ad + bc, bd)$
- $(a, b) \times (c, d) = (ac, bd)$
- A comparação é realizada via multiplicação cruzada ($ad < bc$).
Exatidão: Enquanto $|n|, |d| < 2^{53}$ , toda a aritmética é exata sem bibliotecas de multiprecisão. Isso cobre domínios práticos como moeda (até $\approx \$ 90$ bilhões em centavos) e medições científicas.

2. A Operação de Limpeza (Cleanup)

Para evitar que as magnitudes do numerador e do denominador cresçam indefinidamente (o que excederia a janela de $2^{53}$ ), o sistema emprega uma operação de Limpeza (Cleanup):

Mecanismo: Divide-se tanto $n$ quanto $d$ pelo $\gcd(|n|, |d|)$ .
Proposta de Hardware: O artigo propõe uma nova instrução SIMD, RatCleanup, para realizar a redução vetorizada de GCD, tornando a RPA competitiva com floats de precisão simples em termos de vazão (throughput).
Cancelamento Rastreado: Para computações estruturadas (ex: denominadores fixos em moeda), o compilador pode cancelar fatores sem um algoritmo de GCD completo, reduzindo o custo para $O(1)$ .

3. Aritmética de Árvore de Quociente (RPA Aninhada)

O framework estende-se para Pares Racionais Aninhados, onde numeradores ou denominadores podem ser, eles próprios, pares racionais, formando uma árvore de expressão simbólica.

Avaliação Adiada (Deferred Evaluation): Expressões são mantidas como árvores. A avaliação (achatamento para um único par) é adiada até que um resultado de ponto flutuante concreto seja explicitamente solicitado.
Profundidade Limitada: O Teorema 4.2 prova que a profundidade da árvore cresce no máximo 1 por operação aritmética ( $O(m)$ de tamanho total para $m$ operações), evitando a explosão combinatória ( $O(2^m)$ ) vista em sistemas de álgebra simbólica genéricos.
Cancelamento Cruzado: O Teorema 4.3 estabelece que fatores comuns aparecendo tanto nas subárvores do numerador quanto do denominador podem ser cancelados simbolicamente antes de qualquer divisão ocorrer. Isso se aplica mesmo a valores transcendentais (ex: $e^x$ ), se forem referencialmente iguais.

Principais Contribuições

Definição Formal de RPA: Explora a janela de exatidão inteira IEEE 754 para criar um tipo racional de largura fixa e acelerado por hardware.
A Primitiva de Limpeza: Uma proposta de instrução de hardware (RatCleanup) e prova teórica de que ela mantém os valores dentro da janela de exatidão, garantindo a exatidão indefinidamente.
Álgebra de Par Racional Aninhado: Um tratamento formal de aninhamento simbólico com provas de crescimento de profundidade limitada, achatamento em $O(k)$ etapas e teoremas de cancelamento cruzado.
Teoremas de Estabilidade:
- Estabilidade Adiada: A avaliação adiada reduz o erro de arredondamento de $O(m)$ ULPs (avaliação imediata) para $O(1)$ ULPs.
- Impossibilidade de Desvanecimento de Gradiente (Teorema 8.1): Sob RPA com limpeza, é estruturalmente impossível que um produto de pares racionais não nulos seja zero. Isso elimina o subfluxo aritmético em gradientes de redes profundas.
Determinismo Cross-Hardware: Dada uma ordem de computação fixa, os resultados da RPA são independentes de modos de arredondamento de hardware, disponibilidade de FMA ou versões de drivers.

Resultados e Alegações

O artigo fornece provas teóricas e estimativas analíticas em vez de benchmarks empíricos:

Vazão (Throughput): Estimativas analíticas sugerem que a RPA plana é $\sim 5\text{--}18\times$ mais lenta que FP32 (dependendo da operação e do custo de limpeza), mas comparável a FP64. Com a instrução proposta RatCleanup, o overhead é gerenciável para aplicações de alta precisão.
Estabilidade de Gradiente: A impossibilidade estrutural de gradientes desvanecentes permite a viabilidade teórica de redes "puras" muito profundas (centenas de camadas) sem conexões de salto (skip connections) ou mecanismos de portão (gating), desde que a aritmética permaneça dentro da janela de exatidão.
Convergência Exata: Critérios de convergência podem ser definidos como igualdade exata ( $L_t = L_{t-1}$ ) em vez de limiares heurísticos ( $|L_t - L_{t-1}| < \epsilon$ ).
Eficiência de Largura de Banda: Ao tratar a computação como uma fase simbólica (construção de árvore e cancelamento) seguida por uma fase numérica (materialização), a QTA reduz o tráfego de memória. Subárvores compartilhadas (ex: pesos) são carregadas uma única vez, e cancelamentos simbólicos eliminam escritas intermediárias na memória.

Significância

O artigo posiciona a QTA não apenas como um formato numérico, mas como um substrato computacional que desacopla a manipulação simbólica da avaliação numérica.

Inteligência Estrutural: Argumenta-se que os sistemas de IA modernos pagam um "custo de pior caso" para cada consulta. A QTA introduz uma camada de inteligência estrutural que explora propriedades algébicas (cancelamento, divisão adiada) para reduzir a computação real necessária, de forma semelhante ao cache ou à atenção esparsa, mas com garantias exatas.
Segurança e Certificação: Para domínios críticos de segurança (veículos autônomos, IA médica), a capacidade de fornecer derivadas certificadas (provas exatas de estacionariedade) e treinamento reproduzível é uma mudança de paradigma em relação às heurísticas probabilísticas.
Independência de Hardware: Oferece um caminho para a computação científica determinística, eliminando o "apodrecimento de bits" (bit-rot) de resultados através de diferentes gerações de GPUs ou versões de CUDA.

Os autores concluem que, embora a RPA troque vazão bruta por exatidão, essa troca é essencial para a computação científica e o aprendizado de máquina de segurança crítica, onde o custo do erro é maior do que o custo da computação. A instrução proposta RatCleanup é identificada como o habilitador chave para tornar este framework prático nas arquiteturas de hardware existentes.