diff --git a/config/dev.yml b/config/dev.yml
--- a/config/dev.yml
+++ b/config/dev.yml
@@ -9,3 +9,6 @@
 debug: yes
 
 server-type: asgi
+
+max_query_cost:
+  anonymous: 500
diff --git a/config/staging.yml b/config/staging.yml
--- a/config/staging.yml
+++ b/config/staging.yml
@@ -9,3 +9,6 @@
 debug: no
 
 server-type: asgi
+
+max_query_cost:
+  anonymous: 500
diff --git a/swh/graphql/app.py b/swh/graphql/app.py
--- a/swh/graphql/app.py
+++ b/swh/graphql/app.py
@@ -8,6 +8,7 @@
 from pathlib import Path
 
 from ariadne import gql, load_schema_from_path, make_executable_schema
+from ariadne.validation import cost_validator
 
 from .resolvers import resolvers, scalars
 
@@ -41,3 +42,13 @@
     scalars.swhid_scalar,
     scalars.content_hash_scalar,
 )
+
+
+def validation_rules(context_value, document, data):
+    from .server import graphql_cfg
+
+    # add logic to set max_query_cost per user type
+    max_query_cost = graphql_cfg["max_query_cost"]["anonymous"]
+    if max_query_cost:
+        return [cost_validator(maximum_cost=max_query_cost)]
+    return None
diff --git a/swh/graphql/schema/schema.graphql b/swh/graphql/schema/schema.graphql
--- a/swh/graphql/schema/schema.graphql
+++ b/swh/graphql/schema/schema.graphql
@@ -1,3 +1,5 @@
+directive @cost(complexity: Int, multipliers: [String!], useMultipliers: Boolean) on FIELD | FIELD_DEFINITION
+
 """
 SoftWare Heritage persistent Identifier
 """
@@ -132,12 +134,12 @@
     Returns the page after this cursor
     """
     after: String
-  ): VisitConnection!
+  ): VisitConnection! @cost(complexity: 1, multipliers: ["first"])
 
   """
   Latest visit object for the origin
   """
-  latestVisit: Visit
+  latestVisit: Visit @cost(complexity: 1)
 
   """
   Connection to all the snapshots for the origin
@@ -152,7 +154,7 @@
     Returns the page after this cursor
     """
     after: String
-  ): SnapshotConnection
+  ): SnapshotConnection @cost(complexity: 2, multipliers: ["first"])  # This costs more because of local (graphql level) pagination
 }
 
 """
@@ -244,7 +246,7 @@
     Returns the page after this cursor
     """
     after: String
-  ): VisitStatusConnection
+  ): VisitStatusConnection @cost(complexity: 3)  # here first is optional, hence adding a higher value for cost
 
   """
   Latest status object for the Visit
@@ -259,7 +261,7 @@
     Filter by the availability of a snapshot in the status
     """
     requireSnapshot: Boolean
-  ): VisitStatus
+  ): VisitStatus @cost(complexity: 1)
 }
 
 """
@@ -319,7 +321,7 @@
   """
   Snapshot object
   """
-  snapshot: Snapshot
+  snapshot: Snapshot @cost(complexity: 1)
 
   """
   Type of the origin visited. Eg: git/hg/svn/tar/deb
@@ -404,7 +406,7 @@
     Filter by branch name
     """
     nameInclude: String
-  ): BranchConnection
+  ): BranchConnection @cost(complexity: 2, multipliers: ["first"])  # This costs more because of local (graphql level) pagination
 }
 
 """
@@ -501,7 +503,7 @@
   """
   Branch target object
   """
-  target: BranchTarget
+  target: BranchTarget @cost(complexity: 1)
 }
 
 """
@@ -584,7 +586,7 @@
   """
   The unique directory object that revision points to
   """
-  directory: Directory
+  directory: Directory @cost(complexity: 1)
 
   """
   Connection to all the parents of the revision
@@ -599,7 +601,7 @@
     Returns the page after this cursor
     """
     after: String
-  ): RevisionConnection
+  ): RevisionConnection @cost(complexity: 3) # here first is not mandatory, hence adding a higher value for cost
 
   """
   Connection to all the revisions heading to this one
@@ -615,7 +617,7 @@
     Returns the page after the cursor
     """
     after: String
-  ): RevisionConnection
+  ): RevisionConnection @cost(complexity: 2, multipliers: ["first"]) # This costs more because of local (graphql level) pagination
 }
 
 """
@@ -674,7 +676,7 @@
   """
   Release target object
   """
-  target: ReleaseTarget
+  target: ReleaseTarget @cost(complexity: 1)
 }
 
 """
@@ -748,7 +750,7 @@
   """
   Directory entry target object
   """
-  target: DirectoryEntryTarget
+  target: DirectoryEntryTarget @cost(complexity: 1)
 }
 
 """
@@ -772,7 +774,7 @@
     """
     Returns the first _n_ elements from the list
     """
-    first: Int
+    first: Int!
 
     """
     Returns the page after this cursor
@@ -783,7 +785,7 @@
     Filter by entry name
     """
     nameInclude: String
-  ): DirectoryEntryConnection
+  ): DirectoryEntryConnection @cost(complexity: 2, multipliers: ["first"]) # pagination is local, hence adding a higher value for cost
 }
 
 """
@@ -945,7 +947,7 @@
   """
   Result target object
   """
-  target: SearchResultTarget
+  target: SearchResultTarget @cost(complexity: 1)
 }
 
 """
@@ -960,7 +962,7 @@
     URL of the Origin
     """
     url: String!
-  ): Origin
+  ): Origin @cost(complexity: 1)
 
   """
   Get a Connection to all the origins
@@ -980,7 +982,7 @@
     Filter origins with a URL pattern
     """
     urlPattern: String
-  ): OriginConnection
+  ): OriginConnection @cost(complexity: 1, multipliers: ["first"])
 
   """
   Get the visit object with an origin URL and a visit id
@@ -995,7 +997,7 @@
     Visit id to get
     """
     visitId: Int!
-  ): Visit
+  ): Visit @cost(complexity: 1)
 
   """
   Get the snapshot with a SWHID
@@ -1005,7 +1007,7 @@
     SWHID of the snapshot object
     """
     swhid: SWHID!
-  ): Snapshot
+  ): Snapshot @cost(complexity: 1)
 
   """
   Get the revision with a SWHID
@@ -1015,7 +1017,7 @@
     SWHID of the revision object
     """
     swhid: SWHID!
-  ): Revision
+  ): Revision @cost(complexity: 1)
 
   """
   Get the release with a SWHID
@@ -1025,7 +1027,7 @@
     SWHID of the release object
     """
     swhid: SWHID!
-  ): Release
+  ): Release @cost(complexity: 1)
 
   """
   Get the directory with a SWHID
@@ -1035,7 +1037,7 @@
     SWHID of the directory object
     """
     swhid: SWHID!
-  ): Directory
+  ): Directory @cost(complexity: 1)
 
   """
   Get a directory entry with directory SWHID and a path
@@ -1050,7 +1052,7 @@
     Relative path to the requested object
     """
     path: String!
-  ): DirectoryEntry
+  ): DirectoryEntry @cost(complexity: 1)
 
   """
   Get the content with a SWHID
@@ -1060,7 +1062,7 @@
     SWHID of the content object
     """
     swhid: SWHID!
-  ): Content
+  ): Content @cost(complexity: 1)
 
   """
   Get the content by one or more hashes
@@ -1071,7 +1073,7 @@
     List of hashType:hashValue strings
     """
     checksums: [ContentHash]!
-  ): Content
+  ): Content @cost(complexity: 1)
 
   """
   Resolve the given SWHID to an object
@@ -1081,7 +1083,7 @@
     SWHID to look for
     """
     swhid: SWHID!
-  ): SearchResultConnection!
+  ): SearchResultConnection! @cost(complexity: 1)
 
   """
   Search in SWH
@@ -1101,5 +1103,5 @@
     Returns the page after the cursor
     """
     after: String
-  ): SearchResultConnection!
+  ): SearchResultConnection! @cost(complexity: 1, multipliers: ["first"])
 }
diff --git a/swh/graphql/server.py b/swh/graphql/server.py
--- a/swh/graphql/server.py
+++ b/swh/graphql/server.py
@@ -66,7 +66,7 @@
     """
     from starlette.middleware.cors import CORSMiddleware
 
-    from .app import schema
+    from .app import schema, validation_rules
     from .errors import format_error
 
     global graphql_cfg
@@ -80,7 +80,12 @@
         from ariadne.asgi import GraphQL
 
         application = CORSMiddleware(
-            GraphQL(schema, debug=graphql_cfg["debug"], error_formatter=format_error),
+            GraphQL(
+                schema,
+                debug=graphql_cfg["debug"],
+                validation_rules=validation_rules,
+                error_formatter=format_error,
+            ),
             # FIXME, restrict origins after deploying the JS client
             allow_origins=["*"],
             allow_methods=("GET", "POST", "OPTIONS"),
diff --git a/swh/graphql/tests/conftest.py b/swh/graphql/tests/conftest.py
--- a/swh/graphql/tests/conftest.py
+++ b/swh/graphql/tests/conftest.py
@@ -9,7 +9,7 @@
 import pytest
 
 from swh.graphql import server as app_server
-from swh.graphql.app import schema
+from swh.graphql.app import schema, validation_rules
 from swh.graphql.errors import format_error
 from swh.search import get_search as get_swh_search
 from swh.storage import get_storage as get_swh_storage
@@ -38,6 +38,11 @@
     return search
 
 
+@pytest.fixture(autouse=True)
+def config():
+    app_server.graphql_cfg = {"max_query_cost": {"anonymous": 100}}
+
+
 @pytest.fixture(scope="session")
 def test_app(storage, search):
     app = Flask(__name__)
@@ -51,6 +56,7 @@
             data,
             context_value=request,
             debug=app.debug,
+            validation_rules=validation_rules,
             error_formatter=format_error,
         )
         status_code = 200 if success else 400
diff --git a/swh/graphql/tests/functional/test_directory_entry.py b/swh/graphql/tests/functional/test_directory_entry.py
--- a/swh/graphql/tests/functional/test_directory_entry.py
+++ b/swh/graphql/tests/functional/test_directory_entry.py
@@ -102,7 +102,7 @@
     {
       directory(swhid: "%s") {
         swhid
-        entries {
+        entries(first: 10) {
           nodes {
             targetType
             name {
diff --git a/swh/graphql/tests/functional/test_pagination.py b/swh/graphql/tests/functional/test_pagination.py
--- a/swh/graphql/tests/functional/test_pagination.py
+++ b/swh/graphql/tests/functional/test_pagination.py
@@ -53,6 +53,11 @@
 
 
 def test_too_big_first_arg(client):
+    from swh.graphql import server as app_server
+
+    # set the query cost limit to a higher value for this test
+    app_server.graphql_cfg = {"max_query_cost": {"anonymous": 2000}}
+
     data, errors = get_origin_nodes(client, 1001)  # max page size is 1000
     assert data["origins"] is None
     assert (len(errors)) == 2
diff --git a/swh/graphql/tests/functional/test_query_cost.py b/swh/graphql/tests/functional/test_query_cost.py
new file mode 100644
--- /dev/null
+++ b/swh/graphql/tests/functional/test_query_cost.py
@@ -0,0 +1,111 @@
+# Copyright (C) 2022 The Software Heritage developers
+# See the AUTHORS file at the top-level directory of this distribution
+# License: GNU General Public License version 3, or any later version
+# See top-level LICENSE file for more information
+
+from . import utils
+from ..data import get_snapshots
+
+
+def test_valid_query(client):
+    query_str = """
+    {
+      origins(first: 2) {
+        nodes {
+          url
+        }
+      }
+    }
+    """
+    response, _ = utils.get_query_response(client, query_str)
+    assert len(response["origins"]["nodes"]) == 2
+
+
+def test_query_cost_simple(client):
+    query_str = """
+    {
+      origins(first: 1000) {
+        nodes {
+          url
+        }
+      }
+    }
+    """
+    errors = utils.get_error_response(client, query_str)
+    assert (
+        "The query exceeds the maximum cost of 100. Actual cost is 1000"
+        in errors[0]["message"]
+    )
+
+
+def test_query_cost_origin(client):
+    query_str = """
+    {
+      origins(first: 10) {
+        nodes {
+          url
+          latestVisit {
+            date
+          }
+          visits(first: 5) {
+            nodes {
+              date
+              status {
+                nodes {
+                  date
+                }
+              }
+            }
+          }
+          snapshots(first: 5) {
+            nodes {
+              swhid
+            }
+          }
+        }
+      }
+    }
+    """
+    # Total cost here is 170
+    # 10 (origin) + 10 (latestVisit) + 10*5 (visits) + 10 * 5 * 3 (status) +
+    # 10 * 5*2 (snapshots) = 320
+    errors = utils.get_error_response(client, query_str)
+    assert (
+        "The query exceeds the maximum cost of 100. Actual cost is 320"
+        in errors[0]["message"]
+    )
+
+
+def test_query_cost_snapshots(client):
+    query_str = """
+    {
+      snapshot(swhid: "%s") {
+        branches(first: 50) {
+          nodes {
+            target {
+              ...on Revision {
+                swhid
+              }
+              ...on Directory {
+                swhid
+                entries(first: 3) {
+                  nodes {
+                    type
+                  }
+                }
+              }
+            }
+          }
+        }
+      }
+    }
+    """
+    # Total cost here is 157
+    # 1 (snapshot) + 2 *50 (branches) + 50 * 1 (revision or Directory) +  3 * 2 = 157
+    # parent multiplier is not applied when schema introspection is used
+    # ie: directory entry connection cost is 3 * 2 and not 50 * 3 * 2
+    errors = utils.get_error_response(client, query_str % get_snapshots()[0].swhid())
+    assert (
+        "The query exceeds the maximum cost of 100. Actual cost is 157"
+        in errors[0]["message"]
+    )
diff --git a/swh/graphql/tests/functional/test_release_node.py b/swh/graphql/tests/functional/test_release_node.py
--- a/swh/graphql/tests/functional/test_release_node.py
+++ b/swh/graphql/tests/functional/test_release_node.py
@@ -83,6 +83,7 @@
     errors = utils.get_error_response(client, query_str)
     # API will throw an error in case of an invalid SWHID
     assert len(errors) == 1
+    assert "Input error: Invalid SWHID" in errors[0]["message"]
 
 
 @pytest.mark.parametrize("release_with_target", get_releases_with_target())
diff --git a/swh/graphql/utils/__init__.py b/swh/graphql/utils/__init__.py
new file mode 100644