Engineering Atlas › Problem Solving & Incidents (AI era)

Bisecting: Binary Search for Causes

12 min read · last reviewed 2026-10-17

Open in the interactive app: practice, quiz, mock interview →

In one minute

How it works

When bisection applies

You need three things: a known good point, a known bad point, and a test that tells them apart. The sequence between them should be monotonic for the bug: once broken, it stays broken until the end. Regressions in a linear commit history are the classic case. Performance regressions work too, as long as you turn "slower" into a threshold ("p50 of this benchmark over 40 ms is bad").

The oracle

git bisect run ./check.sh drives the whole search with a script. The exit code is the protocol: 0 means good, 125 means this commit cannot be tested so skip it, codes from 1 to 127 other than 125 mean bad, and anything of 128 or more aborts the bisect (git-bisect docs). Git picked 125 because 126 and 127 are the shell's "not executable" and "command not found", which therefore count as bad: a misspelled script path marks every commit bad, so test the script on both endpoints first. The most common bisection mistake is an oracle that fails for the wrong reason, such as a build break, a missing fixture or a network timeout, and so reports "bad" on commits that do not contain the bug. Make the script check for the specific symptom (an exact error string, an assertion, a measured threshold) and exit 125 when the build itself fails.

Skips and untestable ranges

Real histories contain commits that do not build, or where a dependent feature is half-merged. Skipping them is fine until the skipped commits sit right at the boundary. Then bisect can only say "the first bad commit is one of these", and you inspect that small set by hand; the docs warn that skipping a commit adjacent to the culprit makes Git unable to tell which of them was first (git-bisect docs). A team that keeps every commit on main buildable gets sharper answers.

Bisecting things that are not commits

The same search applies to many spaces. A config file with 200 changed keys between a good and bad environment can be bisected by applying half of the diff. A dependency lockfile upgrade that moved 60 packages can be bisected by package. Feature flags turned on during an incident window can be bisected by toggling half. A fleet where only some hosts misbehave can be bisected by host attributes. Delta debugging generalises this to inputs where several parts must combine to trigger the failure. Russ Cox's hash-based bisect tool goes further and bisects over code locations (a function, a rewrite rule, a call stack) instead of commits: in his Go 1.23 timer example it narrowed a failing test to one time.After() call site (Cox, 2024).

Non-linear history

Git history is a graph with merges. git bisect does not walk a list; it chooses a commit that splits the set of candidate commits (ancestors of bad, not ancestors of any good) as evenly as it can. If a merge brought in a long-lived branch, the first bad commit may be on that branch, or the bug may appear only at the merge itself because two individually fine changes conflict. git bisect --first-parent follows only the first parent at each merge, so the merge commit is reported as the introduction and the merged branch's own commits are ignored (git-bisect docs). That also avoids false positives from non-building commits inside a merged branch.

Down the stack

Layer 1The contract

Given a good commit G, a bad commit B, and an oracle that is deterministic and monotonic along the path, bisection returns the first bad commit using at most about ceil(log2 N) oracle calls for N candidates. If the oracle is not monotonic (the bug appeared, vanished, then reappeared), bisection still returns a good-to-bad transition, just not necessarily the one you care about. If commits are skipped, the result may be a set of candidates instead of a single commit. With a flaky oracle the contract is void: a single wrong answer sends the search into a half that does not contain the cause, and nothing in the output warns you.

Layer 2The mechanism

git bisect keeps its state as plain refs and files under .git: refs/bisect/bad, one refs/bisect/good-<sha> per good mark, refs/bisect/skip-<sha> per skip, plus BISECT_LOG and BISECT_START. Because state is on disk, you can stop, inspect, and replay a session with git bisect replay. When you hunt for a change that is not a regression, git bisect start --term-old fast --term-new slow renames good and bad so the commands read correctly (you cannot mix the two vocabularies in one session; git-bisect docs). At each step git computes the candidates as commits reachable from bad but not from any good, and for each candidate how many other candidates it can reach. The best pick is the commit whose reachable count is closest to half. When the best pick is skipped, git moves to a nearby candidate instead.

When the oracle is noisy, deterministic bisection breaks down. A probabilistic variant keeps a probability for each candidate being the first bad commit, updates it with Bayes' rule after each test given an assumed false-positive and false-negative rate, and tests where the cumulative probability crosses 50%. It costs more tests but tolerates noise. Several open-source tools implement this idea; check their assumptions before trusting the output.

Layer 3The machine

The cost of bisection is not the search, it is each step's build and test. Checking out a commit rewrites the changed files in the working tree, updating their mtimes, which invalidates incremental build outputs that depend on them. In a large C++ or Rust codebase that can mean minutes per step. Practical speed-ups: build each step in a separate git worktree so caches survive, use a compiler cache like ccache or a remote build cache keyed by content hash, and, best of all, bisect over CI artefacts already built per commit so each step is a download plus a test run. Kernel bisection is the extreme case: each step needs a kernel build, an install and a reboot. The kernel's own guide puts a trimmed build (make localmodconfig) at about 10 to 15 minutes on commodity x86 hardware and a bisection between two stable series at about 15 builds, so it is an afternoon of work and an automated test rig pays for itself (Linux kernel docs). The same guide says to double-check every verdict, since one wrong label derails the rest.

Why it's built this way

  1. Changes arrive as many small, ordered steps, so the cause of a regression is usually a single step between a good and a bad point.
  2. Ordered search spaces admit binary search, so the cost grows with log2 of history length, not with its size.
  3. Each step is expensive (build, deploy, test), so you automate the oracle and cache artefacts per commit.
  4. Real histories contain untestable and non-linear parts, so the tool supports skips, graph-aware midpoints and first-parent mode.

Diagram

flowchart TD
    S["Range: good G, bad B"] --> M["Pick midpoint commit"]
    M --> T{"Run oracle"}
    T -->|"exit 0"| G["Mark good: move G up"]
    T -->|"exit 1-127"| B["Mark bad: move B down"]
    T -->|"exit 125"| K["Mark skip: try neighbour"]
    G --> D{"Adjacent or only skips left?"}
    B --> D
    K --> D
    D -->|"no"| M
    D -->|"yes"| R["Report first bad or candidate set"]

Worked example

A service's p99 latency on a synthetic benchmark rose from 18 ms to 31 ms between the release two weeks ago and today. In between are 2,300 commits on main. Building and running the benchmark takes 6 minutes per step, and CI has a container image for every main commit, so steps can skip the build and take about 90 seconds.

The oracle runs the benchmark five times and reports bad if the median p99 is over 25 ms, a threshold far from both modes, so noise rarely crosses it. It exits 125 if the image is missing. log2(2,300) is about 11.2, so expect 12 steps. One image is missing, which costs one extra step. Thirteen steps at 90 seconds is under 20 minutes, unattended. The first bad commit is a logging change that switched a formatter from lazy to eager evaluation in the request path. Nobody had suspected it because the diff touched only a logging helper; the oracle did not need a suspect.

Contrast with a 1-run oracle and a benchmark that is noisy about 5% of the time near the threshold: over 12 steps the chance of at least one wrong answer is about 1 - 0.95^12, roughly 46%. That is why the oracle takes a median of five and uses a threshold well away from both modes.

In the wild

Trade-offs

ApproachStrengthsWeaknessesChoose when
git bisect runMechanical, needs no hypothesis, log2 costNeeds good and bad points and a reliable oracleClear regressions in code
Bisect CI artefactsVery fast steps, no local buildsNeeds per-commit artefacts retainedLarge codebases with slow builds
Bisect config or flagsFinds non-code causesInteractions between keys can confuse itEnvironment drift, incident flag changes
Probabilistic bisectTolerates flaky oraclesMore steps, needs an error-rate estimateIntermittent failures
Reading the diffFast for small rangesBiased toward suspicious-looking codeUnder about 10 commits

Pitfalls in production

Leadership lens

Check yourself

  1. Why does a single wrong oracle answer ruin a bisect without any warning?

    Show answer

    Each answer discards half the range permanently, so a wrong one discards the half that contains the cause, and the search converges confidently on an innocent commit.

  2. A bisect ends with "the first bad commit could be any of" four commits. What happened?

    Show answer

    The commits next to the boundary were skipped as untestable, so the search cannot place the transition more precisely than that set.

  3. Why can the first bad commit be a merge even if both parents are good?

    Show answer

    Two changes that are each fine can conflict semantically when combined, so the bug exists only in the merge result.

  4. Your oracle measures latency. How do you make it safe for bisection?

    Show answer

    Repeat the measurement, take a robust statistic like the median, and set a threshold far from both the good and bad distributions.

Sources and further study

Primary

Systems docs

Books

Other curricula

Watch

Free resources

Open in the interactive app: practice, quiz, mock interview →