Dans cette étude, nous présentons une méthode de prédiction structurée efficace en temps et en mémoire, qui associe les décisions neuronales à la fois dans l'espace et dans le temps. Nous démontrons que nous sommes capables d'effectuer une inférence exacte et efficace sur un graphe spatio-temporel densément connecté en exploitant les récents progrès réalisés dans les Champs Aléatoires Conditionnels Gaussiens profonds (GCRFs). Notre méthode, appelée VideoGCRF, est (a) efficace, (b) possède un minimum global unique, et (c) peut être formée de manière end-to-end aux côtés des réseaux profonds contemporains pour la compréhension vidéo. Nous expérimentons avec plusieurs schémas de connectivité dans le domaine temporel et présentons des améliorations empiriques par rapport à des baselines solides sur les tâches de segmentation sémantique et d'instances de vidéos.