We describe a distributed version of an advanced branch and bound algorithm over graphical models. The crucial issue of load balancing is addressed by estimating subproblem complexity through learning, yielding impressive speedups on various hard problems using hundreds of parallel CPUs.