Considerando el peor escenario posible, el algoritmo de árbol de unión sigue siendo la solución más general para la inferencia MAP exacta con garantías de tiempo de ejecución polinómico. Desafortunadamente, su principal suposición de tratabilidad requiere que el ancho del árbol de un MRF correspondiente esté limitado, lo que limita fuertemente el rango de aplicaciones admisibles. De hecho, muchos problemas prácticos en el área de predicción estructurada requieren modelar dependencias globales ya sea introduciendo directamente factores globales o imponiendo restricciones globales en las variables de predicción. Sin embargo, esto siempre resulta en un grafo completamente conectado, lo que hace que las inferencias exactas mediante este algoritmo sean intratables. Trabajos anteriores que se centran en el problema de la inferencia aumentada por pérdida han demostrado cómo se puede realizar una inferencia eficiente en modelos con factores globales específicos que representan funciones de pérdida no descomponibles dentro del régimen de entrenamiento de SSVMs. Haciendo la observación de que la misma idea fundamental se puede aplicar para resolver una clase más amplia de problemas computacionales, en este documento ajustamos el marco para una inferencia exacta eficiente para permitir interacciones mucho más finas entre la energía del modelo central y las estadísticas suficientes de los términos globales. Como resultado, aumentamos considerablemente el rango de aplicaciones admisibles y mejoramos sustancialmente las garantías teóricas de eficiencia computacional. Ilustramos la aplicabilidad de nuestro método en varios casos de uso, incluido uno que no está cubierto por la formulación previa del problema. Además, proponemos una nueva técnica de transformación de gráficos mediante clonación de nodos, que garantiza un tiempo de ejecución polinómico para resolver nuestro problema objetivo. En particular, la complejidad computacional general de nuestro algoritmo de paso de mensajes restringido depende solo de cantidades independientes de la forma como el ancho de un grafo correspondiente (sin conexiones globales) y el tamaño de imagen de las estadísticas suficientes de los términos globales.