Could you maybe provide a practical example of such a "heavy to process" 404? I'm having difficulty to image how a "Not Found" could (or ever should) involve heavy processing. AFAIK, a 404 should be only given for a non-existing resource (e.g. file). That should be straightforward enough. Granted, I've seen some horrible semantic resource pointers/paths in URI's over the years, some of which requiring processing, and some of them generating 404s. However, such contortions are mostly just a testament to horribly bad design. If the request involves processing on the server side (higher up than the web server or cache itself), resulting in a conclusion that a resource is unavailable, should that not return a 5xx response?
The origin server might be set up to serve everything through cgi. That would mean loading the entire framework just to spit out a 404 for the favicon. If all the other pages cache just fine, you could hit 100% load on favicons when you'd otherwise be at 10%.
It's not an ideal design but I wouldn't call it 'horrible'.
What is CGI in this context? I’ve only heard of it in a movie special effects context.