PaperlayerView exact revision on arXiv

Source-linked AI summary

Sequential Decision-Making for Inline Text Autocomplete

Rohan Chitnis, Shentao Yang, Alborz Geramifard

arXiv:2403.15502v2cs.CLcs.HCcs.LG

TL;DR

Fixed-threshold autocomplete does not directly account for the cognitive load of showing suggestions. The paper uses reinforcement learning to select inline suggestions through sequential decision-making, with reward based on text entry speed. Its experiments suggest this approach does not improve speed for an idealized user, prompting a recommendation to focus on real users’ experience.

  • Problem

    Fixed confidence thresholds do not directly account for the cognitive load of reading and deciding whether to accept surfaced suggestions, which can harm user experience when suggestions are frequent.

    Source: §1 · pp. 1–2

  • Method

    The authors formulate inline autocomplete as sequential decision-making and train a reinforcement-learning policy over language-model candidates using a text-entry-speed reward that captures suggestion-related cognitive load.

    Source: §4 · p. 4

  • Results

    The experiments suggest that sequential decision-making and RL do not improve text entry speed for an idealized user.

    Source: §7 · p. 9

  • Takeaways & Limitations

    The authors recommend that future work target real users’ text-entry experience rather than text entry speed alone.

    Source: §1 · p. 2, §7 · p. 10

    The user study used prompted writing tasks, and its results may differ for freeform writing.

    Source: §7 · p. 10

Abstract

from arXiv · show

Autocomplete suggestions are fundamental to modern text entry systems, with applications in domains such as messaging and email composition. Typically, autocomplete suggestions are generated from a language model with a confidence threshold. However, this threshold does not directly take into account the cognitive load imposed on the user by surfacing suggestions, such as the effort to switch contexts from typing to reading the suggestion, and the time to decide whether to accept the suggestion. In this paper, we study the problem of improving inline autocomplete suggestions in text entry systems via a sequential decision-making formulation, and use reinforcement learning to learn suggestion policies through repeated interactions with a target user over time. This formulation allows us to factor cognitive load into the objective of training an autocomplete model, through a reward function based on text entry speed. We acquired theoretical and experimental evidence that, under certain objectives, the sequential decision-making formulation of the autocomplete problem provides a better suggestion policy than myopic single-step reasoning. However, aligning these objectives with real users requires further exploration. In particular, we hypothesize that the objectives under which sequential decision-making can improve autocomplete systems are not tailored solely to text entry speed, but more broadly to metrics such as user satisfaction and convenience.

1 Introduction

Inline autocomplete can speed text entry, but fixed confidence thresholds do not directly account for the cognitive load of viewing and deciding on suggestions. The paper formulates suggestion selection as sequential decision-making and studies when reinforcement learning can improve it.

1 Introduction

  • Fixed-threshold systems do not directly account for the cognitive load of reading and deciding whether to accept a suggestion, and too many suggestions can harm user experience.Inline systems must decide both what to suggest and when to avoid interrupting users’ focus.Source: §1 · pp. 1–2
  • The authors formulate inline autocomplete as sequential decision-making and use reinforcement learning to learn suggestion policies through repeated interactions with a target user.Their reward is based on text entry speed and captures the cognitive load of surfacing suggestions.Source: §1 · p. 2
  • Theoretical and experimental evidence indicates that RL can outperform myopic reasoning under certain objectives, but aligning those objectives with real users requires further exploration.The authors suggest objectives may need to reflect user satisfaction and convenience, not text entry speed alone.Source: §1 · p. 2
  • For an idealized user who accepts correct suggestions and types without typos, the authors found no evidence that RL-trained models improve text entry speed over a fixed-threshold approach.The comparison used a real dataset and language model.Source: §1 · p. 2
  • In a keyboard-typing study with 9 users, suggestion-inspection load depended on whether the suggestion matched the user’s intent, not its length: 10ms for matches and 50ms for mismatches.The study found no evidence that acceptance rate changed with the number of past surfaced suggestions.Source: §1 · p. 2
  • The authors recommend that future work not target text entry speed for idealized users alone, but instead study more realistic scenarios with a focus on user experience.They identify stochastic user behavior and input typos as examples of more realistic conditions.Source: §1 · pp. 2–3

2 Related Work

Prior work covers neural language models for autocomplete, empirical studies of autocomplete systems, and RL approaches to related tasks. This paper uses a neural LM to generate candidates but applies deep RL to select inline suggestions.

2 Related Work

  • Neural language models have been used for query autocomplete, including methods that use context in generation and ranking and models personalized with user IDs.This paper also uses a neural LM for candidate generation, but uses a deep-RL policy for selection.Source: §2 · p. 3
  • Empirical studies report both benefits and costs: autocomplete can reduce word error rate, impair text entry speed while lowering perceived burden, and increase text entered in search.These studies motivate examining cognitive load alongside text entry performance.Source: §2 · p. 3
  • Related RL work studied query autocomplete as a stateless bandit and autocomplete as a two-agent communication game with keyword-only user input.This paper instead adopts an MDP and allows users to enter any English characters.Source: §2 · p. 3

3 Background: Reinforcement Learning

The section introduces reinforcement learning through the Markov decision process framework, where policies seek to maximize expected discounted reward. It also distinguishes common RL algorithm families and offline learning.

3 Background: Reinforcement Learning

  • An MDP specifies states, actions, transitions, rewards, and a discount factor; its optimal policy maximizes expected discounted rewards over an episode.The section defines state-action Q-values as expected returns and state values as the maximum Q-value over actions.Source: §3 · p. 3
  • In RL, an agent interacts with an environment whose transition model and reward are unknown to discover an optimal policy.Policy-gradient methods optimize a policy directly, while value-based methods learn state-action values and infer a policy from them.Source: §3 · p. 3
  • Offline RL learns from a static dataset of prior interactions rather than interacting with the environment.Source: §3 · p. 4

4 Problem Formulation: Autocomplete as Sequential Decision-Making

The formulation builds an MDP over a language model’s candidate completions and lets an agent choose whether to surface one or wait. User and language-model behavior determine transitions, while the reward accounts for time saved or lost and suggestion-related cognitive load.

4 Problem Formulation: Autocomplete as Sequential Decision-Making

  • The MDP state combines the entered text context with the language model’s k candidate completions and their probabilities; actions are to surface one candidate or wait.Increasing k gives the agent more candidates to choose from but also increases problem complexity.Source: §4 · p. 4
  • After each agent action, the user accepts a suggestion or enters a character, then the language model generates candidates from the updated context.In the idealized-user setup, users accept only suggestions matching a prefix of the remaining target sentence and otherwise type without typos.Source: §4 · p. 4
  • The reward is proportional to time saved or lost, with α penalizing suggestion length and β representing a constant gaze-shift cost.For the idealized user, accepted correct suggestions give positive reward, ignored incorrect suggestions give negative reward, and waiting gives zero; the discount factor can strongly influence the optimal solution.Source: §4 · p. 4

5 Theoretical Analysis

The analysis asks when sequential reasoning can outperform myopic autocomplete, then derives conditions under which farsighted and myopic policies differ. In a 500-word language-model test, their disagreement peaked at α between 0.3 and 0.4 but covered only about 2% of states; the analysis’s assumptions may not match real text-entry goals or practical language models.

5 Theoretical Analysis

  • The theoretical study asks whether conditions exist under which sequential decision-making improves on myopic reasoning, holding other MDP components fixed.It compares return at a particular timestep for γ=1 and γ=0.Source: §5 · p. 4

5.1 Analysis Setup

  • The setup uses two equally likely words sharing their first m letters, with an idealized user and one candidate; the analysis seeks parameters where γ=1 waits and γ=0 suggests.The language model provides the non-target word through m entered letters and the target word afterward.Source: §5.1 · p. 5

5.2 Derivation for γ = 0

  • For γ=0, suggesting at position m is preferred when (n −m)(0.5 −α) −β > 0.Source: §5.2 · p. 5

5.3 Derivation for γ = 1

  • For γ=1, waiting at position m is preferred when (n −m + 1)α + β > 1.The farsighted Q-value expressions are recursive because they include lookahead.Source: §5.3 · pp. 5–6

5.4 Final Constraints on α and β

  • At position m, policies can differ when (n −m)(0.5 −α) −β > 0 and (n −m + 1)α + β > 1; disagreement peaked at α=0.3–0.4 but covered only ∼2% of states.The empirical comparison used the most likely 500 words from the language model and β=60/521.Source: §5.2 · p. 5, §5.4 · p. 6, §5.3 · p. 6

5.5 Limitations of our Analysis

  • The analysis’s constraints may not reflect text-entry speed: the user study found faster-entry values of α and β near zero, and the analysis used a simple language model unlikely to match practice.Whether sequential decision-making benefits autocomplete depends on the user’s goal and the language model used to implement the MDP.Source: §5.5 · p. 6

6 Experiments

The experiments compare RL autocomplete policies with threshold-based systems in simulations and examine how real users respond to suggestions. With reward parameters estimated from the user study, the threshold baseline always suggests, while the study finds cognitive load depends on correctness rather than suggestion length.

6.1 Experimental Setup

  • The setup used SMS and Reddit sentences, a roughly 25 MB transformer, and simulations assuming an idealized user; IQL trained on 5,000 threshold-policy trajectories with 5% random actions.Sentences were filtered for length, profanity, perplexity, and allowed characters.Source: §6.1 · p. 7, §6.2 · p. 7

6.2 Computational Experiments

  • For k = 1, IQL reached 9.37 ± 0.17 average return versus 9.27 ± 0.18 for the threshold agent, with no significant improvement over that baseline.PPO saved the most characters but earned lower return because it made more incorrect suggestions.Source: §6.2 · p. 7, Figure 3 · p. 8
  • At α = 0.4, PPO with γ = 0.99 achieved 3.14 ± 0.27 return versus 2.65 ± 0.16 with γ = 0, but remained below IQL and the threshold agent.The difference was significant after 1M training steps.Source: Figure 4 · p. 8, §6.2 · p. 8
  • Allowing one- or two-word candidates degraded return for both oracle and threshold agents and reduced the oracle’s saved characters, so RL agents were not trained in this setting.Two-word candidates could displace the correct one-word candidate from the available pool.Source: §6.2 · p. 8

6.3 User Study

  • Cognitive load did not grow significantly with suggestion length, but differed significantly between correct and incorrect suggestions.The study measured load as the time difference to enter the next key with versus without suggestions.Source: Figure 5 · p. 9, §6.3 · p. 9
  • The study found no evidence that acceptance rate declined with the cumulative number of surfaced suggestions or incorrect suggestions.Nine users entered 42 sentences on a keyboard, with and without autocomplete.Source: §6.3 · pp. 8–9
  • With user-study-based parameters, the optimal threshold was 0, and RL did not improve text-entry speed for the idealized user.The threshold-based agent always surfaced the top language-model candidate, regardless of probability.Source: §6.3 · p. 9

7 Conclusion and Future Work

The paper finds that RL and sequential decision-making do not improve text-entry speed for an idealized user. It recommends exploring objectives tied to real users’ enjoyment and notes that future studies should test more realistic writing and simulation conditions.

7 Conclusion and Future Work

  • Experimental findings suggest RL and sequential decision-making do not improve text-entry speed for an idealized user.The authors recommend that future work target real users’ enjoyment rather than speed alone.Source: §7 · pp. 9–10
  • The user study used prompted writing, and the authors suggest freeform writing could produce different results.They also identify more realistic simulations—including stochastic acceptance, typos, and semantic matching—as future directions.Source: §7 · p. 10

A Reward Derivation

The reward is designed to minimize total text-entry time by crediting accepted suggestions for saved writing time and penalizing reading and distraction costs.

A Reward Derivation

  • The objective minimizes total user entry time by rewarding saved writing time and subtracting cognitive-load costs from surfaced suggestions.The reward is proportional to the time saved by an accepted correct suggestion minus the time lost to cognitive load.Source: A Reward Derivation · p. 12
  • The reward credits accepted suggestions by their length times character-writing time, then subtracts reading time and a fixed distraction cost for each nonempty suggestion.The expression treats an empty suggestion as imposing no fixed distraction cost.Source: A Reward Derivation · p. 12
  • The estimates use 521 ms per written character, 40 ms per read character, and 60 ms of distraction per suggestion, yielding α = 40/521 and β = 60/521.The distraction estimate is two 30 ms saccades; writing and reading estimates come from an internal EMG-handwriting dataset.Source: A Reward Derivation · p. 13

B Further Details on Computational Experiments

The computational experiments use PPO, DQN, and IQL agents, and the multi-word experiment normalizes language-model probabilities to compare suggestions of different lengths.

B Further Details on Computational Experiments

  • PPO and DQN score each candidate suggestion or wait with a state-and-candidate Q-network, while IQL uses an MLP with one output per action; all agents train for 250K steps.PPO and DQN use DistilBERT with a projection MLP and require k + 1 forward passes per action choice.Source: B Further Details on Computational… · p. 13
  • The default PPO, DQN, and IQL settings use discount factor 0.99, with distinct learning rates and agent-specific training hyperparameters.PPO uses learning rate 10^-6, DQN 3 · 10^-7, and IQL 3 · 10^-4.Source: B Further Details on Computational… · p. 13

C Multi-Word Suggestion Length Normalization

  • For multi-word suggestions, the experiment replaces raw language-model probabilities with normalized probabilities to counter the lower joint likelihood of longer suggestions.The normalized probability is based on the geometric mean of the conditional probabilities across the m words; for m = 1, it equals the raw probability.Source: C Multi-Word Suggestion Length… · pp. 13–14
  • In the example context “finally,” normalization assigns “entine’s day” 33%, “ue” 32%, and “entine’s” 17%, allowing the two-word completion to outrank its first word alone.Without normalization, the joint probability of the two-word suggestion cannot exceed the probability of its first word.Source: C Multi-Word Suggestion Length… · p. 14

D Why Does Incorporating 2-Word Suggestions Harm the Oracle?

Two-word candidates can displace a correct one-word candidate from the agent’s top-k choices, harming even an oracle that knows the target sentence.

D Why Does Incorporating 2-Word Suggestions Harm the Oracle?

  • Two-word suggestions can occupy candidate slots that would otherwise contain the correct one-word suggestion, reducing even the oracle agent’s performance.The oracle has privileged access to the target sentence and does not make wrong suggestions that users ignore.Source: D Why Does Incorporating 2-Word… · p. 14
  • With k = 5, the correct candidate “eat” ranked sixth behind five unmatched completions, so the oracle waited instead of earning positive reward.Without the unmatched two-word candidates, “eat” would have appeared among the five options.Source: D Why Does Incorporating 2-Word… · p. 14

E Cognitive Load User Study - Extended Results

The extended results show cognitive-load measurements by suggestion correctness and acceptance rates against cumulative suggestion counts.

E Cognitive Load User Study - Extended Results

  • Figure 6 reports cognitive load for all suggestions, correct suggestions, and incorrect suggestions in three separate columns.It includes N = 9 subjects, with averages and 95% confidence intervals above the individual datapoints.Source: Figure 6 · p. 15
  • Figure 7 plots acceptance rate against the cumulative number of past suggestions and past incorrect suggestions.The two series are blue for all past suggestions and orange for past incorrect suggestions; error bars show 95% confidence intervals.Source: Figure 7 · p. 15
  • The Figure 7 data showed no evidence that acceptance rate declined with the cumulative number of surfaced or incorrect suggestions.The authors therefore found no evidence for the accumulated fatigue hypothesis.Source: Figure 7 · p. 15
Loading 2403.15502v2…