Is that really true? Can't you track invalidations via a dependency graph?

Right, as you said, you'd have to recompile dependents.