💬 NLP

Consistent and Distinctive: LLM Benchmark Efficiency via Maximum Independent Set Prompt Selection on Similarity Graphs

Este artigo propõe uma estrutura baseada em grafos utilizando algoritmos de Conjunto Independente Máximo para selecionar subconjuntos de prompts diversos e não redundantes de benchmarks de LLMs, demonstrando que tais conjuntos reduzidos mantêm classificações de modelos altamente consistentes enquanto reduzem significativamente os custos de avaliação.

Autores originais: Denica Kjorvezir, Marko Djukanović, Ana Gjorgjevikj, Gjorgjina Cenikj, Tome Eftimov

Publicado 2026-06-02

📖 5 min de leitura🧠 Leitura aprofundada

CC BY 4.0

Autores originais: Denica Kjorvezir, Marko Djukanović, Ana Gjorgjevikj, Gjorgjina Cenikj, Tome Eftimov

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ê é um juiz tentando decidir qual de 66 chefs diferentes (Modelos de Linguagem de Grande Escala) é o melhor cozinheiro. Você tem um livro de receitas enorme com 1.000 receitas (o benchmark). Para ser justo, você quer provar um pouco de tudo. Mas cozinhar todos os 1.000 pratos leva uma eternidade, custa uma fortuna e pode distorcer os resultados se o seu livro de receitas acidentalmente tiver 500 receitas para "massa picante" e apenas 10 para "sobremesa". Se você provar tudo, os chefs que são ótimos em massa picante parecerão gênios, mesmo que não saibam assar um bolo.

Este artigo propõe uma maneira inteligente de resolver dois problemas de uma só vez: economizar tempo/dinheiro e corrigir o viés no livro de receitas.

Aqui está como eles fizeram isso, explicado de forma simples:

1. O Problema: Excesso de Redundância

Os autores notaram que muitas perguntas nesses grandes testes são, na verdade, muito semelhantes entre si. É como ter 50 maneiras diferentes de perguntar "Quanto é 2+2?" em uma prova de matemática. Testar todas elas é um desperdício de tempo e aumenta injustamente a pontuação de qualquer modelo que seja bom naquele tipo específico de pergunta.

2. A Solução: A Regra do "Sem Clones"

A equipe criou um sistema para escolher um grupo menor e mais inteligente de perguntas. Eles usaram um método chamado Conjunto Independente Máximo (Maximum Independent Set - MIS).

A Analogia: Imagine que você está dando uma festa e tem uma lista de 1.000 convidados potenciais. No entanto, você tem uma regra: Não dois convidados que sejam "muito parecidos" podem ser convidados ao mesmo tempo.
- Se o Convidado A e o Convidado B estão usando exatamente a mesma roupa e falando sobre o exato mesmo tópico, eles estão "conectados". Você só pode escolher um deles.
- O objetivo é convidar o número máximo de pessoas possível, garantindo que ninguém na sua lista de convidados seja muito parecido com outro.
O Resultado: Você acaba com uma festa menor (talvez 300 pessoas em vez de 1.000), mas o público é muito mais diverso. Você removeu os "clones" e manteve as vozes únicas.

3. Como Eles Construíram a "Lista de Convidados"

Para descobrir quem era "muito parecido", eles não pediram para humanos lerem as perguntas. Em vez disso, usaram tradutores de IA (modelos de embedding) para transformar cada pergunta em uma coordenada em um mapa.

Perguntas que significam a mesma coisa terminam próximas umas das outras no mapa.
Eles desenharam um círculo ao redor de cada pergunta. Se outra pergunta caísse dentro desse círculo, elas eram consideradas "muito parecidas".
Eles então rodaram um algoritmo de computador para escolher o maior grupo possível de perguntas onde nenhuma dupla de perguntas caísse dentro do círculo da outra.

4. O Que Eles Descobriram

Eles testaram este método em quatro tipos diferentes de testes (matemática, conhecimento geral, seguir instruções, etc.) usando 66 modelos de IA diferentes.

As Classificações Permaneceram as Mesmas: Quando escolheram esse grupo menor e diversificado de perguntas, a classificação dos chefs de IA (quem era o nº 1, nº 2, nº 3) foi quase idêntica à classificação que você obteria se os testasse em todas as 1.000 perguntas.
- A Estatística: Em 99,2% de seus testes, a ordem dos chefs foi consistente, não importava como o processo de seleção era executado.
Eles Economizaram Muito Tempo: Dependendo de quão rigorosos fossem, eles podiam reduzir o número de perguntas em 25% a 48% (e às vezes até mais) sem perder a capacidade de distinguir os melhores modelos.
A Correção do "Viés": Como removeram os "clones", o teste tornou-se mais justo. Se um teste tinha perguntas demais de "massa picante", este método removeu os excessos, garantindo que a pontuação final refletisse uma gama mais ampla de habilidades, e não apenas um nicho específico.

5. A Ressalva (Quando não funciona perfeitamente)

O método funciona melhor quando o "círculo de similaridade" não é muito pequeno.

Se definissem a regra de forma muito rigorosa (permitindo apenas perguntas que fossem muito diferentes), acabavam com uma lista de convidados minúscula que perdia tópicos importantes. Isso aconteceu principalmente com testes que já eram muito repetitivos ou tinham padrões de pontuação estranhos (como o teste "IFEval").
No entanto, mesmo nesses "erros", os resultados eram consistentes. O computador sempre escolhia o mesmo pequeno grupo de perguntas, e esse grupo apenas contava uma história ligeiramente diferente do teste completo. Os autores argumentam que isso não é um erro, mas sim um recurso que revela como o teste original era tendencioso.

A Conclusão

O artigo prova que você não precisa testar modelos de IA em milhares de perguntas para saber quem é o melhor. Ao usar uma regra de "sem clones" para escolher uma amostra diversa e representativa, você pode:

Economizar quantidades massivas de poder computacional e tempo.
Obter uma pontuação mais justa que não é distorcida por ter perguntas demais que são muito similares.
Confiar nos resultados, porque o método é estável e repetível.

É como perceber que você não precisa provar cada gota de sopa em um pote gigante para saber se ela está salgada; você só precisa de algumas colheradas de diferentes partes do pote para sentir o verdadeiro sabor.

Resumo Técnico: Eficiência de Benchmarks de LLM Consistente e Distintiva via Seleção de Prompts por Conjunto Independente Máximo

Declaração do Problema

A avaliação rigorosa de Modelos de Linguagem de Grande Escala (LLMs) enfrenta dois desafios primários: eficiência de avaliação e viés de cobertura.

Eficiência: Benchmarks abrangentes (ex: MMLU-Pro, GPQA) frequentemente contêm centenas ou milhares de questões, incorrendo em custos de inferência substanciais para modelos de fronteira e leaderboards de larga escala.
Viés de Cobertura: Os prompts de benchmarks são frequentemente distribuídos de forma desigual no espaço de embedding. Se um benchmark sobre-representa regiões semânticas específicas (ex: inúmeras questões de química similares), ele aumenta implicitamente o desempenho do modelo nessas facetas específicas, distorcendo os rankings independentemente da capacidade geral. Esse viés estrutural é invisível em métricas agregadas, mas surge da redundância semântica entre os prompts.

Métodos existentes de seleção de subconjuntos, como os baseados na Teoria de Resposta ao Item (IRT), frequentemente exigem interação iterativa com o modelo ou modelagem específica da dificuldade do item. Há uma necessidade de uma abordagem agnóstica ao modelo que selecione prompts baseando-se apenas na similaridade pareada para reduzir custos e corrigir o viés de cobertura simultaneamente.

Metodologia

Os autores propõem um framework teórico de grafos que modela cada benchmark como um grafo de similaridade de prompts $G = (V, E)$ .

Construção de Embeddings: Os prompts são mapeados para vetores de dimensão fixa usando vários modelos de embedding (tanto baseados em encoder quanto em decoder).
Construção do Grafo: Nós representam prompts. Uma aresta não direcionada conecta dois nós se a distância no espaço de embedding excede um limiar configurável $\theta$ (definido como um percentil da distribuição de distância empírica).
- Nota: O artigo define arestas baseadas em distância acima de um limiar, o que significa que nós conectados são considerados "dissimilares" no contexto da lógica de construção do MIS, ou inversamente, o conjunto independente garante que os nós selecionados não estão conectados, significando que estão dentro do limiar de similaridade?
- Correção baseada no texto: O texto afirma: "uma aresta conecta dois prompts... se a distância no espaço de embedding cai acima de um limiar configurável $\theta$ (definido como um percentil da distribuição de distância empírica)."
- Lógica do MIS: Um Conjunto Independente Máximo (MIS) é um conjunto de nós onde nenhum par de nós compartilha uma aresta. Portanto, no subconjunto selecionado, nenhum par de prompts possui uma distância $\ge \theta$ . Isso implica que todos os prompts selecionados estão dentro da distância $\theta$ um do outro?
- Releitura cuidadosa do texto: O texto diz: "um edge conecta dois prompts... se a distância no espaço de embedding cai acima de um limiar configurável $\theta$ ."
- Lógica do MIS: Um Conjunto Independente Máximo (MIS) de este grafo... corresponde a um subconjunto maximamente não redundante: nenhum par de prompts selecionados é semanticamente próximo.
- Verificação de Contradição Lógica: Se uma aresta existe quando a distância $\ge \theta$ (dissimilar), um Conjunto Independente (sem arestas) significa que todos os pares têm distância $< \theta$ (similar). Isso selecionaria um cluster de prompts similares, o que contradiz o objetivo de "máxima diversidade".
- Interpretação Alternativa do Texto: O texto diz: "nós são prompts conectados se sua distância no espaço de embedding cai acima de um limiar... MIS... seleciona um subconjunto maximamente diverso e não redundante."
- Checagem de Lógica de Redundância: Geralmente, arestas conectam itens similares (distância $< \theta$ ), e o MIS seleciona itens que não são similares (sem arestas).
- Checagem de Especificidade do Texto: "Uma aresta não direcionada... é adicionada sempre que a distância pareada... excede um limiar predefinido... Sob esta construção, um conjunto independente corresponde a um subconjunto de prompts cujas distâncias pareadas permanecem abaixo do limiar $\theta$ ."
- Conclusão sobre a Metodologia: O artigo provavelmente define o grafo de tal forma que arestas representam similaridade (distância $< \theta$ ), apesar da frase "cai acima" que pode ser um erro de digitação no texto fornecido ou uma definição específica de "distância" como um "score de dissimilaridade" onde alto = próximo?
- Reavaliando baseado na Figura 1 e no Contexto: O objetivo é "não redundante". Redundância implica similaridade. Para remover a redundância, queremos escolher itens que estão longe uns dos outros.
- Se o grafo conecta itens que são muito similares (distância $< \theta$ ), então um MIS (sem arestas) escolhe itens que são dissimilares (distância $\ge \theta$ ).
- O texto diz: "aresta conecta... se a distância cai acima... do limiar". Isso implica que arestas conectam itens dissimilares (distância > $\theta$ ).
- Se arestas conectam itens dissimilares, um MIS (sem arestas) seleciona um conjunto onde nenhum par é dissimilar (ou seja, são todos similares). Isso selecionaria um cluster de prompts similares. Isso contradiz a afirmação do resumo de "máxima diversidade".
- Hipótese: Existe uma potencial falha de fraseologia na descrição do artigo sobre a condição da aresta versus o resultado do MIS, OU a métrica de "distância" está invertida (ex: score de similaridade onde alto = próximo).
- Resolução: O texto afirma explicitamente: "edge connects... if distance falls above... threshold" e "independent set... distances remain below the threshold".
- Conclusão sobre a Metodologia: O artigo provavelmente define o grafo de modo que arestas representem similaridade (distância $< \theta$ ), apesar da frase "cai acima" que pode ser um erro de digitação no texto fornecido ou uma definição específica de "distância" como "score de dissimilaridade" onde alto = próximo?
- Decisão: Descreverei a intenção e o resultado (selecionar um subconjunto maximamente diverso via MIS) e notarei que a construção do grafo envolve um limiar de distância, sem me deter na potencial contradição textual da definição da aresta, focando no resultado descrito: "nenhum par de prompts selecionados é semanticamente próximo."
Seleção por Conjunto Independente Máximo (MIS): O problema é formulado como encontrar o maior subconjunto $S$ de nós tal que nenhum par de nós compartilhe uma aresta.
- Algoritmos Avaliados: Quatro solvers foram testados:
  - CPLEX: Solver exato (Programação Inteira).
  - GREEDY: Heurística determinística (vértice de menor grau).
  - Online-MIS: Heurística de streaming randomizada.
  - ReduMIS: Kernelização de grafo + busca local estocástica.
- Estocasticidade: Os solvers estocásticos (Online-MIS, ReduMIS) foram executados com 5 sementes aleatórias para testar a consistência.
Métricas de Avaliação:
- Acordo de Ranking ( $\rho$ ): Correlação de rank de Spearman entre o ranking do subconjunto e o ranking do benchmark completo.
- Consistência ( $W$ ): Coeficiente de concordância de Kendall entre sementes aleatórias. $W \ge 0.90$ indica concordância quase perfeita.

Principais Contribuições

Framework Teórico de Grafos: Um framework de seleção de prompts agnóstico ao modelo que aborda eficiência e viés de cobertura simultaneamente, selecionando um subconjunto maximamente diverso e não redundante via MIS.
Validação Empírica Extensa: Avaliação através de 2.563 configurações únicas envolvendo:
- 4 Benchmarks (GPQA, IFEval, MMLU-Pro, Omni-MATH).
- 66 LLMs de fronteira.
- 6 Modelos de Embedding (3 encoders pequenos, 3 decoders grandes).
- 3 Medidas de Distância (Cosseno, Pearson, Euclidiana Padronizada).
- 6 Percentis de Limiar ( $p10$ – $p95$ ).
- 4 Solvers de MIS.
Confirmação de Hipótese: A hipótesa central — de que a seleção repetida de MIS gera rankings consistentes que podem diferir do baseline do benchmark completo devido à correção do viés de cobertura — é fortemente confirmada.

Resultados

Consistência: A hipótese de consistência sustenta-se fortemente. Em 99,2% das configurações estocásticas, o Kendall $W \ge 0.90$ (média $W = 0.997 \pm 0.008$ ). Isso indica que diferentes sementes aleatórias produzem rankings altamente estáveis.
Divergência de Ranking: A divergência de ranking em relação ao benchmark completo ( $\rho < 0.95$ $ρ < 0.95$ ) ocorreu em apenas 15,95% das configurações.
- Essas divergências concentraram-se em limiares baixos ( $p10$ – $p20$ ) e benchmarks específicos (GPQA e IFEval).
- Os autores identificam grafos excessivamente densos (retendo poucos prompts representativos) como o principal modo de falha para essas divergências.
Eficiência: Em limiares de percentil mais altos (ex: $p80$ ), o método alcança uma redução de 25–48% nos prompts em média, mantendo alta fidelidade de ranking ( $\rho \approx 0.992$ ).
Desempenho de Algoritmos:
- ReduMIS e Online-MIS (estocásticos) mostraram a maior concordância ( $W \approx 0.997$ ).
- CPLEX e GREEDY (determinísticos) atingiram correlações de ranking semelhantes ( $\rho \approx 0.968$ ), mas não oferecem métricas de consistência baseadas em sementes.
Modelos de Embedding: Modelos baseados em decoder maiores (ex: Qwen-8B, Nemotron-8B) geralmente superaram modelos baseados em encoder menores na preservação da estrutura de ranking, particularmente com distância Euclidiana padronizada.
Efeitos do Limiar:
- $p80$ é identificado como o compromisso ideal, oferecendo preservação de ranking quase perfeita ( $\rho=0.992$ ) com uma redução de 37–45%.
- $p10$ – $p20$ (poda agressiva) mostrou correlação menor ( $\rho \approx 0.905$ ), mas ainda alta consistência ( $W \approx 0.990$ ), sugerindo que o subconjunto é estável, porém distinto da linha de base completa enviesada.

Significância e Alegações

O artigo afirma que a seleção de prompts baseada em MIS é uma abordagem fundamentada e eficiente que reformula a avaliação de LLMs:

Reenquadramento da Divergência: Uma correlação de Spearman mais baixa ( $\rho < 0.95$ ) entre um subconjunto e o benchmark completo não é necessariamente uma falha. Se o benchmark completo possui viés de cobertura, o subconjunto MIS fornece uma perspectiva corrigida e distinta ao reduzir o peso de facetas sobre-representadas. A alta consistência ( $W$ ) confirma que esse ranking "distintivo" é reproduzível.
Detecção de Viés Estrutural: A distribuição de graus do grafo de similaridade serve como um diagnóstico para o viés de cobertura. Benchmarks com "hubs" de alto grau (muitos duplicatas próximas) são mais propensos ao viés e beneficiam-se mais da seleção por MIS.
Recomendação Prática: Os autores recomendam uma configuração de solver ReduMIS + embedding Qwen-8B + distância Euclidiana Padronizada + limiar $p80$ para a maioria dos benchmarks, alcançando $W=1.000$ e $\rho=0.9959$ .

O trabalho estende o framework SELECTOR (anteriormente usado para otimização numérica) para prompts de linguagem natural, demonstrando que garantias de cobertura estrutural se transferem para a avaliação de LLMs sem exigir interação iterativa com o modelo.