diff --git a/java/res/drawable-hdpi/sym_keyboard_settings_holo_dark.png b/java/res/drawable-hdpi/sym_keyboard_settings_holo_dark.png
index c76008a..5af09ad 100644
--- a/java/res/drawable-hdpi/sym_keyboard_settings_holo_dark.png
+++ b/java/res/drawable-hdpi/sym_keyboard_settings_holo_dark.png
Binary files differ
diff --git a/java/res/drawable-mdpi/sym_keyboard_settings_holo_dark.png b/java/res/drawable-mdpi/sym_keyboard_settings_holo_dark.png
index a76a976..36c8c96 100644
--- a/java/res/drawable-mdpi/sym_keyboard_settings_holo_dark.png
+++ b/java/res/drawable-mdpi/sym_keyboard_settings_holo_dark.png
Binary files differ
diff --git a/java/res/drawable-xhdpi/sym_keyboard_settings_holo_dark.png b/java/res/drawable-xhdpi/sym_keyboard_settings_holo_dark.png
index 05eaffe..99ee97d 100644
--- a/java/res/drawable-xhdpi/sym_keyboard_settings_holo_dark.png
+++ b/java/res/drawable-xhdpi/sym_keyboard_settings_holo_dark.png
Binary files differ
diff --git a/java/res/drawable-xxhdpi/sym_keyboard_settings_holo_dark.png b/java/res/drawable-xxhdpi/sym_keyboard_settings_holo_dark.png
index e435846..7041bb6 100644
--- a/java/res/drawable-xxhdpi/sym_keyboard_settings_holo_dark.png
+++ b/java/res/drawable-xxhdpi/sym_keyboard_settings_holo_dark.png
Binary files differ
diff --git a/java/res/values-sw600dp-land/dimens.xml b/java/res/values-sw600dp-land/dimens.xml
index d067265..d79e8ca 100644
--- a/java/res/values-sw600dp-land/dimens.xml
+++ b/java/res/values-sw600dp-land/dimens.xml
@@ -66,7 +66,7 @@
     <!-- Emoji keyboard -->
     <fraction name="emoji_keyboard_key_width">10%p</fraction>
     <fraction name="emoji_keyboard_row_height">33%p</fraction>
-    <fraction name="emoji_keyboard_key_letter_size">85%p</fraction>
+    <fraction name="emoji_keyboard_key_letter_size">70%p</fraction>
     <integer name="emoji_keyboard_max_key_count">30</integer>
 
 </resources>
diff --git a/java/res/values-sw600dp/dimens.xml b/java/res/values-sw600dp/dimens.xml
index 591355d..b2f4ae0 100644
--- a/java/res/values-sw600dp/dimens.xml
+++ b/java/res/values-sw600dp/dimens.xml
@@ -92,7 +92,7 @@
     <!-- Emoji keyboard -->
     <fraction name="emoji_keyboard_key_width">12.5%p</fraction>
     <fraction name="emoji_keyboard_row_height">33%p</fraction>
-    <fraction name="emoji_keyboard_key_letter_size">76%p</fraction>
+    <fraction name="emoji_keyboard_key_letter_size">60%p</fraction>
     <integer name="emoji_keyboard_max_key_count">24</integer>
 
 </resources>
diff --git a/java/res/values-sw768dp-land/dimens.xml b/java/res/values-sw768dp-land/dimens.xml
index 664630b..ce315b0 100644
--- a/java/res/values-sw768dp-land/dimens.xml
+++ b/java/res/values-sw768dp-land/dimens.xml
@@ -67,7 +67,7 @@
     <!-- Emoji keyboard -->
     <fraction name="emoji_keyboard_key_width">7.69%p</fraction>
     <fraction name="emoji_keyboard_row_height">33%p</fraction>
-    <fraction name="emoji_keyboard_key_letter_size">68%p</fraction>
+    <fraction name="emoji_keyboard_key_letter_size">60%p</fraction>
     <integer name="emoji_keyboard_max_key_count">39</integer>
 
 </resources>
diff --git a/java/res/values-sw768dp/dimens.xml b/java/res/values-sw768dp/dimens.xml
index 1fd933a..c90da7f 100644
--- a/java/res/values-sw768dp/dimens.xml
+++ b/java/res/values-sw768dp/dimens.xml
@@ -92,7 +92,7 @@
     <!-- Emoji keyboard -->
     <fraction name="emoji_keyboard_key_width">10%p</fraction>
     <fraction name="emoji_keyboard_row_height">33%p</fraction>
-    <fraction name="emoji_keyboard_key_letter_size">76%p</fraction>
+    <fraction name="emoji_keyboard_key_letter_size">68%p</fraction>
     <integer name="emoji_keyboard_max_key_count">30</integer>
 
 </resources>
diff --git a/java/res/values-v19/emoji-categories.xml b/java/res/values-v19/emoji-categories.xml
index 0d5aa1a..51aad6e 100644
--- a/java/res/values-v19/emoji-categories.xml
+++ b/java/res/values-v19/emoji-categories.xml
@@ -214,7 +214,7 @@
         <item>fe835|0038,20e3|99</item> <!-- TODO: fix support min sdk version (99) -->
         <item>fe836|0039,20e3|99</item> <!-- TODO: fix support min sdk version (99) -->
         <item>fe837|0030,20e3|99</item> <!-- TODO: fix support min sdk version (99) -->
-        <item>1f51f</item>
+        <item>1f51f||99</item> <!-- TODO: fix support min sdk version (99) -->
         <item>fe82c|0023,20e3|99</item> <!-- TODO: fix support min sdk version (99) -->
         <item>1f51d</item>
         <item>1f519</item>
diff --git a/java/res/values/config.xml b/java/res/values/config.xml
index 465d52c..66b9b70 100644
--- a/java/res/values/config.xml
+++ b/java/res/values/config.xml
@@ -103,7 +103,7 @@
      -->
     <string-array name="auto_correction_threshold_values" translatable="false">
         <!-- Off, When auto correction setting is Off, this value is not used. -->
-        <item></item>
+        <item>floatMaxValue</item>
         <!-- Modest : Suggestion whose normalized score is greater than this value
              will be subject to auto-correction. -->
         <item>0.185</item>
diff --git a/java/res/values/dimens.xml b/java/res/values/dimens.xml
index 2d626db..18cb262 100644
--- a/java/res/values/dimens.xml
+++ b/java/res/values/dimens.xml
@@ -118,7 +118,7 @@
     <!-- Emoji keyboard -->
     <fraction name="emoji_keyboard_key_width">14.2857%p</fraction>
     <fraction name="emoji_keyboard_row_height">33%p</fraction>
-    <fraction name="emoji_keyboard_key_letter_size">81%p</fraction>
+    <fraction name="emoji_keyboard_key_letter_size">68%p</fraction>
     <integer name="emoji_keyboard_max_key_count">21</integer>
     <dimen name="emoji_category_page_id_height">3dp</dimen>
 
diff --git a/java/src/com/android/inputmethod/keyboard/EmojiKeyboardView.java b/java/src/com/android/inputmethod/keyboard/EmojiKeyboardView.java
index eb48d01..db7c845 100644
--- a/java/src/com/android/inputmethod/keyboard/EmojiKeyboardView.java
+++ b/java/src/com/android/inputmethod/keyboard/EmojiKeyboardView.java
@@ -580,10 +580,18 @@
     }
 
     private void setCurrentCategoryId(final int categoryId, final boolean force) {
-        if (mEmojiCategory.getCurrentCategoryId() == categoryId && !force) {
+        final int oldCategoryId = mEmojiCategory.getCurrentCategoryId();
+        if (oldCategoryId == categoryId && !force) {
             return;
         }
 
+        if (oldCategoryId == CATEGORY_ID_RECENTS) {
+            // Needs to save pending updates for recent keys when we get out of the recents
+            // category because we don't want to move the recent emojis around while the user
+            // is in the recents category.
+            mEmojiKeyboardAdapter.flushPendingRecentKeys();
+        }
+
         mEmojiCategory.setCurrentCategoryId(categoryId);
         final int newTabId = mEmojiCategory.getTabIdFromCategoryId(categoryId);
         final int newCategoryPageId = mEmojiCategory.getPageIdFromCategoryId(categoryId);
@@ -612,8 +620,18 @@
             mRecentsKeyboard = mEmojiCategory.getKeyboard(CATEGORY_ID_RECENTS, 0);
         }
 
+        public void flushPendingRecentKeys() {
+            mRecentsKeyboard.flushPendingRecentKeys();
+            final KeyboardView recentKeyboardView =
+                    mActiveKeyboardView.get(mEmojiCategory.getRecentTabId());
+            if (recentKeyboardView != null) {
+                recentKeyboardView.invalidateAllKeys();
+            }
+        }
+
         public void addRecentKey(final Key key) {
             if (mEmojiCategory.isInRecentTab()) {
+                mRecentsKeyboard.addPendingKey(key);
                 return;
             }
             mRecentsKeyboard.addKeyFirst(key);
diff --git a/java/src/com/android/inputmethod/keyboard/EmojiLayoutParams.java b/java/src/com/android/inputmethod/keyboard/EmojiLayoutParams.java
index 71790b7..ceb44e7 100644
--- a/java/src/com/android/inputmethod/keyboard/EmojiLayoutParams.java
+++ b/java/src/com/android/inputmethod/keyboard/EmojiLayoutParams.java
@@ -56,7 +56,7 @@
                 - (mKeyVerticalGap - mBottomPadding) / 2;
         mEmojiPagerHeight = defaultKeyboardHeight - mEmojiActionBarHeight
                 - mEmojiCategoryPageIdViewHeight;
-        mEmojiPagerBottomMargin = mKeyVerticalGap / 2;
+        mEmojiPagerBottomMargin = 0;
         mEmojiKeyboardHeight = mEmojiPagerHeight - mEmojiPagerBottomMargin - 1;
     }
 
diff --git a/java/src/com/android/inputmethod/keyboard/internal/DynamicGridKeyboard.java b/java/src/com/android/inputmethod/keyboard/internal/DynamicGridKeyboard.java
index 0dd71e2..587f95a 100644
--- a/java/src/com/android/inputmethod/keyboard/internal/DynamicGridKeyboard.java
+++ b/java/src/com/android/inputmethod/keyboard/internal/DynamicGridKeyboard.java
@@ -39,6 +39,7 @@
     private static final String TAG = DynamicGridKeyboard.class.getSimpleName();
     private static final int TEMPLATE_KEY_CODE_0 = 0x30;
     private static final int TEMPLATE_KEY_CODE_1 = 0x31;
+    private final Object mLock = new Object();
 
     private final SharedPreferences mPrefs;
     private final int mLeftPadding;
@@ -48,6 +49,7 @@
     private final int mMaxKeyCount;
     private final boolean mIsRecents;
     private final ArrayDeque<GridKey> mGridKeys = CollectionUtils.newArrayDeque();
+    private final ArrayDeque<Key> mPendingKeys = CollectionUtils.newArrayDeque();
 
     private Key[] mCachedGridKeys;
 
@@ -74,6 +76,21 @@
         throw new RuntimeException("Can't find template key: code=" + code);
     }
 
+    public void addPendingKey(final Key usedKey) {
+        synchronized (mLock) {
+            mPendingKeys.addLast(usedKey);
+        }
+    }
+
+    public void flushPendingRecentKeys() {
+        synchronized (mLock) {
+            while (!mPendingKeys.isEmpty()) {
+                addKey(mPendingKeys.pollFirst(), true);
+            }
+            saveRecentKeys();
+        }
+    }
+
     public void addKeyFirst(final Key usedKey) {
         addKey(usedKey, true);
         if (mIsRecents) {
@@ -89,7 +106,7 @@
         if (usedKey == null) {
             return;
         }
-        synchronized (mGridKeys) {
+        synchronized (mLock) {
             mCachedGridKeys = null;
             final GridKey key = new GridKey(usedKey);
             while (mGridKeys.remove(key)) {
@@ -167,7 +184,7 @@
 
     @Override
     public Key[] getKeys() {
-        synchronized (mGridKeys) {
+        synchronized (mLock) {
             if (mCachedGridKeys != null) {
                 return mCachedGridKeys;
             }
diff --git a/java/src/com/android/inputmethod/latin/makedict/DictUpdater.java b/java/src/com/android/inputmethod/latin/makedict/DictUpdater.java
index 709ea33..c4f7ec9 100644
--- a/java/src/com/android/inputmethod/latin/makedict/DictUpdater.java
+++ b/java/src/com/android/inputmethod/latin/makedict/DictUpdater.java
@@ -16,6 +16,7 @@
 
 package com.android.inputmethod.latin.makedict;
 
+import com.android.inputmethod.annotations.UsedForTesting;
 import com.android.inputmethod.latin.makedict.FusionDictionary.WeightedString;
 
 import java.io.IOException;
@@ -24,6 +25,7 @@
 /**
  * An interface of a binary dictionary updater.
  */
+@UsedForTesting
 public interface DictUpdater extends DictDecoder {
 
     /**
@@ -31,6 +33,7 @@
      *
      * @param word the word to be deleted.
      */
+    @UsedForTesting
     public void deleteWord(final String word) throws IOException, UnsupportedFormatException;
 
     /**
@@ -43,6 +46,7 @@
      * @param isBlackListEntry whether this should be a blacklist entry.
      */
     // TODO: Support batch insertion.
+    @UsedForTesting
     public void insertWord(final String word, final int frequency,
             final ArrayList<WeightedString> bigramStrings,
             final ArrayList<WeightedString> shortcuts, final boolean isNotAWord,
diff --git a/java/src/com/android/inputmethod/latin/makedict/Ver3DictUpdater.java b/java/src/com/android/inputmethod/latin/makedict/Ver3DictUpdater.java
index fa7ae31..07adda6 100644
--- a/java/src/com/android/inputmethod/latin/makedict/Ver3DictUpdater.java
+++ b/java/src/com/android/inputmethod/latin/makedict/Ver3DictUpdater.java
@@ -57,7 +57,7 @@
     public void deleteWord(final String word) throws IOException, UnsupportedFormatException {
         if (mOutStream == null) openStreamAndBuffer();
         mDictBuffer.position(0);
-        super.readHeader();
+        readHeader();
         final int wordPos = getTerminalPosition(word);
         if (wordPos != FormatSpec.NOT_VALID_WORD) {
             mDictBuffer.position(wordPos);
diff --git a/java/src/com/android/inputmethod/latin/makedict/Ver4DictDecoder.java b/java/src/com/android/inputmethod/latin/makedict/Ver4DictDecoder.java
index bab24e3..5372907 100644
--- a/java/src/com/android/inputmethod/latin/makedict/Ver4DictDecoder.java
+++ b/java/src/com/android/inputmethod/latin/makedict/Ver4DictDecoder.java
@@ -48,7 +48,7 @@
 
     private final File mDictDirectory;
     private final DictionaryBufferFactory mBufferFactory;
-    private DictBuffer mDictBuffer;
+    protected DictBuffer mDictBuffer;
     private DictBuffer mFrequencyBuffer;
     private DictBuffer mTerminalAddressTableBuffer;
     private DictBuffer mBigramBuffer;
diff --git a/java/src/com/android/inputmethod/latin/makedict/Ver4DictUpdater.java b/java/src/com/android/inputmethod/latin/makedict/Ver4DictUpdater.java
new file mode 100644
index 0000000..3d8f186
--- /dev/null
+++ b/java/src/com/android/inputmethod/latin/makedict/Ver4DictUpdater.java
@@ -0,0 +1,59 @@
+/*
+ * Copyright (C) 2013 The Android Open Source Project
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ *      http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package com.android.inputmethod.latin.makedict;
+
+import com.android.inputmethod.annotations.UsedForTesting;
+import com.android.inputmethod.latin.makedict.FusionDictionary.WeightedString;
+
+import java.io.File;
+import java.io.IOException;
+import java.util.ArrayList;
+
+/**
+ * An implementation of DictUpdater for version 4 binary dictionary.
+ */
+@UsedForTesting
+public class Ver4DictUpdater extends Ver4DictDecoder implements DictUpdater {
+
+    @UsedForTesting
+    public Ver4DictUpdater(final File dictDirectory, final int factoryType) {
+        // DictUpdater must have an updatable DictBuffer.
+        super(dictDirectory, ((factoryType & MASK_DICTBUFFER) == USE_BYTEARRAY)
+                ? USE_BYTEARRAY : USE_WRITABLE_BYTEBUFFER);
+    }
+
+    @Override
+    public void deleteWord(final String word) throws IOException, UnsupportedFormatException {
+        if (mDictBuffer == null) openDictBuffer();
+        readHeader();
+        final int wordPos = getTerminalPosition(word);
+        if (wordPos != FormatSpec.NOT_VALID_WORD) {
+            mDictBuffer.position(wordPos);
+            final int flags = PtNodeReader.readPtNodeOptionFlags(mDictBuffer);
+            mDictBuffer.position(wordPos);
+            mDictBuffer.put((byte) DynamicBinaryDictIOUtils.markAsDeleted(flags));
+        }
+    }
+
+    @Override
+    public void insertWord(final String word, final int frequency,
+        final ArrayList<WeightedString> bigramStrings, final ArrayList<WeightedString> shortcuts,
+        final boolean isNotAWord, final boolean isBlackListEntry)
+                throws IOException, UnsupportedFormatException {
+        // TODO: Implement this method.
+    }
+}
diff --git a/java/src/com/android/inputmethod/latin/settings/SettingsValues.java b/java/src/com/android/inputmethod/latin/settings/SettingsValues.java
index ee322e9..2abcdc7 100644
--- a/java/src/com/android/inputmethod/latin/settings/SettingsValues.java
+++ b/java/src/com/android/inputmethod/latin/settings/SettingsValues.java
@@ -45,8 +45,9 @@
  */
 public final class SettingsValues {
     private static final String TAG = SettingsValues.class.getSimpleName();
-    // "floatNegativeInfinity" is a special marker string for Float.NEGATIVE_INFINITE
-    // currently used for auto-correction
+    // "floatMaxValue" and "floatNegativeInfinity" are special marker strings for
+    // Float.NEGATIVE_INFINITE and Float.MAX_VALUE. Currently used for auto-correction settings.
+    private static final String FLOAT_MAX_VALUE_MARKER_STRING = "floatMaxValue";
     private static final String FLOAT_NEGATIVE_INFINITY_MARKER_STRING = "floatNegativeInfinity";
 
     // From resources:
@@ -343,24 +344,28 @@
         final String[] autoCorrectionThresholdValues = res.getStringArray(
                 R.array.auto_correction_threshold_values);
         // When autoCorrectionThreshold is greater than 1.0, it's like auto correction is off.
-        float autoCorrectionThreshold = Float.MAX_VALUE;
+        final float autoCorrectionThreshold;
         try {
             final int arrayIndex = Integer.valueOf(currentAutoCorrectionSetting);
             if (arrayIndex >= 0 && arrayIndex < autoCorrectionThresholdValues.length) {
                 final String val = autoCorrectionThresholdValues[arrayIndex];
-                if (FLOAT_NEGATIVE_INFINITY_MARKER_STRING.equals(val)) {
+                if (FLOAT_MAX_VALUE_MARKER_STRING.equals(val)) {
+                    autoCorrectionThreshold = Float.MAX_VALUE;
+                } else if (FLOAT_NEGATIVE_INFINITY_MARKER_STRING.equals(val)) {
                     autoCorrectionThreshold = Float.NEGATIVE_INFINITY;
                 } else {
                     autoCorrectionThreshold = Float.parseFloat(val);
                 }
+            } else {
+                autoCorrectionThreshold = Float.MAX_VALUE;
             }
-        } catch (NumberFormatException e) {
+        } catch (final NumberFormatException e) {
             // Whenever the threshold settings are correct, never come here.
-            autoCorrectionThreshold = Float.MAX_VALUE;
             Log.w(TAG, "Cannot load auto correction threshold setting."
                     + " currentAutoCorrectionSetting: " + currentAutoCorrectionSetting
                     + ", autoCorrectionThresholdValues: "
                     + Arrays.toString(autoCorrectionThresholdValues), e);
+            return Float.MAX_VALUE;
         }
         return autoCorrectionThreshold;
     }
diff --git a/native/jni/src/suggest/core/policy/dictionary_header_structure_policy.h b/native/jni/src/suggest/core/policy/dictionary_header_structure_policy.h
index a6829b4..5492c60 100644
--- a/native/jni/src/suggest/core/policy/dictionary_header_structure_policy.h
+++ b/native/jni/src/suggest/core/policy/dictionary_header_structure_policy.h
@@ -37,6 +37,8 @@
 
     virtual float getMultiWordCostMultiplier() const = 0;
 
+    virtual int getLastDecayedTime() const = 0;
+
     virtual void readHeaderValueOrQuestionMark(const char *const key, int *outValue,
             int outValueSize) const = 0;
 
diff --git a/native/jni/src/suggest/policyimpl/dictionary/bigram/dynamic_bigram_list_policy.cpp b/native/jni/src/suggest/policyimpl/dictionary/bigram/dynamic_bigram_list_policy.cpp
index 8753c6e..b1170e2 100644
--- a/native/jni/src/suggest/policyimpl/dictionary/bigram/dynamic_bigram_list_policy.cpp
+++ b/native/jni/src/suggest/policyimpl/dictionary/bigram/dynamic_bigram_list_policy.cpp
@@ -360,13 +360,13 @@
 }
 
 bool DynamicBigramListPolicy::updateProbabilityForDecay(
-        BigramListReadWriteUtils::BigramFlags bigramFlags, const int targetPtNodePos,
+        const BigramListReadWriteUtils::BigramFlags bigramFlags, const int targetPtNodePos,
         int *const bigramEntryPos, bool *const outRemoved) const {
     *outRemoved = false;
     if (mIsDecayingDict) {
         // Update bigram probability for decaying.
         const int newProbability = ForgettingCurveUtils::getEncodedProbabilityToSave(
-                BigramListReadWriteUtils::getProbabilityFromFlags(bigramFlags));
+                BigramListReadWriteUtils::getProbabilityFromFlags(bigramFlags), mHeaderPolicy);
         if (ForgettingCurveUtils::isValidEncodedProbability(newProbability)) {
             // Write new probability.
             const BigramListReadWriteUtils::BigramFlags updatedBigramFlags =
diff --git a/native/jni/src/suggest/policyimpl/dictionary/bigram/dynamic_bigram_list_policy.h b/native/jni/src/suggest/policyimpl/dictionary/bigram/dynamic_bigram_list_policy.h
index b358b4e..0504b59 100644
--- a/native/jni/src/suggest/policyimpl/dictionary/bigram/dynamic_bigram_list_policy.h
+++ b/native/jni/src/suggest/policyimpl/dictionary/bigram/dynamic_bigram_list_policy.h
@@ -27,6 +27,7 @@
 namespace latinime {
 
 class BufferWithExtendableBuffer;
+class DictionaryHeaderStructurePolicy;
 class DictionaryShortcutsStructurePolicy;
 
 /*
@@ -34,10 +35,12 @@
  */
 class DynamicBigramListPolicy : public DictionaryBigramsStructurePolicy {
  public:
-    DynamicBigramListPolicy(BufferWithExtendableBuffer *const buffer,
+    DynamicBigramListPolicy(const DictionaryHeaderStructurePolicy *const headerPolicy,
+            BufferWithExtendableBuffer *const buffer,
             const DictionaryShortcutsStructurePolicy *const shortcutPolicy,
             const bool isDecayingDict)
-            : mBuffer(buffer), mShortcutPolicy(shortcutPolicy), mIsDecayingDict(isDecayingDict) {}
+            : mHeaderPolicy(headerPolicy), mBuffer(buffer), mShortcutPolicy(shortcutPolicy),
+              mIsDecayingDict(isDecayingDict) {}
 
     ~DynamicBigramListPolicy() {}
 
@@ -74,6 +77,7 @@
     static const int CONTINUING_BIGRAM_LINK_COUNT_LIMIT;
     static const int BIGRAM_ENTRY_COUNT_IN_A_BIGRAM_LIST_LIMIT;
 
+    const DictionaryHeaderStructurePolicy *const mHeaderPolicy;
     BufferWithExtendableBuffer *const mBuffer;
     const DictionaryShortcutsStructurePolicy *const mShortcutPolicy;
     const bool mIsDecayingDict;
@@ -81,7 +85,7 @@
     // Follow bigram link and return the position of bigram target PtNode that is currently valid.
     int followBigramLinkAndGetCurrentBigramPtNodePos(const int originalBigramPos) const;
 
-    bool updateProbabilityForDecay(BigramListReadWriteUtils::BigramFlags bigramFlags,
+    bool updateProbabilityForDecay(const BigramListReadWriteUtils::BigramFlags bigramFlags,
             const int targetPtNodePos, int *const bigramEntryPos, bool *const outRemoved) const;
 };
 } // namespace latinime
diff --git a/native/jni/src/suggest/policyimpl/dictionary/dynamic_patricia_trie_gc_event_listeners.cpp b/native/jni/src/suggest/policyimpl/dictionary/dynamic_patricia_trie_gc_event_listeners.cpp
index 324b530..a17a0ac 100644
--- a/native/jni/src/suggest/policyimpl/dictionary/dynamic_patricia_trie_gc_event_listeners.cpp
+++ b/native/jni/src/suggest/policyimpl/dictionary/dynamic_patricia_trie_gc_event_listeners.cpp
@@ -16,6 +16,7 @@
 
 #include "suggest/policyimpl/dictionary/dynamic_patricia_trie_gc_event_listeners.h"
 
+#include "suggest/core/policy/dictionary_header_structure_policy.h"
 #include "suggest/policyimpl/dictionary/utils/forgetting_curve_utils.h"
 
 namespace latinime {
@@ -29,7 +30,8 @@
     bool isUselessPtNode = !node->isTerminal();
     if (node->isTerminal() && mIsDecayingDict) {
         const int newProbability =
-                ForgettingCurveUtils::getEncodedProbabilityToSave(node->getProbability());
+                ForgettingCurveUtils::getEncodedProbabilityToSave(node->getProbability(),
+                        mHeaderPolicy);
         int writingPos = node->getProbabilityFieldPos();
         // Update probability.
         if (!DynamicPatriciaTrieWritingUtils::writeProbabilityAndAdvancePosition(
diff --git a/native/jni/src/suggest/policyimpl/dictionary/dynamic_patricia_trie_gc_event_listeners.h b/native/jni/src/suggest/policyimpl/dictionary/dynamic_patricia_trie_gc_event_listeners.h
index 463715a..3ca2f2a 100644
--- a/native/jni/src/suggest/policyimpl/dictionary/dynamic_patricia_trie_gc_event_listeners.h
+++ b/native/jni/src/suggest/policyimpl/dictionary/dynamic_patricia_trie_gc_event_listeners.h
@@ -29,6 +29,8 @@
 
 namespace latinime {
 
+class DictionaryHeaderStructurePolicy;
+
 class DynamicPatriciaTrieGcEventListeners {
  public:
     // Updates all PtNodes that can be reached from the root. Checks if each PtNode is useless or
@@ -38,10 +40,12 @@
         : public DynamicPatriciaTrieReadingHelper::TraversingEventListener {
      public:
         TraversePolicyToUpdateUnigramProbabilityAndMarkUselessPtNodesAsDeleted(
+                const DictionaryHeaderStructurePolicy *const headerPolicy,
                 DynamicPatriciaTrieWritingHelper *const writingHelper,
                 BufferWithExtendableBuffer *const buffer, const bool isDecayingDict)
-                : mWritingHelper(writingHelper), mBuffer(buffer), mIsDecayingDict(isDecayingDict),
-                  mValueStack(), mChildrenValue(0), mValidUnigramCount(0) {}
+                : mHeaderPolicy(headerPolicy), mWritingHelper(writingHelper), mBuffer(buffer),
+                  mIsDecayingDict(isDecayingDict), mValueStack(), mChildrenValue(0),
+                  mValidUnigramCount(0) {}
 
         ~TraversePolicyToUpdateUnigramProbabilityAndMarkUselessPtNodesAsDeleted() {};
 
@@ -72,9 +76,10 @@
         DISALLOW_IMPLICIT_CONSTRUCTORS(
                 TraversePolicyToUpdateUnigramProbabilityAndMarkUselessPtNodesAsDeleted);
 
+        const DictionaryHeaderStructurePolicy *const mHeaderPolicy;
         DynamicPatriciaTrieWritingHelper *const mWritingHelper;
         BufferWithExtendableBuffer *const mBuffer;
-        const int mIsDecayingDict;
+        const bool mIsDecayingDict;
         std::vector<int> mValueStack;
         int mChildrenValue;
         int mValidUnigramCount;
@@ -85,7 +90,8 @@
     class TraversePolicyToUpdateBigramProbability
             : public DynamicPatriciaTrieReadingHelper::TraversingEventListener {
      public:
-        TraversePolicyToUpdateBigramProbability(DynamicBigramListPolicy *const bigramPolicy)
+        TraversePolicyToUpdateBigramProbability(
+                DynamicBigramListPolicy *const bigramPolicy)
                 : mBigramPolicy(bigramPolicy), mValidBigramEntryCount(0) {}
 
         bool onAscend() { return true; }
diff --git a/native/jni/src/suggest/policyimpl/dictionary/dynamic_patricia_trie_policy.cpp b/native/jni/src/suggest/policyimpl/dictionary/dynamic_patricia_trie_policy.cpp
index 60d0db0..31e3fb4 100644
--- a/native/jni/src/suggest/policyimpl/dictionary/dynamic_patricia_trie_policy.cpp
+++ b/native/jni/src/suggest/policyimpl/dictionary/dynamic_patricia_trie_policy.cpp
@@ -42,7 +42,6 @@
 const int DynamicPatriciaTriePolicy::MAX_DICT_EXTENDED_REGION_SIZE = 1024 * 1024;
 const int DynamicPatriciaTriePolicy::MIN_DICT_SIZE_TO_REFUSE_DYNAMIC_OPERATIONS =
         DynamicPatriciaTrieWritingHelper::MAX_DICTIONARY_SIZE - 1024;
-const int DynamicPatriciaTriePolicy::DECAY_INTERVAL_FOR_DECAYING_DICTS = 2 * 60 * 60;
 
 void DynamicPatriciaTriePolicy::createAndGetAllChildNodes(const DicNode *const dicNode,
         DicNodeVector *const childDicNodes) const {
@@ -314,15 +313,15 @@
         AKLOGI("Warning: flushWithGC() is called for non-updatable dictionary.");
         return;
     }
-    const bool runGCwithDecay = needsToDecay();
-    DynamicBigramListPolicy bigramListPolicyForGC(&mBufferWithExtendableBuffer,
-            &mShortcutListPolicy, runGCwithDecay);
+    const bool needsToDecay = mHeaderPolicy.isDecayingDict()
+            && (mNeedsToDecayForTesting || ForgettingCurveUtils::needsToDecay(
+                    false /* mindsBlockByDecay */, mUnigramCount, mBigramCount, &mHeaderPolicy));
+    DynamicBigramListPolicy bigramListPolicyForGC(&mHeaderPolicy, &mBufferWithExtendableBuffer,
+            &mShortcutListPolicy, needsToDecay);
     DynamicPatriciaTrieWritingHelper writingHelper(&mBufferWithExtendableBuffer,
-            &bigramListPolicyForGC, &mShortcutListPolicy, runGCwithDecay);
+            &bigramListPolicyForGC, &mShortcutListPolicy, needsToDecay);
     writingHelper.writeToDictFileWithGC(getRootPosition(), filePath, &mHeaderPolicy);
-    if (runGCwithDecay) {
-        mNeedsToDecayForTesting = false;
-    }
+    mNeedsToDecayForTesting = false;
 }
 
 bool DynamicPatriciaTriePolicy::needsToRunGC(const bool mindsBlockByGC) const {
@@ -344,16 +343,8 @@
         // Needs to reduce dictionary size.
         return true;
     } else if (mHeaderPolicy.isDecayingDict()) {
-        if (mUnigramCount >= ForgettingCurveUtils::MAX_UNIGRAM_COUNT) {
-            // Unigram count exceeds the limit.
-            return true;
-        } else if (mBigramCount >= ForgettingCurveUtils::MAX_BIGRAM_COUNT) {
-            // Bigram count exceeds the limit.
-            return true;
-        } else if (mindsBlockByGC && needsToDecay()) {
-            // Time to update probabilities for decaying.
-            return true;
-        }
+        return mNeedsToDecayForTesting || ForgettingCurveUtils::needsToDecay(
+                mindsBlockByGC, mUnigramCount, mBigramCount, &mHeaderPolicy);
     }
     return false;
 }
@@ -369,9 +360,4 @@
     }
 }
 
-bool DynamicPatriciaTriePolicy::needsToDecay() const {
-    return mHeaderPolicy.isDecayingDict() && (mNeedsToDecayForTesting
-            || mHeaderPolicy.getLastDecayedTime() + DECAY_INTERVAL_FOR_DECAYING_DICTS < time(0));
-}
-
 } // namespace latinime
diff --git a/native/jni/src/suggest/policyimpl/dictionary/dynamic_patricia_trie_policy.h b/native/jni/src/suggest/policyimpl/dictionary/dynamic_patricia_trie_policy.h
index c3bbe99..903f65e 100644
--- a/native/jni/src/suggest/policyimpl/dictionary/dynamic_patricia_trie_policy.h
+++ b/native/jni/src/suggest/policyimpl/dictionary/dynamic_patricia_trie_policy.h
@@ -37,7 +37,7 @@
               mBufferWithExtendableBuffer(mBuffer->getBuffer() + mHeaderPolicy.getSize(),
                       mBuffer->getBufferSize() - mHeaderPolicy.getSize()),
               mShortcutListPolicy(&mBufferWithExtendableBuffer),
-              mBigramListPolicy(&mBufferWithExtendableBuffer, &mShortcutListPolicy,
+              mBigramListPolicy(&mHeaderPolicy, &mBufferWithExtendableBuffer, &mShortcutListPolicy,
                       mHeaderPolicy.isDecayingDict()),
               mUnigramCount(mHeaderPolicy.getUnigramCount()),
               mBigramCount(mHeaderPolicy.getBigramCount()), mNeedsToDecayForTesting(false) {}
@@ -105,7 +105,6 @@
     static const char *const SET_NEEDS_TO_DECAY_FOR_TESTING_QUERY;
     static const int MAX_DICT_EXTENDED_REGION_SIZE;
     static const int MIN_DICT_SIZE_TO_REFUSE_DYNAMIC_OPERATIONS;
-    static const int DECAY_INTERVAL_FOR_DECAYING_DICTS;
 
     const MmappedBuffer *const mBuffer;
     const HeaderPolicy mHeaderPolicy;
@@ -115,8 +114,6 @@
     int mUnigramCount;
     int mBigramCount;
     int mNeedsToDecayForTesting;
-
-    bool needsToDecay() const;
 };
 } // namespace latinime
 #endif // LATINIME_DYNAMIC_PATRICIA_TRIE_POLICY_H
diff --git a/native/jni/src/suggest/policyimpl/dictionary/dynamic_patricia_trie_writing_helper.cpp b/native/jni/src/suggest/policyimpl/dictionary/dynamic_patricia_trie_writing_helper.cpp
index 70a9ee5..067c8ec 100644
--- a/native/jni/src/suggest/policyimpl/dictionary/dynamic_patricia_trie_writing_helper.cpp
+++ b/native/jni/src/suggest/policyimpl/dictionary/dynamic_patricia_trie_writing_helper.cpp
@@ -165,7 +165,10 @@
             MAX_DICTIONARY_SIZE);
     int unigramCount = 0;
     int bigramCount = 0;
-    if (!runGC(rootPtNodeArrayPos, &newDictBuffer, &unigramCount, &bigramCount)) {
+    if (mNeedsToDecay) {
+        ForgettingCurveUtils::sTimeKeeper.setCurrentTime();
+    }
+    if (!runGC(rootPtNodeArrayPos, headerPolicy, &newDictBuffer, &unigramCount, &bigramCount)) {
         return;
     }
     BufferWithExtendableBuffer headerBuffer(0 /* originalBuffer */, 0 /* originalBufferSize */);
@@ -481,14 +484,14 @@
 }
 
 bool DynamicPatriciaTrieWritingHelper::runGC(const int rootPtNodeArrayPos,
-        BufferWithExtendableBuffer *const bufferToWrite, int *const outUnigramCount,
-        int *const outBigramCount) {
+        const HeaderPolicy *const headerPolicy, BufferWithExtendableBuffer *const bufferToWrite,
+        int *const outUnigramCount, int *const outBigramCount) {
     DynamicPatriciaTrieReadingHelper readingHelper(mBuffer, mBigramPolicy, mShortcutPolicy);
     readingHelper.initWithPtNodeArrayPos(rootPtNodeArrayPos);
     DynamicPatriciaTrieGcEventListeners
             ::TraversePolicyToUpdateUnigramProbabilityAndMarkUselessPtNodesAsDeleted
                     traversePolicyToUpdateUnigramProbabilityAndMarkUselessPtNodesAsDeleted(
-                            this, mBuffer, mNeedsToDecay);
+                            headerPolicy, this, mBuffer, mNeedsToDecay);
     if (!readingHelper.traverseAllPtNodesInPostorderDepthFirstManner(
             &traversePolicyToUpdateUnigramProbabilityAndMarkUselessPtNodesAsDeleted)) {
         return false;
@@ -505,7 +508,6 @@
             &traversePolicyToUpdateBigramProbability)) {
         return false;
     }
-
     if (mNeedsToDecay && traversePolicyToUpdateBigramProbability.getValidBigramEntryCount()
             > ForgettingCurveUtils::MAX_BIGRAM_COUNT_AFTER_GC) {
         // TODO: Remove more bigrams.
@@ -524,7 +526,7 @@
 
     // Create policy instance for the GCed dictionary.
     DynamicShortcutListPolicy newDictShortcutPolicy(bufferToWrite);
-    DynamicBigramListPolicy newDictBigramPolicy(bufferToWrite, &newDictShortcutPolicy,
+    DynamicBigramListPolicy newDictBigramPolicy(headerPolicy, bufferToWrite, &newDictShortcutPolicy,
             mNeedsToDecay);
     // Create reading helper for the GCed dictionary.
     DynamicPatriciaTrieReadingHelper newDictReadingHelper(bufferToWrite, &newDictBigramPolicy,
diff --git a/native/jni/src/suggest/policyimpl/dictionary/dynamic_patricia_trie_writing_helper.h b/native/jni/src/suggest/policyimpl/dictionary/dynamic_patricia_trie_writing_helper.h
index 0caf291..ca86647 100644
--- a/native/jni/src/suggest/policyimpl/dictionary/dynamic_patricia_trie_writing_helper.h
+++ b/native/jni/src/suggest/policyimpl/dictionary/dynamic_patricia_trie_writing_helper.h
@@ -128,8 +128,9 @@
             const int probabilityOfNewPtNode, const int *const newNodeCodePoints,
             const int newNodeCodePointCount);
 
-    bool runGC(const int rootPtNodeArrayPos, BufferWithExtendableBuffer *const bufferToWrite,
-            int *const outUnigramCount, int *const outBigramCount);
+    bool runGC(const int rootPtNodeArrayPos, const HeaderPolicy *const headerPolicy,
+            BufferWithExtendableBuffer *const bufferToWrite, int *const outUnigramCount,
+            int *const outBigramCount);
 
     int getUpdatedProbability(const int originalProbability, const int newProbability);
 };
diff --git a/native/jni/src/suggest/policyimpl/dictionary/utils/forgetting_curve_utils.cpp b/native/jni/src/suggest/policyimpl/dictionary/utils/forgetting_curve_utils.cpp
index b502fe2..19ca354 100644
--- a/native/jni/src/suggest/policyimpl/dictionary/utils/forgetting_curve_utils.cpp
+++ b/native/jni/src/suggest/policyimpl/dictionary/utils/forgetting_curve_utils.cpp
@@ -15,10 +15,12 @@
  */
 
 #include <cmath>
+#include <ctime>
 #include <stdlib.h>
 
 #include "suggest/policyimpl/dictionary/utils/forgetting_curve_utils.h"
 
+#include "suggest/core/policy/dictionary_header_structure_policy.h"
 #include "suggest/policyimpl/dictionary/utils/probability_utils.h"
 
 namespace latinime {
@@ -35,8 +37,14 @@
 // Currently, we try to decay each uni/bigram once every 2 hours. Accordingly, the expected
 // duration of the decay is approximately 66hours.
 const float ForgettingCurveUtils::MIN_PROBABILITY_TO_DECAY = 0.03f;
+const int ForgettingCurveUtils::DECAY_INTERVAL_SECONDS = 2 * 60 * 60;
 
 const ForgettingCurveUtils::ProbabilityTable ForgettingCurveUtils::sProbabilityTable;
+ForgettingCurveUtils::TimeKeeper ForgettingCurveUtils::sTimeKeeper;
+
+void ForgettingCurveUtils::TimeKeeper::setCurrentTime() {
+    mCurrentTime = time(0);
+}
 
 /* static */ int ForgettingCurveUtils::getProbability(const int encodedUnigramProbability,
         const int encodedBigramProbability) {
@@ -76,19 +84,44 @@
     return encodedProbability >= MIN_VALID_ENCODED_PROBABILITY;
 }
 
-/* static */ int ForgettingCurveUtils::getEncodedProbabilityToSave(const int encodedProbability) {
-    const int currentEncodedProbability = max(min(encodedProbability, MAX_ENCODED_PROBABILITY), 0);
+/* static */ int ForgettingCurveUtils::getEncodedProbabilityToSave(const int encodedProbability,
+        const DictionaryHeaderStructurePolicy *const headerPolicy) {
+    const int elapsedTime = sTimeKeeper.peekCurrentTime() - headerPolicy->getLastDecayedTime();
+    const int decayIterationCount = max(elapsedTime / DECAY_INTERVAL_SECONDS, 1);
+    int currentEncodedProbability = max(min(encodedProbability, MAX_ENCODED_PROBABILITY), 0);
     // TODO: Implement the decay in more proper way.
-    const float currentRate = static_cast<float>(currentEncodedProbability)
-            / static_cast<float>(MAX_ENCODED_PROBABILITY);
-    const float thresholdToDecay = MIN_PROBABILITY_TO_DECAY
-            + (1.0f - MIN_PROBABILITY_TO_DECAY) * (1.0f - currentRate);
-    const float randValue = static_cast<float>(rand()) / static_cast<float>(RAND_MAX);
-    if (thresholdToDecay < randValue) {
-        return max(currentEncodedProbability - ENCODED_PROBABILITY_STEP, 0);
-    } else {
-        return currentEncodedProbability;
+    for (int i = 0; i < decayIterationCount; ++i) {
+        const float currentRate = static_cast<float>(currentEncodedProbability)
+                / static_cast<float>(MAX_ENCODED_PROBABILITY);
+        const float thresholdToDecay = MIN_PROBABILITY_TO_DECAY
+                + (1.0f - MIN_PROBABILITY_TO_DECAY) * currentRate;
+        const float randValue = static_cast<float>(rand()) / static_cast<float>(RAND_MAX);
+        if (thresholdToDecay < randValue) {
+            currentEncodedProbability = max(currentEncodedProbability - ENCODED_PROBABILITY_STEP,
+                    0);
+        }
     }
+    return currentEncodedProbability;
+}
+
+/* static */ bool ForgettingCurveUtils::needsToDecay(const bool mindsBlockByDecay,
+        const int unigramCount, const int bigramCount,
+        const DictionaryHeaderStructurePolicy *const headerPolicy) {
+    if (unigramCount >= ForgettingCurveUtils::MAX_UNIGRAM_COUNT) {
+        // Unigram count exceeds the limit.
+        return true;
+    } else if (bigramCount >= ForgettingCurveUtils::MAX_BIGRAM_COUNT) {
+        // Bigram count exceeds the limit.
+        return true;
+    }
+    if (mindsBlockByDecay) {
+        return false;
+    }
+    if (headerPolicy->getLastDecayedTime() + DECAY_INTERVAL_SECONDS < time(0)) {
+        // Time to decay.
+        return true;
+    }
+    return false;
 }
 
 /* static */ int ForgettingCurveUtils::decodeProbability(const int encodedProbability) {
diff --git a/native/jni/src/suggest/policyimpl/dictionary/utils/forgetting_curve_utils.h b/native/jni/src/suggest/policyimpl/dictionary/utils/forgetting_curve_utils.h
index d666f22..2ad4238 100644
--- a/native/jni/src/suggest/policyimpl/dictionary/utils/forgetting_curve_utils.h
+++ b/native/jni/src/suggest/policyimpl/dictionary/utils/forgetting_curve_utils.h
@@ -23,16 +23,32 @@
 
 namespace latinime {
 
+class DictionaryHeaderStructurePolicy;
+
 // TODO: Check the elapsed time and decrease the probability depending on the time. Time field is
 // required to introduced to each terminal PtNode and bigram entry.
 // TODO: Quit using bigram probability to indicate the delta.
 class ForgettingCurveUtils {
  public:
+    class TimeKeeper {
+     public:
+        TimeKeeper() : mCurrentTime(0) {}
+        void setCurrentTime();
+        int peekCurrentTime() const { return mCurrentTime; };
+
+     private:
+        DISALLOW_COPY_AND_ASSIGN(TimeKeeper);
+
+        int mCurrentTime;
+    };
+
     static const int MAX_UNIGRAM_COUNT;
     static const int MAX_UNIGRAM_COUNT_AFTER_GC;
     static const int MAX_BIGRAM_COUNT;
     static const int MAX_BIGRAM_COUNT_AFTER_GC;
 
+    static TimeKeeper sTimeKeeper;
+
     static int getProbability(const int encodedUnigramProbability,
             const int encodedBigramProbability);
 
@@ -41,7 +57,11 @@
 
     static int isValidEncodedProbability(const int encodedProbability);
 
-    static int getEncodedProbabilityToSave(const int encodedProbability);
+    static int getEncodedProbabilityToSave(const int encodedProbability,
+            const DictionaryHeaderStructurePolicy *const headerPolicy);
+
+    static bool needsToDecay(const bool mindsBlockByDecay, const int unigramCount,
+            const int bigramCount, const DictionaryHeaderStructurePolicy *const headerPolicy);
 
  private:
     DISALLOW_IMPLICIT_CONSTRUCTORS(ForgettingCurveUtils);
@@ -68,6 +88,7 @@
     static const int MIN_VALID_ENCODED_PROBABILITY;
     static const int ENCODED_PROBABILITY_STEP;
     static const float MIN_PROBABILITY_TO_DECAY;
+    static const int DECAY_INTERVAL_SECONDS;
 
     static const ProbabilityTable sProbabilityTable;
 
diff --git a/tests/src/com/android/inputmethod/latin/BinaryDictionaryDecayingTests.java b/tests/src/com/android/inputmethod/latin/BinaryDictionaryDecayingTests.java
index b2d31c2..ded8eaa 100644
--- a/tests/src/com/android/inputmethod/latin/BinaryDictionaryDecayingTests.java
+++ b/tests/src/com/android/inputmethod/latin/BinaryDictionaryDecayingTests.java
@@ -50,8 +50,8 @@
     }
 
     private void forcePassingShortTime(final BinaryDictionary binaryDictionary) {
-        // Entries having low probability would be suppressed once in 2 GCs.
-        final int count = 2;
+        // Entries having low probability would be suppressed once in 3 GCs.
+        final int count = 3;
         for (int i = 0; i < count; i++) {
             binaryDictionary.getPropertyForTests(SET_NEEDS_TO_DECAY_FOR_TESTING_KEY);
             binaryDictionary.flushWithGC();
diff --git a/tests/src/com/android/inputmethod/latin/BinaryDictionaryTests.java b/tests/src/com/android/inputmethod/latin/BinaryDictionaryTests.java
index 6a21522..5b8f0e9 100644
--- a/tests/src/com/android/inputmethod/latin/BinaryDictionaryTests.java
+++ b/tests/src/com/android/inputmethod/latin/BinaryDictionaryTests.java
@@ -18,6 +18,7 @@
 
 import android.test.AndroidTestCase;
 import android.test.suitebuilder.annotation.LargeTest;
+import android.text.TextUtils;
 import android.util.Pair;
 
 import com.android.inputmethod.latin.makedict.CodePointUtils;
@@ -126,7 +127,7 @@
     public void testRandomlyAddUnigramWord() {
         final int wordCount = 1000;
         final int codePointSetSize = 50;
-        final int seed = 123456789;
+        final long seed = System.currentTimeMillis();
 
         File dictFile = null;
         try {
@@ -223,7 +224,8 @@
         final int wordCount = 100;
         final int bigramCount = 1000;
         final int codePointSetSize = 50;
-        final int seed = 11111;
+        final long seed = System.currentTimeMillis();
+        final Random random = new Random(seed);
 
         File dictFile = null;
         try {
@@ -234,43 +236,42 @@
         BinaryDictionary binaryDictionary = new BinaryDictionary(dictFile.getAbsolutePath(),
                 0 /* offset */, dictFile.length(), true /* useFullEditDistance */,
                 Locale.getDefault(), TEST_LOCALE, true /* isUpdatable */);
+
         final ArrayList<String> words = new ArrayList<String>();
-        // Test a word that isn't contained within the dictionary.
-        final Random random = new Random(seed);
+        final ArrayList<Pair<String, String>> bigramWords = new ArrayList<Pair<String,String>>();
         final int[] codePointSet = CodePointUtils.generateCodePointSet(codePointSetSize, random);
-        final int[] unigramProbabilities = new int[wordCount];
+        final HashMap<String, Integer> unigramProbabilities = new HashMap<String, Integer>();
+        final HashMap<Pair<String, String>, Integer> bigramProbabilities =
+                new HashMap<Pair<String, String>, Integer>();
+
         for (int i = 0; i < wordCount; ++i) {
             final String word = CodePointUtils.generateWord(random, codePointSet);
             words.add(word);
             final int unigramProbability = random.nextInt(0xFF);
-            unigramProbabilities[i] = unigramProbability;
+            unigramProbabilities.put(word, unigramProbability);
             binaryDictionary.addUnigramWord(word, unigramProbability);
         }
 
-        final int[][] probabilities = new int[wordCount][wordCount];
-
-        for (int i = 0; i < wordCount; ++i) {
-            for (int j = 0; j < wordCount; ++j) {
-                probabilities[i][j] = Dictionary.NOT_A_PROBABILITY;
-            }
-        }
-
         for (int i = 0; i < bigramCount; i++) {
-            final int word0Index = random.nextInt(wordCount);
-            final int word1Index = random.nextInt(wordCount);
-            final String word0 = words.get(word0Index);
-            final String word1 = words.get(word1Index);
+            final String word0 = words.get(random.nextInt(wordCount));
+            final String word1 = words.get(random.nextInt(wordCount));
+            if (TextUtils.equals(word0, word1)) {
+                continue;
+            }
+            final Pair<String, String> bigram = new Pair<String, String>(word0, word1);
+            bigramWords.add(bigram);
             final int bigramProbability = random.nextInt(0xF);
-            probabilities[word0Index][word1Index] = binaryDictionary.calculateProbability(
-                    unigramProbabilities[word1Index], bigramProbability);
+            bigramProbabilities.put(bigram, bigramProbability);
             binaryDictionary.addBigramWords(word0, word1, bigramProbability);
         }
 
-        for (int i = 0; i < words.size(); i++) {
-            for (int j = 0; j < words.size(); j++) {
-                assertEquals(probabilities[i][j],
-                        binaryDictionary.getBigramProbability(words.get(i), words.get(j)));
-            }
+        for (final Pair<String, String> bigram : bigramWords) {
+            final int unigramProbability = unigramProbabilities.get(bigram.second);
+            final int bigramProbability = bigramProbabilities.get(bigram);
+            final int probability = binaryDictionary.calculateProbability(unigramProbability,
+                    bigramProbability);
+            assertEquals(probability,
+                    binaryDictionary.getBigramProbability(bigram.first, bigram.second));
         }
 
         dictFile.delete();
@@ -419,8 +420,8 @@
         final int wordCount = 100;
         final int bigramCount = 1000;
         final int codePointSetSize = 30;
-        // TODO: Use various seeds such as a current timestamp to make this test more random.
-        final int seed = 314159265;
+        final long seed = System.currentTimeMillis();
+        final Random random = new Random(seed);
 
         File dictFile = null;
         try {
@@ -432,35 +433,32 @@
         BinaryDictionary binaryDictionary = new BinaryDictionary(dictFile.getAbsolutePath(),
                 0 /* offset */, dictFile.length(), true /* useFullEditDistance */,
                 Locale.getDefault(), TEST_LOCALE, true /* isUpdatable */);
+
         final ArrayList<String> words = new ArrayList<String>();
-        // Test a word that isn't contained within the dictionary.
-        final Random random = new Random(seed);
+        final ArrayList<Pair<String, String>> bigramWords = new ArrayList<Pair<String,String>>();
         final int[] codePointSet = CodePointUtils.generateCodePointSet(codePointSetSize, random);
-        final int[] unigramProbabilities = new int[wordCount];
+        final HashMap<String, Integer> unigramProbabilities = new HashMap<String, Integer>();
+        final HashMap<Pair<String, String>, Integer> bigramProbabilities =
+                new HashMap<Pair<String, String>, Integer>();
+
         for (int i = 0; i < wordCount; ++i) {
             final String word = CodePointUtils.generateWord(random, codePointSet);
             words.add(word);
             final int unigramProbability = random.nextInt(0xFF);
-            unigramProbabilities[i] = unigramProbability;
+            unigramProbabilities.put(word, unigramProbability);
             binaryDictionary.addUnigramWord(word, unigramProbability);
         }
 
-        final int[][] probabilities = new int[wordCount][wordCount];
-
-        for (int i = 0; i < wordCount; ++i) {
-            for (int j = 0; j < wordCount; ++j) {
-                probabilities[i][j] = Dictionary.NOT_A_PROBABILITY;
-            }
-        }
-
         for (int i = 0; i < bigramCount; i++) {
-            final int word0Index = random.nextInt(wordCount);
-            final int word1Index = random.nextInt(wordCount);
-            final String word0 = words.get(word0Index);
-            final String word1 = words.get(word1Index);
+            final String word0 = words.get(random.nextInt(wordCount));
+            final String word1 = words.get(random.nextInt(wordCount));
+            if (TextUtils.equals(word0, word1)) {
+                continue;
+            }
+            final Pair<String, String> bigram = new Pair<String, String>(word0, word1);
+            bigramWords.add(bigram);
             final int bigramProbability = random.nextInt(0xF);
-            probabilities[word0Index][word1Index] = binaryDictionary.calculateProbability(
-                    unigramProbabilities[word1Index], bigramProbability);
+            bigramProbabilities.put(bigram, bigramProbability);
             binaryDictionary.addBigramWords(word0, word1, bigramProbability);
         }
 
@@ -470,12 +468,15 @@
                 0 /* offset */, dictFile.length(), true /* useFullEditDistance */,
                 Locale.getDefault(), TEST_LOCALE, true /* isUpdatable */);
 
-        for (int i = 0; i < words.size(); i++) {
-            for (int j = 0; j < words.size(); j++) {
-                assertEquals(probabilities[i][j],
-                        binaryDictionary.getBigramProbability(words.get(i), words.get(j)));
-            }
+        for (final Pair<String, String> bigram : bigramWords) {
+            final int unigramProbability = unigramProbabilities.get(bigram.second);
+            final int bigramProbability = bigramProbabilities.get(bigram);
+            final int probability = binaryDictionary.calculateProbability(unigramProbability,
+                    bigramProbability);
+            assertEquals(probability,
+                    binaryDictionary.getBigramProbability(bigram.first, bigram.second));
         }
+
         dictFile.delete();
     }
 
@@ -487,8 +488,8 @@
         final float addBigramProb = 0.8f;
         final float removeBigramProb = 0.2f;
         final int codePointSetSize = 30;
-        final int seed = 141421356;
 
+        final long seed = System.currentTimeMillis();
         final Random random = new Random(seed);
 
         File dictFile = null;
@@ -539,6 +540,9 @@
                     }
                     final String word0 = words.get(word0Index);
                     final String word1 = words.get(word1Index);
+                    if (TextUtils.equals(word0, word1)) {
+                        continue;
+                    }
                     final int bigramProbability = random.nextInt(0xF);
                     final Pair<String, String> bigram = new Pair<String, String>(word0, word1);
                     bigramWords.add(bigram);
@@ -586,8 +590,8 @@
     public void testAddManyUnigramsAndFlushWithGC() {
         final int flashWithGCIterationCount = 3;
         final int codePointSetSize = 50;
-        final int seed = 22360679;
 
+        final long seed = System.currentTimeMillis();
         final Random random = new Random(seed);
 
         File dictFile = null;
@@ -632,8 +636,7 @@
         final int codePointSetSize = 50;
         final int unigramCountPerIteration = 1000;
         final int bigramCountPerIteration = 2000;
-        final int seed = 1123581321;
-
+        final long seed = System.currentTimeMillis();
         final Random random = new Random(seed);
 
         File dictFile = null;
@@ -661,6 +664,9 @@
             for (int j = 0; j < bigramCountPerIteration; j++) {
                 final String word0 = words.get(random.nextInt(words.size()));
                 final String word1 = words.get(random.nextInt(words.size()));
+                if (TextUtils.equals(word0, word1)) {
+                    continue;
+                }
                 bigrams.add(new Pair<String, String>(word0, word1));
                 final int bigramProbability = random.nextInt(0xF);
                 binaryDictionary.addBigramWords(word0, word1, bigramProbability);
diff --git a/tests/src/com/android/inputmethod/latin/makedict/BinaryDictDecoderEncoderTests.java b/tests/src/com/android/inputmethod/latin/makedict/BinaryDictDecoderEncoderTests.java
index aa16583..0189b33 100644
--- a/tests/src/com/android/inputmethod/latin/makedict/BinaryDictDecoderEncoderTests.java
+++ b/tests/src/com/android/inputmethod/latin/makedict/BinaryDictDecoderEncoderTests.java
@@ -646,7 +646,7 @@
         }
     }
 
-    public void testDeleteWord() {
+    private void runTestDeleteWord(final FormatOptions formatOptions) {
         final String dictName = "testDeleteWord";
         final String dictVersion = Long.toString(System.currentTimeMillis());
         final File file = setUpDictionaryFile(dictName, dictVersion);
@@ -655,10 +655,17 @@
                 new FusionDictionary.DictionaryOptions(
                         new HashMap<String, String>(), false, false));
         addUnigrams(sWords.size(), dict, sWords, null /* shortcutMap */);
-        timeWritingDictToFile(file, dict, VERSION3_WITH_DYNAMIC_UPDATE);
+        timeWritingDictToFile(file, dict, formatOptions);
 
-        final Ver3DictUpdater dictUpdater = new Ver3DictUpdater(file,
-                DictDecoder.USE_WRITABLE_BYTEBUFFER);
+        final DictUpdater dictUpdater;
+        if (formatOptions.mVersion == 3) {
+            dictUpdater = new Ver3DictUpdater(file, DictDecoder.USE_WRITABLE_BYTEBUFFER);
+        } else if (formatOptions.mVersion == 4) {
+            dictUpdater = new Ver4DictUpdater(file, DictDecoder.USE_WRITABLE_BYTEBUFFER);
+        } else {
+            throw new RuntimeException("DictUpdater for version " + formatOptions.mVersion
+                    + " doesn't exist.");
+        }
 
         try {
             MoreAsserts.assertNotEqual(FormatSpec.NOT_VALID_WORD,
@@ -676,4 +683,9 @@
         } catch (UnsupportedFormatException e) {
         }
     }
+
+    public void testDeleteWord() {
+        runTestDeleteWord(VERSION3_WITH_DYNAMIC_UPDATE);
+        runTestDeleteWord(VERSION4_WITH_DYNAMIC_UPDATE);
+    }
 }
diff --git a/tests/src/com/android/inputmethod/latin/makedict/BinaryDictIOUtilsTests.java b/tests/src/com/android/inputmethod/latin/makedict/BinaryDictIOUtilsTests.java
index acd6585..afe5adb 100644
--- a/tests/src/com/android/inputmethod/latin/makedict/BinaryDictIOUtilsTests.java
+++ b/tests/src/com/android/inputmethod/latin/makedict/BinaryDictIOUtilsTests.java
@@ -45,6 +45,9 @@
 
     private static final String TEST_DICT_FILE_EXTENSION = ".testDict";
 
+    private static final int VERSION3 = 3;
+    private static final int VERSION4 = 4;
+
     private static final String[] CHARACTERS = {
         "a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l", "m",
         "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x", "y", "z",
@@ -183,11 +186,16 @@
     // return amount of time to insert a word
     private long insertAndCheckWord(final File file, final String word, final int frequency,
             final boolean exist, final ArrayList<WeightedString> bigrams,
-            final ArrayList<WeightedString> shortcuts) {
+            final ArrayList<WeightedString> shortcuts, final int formatVersion) {
         long amountOfTime = -1;
         try {
-            final Ver3DictUpdater dictUpdater = new Ver3DictUpdater(file,
-                    DictDecoder.USE_WRITABLE_BYTEBUFFER);
+            final DictUpdater dictUpdater;
+            if (formatVersion == VERSION3) {
+                dictUpdater = new Ver3DictUpdater(file, DictDecoder.USE_WRITABLE_BYTEBUFFER);
+            } else {
+                throw new RuntimeException("DictUpdater for version " + formatVersion + " doesn't"
+                        + " exist.");
+            }
 
             if (!exist) {
                 assertEquals(FormatSpec.NOT_VALID_WORD, getWordPosition(file, word));
@@ -204,10 +212,15 @@
         return amountOfTime;
     }
 
-    private void deleteWord(final File file, final String word) {
+    private void deleteWord(final File file, final String word, final int formatVersion) {
         try {
-            final Ver3DictUpdater dictUpdater = new Ver3DictUpdater(file,
-                    DictDecoder.USE_WRITABLE_BYTEBUFFER);
+            final DictUpdater dictUpdater;
+            if (formatVersion == VERSION3) {
+                dictUpdater = new Ver3DictUpdater(file, DictDecoder.USE_WRITABLE_BYTEBUFFER);
+            } else {
+                throw new RuntimeException("DictUpdater for version " + formatVersion + " doesn't"
+                        + " exist.");
+            }
             dictUpdater.deleteWord(word);
         } catch (IOException e) {
         } catch (UnsupportedFormatException e) {
@@ -229,7 +242,7 @@
         }
     }
 
-    public void testInsertWord() {
+    private void runTestInsertWord(final int formatVersion) {
         File file = null;
         try {
             file = File.createTempFile("testInsertWord", TEST_DICT_FILE_EXTENSION,
@@ -253,33 +266,37 @@
         }
 
         MoreAsserts.assertNotEqual(FormatSpec.NOT_VALID_WORD, getWordPosition(file, "abcd"));
-        insertAndCheckWord(file, "abcde", 10, false, null, null);
+        insertAndCheckWord(file, "abcde", 10, false, null, null, formatVersion);
 
-        insertAndCheckWord(file, "abcdefghijklmn", 10, false, null, null);
+        insertAndCheckWord(file, "abcdefghijklmn", 10, false, null, null, formatVersion);
         checkReverseLookup(file, "abcdefghijklmn", getWordPosition(file, "abcdefghijklmn"));
 
-        insertAndCheckWord(file, "abcdabcd", 10, false, null, null);
+        insertAndCheckWord(file, "abcdabcd", 10, false, null, null, formatVersion);
         checkReverseLookup(file, "abcdabcd", getWordPosition(file, "abcdabcd"));
 
         // update the existing word.
-        insertAndCheckWord(file, "abcdabcd", 15, true, null, null);
+        insertAndCheckWord(file, "abcdabcd", 15, true, null, null, formatVersion);
 
         // split 1
-        insertAndCheckWord(file, "ab", 20, false, null, null);
+        insertAndCheckWord(file, "ab", 20, false, null, null, formatVersion);
 
         // split 2
-        insertAndCheckWord(file, "ami", 30, false, null, null);
+        insertAndCheckWord(file, "ami", 30, false, null, null, formatVersion);
 
-        deleteWord(file, "ami");
+        deleteWord(file, "ami", formatVersion);
         assertEquals(FormatSpec.NOT_VALID_WORD, getWordPosition(file, "ami"));
 
-        insertAndCheckWord(file, "abcdabfg", 30, false, null, null);
+        insertAndCheckWord(file, "abcdabfg", 30, false, null, null, formatVersion);
 
-        deleteWord(file, "abcd");
+        deleteWord(file, "abcd", formatVersion);
         assertEquals(FormatSpec.NOT_VALID_WORD, getWordPosition(file, "abcd"));
     }
 
-    public void testInsertWordWithBigrams() {
+    public void testInsertWord() {
+        runTestInsertWord(VERSION3);
+    }
+
+    private void runTestInsertWordWithBigrams(final int formatVersion) {
         File file = null;
         try {
             file = File.createTempFile("testInsertWordWithBigrams", TEST_DICT_FILE_EXTENSION,
@@ -306,8 +323,8 @@
         final ArrayList<WeightedString> banana = new ArrayList<WeightedString>();
         banana.add(new WeightedString("banana", 10));
 
-        insertAndCheckWord(file, "banana", 0, false, null, null);
-        insertAndCheckWord(file, "recursive", 60, true, banana, null);
+        insertAndCheckWord(file, "banana", 0, false, null, null, formatVersion);
+        insertAndCheckWord(file, "recursive", 60, true, banana, null, formatVersion);
 
         final PtNodeInfo info = findWordFromFile(file, "recursive");
         int bananaPos = getWordPosition(file, "banana");
@@ -316,7 +333,11 @@
         assertEquals(info.mBigrams.get(0).mAddress, bananaPos);
     }
 
-    public void testRandomWords() {
+    public void testInsertWordWithBigrams() {
+        runTestInsertWordWithBigrams(VERSION3);
+    }
+
+    private void runTestRandomWords(final int formatVersion) {
         File file = null;
         try {
             file = File.createTempFile("testRandomWord", TEST_DICT_FILE_EXTENSION,
@@ -345,7 +366,7 @@
         int cnt = 0;
         for (final String word : sWords) {
             final long diff = insertAndCheckWord(file, word,
-                    cnt % FormatSpec.MAX_TERMINAL_FREQUENCY, false, null, null);
+                    cnt % FormatSpec.MAX_TERMINAL_FREQUENCY, false, null, null, formatVersion);
             maxTimeToInsert = Math.max(maxTimeToInsert, diff);
             minTimeToInsert = Math.min(minTimeToInsert, diff);
             sum += diff;
@@ -356,8 +377,13 @@
             MoreAsserts.assertNotEqual(FormatSpec.NOT_VALID_WORD, getWordPosition(file, word));
         }
 
+        Log.d(TAG, "Test version " + formatVersion);
         Log.d(TAG, "max = " + ((double)maxTimeToInsert/1000000) + " ms.");
         Log.d(TAG, "min = " + ((double)minTimeToInsert/1000000) + " ms.");
         Log.d(TAG, "avg = " + ((double)sum/mMaxUnigrams/1000000) + " ms.");
     }
+
+    public void testRandomWords() {
+        runTestRandomWords(VERSION3);
+    }
 }