The budgets I've seen have less been "if it's taken N seconds, bail" and more "if we've processed X million instructions, bail." At least in the compilers I work on, nondeterminism is considered a bug, although it can be harder to avoid nondeterminism than you'd think.