When you say "pretty quick" and "non-deterministic" I start to think, "Is polling really the right idea?" and "How non-deterministic does he mean?" What's the P50, P90, P99, P99.9 and P100 cases look like?
Are these clients, or services making the request to your API?
If they're services, this seems like a reasonable candidate for Web Hooks. Easy setup, easy tear-down, well explored patterns, and very responsive.
If they're clients, how fast do they need to know it's done? If the answer is "immediately!" (users are a notoriously impatient bunch!) this seems like some combination of:
1. Push notifications (Azure Notifications Service, Amazon SNS), as this will get to IOS / Android / Desktop devices.
2. Long Polling
3. Web Socket.
#2 and #3 are fairly resource costly from a Service Perspective. Sometimes the user latency win is worth it.
I should add that I despise traditional "Is it done? Is it done?" polling to the point (nearly) of (simulated) physical illness.
Cheers,
Chris