I don't this this is even a problem.
Just did a quick grep on crate.io packages, it seems most of the crate uses exactly same version of the dependencies + similar configuration set.
For example, for the serde dependencies, it turns out like that.
309 ">= 0.3.0","features" [""]
356 "^1.0","features" ["derive"]
368 "^1.0.0","features" []
1039 "^1.0.2","features" []
1538 "^0.9","features" []
1846 "^1","features" []
1920 "^0.8","features" []
8952 "^1.0","features" []
And for libc
472 "*","features" []
480 "^0.2.21","features" []
506 "^0.1","features" [""]
711 "^0.1","features" []
1004 "*","features" [""]
8460 "^0.2","features" []
I don't think the feature set and toolchain is a problem, it can be treated as a part of "version" in the cache system, as well as the Rust edition, etc.
But one thing makes the original idea doesn't work, it seems most of the crate use exact version of a dependency. But I do think this makes a LRU cache very efficient in fact.
And the assumption is there is definitely a commonly used version + build configuration for certain crate. And when switching toolchain / compiler version, it will just use a different cache / invalidate the previous cache.
So there won't be exponential binaries in the cache and we don't need to build every possible configuration for sure.