Are you logging your queries? If you have enough searches you could build your own predictions. You're also proxying results, so you could use those to build an index too.
E.g. if "in" often leads to instapaper, predict that, while if "ins" often eventually leads to "instantapp", that's the prediction for that prefix.