Combating Missed Recalls in E-commerce Search: A CoT-Prompting Testing Approach

Both subjective and objective factors are considered to confirm a missed recall. More importantly, the factors considered vary according to different missed recalls. Here we summarize several significant factors.

• •

  Reasonableness of the query: As the search component is designed for human usage, confirmed missed recalls can only be induced by human-perceively reasonable queries. In practice, a query should align with how general users express shopping needs and convey explicit intention towards the target shop. For example, if a shop named lovely pets located 100 meters east of Becker street post office can not be retrieved by the query100 meters east of Becker street post office, it is not a missed recall. General users usually do not express their shopping needs towards a pet store in that fashion. However, how shopping intentions are expressed involves the subjectivity of human nature, which can hardly be encoded into definite rules.

• •

  The geography: Distance affects search results. Shops far away have lower priority during retrieval at the M-App. Hence, long distances may cause false positives of missed recall.

  

• •

  Operating status: Usually, only open shops will be retrieved by most e-commerce apps. If a certain shop is closed when a user initiates a search towards it in the M-App, it is normal that it can not be retrieved.

• •

  Ordering strategies: To enhance user experience, e-commerce apps incorporate multiple ordering strategies, affecting the search results. For example, if a user searches for hotpot, those shops offering discounts due to sales promotion may be prioritized during retrieval. Given the fixed number of shops exposed to users, a false impression of missed recall may be presented. To give another example, administrative punishment, lowering the priority in retrieval, works similarly.

• •

  Others: User preferences and click-through history of the user affect search results as well. Those factors may also create false impressions of missed recalls.

The above findings demonstrate the complication of identifying missed recall and further prove the oracle problem faced by testing towards missed recalls automatically and proactively. However, despite the complicated standards, general users manage to report missed recalls, with limited knowledge about the operational strategy of the corporation. Hence, we present how general users manage to identify missed recalls and use these findings to inspire our method design.

On reporting missed recalls, users typically compare the search results of multiple queries towards the same target shop. Accounting for all confirmed user-reported missed recalls (around 80³³3We purposely omit the actual number for protection of the operational status of the corporation.), about 3 queries are constructed for the same shop averagely. Without much knowledge about the confirmation standards used in the corporation, users report missed recalls only when those queries return inconsistent search results. For example, 3 queries are constructed for one target shop, and two queries can recall this shop but one can not. Then, this user reports a missed recall.

After analyzing all queries involved in the user-reported missed recalls we study (over 200 queries ^††footnotemark: ), we obtain 2 observations. We observe user queries are diverse and prone to the personal style of expression, which rules can hardly mimic, but what users consider when constructing queries remains stable.

To illustrate the subjectivity and diversity of user queries, we demonstrate the following three types of queries as examples.

• •

  Equivalent queries. In concept, the queries are basically the equivalents of the shop name. For example, hardware Chen’s is an equivalent query for the shop Chen’s hardware.

• •

  Including queries. Including queries conceptually include the target shop. For example, Indian Restaurant is an including query for the shop Ali’s curry house.

• •

  Included queries. Included queries are conceptually included by the target shop. For example, spicy hotpots is an included query for a restaurant serving spicy and non-spicy hotpots.

Unlike user queries, diverse and subjective, what users consider when constructing queries remains relatively stable. Here we present prominent information types users consider when constructing queries.

• •

  Shop name. Users usually take the full name of the shop, characters from the full name of the shop and initials of the shop as queries. For example, given a target shop Ma’s burgers, users may also search for Ma’s and hamburgers.

• •

  Products/ services the shop offers. Users also search for a certain shop by the products or services it offers, like hotpot, haircut and pedicures.

• •

  Geographic location of the shop. Users may avoid typing the shop’s exact name due to cognitive workload. So they search vaguely by geographic location and construct queries like hotpot People’s square and dumplings nearby.

In summary, findings from the reported missed recalls substantiate the challenges of testing targeting missed recalls and user practices also hint at solutions. Constructing multiple queries towards the same shop and comparing the search results inspires us to consider metamorphic testing to overcome the oracle problem. Subjectivity of human nature leads to diverse queries, which inspires us not to rely on pure rules, but to incorporate subjective factors of humans in test case generation. As users typically consider shop names, services and products the shop provides and the location of the shop when constructing queries, we can use shop names and shop types as input data for test case generation. For shop names and shop types include the three types of information.

In this step we generate test cases/queries automatically by the LLM. As we use a metamorphic relation to provide test oracle, our test cases (essentially user queries) must: (1) be real enough, approximating to user-constructed ones; (2) support the metamorphic relation. To generate real test cases, we leverage the ability of the LLM instead of traditional NLP techniques. LLMs are trained with a large corpus of natural languages, implicitly conveying how humans express their shopping needs and interact with search components. It is reasonable to assume that given the information needed, the LLM could generate queries that approximate what users search with on the search component. After trading off the costs and base abilities, we choose GPT-3.5 turbo for query generation. To support the metamorphic relation, we generate a group of test cases/queries for one shop instead of a single test case/query. Those queries all target the same shop and express search intention towards it.

We tailor the prompt to mimic how general users construct queries during their search behavior. According to what information general users consider when constructing queries, we take shop names and shop types as the input. The shop names also include information about where the shop is located. To leverage the ability of LLM to generate queries close to what general users construct during searching, we use a series of techniques, including in-context learning(Min et al., 2022), CoT(Zhang et al., 2022), question-answering examples (Brown et al., 2020) and human in the loop(Ge et al., 2023).

We first break the query generation process of general users (illustrated in section  3.2) into three steps (shop name based generation, services/products based generation and location based generation) according to the information types they consider. Then we accordingly implement the three steps into the prompt with the CoT technique. Next we use the in-context learning technique to provide domain knowledge about our specific task and include multiple examples in the prompt. As LLMs benefit from examples in a question-answer format in the prompt (Brown et al., 2020), all examples are provided in the question-answer format. To ensure the quality of all the examples in the prompt, we randomly sample from real user queries of Meituan and manually revise them to achieve consistency in our scenario. We also use human evaluation to substitute all examples that general users think ”not real enough” due to revision. Finally, we use the human-in-the-loop technique and iteratively improve our prompt based on the human feedback on the quality of the queries generated. We stop the iteration process until no unreal ones are found in randomly sampled 50 generated queries. Our final prompt consists of four parts: (1) target shops and shop types; (2) descriptions of the task; (3) the CoT process of query generation; (4) example search queries. The prompt is written in Chinese, as the input data are also in Chinese. Figure  3 provides a simplified demonstration of our prompt. For privacy concerns, the shop information and example queries presented are desensitized.

Due to hallucination issues, LLMs may generate unreliable content despite the customized CoT prompt to ensure generation quality. For example, the query a barber is generated for the target shop, a hairdressing salon. Another example is supermarket near A for the target shop A supermarket, which confuses A as a location.

Those test cases are human-perceively unreasonable but can not be detected by traditional techniques. For example, the a barber scenarios would achieve high semantical similarity scores and the supermarket near A scenarios would achieve high textual matching scores.

Hence, we leverage a rethink scheme (Liu et al., 2023) to reduce false positives induced by unreasonable test cases in the test case validation step. Specifically, given the name and type of the target shop and the generated test case, we call the LLM again to re-think the generated test cases and drop ones that do not align with how general users express their shopping needs. The rationale is that multiple trials with the LLM decrease the probability of unreliable responses incurred by hallucination. Only test cases validated as resonanble are kept for the next step. The prompt used for test case validation follows the few-shot strategy. Multiple examples, both reasonable test cases to be kept and unreasonable test cases to be dropped, are included in the prompt.

In this step, we determine whether a certain test case incurs a missed recall by consistency checks. We propose the metamorphic relation that test cases generated for one target shop should present consistent search results. Violations of this metamorphic relation indicate missed recalls. Hence, the test oracle is formally expressed below.

Given test cases $X_{1},X_{2},\ldots,X_{n}$ for a target shop $t$, the function $R(X)$ represent search results recalled by $X$ . Formally, for any $X_{n}$, we define $y_{n}$ as follows:

The oracle suggests a potential missed-recall when, for any pair $i,j$ where $1\leq i,j\leq n$, we have $y_{i}\neq y_{j}$.

We report test cases that do not recall the target shops as those incurring missed recalls only when other test cases with the same target shop can recall it. To prevent false positives, we are particularly cautious about the situation that all test cases towards a specific shop can not recall the target shop. For example, if a shop decides to cease its business cooperation with an e-commerce app, whatever user queries you try on the search component of that app can not recall this shop. Those situations should not report missed recalls.

In implementation, an internal test API that provides the same functionalities to the search component is used to get all search results. As shown in section  3.1, apart from the query, many other factors also affect the search results of search components in e-commerce apps. To prevent false positives, we use the same user account to ensure the same user profiling and change the location of searches to the accurate geographic locations of the target shops to prevent the explainability of long distances. We also conduct searches during the time slot of 10 am. to 9 pm., when most shops are open, which prevents the explainability of shop status.

Datasets. We use two datasets to evaluate the performance of mrDetector.

• •

  Dataset A: Dataset A is a manually constructed open-access dataset consisting of 600 entries of shops. The shop entries are collected via the Baidu Map API⁴⁴4https://api.map.baidu.com/place/v2/search, which returns nearby shops given a geographic location. We randomly sampled these shops from all shops in Beijing and Shanghai via the API in November 2023. Those 600 entries cover most daily life services, including hairdressing, skin care, nail polishment and catering. We believe such diverse shop types could unveil the ability of mrDetector to detect general missed recalls, avoiding the possibility that mrDetector overfits on a certain shop type.

• •

  Dataset B: 600 entries of shops randomly sampled from the business partner table of Meituan. This table records all shops that have established business cooperation with Meituan. The shop types are in line with that of Dataset A. Dataset B is a dataset of real business data.

Dataset A and Dataset B employ the same data format and are all in Chinese. As shown in Table 1, we demonstrate how each shop is presented in each entry with a mock shop.

Metrics. We use Reported Cases ($N_{reported}$), Confirmed Cases ($N_{Confirmed}$), False Positive Ratio ($R_{fp}$), and Test Case Efficiency ($E_{tc}$) to measure the performance of mrDetector.

$N_{Reported}$ and $N_{Confirmed}$ describe the benefit side of mrDetector. $N_{reported}$ measures how many missed recalls are reported by mrDetector. Higher $N_{reported}$ indicates stronger ability to discover missed recalls. $N_{Confirmed}$ measures how many reported missed recalls are confirmed by human. Higher $N_{Confirmed}$ indicates higher accuracy of mrDetector. We present $N_{Reported}$ and $N_{Confirmed}$ both entry-wise and shop-wise. $R_{fp}$ and $E_{tc}$ describe the cost side of mrDetector, and are calculated as:

where $N_{Total}$ refers to the total number of test cases/queries during one round of test. Lower $R_{fp}$ indicates less human efforts incurred by false positives in confirming. $E_{tc}$ measures the average number of test cases needed to find a confirmed missed recall. Lower $E_{tc}$ hints a smaller number of test cases needed to find the same amount of missed recalls and hence a higher test efficiency. $R_{fp}$ and $E_{tc}$ are reported entry-wise.

Experimental environment. We implement mrDetector with 612 lines of Python codes. All experiments are conducted on an Ubuntu 20.04 server with Intel (R) Xeon (R) Platinum 8175M CPU (2.50GHz), 48GB RAM and two NVIDIA GeForce RTX 4090 GPUs (210MHz).

Manual Confirmation Procedure. Manual confirmation of reported missed recalls requires examining the reasonableness of test cases, which is prone to the subjectivity of the conductor. During confirmation, two authors first independently confirm reported missed recalls. Then, they solve differences by discussing and consulting a third party. We believe such a cross-validating procedure curbs the effects of human subjectivity on confirmation results.

Baselines. mrDetector use GPT-3.5 turbo, which is estimated to have over 100B parameters (Ye et al., 2023), to conduct test case generation. Here we compare the performances of mrDetector with LLMs of different parameter sizes to unveil how the selection of the LLM affects the performance. Besides mrDetector, we implement three baseline methods with three LLMs of different parameter sizes.

• •

  GPT-Neo Version: mrDetector implemented with GPT-Neo. GPT-Neo (Black et al., 2021) is a pre-trained language model following the transformer architecture. According to the official document, it has around 2.6B parameters.

• •

  ChatGLM2 Version: mrDetector implemented with ChatGLM2. ChatGLM2 is an open bilingual language model based on General Language Model framework (Du et al., 2022). It leverages both the Chinese and English languages and has approximately 6B parameters.

• •

  Qwen Version: mrDetector implemented with Qwen 14-B. It  (Bai et al., 2023) is a 14B-parameter version of the large language model series, Qwen (abbr. Tongyi Qianwen), proposed by Alibaba Cloud.

Results. We answer RQ1 with Dataset A. As demonstrated in Table  2, comprehensively mrDetector performs best with GPT-3.5 turbo, which has the largest parameter size. Specifically, on the cost side mrDetector only reports one false positive and only needs 80.95 test cases to discover a confirmed missed recall with GPT-3.5 turbo. This achieves the best among all LLMs concerned. On the benefit side, mrDetector built on GPT-3.5 turbo shows a comparable ability with that built on Qwen, which performs best with benefit metrics.

According to the results in Table 2, a conclusion could be loosely drawn that larger parameters benefit the performance of mrDetector. Analysis with false positives also confirms this conclusion. Test cases not in line with what general users search with on e-commerce apps are the most significant reason for incurring false positives. Chat-NEO, which has the minimal-sized parameters, often outputs random characters or emojis that hardly convey search intentions toward the target shops. Chat-GLM2 and Qwen do not output random characters but sometimes fail to catch the subjective way general users express shopping needs via user queries. For example, in the Chinese language context, a seafood joint usually refers to where sells raw seafood. While a seafood restaurant instead refers to a restaurant that sells seafood dishes. So general users seldom use seafood joint to search for a seafood restaurant on e-commerce apps. GPT-3.5 turbo, which has the maximal-size parameters, only generates one test case that is not real enough. Analysis with false positives may also partially explain why mrDetector build on Qwen performs best with benefit metrics. Qwen includes a larger ratio of Chinese corpus in the training data. Hence, it may enjoy advantages in dealing with Chinese input data.

Baselines. mrDetector uses a customized CoT prompt to generate test cases that both align with users’ search behavior and support our metamorphic relation. Here we investigate how different prompt engineering strategies affect the performance of mrDetector. Besides mrDetector, we implement two baseline methods with two different prompt engineering strategies.

• •

  Few-shot Version: mrDetector implemented with a standard few-shot prompt and GPT-3.5 turbo. The standard few-shot prompt includes all examples in the customized CoT prompt, but no hints about the steps of test case generation are provided.

• •

  Zero-shot Version: mrDetector implemented with a standard zero-shot prompt and GPT-3.5 turbo. Only textual descriptions of the generation task are included in the zero-shot prompt. No examples and hints about the steps of test case generation are provided.

Results. We answer RQ2 with Dataset A. As demonstrated in Table  3, comprehensively mrDetector performs best with the customized CoT prompt. mrDetector implemented with a standard few-shot prompt generates far more test cases than that implemented with the zero-shot prompt and customized CoT prompt. Hence, it is reasonable that it reports the most missed recalls. Judging from the benefit side, the few-shot version discovers around three times more missed recalls than the customized CoT prompt version. However, judging from the cost side, it reports over 30 times more false positives than the customized CoT prompt version. Trading off costs and benefits, comprehensively, the customized CoT prompt achieves the best performance with its significantly low $R_{fp}$.

We develop two assumptions based on the above observation and analysis with test cases generated. Firstly, examples in the prompt may increase the number of test cases generated. Examples are materials that the LLM can learn from and mimic, hence may inspire more generation results. This partially explains why the few-shot version generates the most test cases. Secondly, the steps stating how a generation task should be solved and contained in the customized CoT prompt may guide how the LLM thinks. So, how the LLM generates test cases may approximate how general users construct queries, and hence less test cases, especially unreal test cases, are generated. This assumption partially explains why the customized CoT prompt version archives the lowest $R_{fp}$, six times lower than the second lowest.

Baseline. To reduce the impact of hallucination issues, mrDetector leverage a rethink scheme and call the LLM again to validate the generated test cases. To illustrate how effective this LLM validation step is, we implement the Without LLM Validation Version of mrDetector as the baseline. Except for omitting the LLM validation step, no further changes are made.

Results. We answer RQ3 with Dataset A. As shown in Table 4, the LLM validation step significantly reduces the false positive ratio (3.28 times). ALL false positives the validation step prevents are due to edge cases not aligning with how general users search on e-commerce apps. For example, Shanghai [space] restaurant is generated for a restaurant serving Shanghai Cuisine. However, in the Chinese context, this test case is generally interpreted as restaurants in Shanghai, instead of Shanghai Cuisine Restaurants. This edge case, which can not be easily detected by traditional techniques like semantic similarity and textual mating, proves an LLM validation step is necessary.

This validation step with LLM helps reduce the count of missed recalls that were reported and confirmed due to our cautious approach in the experiment. When the LLM cannot provide a clear decision for test cases, we consider them as failing the LLM check step. This experimental approach reduces the number of test cases and consequently lowers the count of reported missed recalls.

To show how well mrDetector works in real industries, we use Dataset B, which contains actual industry data. This data, handled by different departments, is often untidy. While doing well with open data can demonstrate algorithmic strengths, it doesn’t guarantee success in real industrial scenarios, where results are affected by both algorithms and other factors.

Results. In total, 6396 test cases are generated by mrDetector. 118 entries of missed recalls (involving 91 shops) are reported. After human confirmation, 101 entries (involving 76 shops) are confirmed. The $R_{fp}$ is 0.144, which means false positives take 14 percent of human efforts during confirming. The $E_{tc}$ reaches 63.327. This demonstrates that on average 63 test cases are needed to find a confirmed missed recall.

Revisiting the results of RQ1 to RQ3, we find mrDetector generates more test cases and finds more missed recalls with industrial data. One possible explanation is that the customized CoT prompt is inspired by the historical missed recalls, which are based on real industrial data. This may benefit the performance of mrDetector in a real industrial setting.

We also find that mrDetector reports more false positives with real industrial data. During confirmation, we find those false positives are incurred not only by unreal test cases (the same as in RQ1, RQ2, and RQ3) but also by the quality of the input data. Although not common, it exists that the shop type provided is reasonable but too broad to describe a shop from the subjective aspects of humans. For example, a shop curing nail fungus often is not considered a nail polish center by general users, although it does deal with nails.

Effective as mrDetector is in detecting online missed recalls, according to engineers in charge, it can further help reduce future missed recalls if it reports missed recalls that are reproducible on the phone. To prepare fixes, the first step for engineers is to reproduce those missed recalls on the phone and analyze their impact on the user experience. Hence, although reproducibility does not compromise the effectiveness, it increases the handiness of mrDetector in a real industrial setting. To this end, we randomly sample 15 confirmed missed recalls and manually reproduce them on a mobile phone. Specifically, we search for the same test cases/user queries on the M-App installed on an iPhone 13, and check whether the same missed recalls appear. During the searches, we roughly change the geographic location by filling in the nearest landmark buildings to the target shops. Over half (8/15) of missed recalls can be reproduced. After analyzing those that can not be reproduced, we find the most prominent reason lies in the outdatedness of the target shop information. Some shops no longer exist but they haven’t been erased from the business partner table. So, they are taken as target shops during the test. This explains 4 out of 7 missed recalls that can not be reproduced. This reproduction experiment further illustrates the handiness of mrDetector, besides its effectiveness in detecting missed recalls.

General users construct natural language queries to express their search intentions. The search component first segments the query and decides which part conveys the main search intention. For some user queries like Fresh**de SPA, where the two parts both carry important information about the user’s intention, choosing a main part might be tricky. For example, if the search component takes Fresh**de as the part mainly carrying user search intentions, shops whose title contains the characters Fresh**de could be recalled. In this case, as shops like Fresh**de Laundry and Fresh**de Massage exist nearby, the shop Fresh**de Healthy SPA may be neglected. Hence, a missed recall occurs.

Some shop names contain locations. When a user wants to search for that shop on an e-commerce app, often a phrase referring to a location will be contained in the user query. When the search component gets this query, it must decide whether this location phrase specifies the location of the target shop or only states the name of the target shop. This judgment may lead to missed recalls. For example, there’s a shop named F**’s Seafood Barbecue (Fangbang). When searching with Barbecue Fangbang, the search component may loosely translate this query as find barbecue shops located at Fangbang. As so many barbecue shops exist at Fangbang and only several of them can be presented to users, it is possible, although rare, that the shop F**’s Seafood Barbecue (Fangbang) didn’t get recalled. Hence, a missed recall occurs.