The average or maximum number of child nodes expanded from a search node during proof search or model search; measured per decision step or as an overall branching base of the search tree.

Principle

Branching Factor determines the exponential growth rate of a search tree: if each node expands to b children, tree size grows roughly as b^d for depth d, so reducing b is critical for efficiency.

Demonstration

A DPLL-style search that assigns a variable either true or false has a branching factor of up to 2 per decision; a heuristic that often produces unit propagations effectively reduces the average branching factor below 2.

Misapplication

Treating branching factor as an instance-intrinsic constant independent of the chosen algorithm or heuristic ignores that branching depends strongly on variable ordering, propagation, and pruning policies.

Consequence

Lower average branching factor dramatically reduces search effort and can convert exponential-time searches into practically solvable instances by cutting the effective base of exponentiation.

Reversal

A high branching factor (many children per node) denotes broad search rather than deep search; some algorithms trade higher branching for shallower depths with different complexity tradeoffs.

Boundary

Applies to branching search processes; it excludes measures for non-branching inference systems (purely linear transformation pipelines) and depends on the algorithm, not only the problem instance.

Semantic Tension

Tension with Backdoor Size and Clause Width: a small backdoor can force low branching after assignments, while wide clauses might increase branching unless propagation prevents it.

Synthesis

Branching Factor is the local fan-out measure of search procedures that, together with search depth, controls the combinatorial explosion of nodes; it is both algorithm- and instance-dependent and central to runtime predictions.