I've been looking for a reference for the above question.
As far as I know the answer is:
If we can make a solver that is efficient for all randomly generated instances, it should be efficient for any instance.
i.e. if we make a solver that doesnt rely on any inherent structure, it will always be efficient.
Is this correct? Either way, does anyone have a reference to a paper I can cite for the answer.
If your solver is efficient for random 3-SAT, it by no means entails that it is efficient for an arbitrary 3-SAT instance. Randomly generated instances are very different from instances that arise in practice (meaning they are structured differently). For instance, you can read about the phase transition in random $k$-SAT: depending on the clause-to-variable ratio, an instance can be easy (not constrained enough, or too constrained) or hard (in some sense critically constrained). This phenomenon is rather fascinating in itself.
You can always argue that if you have a solver that does not exploit any structure of the input and is always rather magically efficient, much of the theory we have developed around SAT is useless. Unfortunately, many people have worked a lot on the problem, and we are still unable to give an efficient algorithm for e.g. SAT (not to mention an algorithm that would be efficient in practice as well!). So how do we cope with this? We look at e.g. structural aspects of the input: what can we leverage? How can we be fast at least sometimes? Because we can't solve a problem we care about, we look for other approaches and angles of attack.
I think the main reasons we have been interested in random $k$-SAT is that first, such instances are easy to generate to test our solvers. We have also learned that random instances are very different from instances that arise in practice (and of course those are the instances we often care about). This has increased our understanding of the nature of computation, heuristics, complexity, and ultimately made us able to build faster solvers as well.
the other answer is good, here is a bit additional context & 2 papers as requested. the discovery of phase transitions in NP complete problems associated with random inputs was a striking scientific discovery at the time (mid 1990s), worthy of publication in a leading/ elite scientific journal, Science magazine, typically reserved for only very remarkable and cross-cutting discoveries by top scientists. phase transitions are normally seen/ studied mostly in physics and this discovery links theoretical physics areas such as thermodynamics theory with computer science theory, and is still being explored decades later, and there are now many dozens of papers on the subject. from Selmans own web site
another area where random inputs is now shown to play a significant role is in lower bounds proofs involving monotone circuits. Razborov won a TCS Nevanlinna prize for early work in this area now extended by Rossman.
another way to regard random inputs however is just more generally as one of the most basic input distributions that can be studied for statistical/ average case complexity, for any algorithm. for example with sorting algorithms and many others, an easy way to test them is with random inputs.
