Excerpts from an old wikitech-l discussion which might be relevant:
http://article.gmane.org/gmane.science.linguistics.wikipedia.technical/48856
http://article.gmane.org/gmane.science.linguistics.wikipedia.technical/48908

ayg wrote:

It amuses me a bit that I somehow ended up being the one quoted here, since I'm not exactly a great parser expert. I still think a postprocessor is the way to go here. There'd be no other way to cache pages with nonzero stub threshold unless we want to add a lot more cache invalidation logic or accept outdated link coloring. And a postprocessor would let us get rid of cache fragmentation for some other preferences, and avoid having to purge caches in some cases (like page creation/deletion), and maybe other good stuff too. Maybe there's a fatal flaw I'm missing, though, beyond "nobody's stepping up to do it".

Can we ditch stub threshold from parser completely and make is a JS-only thing? This will decrease cache fragmentation at the expense of one simple API request cacheable on Squid level. Furthermore, users with 0 stub threshold will need no API requests at all.

(In reply to comment #3)

Can we ditch stub threshold from parser completely and make is a JS-only thing?
This will decrease cache fragmentation at the expense of one simple API request
cacheable on Squid level. Furthermore, users with 0 stub threshold will need no
API requests at all.

bug 28426

Maybe the length of each article could be included in the links in some sort of data attribute, and coloring could be done entirely on the client side?

(In reply to comment #5)

Maybe the length of each article could be included in the links in some sort of
data attribute, and coloring could be done entirely on the client side?

From http://lists.wikimedia.org/pipermail/wikitech-l/2011-June/053754.html:

We can't put the numbers in any form in the parser cache, because
they'll become outdated as soon as the length of the linked page
changes. The only way to use the parser cache is to put some marker
in it which is substituted for the appropriate page's length when the
parser cache entry is retrieved and displayed. Once we're doing that,
we may as well also check the user's pref and add a class depending on
it, so we don't have to do anything in JS.

Even if we solve this for parser cache, of course, it won't work for
Squid cache. Anons are never going to get nonzero stub thresholds.