The quantum approximate optimisation algorithm (QAOA) is one of the flagship algorithms used to tackle combinatorial optimisation on graphs problems using a quantum computer, and is considered a strong candidate for early fault-tolerant advantage. In this work, I study the enhancement of the QAOA with a generator coordinates method (GCM), and achieve systematic performances improvements in the approximation ratio and fidelity for the Maximum Independent Set on Erdös-Rényi graphs. The cost-to-solution of the present method and the QAOA are compared by analysing the number of logical CNOT and T gates required for either algorithm. Extrapolating on the numerical results obtained, it is estimated that for this specific problem and setup, the approach surpasses QAOA for graphs of size greater than 75 using as little as eight trial states.