diff --git a/mercurial/branchmap.py b/mercurial/branchmap.py
--- a/mercurial/branchmap.py
+++ b/mercurial/branchmap.py
@@ -18,6 +18,7 @@
 from . import (
     encoding,
     error,
+    pycompat,
     scmutil,
     util,
 )
@@ -52,18 +53,19 @@
                               filteredhash=filteredhash)
         if not partial.validfor(repo):
             # invalidate the cache
-            raise ValueError('tip differs')
+            raise ValueError(r'tip differs')
         cl = repo.changelog
         for l in lines:
             if not l:
                 continue
             node, state, label = l.split(" ", 2)
             if state not in 'oc':
-                raise ValueError('invalid branch state')
+                raise ValueError(r'invalid branch state')
             label = encoding.tolocal(label.strip())
             node = bin(node)
             if not cl.hasnode(node):
-                raise ValueError('node %s does not exist' % hex(node))
+                raise ValueError(
+                    r'node %s does not exist' % pycompat.sysstr(hex(node)))
             partial.setdefault(label, []).append(node)
             if state == 'c':
                 partial._closednodes.add(node)
@@ -73,7 +75,7 @@
             if repo.filtername is not None:
                 msg += ' (%s)' % repo.filtername
             msg += ': %s\n'
-            repo.ui.debug(msg % inst)
+            repo.ui.debug(msg % pycompat.bytestr(inst))
         partial = None
     return partial