Early prototype is best- from the dev perspective. Publishers want it to be as near complete (but not actually complete) as the developer can make it though. Basically the closer it is to done the better they can judge it. Also, if you’re new to the scene, publishers want to know you can get the work done, so the closer to complete the more they feel confident of that. If you’re not new and have a history of releases (even if they didnt sell well) that will likely put them at ease.
That said, publishers don’t have a huge role to play anymore, so when you go to them YOU need to be dictating what you need them for. Be specific and build it directly into the contract.