Hootan Nakhost

TMLR Journal 2024 Journal Article

SQL-PaLM: Improved large language model adaptation for Text-to-SQL

• Ruoxi Sun
• Sercan O Arik
• Alexandre Muzio
• Lesly Miculicich
• Satya Kesav Gundabathula
• Pengcheng Yin
• Hanjun Dai
• Hootan Nakhost

Text-to-SQL, the process of translating natural language into Structured Query Language (SQL), represents a transformative application of large language models (LLMs), potentially revolutionizing how humans interact with data. This paper introduces the SQL-PaLM framework, a comprehensive solution for understanding and enhancing Text-to-SQL using LLMs, using in the learning regimes of few-shot prompting and instruction fine-tuning. With few-shot prompting, we explore the effectiveness of consistency decoding with execution-based error filtering. With instruction fine-tuning, we delve deep in understanding the critical paradigms that influence the performance of tuned LLMs. In particular, we investigate how performance can be improved through expanded training data coverage and diversity, synthetic data augmentation, and integrating query-specific database content. We propose a test-time selection method to further refine accuracy by integrating SQL outputs from multiple paradigms with execution feedback as guidance. Additionally, we tackle the practical challenge of navigating intricate databases with a significant number of tables and columns, proposing efficient techniques for accurately selecting relevant database elements to enhance Text-to-SQL performance. Our holistic approach yields substantial advancements in Text-to-SQL, as demonstrated on two key public benchmarks, Spider and BIRD. Through comprehensive ablations and error analyses, we shed light on the strengths and weaknesses of our framework, offering valuable insights into Text-to-SQL's future work.

NeurIPS Conference 2024 Conference Paper

Teach Better or Show Smarter? On Instructions and Exemplars in Automatic Prompt Optimization

• Xingchen Wan
• Ruoxi Sun
• Hootan Nakhost
• Sercan Ö. Arık

Large language models have demonstrated remarkable capabilities but their performance is heavily reliant on effective prompt engineering. Automatic prompt optimization (APO) methods are designed to automate this and can be broadly categorized into those targeting instructions (instruction optimization, IO) vs. those targeting exemplars (exemplar optimization, EO). Despite their shared objective, these have evolved rather independently, with IO receiving more research attention recently. This paper seeks to bridge this gap by comprehensively comparing the performance of representative IO and EO techniques both isolation and combination on a diverse set of challenging tasks. Our findings reveal that intelligently reusing model-generated input-output pairs obtained from evaluating prompts on the validation set as exemplars, consistently improves performance on top of IO methods but is currently under-investigated. We also find that despite the recent focus on IO, how we select exemplars can outweigh how we optimize instructions, with EO strategies as simple as random search outperforming state-of-the-art IO methods with seed instructions without any optimization. Moreover, we observe a synergy between EO and IO, with optimal combinations surpassing the individual contributions. We conclude that studying exemplar optimization both as a standalone method and its optimal combination with instruction optimization remain a crucial aspect of APO and deserve greater consideration in future research, even in the era of highly capable instruction-following models.

NeurIPS Conference 2020 Conference Paper

Interpretable Sequence Learning for Covid-19 Forecasting

• Sercan Arik
• Chun-Liang Li
• Jinsung Yoon
• Rajarishi Sinha
• Arkady Epshteyn
• Long Le
• Vikas Menon
• Shashank Singh

We propose a novel approach that integrates machine learning into compartmental disease modeling (e. g. , SEIR) to predict the progression of COVID-19. Our model is explainable by design as it explicitly shows how different compartments evolve and it uses interpretable encoders to incorporate covariates and improve performance. Explainability is valuable to ensure that the model's forecasts are credible to epidemiologists and to instill confidence in end-users such as policy makers and healthcare institutions. Our model can be applied at different geographic resolutions, and we demonstrate it for states and counties in the United States. We show that our model provides more accurate forecasts compared to the alternatives, and that it provides qualitatively meaningful explanatory insights.

IJCAI Conference 2013 Conference Paper

Towards a Second Generation Random Walk Planner: An Experimental Exploration

• Hootan Nakhost
• Martin Müller

Random walks have become a popular component of recent planning systems. The increased exploration is a valuable addition to more exploitative search methods such as Greedy Best First Search (GBFS). A number of successful planners which incorporate random walks have been built. The work presented here aims to exploit the experience gained from building those systems. It begins a systematic study of the design space and alternative choices for building such a system, and develops a new random walk planner from scratch, with careful experiments along the way. Four major insights are: 1. a high state evaluation frequency is usually superior to the endpoint-only evaluation used in earlier systems, 2. adjusting the restarting parameter according to the progress speed in the search space performs better than any fixed setting, 3. biasing the action selection towards preferred operators of only the current state is better than Monte Carlo Helpful Actions, which depend on the number of times an action has been a preferred operator in previous walks, and 4. even simple forms of random walk planning can compete with GBFS.

SoCS Conference 2012 Conference Paper

A Theoretical Framework for Studying Random Walk Planning

• Hootan Nakhost
• Martin Müller 0003

Random walks are a relatively new component used in several state of the art satisficing planners. Empirical results have been mixed: while the approach clearly outperforms more systematic search methods such as weighted A* on many planning domains, it fails in many others. So far, the explanations for these empirical results have been somewhat ad hoc. This paper proposes a formal framework for comparing the performance of random walk and systematic search methods. Fair homogenous graphs are proposed as a graph class that represents characteristics of the state space of prototypical planning domains, and is simple enough to allow a theoretical analysis of the performance of both random walk and systematic search algorithms. This gives well-founded insights into the relative strength and weaknesses of these approaches. The close relation of the models to some well-known planning domains is shown through simplified but semi-realistic planning domains that fulfill the constraints of the models. One main result is that in contrast to systematic search methods, for which the branching factor plays a decisive role, the performance of random walk methods is determined to a large degree by the Regress Factor, the ratio between the probabilities of progressing towards and regressing away from a goal with an action. The performance of random walk and systematic search methods can be compared by considering both branching and regress factors of a state space.

ECAI Conference 2012 Conference Paper

ArvandHerd: Parallel Planning with a Portfolio

• Richard Valenzano
• Hootan Nakhost
• Martin Müller 0003
• Jonathan Schaeffer 0001
• Nathan R. Sturtevant

ArvandHerd is a parallel planner that won the multicore sequential satisficing track of the 2011 International Planning Competition (IPC 2011). It assigns processors to run different members of an algorithm portfolio which contains several configurations of each of two different planners: LAMA-2008 and Arvand. In this paper, we demonstrate that simple techniques for using different planner configurations can significantly improve the coverage of both of these planners. We then show that these two planners, when using multiple configurations, can be combined to construct a high performance parallel planner. In particular, we will show that ArvandHerd can solve more IPC benchmark problems than even a perfect parallelization of LAMA-2011, which won the satisficing track at IPC 2011. We will also show that the coverage of ArvandHerd can be further improved if LAMA-2008 is replaced by LAMA-2011 in the portfolio.

ICAPS Conference 2012 Conference Paper

Planning Via Random Walk-Driven Local Search

• Fan Xie 0001
• Hootan Nakhost
• Martin Müller 0003

The ideas of local search and random walks have been used successfully in several recent satisficing planners. Random Walk-Driven Local Search (RW-LS) is a strong new addition to this family of planning algorithms. The method uses a greedy best-first search driven by a combination of random walks and direct node evaluation. In this way, RW-LS balances between exploration and exploitation. The algorithm has been implemented in the system Arvand-LS. Its performance is evaluated against other state of the art planners on problems from IPC-2011, as well as on scaled up instances from several IPC domains. The results show significant improvements in both coverage and plan quality.

ICAPS Conference 2012 Conference Paper

Resource-Constrained Planning: A Monte Carlo Random Walk Approach

• Hootan Nakhost
• Jörg Hoffmann 0001
• Martin Müller 0003

The need to economize limited resources, such as fuel or money, is aubiquitous feature of planning problems. If the resources cannot bereplenished, the planner must make do with the initial supply. It isthen of paramount importance how constrained the problem is, i. e. , whether and to which extent the initial resource supply exceedsthe minimum need. While there is a large body of literature on numericplanning and planning with resources, such resource constrainednesshas only been scantily investigated. We herein start to address thisin more detail. We generalize the previous notion of resourceconstrainedness, characterized through a numeric problem feature C≥ 1, to the case of multiple resources. We implement an extendedbenchmark suite controlling C. We conduct a large-scale study of thecurrent state of the art as a function of C, highlighting whichtechniques contribute to success. We introduce two new techniques ontop of a recent Monte Carlo Random Walk method, resulting in a plannerthat, in these benchmarks, outperforms previous planners whenresources are scarce (C close to 1). We investigate the parametersinfluencing the performance of that planner, and we show that one ofthe two new techniques works well also on the regular IPC benchmarks.

AAAI Conference 2011 Conference Paper

A Local Monte Carlo Tree Search Approach in Deterministic Planning

• Fan Xie
• Hootan Nakhost
• Martin Müller

Much recent work in satisficing planning has aimed at striking a balance between coverage - solving as many problems as possible - and plan quality. Current planners achieve near perfect coverage on the latest IPC benchmarks. It is therefore natural to investigate their scaling behavior on more difficult instances. Among state of the art planners, LAMA (Richter, Helmert, and Westphal 2008) is able to generate high quality plans, but its coverage drops off rapidly with increasing problem complexity. The Arvand planner (Nakhost and Müller 2009) scales to much harder instances but generates lower quality plans. This paper introduces a new algorithm, Monte Carlo Random Walk-based Local Tree Search (MRW-LTS), which uses random walks to selectively build local search trees. Experiments demonstrate that MRW-LTS combines a scaling behavior that is better than LAMA’s with a plan quality that is better than Arvand’s.

ICAPS Conference 2010 Conference Paper

Action Elimination and Plan Neighborhood Graph Search: Two Algorithms for Plan Improvement

• Hootan Nakhost
• Martin Müller 0003

Compared to optimal planners, satisficing planners can solve much harder problems but may produce overly costly and long plans. Plan quality for satisficing planners has become increasingly important. The most recent planning competition IPC-2008 used the cost of the best known plan divided by the cost of the generated plan as an evaluation metric. This paper proposes and evaluates two simple but effective methods for plan improvement: Action Elimination improves an existing plan by repeatedly removing sets of irrelevant actions. Plan Neighborhood Graph Search finds a new, shorter plan by creating a plan neighborhood graph PNG(π) of a given plan π , and then extracts a shortest path from PNG(π). Both methods are implemented in the Aras postprocessor and are empirically shown to improve the result of several planners, including the top four planners from IPC-2008, under competition conditions.

SoCS Conference 2010 Conference Paper

Improving Local Search for Resource-Constrained Planning

• Hootan Nakhost
• Jörg Hoffmann 0001
• Martin Müller 0003

A ubiquitous feature of planning problems - problems involving the automatic generation of action sequences for attaining a given goal - is the need to economize limited resources such as fuel or money. While heuristic search, mostly based on standard algorithms such as A*, is currently the superior method for most varieties of planning, its ability to solve critically resource-constrained problems is limited: current planning heuristics are bad at dealing with this kind of structure. To address this, one can try to devise better heuristics. An alternative approach is to change the nature of the search instead. Local search has received some attention in planning, but not with a specific focus on how to deal with limited resources. We herein begin to fill this gap. We highlight the limitations of previous methods, and we devise a new improvement (smart restarts) to the local search method of a previously proposed planner (Arvand). Systematic experiments show how performance depends on problem structure and search parameters. In particular, we show that our new method can outperform previous planners by a large margin.

IJCAI Conference 2009 Conference Paper

• Hootan Nakhost
• Martin Müller

Search methods based on Monte-Carlo simulation have recently led to breakthrough performance improvements in difficult game-playing domains such as Go and General Game Playing. Monte-Carlo Random Walk (MRW) planning applies Monte- Carlo ideas to deterministic classical planning. In the forward chaining planner ARVAND, Monte- Carlo random walks are used to explore the local neighborhood of a search state for action selection. In contrast to the stochastic local search approach used in the recent planner Identidem, random walks yield a larger and unbiased sample of the search neighborhood, and require state evaluations only at the endpoints of each walk. On IPC-4 competition problems, the performance of ARVAND is competitive with state of the art systems.