How do you prove a feasibility predicate is monotone before binary searching an answer range?

## What monotonicity means here, precisely For a first-true search over candidates `lo..hi`, the property required is: > if `feasible(x)` is true, then `feasible(y)` is true for every `y > x` in the range. Equivalently, the sequence of answers reads `F…F T…T` and never switches back. This is a property of *the boolean predicate*, not of the metric behind it. The underlying measurement may wobble, curve or plateau; what matters is whether crossing the threshold that turns the boolean true can ever be undone by moving further in the same direction. ## Prove by relaxation, not by sampling The standard proof shape is a witness argument. A candidate `x` is feasible because *something* satisfies the requirement under `x` — an assignment, a schedule, a configuration, a physical run. Show that the same witness remains valid under any larger candidate, because the larger candidate only weakens the constraint it had to satisfy. Then feasibility cannot turn back off, and monotonicity holds for the whole range by that one argument. Sampling has the opposite logical shape. Probing ten candidates and finding a clean false-then-true pattern proves nothing about the candidates you did not probe; but a *single* probe that comes back false above a true one refutes monotonicity outright. So the honest workflow is: argue monotonicity as a property of the system, and use a coarse sweep as a cheap attempt to *falsify* your own argument, not to confirm it. ## Where the argument quietly fails Relaxation arguments hold when the parameter is purely a budget: more time, more capacity, more tolerance, and nothing else changes. They break when the parameter also changes *how the system behaves*. **A rate limit and retries.** Suppose you are tuning a request-rate limit and the predicate is "p99 latency stays under the target". The tempting claim is that a stricter limit is always at least as safe, so feasibility is monotone downwards. It is not automatic. Rejected requests are frequently retried, and retries add load; tighten the limit enough and offered load rises, queues deepen, and a limit that should have been "safer" misses the target that a looser one met. The predicate has a hole in the middle of the range. **Batching.** A pipeline where the parameter is batch size can behave the same way: very small batches keep the working set resident and stay fast, very large batches amortise a fixed flush cost and stream well, and a middling batch can be the worst of both — too big to stay resident, too small to amortise. If the requirement is a latency ceiling, the predicate can read true, false, true across the range. Nothing about that is exotic; it happens whenever the parameter selects between qualitatively different regimes. The pattern to watch for is a parameter that changes *which mechanism runs* — a code path, a retry policy, a cache residency boundary, an admission decision — rather than merely how much of a resource is available. ## What a non-monotone predicate does to the search The damaging part is that nothing fails. Binary search commits to one side at every probe and never revisits the discarded half. Land one probe inside a dip and the entire region containing the true boundary is deleted from consideration; the loop terminates normally, the window collapses normally, and a number comes back that looks exactly like an answer. There is no exception, no diagnostic, and — if the returned value happens to be feasible — no obvious way to notice from the result alone. Compare this with a full sweep, which is slower but shows you the shape. ## Salvaging a range you cannot prove monotone - **Explain the dip first.** A measured non-monotonicity you cannot account for is a signal that your model of the system is wrong; searching harder does not fix that. - **Restrict the range.** Often monotonicity holds cleanly on a sub-range you can argue about — above the point where the alternative regime kicks in, say. Search there and document the restriction. - **Change the predicate.** Sometimes a stricter or differently-worded requirement is monotone where the original was not, for instance by including the retry-amplified load in the definition rather than treating it as an external effect. - **Use a different tool.** If the response is unimodal rather than monotone — one interior optimum instead of one flip — a search that compares two interior points is the right shape, and if it is neither, a coarse grid plus judgment beats a fast wrong answer. ## Direction discipline Finally, state the direction explicitly. "Monotone" alone is ambiguous: feasibility can be true above a threshold (more budget helps) or true below one (less aggressive setting helps). Pin down which, because the loop's boundary conventions follow from it, and a correct proof paired with a mirrored loop still gives the wrong answer.