--- a/taskcluster/taskgraph/util/verify.py
+++ b/taskcluster/taskgraph/util/verify.py
@@ -1,31 +1,36 @@
 # -*- coding: utf-8 -*-
 # This Source Code Form is subject to the terms of the Mozilla Public
 # License, v. 2.0. If a copy of the MPL was not distributed with this
 # file, You can obtain one at http://mozilla.org/MPL/2.0/.
 
 import re
 import os
+import sys
 
 base_path = os.path.join(os.getcwd(), "taskcluster/docs/")
 
 
 class VerificationSequence(object):
     """
     Container for a sequence of verifications over a TaskGraph. Each
     verification is represented as a callable taking (task, taskgraph,
-    scratch_pad), called for each task in the taskgraph.
+    scratch_pad), called for each task in the taskgraph, and one more
+    time with no task but with the taskgraph and the same scratch_pad
+    that was passed for each task.
     """
     def __init__(self):
         self.verifications = {}
 
     def __call__(self, graph_name, graph):
         for verification in self.verifications.get(graph_name, []):
-            graph.for_each_task(verification, scratch_pad={})
+            scratch_pad = {}
+            graph.for_each_task(verification, scratch_pad=scratch_pad)
+            verification(None, graph, scratch_pad=scratch_pad)
         return graph_name, graph
 
     def add(self, graph_name):
         def wrap(func):
             self.verifications.setdefault(graph_name, []).append(func)
             return func
         return wrap
 
@@ -66,16 +71,18 @@ def verify_docs(filename, identifiers, a
 
 @verifications.add('full_task_graph')
 def verify_task_graph_symbol(task, taskgraph, scratch_pad):
     """
         This function verifies that tuple
         (collection.keys(), machine.platform, groupSymbol, symbol) is unique
         for a target task graph.
     """
+    if task is None:
+        return
     task_dict = task.task
     if "extra" in task_dict:
         extra = task_dict["extra"]
         if "treeherder" in extra:
             treeherder = extra["treeherder"]
 
             collection_keys = tuple(sorted(treeherder.get('collection', {}).keys()))
             platform = treeherder.get('machine', {}).get('platform')
@@ -93,21 +100,46 @@ def verify_task_graph_symbol(task, taskg
 
 
 @verifications.add('full_task_graph')
 def verify_gecko_v2_routes(task, taskgraph, scratch_pad):
     """
         This function ensures that any two
         tasks have distinct index.v2.routes
     """
+    if task is None:
+        return
     route_prefix = "index.gecko.v2"
     task_dict = task.task
     routes = task_dict.get('routes', [])
 
     for route in routes:
         if route.startswith(route_prefix):
             if route in scratch_pad:
                 raise Exception(
                     "conflict between {}:{} for route: {}"
                     .format(task.label, scratch_pad[route], route)
                 )
             else:
                 scratch_pad[route] = task.label
+
+
+@verifications.add('full_task_graph')
+def verify_dependency_tiers(task, taskgraph, scratch_pad):
+    tiers = scratch_pad
+    if task is not None:
+        tiers[task.label] = task.task.get('extra', {}) \
+                                     .get('treeherder', {}) \
+                                     .get('tier', sys.maxint)
+    else:
+        def printable_tier(tier):
+            if tier == sys.maxint:
+                return 'unknown'
+            return tier
+
+        for task in taskgraph.tasks.itervalues():
+            tier = tiers[task.label]
+            for d in task.dependencies.itervalues():
+                if tier < tiers[d]:
+                    raise Exception(
+                        '{} (tier {}) cannot depend on {} (tier {})'
+                        .format(task.label, printable_tier(tier),
+                                d, printable_tier(tiers[d])))