Quadratic Sieve: what's the next step after it fails?
In the QS algorithm, every linear combination adding up to a zero vector modulo $2$ has a chance of $1/2$ to give you a nontrivial factor.

Your suggestion 2) is the way to go, because adding additional numbers provides you with a lot more different linear combinations to get that zero-vector ($\phi(b)+1$ is just the minimal number required to find at least one set of linear dependent vectors).