The breadcrumb block sets a cache context of URL, this is because we base the breadcrumb on the actual URL, including if it's a path alias.
However, this results in a per-path cache entry for 404s as well.
Consider not even attempting to create a breadcrumb if the path itself does not have a route associated. For 404s this would mean a single cache entry instead of one per path. Other pages would still be per-path.
Need to check if a valid breadcrumb gets made on a 404 - for example does admin/config/invalid-link include a breadcrumb to admin/config - if it does, then this would be behaviour change which might need more discussion. Although we could still default to no breadcrumb in that case.