>If you do it naively, the complexity will be exponential

Hindley-Milner type inference is doubly exponential already but is still widely used. If people never actually use extremely nested expressions in real code that require this sort of disambiguation then it will probably be completely fine.