Failing to Explore: Language Models on Interactive Tasks
Mahdi JafariRaviz, Keivan Rezaei, Arshia Soltani Moakhar, Zahra Sodagar, Yize Cheng, Soheil Feizi · 2026
Read Failing to Explore: Language Models on Interactive Tasks by Mahdi JafariRaviz, Keivan Rezaei, Arshia Soltani Moakhar, Zahra Sodagar, Yize Cheng, Soheil Feizi (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2601-22345.txt.
Introduction
Mahdi JafariRaviz and five co-authors find that top language models explore too little when a task needs trial and error. Their 2026 preprint sets three tasks whose search load can be dialed up or down. Each model gets a fixed budget of tries in a live, changing setup.
Across leading models, the team find thin search and weak final picks. Simple search-then-use rules often beat the models by a wide gap. More tries help the models less than one would hope. The result warns teams that chat skill is not search skill. Agents sent to explore need checks.
Catalog record
| CREATOR | Mahdi JafariRaviz, Keivan Rezaei, Arshia Soltani Moakhar, Zahra Sodagar, Yize Cheng, Soheil Feizi |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 104 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2601-22345
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Failing to Explore: Language Models on Interactive Tasks Mahdi JafariRaviz, Keivan Rezaei, Arshia Soltani Moakhar, Zahra Sodagar, Yize Cheng, Soheil Feizi Abstract We evaluate language models on their ability to explore interactive environments under a limited interaction budget. We introduce three parametric tasks with controllable exploration difficulty, spanning continuous and discrete environments. Across state-of-the-art models, we find systematic under-exploration and suboptimal solutions, with performance often significantly worse than simple explore–exploit heuristic baselines and scaling weakly as the budget increases. Finally, we study two interventions: splitting a fixed budget into p p parallel executions, which surprisingly improves performance despite a no-gain theoretical result for our tasks, and periodically summarizing the interaction history, which preserves key discoveries and further improves exploration 1 1 1 Code is at github.com/mahdi-jfri/explore-exploit-bench . . † † affiliationnotice: Equal contribution Department of Computer Science, University of Maryland {mahdij, krezaei, asoltan3, zsodagar, yzcheng, sfeizi}@umd.edu 1 Introduction Figure 1 : Overview of our environments. Across all tasks, the model interacts with a partially observed environment under a limited budget and must balance exploration with identifying optimal solutions while avoiding sub-optimal decisions. Left ( HillSearch ) : there is a hidden function f(x) . At each interaction, the model observes the value of the function at a chosen point. The model should avoid identifying suboptimal solutions and explore sufficiently to find optimal points. Middle ( TreeSearch ) : there is a tree in which each node has a hidden reward. At each interaction, the model can query the reward of a node that has already been explored or is adjacent to explored nodes. The model should not get trapped by early high rewards from trap gateways and must explore enough to eventually find optimal leaves of good gateways. Right ( MaxSatSearch ) : there are m hidden clauses, among which one important clause exists and is repeated w_{\text{gold}} times. At each iteration, the model queries the number of satisfied clauses for a given assignment of the variables. While the model may increase the number of satisfied clauses by modifying variable assignments, achieving a high reward requires satisfying the important clause, necessitating sufficient exploration of assignments for variables involved. Agentic AI is an increasingly prominent direction, where language models (LMs) act as agents that go beyond a single static response by iteratively taking actions—e.g., calling tools and APIs ( 48 ) , invoking other LMs ( 51 ) , processing feedback, and choosing follow-up steps. This paradigm is increasingly used in practical settings such as tool-using LMs ( 46 ; 65 ) , web-based agents in realistic web environments ( 64 ; 70 ; 39 ) , software engineering agents ( 25 ; 31 ) , and grounded robotic decision making ( 2 ; 29 ) . In these settings, agents operate in environments with partial information and costly interactions (e.g., a physical robot action, an experiment, or a paid API call). Achieving strong performance therefore requires effective use of a limited interaction budget , which raises a critical need to evaluate whether LMs can act well in such environments under resource constraints. Most current evaluations of LMs focus on static performance ( 42 ; 43 ; 45 ; 30 ) . In this work, we focus on discovery : the model interacts with a black-box environment that contains hidden solutions , and must use a limited budget of queries to an oracle to iteratively learn about the environment and identify high-quality solutions. More specifically, we study how well LMs can explore such environments—i.e., how effectively they probe to discover better solutions, rather than committing early to sub-optimal ones. We provide a suite of three parametric tasks, HillSearch , TreeSearch , and MaxSatSearch , each specifying a family of problem instances that can be instantiated by choosing interpretable parameters; importantly, these parameters explicitly control the exploration required to discover high-quality solutions, making the explorative difficulty tunable. These include discovering the maximum of a hidden continuous function ( HillSearch ), discovering high-reward nodes in a tree with hidden node values ( TreeSearch ) and discovering a high-satisfaction variable assignment under a hidden clause structure ( MaxSatSearch ) (See Figure 1 for an illustration). To require meaningful exploration, we explicitly incorporate traps : sub-optimal solutions that are easy to find early in the environment, but can distract the model from continued exploration and lead to premature commitment. All tasks are easy to describe in short natural language, resembling familiar problems in LMs’ training data. The model is given a total budget of N interactions (i.e., N rounds of querying the oracle) to gather information and discover solutions. We evaluate a suite of recent LMs (including reasoning models) on instances of our task suite, and compare their performance to simple explore–exploit heuristic baselines. These baselines are intentionally lightweight (a few lines of code) and easy to describe, and they serve as a strong sanity check that additional interaction budget indeed translates into improved discovery. Our evaluation reveals consistent underperformance of LMs compared to these simple baselines. This gap signals systematic under-exploration : models often commit early to trap solutions and fail to use additional interaction budget effectively. In particular, we observe that performance scales weakly with N , despite the fact that the environments contain better solutions that can be discovered with further exploration. To improve performance in budgeted interactive tasks, we propose two interventions. (1) Parallel budget allocation: we split the total budget into p independent threads, run the model separately in each, and select the best solution found across threads. Although we prove that, on our tasks, parallelizing a fixed budget into p threads cannot improve upon an optimal single-thread strategy, we nonetheless observe consistent gains for LMs, suggesting their single-thread behavior is far from optimal. We further provide theory clarifying when such gains can arise. (2) Periodic summarization : we periodically summarize the interaction history every fixed number of interactions, remove the full context, and continue from the summary. This guides the model to retain the key takeaways while reducing context-related failures, improving discovery and increasing performance. Contributions. Our contributions are as follows: • We go beyond static evaluation by introducing a suite of parametric, controllable tasks that make LM exploration measurable and difficulty-tunable across continuous and discrete/combinatorial environments. • We find that LMs—including frontier GPT-5 models—underperform simple explore–exploit methods, committing prematurely to sub-optimal solutions and scaling weakly with increased interaction budget. • We study two lightweight interventions—parallelizing a fixed budget into independent threads and periodically summarizing the interaction history—that consistently improve explorative performance. 2 Related Work LMs as combinatorial optimizers and algorithmic simulators Recent studies demonstrate that LMs can achieve strong performance at solving combinatorial problems ( 50 ; 44 ; 23 ; 62 ) , performing in-context algorithmic simulation ( 69 ; 36 ) , and executing complex optimization tasks ( 24 ) . Collectively, these capabilities suggest that LMs are well-equipped for the requirements of our study, providing a strong foundation for their application in our setting. Summarization and parallelization for LM exploration Both parallelization and summarization have been widely studied for LMs. Parallel sampling is commonly used to encourage exploration (e.g., pass@ k ). However, prior work on parallel inference typically increases the total compute or budget