diff --git a/java/com/google/gerrit/server/project/RefFilter.java b/java/com/google/gerrit/server/project/RefFilter.java
index cdabcbe..3f83f83 100644
--- a/java/com/google/gerrit/server/project/RefFilter.java
+++ b/java/com/google/gerrit/server/project/RefFilter.java
@@ -18,23 +18,25 @@
 
 import com.google.common.base.Strings;
 import com.google.common.collect.ImmutableList;
-import com.google.gerrit.extensions.api.projects.RefInfo;
 import com.google.gerrit.extensions.restapi.BadRequestException;
 import dk.brics.automaton.RegExp;
 import dk.brics.automaton.RunAutomaton;
 import java.util.List;
 import java.util.Locale;
+import java.util.function.Function;
 import java.util.stream.Stream;
 
-public class RefFilter<T extends RefInfo> {
+public class RefFilter<T> {
   private final String prefix;
+  private final Function<T, String> refNameExtractor;
   private String matchSubstring;
   private String matchRegex;
   private int start;
   private int limit;
 
-  public RefFilter(String prefix) {
+  public RefFilter(String prefix, Function<T, String> refNameExtractor) {
     this.prefix = prefix;
+    this.refNameExtractor = refNameExtractor;
   }
 
   public RefFilter<T> subString(String subString) {
@@ -78,9 +80,8 @@
     return results.collect(toImmutableList());
   }
 
-  private static <T extends RefInfo> boolean matchesSubstring(
-      String prefix, String lowercaseSubstring, T refInfo) {
-    String ref = refInfo.ref;
+  private boolean matchesSubstring(String prefix, String lowercaseSubstring, T refInfo) {
+    String ref = refNameExtractor.apply(refInfo);
     if (ref.startsWith(prefix)) {
       ref = ref.substring(prefix.length());
     }
@@ -102,9 +103,8 @@
     }
   }
 
-  private static <T extends RefInfo> boolean matchesRegex(
-      String prefix, RunAutomaton a, T refInfo) {
-    String ref = refInfo.ref;
+  private boolean matchesRegex(String prefix, RunAutomaton a, T refInfo) {
+    String ref = refNameExtractor.apply(refInfo);
     if (ref.startsWith(prefix)) {
       ref = ref.substring(prefix.length());
     }
diff --git a/java/com/google/gerrit/server/restapi/project/ListBranches.java b/java/com/google/gerrit/server/restapi/project/ListBranches.java
index 2c26933..c454aea 100644
--- a/java/com/google/gerrit/server/restapi/project/ListBranches.java
+++ b/java/com/google/gerrit/server/restapi/project/ListBranches.java
@@ -19,6 +19,7 @@
 import com.google.common.collect.ComparisonChain;
 import com.google.common.collect.ImmutableList;
 import com.google.common.collect.Sets;
+import com.google.gerrit.entities.Project;
 import com.google.gerrit.entities.RefNames;
 import com.google.gerrit.extensions.api.projects.BranchInfo;
 import com.google.gerrit.extensions.api.projects.ProjectApi.ListRefsRequest;
@@ -49,8 +50,10 @@
 import java.util.Collection;
 import java.util.Comparator;
 import java.util.List;
+import java.util.Optional;
 import java.util.Set;
 import java.util.TreeMap;
+import java.util.stream.Collectors;
 import org.eclipse.jgit.errors.RepositoryNotFoundException;
 import org.eclipse.jgit.lib.Constants;
 import org.eclipse.jgit.lib.Ref;
@@ -131,13 +134,20 @@
   public Response<ImmutableList<BranchInfo>> apply(ProjectResource rsrc)
       throws RestApiException, IOException, PermissionBackendException {
     rsrc.getProjectState().checkStatePermitsRead();
-    return Response.ok(
-        new RefFilter<BranchInfo>(Constants.R_HEADS)
+
+    // Filter on refs/heads/*, substring and regex without checking ref visibility
+    List<Ref> allBranches = readAllBranches(rsrc);
+    Set<String> targets = getTargets(allBranches);
+    ImmutableList<Ref> filtered =
+        new RefFilter<>(Constants.R_HEADS, (Ref r) -> r.getName())
             .subString(matchSubstring)
             .regex(matchRegex)
-            .start(start)
-            .limit(limit)
-            .filter(allBranches(rsrc)));
+            .filter(allBranches);
+
+    // Filter for visibility, taking 'start' and 'limit' parameters into account
+    return Response.ok(
+        filterForVisibility(rsrc, filtered, targets).stream()
+            .collect(ImmutableList.toImmutableList()));
   }
 
   BranchInfo toBranchInfo(BranchResource rsrc)
@@ -151,14 +161,20 @@
       if (r == null) {
         throw new ResourceNotFoundException();
       }
-      return toBranchInfo(rsrc, ImmutableList.of(r)).get(0);
+      return toBranchInfo(
+              r,
+              getTargets(ImmutableList.of(r)),
+              rsrc.getNameKey(),
+              rsrc.getProjectState(),
+              rsrc.getUser())
+          .get();
     } catch (RepositoryNotFoundException noRepo) {
       throw new ResourceNotFoundException(rsrc.getNameKey().get(), noRepo);
     }
   }
 
-  private List<BranchInfo> allBranches(ProjectResource rsrc)
-      throws IOException, ResourceNotFoundException, PermissionBackendException {
+  private List<Ref> readAllBranches(ProjectResource rsrc)
+      throws IOException, ResourceNotFoundException {
     List<Ref> refs;
     try (Repository db = repoManager.openRepository(rsrc.getNameKey())) {
       Collection<Ref> heads = db.getRefDatabase().getRefsByPrefix(Constants.R_HEADS);
@@ -168,89 +184,121 @@
           db.getRefDatabase()
               .exactRef(Constants.HEAD, RefNames.REFS_CONFIG, RefNames.REFS_USERS_DEFAULT)
               .values());
+      return refs;
     } catch (RepositoryNotFoundException noGitRepository) {
       throw new ResourceNotFoundException(rsrc.getNameKey().get(), noGitRepository);
     }
-    return toBranchInfo(rsrc, refs);
   }
 
-  private List<BranchInfo> toBranchInfo(ProjectResource rsrc, List<Ref> refs)
-      throws PermissionBackendException {
-    Set<String> targets = Sets.newHashSetWithExpectedSize(1);
+  /**
+   * Filter the input {@code refs} list w.r.t. current user's visibility of the ref. This also takes
+   * into account the {@link #start} and {@link #limit} parameters. We check refs iteratively while
+   * keeping track of matching (visible) refs. We only populate the output list if the matching ref
+   * ordinal is greater or equal {@link #start} and keep filling the output list until a {@link
+   * #limit} number of refs is gotten.
+   */
+  private List<BranchInfo> filterForVisibility(
+      ProjectResource rsrc, List<Ref> refs, Set<String> targets) throws PermissionBackendException {
+    refs = refs.stream().sorted(new RefComparator()).collect(Collectors.toUnmodifiableList());
+    List<BranchInfo> branches = new ArrayList<>();
+    int matchingRefs = 0;
     for (Ref ref : refs) {
-      if (ref.isSymbolic()) {
-        targets.add(ref.getTarget().getName());
+      Optional<BranchInfo> info =
+          toBranchInfo(ref, targets, rsrc.getNameKey(), rsrc.getProjectState(), rsrc.getUser());
+      if (info.isPresent()) {
+        matchingRefs += 1;
+        if (matchingRefs > start) {
+          branches.add(info.get());
+        }
+        if (limit > 0 && branches.size() == limit) {
+          // Break and return earlier if we've already found 'limit' refs. The processing of the
+          // remaining refs for visibility is not needed anymore.
+          break;
+        }
       }
     }
-
-    PermissionBackend.ForProject perm = permissionBackend.currentUser().project(rsrc.getNameKey());
-    List<BranchInfo> branches = new ArrayList<>(refs.size());
-    for (Ref ref : refs) {
-      if (ref.isSymbolic()) {
-        // A symbolic reference to another branch, instead of
-        // showing the resolved value, show the name it references.
-        //
-        String target = ref.getTarget().getName();
-
-        try {
-          perm.ref(target).check(RefPermission.READ);
-        } catch (AuthException e) {
-          continue;
-        }
-
-        if (target.startsWith(Constants.R_HEADS)) {
-          target = target.substring(Constants.R_HEADS.length());
-        }
-
-        BranchInfo b = new BranchInfo();
-        b.ref = ref.getName();
-        b.revision = target;
-        branches.add(b);
-
-        if (!Constants.HEAD.equals(ref.getName())) {
-          if (isConfigRef(ref.getName())) {
-            // Never allow to delete the meta config branch.
-            b.canDelete = null;
-          } else {
-            b.canDelete =
-                perm.ref(ref.getName()).testOrFalse(RefPermission.DELETE)
-                        && rsrc.getProjectState().statePermitsWrite()
-                    ? true
-                    : null;
-          }
-        }
-        continue;
-      }
-
-      try {
-        perm.ref(ref.getName()).check(RefPermission.READ);
-        branches.add(
-            createBranchInfo(
-                perm.ref(ref.getName()), ref, rsrc.getProjectState(), rsrc.getUser(), targets));
-      } catch (AuthException e) {
-        // Do nothing.
-      }
-    }
-    branches.sort(new BranchComparator());
     return branches;
   }
 
-  private static class BranchComparator implements Comparator<BranchInfo> {
+  /**
+   * Returns a {@link BranchInfo} if the branch is visible to the caller or {@link Optional#empty()}
+   * otherwise.
+   */
+  private Optional<BranchInfo> toBranchInfo(
+      Ref ref,
+      Set<String> targets,
+      Project.NameKey project,
+      ProjectState projectState,
+      CurrentUser currentUser)
+      throws PermissionBackendException {
+    PermissionBackend.ForProject perm = permissionBackend.currentUser().project(project);
+    if (ref.isSymbolic()) {
+      // A symbolic reference to another branch, instead of
+      // showing the resolved value, show the name it references.
+      //
+      String target = ref.getTarget().getName();
+
+      try {
+        perm.ref(target).check(RefPermission.READ);
+      } catch (AuthException e) {
+        return Optional.empty();
+      }
+
+      if (target.startsWith(Constants.R_HEADS)) {
+        target = target.substring(Constants.R_HEADS.length());
+      }
+
+      BranchInfo info = new BranchInfo();
+      info.ref = ref.getName();
+      info.revision = target;
+      if (!Constants.HEAD.equals(ref.getName())) {
+        if (isConfigRef(ref.getName())) {
+          // Never allow to delete the meta config branch.
+          info.canDelete = null;
+        } else {
+          info.canDelete =
+              perm.ref(ref.getName()).testOrFalse(RefPermission.DELETE)
+                      && projectState.statePermitsWrite()
+                  ? true
+                  : null;
+        }
+      }
+      return Optional.of(info);
+    }
+
+    try {
+      perm.ref(ref.getName()).check(RefPermission.READ);
+      BranchInfo branchInfo =
+          createBranchInfo(perm.ref(ref.getName()), ref, projectState, currentUser, targets);
+      return Optional.of(branchInfo);
+    } catch (AuthException e) {
+      // Do nothing.
+      return Optional.empty();
+    }
+  }
+
+  private static Set<String> getTargets(List<Ref> refs) {
+    Set<String> targets = Sets.newHashSetWithExpectedSize(1);
+    refs.stream().filter(Ref::isSymbolic).forEach(r -> targets.add(r.getTarget().getName()));
+    return targets;
+  }
+
+  private static class RefComparator implements Comparator<Ref> {
     @Override
-    public int compare(BranchInfo a, BranchInfo b) {
+    public int compare(Ref a, Ref b) {
       return ComparisonChain.start()
           .compareTrueFirst(isHead(a), isHead(b))
           .compareTrueFirst(isConfig(a), isConfig(b))
-          .compare(a.ref, b.ref)
+          .compare(a.getName(), b.getName())
           .result();
     }
 
-    private static boolean isHead(BranchInfo i) {
-      return Constants.HEAD.equals(i.ref);
+    private static boolean isHead(Ref r) {
+      return Constants.HEAD.equals(r.getName());
     }
 
-    private static boolean isConfig(BranchInfo i) {
-      return RefNames.REFS_CONFIG.equals(i.ref);
+    private static boolean isConfig(Ref r) {
+      return RefNames.REFS_CONFIG.equals(r.getName());
     }
   }
 
diff --git a/java/com/google/gerrit/server/restapi/project/ListTags.java b/java/com/google/gerrit/server/restapi/project/ListTags.java
index ac0dff9..31e4be5 100644
--- a/java/com/google/gerrit/server/restapi/project/ListTags.java
+++ b/java/com/google/gerrit/server/restapi/project/ListTags.java
@@ -139,7 +139,7 @@
     tags.sort(comparing(t -> t.ref));
 
     return Response.ok(
-        new RefFilter<TagInfo>(Constants.R_TAGS)
+        new RefFilter<>(Constants.R_TAGS, (TagInfo tag) -> tag.ref)
             .start(start)
             .limit(limit)
             .subString(matchSubstring)