🤖 machine learning

Sketch-and-Verify: Structured Inference-Time Scaling via Program Sketching

O artigo apresenta o Sketch-and-Verify, uma estratégia de escalonamento no momento da inferência, econômica para modelos de código pequenos, que supera a amostragem plana ao enumerar esboços algorítmicos diversos e preenchê-los com múltiplos candidatos, embora não possa substituir integralmente o desempenho de níveis de modelos mais robustos.

Autores originais: Shan Jiang, Zijian Yi, Chenguang Zhu

Publicado 2026-05-12

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Shan Jiang, Zijian Yi, Chenguang Zhu

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 resolver um quebra-cabeça complicado, mas só tem um robô pequeno e barato para ajudar. Esse robô é rápido e barato, mas tem um mau hábito: quando tenta resolver um problema, quase sempre escolhe a mesma maneira errada de pensar. Se você pedir para ele tentar 100 vezes, ele apenas lhe dará 100 versões ligeiramente diferentes daquela mesma resposta errada.

Este é o problema que o artigo "Sketch-and-Verify" (Esboçar e Verificar) tenta resolver. Ele oferece uma nova maneira de usar esse robô pequeno e barato para que ele possa resolver mais problemas sem precisar fazer um upgrade para um robô gigante e supercaro.

Veja como o método funciona, dividido em etapas simples:

1. O Problema: A "Mesma Canção Velha"

Geralmente, quando pedimos a uma IA para escrever código, apenas dizemos: "Tente 100 vezes e me dê o melhor".

O Defeito: Se a ideia "padrão" da IA estiver errada, pedir para ela tentar 100 vezes é como pedir a uma pessoa para escrever 100 versões diferentes de uma música ruim. Você pode mudar a letra ou o andamento, mas a melodia ainda está errada. A IA fica presa em um ciclo de mudanças "cosméticas" (mudar nomes de variáveis ou formatação) sem nunca tentar uma abordagem fundamentalmente diferente.

2. A Solução: O "Arquiteto e o Construtor"

Os autores propõem um processo de duas etapas chamado Sketch-and-Verify. Em vez de pedir à IA para escrever todo o código imediatamente, eles dividem o trabalho em dois papéis:

Etapa 1: O Arquiteto (O Esboço)
Primeiro, pedem à IA para agir como um arquiteto. Dizem: "Não escreva o código ainda. Apenas liste 5 maneiras completamente diferentes de resolver este problema."
- Exemplo: "Estratégia A: Use um mapa. Estratégia B: Ordene a lista primeiro. Estratégia C: Use um loop."
- Uma vez que a IA escolhe uma estratégia, ela desenha um "projeto" grosseiro (um esboço) com buracos nele. O projeto tem a estrutura principal (as paredes e o telhado), mas deixa os detalhes específicos (a cor da tinta, a maçaneta) como espaços vazios marcados com ??.
- Por que isso ajuda: Isso força a IA a parar e pensar sobre caminhos diferentes antes de começar a construir. Garante que a IA explore diferentes "bairros" de soluções em vez de apenas andar em círculos no mesmo bairro.
Etapa 2: O Construtor (O Preenchimento)
Agora, para cada projeto, a IA atua como um construtor. Ela preenche os buracos ?? para criar um programa completo.
- Se a IA fez 5 projetos (estratégias) e preencheu cada um 10 vezes, ela agora tem 50 programas completamente diferentes para testar.
- Como os projetos eram diferentes, esses 50 programas são estruturalmente diversos. Eles não são apenas reescritas da mesma ideia; são abordagens genuinamente diferentes.
Etapa 3: O Inspetor (Verificar)
Finalmente, eles executam todos esses programas em um teste. Mantêm os que funcionam e escolhem o melhor.

3. Os Resultados: Barato vs. Caro

Os pesquisadores testaram isso em um teste de codificação padrão chamado HumanEval+ usando três versões da IA Gemini do Google:

Lite: O modelo pequeno, barato e rápido.
Flash: O modelo médio.
Pro: O modelo grande, caro e inteligente.

As Grandes Descobertas:

Para o Robô Barato (Lite): O método "Sketch-and-Verify" foi uma mudança de jogo.
- Se pedissem apenas ao robô Lite para tentar 100 vezes normalmente (Amostragem Plana), ele resolvia cerca de 53% dos problemas difíceis.
- Se usassem o método Sketch-and-Verify (criando 10 projetos e preenchendo-os 10 vezes), ele resolvia 79% dos problemas difíceis.
- A Analogia: É como dizer a um aluno: "Não escreva apenas 100 redações sobre o mesmo tema. Escreva 10 esboços para 10 temas diferentes e depois preencha-os." O aluno aprende mais e tira uma nota melhor pelo mesmo esforço.
Para o Robô Caro (Pro): O método não ajudou muito.
- O robô Pro já é tão inteligente que sua ideia "padrão" geralmente está certa. Forçá-lo a esboçar estratégias diferentes na verdade o deixou ligeiramente pior, pois foi distraído de seu melhor instinto.
- A Regra: Se você tem um robô superinteligente, deixe-o pensar com força (Greedily). Se você só tem um robô barato, use o Sketch-and-Verify para forçá-lo a pensar criativamente.

4. A Conclusão

O artigo argumenta que o Sketch-and-Verify é uma maneira inteligente de gastar poder computacional extra quando você está preso com um modelo de IA menor e mais barato.

Não é mágica: Não torna um modelo fraco mais forte do que um modelo forte. Se você pode pagar pelo modelo "Pro" caro, use apenas esse.
É uma estratégia: Se você precisa usar o modelo barato (por causa de orçamento ou velocidade), este método é a melhor maneira de extrair desempenho extra dele. Impede que a IA fique presa em uma rotina e a força a explorar soluções diferentes, muito como uma sessão de brainstorming humana.

Em resumo: Não peça apenas à IA para tentar mais; peça para ela tentar diferentemente.

Resumo Técnico: Sketch-and-Verify: Escalonamento Estruturado em Tempo de Inferência via Esboço de Programas

1. Declaração do Problema

O artigo aborda uma restrição operacional específica enfrentada por praticantes: dado um modelo de código fixo, pequeno e custo-efetivo (por exemplo, Gemini 3.1 Flash Lite) escolhido por razões de latência ou orçamento, como deve-se alocar uma quantidade limitada de computação extra em tempo de teste para melhorar a precisão?

Abordagens padrão envolvem amostragem plana (gerar $N$ programas candidatos independentes e selecionar o melhor via execução). Os autores argumentam que a amostragem plana é ineficiente porque trata o espaço de programas como homogêneo. Grandes modelos de linguagem (LLMs) frequentemente atribuem alta massa de probabilidade a uma única estratégia algorítmica "modal". Consequentemente, mesmo com temperatura alta ou $N$ grande, o pool de candidatos resultante carece de diversidade estrutural; consiste principalmente em variantes cosméticas superficiais (nomes de variáveis diferentes, formatação) das mesmas 2–3 estratégias. Se a estratégia padrão do modelo estiver incorreta para um problema específico, a amostragem plana provavelmente falhará em descobrir a solução correta, independentemente do número de amostras.

2. Metodologia: SKETCHVERIFY

Os autores propõem SKETCHVERIFY, um método que reestrutura a computação em tempo de inferência ao fatorizar o espaço de busca em estratégia algorítmica e detalhes de implementação. Inspirado por esboço de programas (Solar-Lezama, 2008, 2013) e trabalhos anteriores sobre testes de compiladores impulsionados por LLM (OBsmith, Jiang et al., 2026b), o método opera em quatro estágios:

Estágio 1: Geração de Esboço (Prompting Primeiro-Categoria)
- Enumeração de Categorias: O LLM é instruído a listar $K$ estratégias algorítmicas fundamentalmente diferentes (por exemplo, "hash map", "dois ponteiros", "programação dinâmica") em linguagem natural. Isso força o modelo a raciocinar sobre o espaço de estratégias antes de codificar.
- Esboço: Para cada estratégia, o LLM gera um programa parcial (um "esboço") onde o algoritmo, as estruturas de dados e o fluxo de controle estão totalmente especificados, mas os detalhes de implementação (expressões, condições, limites de loops) são substituídos por espaços reservados ??. O alvo é de 4 a 8 espaços por esboço.
- Inovação Chave: Este processo de dois passos impede que o modelo autoregressivo se fixe em uma única estratégia padrão, garantindo diversidade estrutural entre os $K$ esboços.
Estágio 2: Preenchimento
- Cada esboço válido é preenchido $M$ vezes para produzir $K \times M$ programas candidatos completos.
- Para incentivar variação dentro de um único esboço, cada terceiro preenchimento é condicionado ao preenchimento anterior e solicitado a fornecer uma implementação diferente.
Estágio 3: Verificação
- Os candidatos são filtrados para compilação e execução sem falhas.
- Os candidatos sobreviventes são executados em $D$ entradas de teste diversas (geradas via uma abordagem baseada em esboço similar).
- Uma impressão digital de execução é gerada para cada candidato: um vetor de pares (status, saída). Impressões digitais idênticas indicam equivalência comportamental.
Estágio 4: Seleção
- Os candidatos são agrupados por suas impressões digitais de execução.
- O maior cluster (representando o consenso comportamental mais robusto) é selecionado.
- Do maior cluster, o programa mais curto é retornado (lâmina de Occam). Esta regra de seleção é idêntica à linha de trabalho concorrente "Votação Semântica", isolando o benefício da geração estruturada do mecanismo de seleção.

3. Contribuições Principais

Framework SKETCHVERIFY: Introduz uma política de custo-desempenho dentro do nível que aplica esboço de programas ao escalonamento em tempo de inferência. Fatoriza o espaço de busca em $K$ (estratégias) e $M$ (implementações), alcançando uma curva de escalonamento pass@1 mais íngreme do que a amostragem plana em modelos fracos.
Análise Pareto Custo-Qualidade: Fornece uma análise rigorosa no benchmark HumanEval+, especificamente reanalisando um "subconjunto difícil" de 19 problemas onde o modelo Lite de base (ganancioso) falha.
- Dentro do Nível: O esboço domina a amostragem plana em contagens de candidatos correspondentes. No subconjunto difícil, Lite Sketch ( $K=2, M=5$ ) recupera 58% dos problemas versus 26% para amostragem plana ( $N=10$ ). Mesmo com um aumento de orçamento de 3x, a amostragem plana ( $N=50$ ) atinge apenas 47%, ainda perdendo para a configuração de esboço mais barata.
- Entre Níveis: O esboço não substitui a atualização do modelo. Níveis mais fortes (por exemplo, Gemini Pro ganancioso) dominam as configurações Lite+Sketch tanto em custo quanto em precisão. O esboço é um complemento, e não um substituto, para atualizar o nível do modelo.
Decomposição Primeiro-Categoria: Propõe uma estratégia específica de prompting (enumerar nomes de estratégias antes de codificar) que é crítica para gerar diversidade estrutural em vez de variantes cosméticas.
Caracterização do Trade-off K-vs-M: Através de varreduras de escalonamento, os autores mostram que a relação entre $K$ e $M$ é não monotônica. Alocações mistas (por exemplo, $K=2, M=5$ ) frequentemente superam extremos puramente planos ( $K=1$ ) ou puramente de esboço ( $M=1$ ), e simplesmente aumentar $K$ nem sempre produz ganhos lineares (por exemplo, $K=5, M=10$ teve desempenho inferior a $K=2, M=5$ em algumas métricas).
Composabilidade: Demonstra que a geração estruturada se compõe limpa com a seleção baseada em execução (Votação Semântica). O método atua como um gerador de um pool diversificado de candidatos, enquanto o seletor permanece agnóstico ao método de geração.

4. Resultados Experimentais

Benchmarks: Avaliado no HumanEval+ (164 problemas em Python com suites de teste aumentadas). Validação cruzada em MBPP+ e LiveCodeBench é notada como trabalho futuro.
Modelos: Três níveis de modelos Google Gemini (Pro, Flash, Flash Lite) em baixos níveis de raciocínio.
Desempenho no Subconjunto Difícil (19 problemas onde Lite ganancioso falha):
- Lite Sketch ( $K=10, M=10$ ): 79% pass@1.
- Lite Flat ( $N=100$ ): 53% pass@1.
- Lite Sketch ( $K=2, M=5$ ): 58% pass@1 (a um custo menor que Flat $N=50$ ).
- Flash/Pro Greedy: Supera todas as configurações Lite, confirmando que a capacidade do modelo é o principal motor da precisão.
Curvas de Escalonamento: No conjunto completo HumanEval+, a amostragem plana Lite satura em ~89% pass@1. SKETCHVERIFY quebra esse teto, atingindo 93% em $K=10, M=10$ . No entanto, no Flash e Pro, onde os modelos estão quase saturados, os ganhos do esboço são marginais ou inexistentes em comparação com a decodificação gananciosa.

5. Significado e Alegações

O artigo posiciona o SKETCHVERIFY como uma política de custo-desempenho dentro do nível, e não uma melhoria universal de precisão.

Regra para Praticantes: Se um nível de modelo mais forte estiver disponível, use decodificação gananciosa nesse nível. Se estiver restrito a um modelo mais fraco (devido a latência, implantação ou orçamento), o SKETCHVERIFY é a maneira mais custo-efetiva de gastar computação extra em tempo de teste.
Mecanismo: O método tem sucesso ao forçar explicitamente a exploração de diferentes estratégias algorítmicas (diversidade estrutural) em vez de depender da estocasticidade da amostragem plana para encontrar acidentalmente uma nova abordagem.
Limitações: Os autores reconhecem limitações incluindo a dependência de uma única família de modelos (Gemini), um único nível de raciocínio, e o fato de que a qualidade do esboço é limitada pela própria distribuição de estratégias do modelo (se o modelo não consegue conceber a estratégia correta, o esboço não pode gerá-la). Eles também notam uma sobrecarga de ~7% em tokens para a fase de geração de esboço.

O artigo conclui que, embora o esboço seja altamente eficaz para modelos fracos que lutam com diversidade estratégica, não é uma panaceia para modelos que já atingiram seu teto de capacidade ou para problemas onde a estratégia correta está totalmente fora do conhecimento latente do modelo.