Scaling test-time compute to search for optimal solutions is an important step towards building generally-capable language models that can reason. Recent work, however, shows that tasks of varying complexity require distinct search strategies to solve optimally, thus making it challenging to design a one-size-fits-all approach. Prior solutions either attempt to predict task difficulty to select the optimal search strategy, often infeasible in practice, or use a static, pre-defined strategy, e.g., repeated parallel sampling or greedy sequential search, which is sub-optimal. In this work, we argue for an alternative view using the probabilistic framework of Bayesian optimization (BO), where the search strategy is adapted dynamically based on the evolving uncertainty estimates of solutions as search progresses. To this end, we introduce Bayesian-OPRO (BOPRO)––a generalization of a recent method for in-context optimization, which iteratively samples from new proposal distributions by modifying the prompt to the LLM with a subset of its previous generations selected to explore or exploit different parts of the search space. We evaluate our method on word search, molecule optimization, and a joint hypothesis+program search task using a 1-D version of the challenging Abstraction and Reasoning Corpus (1D-ARC). Our results show that BOPRO outperforms all baselines in word search (≥10 points) and molecule optimization (higher quality and 17% fewer invalid molecules), but trails a best-k prompting strategy in program search. Our analysis reveals that despite the ability to balance exploration and exploitation using BOPRO, failure is likely due to the inability of code representation models in distinguishing sequences with low edit-distances.

Nishanth Sridhar Nakshatri, Shamik Roy, Rajarshi Das, Suthee Chaidaroon, Leonid Boytsov, Rashmi Gangadharaiah. Proceedings of the 2025 Conference of the Nations of the Americas Chapter of the Association for Computational Linguistics: Human Language Technologies (Volume 1: Long Papers). 2025.

Alex Mallen, Akari Asai, Victor Zhong, Rajarshi Das, Daniel Khashabi, Hannaneh Hajishirzi. Proceedings of the 61st Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). 2023.

Question answering (QA) over knowledge bases (KBs) is challenging because of the diverse, essentially unbounded, types of reasoning patterns needed. However, we hypothesize in a large KB, reasoning patterns required to answer a query type reoccur for various entities in their respective subgraph neighborhoods. Leveraging this structural similarity between local neighborhoods of different subgraphs, we introduce a semiparametric model (CBR-SUBG) with (i) a nonparametric component that for each query, dynamically retrieves other similar $k$-nearest neighbor (KNN) training queries along with query-specific subgraphs and (ii) a parametric component that is trained to identify the (latent) reasoning patterns from the subgraphs of KNN queries and then apply them to the subgraph of the target query. We also propose an adaptive subgraph collection strategy to select a query-specific compact subgraph, allowing us to scale to full Freebase KB containing billions of facts. We show that CBR-SUBG can answer queries requiring subgraph reasoning patterns and performs competitively with the best models on several KBQA benchmarks. Our subgraph collection strategy also produces more compact subgraphs (e.g. 55% reduction in size for WebQSP while increasing answer recall by 4.85%)\footnote{Code, model, and subgraphs are available at \url{https://github.com/rajarshd/CBR-SUBG}}.

Neha Kennard, Tim O’Gorman, Rajarshi Das, Akshay Sharma, Chhandak Bagchi, Matthew Clinton, Pranay Kumar Yelugam, Hamed Zamani, Andrew McCallum. Proceedings of the 2022 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies. 2022.

Rajarshi Das, Manzil Zaheer, Dung Thai, Ameya Godbole, Ethan Perez, Jay Yoon Lee, Lizhen Tan, Lazaros Polymenakos, Andrew McCallum. Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing. 2021.

Given questions regarding some prototypical situation -such as Name something that people usually do before they leave the house for work?-a human can easily answer them via acquired experiences.There can be multiple right answers for such questions, with some more common for a situation than others.This paper introduces a new question answering dataset for training and evaluating common sense reasoning capabilities of artificial intelligence systems in such prototypical situations.The training set is gathered from an existing set of questions played in a longrunning international game show -FAMILY-FEUD.The hidden evaluation set is created by gathering answers for each question from 100 crowd-workers.We also propose a generative evaluation task where a model has to output a ranked list of answers, ideally covering all prototypical answers for a question.After presenting multiple competitive baseline models, we find that human performance still exceeds model scores on all evaluation metrics with a meaningful gap, supporting the challenging nature of the task. * Equal contribution.(i) Name something that people usually do before they leave for work?Ask 100 crowd-workers + manual clustering

String similarity models are vital for record linkage, entity resolution, and search.In this work, we present STANCE-a learned model for computing the similarity of two strings.Our approach encodes the characters of each string, aligns the encodings using Sinkhorn Iteration (alignment is posed as an instance of optimal transport) and scores the alignment with a convolutional neural network.We evaluate STANCE's ability to detect whether two strings can refer to the same entity-a task we term alias detection.We construct five new alias detection datasets (and make them publicly available).We show that STANCE (or one of its variants) outperforms both state-ofthe-art and classic, parameter-free similarity models on four of the five datasets.We also demonstrate STANCE's ability to improve downstream tasks by applying it to an instance of cross-document coreference and show that it leads to a 2.8 point improvement in B 3 F1 over the previous state-of-the-art approach.

Rajarshi Das, Arvind Neelakantan, David Belanger, Andrew McCallum. Proceedings of the 15th Conference of the European Chapter of the Association for Computational Linguistics: Volume 1, Long Papers. 2017.

Rajarshi Das, Manzil Zaheer, Chris Dyer. Proceedings of the 53rd Annual Meeting of the Association for Computational Linguistics and the 7th International Joint Conference on Natural Language Processing (Volume 1: Long Papers). 2015.

Many government agencies worldwide are releasing public datasets about the services provided in healthcare, such as Medicare in the US. These datasets can be queried by multiple classes of users, including hospitals, patients, physicians and policy makers. However, to realize the true value of the information present in these datasets, appropriate analysis, including classification and clustering needs to be performed. Additional insight can be gained by combining the healthcare data with other data sources such as demographics and epidemiology. We provide an analytics framework based on open-source tools that facilitate the exploration of these datasets. We illustrate our framework by providing a detailed analysis of physician and hospital ratings data. Our technique should prove valuable to hospital administrators and policy makers.

One of the main driving forces of the growing adoption of virtualization is its dramatic simplification of the provisioning and dynamic management of IT resources. By decoupling running entities from the underlying physical resources, and by providing easy-to-use controls to allocate, deallocate and migrate virtual machines (VMs) across physical boundaries, virtualization opens up new opportunities for improving overall system resource use and power efficiency. While a range of techniques for dynamic, distributed resource management of virtualized systems have been proposed and have seen their widespread adoption in enterprise systems, similar techniques for dynamic power management have seen limited acceptance. The main barrier to dynamic, power-aware virtualization management stems not from the limitations of virtualization, but rather from the underlying physical systems; and in particular, the high latency and energy cost of power state change actions suited for virtualization power management.

This paper describes our experiences deploying a recommender system for a mobile phone-based knowledge sharing application to farmers in rural India. Users of the system record questions and call back for answers left by other users and experts. We used collaborative filtering to derive relevant content for each user based on historical navigation patterns of the community. An empirical analysis of behavioral and interview data reveals key issues for future mobile recommender systems in developing regions of the world.

Electrical power management in large-scale IT systems such as commercial data- centers is an application area of rapidly growing interest from both an economic and ecological perspective, with billions of dollars and millions of metric tons of CO2 emissions at stake annually. Businesses want to save power without sac- rificing performance. This paper presents a reinforcement learning approach to simultaneous online management of both performance and power consumption. We apply RL in a realistic laboratory testbed using a Blade cluster and dynam- ically varying HTTP workload running on a commercial web applications mid- dleware platform. We embed a CPU frequency controller in the Blade servers’ firmware, and we train policies for this controller using a multi-criteria reward signal depending on both application performance and CPU power consumption. Our testbed scenario posed a number of challenges to successful use of RL, in- cluding multiple disparate reward functions, limited decision sampling rates, and pathologies arising when using multiple sensor readings as state variables. We describe innovative practical solutions to these challenges, and demonstrate clear performance improvements over both hand-designed policies as well as obvious “cookbook” RL implementations.

As online markets for the exchange of goods and services become more common, the study of markets composed, at least in part, of autonomous agents has taken on increasing importance. In contrast to traditional complete–information economic scenarios, agents that are operating in an electronic marketplace often do so under considerable uncertainty. In order to reduce their uncertainty, these agents must learn about the world around them. When an agent producer is engaged in a learning task in which data collection is costly, such as learning the preferences of a consumer population, it is faced with a classic decision problem: when to explore and when to exploit. If the agent has a limited number of chances to experiment, it must explicitly consider the cost of learning (in terms of foregone profit) against the value of the information acquired. Information goods add an additional dimension to this problem; due to their flexibility, they can be bundled and priced according to a number of different price schedules. An optimizing producer should consider the profit each price schedule can extract, as well as the difficulty of learning of this schedule. In this paper, we demonstrate the tradeoff between complexity and profitability for a number of common price schedules. We begin with a one–shot decision as to which schedule to learn. Schedules with moderate complexity are preferred in the short and medium term, as they are learned quickly, yet extract a significant fraction of the available profit. We then turn to the repeated version of this one–shot decision and show that moderate complexity schedules, in particular two–part tariff, perform well when the producer must adapt to nonstationarity in the consumer population. When a producer can dynamically change schedules as it learns, it can use an explicit decision–theoretic formulation to greedily select the schedule which appears to yield the greatest profit in the next period. By explicitly considering both the learnability and the profit extracted by different price schedules, a producer can extract more profit as it learns than if it naively chose models that are accurate once learned.

We explore a scenario in which a monopolist producer of information goods seeks to maximize its profits in a market where consumer demand shifts frequently and unpredictably. The producer may set an arbitrarily complex price schedule---a function that maps the set of purchased items to a price. However, lacking direct knowledge of consumer demand, it cannotcompute the optimal schedule. Instead, it attempts to optimize profits via trial and error. By means of a simple model of consumer demand and a modified version of a simple nonlinear optimization routine, we study a variety of parametrizations of the price schedule and quantify some of the relationships among learnability, complexity, and profitability. In particular, we show that fixed pricing or simple two-parameter dynamic pricing schedules are preferred when demand shifts frequently, but that dynamic pricing based on more complex schedules tends to be most profitable when demand shifts very infrequently.

We develop two bidding algorithms for real-time Continuous Double Auctions (CDAs) using a variety of market rules that offer what we believe to be the strongest known performance of any published bidding strategy. Our algorithms are based on extensions of the "ZIP" (Cliff, 1997) and "GD" (Gjerstad and Dickhaut, 1998) strategies: we have made essential modifications to these strategies which enable trading multiple units in real-time markets. We test these strategies against each other and against the sniping strategy of (Rust et al., 1992) and the baseline "Zero Intelligence" strategy of (Gode and Sunder, 1992), using both a discrete-time simulator and a genuine real-time multi-agent environment called MAGENTA (Das et al., 2001). Under various market rules and limit price distributions, our modified Gjerstad-Dickhaut ("MGD") strategy outperforms the original GD, and generally ominates the other strategies.

Electronic goods are flexible and have negligible marginal costs. These features allow a producer of electronic goods to explore pricing schemes, and in particular bundling, that would not be feasible with physical goods. However, they can also make it more difficult for a producer to differentiate itself from competitors offering identical goods. Previous research in this area indicates that in markets where producers compete over the sale of identical information goods, cyclical price wars often develop. In this paper, we provide a characterization of the conditions that result in price wars and show analytically how the existence of niches within the consumer population can lead duopolist producers to each target separate niches and avoid price wars. In situations where producers have incomplete information about consumer preferences, and so must learn a strategy, producers will be concerned not only with the relative benefits of niche targeting as opposed to a price war, but also with th...

In an automated market for electronic goods new problems arise that have not been well studied previously. For example, information goods are very flexible. Marginal costs are negligible and nearly limitless bundling and unbundling of these items are possible, in contrast to physical goods. Consequently, producers can offer complex pricing schemes. However, the profit-maximizing design of a complex pricing schedule depends on a producer's knowledge of the distribution of consumer preferences for the available information goods. Preferences are private and can only be gradually uncovered through market experience. In this paper we compare dynamic performance across price schedules of varying complexity. We provide the producer with two machine learning methods producer that is performing a naive, knowledge-free form of leanings (function approximation and hill-climbing) which implement a strategy that balances exploitation to maximize current profits against exploration of the profit landscape to improve future profits. We find that the tradeoff between exploitation and exploration is different depending on the learning algorithms employed, and in particular depending on the complexity of the price schedule that if offered. In general, simpler price schedules are more robust and give up less profit during the learning periods even though in our stationary environment learning eventually is complete and the more complex schedules have high long-run profits. These results hold for both learning methods, even though the relative performance of the methods is quite sensitive to choice of initial conditions and differences in the smoothness of the profit landscape for different price schedules. Our results have implications for automated learning and strategic pricing in non-stationary environments, which arise when the consumer population changes, individuals change their preferences, or competing firms change their strategies.