In dieser Arbeit stellen wir eine zeit- und speichereffiziente Methode für strukturierte Vorhersage vor, die Neuronenentscheidungen sowohl im Raum als auch in der Zeit verbindet. Wir zeigen, dass wir durch den Einsatz jüngster Fortschritte bei tiefen Gaußschen konditionellen Markovfeldern (GCRFs) exakte und effiziente Inferenz auf einem dicht verbundenen räumlich-zeitlichen Graphen durchführen können. Unsere Methode, VideoGCRF genannt, ist (a) effizient, (b) besitzt ein eindeutiges globales Minimum und (c) kann end-to-end zusammen mit modernen tiefen Netzen zur Videobearbeitung trainiert werden. Wir experimentieren mit verschiedenen Verbindungsmustern im zeitlichen Bereich und präsentieren empirische Verbesserungen gegenüber starken Baseline-Methoden bei den Aufgaben der semantischen und instanzbasierten Segmentierung von Videos.