Algoritmos e Estruturas de Dados

Por que algoritmos e estruturas de dados importam em IA (AI)

Sistemas modernos de IA parecem “centrados no modelo”, mas seu desempenho e confiabilidade muitas vezes dependem de escolhas clássicas da ciência da computação: como os dados são representados, como o trabalho é escalonado (scheduling) e quais algoritmos são usados para buscar, otimizar e recuperar. A mesma rede neural (neural network) pode ser:

  • 10× mais lenta devido a um layout de memória (memory layout) ruim ou a uma implementação de atenção (attention) ineficiente
  • Cara demais porque a decodificação (decoding) na inferência (inference) escala mal com o comprimento da sequência
  • Imprecisa porque a recuperação (retrieval) é lenta ou retorna candidatos de baixa qualidade

Este artigo faz um panorama de algoritmos e estruturas de dados fundamentais usados em treinamento (training), inferência e recuperação, conectando fundamentos teóricos (complexidade (complexity), assintótica (asymptotics), algoritmos de grafos (graph algorithms)) a padrões práticos usados em sistemas contemporâneos de aprendizado profundo (deep learning) e de modelos de linguagem de grande porte (LLM systems).

Contexto relacionado: Complexidade, Computação Numérica, Noções Básicas de Sistemas Distribuídos, Busca.

Fundamentos centrais: complexidade, localidade e grafos

A complexidade assintótica (Big‑O) ainda prevê gargalos

Muitas cargas de trabalho de aprendizado de máquina (machine learning) são “apenas álgebra linear (linear algebra)”, mas peças críticas continuam sendo algorítmicas:

  • Autoatenção (self-attention) em transformadores (transformers) “vanilla” tem custo O(L²·d) em tempo e O(L²) em memória para comprimento de sequência L e tamanho oculto d — uma restrição fundamental de escalabilidade.
  • Recuperação de vizinho mais próximo (nearest neighbor retrieval) costuma ser O(N·d) por força bruta (N vetores), motivando métodos aproximados.
  • Busca em feixe (beam search) é tipicamente O(T · B · log B) para comprimento de sequência T e tamanho do feixe B (além do custo do forward do modelo).

À medida que os modelos escalam, você otimiza cada vez mais as partes que não são multiplicação de matrizes (matmul): indexação (indexing), amostragem (sampling), ordenação (sorting), cache e escalonamento. Veja Complexidade para intuição de tratabilidade.

Localidade e layout de memória são preocupações de primeira classe

Em GPUs/TPUs, o desempenho frequentemente é limitado pela largura de banda de memória (memory bandwidth), e não por operações de ponto flutuante (FLOPs). Estruturas de dados teoricamente equivalentes podem se comportar de forma muito diferente dependendo de:

  • Memória contígua vs. estriada (strided)
  • Layout row-major vs. column-major
  • Alinhamento e acesso coalescido
  • Reuso de cache (por exemplo, reuso do cache KV em transformadores)

Por isso muitos “algoritmos” em IA dizem respeito a movimentação de dados: tiling, blocking e fusão de kernels (kernels). Veja Computação Numérica para considerações sobre ponto flutuante e estabilidade.

Grafos em todo lugar: grafos computacionais e DAGs de dependência

Frameworks de aprendizado profundo constroem e percorrem grafos internamente:

  • Grafo de computação (computation graph) (DAG, directed acyclic graph) para as passagens direta e reversa
  • Grafos de operadores (operator graphs) para compilação/fusão (por exemplo, XLA, TorchInductor)
  • Grafos de execução distribuída para paralelismo de pipeline/tensor

Algoritmos de grafos como ordenação topológica (topological sorting) e eliminação de subexpressões comuns (common subexpression elimination) aparecem dentro de compiladores e sistemas de diferenciação automática (autodiff).

Principais estruturas de dados em sistemas de ML

Arrays densos / tensores (a “linguagem de montagem” do aprendizado profundo)

A estrutura dominante é o tensor (tensor): um array denso n‑dimensional com:

  • forma (shape) (dimensões)
  • tipo de dado (dtype) (FP32, BF16, FP16, FP8, INT8, …)
  • passo/layout (stride/layout) (como índices mapeiam para a memória)

Notas práticas:

  • Processamento em lote (batching) transforma muitas operações pequenas em menos operações grandes, melhorando a utilização.
  • Visões (views) (reformatações (reshapes)) muitas vezes são gratuitas, mas transposições (transposes) podem introduzir passos não contíguos e kernels mais lentos.
  • Precisão mista (mixed precision) muda tanto a velocidade quanto o comportamento numérico; escalonamento de perda (loss scaling) é um ajuste algorítmico para underflow.

Representações esparsas: CSR/CSC/COO

Quando a maioria das entradas é zero, formatos esparsos reduzem memória e podem reduzir computação:

  • COO (lista de coordenadas): armazene (i, j, value)
  • CSR/CSC: linha/coluna esparsa comprimida, eficiente para padrões de matvec/matmul esparsos
  • Padrões esparsos em blocos (block-sparse): comuns em poda estruturada (structured pruning) e em algumas variantes eficientes de atenção

Esparsidade é mais valiosa quando:

  • a esparsidade é alta e estruturada o suficiente para ser explorada
  • o suporte de kernels/hardware é bom (varia muito)

Tabelas hash e dicionários

Mapas hash (hash maps) são onipresentes em sistemas de ML:

  • mapas token (token) → identificador (id) em vocabulários de PLN
  • hashing de atributos (feature hashing) em ML clássico
  • roteamento de parâmetros (por exemplo, tabelas de gating em Mistura de Especialistas (Mixture-of-Experts))
  • cacheamento (caching) (por exemplo, memoização (memoizing) de pré-processamento)

Ideias-chave:

  • consulta média O(1), mas atenção a colisões e overhead de memória
  • hashing estável entre processos importa em pipelines distribuídos

Heaps / filas de prioridade

Heaps (heaps) suportam lógica eficiente de “manter os melhores K”:

  • Amostragem top‑k (top-k sampling) e busca em feixe na decodificação de modelos de linguagem de grande porte
  • seleção de negativos difíceis em aprendizado métrico (metric learning)
  • recuperação dos principais candidatos a partir de um fluxo de pontuações

Complexidade: O(n log k) para manter elementos top‑k a partir de n itens.

Árvores e árvores de prefixos

Árvores aparecem em:

  • Árvores de decisão (decision trees) e árvores com boosting de gradiente (gradient-boosted trees)
  • Árvores de prefixos (tries) para léxicos e decodificação com restrições (constrained decoding) (por exemplo, decodificação por esquema JSON (JSON schema decoding))
  • Árvores kd (kd-trees) / árvores bola (ball trees) (menos comuns em dimensões muito altas, mas ainda usadas em alguns cenários)

Para decodificação com restrições em modelos de linguagem de grande porte, árvores de prefixos permitem verificar “quais tokens são válidos como próximo?” de forma eficiente.

Grafos e listas de adjacência

Estruturas de grafo aparecem em:

  • redes neurais em grafos (GNN neighborhoods)
  • grafos de conhecimento
  • grafos de dependência em compiladores/diferenciação automática

Listas de adjacência (adjacency lists) são típicas para grafos esparsos; matrizes de adjacência (adjacency matrices) são usadas para grafos densos ou pequenos.

O cache de chaves e valores (KV cache) (uma estrutura moderna, específica de modelos de linguagem)

Durante inferência autorregressiva (autoregressive inference), transformadores reutilizam chaves/valores de atenção do passado:

  • o cache de chaves e valores armazena, por camada, tensores K e V para tokens gerados anteriormente
  • sem cache, a decodificação fica muito mais cara porque você recomputa repetidamente estados passados

Sistemas como vLLM introduzem caches KV paginados/em blocos (paged/block KV caches) (um alocador de memória (memory allocator) + tabela de indireção (indirection table)) para:

  • reduzir fragmentação
  • suportar muitas sequências concorrentes
  • habilitar processamento em lote contínuo (continuous batching)

Este é um exemplo concreto de como “design de estrutura de dados” viabiliza diretamente inferência com maior vazão.

Algoritmos de treinamento: otimizando parâmetros com eficiência

Treinamento é uma interação entre:

  1. computação forward,
  2. computação de gradientes,
  3. atualizações de parâmetros,
  4. pipeline de dados e escalonamento.

Retropropagação e diferenciação automática

O treinamento em aprendizado profundo depende de diferenciação automática em modo reverso (reverse-mode automatic differentiation), tipicamente implementada como:

  • construir uma fita (tape) / grafo de operações na passagem direta
  • percorrer em ordem topológica reversa para acumular gradientes

Conceitualmente, isso é travessia de grafo mais programação dinâmica (dynamic programming) sobre o DAG. Veja Retropropagação.

Otimização baseada em gradiente

A maior parte do treinamento de redes neurais usa variantes de descida do gradiente (gradient descent):

  • SGD, Momentum
  • Adam/AdamW (momentos adaptativos)
  • Lion, Adafactor (alternativas eficientes em memória em alguns regimes)

Elas são algoritmicamente simples, mas pesadas em estrutura de dados: otimizadores frequentemente mantêm tensores de estado (state tensors) (por exemplo, Adam mantém primeiro/segundo momentos), às vezes dobrando ou triplicando o uso de memória. Veja Descida do Gradiente.

Implicação prática: a escolha do otimizador muda não só a convergência, mas também a pegada de memória (memory footprint), que pode dominar em escala.

Minilotes, embaralhamento e amostragem

Um pipeline típico de treinamento usa:

  • minilotes (mini-batches) para vetorização eficiente
  • buffers de embaralhamento (shuffle buffers) para reduzir correlação entre amostras consecutivas
  • amostradores (samplers) (uniforme, ponderado, estratificado) para lidar com desbalanceamento

Algoritmos de amostragem que importam:

  • amostragem por reservatório (reservoir sampling) para datasets em streaming quando você não pode armazenar tudo
  • método do alias (alias method) para amostrar rápido de uma distribuição discreta (amostras O(1) após pré-processamento O(n))
  • amostragem aleatória ponderada (weighted random sampling) para desbalanceamento de classes

Um loop prático de treinamento em minilotes (ilustrativo)

Abaixo está um esboço mínimo (não específico de framework) mostrando onde algoritmos e estruturas de dados entram: processamento em lote, embaralhamento, forward/backward, estado do otimizador.

import numpy as np

def iterate_minibatches(X, y, batch_size, rng):
    idx = np.arange(len(X))
    rng.shuffle(idx)  # Fisher–Yates shuffle under the hood
    for start in range(0, len(X), batch_size):
        batch_idx = idx[start:start+batch_size]
        yield X[batch_idx], y[batch_idx]

# Toy model: linear classifier
W = np.zeros((100, 10), dtype=np.float32)
m = np.zeros_like(W)  # momentum / Adam state (data structure cost!)
v = np.zeros_like(W)

lr = 1e-3
beta1, beta2 = 0.9, 0.999
eps = 1e-8
rng = np.random.default_rng(0)

for step in range(1000):
    for Xb, yb in iterate_minibatches(X, y, batch_size=256, rng=rng):
        logits = Xb @ W                  # dense matmul
        probs = np.exp(logits) / np.sum(np.exp(logits), axis=1, keepdims=True)
        grad_logits = probs
        grad_logits[np.arange(len(yb)), yb] -= 1
        grad_W = (Xb.T @ grad_logits) / len(Xb)

        # Adam update (algorithm + extra state tensors)
        m = beta1 * m + (1 - beta1) * grad_W
        v = beta2 * v + (1 - beta2) * (grad_W ** 2)
        W -= lr * m / (np.sqrt(v) + eps)

Mesmo neste exemplo de brinquedo, observe:

  • embaralhamento é uma escolha algorítmica que afeta a generalização
  • estado do otimizador (m, v) é uma grande estrutura de memória
  • o cálculo é majoritariamente álgebra linear densa, mas a orquestração importa

Reduzindo memória de treinamento: checkpointing e particionamento

Técnicas-chave são essencialmente trocas espaço–tempo algorítmicas:

  • checkpointing de ativações (activation checkpointing): economize memória recomputando partes da passagem direta durante a passagem reversa (mais computação, menos memória)
  • acumulação de gradientes (gradient accumulation): simule lotes grandes com microlotes menores (armazene gradientes por mais tempo)
  • particionamento de otimizador/parâmetros (sharding) (por exemplo, ZeRO): particione tensores entre dispositivos para reduzir memória por dispositivo

Elas estão profundamente ligadas a Noções Básicas de Sistemas Distribuídos.

Algoritmos de comunicação coletiva (treinamento distribuído)

Em treinamento com paralelismo de dados (data parallel training), gradientes são sincronizados usando:

  • redução total (all-reduce) (all-reduce em anel (ring all-reduce) é comum): eficiente em largura de banda, O(p) passos para p dispositivos
  • redução‑espalhamento + coleta total (reduce-scatter + all-gather): melhora sobreposição e comportamento de memória
  • padrões de servidor de parâmetros (parameter server) (menos comuns em pré-treinamento de modelos de linguagem hoje, mas ainda usados)

Embora este artigo não aprofunde sistemas distribuídos, note que esses são algoritmos com trade-offs concretos de assintótica e fatores constantes.

Algoritmos de inferência: tornando a predição rápida e escalável

Inferência inclui:

  • executar o forward do modelo
  • decodificar saídas (para modelos generativos)
  • processamento em lote/escalonamento e cache
  • recuperação opcional aumentada

Inferência eficiente em transformadores: cache e kernels de atenção

Para modelos de Arquitetura Transformer, as maiores alavancas são:

  • cache de chaves e valores (evita recomputar contexto passado)
  • atenção eficiente em memória (memory-efficient attention) (por exemplo, tiling no estilo FlashAttention para evitar materializar grandes matrizes de atenção L×L)
  • quantização (quantization) (pesos/ativações INT8/FP8) para reduzir largura de banda de memória
  • decodificação especulativa (speculative decoding) (modelo rascunho + verificação) para reduzir passos caros do modelo grande

Isso é uma mistura de algoritmos (decodificação especulativa) e design de layout de dados/kernel (FlashAttention).

Algoritmos de decodificação para modelos de linguagem

Dadas probabilidades do próximo token, estratégias comuns de decodificação incluem:

  • decodificação gulosa (greedy decoding): escolher argmax a cada passo (rápido, pode ser repetitivo)
  • busca em feixe: manter as B melhores sequências parciais (maior qualidade em algumas tarefas; mais computação/memória)
  • amostragem top‑k: amostrar entre os k tokens mais prováveis
  • amostragem de núcleo (nucleus sampling) (top‑p): amostrar entre o menor conjunto com probabilidade cumulativa ≥ p

Isso se conecta diretamente a ideias clássicas de Busca: manter uma fronteira (frontier) (feixes), pontuar e podar.

Exemplo: seleção top‑k com um heap

Se você precisa dos itens top‑k a partir de uma grande lista de pontuações, um heap evita ordenar tudo.

import heapq

def top_k_indices(scores, k):
    # Keep a min-heap of size k: O(n log k)
    heap = []
    for i, s in enumerate(scores):
        if len(heap) < k:
            heapq.heappush(heap, (s, i))
        else:
            if s > heap[0][0]:
                heapq.heapreplace(heap, (s, i))
    # Return indices sorted by score descending
    return [i for s, i in sorted(heap, reverse=True)]

Na prática, kernels de GPU implementam top‑k de forma diferente, mas a ideia subjacente — evitar ordenação completa quando k é pequeno — permanece.

Processamento em lote e escalonamento em serving

Pilhas de inferência em produção adicionam algoritmos de nível de sistema:

  • processamento em lote dinâmico / processamento em lote contínuo: combinar requisições que chegam em momentos diferentes
  • escalonadores sem ociosidade (work-conserving schedulers): maximizar utilização de GPU respeitando objetivos de nível de serviço (SLOs) de latência (latency SLOs)
  • controle de admissão (admission control): políticas de enfileiramento (queueing policies) para evitar sobrecarga

Isso exige estruturas do tipo fila (buffers circulares (ring buffers), filas de prioridade) e gestão cuidadosa de memória (especialmente com caches de chaves e valores).

Algoritmos e estruturas de recuperação (clássica + vetorial)

Recuperação é central para busca, recomendações e Geração Aumentada por Recuperação (Retrieval-Augmented Generation, RAG). A tarefa-chave: dada uma consulta, encontrar itens relevantes de forma eficiente em um grande corpus.

Recuperação lexical clássica: índices invertidos

Um índice invertido (inverted index) mapeia termos → lista de documentos que contêm o termo, frequentemente com posições e frequências do termo.

Estrutura de dados:

  • dicionário/mapa hash de token para lista de ocorrências (postings list)
  • listas de ocorrências são armazenadas como sequências de inteiros comprimidas (por exemplo, codificação por delta (delta-encoding) + codificação por bytes variáveis (variable-byte coding))

Algoritmo:

  1. tokenizar a consulta
  2. buscar listas de ocorrências
  3. intersectar/mesclar (frequentemente usando técnicas de dois ponteiros (two-pointer))
  4. pontuar (TF-IDF/BM25) e retornar os melhores resultados

Isso é extremamente eficiente para correspondência exata de termos e continua amplamente usado.

Recuperação vetorial: busca de vizinhos mais próximos no espaço de incorporações

Recuperação neural representa documentos e consultas como vetores, e então busca por similaridade do cosseno (cosine similarity) ou produto escalar (dot product).

Força bruta vs. Vizinhos Mais Próximos Aproximados (Approximate Nearest Neighbor, ANN)

  • Força bruta: calcular similaridade com todos os vetores, O(N·d). Funciona para N pequeno ou quando muito acelerado por GPU e processado em lote.
  • ANN: trocar uma pequena quantidade de precisão por grandes ganhos de velocidade.

Estruturas/algoritmos comuns de ANN:

  • HNSW (Hierarchical Navigable Small World graphs): busca baseada em grafo, muito popular na prática
  • IVF (Inverted File Index): clusters k-means; busca apenas nas listas de alguns centróides
  • PQ (quantização de produto (Product Quantization)): comprimir vetores para reduzir memória e acelerar computações de distância
  • LSH (hashing sensível à localidade (Locality Sensitive Hashing)): hash para que vetores próximos colidam com alta probabilidade (menos dominante que HNSW/IVF+PQ hoje)

Nota prática: muitos bancos de dados vetoriais (vector DBs) de produção combinam IVF + PQ ou HNSW, às vezes com reordenação usando produtos escalares exatos em um conjunto menor de candidatos.

Exemplo: busca vetorial simples por força bruta

import numpy as np

def cosine_search(query, docs, top_k=5):
    # query: (d,), docs: (N, d)
    query = query / (np.linalg.norm(query) + 1e-12)
    docs_norm = docs / (np.linalg.norm(docs, axis=1, keepdims=True) + 1e-12)
    scores = docs_norm @ query  # (N,)
    top_idx = np.argpartition(-scores, top_k)[:top_k]  # partial selection
    top_idx = top_idx[np.argsort(-scores[top_idx])]
    return list(zip(top_idx.tolist(), scores[top_idx].tolist()))

Mesmo aqui, o truque algorítmico principal é seleção parcial (partial selection) (argpartition), em vez de ordenação completa.

Recuperação híbrida e reordenação

Sistemas modernos frequentemente:

  1. recuperam candidatos usando léxico (BM25) e/ou ANN vetorial
  2. reordenam (re-rank) os melhores candidatos com um codificador cruzado (cross-encoder) ou um modelo maior

Essa arquitetura reduz custo: modelos caros rodam apenas em dezenas/centenas de candidatos, não em milhões.

Filtros e metadados: filtros de Bloom e conjuntos de bits

Quando a recuperação inclui restrições (idioma, intervalos de data, permissões), sistemas dependem de:

  • conjuntos de bits (bitsets) para interseção rápida de conjuntos
  • filtros de Bloom (Bloom filters) para testar rapidamente “possivelmente no conjunto” com pouca memória (falsos positivos permitidos)

Essas são estruturas de dados clássicas que se tornam críticas em escala.

Algoritmos e estruturas em diferentes famílias de modelos

Árvores de decisão e boosting

Modelos baseados em árvores dependem de:

  • seleção gulosa de divisões (ordenar/particionar atributos)
  • estruturas de árvore para inferência (ramificação por limiares)
  • algoritmos baseados em histogramas para treinamento rápido (comuns em bibliotecas modernas de GBDT)

Mesmo que aprendizado profundo domine muitas tarefas, árvores continuam fortes para dados tabulares e são altamente algorítmicas.

Redes neurais em grafos (GNNs)

Treinamento/inferência de GNN envolve:

  • amostragem de vizinhos (neighbor sampling) (caminhadas aleatórias (random walks), amostragem por importância (importance sampling))
  • armazenamento esparso de adjacência (CSR/CSC)
  • propagação de mensagens (message passing) sobre arestas (frequentemente padrões de matmul esparsa‑densa (sparse-dense matmul))

A escolha do algoritmo de amostragem e do formato de adjacência pode determinar a escalabilidade.

Armadilhas comuns e como raciocinar sobre elas

Quando “o modelo está lento”, mas o gargalo é algorítmico

Culpados típicos:

  • atenção O(L²) em contextos longos sem kernels eficientes em memória
  • implementações lentas de top‑k/top‑p ou transferências excessivas CPU↔GPU
  • carregador de dados (data loader) ineficiente (leituras pequenas, embaralhamento ruim, sem pré-busca (prefetch))
  • recuperação usando força bruta em N grande sem ANN

Multiplicadores ocultos de memória

Fique atento a:

  • estados do otimizador (Adam ≈ 2× parâmetros, além de gradientes)
  • ativações (escala com tamanho do lote e profundidade)
  • caches de chaves e valores (escala com número de sequências concorrentes × comprimento de contexto × camadas)

Trade-offs entre denso e esparso

Esparso não é automaticamente mais rápido:

  • kernels esparsos podem ter piores fatores constantes (constant factors)
  • esparsidade não estruturada (unstructured sparsity) é difícil para o hardware explorar
  • use esparsidade quando ela reduz significativamente a largura de banda de memória e é suportada por kernels

Checklist prático: escolhendo algoritmos e estruturas de dados

Ao implementar um componente de sistema de IA (loop de treinamento, servidor de inferência, recuperador), pergunte:

  1. Qual é a escalabilidade assintótica?
    Qual variável cresce: tamanho do dataset, comprimento de sequência, número de usuários, quantidade de incorporações?

  2. Onde o tempo é gasto: computação ou memória?
    Se for limitado por memória (memory-bound), melhore layout, reduza precisão, faça fusão de operações ou use cache.

  3. Qual é a operação “top‑k” ou de “fronteira”?
    Use heaps/seleção parcial em vez de ordenações completas.

  4. Dá para pré-computar ou indexar?
    Índice invertido, grafo ANN, centróides IVF, incorporações em cache.

  5. Existe um trade-off espaço–tempo disponível?
    Checkpointing de ativações, compressão PQ, particionamento.

  6. Como isso se comporta em um ambiente distribuído?
    Algoritmos de comunicação (redução total) e estratégias de particionamento importam. Veja Noções Básicas de Sistemas Distribuídos.

Resumo

Algoritmos e estruturas de dados não são “conhecimento de fundo” em IA — eles são a maquinaria que torna o treinamento escalável, a inferência rápida e a recuperação eficaz. Ideias centrais incluem:

  • Algoritmos de grafos (diferenciação automática, compilação, escalonamento)
  • Algoritmos de otimização (famílias SGD/Adam e seu estado)
  • Heaps/filas/hashes para decodificação, amostragem, cache e orquestração
  • Estruturas de indexação (índices invertidos, HNSW/IVF/PQ) que tornam a recuperação prática
  • Estruturas especializadas como o cache de chaves e valores em transformadores, permitindo geração com alta vazão

Esses fundamentos se conectam diretamente ao comportamento prático do sistema: latência, vazão, pegada de memória e, em última análise, a viabilidade de implantar IA em escala.