diff --git a/java/src/com/android/inputmethod/latin/BinaryDictionary.java b/java/src/com/android/inputmethod/latin/BinaryDictionary.java
index 42105e2..7807305 100644
--- a/java/src/com/android/inputmethod/latin/BinaryDictionary.java
+++ b/java/src/com/android/inputmethod/latin/BinaryDictionary.java
@@ -259,9 +259,8 @@
         }
         final DicTraverseSession session = getTraverseSession(sessionId);
         Arrays.fill(session.mInputCodePoints, Constants.NOT_A_CODE);
-        // TODO: toLowerCase in the native code
-        final int[] prevWordCodePointArray = (null == prevWordsInfo.mPrevWord)
-                ? null : StringUtils.toCodePointArray(prevWordsInfo.mPrevWord);
+        prevWordsInfo.outputToArray(session.mPrevWordCodePointArrays,
+                session.mIsBeginningOfSentenceArray);
         final InputPointers inputPointers = composer.getInputPointers();
         final boolean isGesture = composer.isBatchMode();
         final int inputSize;
@@ -283,13 +282,13 @@
         } else {
             session.mInputOutputLanguageWeight[0] = Dictionary.NOT_A_LANGUAGE_WEIGHT;
         }
-        // proximityInfo and/or prevWordForBigrams may not be null.
+        // TOOD: Pass multiple previous words information for n-gram.
         getSuggestionsNative(mNativeDict, proximityInfo.getNativeProximityInfo(),
                 getTraverseSession(sessionId).getSession(), inputPointers.getXCoordinates(),
                 inputPointers.getYCoordinates(), inputPointers.getTimes(),
                 inputPointers.getPointerIds(), session.mInputCodePoints, inputSize,
-                session.mNativeSuggestOptions.getOptions(), prevWordCodePointArray,
-                prevWordsInfo.mIsBeginningOfSentence, session.mOutputSuggestionCount,
+                session.mNativeSuggestOptions.getOptions(), session.mPrevWordCodePointArrays[0],
+                session.mIsBeginningOfSentenceArray[0], session.mOutputSuggestionCount,
                 session.mOutputCodePoints, session.mOutputScores, session.mSpaceIndices,
                 session.mOutputTypes, session.mOutputAutoCommitFirstWordConfidence,
                 session.mInputOutputLanguageWeight);
@@ -352,10 +351,13 @@
         if (!prevWordsInfo.isValid() || TextUtils.isEmpty(word)) {
             return NOT_A_PROBABILITY;
         }
-        final int[] codePoints0 = StringUtils.toCodePointArray(prevWordsInfo.mPrevWord);
-        final int[] codePoints1 = StringUtils.toCodePointArray(word);
-        return getBigramProbabilityNative(mNativeDict, codePoints0,
-                prevWordsInfo.mIsBeginningOfSentence, codePoints1);
+        final int[][] prevWordCodePointArrays = new int[Constants.MAX_PREV_WORD_COUNT_FOR_N_GRAM][];
+        final boolean[] isBeginningOfSentenceArray =
+                new boolean[Constants.MAX_PREV_WORD_COUNT_FOR_N_GRAM];
+        prevWordsInfo.outputToArray(prevWordCodePointArrays, isBeginningOfSentenceArray);
+        final int[] wordCodePoints = StringUtils.toCodePointArray(word);
+        return getBigramProbabilityNative(mNativeDict, prevWordCodePointArrays[0],
+                isBeginningOfSentenceArray[0], wordCodePoints);
     }
 
     public WordProperty getWordProperty(final String word) {
@@ -442,10 +444,13 @@
         if (!prevWordsInfo.isValid() || TextUtils.isEmpty(word)) {
             return false;
         }
-        final int[] codePoints0 = StringUtils.toCodePointArray(prevWordsInfo.mPrevWord);
-        final int[] codePoints1 = StringUtils.toCodePointArray(word);
-        if (!addBigramWordsNative(mNativeDict, codePoints0, prevWordsInfo.mIsBeginningOfSentence,
-                codePoints1, probability, timestamp)) {
+        final int[][] prevWordCodePointArrays = new int[Constants.MAX_PREV_WORD_COUNT_FOR_N_GRAM][];
+        final boolean[] isBeginningOfSentenceArray =
+                new boolean[Constants.MAX_PREV_WORD_COUNT_FOR_N_GRAM];
+        prevWordsInfo.outputToArray(prevWordCodePointArrays, isBeginningOfSentenceArray);
+        final int[] wordCodePoints = StringUtils.toCodePointArray(word);
+        if (!addBigramWordsNative(mNativeDict, prevWordCodePointArrays[0],
+                isBeginningOfSentenceArray[0], wordCodePoints, probability, timestamp)) {
             return false;
         }
         mHasUpdated = true;
@@ -457,10 +462,13 @@
         if (!prevWordsInfo.isValid() || TextUtils.isEmpty(word)) {
             return false;
         }
-        final int[] codePoints0 = StringUtils.toCodePointArray(prevWordsInfo.mPrevWord);
-        final int[] codePoints1 = StringUtils.toCodePointArray(word);
-        if (!removeBigramWordsNative(mNativeDict, codePoints0, prevWordsInfo.mIsBeginningOfSentence,
-                codePoints1)) {
+        final int[][] prevWordCodePointArrays = new int[Constants.MAX_PREV_WORD_COUNT_FOR_N_GRAM][];
+        final boolean[] isBeginningOfSentenceArray =
+                new boolean[Constants.MAX_PREV_WORD_COUNT_FOR_N_GRAM];
+        prevWordsInfo.outputToArray(prevWordCodePointArrays, isBeginningOfSentenceArray);
+        final int[] wordCodePoints = StringUtils.toCodePointArray(word);
+        if (!removeBigramWordsNative(mNativeDict, prevWordCodePointArrays[0],
+                isBeginningOfSentenceArray[0], wordCodePoints)) {
             return false;
         }
         mHasUpdated = true;
diff --git a/java/src/com/android/inputmethod/latin/Constants.java b/java/src/com/android/inputmethod/latin/Constants.java
index f933936..b4e115c 100644
--- a/java/src/com/android/inputmethod/latin/Constants.java
+++ b/java/src/com/android/inputmethod/latin/Constants.java
@@ -166,6 +166,10 @@
     // Must be equal to MAX_WORD_LENGTH in native/jni/src/defines.h
     public static final int DICTIONARY_MAX_WORD_LENGTH = 48;
 
+    // (MAX_PREV_WORD_COUNT_FOR_N_GRAM + 1)-gram is supported in Java side. Needs to modify
+    // MAX_PREV_WORD_COUNT_FOR_N_GRAM in native/jni/src/defines.h for suggestions.
+    public static final int MAX_PREV_WORD_COUNT_FOR_N_GRAM = 2;
+
     // Key events coming any faster than this are long-presses.
     public static final int LONG_PRESS_MILLISECONDS = 200;
     // TODO: Set this value appropriately.
diff --git a/java/src/com/android/inputmethod/latin/ContactsBinaryDictionary.java b/java/src/com/android/inputmethod/latin/ContactsBinaryDictionary.java
index 96160fa..ad14c06 100644
--- a/java/src/com/android/inputmethod/latin/ContactsBinaryDictionary.java
+++ b/java/src/com/android/inputmethod/latin/ContactsBinaryDictionary.java
@@ -233,19 +233,19 @@
                 final int wordLen = StringUtils.codePointCount(word);
                 if (wordLen < MAX_WORD_LENGTH && wordLen > 1) {
                     if (DEBUG) {
-                        Log.d(TAG, "addName " + name + ", " + word + ", "
-                                + prevWordsInfo.mPrevWord);
+                        Log.d(TAG, "addName " + name + ", " + word + ", "  + prevWordsInfo);
                     }
                     runGCIfRequiredLocked(true /* mindsBlockByGC */);
                     addUnigramLocked(word, FREQUENCY_FOR_CONTACTS,
                             null /* shortcut */, 0 /* shortcutFreq */, false /* isNotAWord */,
                             false /* isBlacklisted */, BinaryDictionary.NOT_A_VALID_TIMESTAMP);
-                    if (!TextUtils.isEmpty(prevWordsInfo.mPrevWord) && mUseFirstLastBigrams) {
+                    if (!prevWordsInfo.isValid() && mUseFirstLastBigrams) {
                         runGCIfRequiredLocked(true /* mindsBlockByGC */);
                         addNgramEntryLocked(prevWordsInfo, word, FREQUENCY_FOR_CONTACTS_BIGRAM,
                                 BinaryDictionary.NOT_A_VALID_TIMESTAMP);
                     }
-                    prevWordsInfo = new PrevWordsInfo(word);
+                    prevWordsInfo = prevWordsInfo.getNextPrevWordsInfo(
+                            new PrevWordsInfo.WordInfo(word));
                 }
             }
         }
diff --git a/java/src/com/android/inputmethod/latin/DicTraverseSession.java b/java/src/com/android/inputmethod/latin/DicTraverseSession.java
index 8bbf426..b341f62 100644
--- a/java/src/com/android/inputmethod/latin/DicTraverseSession.java
+++ b/java/src/com/android/inputmethod/latin/DicTraverseSession.java
@@ -28,6 +28,10 @@
     // Must be equal to MAX_RESULTS in native/jni/src/defines.h
     private static final int MAX_RESULTS = 18;
     public final int[] mInputCodePoints = new int[Constants.DICTIONARY_MAX_WORD_LENGTH];
+    public final int[][] mPrevWordCodePointArrays =
+            new int[Constants.MAX_PREV_WORD_COUNT_FOR_N_GRAM][];
+    public final boolean[] mIsBeginningOfSentenceArray =
+            new boolean[Constants.MAX_PREV_WORD_COUNT_FOR_N_GRAM];
     public final int[] mOutputSuggestionCount = new int[1];
     public final int[] mOutputCodePoints =
             new int[Constants.DICTIONARY_MAX_WORD_LENGTH * MAX_RESULTS];
diff --git a/java/src/com/android/inputmethod/latin/DictionaryFacilitator.java b/java/src/com/android/inputmethod/latin/DictionaryFacilitator.java
index 8c4870d..2f1aca6 100644
--- a/java/src/com/android/inputmethod/latin/DictionaryFacilitator.java
+++ b/java/src/com/android/inputmethod/latin/DictionaryFacilitator.java
@@ -23,6 +23,7 @@
 
 import com.android.inputmethod.annotations.UsedForTesting;
 import com.android.inputmethod.keyboard.ProximityInfo;
+import com.android.inputmethod.latin.PrevWordsInfo.WordInfo;
 import com.android.inputmethod.latin.SuggestedWords.SuggestedWordInfo;
 import com.android.inputmethod.latin.personalization.ContextualDictionary;
 import com.android.inputmethod.latin.personalization.PersonalizationDataChunk;
@@ -407,13 +408,14 @@
             final boolean blockPotentiallyOffensive) {
         final Dictionaries dictionaries = mDictionaries;
         final String[] words = suggestion.split(Constants.WORD_SEPARATOR);
+        PrevWordsInfo prevWordsInfoForCurrentWord = prevWordsInfo;
         for (int i = 0; i < words.length; i++) {
             final String currentWord = words[i];
-            final PrevWordsInfo prevWordsInfoForCurrentWord =
-                    (i == 0) ? prevWordsInfo : new PrevWordsInfo(words[i - 1]);
             final boolean wasCurrentWordAutoCapitalized = (i == 0) ? wasAutoCapitalized : false;
             addWordToUserHistory(dictionaries, prevWordsInfoForCurrentWord, currentWord,
                     wasCurrentWordAutoCapitalized, timeStampInSeconds, blockPotentiallyOffensive);
+            prevWordsInfoForCurrentWord =
+                    prevWordsInfoForCurrentWord.getNextPrevWordsInfo(new WordInfo(currentWord));
         }
     }
 
@@ -647,7 +649,8 @@
                 contextualDict.addNgramEntry(prevWordsInfo, phrase[i],
                         bigramProbabilityForWords, BinaryDictionary.NOT_A_VALID_TIMESTAMP);
             }
-            prevWordsInfo = new PrevWordsInfo(phrase[i]);
+            prevWordsInfo =
+                    prevWordsInfo.getNextPrevWordsInfo(new PrevWordsInfo.WordInfo(phrase[i]));
         }
     }
 
diff --git a/java/src/com/android/inputmethod/latin/ExpandableBinaryDictionary.java b/java/src/com/android/inputmethod/latin/ExpandableBinaryDictionary.java
index 6199c7d..1884e41 100644
--- a/java/src/com/android/inputmethod/latin/ExpandableBinaryDictionary.java
+++ b/java/src/com/android/inputmethod/latin/ExpandableBinaryDictionary.java
@@ -426,10 +426,6 @@
                 if (mBinaryDictionary == null) {
                     return null;
                 }
-                if (composer.size() == 0 && prevWordsInfo.mIsBeginningOfSentence
-                        && !enableBeginningOfSentencePrediction()) {
-                    return null;
-                }
                 final ArrayList<SuggestedWordInfo> suggestions =
                         mBinaryDictionary.getSuggestions(composer, prevWordsInfo, proximityInfo,
                                 blockOffensiveWords, additionalFeaturesOptions, sessionId,
diff --git a/java/src/com/android/inputmethod/latin/PrevWordsInfo.java b/java/src/com/android/inputmethod/latin/PrevWordsInfo.java
index 42b311c..5dda444 100644
--- a/java/src/com/android/inputmethod/latin/PrevWordsInfo.java
+++ b/java/src/com/android/inputmethod/latin/PrevWordsInfo.java
@@ -16,47 +16,122 @@
 
 package com.android.inputmethod.latin;
 
+import java.util.Arrays;
+
+import com.android.inputmethod.latin.utils.StringUtils;
+
 /**
  * Class to represent information of previous words. This class is used to add n-gram entries
  * into binary dictionaries, to get predictions, and to get suggestions.
  */
-// TODO: Support multiple previous words for n-gram.
 public class PrevWordsInfo {
-    public static final PrevWordsInfo EMPTY_PREV_WORDS_INFO = new PrevWordsInfo(null);
+    public static final PrevWordsInfo EMPTY_PREV_WORDS_INFO =
+            new PrevWordsInfo(WordInfo.EMPTY_WORD_INFO);
     public static final PrevWordsInfo BEGINNING_OF_SENTENCE = new PrevWordsInfo();
 
-    // The word immediately before the considered word. null means we don't have any context
-    // including the "beginning of sentence context" - we just don't know what to predict.
-    // An example of that is after a comma.
-    // For simplicity of implementation, this may also be null transiently after the WordComposer
-    // was reset and before starting a new composing word, but we should never be calling
-    // getSuggetions* in this situation.
-    // This is an empty string when mIsBeginningOfSentence is true.
-    public final String mPrevWord;
+    /**
+     * Word information used to represent previous words information.
+     */
+    public static class WordInfo {
+        public static final WordInfo EMPTY_WORD_INFO = new WordInfo(null);
+        public static final WordInfo BEGINNING_OF_SENTENCE = new WordInfo();
 
-    // TODO: Have sentence separator.
-    // Whether the current context is beginning of sentence or not. This is true when composing at
-    // the beginning of an input field or composing a word after a sentence separator.
-    public final boolean mIsBeginningOfSentence;
+        // This is an empty string when mIsBeginningOfSentence is true.
+        public final String mWord;
+        // TODO: Have sentence separator.
+        // Whether the current context is beginning of sentence or not. This is true when composing
+        // at the beginning of an input field or composing a word after a sentence separator.
+        public final boolean mIsBeginningOfSentence;
+
+        // Beginning of sentence.
+        public WordInfo() {
+            mWord = "";
+            mIsBeginningOfSentence = true;
+        }
+
+        public WordInfo(final String word) {
+            mWord = word;
+            mIsBeginningOfSentence = false;
+        }
+
+        public boolean isValid() {
+            return mWord != null;
+        }
+    }
+
+    // The words immediately before the considered word. EMPTY_WORD_INFO element means we don't
+    // have any context for that previous word including the "beginning of sentence context" - we
+    // just don't know what to predict using the information. An example of that is after a comma.
+    // For simplicity of implementation, elements may also be EMPTY_WORD_INFO transiently after the
+    // WordComposer was reset and before starting a new composing word, but we should never be
+    // calling getSuggetions* in this situation.
+    public WordInfo[] mPrevWordsInfo = new WordInfo[Constants.MAX_PREV_WORD_COUNT_FOR_N_GRAM];
 
     // Beginning of sentence.
     public PrevWordsInfo() {
-        mPrevWord = "";
-        mIsBeginningOfSentence = true;
+        mPrevWordsInfo[0] = WordInfo.BEGINNING_OF_SENTENCE;
+        Arrays.fill(mPrevWordsInfo, 1 /* start */, mPrevWordsInfo.length, WordInfo.EMPTY_WORD_INFO);
     }
 
-    public PrevWordsInfo(final String prevWord) {
-        mPrevWord = prevWord;
-        mIsBeginningOfSentence = false;
+    // Construct from the previous word information.
+    public PrevWordsInfo(final WordInfo prevWordInfo) {
+        mPrevWordsInfo[0] = prevWordInfo;
+        Arrays.fill(mPrevWordsInfo, 1 /* start */, mPrevWordsInfo.length, WordInfo.EMPTY_WORD_INFO);
+    }
+
+    // Construct from WordInfo array. n-th element represents (n+1)-th previous word's information.
+    public PrevWordsInfo(final WordInfo[] prevWordsInfo) {
+        for (int i = 0; i < Constants.MAX_PREV_WORD_COUNT_FOR_N_GRAM; i++) {
+            mPrevWordsInfo[i] =
+                    (prevWordsInfo.length > i) ? prevWordsInfo[i] : WordInfo.EMPTY_WORD_INFO;
+        }
+    }
+
+    // Create next prevWordsInfo using current prevWordsInfo.
+    public PrevWordsInfo getNextPrevWordsInfo(final WordInfo wordInfo) {
+        final WordInfo[] prevWordsInfo = new WordInfo[Constants.MAX_PREV_WORD_COUNT_FOR_N_GRAM];
+        prevWordsInfo[0] = wordInfo;
+        for (int i = 1; i < prevWordsInfo.length; i++) {
+            prevWordsInfo[i] = mPrevWordsInfo[i - 1];
+        }
+        return new PrevWordsInfo(prevWordsInfo);
     }
 
     public boolean isValid() {
-        return mPrevWord != null;
+        return mPrevWordsInfo[0].isValid();
+    }
+
+    public void outputToArray(final int[][] codePointArrays,
+            final boolean[] isBeginningOfSentenceArray) {
+        for (int i = 0; i < mPrevWordsInfo.length; i++) {
+            final WordInfo wordInfo = mPrevWordsInfo[i];
+            if (wordInfo == null || !wordInfo.isValid()) {
+                codePointArrays[i] = new int[0];
+                isBeginningOfSentenceArray[i] = false;
+                continue;
+            }
+            codePointArrays[i] = StringUtils.toCodePointArray(wordInfo.mWord);
+            isBeginningOfSentenceArray[i] = wordInfo.mIsBeginningOfSentence;
+        }
     }
 
     @Override
     public String toString() {
-        return "PrevWord: " + mPrevWord + ", isBeginningOfSentence: "
-                    + mIsBeginningOfSentence + ".";
+        final StringBuffer builder = new StringBuffer();
+        for (int i = 0; i < mPrevWordsInfo.length; i++) {
+            final WordInfo wordInfo = mPrevWordsInfo[i];
+            builder.append("PrevWord[");
+            builder.append(i);
+            builder.append("]: ");
+            if (!wordInfo.isValid()) {
+                builder.append("Empty. ");
+                continue;
+            }
+            builder.append(wordInfo.mWord);
+            builder.append(", isBeginningOfSentence: ");
+            builder.append(wordInfo.mIsBeginningOfSentence);
+            builder.append(". ");
+        }
+        return builder.toString();
     }
 }
diff --git a/java/src/com/android/inputmethod/latin/RichInputConnection.java b/java/src/com/android/inputmethod/latin/RichInputConnection.java
index 96476b2..3be6bcc 100644
--- a/java/src/com/android/inputmethod/latin/RichInputConnection.java
+++ b/java/src/com/android/inputmethod/latin/RichInputConnection.java
@@ -603,7 +603,7 @@
                 || spacingAndPunctuations.isWordConnector(lastChar)) {
             return PrevWordsInfo.EMPTY_PREV_WORDS_INFO;
         }
-        return new PrevWordsInfo(nthPrevWord);
+        return new PrevWordsInfo(new PrevWordsInfo.WordInfo(nthPrevWord));
     }
 
     /**
diff --git a/java/src/com/android/inputmethod/latin/inputlogic/InputLogic.java b/java/src/com/android/inputmethod/latin/inputlogic/InputLogic.java
index 9462c38..32c6942 100644
--- a/java/src/com/android/inputmethod/latin/inputlogic/InputLogic.java
+++ b/java/src/com/android/inputmethod/latin/inputlogic/InputLogic.java
@@ -1528,7 +1528,8 @@
         } else {
             return LastComposedWord.NOT_A_COMPOSED_WORD == mLastComposedWord ?
                     PrevWordsInfo.BEGINNING_OF_SENTENCE :
-                            new PrevWordsInfo(mLastComposedWord.mCommittedWord.toString());
+                            new PrevWordsInfo(new PrevWordsInfo.WordInfo(
+                                    mLastComposedWord.mCommittedWord.toString()));
         }
     }
 
diff --git a/java/src/com/android/inputmethod/latin/personalization/UserHistoryDictionary.java b/java/src/com/android/inputmethod/latin/personalization/UserHistoryDictionary.java
index 3916fc2..aede003 100644
--- a/java/src/com/android/inputmethod/latin/personalization/UserHistoryDictionary.java
+++ b/java/src/com/android/inputmethod/latin/personalization/UserHistoryDictionary.java
@@ -60,7 +60,7 @@
     public static void addToDictionary(final ExpandableBinaryDictionary userHistoryDictionary,
             final PrevWordsInfo prevWordsInfo, final String word, final boolean isValid,
             final int timestamp, final DistracterFilter distracterFilter) {
-        final String prevWord = prevWordsInfo.mPrevWord;
+        final String prevWord = prevWordsInfo.mPrevWordsInfo[0].mWord;
         if (word.length() >= Constants.DICTIONARY_MAX_WORD_LENGTH ||
                 (prevWord != null && prevWord.length() >= Constants.DICTIONARY_MAX_WORD_LENGTH)) {
             return;
diff --git a/java/src/com/android/inputmethod/latin/spellcheck/AndroidSpellCheckerSession.java b/java/src/com/android/inputmethod/latin/spellcheck/AndroidSpellCheckerSession.java
index 55274cf..6bfd354 100644
--- a/java/src/com/android/inputmethod/latin/spellcheck/AndroidSpellCheckerSession.java
+++ b/java/src/com/android/inputmethod/latin/spellcheck/AndroidSpellCheckerSession.java
@@ -61,7 +61,8 @@
             final int offset = ssi.getOffsetAt(i);
             final int length = ssi.getLengthAt(i);
             final String subText = typedText.substring(offset, offset + length);
-            final PrevWordsInfo prevWordsInfo = new PrevWordsInfo(currentWord);
+            final PrevWordsInfo prevWordsInfo =
+                    new PrevWordsInfo(new PrevWordsInfo.WordInfo(currentWord));
             currentWord = subText;
             if (!subText.contains(AndroidSpellCheckerService.SINGLE_QUOTE)) {
                 continue;
@@ -203,7 +204,8 @@
                 } else {
                     prevWord = null;
                 }
-                final PrevWordsInfo prevWordsInfo = new PrevWordsInfo(prevWord);
+                final PrevWordsInfo prevWordsInfo =
+                        new PrevWordsInfo(new PrevWordsInfo.WordInfo(prevWord));
                 retval[i] = onGetSuggestionsInternal(textInfos[i], prevWordsInfo, suggestionsLimit);
                 retval[i].setCookieAndSequence(textInfos[i].getCookie(),
                         textInfos[i].getSequence());
diff --git a/java/src/com/android/inputmethod/latin/spellcheck/AndroidWordLevelSpellCheckerSession.java b/java/src/com/android/inputmethod/latin/spellcheck/AndroidWordLevelSpellCheckerSession.java
index 54eebe3..e9d5a7a 100644
--- a/java/src/com/android/inputmethod/latin/spellcheck/AndroidWordLevelSpellCheckerSession.java
+++ b/java/src/com/android/inputmethod/latin/spellcheck/AndroidWordLevelSpellCheckerSession.java
@@ -72,10 +72,10 @@
 
         // TODO: Support n-gram input
         private static String generateKey(final String query, final PrevWordsInfo prevWordsInfo) {
-            if (TextUtils.isEmpty(query) || TextUtils.isEmpty(prevWordsInfo.mPrevWord)) {
+            if (TextUtils.isEmpty(query) || !prevWordsInfo.isValid()) {
                 return query;
             }
-            return query + CHAR_DELIMITER + prevWordsInfo.mPrevWord;
+            return query + CHAR_DELIMITER + prevWordsInfo;
         }
 
         public SuggestionsParams getSuggestionsFromCache(String query,
diff --git a/java/src/com/android/inputmethod/latin/utils/LanguageModelParam.java b/java/src/com/android/inputmethod/latin/utils/LanguageModelParam.java
index 4248beb..9ec19ef 100644
--- a/java/src/com/android/inputmethod/latin/utils/LanguageModelParam.java
+++ b/java/src/com/android/inputmethod/latin/utils/LanguageModelParam.java
@@ -117,7 +117,8 @@
                 continue;
             }
             languageModelParams.add(languageModelParam);
-            prevWordsInfo = new PrevWordsInfo(languageModelParam.mTargetWord);
+            prevWordsInfo = prevWordsInfo.getNextPrevWordsInfo(
+                    new PrevWordsInfo.WordInfo(tempWord));
         }
         return languageModelParams;
     }
@@ -153,7 +154,7 @@
             final DistracterFilter distracterFilter) {
         final String word;
         if (StringUtils.getCapitalizationType(targetWord) == StringUtils.CAPITALIZE_FIRST
-                && prevWordsInfo.mPrevWord == null && !isValidWord) {
+                && !prevWordsInfo.isValid() && !isValidWord) {
             word = targetWord.toLowerCase(locale);
         } else {
             word = targetWord;
@@ -167,7 +168,7 @@
         }
         final int unigramProbability = isValidWord ?
                 UNIGRAM_PROBABILITY_FOR_VALID_WORD : UNIGRAM_PROBABILITY_FOR_OOV_WORD;
-        if (prevWordsInfo.mPrevWord == null) {
+        if (!prevWordsInfo.isValid()) {
             if (DEBUG) {
                 Log.d(TAG, "--- add unigram: current("
                         + (isValidWord ? "Valid" : "OOV") + ") = " + word);
@@ -175,12 +176,12 @@
             return new LanguageModelParam(word, unigramProbability, timestamp);
         }
         if (DEBUG) {
-            Log.d(TAG, "--- add bigram: prev = " + prevWordsInfo.mPrevWord + ", current("
+            Log.d(TAG, "--- add bigram: prev = " + prevWordsInfo + ", current("
                     + (isValidWord ? "Valid" : "OOV") + ") = " + word);
         }
         final int bigramProbability = isValidWord ?
                 BIGRAM_PROBABILITY_FOR_VALID_WORD : BIGRAM_PROBABILITY_FOR_OOV_WORD;
-        return new LanguageModelParam(prevWordsInfo.mPrevWord, word, unigramProbability,
-                bigramProbability, timestamp);
+        return new LanguageModelParam(prevWordsInfo.mPrevWordsInfo[0].mWord, word,
+                unigramProbability, bigramProbability, timestamp);
     }
 }
diff --git a/tests/src/com/android/inputmethod/latin/BinaryDictionaryDecayingTests.java b/tests/src/com/android/inputmethod/latin/BinaryDictionaryDecayingTests.java
index 28cce83..ae18426 100644
--- a/tests/src/com/android/inputmethod/latin/BinaryDictionaryDecayingTests.java
+++ b/tests/src/com/android/inputmethod/latin/BinaryDictionaryDecayingTests.java
@@ -20,6 +20,7 @@
 import android.test.suitebuilder.annotation.LargeTest;
 import android.util.Pair;
 
+import com.android.inputmethod.latin.PrevWordsInfo.WordInfo;
 import com.android.inputmethod.latin.makedict.BinaryDictIOUtils;
 import com.android.inputmethod.latin.makedict.CodePointUtils;
 import com.android.inputmethod.latin.makedict.DictDecoder;
@@ -77,13 +78,13 @@
 
     private void addBigramWords(final BinaryDictionary binaryDictionary, final String word0,
             final String word1, final int probability) {
-        binaryDictionary.addNgramEntry(new PrevWordsInfo(word0), word1, probability,
+        binaryDictionary.addNgramEntry(new PrevWordsInfo(new WordInfo(word0)), word1, probability,
                 mCurrentTime /* timestamp */);
     }
 
     private static boolean isValidBigram(final BinaryDictionary binaryDictionary,
             final String word0, final String word1) {
-        return binaryDictionary.isValidNgram(new PrevWordsInfo(word0), word1);
+        return binaryDictionary.isValidNgram(new PrevWordsInfo(new WordInfo(word0)), word1);
     }
 
     private void forcePassingShortTime(final BinaryDictionary binaryDictionary) {
diff --git a/tests/src/com/android/inputmethod/latin/BinaryDictionaryTests.java b/tests/src/com/android/inputmethod/latin/BinaryDictionaryTests.java
index 160b08c..fbce9a8 100644
--- a/tests/src/com/android/inputmethod/latin/BinaryDictionaryTests.java
+++ b/tests/src/com/android/inputmethod/latin/BinaryDictionaryTests.java
@@ -21,6 +21,7 @@
 import android.text.TextUtils;
 import android.util.Pair;
 
+import com.android.inputmethod.latin.PrevWordsInfo.WordInfo;
 import com.android.inputmethod.latin.makedict.CodePointUtils;
 import com.android.inputmethod.latin.makedict.FormatSpec;
 import com.android.inputmethod.latin.makedict.WeightedString;
@@ -203,23 +204,23 @@
 
     private static void addBigramWords(final BinaryDictionary binaryDictionary, final String word0,
             final String word1, final int probability) {
-        binaryDictionary.addNgramEntry(new PrevWordsInfo(word0), word1, probability,
+        binaryDictionary.addNgramEntry(new PrevWordsInfo(new WordInfo(word0)), word1, probability,
                 BinaryDictionary.NOT_A_VALID_TIMESTAMP /* timestamp */);
     }
 
     private static boolean isValidBigram(final BinaryDictionary binaryDictionary,
             final String word0, final String word1) {
-        return binaryDictionary.isValidNgram(new PrevWordsInfo(word0), word1);
+        return binaryDictionary.isValidNgram(new PrevWordsInfo(new WordInfo(word0)), word1);
     }
 
     private static void removeBigramEntry(final BinaryDictionary binaryDictionary,
             final String word0, final String word1) {
-        binaryDictionary.removeNgramEntry(new PrevWordsInfo(word0), word1);
+        binaryDictionary.removeNgramEntry(new PrevWordsInfo(new WordInfo(word0)), word1);
     }
 
     private static int getBigramProbability(final BinaryDictionary binaryDictionary,
             final String word0,  final String word1) {
-        return binaryDictionary.getNgramProbability(new PrevWordsInfo(word0), word1);
+        return binaryDictionary.getNgramProbability(new PrevWordsInfo(new WordInfo(word0)), word1);
     }
 
     public void testAddUnigramWord() {
diff --git a/tests/src/com/android/inputmethod/latin/RichInputConnectionAndTextRangeTests.java b/tests/src/com/android/inputmethod/latin/RichInputConnectionAndTextRangeTests.java
index 2c92bb3..5a5ec6d 100644
--- a/tests/src/com/android/inputmethod/latin/RichInputConnectionAndTextRangeTests.java
+++ b/tests/src/com/android/inputmethod/latin/RichInputConnectionAndTextRangeTests.java
@@ -156,16 +156,16 @@
     public void testGetPreviousWord() {
         // If one of the following cases breaks, the bigram suggestions won't work.
         assertEquals(RichInputConnection.getPrevWordsInfoFromNthPreviousWord(
-                "abc def", mSpacingAndPunctuations, 2).mPrevWord, "abc");
+                "abc def", mSpacingAndPunctuations, 2).mPrevWordsInfo[0].mWord, "abc");
         assertEquals(RichInputConnection.getPrevWordsInfoFromNthPreviousWord(
                 "abc", mSpacingAndPunctuations, 2), PrevWordsInfo.BEGINNING_OF_SENTENCE);
         assertEquals(RichInputConnection.getPrevWordsInfoFromNthPreviousWord(
                 "abc. def", mSpacingAndPunctuations, 2), PrevWordsInfo.BEGINNING_OF_SENTENCE);
 
         assertFalse(RichInputConnection.getPrevWordsInfoFromNthPreviousWord(
-                "abc def", mSpacingAndPunctuations, 2).mIsBeginningOfSentence);
+                "abc def", mSpacingAndPunctuations, 2).mPrevWordsInfo[0].mIsBeginningOfSentence);
         assertTrue(RichInputConnection.getPrevWordsInfoFromNthPreviousWord(
-                "abc", mSpacingAndPunctuations, 2).mIsBeginningOfSentence);
+                "abc", mSpacingAndPunctuations, 2).mPrevWordsInfo[0].mIsBeginningOfSentence);
         // The following tests reflect the current behavior of the function
         // RichInputConnection#getNthPreviousWord.
         // TODO: However at this time, the code does never go
@@ -174,20 +174,20 @@
         // logical. These tests are just there to catch any unintentional
         // changes in the behavior of the RichInputConnection#getPreviousWord method.
         assertEquals(RichInputConnection.getPrevWordsInfoFromNthPreviousWord(
-                "abc def ", mSpacingAndPunctuations, 2).mPrevWord, "abc");
+                "abc def ", mSpacingAndPunctuations, 2).mPrevWordsInfo[0].mWord, "abc");
         assertEquals(RichInputConnection.getPrevWordsInfoFromNthPreviousWord(
-                "abc def.", mSpacingAndPunctuations, 2).mPrevWord, "abc");
+                "abc def.", mSpacingAndPunctuations, 2).mPrevWordsInfo[0].mWord, "abc");
         assertEquals(RichInputConnection.getPrevWordsInfoFromNthPreviousWord(
-                "abc def .", mSpacingAndPunctuations, 2).mPrevWord, "def");
+                "abc def .", mSpacingAndPunctuations, 2).mPrevWordsInfo[0].mWord, "def");
         assertEquals(RichInputConnection.getPrevWordsInfoFromNthPreviousWord(
                 "abc ", mSpacingAndPunctuations, 2), PrevWordsInfo.BEGINNING_OF_SENTENCE);
 
         assertEquals(RichInputConnection.getPrevWordsInfoFromNthPreviousWord(
-                "abc def", mSpacingAndPunctuations, 1).mPrevWord, "def");
+                "abc def", mSpacingAndPunctuations, 1).mPrevWordsInfo[0].mWord, "def");
         assertEquals(RichInputConnection.getPrevWordsInfoFromNthPreviousWord(
-                "abc def ", mSpacingAndPunctuations, 1).mPrevWord, "def");
+                "abc def ", mSpacingAndPunctuations, 1).mPrevWordsInfo[0].mWord, "def");
         assertEquals(RichInputConnection.getPrevWordsInfoFromNthPreviousWord(
-                "abc 'def", mSpacingAndPunctuations, 1).mPrevWord, "'def");
+                "abc 'def", mSpacingAndPunctuations, 1).mPrevWordsInfo[0].mWord, "'def");
         assertEquals(RichInputConnection.getPrevWordsInfoFromNthPreviousWord(
                 "abc def.", mSpacingAndPunctuations, 1), PrevWordsInfo.BEGINNING_OF_SENTENCE);
         assertEquals(RichInputConnection.getPrevWordsInfoFromNthPreviousWord(
diff --git a/tests/src/com/android/inputmethod/latin/makedict/Ver4DictEncoder.java b/tests/src/com/android/inputmethod/latin/makedict/Ver4DictEncoder.java
index 8f32e53..76eaef4 100644
--- a/tests/src/com/android/inputmethod/latin/makedict/Ver4DictEncoder.java
+++ b/tests/src/com/android/inputmethod/latin/makedict/Ver4DictEncoder.java
@@ -104,7 +104,8 @@
         for (final WordProperty word0Property : dict) {
             if (null == word0Property.mBigrams) continue;
             for (final WeightedString word1 : word0Property.mBigrams) {
-                final PrevWordsInfo prevWordsInfo = new PrevWordsInfo(word0Property.mWord);
+                final PrevWordsInfo prevWordsInfo =
+                        new PrevWordsInfo(new PrevWordsInfo.WordInfo(word0Property.mWord));
                 if (!binaryDict.addNgramEntry(prevWordsInfo, word1.mWord,
                         word1.getProbability(), 0 /* timestamp */)) {
                     MakedictLog.e("Cannot add n-gram entry for "
diff --git a/tests/src/com/android/inputmethod/latin/personalization/UserHistoryDictionaryTests.java b/tests/src/com/android/inputmethod/latin/personalization/UserHistoryDictionaryTests.java
index 48d3a1c..f87f3b4 100644
--- a/tests/src/com/android/inputmethod/latin/personalization/UserHistoryDictionaryTests.java
+++ b/tests/src/com/android/inputmethod/latin/personalization/UserHistoryDictionaryTests.java
@@ -22,6 +22,7 @@
 
 import com.android.inputmethod.latin.ExpandableBinaryDictionary;
 import com.android.inputmethod.latin.PrevWordsInfo;
+import com.android.inputmethod.latin.PrevWordsInfo.WordInfo;
 import com.android.inputmethod.latin.utils.BinaryDictionaryUtils;
 import com.android.inputmethod.latin.utils.DistracterFilter;
 import com.android.inputmethod.latin.utils.FileUtils;
@@ -115,7 +116,7 @@
             UserHistoryDictionary.addToDictionary(dict, prevWordsInfo, word, true,
                     (int)TimeUnit.MILLISECONDS.toSeconds(System.currentTimeMillis()),
                     DistracterFilter.EMPTY_DISTRACTER_FILTER);
-            prevWordsInfo = new PrevWordsInfo(word);
+            prevWordsInfo = prevWordsInfo.getNextPrevWordsInfo(new WordInfo(word));
         }
     }
 
@@ -262,11 +263,11 @@
         final UserHistoryDictionary dict =
                 PersonalizationHelper.getUserHistoryDictionary(getContext(), dummyLocale);
         dict.waitAllTasksForTests();
-        PrevWordsInfo prevWordsInfo = new PrevWordsInfo(null);
+        PrevWordsInfo prevWordsInfo = PrevWordsInfo.EMPTY_PREV_WORDS_INFO;
         for (final String word : words) {
             UserHistoryDictionary.addToDictionary(dict, prevWordsInfo, word, true, mCurrentTime,
                     DistracterFilter.EMPTY_DISTRACTER_FILTER);
-            prevWordsInfo = new PrevWordsInfo(word);
+            prevWordsInfo = prevWordsInfo.getNextPrevWordsInfo(new WordInfo(word));
             dict.waitAllTasksForTests();
             assertTrue(dict.isInDictionary(word));
         }