> I do wonder how branch prediction actually works in the CPU, predicting which branch to take also seems like it should be expensive

There are a few hardware algorithms that are vendor-dependent. The earliest branch predictors were two-bit saturating counters that moved between four states of 'strongly taken', 'weakly taken', 'weakly not taken', 'strongly not taken', and the state change depended on the eventual computed result of the branch.

Newer branch predictors are stuff like two-level adaptive branch predictors that are a hardware `std::unordered_map` of branch instruction addresses to the above-mentioned saturating counters; this remembers the result of the last n (where n is the size of the map) branch instructions.

Ryzen CPUs contain perceptron branch predictors that are basically hardware neural networks—not far from LLMs.