A pruned backtracking search must run inside a request latency budget — how do you decide whether it can ship?

## The claim to challenge first "With good pruning it's basically polynomial" is the sentence this question exists to catch. It is wrong in a specific and important way. Pruning removes subtrees **when the bound proves them hopeless**. Big-O is an upper bound over *all* inputs, and the input on which the bound never fires still exists. A pruned search is a faster exponential search: better constant, dramatically better average case on realistic data, identical worst case. The practical form of that distinction: benchmarks on production traffic tell you about the inputs you have seen. They say nothing about the input a user will submit tomorrow, and nothing at all about an input an adversary will submit deliberately. ## Find the shape that defeats the prune Before any latency conversation, characterise the bad input concretely. For a budget-capped bundle builder over a gift catalogue, the pruning test is "running total over budget — stop". It fires early when items are expensive relative to the cap. It therefore *fails* when: - items are priced far below a generous cap, so almost every partial selection stays feasible and the search walks nearly the whole tree; - prices cluster tightly, so the bound is nearly the same on every branch and gives no discrimination; - the catalogue is large, since the tree doubles with every additional item. And now notice that this is not an exotic shape. "Cheap items, generous budget, big catalogue" is a *good customer* — the search collapses precisely on the traffic you most want. That is the argument that moves a room: the worst case is not adversarial here, it is aspirational. ## The three controls **1. Bound the input.** Plot nodes visited against catalogue size on realistic price distributions, including the bad shape above. Set the accepted input size where the curve is still flat, with headroom, and reject or narrow beyond it — filters, categories, a required price floor. This is a product conversation, not a technical one: "we search up to 30 candidate items; past that we ask you to narrow the selection" is a shippable sentence. **2. Bound the search.** Even inside the input cap, carry a hard **node budget** or deadline in the recursion and stop when it is exhausted. What you return at that point must be designed, not accidental: the best bundle found so far, explicitly marked approximate, is usually right; an error that invites an identical retry is usually wrong. Prefer counting nodes over checking a clock — node counts are deterministic and therefore reproducible in tests, while wall-clock caps make failures depend on which machine ran them. **3. Make it observable.** Emit the node count per request and a counter for cap-hits. Without that you cannot tell a search that finished early from one that finished exactly, and you will not notice the day a catalogue change moves the whole distribution. The cap-hit rate is the metric that tells you whether the input bound is still right. ## The judgement that is actually yours With the controls in place, the remaining decision is about worth, not about speed: - **What is exactness worth here?** If the product promises "the best bundle under your budget", approximations need disclosure. If it promises "some good bundles", a greedy or value-density heuristic runs in near-linear time and may be indistinguishable to the user. - **What is the cost of the alternative?** A pseudo-polynomial dynamic program may exist for the exact same objective and be dramatically better behaved on large catalogues, at the cost of memory proportional to the cap and a structure fewer people on the team can debug at 3am. Ask who maintains it. - **Does it belong on the request path at all?** Precomputing bundles per category overnight, or caching by the tuple of filters, converts a latency problem into a freshness problem — often the better trade for a catalogue that changes daily rather than per request. - **What breaks at ten times the catalogue?** If the answer is "the search doubles thirty more times", say that plainly. A control that only holds at today's scale is a dated decision, and it should be written down with the date on it. ## The one-sentence version to have ready "It prunes well on our data, the worst case is still exponential, so it ships behind an input cap and a node budget with a documented fallback — and we revisit when cap-hits exceed a threshold or the catalogue grows past the size we measured." That sentence contains the correction, the controls, the fallback and the trigger to reconsider, which is the whole of the judgement.