We call N-BRW a branching random walk subject to a "selection" procedure: at each generation, all particles which are not in the N highest of the process are removed. As N goes to infinity, the speed of its front is known to converge very slowly towards the speed of the BRW without selection, a phenomenon dubbed "Brunet-Derrida behavior". We aim to extend this result in two directions: first, we consider a N-BRW whose increments are time-inhomogeneous; second, we couple arbitrarily the number of particles N with the number of generations T of the walk. These extensions allow us to interpret the N-BRW as a "beam search" optimization algorithm on a random instance. We show that the maximal displacement of the time-inhomogeneous N-BRW is subject to a phase transition when log(N)~T^{1/3}. The "sub-critical regime" displays the Brunet-Derrida behavior; but in the "super-critical regime", the speed of the N-BRW grows even more slowly in N. In algorithmic terms, this shows that the beam search optimization algorithm on some random hierarchical dataset is subject to an "algorithmic hardness threshold" phenomenon, and we obtain sharp estimates of the output of the beam search around that threshold.