diff --git a/java/pom.xml b/java/pom.xml
--- a/java/pom.xml
+++ b/java/pom.xml
@@ -36,6 +36,12 @@
         <version>5.7.0</version>
         <scope>test</scope>
     </dependency>
+    <dependency>
+      <groupId>org.junit.jupiter</groupId>
+      <artifactId>junit-jupiter-params</artifactId>
+      <version>5.7.0</version>
+      <scope>test</scope>
+    </dependency>
     <dependency>
       <groupId>org.slf4j</groupId>
       <artifactId>slf4j-simple</artifactId>
diff --git a/java/src/main/java/org/softwareheritage/graph/rpc/Traversal.java b/java/src/main/java/org/softwareheritage/graph/rpc/Traversal.java
--- a/java/src/main/java/org/softwareheritage/graph/rpc/Traversal.java
+++ b/java/src/main/java/org/softwareheritage/graph/rpc/Traversal.java
@@ -238,6 +238,7 @@
         private final TraversalRequest request;
         private final NodePropertyBuilder.NodeDataMask nodeDataMask;
         private final NodeObserver nodeObserver;
+        private long remainingMatches;
 
         private Node.Builder nodeBuilder;
 
@@ -258,6 +259,11 @@
             if (request.hasMaxEdges()) {
                 setMaxEdges(request.getMaxEdges());
             }
+            if (request.hasMaxMatchingNodes() && request.getMaxMatchingNodes() > 0) {
+                this.remainingMatches = request.getMaxMatchingNodes();
+            } else {
+                this.remainingMatches = -1;
+            }
         }
 
         @Override
@@ -273,14 +279,28 @@
                 NodePropertyBuilder.buildNodeProperties(g, nodeDataMask, nodeBuilder, node);
             }
             super.visitNode(node);
-            if (request.getReturnNodes().hasMinTraversalSuccessors()
-                    && traversalSuccessors < request.getReturnNodes().getMinTraversalSuccessors()
-                    || request.getReturnNodes().hasMaxTraversalSuccessors()
-                            && traversalSuccessors > request.getReturnNodes().getMaxTraversalSuccessors()) {
-                nodeBuilder = null;
+
+            boolean nodeMatchesConstraints = true;
+
+            if (request.getReturnNodes().hasMinTraversalSuccessors()) {
+                nodeMatchesConstraints &= traversalSuccessors >= request.getReturnNodes().getMinTraversalSuccessors();
             }
-            if (nodeBuilder != null) {
-                nodeObserver.onNext(nodeBuilder.build());
+            if (request.getReturnNodes().hasMaxTraversalSuccessors()) {
+                nodeMatchesConstraints &= traversalSuccessors <= request.getReturnNodes().getMaxTraversalSuccessors();
+            }
+
+            if (nodeMatchesConstraints) {
+                if (nodeBuilder != null) {
+                    nodeObserver.onNext(nodeBuilder.build());
+                }
+
+                if (remainingMatches >= 0) {
+                    remainingMatches--;
+                    if (remainingMatches == 0) {
+                        // We matched as many nodes as allowed
+                        throw new StopTraversalException();
+                    }
+                }
             }
         }
 
diff --git a/java/src/test/java/org/softwareheritage/graph/GraphTest.java b/java/src/test/java/org/softwareheritage/graph/GraphTest.java
--- a/java/src/test/java/org/softwareheritage/graph/GraphTest.java
+++ b/java/src/test/java/org/softwareheritage/graph/GraphTest.java
@@ -22,6 +22,7 @@
 import org.junit.jupiter.api.BeforeAll;
 
 import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.fail;
 
 public class GraphTest {
     static SwhBidirectionalGraph graph;
@@ -53,6 +54,34 @@
         assertEquals(expectedList, actualList);
     }
 
+    public static <T> void assertContainsAll(Collection<T> expected, Collection<T> actual) {
+        ArrayList<T> expectedList = new ArrayList<>(expected);
+        ArrayList<T> actualList = new ArrayList<>(actual);
+        expectedList.sort(Comparator.comparing(Object::toString));
+        Iterator<T> expectedIterator = expectedList.iterator();
+
+        actualList.sort(Comparator.comparing(Object::toString));
+
+        for (T actualItem : actualList) {
+            boolean found = false;
+            while (expectedIterator.hasNext()) {
+                if (expectedIterator.next().equals(actualItem)) {
+                    found = true;
+                    break;
+                }
+            }
+            if (!found) {
+                // TODO: better message when actualItem is present twice in actualList,
+                // but only once in expectedList
+                fail(String.format("%s not found in %s", actualItem, expectedList));
+            }
+        }
+    }
+
+    public static <T> void assertLength(int expected, Collection<T> actual) {
+        assertEquals(String.format("Size of collection %s:", actual), expected, actual.size());
+    }
+
     public static ArrayList<Long> lazyLongIteratorToList(LazyLongIterator input) {
         ArrayList<Long> inputList = new ArrayList<>();
         Iterator<Long> inputIt = LazyLongIterators.eager(input);
diff --git a/java/src/test/java/org/softwareheritage/graph/rpc/CountEdgesTest.java b/java/src/test/java/org/softwareheritage/graph/rpc/CountEdgesTest.java
--- a/java/src/test/java/org/softwareheritage/graph/rpc/CountEdgesTest.java
+++ b/java/src/test/java/org/softwareheritage/graph/rpc/CountEdgesTest.java
@@ -15,6 +15,8 @@
 
 import static org.junit.jupiter.api.Assertions.assertEquals;
 import static org.junit.jupiter.api.Assertions.assertThrows;
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.ValueSource;
 
 public class CountEdgesTest extends TraversalServiceTest {
     private TraversalRequest.Builder getTraversalRequestBuilder(SWHID src) {
@@ -41,6 +43,29 @@
         assertEquals(13, actual.getCount());
     }
 
+    @ParameterizedTest
+    @ValueSource(ints = {0, 1, 2, 13, 14, 15, Integer.MAX_VALUE})
+    public void forwardFromRootWithLimit(int limit) {
+        CountResponse actual = client
+                .countEdges(getTraversalRequestBuilder(new SWHID(TEST_ORIGIN_ID)).setMaxMatchingNodes(limit).build());
+
+        switch (limit) {
+            case 1:
+                // 1. origin -> snp:20
+                assertEquals(1, actual.getCount());
+                break;
+            case 2:
+                // 1. origin -> snp:20
+                // 2. either snp:20 -> rev:9 or snp:20 -> rel:10
+                assertEquals(3, actual.getCount());
+                break;
+            default :
+                // Counts all edges
+                assertEquals(13, actual.getCount());
+                break;
+        }
+    }
+
     @Test
     public void forwardFromMiddle() {
         CountResponse actual = client.countEdges(getTraversalRequestBuilder(fakeSWHID("dir", 12)).build());
diff --git a/java/src/test/java/org/softwareheritage/graph/rpc/CountNodesTest.java b/java/src/test/java/org/softwareheritage/graph/rpc/CountNodesTest.java
--- a/java/src/test/java/org/softwareheritage/graph/rpc/CountNodesTest.java
+++ b/java/src/test/java/org/softwareheritage/graph/rpc/CountNodesTest.java
@@ -15,6 +15,8 @@
 
 import static org.junit.jupiter.api.Assertions.assertEquals;
 import static org.junit.jupiter.api.Assertions.assertThrows;
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.ValueSource;
 
 public class CountNodesTest extends TraversalServiceTest {
     private TraversalRequest.Builder getTraversalRequestBuilder(SWHID src) {
@@ -41,6 +43,19 @@
         assertEquals(12, actual.getCount());
     }
 
+    @ParameterizedTest
+    @ValueSource(ints = {0, 1, 2, 5, 11, 12, 13, 14, 15, Integer.MAX_VALUE})
+    public void forwardFromRootWithLimit(int limit) {
+        CountResponse actual = client
+                .countNodes(getTraversalRequestBuilder(new SWHID(TEST_ORIGIN_ID)).setMaxMatchingNodes(limit).build());
+
+        if (limit == 0) {
+            assertEquals(12, actual.getCount());
+        } else {
+            assertEquals(Math.min(limit, 12), actual.getCount());
+        }
+    }
+
     @Test
     public void forwardFromMiddle() {
         CountResponse actual = client.countNodes(getTraversalRequestBuilder(fakeSWHID("dir", 12)).build());
@@ -75,6 +90,14 @@
         assertEquals(6, actual.getCount());
     }
 
+    @ParameterizedTest
+    @ValueSource(ints = {1, 2, 3, 4, 5, 6, 7})
+    public void backwardRevToRevRevToRelWithLimit(int limit) {
+        CountResponse actual = client.countNodes(getTraversalRequestBuilder(fakeSWHID("rev", 3))
+                .setEdges("rev:rev,rev:rel").setDirection(GraphDirection.BACKWARD).setMaxMatchingNodes(limit).build());
+        assertEquals(Math.min(limit, 6), actual.getCount());
+    }
+
     @Test
     public void testWithEmptyMask() {
         CountResponse actual = client.countNodes(
diff --git a/java/src/test/java/org/softwareheritage/graph/rpc/TraverseLeavesTest.java b/java/src/test/java/org/softwareheritage/graph/rpc/TraverseLeavesTest.java
--- a/java/src/test/java/org/softwareheritage/graph/rpc/TraverseLeavesTest.java
+++ b/java/src/test/java/org/softwareheritage/graph/rpc/TraverseLeavesTest.java
@@ -8,6 +8,8 @@
 package org.softwareheritage.graph.rpc;
 
 import org.junit.jupiter.api.Test;
+import org.junit.jupiter.params.ParameterizedTest;
+import org.junit.jupiter.params.provider.ValueSource;
 import org.softwareheritage.graph.GraphTest;
 import org.softwareheritage.graph.SWHID;
 
@@ -19,18 +21,38 @@
                 .setReturnNodes(NodeFilter.newBuilder().setMaxTraversalSuccessors(0).build());
     }
 
-    @Test
-    public void forwardFromSnp() {
-        TraversalRequest request = getLeavesRequestBuilder(fakeSWHID("snp", 20)).build();
-
+    private void _checkForwardFromSnp(int limit, ArrayList<SWHID> actualLeaves) {
         ArrayList<SWHID> expectedLeaves = new ArrayList<>();
         expectedLeaves.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000001"));
         expectedLeaves.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000004"));
         expectedLeaves.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000005"));
         expectedLeaves.add(new SWHID("swh:1:cnt:0000000000000000000000000000000000000007"));
 
+        if (limit == 0) {
+            GraphTest.assertEqualsAnyOrder(expectedLeaves, actualLeaves);
+        } else {
+            GraphTest.assertContainsAll(expectedLeaves, actualLeaves);
+            GraphTest.assertLength(Math.max(0, Math.min(limit, 4)), actualLeaves);
+        }
+    }
+
+    @Test
+    public void forwardFromSnp() {
+        TraversalRequest request = getLeavesRequestBuilder(fakeSWHID("snp", 20)).build();
+
         ArrayList<SWHID> actualLeaves = getSWHIDs(client.traverse(request));
-        GraphTest.assertEqualsAnyOrder(expectedLeaves, actualLeaves);
+
+        _checkForwardFromSnp(0, actualLeaves);
+    }
+
+    @ParameterizedTest
+    @ValueSource(ints = {0, 1, 2, 3, 4, 5, Integer.MAX_VALUE})
+    public void forwardFromSnpWithLimit(int limit) {
+        TraversalRequest request = getLeavesRequestBuilder(fakeSWHID("snp", 20)).setMaxMatchingNodes(limit).build();
+
+        ArrayList<SWHID> actualLeaves = getSWHIDs(client.traverse(request));
+
+        _checkForwardFromSnp(limit, actualLeaves);
     }
 
     @Test
@@ -97,4 +119,15 @@
         expectedLeaves.add(new SWHID("swh:1:dir:0000000000000000000000000000000000000012"));
         GraphTest.assertEqualsAnyOrder(expectedLeaves, actualLeaves);
     }
+
+    @ParameterizedTest
+    @ValueSource(ints = {0, 1, 2, Integer.MAX_VALUE})
+    public void backwardCntToDirDirToDirWithLimit(int limit) {
+        TraversalRequest request = getLeavesRequestBuilder(fakeSWHID("cnt", 5)).setEdges("cnt:dir,dir:dir")
+                .setDirection(GraphDirection.BACKWARD).setMaxMatchingNodes(limit).build();
+        ArrayList<SWHID> actualLeaves = getSWHIDs(client.traverse(request));
+        ArrayList<SWHID> expectedLeaves = new ArrayList<>();
+        expectedLeaves.add(new SWHID("swh:1:dir:0000000000000000000000000000000000000012"));
+        GraphTest.assertEqualsAnyOrder(expectedLeaves, actualLeaves);
+    }
 }
diff --git a/proto/swhgraph.proto b/proto/swhgraph.proto
--- a/proto/swhgraph.proto
+++ b/proto/swhgraph.proto
@@ -106,6 +106,9 @@
     /* FieldMask of which fields are to be returned (e.g., "swhid,cnt.length").
      * By default, all fields are returned. */
     optional google.protobuf.FieldMask mask = 8;
+    /* Maximum number of matching results before stopping. For Traverse(), this is
+     * the total number of results. Defaults to infinite. */
+    optional int64 max_matching_nodes = 9;
 }
 
 /* FindPathToRequest describes a request to find a shortest path between a
diff --git a/swh/graph/rpc/swhgraph_pb2.py b/swh/graph/rpc/swhgraph_pb2.py
--- a/swh/graph/rpc/swhgraph_pb2.py
+++ b/swh/graph/rpc/swhgraph_pb2.py
@@ -16,7 +16,7 @@
 from google.protobuf import field_mask_pb2 as google_dot_protobuf_dot_field__mask__pb2
 
 
-DESCRIPTOR = _descriptor_pool.Default().AddSerializedFile(b'\n\x1cswh/graph/rpc/swhgraph.proto\x12\tswh.graph\x1a google/protobuf/field_mask.proto\"W\n\x0eGetNodeRequest\x12\r\n\x05swhid\x18\x01 \x01(\t\x12-\n\x04mask\x18\x08 \x01(\x0b\x32\x1a.google.protobuf.FieldMaskH\x00\x88\x01\x01\x42\x07\n\x05_mask\"\xd8\x02\n\x10TraversalRequest\x12\x0b\n\x03src\x18\x01 \x03(\t\x12,\n\tdirection\x18\x02 \x01(\x0e\x32\x19.swh.graph.GraphDirection\x12\x12\n\x05\x65\x64ges\x18\x03 \x01(\tH\x00\x88\x01\x01\x12\x16\n\tmax_edges\x18\x04 \x01(\x03H\x01\x88\x01\x01\x12\x16\n\tmin_depth\x18\x05 \x01(\x03H\x02\x88\x01\x01\x12\x16\n\tmax_depth\x18\x06 \x01(\x03H\x03\x88\x01\x01\x12\x30\n\x0creturn_nodes\x18\x07 \x01(\x0b\x32\x15.swh.graph.NodeFilterH\x04\x88\x01\x01\x12-\n\x04mask\x18\x08 \x01(\x0b\x32\x1a.google.protobuf.FieldMaskH\x05\x88\x01\x01\x42\x08\n\x06_edgesB\x0c\n\n_max_edgesB\x0c\n\n_min_depthB\x0c\n\n_max_depthB\x0f\n\r_return_nodesB\x07\n\x05_mask\"\x97\x02\n\x11\x46indPathToRequest\x12\x0b\n\x03src\x18\x01 \x03(\t\x12%\n\x06target\x18\x02 \x01(\x0b\x32\x15.swh.graph.NodeFilter\x12,\n\tdirection\x18\x03 \x01(\x0e\x32\x19.swh.graph.GraphDirection\x12\x12\n\x05\x65\x64ges\x18\x04 \x01(\tH\x00\x88\x01\x01\x12\x16\n\tmax_edges\x18\x05 \x01(\x03H\x01\x88\x01\x01\x12\x16\n\tmax_depth\x18\x06 \x01(\x03H\x02\x88\x01\x01\x12-\n\x04mask\x18\x07 \x01(\x0b\x32\x1a.google.protobuf.FieldMaskH\x03\x88\x01\x01\x42\x08\n\x06_edgesB\x0c\n\n_max_edgesB\x0c\n\n_max_depthB\x07\n\x05_mask\"\x81\x03\n\x16\x46indPathBetweenRequest\x12\x0b\n\x03src\x18\x01 \x03(\t\x12\x0b\n\x03\x64st\x18\x02 \x03(\t\x12,\n\tdirection\x18\x03 \x01(\x0e\x32\x19.swh.graph.GraphDirection\x12\x39\n\x11\x64irection_reverse\x18\x04 \x01(\x0e\x32\x19.swh.graph.GraphDirectionH\x00\x88\x01\x01\x12\x12\n\x05\x65\x64ges\x18\x05 \x01(\tH\x01\x88\x01\x01\x12\x1a\n\redges_reverse\x18\x06 \x01(\tH\x02\x88\x01\x01\x12\x16\n\tmax_edges\x18\x07 \x01(\x03H\x03\x88\x01\x01\x12\x16\n\tmax_depth\x18\x08 \x01(\x03H\x04\x88\x01\x01\x12-\n\x04mask\x18\t \x01(\x0b\x32\x1a.google.protobuf.FieldMaskH\x05\x88\x01\x01\x42\x14\n\x12_direction_reverseB\x08\n\x06_edgesB\x10\n\x0e_edges_reverseB\x0c\n\n_max_edgesB\x0c\n\n_max_depthB\x07\n\x05_mask\"\xb2\x01\n\nNodeFilter\x12\x12\n\x05types\x18\x01 \x01(\tH\x00\x88\x01\x01\x12%\n\x18min_traversal_successors\x18\x02 \x01(\x03H\x01\x88\x01\x01\x12%\n\x18max_traversal_successors\x18\x03 \x01(\x03H\x02\x88\x01\x01\x42\x08\n\x06_typesB\x1b\n\x19_min_traversal_successorsB\x1b\n\x19_max_traversal_successors\"\x92\x02\n\x04Node\x12\r\n\x05swhid\x18\x01 \x01(\t\x12\'\n\tsuccessor\x18\x02 \x03(\x0b\x32\x14.swh.graph.Successor\x12\x1b\n\x0enum_successors\x18\t \x01(\x03H\x01\x88\x01\x01\x12%\n\x03\x63nt\x18\x03 \x01(\x0b\x32\x16.swh.graph.ContentDataH\x00\x12&\n\x03rev\x18\x05 \x01(\x0b\x32\x17.swh.graph.RevisionDataH\x00\x12%\n\x03rel\x18\x06 \x01(\x0b\x32\x16.swh.graph.ReleaseDataH\x00\x12$\n\x03ori\x18\x08 \x01(\x0b\x32\x15.swh.graph.OriginDataH\x00\x42\x06\n\x04\x64\x61taB\x11\n\x0f_num_successors\"U\n\x04Path\x12\x1d\n\x04node\x18\x01 \x03(\x0b\x32\x0f.swh.graph.Node\x12\x1b\n\x0emidpoint_index\x18\x02 \x01(\x05H\x00\x88\x01\x01\x42\x11\n\x0f_midpoint_index\"N\n\tSuccessor\x12\x12\n\x05swhid\x18\x01 \x01(\tH\x00\x88\x01\x01\x12#\n\x05label\x18\x02 \x03(\x0b\x32\x14.swh.graph.EdgeLabelB\x08\n\x06_swhid\"U\n\x0b\x43ontentData\x12\x13\n\x06length\x18\x01 \x01(\x03H\x00\x88\x01\x01\x12\x17\n\nis_skipped\x18\x02 \x01(\x08H\x01\x88\x01\x01\x42\t\n\x07_lengthB\r\n\x0b_is_skipped\"\xc6\x02\n\x0cRevisionData\x12\x13\n\x06\x61uthor\x18\x01 \x01(\x03H\x00\x88\x01\x01\x12\x18\n\x0b\x61uthor_date\x18\x02 \x01(\x03H\x01\x88\x01\x01\x12\x1f\n\x12\x61uthor_date_offset\x18\x03 \x01(\x05H\x02\x88\x01\x01\x12\x16\n\tcommitter\x18\x04 \x01(\x03H\x03\x88\x01\x01\x12\x1b\n\x0e\x63ommitter_date\x18\x05 \x01(\x03H\x04\x88\x01\x01\x12\"\n\x15\x63ommitter_date_offset\x18\x06 \x01(\x05H\x05\x88\x01\x01\x12\x14\n\x07message\x18\x07 \x01(\x0cH\x06\x88\x01\x01\x42\t\n\x07_authorB\x0e\n\x0c_author_dateB\x15\n\x13_author_date_offsetB\x0c\n\n_committerB\x11\n\x0f_committer_dateB\x18\n\x16_committer_date_offsetB\n\n\x08_message\"\xcd\x01\n\x0bReleaseData\x12\x13\n\x06\x61uthor\x18\x01 \x01(\x03H\x00\x88\x01\x01\x12\x18\n\x0b\x61uthor_date\x18\x02 \x01(\x03H\x01\x88\x01\x01\x12\x1f\n\x12\x61uthor_date_offset\x18\x03 \x01(\x05H\x02\x88\x01\x01\x12\x11\n\x04name\x18\x04 \x01(\x0cH\x03\x88\x01\x01\x12\x14\n\x07message\x18\x05 \x01(\x0cH\x04\x88\x01\x01\x42\t\n\x07_authorB\x0e\n\x0c_author_dateB\x15\n\x13_author_date_offsetB\x07\n\x05_nameB\n\n\x08_message\"&\n\nOriginData\x12\x10\n\x03url\x18\x01 \x01(\tH\x00\x88\x01\x01\x42\x06\n\x04_url\"-\n\tEdgeLabel\x12\x0c\n\x04name\x18\x01 \x01(\x0c\x12\x12\n\npermission\x18\x02 \x01(\x05\"\x1e\n\rCountResponse\x12\r\n\x05\x63ount\x18\x01 \x01(\x03\"\x0e\n\x0cStatsRequest\"\x9b\x02\n\rStatsResponse\x12\x11\n\tnum_nodes\x18\x01 \x01(\x03\x12\x11\n\tnum_edges\x18\x02 \x01(\x03\x12\x19\n\x11\x63ompression_ratio\x18\x03 \x01(\x01\x12\x15\n\rbits_per_node\x18\x04 \x01(\x01\x12\x15\n\rbits_per_edge\x18\x05 \x01(\x01\x12\x14\n\x0c\x61vg_locality\x18\x06 \x01(\x01\x12\x14\n\x0cindegree_min\x18\x07 \x01(\x03\x12\x14\n\x0cindegree_max\x18\x08 \x01(\x03\x12\x14\n\x0cindegree_avg\x18\t \x01(\x01\x12\x15\n\routdegree_min\x18\n \x01(\x03\x12\x15\n\routdegree_max\x18\x0b \x01(\x03\x12\x15\n\routdegree_avg\x18\x0c \x01(\x01*+\n\x0eGraphDirection\x12\x0b\n\x07\x46ORWARD\x10\x00\x12\x0c\n\x08\x42\x41\x43KWARD\x10\x01\x32\xcf\x03\n\x10TraversalService\x12\x35\n\x07GetNode\x12\x19.swh.graph.GetNodeRequest\x1a\x0f.swh.graph.Node\x12:\n\x08Traverse\x12\x1b.swh.graph.TraversalRequest\x1a\x0f.swh.graph.Node0\x01\x12;\n\nFindPathTo\x12\x1c.swh.graph.FindPathToRequest\x1a\x0f.swh.graph.Path\x12\x45\n\x0f\x46indPathBetween\x12!.swh.graph.FindPathBetweenRequest\x1a\x0f.swh.graph.Path\x12\x43\n\nCountNodes\x12\x1b.swh.graph.TraversalRequest\x1a\x18.swh.graph.CountResponse\x12\x43\n\nCountEdges\x12\x1b.swh.graph.TraversalRequest\x1a\x18.swh.graph.CountResponse\x12:\n\x05Stats\x12\x17.swh.graph.StatsRequest\x1a\x18.swh.graph.StatsResponseB0\n\x1eorg.softwareheritage.graph.rpcB\x0cGraphServiceP\x01\x62\x06proto3')
+DESCRIPTOR = _descriptor_pool.Default().AddSerializedFile(b'\n\x1cswh/graph/rpc/swhgraph.proto\x12\tswh.graph\x1a google/protobuf/field_mask.proto\"W\n\x0eGetNodeRequest\x12\r\n\x05swhid\x18\x01 \x01(\t\x12-\n\x04mask\x18\x08 \x01(\x0b\x32\x1a.google.protobuf.FieldMaskH\x00\x88\x01\x01\x42\x07\n\x05_mask\"\x90\x03\n\x10TraversalRequest\x12\x0b\n\x03src\x18\x01 \x03(\t\x12,\n\tdirection\x18\x02 \x01(\x0e\x32\x19.swh.graph.GraphDirection\x12\x12\n\x05\x65\x64ges\x18\x03 \x01(\tH\x00\x88\x01\x01\x12\x16\n\tmax_edges\x18\x04 \x01(\x03H\x01\x88\x01\x01\x12\x16\n\tmin_depth\x18\x05 \x01(\x03H\x02\x88\x01\x01\x12\x16\n\tmax_depth\x18\x06 \x01(\x03H\x03\x88\x01\x01\x12\x30\n\x0creturn_nodes\x18\x07 \x01(\x0b\x32\x15.swh.graph.NodeFilterH\x04\x88\x01\x01\x12-\n\x04mask\x18\x08 \x01(\x0b\x32\x1a.google.protobuf.FieldMaskH\x05\x88\x01\x01\x12\x1f\n\x12max_matching_nodes\x18\t \x01(\x03H\x06\x88\x01\x01\x42\x08\n\x06_edgesB\x0c\n\n_max_edgesB\x0c\n\n_min_depthB\x0c\n\n_max_depthB\x0f\n\r_return_nodesB\x07\n\x05_maskB\x15\n\x13_max_matching_nodes\"\x97\x02\n\x11\x46indPathToRequest\x12\x0b\n\x03src\x18\x01 \x03(\t\x12%\n\x06target\x18\x02 \x01(\x0b\x32\x15.swh.graph.NodeFilter\x12,\n\tdirection\x18\x03 \x01(\x0e\x32\x19.swh.graph.GraphDirection\x12\x12\n\x05\x65\x64ges\x18\x04 \x01(\tH\x00\x88\x01\x01\x12\x16\n\tmax_edges\x18\x05 \x01(\x03H\x01\x88\x01\x01\x12\x16\n\tmax_depth\x18\x06 \x01(\x03H\x02\x88\x01\x01\x12-\n\x04mask\x18\x07 \x01(\x0b\x32\x1a.google.protobuf.FieldMaskH\x03\x88\x01\x01\x42\x08\n\x06_edgesB\x0c\n\n_max_edgesB\x0c\n\n_max_depthB\x07\n\x05_mask\"\x81\x03\n\x16\x46indPathBetweenRequest\x12\x0b\n\x03src\x18\x01 \x03(\t\x12\x0b\n\x03\x64st\x18\x02 \x03(\t\x12,\n\tdirection\x18\x03 \x01(\x0e\x32\x19.swh.graph.GraphDirection\x12\x39\n\x11\x64irection_reverse\x18\x04 \x01(\x0e\x32\x19.swh.graph.GraphDirectionH\x00\x88\x01\x01\x12\x12\n\x05\x65\x64ges\x18\x05 \x01(\tH\x01\x88\x01\x01\x12\x1a\n\redges_reverse\x18\x06 \x01(\tH\x02\x88\x01\x01\x12\x16\n\tmax_edges\x18\x07 \x01(\x03H\x03\x88\x01\x01\x12\x16\n\tmax_depth\x18\x08 \x01(\x03H\x04\x88\x01\x01\x12-\n\x04mask\x18\t \x01(\x0b\x32\x1a.google.protobuf.FieldMaskH\x05\x88\x01\x01\x42\x14\n\x12_direction_reverseB\x08\n\x06_edgesB\x10\n\x0e_edges_reverseB\x0c\n\n_max_edgesB\x0c\n\n_max_depthB\x07\n\x05_mask\"\xb2\x01\n\nNodeFilter\x12\x12\n\x05types\x18\x01 \x01(\tH\x00\x88\x01\x01\x12%\n\x18min_traversal_successors\x18\x02 \x01(\x03H\x01\x88\x01\x01\x12%\n\x18max_traversal_successors\x18\x03 \x01(\x03H\x02\x88\x01\x01\x42\x08\n\x06_typesB\x1b\n\x19_min_traversal_successorsB\x1b\n\x19_max_traversal_successors\"\x92\x02\n\x04Node\x12\r\n\x05swhid\x18\x01 \x01(\t\x12\'\n\tsuccessor\x18\x02 \x03(\x0b\x32\x14.swh.graph.Successor\x12\x1b\n\x0enum_successors\x18\t \x01(\x03H\x01\x88\x01\x01\x12%\n\x03\x63nt\x18\x03 \x01(\x0b\x32\x16.swh.graph.ContentDataH\x00\x12&\n\x03rev\x18\x05 \x01(\x0b\x32\x17.swh.graph.RevisionDataH\x00\x12%\n\x03rel\x18\x06 \x01(\x0b\x32\x16.swh.graph.ReleaseDataH\x00\x12$\n\x03ori\x18\x08 \x01(\x0b\x32\x15.swh.graph.OriginDataH\x00\x42\x06\n\x04\x64\x61taB\x11\n\x0f_num_successors\"U\n\x04Path\x12\x1d\n\x04node\x18\x01 \x03(\x0b\x32\x0f.swh.graph.Node\x12\x1b\n\x0emidpoint_index\x18\x02 \x01(\x05H\x00\x88\x01\x01\x42\x11\n\x0f_midpoint_index\"N\n\tSuccessor\x12\x12\n\x05swhid\x18\x01 \x01(\tH\x00\x88\x01\x01\x12#\n\x05label\x18\x02 \x03(\x0b\x32\x14.swh.graph.EdgeLabelB\x08\n\x06_swhid\"U\n\x0b\x43ontentData\x12\x13\n\x06length\x18\x01 \x01(\x03H\x00\x88\x01\x01\x12\x17\n\nis_skipped\x18\x02 \x01(\x08H\x01\x88\x01\x01\x42\t\n\x07_lengthB\r\n\x0b_is_skipped\"\xc6\x02\n\x0cRevisionData\x12\x13\n\x06\x61uthor\x18\x01 \x01(\x03H\x00\x88\x01\x01\x12\x18\n\x0b\x61uthor_date\x18\x02 \x01(\x03H\x01\x88\x01\x01\x12\x1f\n\x12\x61uthor_date_offset\x18\x03 \x01(\x05H\x02\x88\x01\x01\x12\x16\n\tcommitter\x18\x04 \x01(\x03H\x03\x88\x01\x01\x12\x1b\n\x0e\x63ommitter_date\x18\x05 \x01(\x03H\x04\x88\x01\x01\x12\"\n\x15\x63ommitter_date_offset\x18\x06 \x01(\x05H\x05\x88\x01\x01\x12\x14\n\x07message\x18\x07 \x01(\x0cH\x06\x88\x01\x01\x42\t\n\x07_authorB\x0e\n\x0c_author_dateB\x15\n\x13_author_date_offsetB\x0c\n\n_committerB\x11\n\x0f_committer_dateB\x18\n\x16_committer_date_offsetB\n\n\x08_message\"\xcd\x01\n\x0bReleaseData\x12\x13\n\x06\x61uthor\x18\x01 \x01(\x03H\x00\x88\x01\x01\x12\x18\n\x0b\x61uthor_date\x18\x02 \x01(\x03H\x01\x88\x01\x01\x12\x1f\n\x12\x61uthor_date_offset\x18\x03 \x01(\x05H\x02\x88\x01\x01\x12\x11\n\x04name\x18\x04 \x01(\x0cH\x03\x88\x01\x01\x12\x14\n\x07message\x18\x05 \x01(\x0cH\x04\x88\x01\x01\x42\t\n\x07_authorB\x0e\n\x0c_author_dateB\x15\n\x13_author_date_offsetB\x07\n\x05_nameB\n\n\x08_message\"&\n\nOriginData\x12\x10\n\x03url\x18\x01 \x01(\tH\x00\x88\x01\x01\x42\x06\n\x04_url\"-\n\tEdgeLabel\x12\x0c\n\x04name\x18\x01 \x01(\x0c\x12\x12\n\npermission\x18\x02 \x01(\x05\"\x1e\n\rCountResponse\x12\r\n\x05\x63ount\x18\x01 \x01(\x03\"\x0e\n\x0cStatsRequest\"\x9b\x02\n\rStatsResponse\x12\x11\n\tnum_nodes\x18\x01 \x01(\x03\x12\x11\n\tnum_edges\x18\x02 \x01(\x03\x12\x19\n\x11\x63ompression_ratio\x18\x03 \x01(\x01\x12\x15\n\rbits_per_node\x18\x04 \x01(\x01\x12\x15\n\rbits_per_edge\x18\x05 \x01(\x01\x12\x14\n\x0c\x61vg_locality\x18\x06 \x01(\x01\x12\x14\n\x0cindegree_min\x18\x07 \x01(\x03\x12\x14\n\x0cindegree_max\x18\x08 \x01(\x03\x12\x14\n\x0cindegree_avg\x18\t \x01(\x01\x12\x15\n\routdegree_min\x18\n \x01(\x03\x12\x15\n\routdegree_max\x18\x0b \x01(\x03\x12\x15\n\routdegree_avg\x18\x0c \x01(\x01*+\n\x0eGraphDirection\x12\x0b\n\x07\x46ORWARD\x10\x00\x12\x0c\n\x08\x42\x41\x43KWARD\x10\x01\x32\xcf\x03\n\x10TraversalService\x12\x35\n\x07GetNode\x12\x19.swh.graph.GetNodeRequest\x1a\x0f.swh.graph.Node\x12:\n\x08Traverse\x12\x1b.swh.graph.TraversalRequest\x1a\x0f.swh.graph.Node0\x01\x12;\n\nFindPathTo\x12\x1c.swh.graph.FindPathToRequest\x1a\x0f.swh.graph.Path\x12\x45\n\x0f\x46indPathBetween\x12!.swh.graph.FindPathBetweenRequest\x1a\x0f.swh.graph.Path\x12\x43\n\nCountNodes\x12\x1b.swh.graph.TraversalRequest\x1a\x18.swh.graph.CountResponse\x12\x43\n\nCountEdges\x12\x1b.swh.graph.TraversalRequest\x1a\x18.swh.graph.CountResponse\x12:\n\x05Stats\x12\x17.swh.graph.StatsRequest\x1a\x18.swh.graph.StatsResponseB0\n\x1eorg.softwareheritage.graph.rpcB\x0cGraphServiceP\x01\x62\x06proto3')
 
 _GRAPHDIRECTION = DESCRIPTOR.enum_types_by_name['GraphDirection']
 GraphDirection = enum_type_wrapper.EnumTypeWrapper(_GRAPHDIRECTION)
@@ -157,40 +157,40 @@
 
   DESCRIPTOR._options = None
   DESCRIPTOR._serialized_options = b'\n\036org.softwareheritage.graph.rpcB\014GraphServiceP\001'
-  _GRAPHDIRECTION._serialized_start=2853
-  _GRAPHDIRECTION._serialized_end=2896
+  _GRAPHDIRECTION._serialized_start=2909
+  _GRAPHDIRECTION._serialized_end=2952
   _GETNODEREQUEST._serialized_start=77
   _GETNODEREQUEST._serialized_end=164
   _TRAVERSALREQUEST._serialized_start=167
-  _TRAVERSALREQUEST._serialized_end=511
-  _FINDPATHTOREQUEST._serialized_start=514
-  _FINDPATHTOREQUEST._serialized_end=793
-  _FINDPATHBETWEENREQUEST._serialized_start=796
-  _FINDPATHBETWEENREQUEST._serialized_end=1181
-  _NODEFILTER._serialized_start=1184
-  _NODEFILTER._serialized_end=1362
-  _NODE._serialized_start=1365
-  _NODE._serialized_end=1639
-  _PATH._serialized_start=1641
-  _PATH._serialized_end=1726
-  _SUCCESSOR._serialized_start=1728
-  _SUCCESSOR._serialized_end=1806
-  _CONTENTDATA._serialized_start=1808
-  _CONTENTDATA._serialized_end=1893
-  _REVISIONDATA._serialized_start=1896
-  _REVISIONDATA._serialized_end=2222
-  _RELEASEDATA._serialized_start=2225
-  _RELEASEDATA._serialized_end=2430
-  _ORIGINDATA._serialized_start=2432
-  _ORIGINDATA._serialized_end=2470
-  _EDGELABEL._serialized_start=2472
-  _EDGELABEL._serialized_end=2517
-  _COUNTRESPONSE._serialized_start=2519
-  _COUNTRESPONSE._serialized_end=2549
-  _STATSREQUEST._serialized_start=2551
-  _STATSREQUEST._serialized_end=2565
-  _STATSRESPONSE._serialized_start=2568
-  _STATSRESPONSE._serialized_end=2851
-  _TRAVERSALSERVICE._serialized_start=2899
-  _TRAVERSALSERVICE._serialized_end=3362
+  _TRAVERSALREQUEST._serialized_end=567
+  _FINDPATHTOREQUEST._serialized_start=570
+  _FINDPATHTOREQUEST._serialized_end=849
+  _FINDPATHBETWEENREQUEST._serialized_start=852
+  _FINDPATHBETWEENREQUEST._serialized_end=1237
+  _NODEFILTER._serialized_start=1240
+  _NODEFILTER._serialized_end=1418
+  _NODE._serialized_start=1421
+  _NODE._serialized_end=1695
+  _PATH._serialized_start=1697
+  _PATH._serialized_end=1782
+  _SUCCESSOR._serialized_start=1784
+  _SUCCESSOR._serialized_end=1862
+  _CONTENTDATA._serialized_start=1864
+  _CONTENTDATA._serialized_end=1949
+  _REVISIONDATA._serialized_start=1952
+  _REVISIONDATA._serialized_end=2278
+  _RELEASEDATA._serialized_start=2281
+  _RELEASEDATA._serialized_end=2486
+  _ORIGINDATA._serialized_start=2488
+  _ORIGINDATA._serialized_end=2526
+  _EDGELABEL._serialized_start=2528
+  _EDGELABEL._serialized_end=2573
+  _COUNTRESPONSE._serialized_start=2575
+  _COUNTRESPONSE._serialized_end=2605
+  _STATSREQUEST._serialized_start=2607
+  _STATSREQUEST._serialized_end=2621
+  _STATSRESPONSE._serialized_start=2624
+  _STATSRESPONSE._serialized_end=2907
+  _TRAVERSALSERVICE._serialized_start=2955
+  _TRAVERSALSERVICE._serialized_end=3418
 # @@protoc_insertion_point(module_scope)
diff --git a/swh/graph/rpc/swhgraph_pb2.pyi b/swh/graph/rpc/swhgraph_pb2.pyi
--- a/swh/graph/rpc/swhgraph_pb2.pyi
+++ b/swh/graph/rpc/swhgraph_pb2.pyi
@@ -74,6 +74,7 @@
     MAX_DEPTH_FIELD_NUMBER: builtins.int
     RETURN_NODES_FIELD_NUMBER: builtins.int
     MASK_FIELD_NUMBER: builtins.int
+    MAX_MATCHING_NODES_FIELD_NUMBER: builtins.int
     @property
     def src(self) -> google.protobuf.internal.containers.RepeatedScalarFieldContainer[typing.Text]:
         """Set of source nodes (SWHIDs)"""
@@ -113,6 +114,11 @@
         By default, all fields are returned.
         """
         pass
+    max_matching_nodes: builtins.int
+    """Maximum number of matching results before stopping. For Traverse(), this is
+    the total number of results. Defaults to infinite.
+    """
+
     def __init__(self,
         *,
         src: typing.Optional[typing.Iterable[typing.Text]] = ...,
@@ -123,9 +129,10 @@
         max_depth: typing.Optional[builtins.int] = ...,
         return_nodes: typing.Optional[global___NodeFilter] = ...,
         mask: typing.Optional[google.protobuf.field_mask_pb2.FieldMask] = ...,
+        max_matching_nodes: typing.Optional[builtins.int] = ...,
         ) -> None: ...
-    def HasField(self, field_name: typing_extensions.Literal["_edges",b"_edges","_mask",b"_mask","_max_depth",b"_max_depth","_max_edges",b"_max_edges","_min_depth",b"_min_depth","_return_nodes",b"_return_nodes","edges",b"edges","mask",b"mask","max_depth",b"max_depth","max_edges",b"max_edges","min_depth",b"min_depth","return_nodes",b"return_nodes"]) -> builtins.bool: ...
-    def ClearField(self, field_name: typing_extensions.Literal["_edges",b"_edges","_mask",b"_mask","_max_depth",b"_max_depth","_max_edges",b"_max_edges","_min_depth",b"_min_depth","_return_nodes",b"_return_nodes","direction",b"direction","edges",b"edges","mask",b"mask","max_depth",b"max_depth","max_edges",b"max_edges","min_depth",b"min_depth","return_nodes",b"return_nodes","src",b"src"]) -> None: ...
+    def HasField(self, field_name: typing_extensions.Literal["_edges",b"_edges","_mask",b"_mask","_max_depth",b"_max_depth","_max_edges",b"_max_edges","_max_matching_nodes",b"_max_matching_nodes","_min_depth",b"_min_depth","_return_nodes",b"_return_nodes","edges",b"edges","mask",b"mask","max_depth",b"max_depth","max_edges",b"max_edges","max_matching_nodes",b"max_matching_nodes","min_depth",b"min_depth","return_nodes",b"return_nodes"]) -> builtins.bool: ...
+    def ClearField(self, field_name: typing_extensions.Literal["_edges",b"_edges","_mask",b"_mask","_max_depth",b"_max_depth","_max_edges",b"_max_edges","_max_matching_nodes",b"_max_matching_nodes","_min_depth",b"_min_depth","_return_nodes",b"_return_nodes","direction",b"direction","edges",b"edges","mask",b"mask","max_depth",b"max_depth","max_edges",b"max_edges","max_matching_nodes",b"max_matching_nodes","min_depth",b"min_depth","return_nodes",b"return_nodes","src",b"src"]) -> None: ...
     @typing.overload
     def WhichOneof(self, oneof_group: typing_extensions.Literal["_edges",b"_edges"]) -> typing.Optional[typing_extensions.Literal["edges"]]: ...
     @typing.overload
@@ -135,6 +142,8 @@
     @typing.overload
     def WhichOneof(self, oneof_group: typing_extensions.Literal["_max_edges",b"_max_edges"]) -> typing.Optional[typing_extensions.Literal["max_edges"]]: ...
     @typing.overload
+    def WhichOneof(self, oneof_group: typing_extensions.Literal["_max_matching_nodes",b"_max_matching_nodes"]) -> typing.Optional[typing_extensions.Literal["max_matching_nodes"]]: ...
+    @typing.overload
     def WhichOneof(self, oneof_group: typing_extensions.Literal["_min_depth",b"_min_depth"]) -> typing.Optional[typing_extensions.Literal["min_depth"]]: ...
     @typing.overload
     def WhichOneof(self, oneof_group: typing_extensions.Literal["_return_nodes",b"_return_nodes"]) -> typing.Optional[typing_extensions.Literal["return_nodes"]]: ...