Because memoization often can affect the asymptotic runtime of algorithms (and of course space usage), this can lead to very confusing behavior for a user, if you determine at runtime similarly to a JIT compiler whether to memoize. Imagine an algorithm's asymptotic complexity jumping back and forth between exponential and linear over the course of a program running as the runtime analyzer memoizes and unmemoizes a function call.
Since you already have a lazy language, you can direct users to use lazy data structures to achieve memoization. http://jelv.is/blog/Lazy-Dynamic-Programming/
One issue I raised is that you don't want to memoize a function that itself is memoized. Well, if we can detect at runtime that a function is not reused, it does tend to mitigate that issue.
You need to be able to turn it on and off depending on demand.
A bloom filter (though there are more efficient variants out there) can watch the keys set and requested and calculate a predicted hit rate over a sample period. Most variants of bloom filters don't allow dropping keys, but that's not strictly necessary: you can simply sample for a given number of hits and then reset the filter.
If the hit ratio is less than a threshold after some number of hits, it can drop the table and reset the state back to sampling for potential memoization.
Another problem for long running processes is avoiding memory spikes. Ideally you just figure out how much you can allocate and stay within that. (You can also use weak references to mitigate low memory situations; the system can track how often it's being garbage collected and use that to self-suppress.)
A bloom filter naturally has very predictable memory usage, and you can limit the number of pairs a cache will hold. That suggests a global strategy whereby you have a parameter saying, "only memoize the top functions and ensure tables fit in X MB." Tracking the size of memoized values does mean walking the graph; though can always limit a graph walk and refuse to memoize very large objects.
It's adding a bunch of machinery to each function, so it would make sense for the compiler to use some heuristics to eliminate likely poor candidates. One heuristic is whether a function has loops or recursion. Another is whether a function has only a single caller.
It just seems like one of those ideas that really could work and cover a ton of use cases, but in prod you'd want a bunch of tunable parameters and compiler hints, and then all the tooling to make it usable. I think you'd want to sort those requirements back to something simple you can actually code so you can see what people do with it in practice.