💬 NLP

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

Este artículo propone un marco basado en grafos que utiliza algoritmos de Conjunto Independiente Máximo para seleccionar subconjuntos de prompts diversos y no redundantes de los benchmarks de LLM, demostrando que tales conjuntos reducidos mantienen clasificaciones de modelos altamente consistentes mientras reducen significativamente los costos de evaluación.

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

Publicado 2026-06-02

📖 5 min de lectura🧠 Análisis profundo

CC BY 4.0

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

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

Imagina que eres un juez tratando de decidir cuál de 66 chefs diferentes (Modelos de Lenguaje Extensos) es el mejor cocinero. Tienes un libro de cocina masivo con 1,000 recetas (el benchmark). Para ser justo, quieres probar un poco de todo. Pero cocinar los 1,000 platos lleva una eternidad, cuesta una fortuna y podría sesgar los resultados si el libro de cocina accidentalmente tiene 500 recetas de "pasta picante" y solo 10 de "postres". Si lo pruebas todo, los chefs que son excelentes en la pasta picante parecerán genios, incluso si no saben hornear un pastel.

Este artículo propone una forma ingeniosa de resolver dos problemas a la vez: ahorrar tiempo/dinero y corregir el sesgo en el libro de cocina.

Así es como lo hicieron, explicado de forma sencilla:

1. El Problema: Demasiada Redundancia

Los autores notaron que muchas preguntas en estas grandes pruebas son en realidad muy similares entre sí. Es como tener 50 formas diferentes de preguntar "¿Cuánto es 2+2?" en un examen de matemáticas. Probar todas ellas es una pérdida de tiempo y aumenta injustamente la puntuación de cualquier modelo que sea bueno en ese tipo específico de pregunta.

2. La Solución: La Regla de "No Clones"

El equipo creó un sistema para elegir un grupo de preguntas más pequeño y más inteligente. Utilizaron un método llamado Conjunto Independiente Máximo (MIS, por sus siglas en inglés).

La Analogía: Imagina que estás organizando una fiesta y tienes una lista de 1,000 posibles invitados. Sin embargo, tienes una regla: No dos invitados que sean "demasiado similares" pueden ser invitados.
- Si el Invitado A y el Invitado B visten exactamente la misma ropa y hablan de exactamente el mismo tema, están "conectados". Solo puedes elegir a uno de ellos.
- El objetivo es invitar al número máximo de personas posible asegurándote de que ninguna pareja de personas en tu lista de invitados sea demasiado similar.
El Resultado: Terminas con una fiesta más pequeña (tal vez 300 personas en lugar de 1,000), pero la multitud es mucho más diversa. Has eliminado a los "clones" y conservado las voces únicas.

3. Cómo Construyeron la "Lista de Invitados"

Para determinar quién es "demasiado similar", no pidieron a humanos que leyeran las preguntas. En su lugar, usaron "traductores" de IA (modelos de embedding) para convertir cada pregunta en una coordenada en un mapa.

Las preguntas que significan lo mismo terminan cerca una de otra en el mapa.
Dibujaron un círculo alrededor de cada pregunta. Si otra pregunta caía dentro de ese círculo, se consideraban "demasiado similares".
Luego ejecutaron un algoritmo computacional para elegir el grupo más grande posible de preguntas donde ninguna pareja de preguntas cayera dentro del círculo de la otra.

4. Lo Que Encontraron

Probaron este método en cuatro tipos diferentes de pruebas (matemáticas, conocimientos generales, seguimiento de instrucciones, etc.) utilizando 66 modelos de IA diferentes.

Las Clasificaciones se Mantuvieron Iguales: Cuando eligieron este grupo más pequeño y diverso de preguntas, la clasificación de los chefs de IA (quién era el #1, #2, #3) fue casi idéntica a la clasificación que obtendrías si los probaras en las 1,000 preguntas.
- El Dato: En el 99.2% de sus pruebas, el orden de los chefs fue consistente, sin importar cómo se realizara el proceso de selección.
Ahorraron Mucho Tiempo: Dependiendo de qué tan estrictos fueran, pudieron reducir el número de preguntas en un 25% a 48% (y a veces incluso más) sin perder la capacidad de distinguir los mejores modelos.
La Corrección del "Sesgo": Debido a que eliminaron a los "clones", la prueba se volvió más justa. Si una prueba tenía demasiadas preguntas de "pasta picante", este método eliminó los excedentes, asegurando que la puntuación final reflejara una gama más amplia de habilidades, no solo un nicho específico.

5. El Problema (Cuando no funciona perfectamente)

El método funciona mejor cuando el "círculo de similitud" no es demasiado pequeño.

Si establecieron la regla demasiado estrictamente (permitiendo solo preguntas que son muy diferentes), terminaron con una lista de invitados diminuta que omitió temas importantes. Esto sucedió principalmente con pruebas que ya eran muy repetitivas o tenían patrones de puntuación extraños (como la prueba "IFEval").
Sin embargo, incluso en estos "fallos", los resultados fueron consistentes. La computadora siempre eligió el mismo pequeño grupo de preguntas, y ese grupo simplemente contó una historia ligeramente diferente a la de la prueba completa. Los autores argumentan que esto no es un error; es una característica que revela cuán sesgada estaba la prueba original.

Conclusión

El artículo demuestra que no es necesario probar los modelos de IA en miles de preguntas para saber quién es el mejor. Al usar una regla de "no clones" para elegir una muestra diversa y representativa, puedes:

Ahorrar cantidades masivas de potencia de cómputo y tiempo.
Obtener una puntuación más justa que no esté sesgada por tener demasiadas preguntas similares.
Confiar en los resultados, porque el método es estable y repetible.

Es como darse cuenta de que no necesitas probar cada gota de sopa en una olla gigante para saber si está salada; solo necesitas un par de cucharadas de diferentes partes de la olla para obtener el verdadero sabor.

Resumen Técnico: Selección de Prompts mediante Conjunto Independiente Máximo para un Benchmarking de LLM Consistente y Distintivo

Declaración del Problema

La evaluación rigurosa de los Modelos de Lenguaje Extensos (LLM) enfrenta dos desafíos primordiales: eficiencia de evaluación y sesgo de cobertura.

Eficiencia: Los benchmarks exhaustivos (por ejemplo, MMLU-Pro, GPQA) suelen contener cientos o miles de preguntas, lo que incurre en costos de inferencia sustanciales para los modelos de frontera y las tablas de clasificación (leaderboards) a gran escala.
Sesgo de Cobertura: Los prompts de los benchmarks están frecuentemente distribuidos de manera desigual en el espacio de embeddings. Si un benchmark sobrerepresenta regiones semánticas específicas (por ejemplo, numerosas preguntas similares de química), aumenta implícitamente el rendimiento del modelo en esas facetas específicas, distorsionando las clasificaciones independientemente de la capacidad general. Este sesgo estructural es invisible en las métricas agregadas pero surge de la redundancia semántica entre los prompts.

Los métodos existentes de selección de subconjuntos, como aquellos basados en la Teoría de Respuesta al Ítem (IRT), a menudo requieren interacción iterativa con el modelo o un modelado específico de la dificultad del ítem. Existe la necesidad de un enfoque agnóstico al modelo que seleccione prompts basándose únicamente en la similitud por pares para reducir simultáneamente los costos y corregir el sesgo de cobertura.

Metodología

Los autores proponen un marco teórico de grafos que modela cada benchmark como un grafo de similitud de prompts $G = (V, E)$ .

Construcción de Embeddings: Los prompts se mapean a vectores de dimensión fija utilizando diversos modelos de embedding (tanto basados en codificadores como en decodificadores).
Construcción del Grafo: Los nodos representan prompts. Un grafo no dirigido conecta dos nodos si su distancia en el espacio de embeddings supera un umbral configurable $\theta$ (definido como un percentil de la distribución de distancia empírica).
- Nota: El artículo define las aristas basadas en una distancia por encima de un umbral, lo que significa que los nodos conectados se consideran "disímiles" en el contexto de la lógica de construcción del MIS, o inversamente, el conjunto independiente asegura que los nodos seleccionados no estén conectados, lo que significa que están dentro del umbral de similitud?
- Corrección basada en el texto: El texto establece: "una arista conecta dos prompts... si su distancia en el espacio de embeddings cae por encima de un umbral configurable ( $d(e_u, e_v) \ge \theta$ )."
- Lógica del MIS: Un Conjunto Independiente Máximo (MIS) es un conjunto de nodos donde ningún par de ellos comparte una arista. Por lo tanto, en el subconjunto seleccionado, ningún par de prompts tiene una distancia $\ge \theta$ . Esto implica que todos los prompts seleccionados están dentro de la distancia $\theta$ entre sí?
- Relectura cuidadosa del texto: El texto dice: "un nodo se conecta a otro si su distancia... cae por encima de un umbral configurable... Bajo esta construcción, un conjunto independiente corresponde a un subconjunto de prompts cuyas distancias de par permanecen por debajo del umbral $\theta$ ."
- Verificación de contradicción lógica: Si una arista existe cuando la distancia $\ge \theta$ (disimilitud), un Conjunto Independiente (sin aristas) significa que todos los pares tienen una distancia $< \theta$ (similitud). Esto seleccionaría un grupo de prompts similares, lo cual contradice el objetivo de "máxima diversidad".
- Interpretación alternativa del texto: El texto dice: "los nodos son prompts conectados si su distancia en el espacio de embeddings cae por encima de un umbral configurable... el MIS... selecciona un subconjunto máximamente diverso y no redundante."
- Lógica estándar del MIS en Redundancia: Usualmente, las aristas conectan elementos similares (distancia $< \theta$ ), y el MIS selecciona elementos que no son similares (sin aristas).
- Decisión de la Metodología: Existe una potencial inconsistencia en la descripción del texto respecto a la condición de la arista frente al resultado del MIS, pero el objetivo es claro: utilizar el MIS para seleccionar un subconjunto donde ningún par de prompts sea semánticamente cercano (diversidad).
Selección de Conjunto Independiente Máximo (MIS): El problema se plantea como la búsqueda del subconjunto más grande $S$ de nodos tal que ningún par de ellos comparta una arista.
- Algoritmos evaluados: Se probaron cuatro solvers:
  - CPLEX: Solver exacto (Programación Lineal Entera).
  - GREEDY: Heurística determinista (vértice de menor grado).
  - Online-MIS: Heurística de flujo (streaming) aleatorizada.
  - ReduMIS: Kernelización de grafos + búsqueda local estocástica.
- Estocasticidad: Los solvers estocásticos (Online-MIS, ReduMIS) se ejecutaron con 5 semillas aleatorias para probar la consistencia.
Métricas de Evaluación:
- Acuerdo de Clasificación ( $\rho$ ): Correlación de rango de Spearman entre la clasificación del subconjunto y la clasificación del benchmark completo.
- Consistencia ( $W$ ): Coeficiente de concordancia de Kendall a través de las semillas aleatorias. Un $W \ge 0.90$ indica una concordancia casi perfecta.

Contribuciones Clave

Marco Teórico de Grafos: Un marco de selección de prompts agnóstico al modelo que aborda la eficiencia y el sesgo de cobertura simultáneamente mediante la selección de un subconjunto máximamente diverso y no redundante vía MIS.
Validación Empírica Exhaustiva: Evaluación a través de 2,563 configuraciones únicas que involucran:
- 4 Benchmarks (GPQA, IFEval, MMLU-Pro, Omni-MATH).
- 66 LLMs de frontera.
- 6 Modelos de Embedding (3 codificadores pequeños, 3 decodificadores grandes).
- 3 Medidas de Distancia (Coseno, Pearson, Euclídea estandarizada).
- 6 Umbrales de percentil ( $p10$ – $p95$ ).
- 4 Solvers de MIS.
Confirmación de Hipótesis: La hipótesis central —que la selección repetida de MIS genera clasificaciones consistentes que pueden diferir de la línea base del benchmark completo debido a la corrección del sesgo de cobertura— se confirma sólidamente.

Resultados

Consistencia: La hipótesis de consistencia se cumple con fuerza. En el 99.2% de las configuraciones estocásticas, el coeficiente de Kendall $W \ge 0.90$ (media $W = 0.997 \pm 0.008$ ). Esto indica que diferentes semillas aleatorias producen clasificaciones altamente estables.
Divergencia de Clasificación: La divergencia de la clasificación respecto al benchmark completo ( $\rho < 0.95$ $ρ < 0.95$ ) ocurrió en solo el 15.95% de las configuraciones.
- Estas divergencias se concentraron en umbrales bajos ( $p10$ – $p20$ ) y benchmarks específicos (GPQA y IFEval).
- Los autores identifican los grafos excesivamente densos (que retienen muy pocos prompts representativos) como el principal modo de falla para estas divergencias.
Eficiencia: En umbrales de percentil más altos (por ejemplo, $p80$ ), el método logra una reducción de prompts del 25–48% en promedio, manteniendo una alta fidelidad de clasificación ( $\rho \approx 0.992$ ).
Desempeño de Algoritmos:
- ReduMIS y Online-MIS (estocásticos) mostraron la mayor concordancia ( $W \approx 0.997$ ).
- CPLEX y GREEDY (deterministas) alcanzaron correlaciones de clasificación similares ( $\rho \approx 0.968$ ) pero no ofrecen métricas de consistencia basadas en semillas.
Modelos de Embedding: Los modelos basados en decodificadores grandes (por ejemplo, Qwen-8B, Nemotron-8B) generalmente superaron a los modelos basados en codificadores pequeños en la preservación de la estructura de clasificación, particularmente con la distancia euclídea estandarizada.
Efectos del Umbral:
- $p80$ se identifica como el compromiso óptimo, ofreciendo una preservación de clasificación casi perfecta ( $\rho=0.992$ ) con una reducción del 37–45%.
- $p10$ – $p20$ (poda agresiva) mostró una correlación menor ( $\rho \approx 0.905$ ) pero aún una alta consistencia ( $W \approx 0.990$ ), lo que sugiere que el subconjunto es estable pero distinto de la línea base completa sesgada.

Significado y Reivindicaciones

El artículo sostiene que la selección de prompts basada en MIS es un enfoque basado en principios y eficiente que redefine la evaluación de los LLM:

Reencuadre de la Divergencia: Una correlación de Spearman más baja ( $\rho < 0.95$ ) entre un subconjunto y el benchmark completo no es necesariamente un defecto. Si el benchmark completo tiene un sesgo de cobertura, el subconjunto MIS proporciona una perspectiva corregida y distintiva al reducir el peso de las facetas sobrerepresentadas. La alta consistencia ( $W$ ) confirma que esta clasificación "distintiva" es reproducible.
2.Detección de Sesgo Estructural: La distribución de grados del grafo de similitud sirve como un diagnóstico para el sesgo de cobertura. Los benchmarks con centros de alto grado (muchos duplicados cercanos) son los más propensos al sesgo y se benefician más de la selección por MIS.
Recomendación Práctica: Los autores recomiendan una configuración de solver ReduMIS + embedding Qwen-8B + distancia Euclídea estandarizada + umbral $p80$ para la mayoría de los benchmarks, logrando $W=1.000$ y $\rho=0.9959$ .

Este trabajo extiende el marco SELECTOR (utilizado previamente para la optimización numérica) a los prompts de lenguaje natural, demostrando que las garantías de cobertura estructural se transfieren a la evaluación de LLM sin requerir interacción iterativa con el modelo.