Hello mitcho,
I experienced a good improvement to client-side pageload times by adding score and date to the related cache primary key:
ALTER TABLE wp_yarpp_related_cache DROP PRIMARY KEY ,
ADD PRIMARY KEY ( score , date , reference_ID , ID )
in this order. It essentially removes the table fetch (adds using index) in the SQL for yarrp_cache_enforce and removes the using filesort pass (and adds using index) in the SQL for get_posts. Faster all around.
Just an FYI. Happy Holidays.
http://wordpress.org/extend/plugins/yet-another-related-posts-plugin/