# US 2025/0156451 A1 · Language model decoding for search query completion > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 2025/0156451 A1 - Document ID: US20250156451A1 - Status: Published application - Kind: A1 - Application number: 18/510,565 - Filed: 2023-11-15 - Published: 2025-05-15 - Earliest claimed: 2023-11-15 - Assignees: Maplebear Inc. - Applicants: Maplebear Inc. - Inventors: Jacob Jensen; Fei Jia; Esther Vasiete Allas; Manmeet Singh; Lee Cohn; Tejaswi Tenneti - Web page: https://patentgrep.com/patent/US20250156451A1 ## CPC - G06F 16/3322: {using system suggestions (G06F16/3325 takes precedence)} - G06F 40/284: Lexical analysis, e.g. tokenisation or collocates - G06F 40/40: Processing or translation of natural language (natural language analysis G06F40/20; semantic analysis G06F40/30) - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract A language model is used to generate autosuggestions to complete or revise a user's partial search query. An initial partial query is applied to the language model to generate query candidates for completing the search query. The language model may generate the query candidates as additional or alternate tokens for the partial search query. When the user revises the partial query, the previously-generated candidates can be re-used to reduce subsequent processing time for generating additional candidates. The previously-generated candidates are compared with the revised partial query to select which of the candidates to be re-used and expanded for generating additional tokens. Additional tokens can be generated in parallel for the previously-generated candidates or with model values from the previous generation, enabling the tokens to be generated effectively with reduced latency consistent with user expectations for search-related autosuggestions. ## Claims ### Claim 1 A method, performed at a computer system comprising a processor and a computer-readable medium, the method comprising: receiving, from a user device, an initial partial search query, wherein the initial partial search query is entered by a user via a user interface displayed on the user device, and wherein the user interface is further configured to receive a search query; generating a first set of query candidates with a language model based on the initial partial search query; sending, to the user device, at least one of the first set of query candidates for display to the user in the user interface, wherein sending the at least one of the first set of query candidates for display to the user in the user interface makes the at least one of the first set of query candidates available for selection as the search query; receiving a revised partial search query entered by the user on the user interface after the initial partial search query; selecting a set of maintained query candidates from the first set of query candidates based on similarity of the first set of query candidates with respect to the revised partial search query; generating a second set of query candidates with the language model based on expansion of the set of maintained query candidates; and sending, to the user device, at least one of the second set of query candidates for display to the user in the user interface, wherein sending the at least one of the second set of query candidates for display to the user in the user interface makes the at least one of the second set of query candidates available for selection as the search query. ### Claim 2 (depends on 1) The method of claim 1, wherein generating the second set of query candidates comprises applying the language model in parallel instances to the set of maintained query candidates. ### Claim 3 (depends on 1) The method of claim 1, wherein generating the second set of query candidates with the language model based on expansion of the set of maintained query candidates comprises applying model values of the maintained query candidates from the first set of query candidates. ### Claim 4 (depends on 1) The method of claim 1, wherein selecting the set of maintained query candidates comprises scoring the first set of query candidates based on embedding similarity with the revised partial search query. ### Claim 5 (depends on 1) The method of claim 1, wherein generating the first set of query candidates comprises selecting the first set of query candidates based on a search space for executing the search query. ### Claim 6 (depends on 5) The method of claim 5, wherein the search space comprises an item inventory. ### Claim 7 (depends on 1) The method of claim 1, wherein the language model comprises a transformer model. ### Claim 8 A computer program product comprising a non-transitory computer readable storage medium having instructions encoded thereon that, when executed by a processor, cause the processor to perform steps comprising: receiving, from a user device, an initial partial search query, wherein the initial partial search query is entered by a user via a user interface displayed on the user device, and wherein the user interface is further configured to receive a search query; generating a first set of query candidates with a language model based on the initial partial search query; sending, to the user device, at least one of the first set of query candidates for display to the user in the user interface, wherein sending the at least one of the first set of query candidates for display to the user in the user interface makes the at least one of the first set of query candidates available for selection as the search query; receiving a revised partial search query entered by the user on the user interface after the initial partial search query; selecting a set of maintained query candidates from the first set of query candidates based on similarity of the first set of query candidates with respect to the revised partial search query; generating a second set of query candidates with the language model based on expansion of the set of maintained query candidates; and sending, to the user device, at least one of the second set of query candidates for display to the user in the user interface, wherein sending the at least one of the second set of query candidates for display to the user in the user interface makes the at least one of the second set of query candidates available for selection as the search query. ### Claim 9 (depends on 8) The non-transitory computer readable storage medium of claim 8, wherein generating the second set of query candidates comprises applying the language model in parallel instances to the set of maintained query candidates. ### Claim 10 (depends on 8) The non-transitory computer readable storage medium of claim 8, wherein generating the second set of query candidates with the language model based on expansion of the set of maintained query candidates comprises applying model values of the maintained query candidates from the first set of query candidates. ### Claim 11 (depends on 8) The non-transitory computer readable storage medium of claim 8, wherein selecting the set of maintained query candidates comprises scoring the first set of query candidates based on embedding similarity with the revised partial search query. ### Claim 12 (depends on 8) The non-transitory computer readable storage medium of claim 8, wherein generating the first set of query candidates comprises selecting the first set of query candidates based on a search space for executing the search query. ### Claim 13 (depends on 12) The non-transitory computer readable storage medium of claim 12, wherein the search space comprises an item inventory. ### Claim 14 (depends on 8) The non-transitory computer readable storage medium of claim 8, wherein the language model comprises a transformer model. ### Claim 15 A system comprising: one or more processors that execute instructions; and a non-transitory computer-readable storage medium having instructions executable by the processor for: receiving, from a user device, an initial partial search query, wherein the initial partial search query is entered by a user via a user interface displayed on the user device, and wherein the user interface is further configured to receive a search query; generating a first set of query candidates with a language model based on the initial partial search query; sending, to the user device, at least one of the first set of query candidates for display to the user in the user interface, wherein sending the at least one of the first set of query candidates for display to the user in the user interface makes the at least one of the first set of query candidates available for selection as the search query; receiving a revised partial search query entered by the user on the user interface after the initial partial search query; selecting a set of maintained query candidates from the first set of query candidates based on similarity of the first set of query candidates with respect to the revised partial search query; generating a second set of query candidates with the language model based on expansion of the set of maintained query candidates; and sending, to the user device, at least one of the second set of query candidates for display to the user in the user interface, wherein sending the at least one of the second set of query candidates for display to the user in the user interface makes the at least one of the second set of query candidates available for selection as the search query. ### Claim 16 (depends on 15) The system of claim 15, wherein generating the second set of query candidates comprises applying the language model in parallel instances to the set of maintained query candidates. ### Claim 17 (depends on 15) The system of claim 15, wherein generating the second set of query candidates with the language model based on expansion of the set of maintained query candidates comprises applying model values of the maintained query candidates from the first set of query candidates. ### Claim 18 (depends on 15) The system of claim 15, wherein selecting the set of maintained query candidates comprises scoring the first set of query candidates based on embedding similarity with the revised partial search query. ### Claim 19 (depends on 15) The system of claim 15, wherein generating the first set of query candidates comprises selecting the first set of query candidates based on a search space for executing the search query. ### Claim 20 (depends on 19) The system of claim 19, wherein the search space comprises an item inventory.