How do you measure performance for word prediction tasks? Say I have to predict the next word in a sentence, given the initial few words. 

Suppose the prefix is "I went to _____". This prefix is common enough that it might appear 10 times in the training data with a few different variations:

I went to college: 5

I went to California: 3

I went to London: 2

In such a case, suppose my model predicts "college" as the right answer. It would still get only a 50% score if I used accuracy as a metric, the data naturally has multiple (correct) answers for the same input. How do I solve this?
Your accuracy should be this: Did the phrase existed before? It means either storing all combinations of 4-grams or searching the data on the fly.

But then the prediction algorithm that uses any combination from the previous data will be 100% accurate. I do not really understand the reason for such accuracy estimation.