Instruction bisection

Bisection here is the search git bisect performs over commits, pointed at a prompt: halve the candidate elements, test each half against the failure, and recurse into whichever half still fails. The candidates are the numbered instructions of a system prompt — text you wrote, that you own, and that you can edit this afternoon — which makes it the natural complement to the context ablation of the previous chapter, where the material under search was data retrieved at request time and a block under suspicion had to be replaced by an inert passage of matching length rather than deleted outright.

The complication is that instructions are not independent constraints. They are natural-language pressures that combine, so a failure can be produced by two lines that are individually harmless, and the search has to be built expecting that rather than surprised by it.

Where halving came from and what it promises#

The technique is delta debugging, from Andreas Zeller's 1999 work on reducing failure-inducing inputs — the paper whose title asks why a program that worked yesterday does not work today. It replaced the practice of manually whittling a 10,000-line failing input down by hand, and its central algorithm, ddmin, halves the input, tests each half, and recurses on whichever part still fails. Compiler and browser teams have used it for two decades to turn a page that crashes into a fourteen-character reproduction.

Halving is not obviously permitted, and the assumption that permits it is worth stating before the algorithm that leans on it is described. Delta debugging treats the failure as a monotone property of the input set: roughly, if a set of elements produces the failure then supersets of it do too. Read in the direction the search actually uses it, the same assumption says that a set which passes has no failing collection hidden anywhere inside it.

That assumption is what converts a test result into a licence to discard. Split the candidates into two halves and run each half on its own. If the first half fails, then by the assumption a failing collection lies wholly inside it, and the second half holds no part of a collection already shown to fail without it — so the second half is thrown away and the search continues at half the size. If the first half passes and the second fails, the same argument runs mirrored. Each level of the search costs two runs and eliminates half the candidates, and repeating that is the entire source of the logarithm in the cost.

The case the argument does not cover is the one where both halves pass. Monotonicity said a passing set contains no failing collection anywhere inside it, so if neither half fails on its own, no failing collection lies wholly inside either half. The elements that matter straddle the cut. Nothing has been eliminated, the candidate set is still at full size, and there is no smaller set to recurse into, which is halving running out of moves rather than halving converging.

What is left to vary at that point is not which half is present but which combinations are. A procedure that only ever tests halves and their complements can never construct a set spanning a cut it has already made, because every set it builds is contiguous in the splits it chose. The smallest combination larger than a single element is a pair, so the search moves to pairs among the survivors. That is a different algorithm at a different price rather than one more turn of the same crank: the halving-and-recursing loop is cheap because each level throws half the work away, and a pair sweep throws nothing away and enumerates instead.

What ddmin guarantees is a 1-minimal failing configuration: a set where removing any single element makes the failure go away. It explicitly does not guarantee a set of size one, it does not guarantee the globally smallest set, and it does not guarantee uniqueness — there can be several distinct minimal sets that each produce the failure. Those caveats are usually academic for a crashing C file, where one macro is genuinely at fault. They are the normal case for a system prompt.

Two notions of minimal are in play in that paragraph, and the distance between them is where the caveats come from. A minimal failing set in the strong sense is one no proper subset of which still fails, and establishing that for a set of k elements means testing every one of its two-to-the-k subsets, which is why no practical algorithm offers it. The 1-minimal version is the cheap approximation: it tests only the k subsets you reach by removing one element at a time. A set can pass that cheaper test and still contain a smaller failing set inside it, because reaching the smaller set requires removing two elements at once and the cheaper test only ever removes one.

Neither notion says anything about blame, and that is the step at which the technique gets misread. Minimality is defined by which subsets were tested and what those tests returned, which makes it a stopping condition for a search rather than a property of the prompt. Two different split orders over the same eleven instructions can terminate on two different sets, both correctly 1-minimal, with different members in them. A property that moves when you change the order in which you ran your experiments is not a property of the thing you were experimenting on.

The belief that the surviving set is the cause is tempting for three honest reasons, and they are worth naming because they are what makes it feel like a finding rather than a guess. The run flips when the set is removed, which is exactly what a cause looks like from outside. The set is small, and a set of two feels like an answer in a way that a list of eleven does not. And in the territory the technique came from it is usually right: a C file that crashes a compiler crashes because of one construct, adding unrelated declarations does not repair a parser bug so monotonicity genuinely holds, and the minimal set really is the defect. A system prompt satisfies none of those three conditions.

Prompts violate monotonicity in both directions, and the second direction is the one that quietly invalidates results rather than merely slowing the search down. Adding an instruction can suppress a failure that a smaller prompt exhibits. So when a variant comes back clean, the reading that survives review is that this particular combination does not fail — not that the elements you dropped were the ones responsible, which is a stronger statement the run did not make.

Splitting the surviving half#

Take a system prompt of 900 tokens and eleven numbered instructions, on a trace that reproduces on 30 of 30 pinned replays. A single run per experiment is admissible evidence at that reproduction rate (chapter 4, where a failure rate is estimated by replaying a frozen request twenty or thirty times at the production sampling settings and reading the proportion off), so the search can be fast. With five candidates surviving the first split, it finishes in about a dozen runs. Each variant keeps the retrieved blocks, the user turn, and the sampling settings identical, so the only thing varying is which instructions are present.

Each row of that table rules out considerably less than it appears to. Run 1 varies nothing and establishes that the harness reproduces the refusal from the frozen request, and it says nothing whatever about any individual instruction. Run 2 keeps the first six instructions and drops the rest, and the refusal disappears. Under the monotonicity assumption that licenses the split, that result says no failing combination lies wholly inside instructions 1 through 6. It does not say those six are irrelevant to the failure, and runs 9 through 11 later depend on them being present.

Run 3 is the complement, with the second half alone and the first six gone, and the refusal returns. A failing combination therefore lies wholly inside 7 through 11, and the first half can be set aside. This is the one level of the sweep at which halving worked exactly as advertised, and no later level repeats it.

Runs 4 through 8 drop one instruction each from the otherwise complete prompt, holding the retrieved blocks, the user turn, the seed and the sampling settings fixed. Every one of them still refuses. The tempting reading is that none of the five is responsible, which cannot be true, since run 3 already showed the failure living inside that half. What the five runs establish is narrower: no single instruction among them is necessary, because for each one there exists a version of the prompt without it that still fails.

Necessity is the property those runs test, and it is not the property most people believe they are testing. A run that drops instruction 9 and still refuses asks whether the failure needs 9 present, rather than whether 9 contributes to it. The two questions come apart the moment more than one combination of instructions can produce the same output, because then removing a member of one combination leaves the other intact and the observable output does not move at all.

Runs 4 through 8 are therefore the important ones, because they are what tells you to stop looking for a single culprit. Every instruction in the failing half can be removed individually with the refusal intact, so the half is 1-minimal at size five by the naive test, and a search that treats 1-minimality as a finish line halts there holding five lines and no candidate. Moving to pairs finds it.

Run 9 drops 9 and 10 together and the refusal survives, which eliminates that pair. Run 10 drops 9 and 11 together and the refusal clears, so the two of them are jointly necessary: the failure needs at least one of the pair present, and taking both away is what takes it away. Run 11 confirms sufficiency in the other direction, keeping only 9 and 11 out of that half alongside the harmless first six, and the refusal returns with 7, 8 and 10 absent from the prompt entirely. Run 12 repeats the baseline at the end and earns its place by being boring. Had the refusal failed to reproduce there, an index rebuild, a snapshot rollout or a cache would have moved underneath the experiment and every row above it would be uninterpretable.

Three rows of that table read together say something sharper than the summary the sweep usually gets, and they are the clearest available demonstration of why a minimal set is not a culprit. Run 8 keeps everything except 11 and still refuses, so a failing combination exists that does not contain 11. Run 10 removes 9 from that same prompt and the failure clears, so every failing combination inside it contains 9. Run 4 runs the argument mirrored: with 9 gone and 11 present the prompt still refuses, and removing 11 as well clears it, so a failing combination exists that contains 11 and not 9.

That is two distinct failing combinations inside one prompt, one built around instruction 9 and one built around instruction 11, each with a partner the sweep never identified. Runs 4 through 8 came back refusing for that reason rather than by accident: each single removal destroyed one combination and left the other standing, which is how a redundant cause hides from a search that removes one element at a time. A searcher who read run 4 as exonerating instruction 9 would have drawn a wrong conclusion from a correct measurement, and would have carried on splitting towards a minimal set that happens not to contain the line they were eventually going to be told to edit.

The cost of the whole procedure follows from the two shapes of search it is built out of, the halving and the pair sweep, and the arithmetic is worth doing on these figures before it is trusted on larger ones. Pure halving over eleven instructions splits them into a six and a five, splits the failing five into a three and a two, and splits a failing three into a two and a one. Three levels, two runs at each level, plus a baseline at each end, comes to under ten runs to reach a single instruction — if every level produces a half that fails on its own. That is the logarithmic best case, and this sweep did not get it.

The pair search prices differently because it enumerates rather than discards. The number of pairs among five survivors is five times four, halved because a pair has no order, which is ten. The sweep above ran three of those ten and stopped when one of them cleared the failure. Had 9 and 11 been the last pair tried rather than the third, seven further runs would have been needed and the sweep would have finished at nineteen rather than twelve. Five singleton runs and three pair runs, on top of two splits and two baselines, is where the dozen comes from.

Quadratic growth is gentle at five and unpleasant very quickly afterwards. The comparison below puts a typical instruction count at 10 to 30, and thirty instructions have thirty times twenty-nine halved, which is four hundred and thirty-five pairs, against the handful of runs halving would have cost had it worked. Going one step further to triples multiplies that again by roughly the survivor count divided by three, which puts the same prompt into the thousands of runs. Pairs are affordable and triples are a research project, and that boundary is the practical limit of the technique rather than a matter of how patient the engineer is.

Every count above assumes one run per arm, and that assumption is carrying a great deal of weight. It holds here only because the failure fires on 30 of 30 pinned replays, which is what makes a single run a verdict rather than a sample. When the failure is intermittent instead, each arm stops being a run and becomes a batch: twenty or thirty samples, a proportion read off them, and an interval around that proportion wide enough to matter.

Multiply the sweep by that and the arithmetic stops being comfortable. Ten pair runs at thirty samples each is three hundred runs for the pair stage alone, and every comparison at the end of it is between two intervals rather than between two answers. An arm whose rate moved by a few points will not be distinguishable from an arm whose rate did not move at all, which means the sweep can be run to completion and still return nothing usable. Finding or manufacturing a deterministic reproduction before bisecting is therefore not tidiness. It is the difference between a search costing a dozen runs and a search that cannot be afforded.

Generating the variants deserves a small amount of care, for reasons that echo the substitution discipline of the previous chapter.

INSTRUCTIONS = {1: "...", 2: "...", ...}   # keyed by their printed number

def render_system(drop: set[int]) -> str:
    lines = [f"{n}. {text}" for n, text in INSTRUCTIONS.items() if n not in drop]
    return PREAMBLE + "\n".join(lines)      # numbering stays 1..11 with gaps

for drop in [set(), {7,8,9,10,11}, {1,2,3,4,5,6}, {9}, {7}, {8}, {10}, {11}, {9,10}, {9,11}]:
    out = replay(system=render_system(drop), seed=PINNED_SEED)
    print(sorted(drop), "REFUSED" if refused(out) else "ok")

Keeping the original numbers and letting the list have gaps means that dropping instruction 9 does not silently renumber 10 and 11, which matters if any instruction refers to another by number, and which also keeps the variants comparable to a reader. Dangling cross-references are worth checking for before the sweep: a prompt that says "subject to rule 4" and no longer contains a rule 4 is a different kind of broken and will produce results you cannot interpret.

Two searches over two different things#

Instruction bisection and context ablation get described interchangeably as "delete parts of the prompt and re-run", and they behave differently enough that treating them as one technique produces bad experiments.

Start with the "held constant" row, because it settles what each search is entitled to ignore. Instruction bisection holds fixed everything that varies between one production request and the next: which blocks retrieval returned, the order it returned them in, their token counts, the user's turn. Context ablation holds fixed everything you wrote: the instructions, the layout of the prompt around the blocks, the budget. Each is clean on exactly the material the other one is searching, which is why running both against the same trace is not redundant work.

The confound rows are the substantive difference, and they follow from that split. Ablating a block moves every block below it and returns hundreds of tokens to the budget, which is why the previous chapter insisted on same-length substitution. Dropping a 25-token instruction from a 900-token system prompt changes the total by under 3% and does not reorder anything the retriever produced, so instruction bisection is comparatively clean on layout and comparatively dirty on interactions. The techniques fail in opposite ways, and the controls that fix one do not address the other.

Comparatively is the honest word there, and the claim should not be pushed past it. Dropping an instruction does shift every token after it, and a prompt sensitive enough to notice that shift is one whose bisection results deserve a repeat with the removed line replaced by inert text of matching length rather than deleted outright. The difference in kind is that ablating a block moves whole blocks between rank slots, which is a change of the same size as the thing being measured, whereas removing an instruction moves everything by a fraction of one block.

The interaction confound has a mechanism underneath it, and the mechanism explains why the effect is severe on the instruction side and mild on the retrieval side. A system prompt is read as one policy rather than as a list of separable rules, and each instruction is interpreted in the light of the others present. Remove one, and the remaining lines are not the same lines; they are the same text under a different set of neighbouring constraints. Retrieved blocks sit closer to evidence than to policy, and evidence composes more additively, in that removing a passage usually removes what that passage said and little else. Usually rather than always — a block that contradicts another changes how the other is read, which is the case the previous chapter was built around.

The last row is the one that decides what happens after the investigation. A localised instruction pair is something a single engineer can rewrite in an afternoon, in a file they own, with a diff that reviewers can read. A finding about a retrieved block is a claim about a corpus, an ingestion pipeline and a ranking function, usually owned by another team, and acting on it changes every query the system will ever serve.

Which to run first on a 30,000-token request#

Take the concrete case: eleven numbered instructions, five retrieved context blocks, a user turn, about 30,000 tokens in total, four seconds a run. The confident answer is to bisect first because bisection is logarithmic, and it is wrong here for a reason that has nothing to do with asymptotics. The two searches cover different halves of the request, so they are not alternatives competing on efficiency; they are two search spaces and the question is which one to eliminate first. Efficiency would be the right axis if both procedures answered the same question, and they do not: a completed bisection says nothing about the retrieved blocks, and a completed ablation sweep says nothing about the instructions.

Ablating five blocks is five runs and about twenty seconds at modest concurrency, and it eliminates the entire retrieval half of the space. It also touches the larger share of the input: the five blocks are perhaps 26,000 of the 30,000 tokens, and they are the portion that differs from request to request, which makes them the more likely home for a failure that appears on one trace and not on similar ones. Bisecting eleven instructions is somewhere between three and thirty runs depending on how far into pairs you go, and the instructions are constant across every request your service makes, so a defect there tends to show up on many traces rather than one.

There is a second reason to sweep the blocks first. Instruction bisection assumes the rest of the request is fixed, and if a retrieved block turns out to be doing the damage, every instruction-level result you collected was measured in the presence of that block and may not survive its removal.

What a single combined deletion teaches#

A teammate deletes three context blocks and two instructions in one run, gets a good answer, and calls it a bisection. They have learned one bit of information: the failure is not produced by the six elements that remained. The responsible element is somewhere among the five that were removed, which is a legitimate first step of a search and is worth precisely as much as any other first step.

One bit is meant literally rather than as a figure of speech. The run had two possible outcomes and returned one of them, so it cut the space of hypotheses in two, and that is the whole of what a single test can deliver however many elements it moved. Removing five elements at once buys no more information than removing one, and it spends the ability to say which of the five did anything.

What makes it hard to build on is that the removed set spans both search spaces. The next split has to decide whether to divide the blocks or the instructions, and because the run also changed layout and returned a few thousand tokens to the budget, the result is confounded in the way the previous chapter described. A cleaner first cut, at identical cost, would have been to substitute all five blocks with matched filler in one run: if the failure survives, retrieval is exonerated in a single run and the whole search collapses onto the instructions.

There is a second limit on what the combined deletion established, and it comes from the direction in which prompts break monotonicity. A good answer means this particular six-element prompt does not fail. It does not mean the responsible elements are among the five that were removed, because one of the six survivors may be suppressing a failure the smaller prompt would otherwise exhibit. Settling that takes the complementary run, with the five restored and the six survivors taken away, which is the same necessity-and-sufficiency pairing that runs 10 and 11 supply in the table above.

Localisation is also not a fix. Establishing that two instructions jointly produce a refusal does not tell you which one to change, and frequently the answer is neither. Removing a member of the set is a demonstration rather than a repair: it shows that the failure depends on that member being present, in a prompt nobody would ship, because the line was there for a reason and the reason has not gone anywhere. What the finding buys is a precise target for a rewrite: narrow the scope of one of them, add an explicit carve-out, or reorder so that the scope of the first is stated before the second is introduced. Each of those is a hypothesis that has to be re-run against the same input, the same seed and the same settings before it counts as verified.

The expectation to carry into the next prompt investigation is therefore the opposite of the one bisection is usually described with. You are not hunting for the line that broke it. You are narrowing to the smallest set of lines that still breaks it, and when that set has two members, the two of them together are the finding — which is why the pair-testing runs are the ones worth keeping in the ticket, and why a search that stops at the first individually-removable instruction reports a culprit that does not exist.

And a rewrite verified on one input is verified on one input. The prompt is shared by every request the service handles, the pair you just untangled was itself the product of somebody fixing an earlier trace, and the next chapter is about what a single escalated trace is actually allowed to change.