diff --git a/java/res/xml-sw600dp/row_symbols4.xml b/java/res/xml-sw600dp/row_symbols4.xml
index 73a5b17..f138d8e 100644
--- a/java/res/xml-sw600dp/row_symbols4.xml
+++ b/java/res/xml-sw600dp/row_symbols4.xml
@@ -41,6 +41,8 @@
             latin:moreKeys="!text/more_keys_for_tablet_double_quote" />
         <Key
             latin:keyLabel="_" />
-        <!-- Here is empty space. -->
+        <!-- Note: This Spacer prevents the above key from being marked as a right edge key. -->
+        <Spacer
+            latin:keyWidth="fillRight" />
     </Row>
 </merge>
diff --git a/java/res/xml-sw600dp/row_symbols_shift4.xml b/java/res/xml-sw600dp/row_symbols_shift4.xml
index 6f3aac7..29befa9 100644
--- a/java/res/xml-sw600dp/row_symbols_shift4.xml
+++ b/java/res/xml-sw600dp/row_symbols_shift4.xml
@@ -33,6 +33,8 @@
             latin:keyXPos="28.0%p"
             latin:keyboardLayout="@xml/key_space"
             latin:backgroundType="normal" />
-        <!-- Here is empty space. -->
+        <!-- Note: This Spacer prevents the above key from being marked as a right edge key. -->
+        <Spacer
+            latin:keyWidth="fillRight" />
     </Row>
 </merge>
diff --git a/java/res/xml-sw600dp/rows_number_normal.xml b/java/res/xml-sw600dp/rows_number_normal.xml
index 48b3040..f692394 100644
--- a/java/res/xml-sw600dp/rows_number_normal.xml
+++ b/java/res/xml-sw600dp/rows_number_normal.xml
@@ -153,5 +153,8 @@
         <Key
             latin:keyLabel="#"
             latin:keyStyle="numKeyStyle" />
+        <!-- Note: This Spacer prevents the above key from being marked as a right edge key. -->
+        <Spacer
+            latin:keyWidth="fillRight" />
     </Row>
 </merge>
diff --git a/java/res/xml-sw768dp/row_dvorak4.xml b/java/res/xml-sw768dp/row_dvorak4.xml
index 0827815..8f9230d 100644
--- a/java/res/xml-sw768dp/row_dvorak4.xml
+++ b/java/res/xml-sw768dp/row_dvorak4.xml
@@ -25,8 +25,10 @@
         latin:keyWidth="8.047%p"
         latin:backgroundType="functional"
     >
+        <!-- Note: This Spacer prevents the below key from being marked as a left edge key. -->
+        <Spacer
+            latin:keyWidth="5.782%p" />
         <include
-            latin:keyXPos="5.782%p"
             latin:keyboardLayout="@xml/key_settings" />
         <include
             latin:keyboardLayout="@xml/key_shortcut" />
@@ -42,5 +44,8 @@
             latin:keyboardLayout="@xml/key_dash" />
         <include
             latin:keyboardLayout="@xml/key_f2" />
+        <!-- Note: This Spacer prevents the above key from being marked as a right edge key. -->
+        <Spacer
+            latin:keyWidth="fillRight" />
     </Row>
 </merge>
diff --git a/java/res/xml-sw768dp/row_hebrew4.xml b/java/res/xml-sw768dp/row_hebrew4.xml
index 180c564..ae14f02 100644
--- a/java/res/xml-sw768dp/row_hebrew4.xml
+++ b/java/res/xml-sw768dp/row_hebrew4.xml
@@ -25,8 +25,10 @@
         latin:keyWidth="8.047%p"
         latin:backgroundType="functional"
     >
+        <!-- Note: This Spacer prevents the below key from being marked as a left edge key. -->
+        <Spacer
+            latin:keyWidth="5.782%p" />
         <include
-            latin:keyXPos="5.782%p"
             latin:keyboardLayout="@xml/key_settings" />
         <include
             latin:keyboardLayout="@xml/key_shortcut" />
@@ -40,5 +42,8 @@
             latin:keyboardLayout="@xml/keys_comma_period" />
         <include
             latin:keyboardLayout="@xml/key_f2" />
+        <!-- Note: This Spacer prevents the above key from being marked as a right edge key. -->
+        <Spacer
+            latin:keyWidth="fillRight" />
     </Row>
 </merge>
diff --git a/java/res/xml-sw768dp/row_qwerty4.xml b/java/res/xml-sw768dp/row_qwerty4.xml
index 92411f5..f1f4214 100644
--- a/java/res/xml-sw768dp/row_qwerty4.xml
+++ b/java/res/xml-sw768dp/row_qwerty4.xml
@@ -25,8 +25,10 @@
         latin:keyWidth="8.047%p"
         latin:backgroundType="functional"
     >
+        <!-- Note: This Spacer prevents the below key from being marked as a left edge key. -->
+        <Spacer
+            latin:keyWidth="5.782%p" />
         <include
-            latin:keyXPos="5.782%p"
             latin:keyboardLayout="@xml/key_settings" />
         <include
             latin:keyboardLayout="@xml/key_shortcut" />
@@ -42,5 +44,8 @@
             latin:keyboardLayout="@xml/key_dash" />
         <include
             latin:keyboardLayout="@xml/key_f2" />
+        <!-- Note: This Spacer prevents the above key from being marked as a right edge key. -->
+        <Spacer
+            latin:keyWidth="fillRight" />
     </Row>
 </merge>
diff --git a/java/res/xml-sw768dp/row_symbols4.xml b/java/res/xml-sw768dp/row_symbols4.xml
index 4e1c119..b801a12 100644
--- a/java/res/xml-sw768dp/row_symbols4.xml
+++ b/java/res/xml-sw768dp/row_symbols4.xml
@@ -25,8 +25,10 @@
         latin:keyWidth="8.047%p"
         latin:backgroundType="functional"
     >
+        <!-- Note: This Spacer prevents the below key from being marked as a left edge key. -->
+        <Spacer
+            latin:keyWidth="13.829%p" />
         <Key
-            latin:keyXPos="13.829%p"
             latin:keyLabel="/" />
         <include
             latin:keyboardLayout="@xml/key_f1" />
@@ -39,6 +41,8 @@
             latin:moreKeys="!text/more_keys_for_tablet_double_quote" />
         <Key
             latin:keyLabel="_" />
-        <!-- Here is empty space. -->
+        <!-- Note: This Spacer prevents the above key from being marked as a right edge key. -->
+        <Spacer
+            latin:keyWidth="fillRight" />
     </Row>
 </merge>
diff --git a/java/res/xml-sw768dp/row_symbols_shift4.xml b/java/res/xml-sw768dp/row_symbols_shift4.xml
index 561351c..f71864b 100644
--- a/java/res/xml-sw768dp/row_symbols_shift4.xml
+++ b/java/res/xml-sw768dp/row_symbols_shift4.xml
@@ -25,11 +25,14 @@
         latin:keyWidth="8.047%p"
         latin:backgroundType="functional"
     >
-        <!-- Here is empty space. -->
+        <!-- Note: This Spacer prevents the below key from being marked as a left edge key. -->
+        <Spacer
+            latin:keyWidth="29.923%p" />
         <include
-            latin:keyXPos="29.923%p"
             latin:keyboardLayout="@xml/key_space"
             latin:backgroundType="normal" />
-        <!-- Here is empty space. -->
+        <!-- Note: This Spacer prevents the above key from being marked as a right edge key. -->
+        <Spacer
+            latin:keyWidth="fillRight" />
     </Row>
 </merge>
diff --git a/java/res/xml-sw768dp/rows_number_normal.xml b/java/res/xml-sw768dp/rows_number_normal.xml
index 84910a8..d4d7c72 100644
--- a/java/res/xml-sw768dp/rows_number_normal.xml
+++ b/java/res/xml-sw768dp/rows_number_normal.xml
@@ -168,5 +168,8 @@
         <Key
             latin:keyLabel="#"
             latin:keyStyle="numKeyStyle" />
+        <!-- Note: This Spacer prevents the above key from being marked as a right edge key. -->
+        <Spacer
+            latin:keyWidth="fillRight" />
     </Row>
 </merge>
diff --git a/java/src/com/android/inputmethod/keyboard/KeyDetector.java b/java/src/com/android/inputmethod/keyboard/KeyDetector.java
index 868c8ca..f5686dc 100644
--- a/java/src/com/android/inputmethod/keyboard/KeyDetector.java
+++ b/java/src/com/android/inputmethod/keyboard/KeyDetector.java
@@ -83,11 +83,17 @@
         int minDistance = Integer.MAX_VALUE;
         Key primaryKey = null;
         for (final Key key: mKeyboard.getNearestKeys(touchX, touchY)) {
-            final boolean isOnKey = key.isOnKey(touchX, touchY);
+            // An edge key always has its enlarged hitbox to respond to an event that occurred in
+            // the empty area around the key. (@see Key#markAsLeftEdge(KeyboardParams)} etc.)
+            if (!key.isOnKey(touchX, touchY)) {
+                continue;
+            }
             final int distance = key.squaredDistanceToEdge(touchX, touchY);
+            if (distance > minDistance) {
+                continue;
+            }
             // To take care of hitbox overlaps, we compare mCode here too.
-            if (primaryKey == null || distance < minDistance
-                    || (distance == minDistance && isOnKey && key.mCode > primaryKey.mCode)) {
+            if (primaryKey == null || distance < minDistance || key.mCode > primaryKey.mCode) {
                 minDistance = distance;
                 primaryKey = key;
             }
diff --git a/native/jni/src/defines.h b/native/jni/src/defines.h
index 2ce10d0..0286365 100644
--- a/native/jni/src/defines.h
+++ b/native/jni/src/defines.h
@@ -327,6 +327,9 @@
 // Max Distance between point to key
 #define MAX_POINT_TO_KEY_LENGTH 10000000
 
+// The max number of the keys in one keyboard layout
+#define MAX_KEY_COUNT_IN_A_KEYBOARD 64
+
 // TODO: Reduce this constant if possible; check the maximum number of digraphs in the same
 // word in the dictionary for languages with digraphs, like German and French
 #define DEFAULT_MAX_DIGRAPH_SEARCH_DEPTH 5
diff --git a/native/jni/src/proximity_info.cpp b/native/jni/src/proximity_info.cpp
index 7371726..a8c0430 100644
--- a/native/jni/src/proximity_info.cpp
+++ b/native/jni/src/proximity_info.cpp
@@ -62,6 +62,7 @@
           CELL_WIDTH((keyboardWidth + gridWidth - 1) / gridWidth),
           CELL_HEIGHT((keyboardHeight + gridHeight - 1) / gridHeight),
           KEY_COUNT(min(keyCount, MAX_KEY_COUNT_IN_A_KEYBOARD)),
+          KEYBOARD_WIDTH(keyboardWidth), KEYBOARD_HEIGHT(keyboardHeight),
           HAS_TOUCH_POSITION_CORRECTION_DATA(keyCount > 0 && keyXCoordinates && keyYCoordinates
                   && keyWidths && keyHeights && keyCharCodes && sweetSpotCenterXs
                   && sweetSpotCenterYs && sweetSpotRadii),
diff --git a/native/jni/src/proximity_info.h b/native/jni/src/proximity_info.h
index f588874..7c22e10 100644
--- a/native/jni/src/proximity_info.h
+++ b/native/jni/src/proximity_info.h
@@ -96,6 +96,14 @@
         return GRID_HEIGHT;
     }
 
+    int getKeyboardWidth() const {
+        return KEYBOARD_WIDTH;
+    }
+
+    int getKeyboardHeight() const {
+        return KEYBOARD_HEIGHT;
+    }
+
     // TODO: These should return int.
     float getKeyCenterXOfCodePointG(int charCode) const;
     float getKeyCenterYOfCodePointG(int charCode) const;
@@ -105,8 +113,6 @@
 
  private:
     DISALLOW_IMPLICIT_CONSTRUCTORS(ProximityInfo);
-    // The max number of the keys in one keyboard layout
-    static const int MAX_KEY_COUNT_IN_A_KEYBOARD = 64;
     // The upper limit of the char code in mCodePointToKeyIndex
     static const int MAX_CHAR_CODE = 127;
     static const float NOT_A_DISTANCE_FLOAT;
@@ -136,6 +142,8 @@
     const int CELL_WIDTH;
     const int CELL_HEIGHT;
     const int KEY_COUNT;
+    const int KEYBOARD_WIDTH;
+    const int KEYBOARD_HEIGHT;
     const bool HAS_TOUCH_POSITION_CORRECTION_DATA;
     char mLocaleStr[MAX_LOCALE_STRING_LENGTH];
     int32_t *mProximityCharsArray;
diff --git a/native/jni/src/proximity_info_state.cpp b/native/jni/src/proximity_info_state.cpp
index e53394b..c9a1ed0 100644
--- a/native/jni/src/proximity_info_state.cpp
+++ b/native/jni/src/proximity_info_state.cpp
@@ -76,6 +76,7 @@
     mTimes.clear();
     mLengthCache.clear();
     mDistanceCache.clear();
+    mNearKeysVector.clear();
     mInputSize = 0;
 
     if (xCoordinates && yCoordinates) {
@@ -122,14 +123,34 @@
 
     if (mInputSize > 0) {
         const int keyCount = mProximityInfo->getKeyCount();
+        mNearKeysVector.resize(mInputSize);
         mDistanceCache.resize(mInputSize * keyCount);
         for (int i = 0; i < mInputSize; ++i) {
+            mNearKeysVector[i].reset();
+            static const float NEAR_KEY_NORMALIZED_SQUARED_THRESHOLD = 4.0f;
             for (int k = 0; k < keyCount; ++k) {
                 const int index = i * keyCount + k;
                 const int x = mInputXs[i];
                 const int y = mInputYs[i];
-                mDistanceCache[index] =
+                const float normalizedSquaredDistance =
                         mProximityInfo->getNormalizedSquaredDistanceFromCenterFloat(k, x, y);
+                mDistanceCache[index] = normalizedSquaredDistance;
+                if (normalizedSquaredDistance < NEAR_KEY_NORMALIZED_SQUARED_THRESHOLD) {
+                    mNearKeysVector[i].set(k, 1);
+                }
+            }
+        }
+
+        static const float READ_FORWORD_LENGTH_SCALE = 0.95f;
+        const int readForwordLength = static_cast<int>(
+                hypotf(mProximityInfo->getKeyboardWidth(), mProximityInfo->getKeyboardHeight())
+                * READ_FORWORD_LENGTH_SCALE);
+        for (int i = 0; i < mInputSize; ++i) {
+            for (int j = i + 1; j < mInputSize; ++j) {
+                if (mLengthCache[j] - mLengthCache[i] >= readForwordLength) {
+                    break;
+                }
+                mNearKeysVector[i] |= mNearKeysVector[j];
             }
         }
     }
@@ -182,7 +203,7 @@
 // the given point and the nearest key position.
 float ProximityInfoState::updateNearKeysDistances(const int x, const int y,
         NearKeysDistanceMap *const currentNearKeysDistances) {
-    static const float NEAR_KEY_THRESHOLD = 10.0f;
+    static const float NEAR_KEY_THRESHOLD = 4.0f;
 
     currentNearKeysDistances->clear();
     const int keyCount = mProximityInfo->getKeyCount();
@@ -394,4 +415,30 @@
     const float inputY = static_cast<float>(mInputYs[inputIndex]);
     return square(inputX - sweetSpotCenterX) + square(inputY - sweetSpotCenterY);
 }
+
+// Puts possible characters into filter and returns new filter size.
+int32_t ProximityInfoState::getAllPossibleChars(
+        const size_t index, int32_t *const filter, const int32_t filterSize) const {
+    if (index >= mInputXs.size()) {
+        return filterSize;
+    }
+    int i = filterSize;
+    for (int j = 0; j < mProximityInfo->getKeyCount(); ++j) {
+        if (mNearKeysVector[index].test(j)) {
+            const int32_t keyCodePoint = mProximityInfo->getCodePointOf(j);
+            bool insert = true;
+            // TODO: Avoid linear search
+            for (int k = 0; k < filterSize; ++k) {
+                if (filter[k] == keyCodePoint) {
+                    insert = false;
+                    break;
+                }
+            }
+            if (insert) {
+                filter[i++] = keyCodePoint;
+            }
+        }
+    }
+    return i;
+}
 } // namespace latinime
diff --git a/native/jni/src/proximity_info_state.h b/native/jni/src/proximity_info_state.h
index 746b9c9..80b84e9 100644
--- a/native/jni/src/proximity_info_state.h
+++ b/native/jni/src/proximity_info_state.h
@@ -17,6 +17,7 @@
 #ifndef LATINIME_PROXIMITY_INFO_STATE_H
 #define LATINIME_PROXIMITY_INFO_STATE_H
 
+#include <bitset>
 #include <cstring> // for memset()
 #include <stdint.h>
 #include <string>
@@ -32,6 +33,7 @@
 
 class ProximityInfoState {
  public:
+    typedef std::bitset<MAX_KEY_COUNT_IN_A_KEYBOARD> NearKeycodesSet;
     static const int NORMALIZED_SQUARED_DISTANCE_SCALING_FACTOR_LOG_2 = 10;
     static const int NORMALIZED_SQUARED_DISTANCE_SCALING_FACTOR =
             1 << NORMALIZED_SQUARED_DISTANCE_SCALING_FACTOR_LOG_2;
@@ -56,7 +58,8 @@
               mHasTouchPositionCorrectionData(false), mMostCommonKeyWidthSquare(0), mLocaleStr(),
               mKeyCount(0), mCellHeight(0), mCellWidth(0), mGridHeight(0), mGridWidth(0),
               mInputXs(), mInputYs(), mTimes(), mDistanceCache(), mLengthCache(),
-              mTouchPositionCorrectionEnabled(false), mInputSize(0) {
+              mNearKeysVector(), mTouchPositionCorrectionEnabled(false),
+              mInputSize(0) {
         memset(mInputCodes, 0, sizeof(mInputCodes));
         memset(mNormalizedSquaredDistances, 0, sizeof(mNormalizedSquaredDistances));
         memset(mPrimaryInputWord, 0, sizeof(mPrimaryInputWord));
@@ -215,6 +218,9 @@
 
     int getSpaceY();
 
+    int32_t getAllPossibleChars(
+            const size_t startIndex, int32_t *const filter, int32_t filterSize) const;
+
  private:
     DISALLOW_COPY_AND_ASSIGN(ProximityInfoState);
     typedef hash_map_compat<int, float> NearKeysDistanceMap;
@@ -272,6 +278,7 @@
     std::vector<int> mTimes;
     std::vector<float> mDistanceCache;
     std::vector<int>  mLengthCache;
+    std::vector<NearKeycodesSet> mNearKeysVector;
     bool mTouchPositionCorrectionEnabled;
     int32_t mInputCodes[MAX_PROXIMITY_CHARS_SIZE_INTERNAL * MAX_WORD_LENGTH_INTERNAL];
     int mNormalizedSquaredDistances[MAX_PROXIMITY_CHARS_SIZE_INTERNAL * MAX_WORD_LENGTH_INTERNAL];