Evaluating Variable-Length Multiple-Option Lists in Chatbots and Mobile Search

Pepa Atanasova, Georgi Karadzhov, Yasen Kiprov, Preslav Nakov, Fabrizio Sebastiani

This paper, presented at SIGIR 2019, tackles a specific but pervasive problem in modern UX: how do we measure the "goodness" of a chatbot's suggestion list? When a chatbot isn't 100% sure what you want, it often presents a few options (e.g., "Did you mean: A, B, or C?"). The authors argue that traditional search engine metrics fail to account for the unique constraints of mobile screens and conversational flow, and they propose new metrics—LAR and OLAR—to fill the gap.

TL;DR

The authors define a set of mandatory properties for evaluating variable-length suggestion lists in chatbots, proving that traditional metrics like F1 and Average Precision fail to penalize "clutter." They introduce Length-Aware Recall (LAR) and its ranked counterpart OLAR, which perfectly balance the need for accuracy with the need for conciseness.

What Problem Does This Paper Address?

In the "ten blue links" era of desktop search, over-returning results was fine; users just scrolled. But on mobile devices and in chatbots, screen real estate is precious. If a chatbot is uncertain about a user's intent, it might return a list of possible options.

The challenge is a classic trade-off:

  1. Recall: You want the correct answer to be in the list.
  2. Conciseness: You want the list to be as short as possible to avoid "clutter" and user annoyance.

Existing Information Retrieval (IR) metrics (like Precision, Recall, or nDCG) were designed for long lists of documents. They often fail to penalize a system for adding extra, irrelevant options at the end of a short list. This paper seeks to define exactly what makes a "good" evaluation measure for this specific scenario and provides a mathematical framework to implement it.

Methods

The researchers began by defining three "desiderata"—properties that any good metric for this task must satisfy:

  • Correctness: A list containing the correct answer is always better than one that doesn't.
  • Confidence: If two lists both contain the correct answer, the shorter list is better (less clutter).
  • Priority: If two lists have the same length and both contain the correct answer, the one that ranks the correct answer higher is better.

They then tested existing metrics (F1, Average Precision, Reciprocal Rank, etc.) against a "gold ranking" of hypothetical response lists. Finding that none of the standard metrics satisfied all properties—specifically, most failed to penalize extra wrong answers—they proposed two new measures:

  1. Length-Aware Recall (LAR): Designed for unranked sets. It calculates the mean of the recall and the reciprocal of the list length. This explicitly rewards shorter lists.
  2. Ordered Length-Aware Recall (OLAR): An extension of LAR for ranked lists. It adds a third term that accounts for the position of the correct answer, ensuring that "Priority" is respected without outweighing the need for "Confidence" (conciseness).

Datasets

The paper does not use a traditional large-scale training dataset. Instead, it uses a synthetic "gold ranking" benchmark.

The authors generated all possible combinations of response lists with up to 5 items (using 'c' for correct and 'w' for wrong, e.g., [c, w, w]). They then manually ranked these combinations based on their three defined properties. This created a ground-truth sequence used to calculate the Kendall’s Tau and Spearman’s rank correlation for every evaluation metric tested.

Key Insights and Ideas

  • The "Clutter" Penalty: Traditional IR metrics are "too nice." For example, Average Precision (AP) stops calculating once it hits the last relevant document. In a chatbot, if the bot gives you the right answer but then follows it with four pieces of junk, AP doesn't care, but a human user definitely does.
  • Smoothing isn't enough: The authors tried "smoothing" existing metrics (like adding a fake correct answer to the end of every list) to force them to behave. While this improved correlation with the gold standard, it still didn't achieve a perfect ranking.
  • The Importance of Reciprocal Length: By using $1/|r_n|$ (the reciprocal of the list length) as a core component of LAR, the authors created a metric that naturally decays as the list gets longer, mirroring the diminishing returns and increasing annoyance of long suggestion lists.

Key Results

  • Failure of Standards: Popular metrics like nDCG, MRR, and AP all failed the "Confidence" property. They could not distinguish between a perfect single-answer response and a response that included the correct answer plus several wrong ones.
  • Perfect Correlation: Both LAR (for unranked) and OLAR (for ranked) achieved a correlation of 1.0 (Kendall’s Tau and Spearman) with the gold ranking.
  • Mathematical Robustness: The authors demonstrated that OLAR's scaling factor ($\mu$) ensures that the "Priority" of a result never accidentally overrides the "Confidence" (length) penalty, keeping the metric aligned with user preferences for brevity.

Limitations and Future Work

  • Single Intent Assumption: The current metrics assume there is only one "correct" intent for a user's query. In reality, a user might have multiple intents (e.g., "Cancel my card and send a new one").
  • Non-Empty Lists: The paper assumes the system always returns at least one response (even if it's a default "I don't know" intent). It doesn't explicitly model the "no-response" case.
  • Future Directions: The authors suggest extending this work to general mobile search where results must be truncated due to screen size, and adapting the metrics for multi-intent scenarios.

Summary updated

Abstract

In recent years, the proliferation of smart mobile devices has lead to the gradual integration of search functionality within mobile platforms. This has created an incentive to move away from the "ten blue links" metaphor, as mobile users are less likely to click on them, expecting to get the answer directly from the snippets. In turn, this has revived the interest in Question Answering. Then, along came chatbots, conversational systems, and messaging platforms, where the user needs could be better served with the system asking follow-up questions in order to better understand the user's intent. While typically a user would expect a single response at any utterance, a system could also return multiple options for the user to select from, based on different system understandings of the user's intent. However, this possibility should not be overused, as this practice could confuse and/or annoy the user. How to produce good variable-length lists, given the conflicting objectives of staying short while maximizing the likelihood of having a correct answer included in the list, is an underexplored problem. It is also unclear how to evaluate a system that tries to do that. Here we aim to bridge this gap. In particular, we define some necessary and some optional properties that an evaluation measure fit for this purpose should have. We further show that existing evaluation measures from the IR tradition are not entirely suitable for this setup, and we propose novel evaluation measures that address it satisfactorily.
BibTeX
@inproceedings{atanasova2019evaluating,
  author = {Pepa Atanasova and Georgi Karadzhov and Yasen Kiprov and Preslav Nakov and Fabrizio Sebastiani},
  title = {{Evaluating Variable-Length Multiple-Option Lists in Chatbots and Mobile Search}},
  booktitle = {International ACM SIGIR Conference on Research and Development in Information Retrieval},
  year = {2019},
  url = {https://openreview.net/forum?id=tdrF-Op0nS},
}

Loading related content...

Figure