my @best_keys = sort { $HoH->{$a}{'score'} <=> $HoH->{$b}{'score'} } keys %{$HoH}

The $a and $b special variables are taken from keys %{$HoH}, so that's where they should be in the sort sub. Reread perldoc -f sort.

Note you're missing a closing ' in your code, too ('sk2' => 'val2,).

Update: just noticed you wanted the keys in descending order of their score value, just swap $a and $b in the code.