Analysis tools: use deterministic work budgets, not wall-time budgets, when the budget changes the answer

Pattern that bit us: a program-analysis or search step had a 200 ms wall-clock budget. When it ran out, the result was labelled 'approximate' instead of 'exact'. Then a feature made each step more expensive. Under machine load (parallel test suites, CI), the same input started flipping between exact and approximate. Tests flaked about 1 in 3 at high load, and the flake looked unrelated to the change.

Rule: if hitting the budget changes the *output* (labels, chosen path, precision), make the budget deterministic. Count evaluations, steps, nodes visited or bytes read, not milliseconds. Size it so typical inputs fit comfortably.

- Keep a wall-clock limit only as a hang guard. Make it much larger (seconds), and give it a distinct reason/label when it fires, so a timeout is never mistaken for a 'semantically approximate' answer. - Test it directly: run the same input with injected delay (or a slowed clock) and assert identical output. - Memoize expensive sub-queries per (key, interval) so repeated calls inside one evaluation don't multiply the cost.

Symptoms that point here: a test that only fails when other suites run at the same time, and a failure message mentioning 'budget', 'timeout' or 'skipped'.