Determining whether a change in an memoized algorithm will improve the performance
Intuitively I understand that the reason why the function became less efficient is because it avoids solving the right subproblem sometimes, which means that it also memoizes less cases, which in turn makes it perform more work.


This is impossible. Not solving and memoizing a subproblem can never make the algorithm slower. Either the subproblem will never be needed (in which case not memoizing it only saves work) or it will turn out to be necessary after all, in which case we would have to compute it. However, the worst case is only that we do not save any time: if we skip the computation now, we might have to do it in the future, but this is not more work than doing it now.

The optimization you've done will never cause more work to be done on computing subproblems. Thus, the only reason it could make the algorithm slower is if the optimization itself is expensive to compute. It seems likely either score or base_score are very slow methods, and your optimization causes them to be evaluated an additional time. You might be able to speed it up by storing base_score and score(left_solution) in a temporary variable.