I just discovered some info that might be relevant to your question.
The cache seems to be built on a post-by-post basis - when a particular post is browsed by a site visitor, its "related post IDs" go into a database table along with all of the posts that it "points to."
So for a theoretical post 9812 it might go into the table as:
| reference_ID | ID |
| 9812 | 0 |
| 9812 | 7761 |
| 9812 | 8032 |
| 9812 | 8049 |
meaning that 7761, 8032 and 8049 are related to (I'd say "pointed to by") 9812. I don't know what the "0" entry is...
Posts 7761, 8032 and 8049, however are -removed- from the cache at this same time, so they'd have to be re-indexed in the future.
So if you browse to one of them at a future time, they'll get rebuilt by YARPP and entered into the table at that time (with their IDs appearing in the reference_ID column.
I can kinda see how Mitcho would have thought that it would be useful to remove 9812 (in my case) from the table just in case it needed to be refreshed because some newly-published post now refers to it - but I don't know that this is a necessary condition and in my case it causes "thrashing" because posts are frequently related to each other in "clusters" and browsing from one to the other causes long cache rebuilds taking about 15 seconds of CPU time each.
I find that to be kind of a "bug" and reported it in
Hopefully this info helps you understand something about when cache entries are created.