In the context of distributed Branch and Bound Search for Graphical Models, effective load balancing is crucial yet hard to achieve due to early pruning of search branches. This paper proposes learning a regression model over structural as well as cost function-based features to more accurately predict subproblem complexity ahead of time, thereby enabling more balanced parallel workloads. Early results show the promise of this approach.