diff --git a/gitiles-servlet/src/main/java/com/google/gitiles/RevisionParser.java b/gitiles-servlet/src/main/java/com/google/gitiles/RevisionParser.java
index 2d27e2c..743b909 100644
--- a/gitiles-servlet/src/main/java/com/google/gitiles/RevisionParser.java
+++ b/gitiles-servlet/src/main/java/com/google/gitiles/RevisionParser.java
@@ -217,11 +217,12 @@
       // Name contains a visible ref; skip expensive reachability check.
       return true;
     }
-    if (!cache.isVisible(repo, walk, access, result.getRevision().getId())) {
+    ObjectId id = result.getRevision().getId();
+    if (!cache.isVisible(repo, walk, access, id)) {
       return false;
     }
     if (result.getOldRevision() != null && result.getOldRevision() != Revision.NULL) {
-      return cache.isVisible(repo, walk, access, result.getOldRevision().getId());
+      return cache.isVisible(repo, walk, access, result.getOldRevision().getId(), id);
     } else {
       return true;
     }
diff --git a/gitiles-servlet/src/main/java/com/google/gitiles/VisibilityCache.java b/gitiles-servlet/src/main/java/com/google/gitiles/VisibilityCache.java
index 449f415..c1b11f8 100644
--- a/gitiles-servlet/src/main/java/com/google/gitiles/VisibilityCache.java
+++ b/gitiles-servlet/src/main/java/com/google/gitiles/VisibilityCache.java
@@ -23,6 +23,7 @@
 import static org.eclipse.jgit.lib.Constants.R_TAGS;
 
 import java.io.IOException;
+import java.util.Arrays;
 import java.util.Collection;
 import java.util.concurrent.Callable;
 import java.util.concurrent.ExecutionException;
@@ -38,11 +39,13 @@
 import org.eclipse.jgit.revwalk.RevSort;
 import org.eclipse.jgit.revwalk.RevWalk;
 
+import com.google.common.base.Function;
 import com.google.common.base.Objects;
 import com.google.common.base.Predicate;
 import com.google.common.base.Throwables;
 import com.google.common.cache.Cache;
 import com.google.common.cache.CacheBuilder;
+import com.google.common.collect.Collections2;
 import com.google.common.util.concurrent.ExecutionError;
 
 /** Cache of per-user object visibility. */
@@ -107,14 +110,14 @@
   }
 
   boolean isVisible(final Repository repo, final RevWalk walk, GitilesAccess access,
-      final ObjectId id) throws IOException {
+      final ObjectId id, final ObjectId... knownReachable) throws IOException {
     try {
       return cache.get(
           new Key(access.getUserKey(), access.getRepositoryName(), id),
           new Callable<Boolean>() {
             @Override
             public Boolean call() throws IOException {
-              return isVisible(repo, walk, id);
+              return isVisible(repo, walk, id, Arrays.asList(knownReachable));
             }
           });
     } catch (ExecutionException e) {
@@ -131,7 +134,8 @@
     }
   }
 
-  private boolean isVisible(Repository repo, RevWalk walk, ObjectId id) throws IOException {
+  private boolean isVisible(Repository repo, RevWalk walk, ObjectId id,
+      Collection<ObjectId> knownReachable) throws IOException {
     RevCommit commit;
     try {
       commit = walk.parseCommit(id);
@@ -153,9 +157,10 @@
     // Check heads first under the assumption that most requests are for refs
     // close to a head. Tags tend to be much further back in history and just
     // clutter up the priority queue in the common case.
-    return isReachableFrom(walk, commit, filter(allRefs, refStartsWith(R_HEADS)))
-        || isReachableFrom(walk, commit, filter(allRefs, refStartsWith(R_TAGS)))
-        || isReachableFrom(walk, commit, filter(allRefs, otherRefs()));
+    return isReachableFrom(walk, commit, knownReachable)
+        || isReachableFromRefs(walk, commit, filter(allRefs, refStartsWith(R_HEADS)))
+        || isReachableFromRefs(walk, commit, filter(allRefs, refStartsWith(R_TAGS)))
+        || isReachableFromRefs(walk, commit, filter(allRefs, otherRefs()));
   }
 
   private static Predicate<Ref> refStartsWith(final String prefix) {
@@ -172,9 +177,24 @@
     return not(or(refStartsWith(R_HEADS), refStartsWith(R_TAGS), refStartsWith("refs/changes/")));
   }
 
-  private boolean isReachableFrom(RevWalk walk, RevCommit commit, Collection<Ref> refs)
+  private boolean isReachableFromRefs(RevWalk walk, RevCommit commit,
+      Collection<Ref> refs) throws IOException {
+    return isReachableFrom(walk, commit,
+        Collections2.transform(refs, new Function<Ref, ObjectId>() {
+          @Override
+          public ObjectId apply(Ref ref) {
+            if (ref.getPeeledObjectId() != null) {
+              return ref.getPeeledObjectId();
+            } else {
+              return ref.getObjectId();
+            }
+          }
+        }));
+  }
+
+  private boolean isReachableFrom(RevWalk walk, RevCommit commit, Collection<ObjectId> ids)
       throws IOException {
-    if (refs.isEmpty()) {
+    if (ids.isEmpty()) {
       return false;
     }
     walk.reset();
@@ -182,14 +202,10 @@
       walk.sort(RevSort.TOPO);
     }
     walk.markStart(commit);
-    for (Ref ref : refs) {
-      if (ref.getPeeledObjectId() != null) {
-        markUninteresting(walk, ref.getPeeledObjectId());
-      } else {
-        markUninteresting(walk, ref.getObjectId());
-      }
+    for (ObjectId id : ids) {
+      markUninteresting(walk, id);
     }
-    // If the commit is reachable from any branch head, it will appear to be
+    // If the commit is reachable from any given tip, it will appear to be
     // uninteresting to the RevWalk and no output will be produced.
     return walk.next() == null;
   }