H erm E s: Interactive Spreadsheet Formula Prediction via Hierarchical Formulet Expansion (2023)

Abstract: We propose HermEs, the first approach for spreadsheet formula prediction via HiEraRchical forMulet ExpanSion, where hierarchical expansion means generating formulas following the underlying parse tree structure, and Formulet refers to commonly-used multi-level patterns mined from real formula parse trees. HermEs improves the formula prediction accuracy by (1) guaranteeing correct grammar by hierarchical generation rather than left-to-right generation and (2) significantly streamlining the token-level decoding with high-level Formulet. Notably, instead of generating formulas in a pre-defined fixed order, we propose a novel sampling strategy to systematically exploit a variety of hierarchical and multi-level expansion orders and provided solid mathematical proof, with the aim of meeting diverse human needs of the formula writing order in real applications. We further develop an interactive formula completion interface based on HermEs, which shows a new user experience in https://github.com/formulet/HERMES .

## introduction hundreds of millions of people use spreadsheets, such as excel and google sheets, for data storage and management. the semi-structured context infers potential relations among data in cells. users can add formulas in their spreadsheets to process and analyze data based on such relations. although spreadsheet formula language targets general users and is much simpler than programming languages like c++, it is still difficult for most excel users without any programming experience to master. to write a formula for a cell, users need to find appropriate formula functions, such as if and subtotal, compose them with correct grammar, and fill in proper values and cell references. this process could be time-consuming and error-prone. for computers, spreadsheet formula prediction is also a challenging task, which requires understanding both textual and numerical data, diverse table structures, and relationships between cells. thanks to the advances in language model (lm) pretraining, natural language (nl) understanding, and spreadsheet table understanding and reasoning, researchers have developed systems that could predict the formula of a selected cell in table @xcite . those systems transform users from "writers" into "decision makers", greatly reducing the required efforts for writing formulas. we have to argue, though, directly applying autoregressive sequence generation to formula generation has fundamental weaknesses. first, they fail to utilize the inner structures in spreadsheet formulas. spreadsheet formulas have well-defined grammar and structure, including the usage of operators, parenthesis, constant values, cell references, and their combinations. without taking the structure into consideration, a minor error made where the model is uncertain during the left-to-right decoding process might cause subsequent grammar mistakes @xcite . previous works have achieved promising results by changing the pure left-toright fashion by decomposing formula generation into two stages, formula sketch prediction and cell range prediction @xcite . but the underlying parse trees of formula sketches have been long neglected. second, the goal of spreadsheet formula prediction is to help spreadsheet users create desired formulas. existing works generate entire formula sketches at once, but lack sufficient interaction with users. as users are only able to accept or reject the final predictions, and thus any mismatch in users' intents might lead to unpleasant post-editing and even from-scratch rewriting. how to interactively assist users in the process of creating formulas are well desirable to be explored. in this work, we propose hermes, the first approach to generate formulas through hierarchical formulet expansion. unlike existing works, we exploit the inherent tree structure of formulas, which guarantees that the generated formulas are grammatically correct. furthermore, we find that many commonly-used formula patterns well reflect highlevel reasoning, e.g., total and percentage change, so we extract formulet, a set of 1-to-3 level expansions from real formula parse trees. to this end, we train the model to hierarchically expand nodes using formulet, which avoids overly small granularity and too many steps to expand the entire parse tree, making the generation process concise and robust (section 3.2.1). the full pipeline contains three stages. we first generate formula sketches that do not contain constant textual/numerical values nor cell references through hierarchical formulet expansion, then generate textual/numerical values, and finally predict cell references. inspired by the user interface for creating equations in word documents (figure 1 (a) ), we develop an interactive experience (figure 1 (b) ) that allows users to expand parse tree nodes in any order he/she prefers (section 5). unlike existing formula prediction systems that can only generate formulas in a fixed order, e.g., left-to-right, users here can drive the generation on their demands and potentially learn how to compose grammar-correct unfamiliar formulas. to support this experience, we propose a novel and systematic sampling strategy with solid mathematical proof to exploit various hierarchical expansion orders for training the hermes decoder. for evaluation, we further introduce a metric: interaction upper bound (iub) accuracy (section 4.3), and we find that the iub accuracy of our model is significantly higher than the accuracy of generating entire formulas at once, showing that the interactive framework can help users complete many more formula tasks. ## hermes model we present details of hermes for spreadsheet formula prediction in this section. figure 2 shows an overall architecture. ## interactive formula generation we propose interactive formula generation, allowing users to participate in the formula generation process, which potentially helps users to complete more tasks as indicated in section 4.5. as shown in figure 5 (a), users could start the interaction process by simply typing "=" in the target cell, then ten recommended (semi-finished) formula sketches will popup in a tooltip for users to select. they are generated by running the expansion predictor and may include different levels of expansions. users need to select one of the sketches from the tooltip, and it will appear in the top bar of the tooltip as the updated (semi-finished formula) sketch. if the updated semi-finished formula sketch contains one or more blank boxes ([nonterminal]s) (figure 5 (b) ), users can select one blank box for the next round of expansion prediction, then again select an expanded sketch from the updated tooltip, and repeat this process until the formula sketch does not contain any blank boxes (figure 5 (c) ). note that the [nonterminal] blank box with the highest probability predicted by non-terminal selector is selected by default, and corresponding expansion predictions are automatically shown, so it's not necessary for users to make blank box selection if they do not want to change the expansion order. finally, the interactive system will complete the formula with constant values and cell references. this interface is developed upon (srinivasa ragavan et al., 2022) using javascript. we implement table detection, header detection, and feature extraction following @xcite in the frontend as inputs, and the hermes model is wrapped to be a backend service using fastapi. ## related works we introduced spreadsheetcoder and fortap in section 4.2. we believe that table pertaining methods in fortap can be combined with our advanced model structure to achieve even greater gains. while tabt5 @xcite is a concurrent work that has been evaluated on spreadsheet formula prediction using a pre-trained language model for left-to-right sequential decoding, we have not included it as a baseline due to the lack of publicly available source code, pre-trained model, and the dataset processing details. recent works in code generation have explored leveraging grammar trees for structured code generation, showing advantages over left-to-right sequential decoding @xcite . for example, @xcite generates code based on high-level patterns (idioms), but in a fixed depth-first order. @xcite recently proposes to generate code completions in flexible orders while using only low-level granularity. hermes explores controllable hierarchical expansion orders based on both high-level and lowlevel expansions in formulet. more broadly speaking, structured generation leverages inherent structural information of tasks such as grammar and semantics. @xcite proposed to generate the logical forms of input utterances with a hierarchical tree decoder. @xcite additionally considers input objects as graphs and generates tree outputs without specific assumption on downstream tasks. existing works on flexible generation mainly investigates methods for generating sequences in arbitrary order. @xcite generate sequences based on token insertions during decoding. @xcite proposes to generate sequences by iteratively inserting and filling in blanks, further allowing users to specify where to insert. in spreadsheet formula generation, hermes continues the idea of @xcite where users can instruct the model on where and what to expand given the formula sketch. we are the first to leverage the tree structure in spreadsheet formula generation. we are also the first work in code generation to combine idiombased generation @xcite with variable hierarchical generation orders. we have derived an optimization algorithm that applies systematic sampling to deal with the idiom-based hierarchical generation which may contain skip-level expansions, and provided solid mathematical proof. we believe our approach is a novel exploration of code generation and can inspire future work in this field. ## conclusion hermes is the first framework for hierarchical spreadsheet formula expansion. it streamlines token-level decoding with multi-level formulets and devises a systematic sampling strategy to exploit various hierarchical multi-level expansion orders. experiment results show significant improvements in prediction accuracy. importantly, it enables a new interactive formula completion experience in our developed interface. we hope for hermes to stimulate more advances in leveraging underlying structures for spreadsheet formula prediction.