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.