Streamliners for Answer Set Programming

Título: Streamliners para Programação de Resposta a Conjuntos (ASP)

Autores: Florentina Voboril, Martin Gebser, Stefan Szeider e Alice Tarzariol.
Contexto: Submetido ao ICLP 2026.

1. O Problema

A Programação de Resposta a Conjuntos (ASP) é um paradigma poderoso para resolução declarativa de problemas, mas o desempenho dos solvers modernos (como o CLINGO) é altamente sensível à codificação do problema. Duas formulações logicamente equivalentes podem resultar em tamanhos de grounding (instanciação) e tempos de execução drasticamente diferentes.

Uma técnica conhecida para melhorar o desempenho é a adição de restrições de "streamliner". Estas são restrições auxiliares que reduzem o espaço de busca eliminando partes da solução sem tornar instâncias satisfatíveis em insatisfatíveis (preservando a satisfatibilidade). Embora existam métodos automáticos para gerar restrições de quebra de simetria ou implicações em ASP, eles frequentemente operam em nível proposicional (causando gargalos de grounding em instâncias grandes) ou exigem vieses de linguagem cuidadosamente desenhados, limitando sua generalidade.

O desafio central abordado neste trabalho é: Como gerar automaticamente restrições de streamliner eficazes e semanticamente diversas para ASP, sem depender de vieses de linguagem manuais ou grandes conjuntos de dados de treinamento?

2. Metodologia

Os autores adaptam a abordagem StreamLLM (originalmente desenvolvida para Programação por Restrições - CP) para o domínio do ASP. O pipeline proposto é totalmente automatizado e funciona da seguinte maneira:

1. Entrada: Um encoding (codificação) ASP original e um pequeno conjunto de instâncias de treinamento satisfatíveis (que podem ser resolvidas em poucos segundos).
2. Geração via LLM: O sistema solicita a múltiplos Modelos de Linguagem de Grande Escala (LLMs) de ponta (incluindo Claude 4.5, GPT-5 Mini, Gemini 3 Pro, Mistral Large e Deepseek V3.2) que gerem cinco restrições candidatas.
   • O prompt instrui o LLM a analisar a codificação e propor restrições de quebra de simetria ou implicações que eliminem soluções redundantes.
   • O LLM deve retornar o código em formato JSON, garantindo sintaxe correta (Clingo).
3. Filtragem e Validação: As restrições candidatas são testadas nas instâncias de treinamento. Restrições são descartadas se:
   • Causarem erros de sintaxe.
   • Tornarem instâncias satisfatíveis em insatisfatíveis.
   • Degradarem o desempenho de tempo de execução em todas as instâncias de treinamento.
4. Seleção e Avaliação: O processo é repetido por 30 minutos. As restrições sobreviventes são combinadas para formar um "Melhor Encoding Virtual" (VBE - Virtual Best Encoding). O VBE seleciona, para cada instância, a variante mais rápida entre o encoding original e suas variantes com streamliners.
5. Objetivo: Identificar se os streamliners gerados oferecem melhorias complementares (ou seja, se diferentes restrições ajudam em diferentes instâncias).

3. Contribuições Principais

• Primeira Aplicação Sistemática: É, até onde se sabe, a primeira aplicação sistemática de geração de streamliners baseada em LLMs especificamente para ASP.
• Adaptação de StreamLLM: Adaptação bem-sucedida do pipeline StreamLLM para a semântica não monotônica e sintaxe rica do ASP (incluindo regras de escolha, agregados e literais condicionais).
• Análise de Complementaridade: Demonstração de que diferentes LLMs e execuções produzem restrições semanticamente diversas (não apenas variações sintáticas), capturando estruturas reais do problema.
• Eficiência com Poucos Dados: Evidência de que apenas um pequeno número de instâncias de treinamento simples é suficiente para guiar a geração de restrições eficazes, contornando a necessidade de grandes conjuntos de dados curados.

4. Resultados Experimentais

Os autores avaliaram a abordagem em três benchmarks da ASP Competition 2011: Partner Units Problem (PUP), Sokoban e Torres de Hanói.

• Desempenho Geral: O VBE alcançou acelerações de 4 a 5 vezes em relação ao encoding original.
• Redução de Tempo:
  • PUP: Redução de tempo de execução acumulada de até 76% (Run 1) e 47% (Run 2) no VBE.
  • Sokoban: Redução de 75% (Run 1) e 57% (Run 2).
  • Torres de Hanói: Redução de 79% (Run 1) e 71% (Run 2). O encoding original resolveu apenas 31 de 46 instâncias, enquanto o VBE resolveu todas as 46.
• Diversidade Semântica: As restrições geradas incluíram quebras de simetria complexas, condições de implicação e políticas de poda específicas de domínio.
• Validação de "Revisão Manual": Os autores tentaram otimizar manualmente as restrições geradas (reduzindo o tamanho do grounding ou removendo condições laterais). Surpreendentemente, as versões manuais frequentemente tiveram desempenho pior que as geradas pelo LLM. Isso sugere que o pipeline empírico do LLM consegue "sintonizar" o desempenho do solver de forma mais eficaz do que considerações teóricas de escalabilidade pura, possivelmente devido à interação complexa com heurísticas internas do solver.

5. Significado e Conclusão

O trabalho demonstra que os LLMs podem atuar como assistentes poderosos para a otimização de codificações em ASP, gerando restrições que vão além de variações sintáticas simples para capturar a estrutura profunda do problema.

• Impacto: A abordagem oferece uma via promissora para melhorar o desempenho de solvers ASP em problemas combinatórios difíceis sem exigir expertise humana profunda para a criação manual de restrições.
• Futuro: Os autores sugerem a expansão para benchmarks mais amplos, o uso de técnicas de adaptação de modelos (como fine-tuning) e a extensão do método para problemas de otimização.

Em resumo, o artigo valida que a geração automática de streamliners via LLMs é uma estratégia viável e altamente eficaz para reduzir o espaço de busca e acelerar a resolução de problemas em ASP.