PaperlayerView exact revision on arXiv

Source-linked AI summary

Failing to Explore: Language Models on Interactive Tasks

Mahdi JafariRaviz, Keivan Rezaei, Arshia Soltani Moakhar, Zahra Sodagar, Yize Cheng, Soheil Feizi

arXiv:2601.22345v1cs.LG

TL;DR

The paper asks whether language models can explore hidden solution spaces effectively under limited interaction budgets. It evaluates them on three controllable task families and finds systematic under-exploration, while parallel execution and periodic summarization improve discovery. The results suggest that sustained exploration and revision mechanisms can matter more than simply providing a longer context or more interactions.

  • Problem

    The paper studies how effectively LMs explore black-box environments to discover better solutions rather than committing early to sub-optimal ones under limited budgets.

  • Method

    The authors introduce three parametric tasks with tunable exploration difficulty and evaluate LMs and lightweight interventions under fixed interaction budgets.

  • Results

    LMs systematically under-explore and underperform simple explore–exploit baselines, while parallel runs and periodic summarization improve performance.

  • Takeaways & Limitations

    Improving agentic discovery may require mechanisms that encourage sustained exploration and revision rather than relying only on longer contexts or interaction budgets.

  • Takeaways & Limitations

    The framework assumes a static environment with deterministic oracle feedback and evaluates interaction over a fixed budget N.

Abstract

from arXiv · show

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 lightweight interventions: splitting a fixed budget into 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. Introduction

The paper introduces a controllable framework for measuring language-model exploration in interactive environments and finds systematic under-exploration. Two lightweight interventions improve discovery despite limited interaction budgets.

  • The paper addresses whether LMs can discover high-quality solutions through black-box interaction under a limited query budget.
  • Three tunable tasks—HillSearch, TreeSearch, and MaxSatSearch—span continuous, discrete, and combinatorial environments with traps that encourage premature commitment.
  • Performance scales weakly with the interaction budget N even when further exploration could reveal better solutions.
  • LMs, including frontier GPT-5 models, underperform simple explore–exploit methods, often committing prematurely to sub-optimal solutions.
  • Parallel fixed-budget threads and periodic interaction-history summaries consistently improve explorative performance.

2. Related Work

Prior LM evaluations establish strong capabilities in reasoning and optimization, but interactive benchmarks have rarely isolated exploration–exploitation behavior. Related work also documents models’ difficulty revising initial ideas and errors.

  • Prior studies report strong LM performance on combinatorial problems, algorithmic simulation, and complex optimization tasks.
  • Parallel inference typically increases total compute, whereas this paper studies splitting a fixed interaction budget across independent branches.
  • Summarization has often been used to fit interactions within context windows, but its impact on exploration behavior is rarely measured.
  • Navigation and interactive-game benchmarks usually emphasize goal reaching, memory, or control rather than explore–exploit tradeoffs.
  • Related studies find that LMs often preserve consistency with earlier errors and struggle to revise an initial idea.

3. Exploring Interactive Environments

The framework models sequential interaction with a static, partially revealed environment under a fixed budget, evaluating both solution quality and how additional queries improve discovery. It applies this evaluation across three environment types.

  • A model interacts with an environment whose hidden solutions become partially revealed through probing under a fixed interaction budget N.
  • Across N discrete rounds, the model generates queries to an oracle, whose feedback depends on each query and the fixed problem instance.
  • Later admissible queries may depend on earlier queries, making interaction sequentially constrained despite deterministic feedback from a static environment.
  • Performance is measured by the quality of the best solution discovered by the end of N rounds.
  • The task suite covers continuous HillSearch, discrete graph-structured TreeSearch, and discrete combinatorial MaxSatSearch.

4. Tasks

The task suite defines three budgeted interactive environments whose parameters control exploration difficulty across continuous and discrete settings. Each task rewards discovering high-quality solutions through oracle queries, with explore–exploit heuristics specified as comparison baselines.

  • The suite formalizes environments, oracle protocols, query feedback, fixed-budget rewards, and parameterized instance generation for model interaction.Task descriptions and reward objectives are provided before interaction begins, with performance evaluated under a fixed budget N.
  • HillSearch: HillSearch asks models to query a hidden smooth Gaussian-hill function and maximize the observed value over N rounds.Instances contain moderate decoy peaks and one narrow, high needle peak, making exploration harder as the needle narrows.
  • HillSearch: HillSearch uses stratified random sampling for 0.8N exploratory queries, then locally refines around the best point within a window of size 0.5.The baseline updates the current best whenever a better point is found.
  • TreeSearch: TreeSearch reveals hidden node rewards while restricting explored nodes to a connected component, and rewards the best node found.Trap chains offer early reward but stagnate, whereas good chains improve toward high-reward leaves; trap chains are longer and can consume the budget.
  • TreeSearch: The TreeSearch heuristic samples nodes randomly while favoring higher-reward parents through a softmax rule with temperature τ = 4.The temperature controls how strongly parent rewards influence node-selection probabilities.
  • MaxSatSearch: MaxSatSearch evaluates full Boolean assignments by the number of satisfied hidden clauses, with the final reward equal to the best score over N assignments.High scores require discovering an assignment satisfying a repeated gold clause whose variables receive no information from non-gold clauses.
  • MaxSatSearch: The MaxSatSearch heuristic uses random assignments for 0.5N rounds, then flips one random variable in the best assignment to iteratively seek improvement.The baseline uses α = 0.5.

5. Experiments

The experiments evaluate language and reasoning models on three tunable interactive-search tasks, comparing them with simple explore–exploit baselines and testing parallel execution and periodic summarization. Models consistently under-explore, use additional budget inefficiently, and improve when their budget or history is structured differently.

  • Experimental setup: The evaluation instantiates HillSearch, TreeSearch, and MaxSatSearch under fixed interaction budgets, comparing LLMs and LRMs with simple explore–exploit baselines.The study also examines reward scaling, parallel threads, periodic summarization, and robustness to task difficulty variations.
  • Baseline comparison: Models achieve sub-optimal reward across all tasks and budgets, while simple explore–exploit baselines consistently and significantly outperform them.The same overall trends are confirmed on 50 instances of each task.
  • Observed behavior: Models often commit early to local or trap solutions: HillSearch queries cluster around local maxima, TreeSearch descends trap branches, and MaxSatSearch makes only small local assignment changes.These behaviors leave the model at low-reward or sub-optimal solutions when broader exploration is needed.
  • Budget scaling: Model reward grows substantially more slowly with interaction budget than baseline reward, indicating weak use of additional interactions and persistent under-exploration.The models do not improve substantially simply by interacting longer with the environment.
  • Parallel threads: Parallel execution improves over single-thread interaction across tasks despite the theoretical result that splitting a fixed budget provides no advantage over an optimal single trace.The method runs p independent threads with budget N/p and selects the best solution found.
  • Periodic summarization and robustness: Periodic summaries can improve performance by encouraging broader exploration and reducing premature commitment to sub-optimal solutions, while parallel and summary methods remain better across task difficulties.Figure 4 varies peak width, gateway ratios, and gold-clause size; the intervention methods consistently outperform standard execution.

Conclusion

The paper evaluates language models’ exploration in interactive domains and finds suboptimal performance linked to early commitment. Parallel runs and periodic summarization improve performance in practice.

  • The framework measures how models interact with environments, explore solution spaces, and obtain good solutions under limited budgets.
  • Models show suboptimal performance, which the authors attribute to early commitment to sub-optimal solutions.
  • Parallel runs and periodic summarization improve performance in practice by tracking progress and blind spots.
  • Improving agentic discovery may require mechanisms that encourage sustained exploration and revision rather than only a longer context.

Impact Statement

The paper addresses a gap in interactive evaluation by isolating exploration under strict query budgets. Its controllable task suite exposes failures that are often obscured in realistic or entangled environments.

  • Most existing benchmarks measure task completion, code generation, or strategic competition rather than systematic exploration under strict query budgets.
  • Real-world web and tool-use benchmarks are realistic but typically mix exploratory capability with planning, instruction-following, and UI manipulation.
  • Interactive coding benchmarks mainly use interaction as a correctness oracle, emphasizing synthesis and debugging rather than unknown-space exploration.
  • Game-based evaluations probe strategic reasoning and social dynamics, but exploration quality is often confounded by opponent behavior and game-theoretic factors.
  • Several partial-observability and interactive-learning benchmarks lack controlled, parameterized environments designed to disentangle exploration strategies.
  • The task suite uses simple parameterized environments with controllable difficulty to isolate premature commitment, under-exploration, and inefficient budget utilization.

B. Task Instances Details

The appendix details procedural generation for three parameterized tasks: continuous HillSearch, graph-structured TreeSearch, and combinatorial MaxSatSearch. Instance parameters control the structures and exploration challenges.

  • HillSearch: HillSearch constructs a continuous function on [0, 10] from Gaussian hills with configurable centers, widths, and heights.
  • HillSearch: HillSearch combines coarse-grid decoy hills with a finer-grid needle hill whose fixed height is 20.Decoy hills use widths αdecoy∆k and heights sampled from 1, 2, 3, 4, 5; the needle uses width αneedle∆k′.
  • TreeSearch: TreeSearch builds rooted trees with trap and good gateways, each branching into disjoint chains, then randomly permutes node IDs.Trap and good gateways have configurable counts, fanout, and chain lengths.
  • TreeSearch: TreeSearch assigns node values by setting the root to 0 and adding edge increments along each root-to-node path.
  • TreeSearch: Trap gateways create short-term positive momentum followed by sparse increases, whereas good gateways provide steady growth of 4 per additional step.
  • MaxSatSearch: MaxSatSearch generates a hidden Boolean formula around a sampled assignment, repeating a gold clause and constructing remaining clauses from other variables.The instance is controlled by n, m, kgold, kother, and wgold.
  • Evaluated instances: The evaluated instances use specified parameter settings for HillSearch, TreeSearch, and MaxSatSearch, including a 772-node TreeSearch instance with maximum value 45.

C. Explaining Tasks to Models

Models receive system and user prompts that define each task, provide instance details, and request queries. The templates distinguish dynamic problem-specific information from the task’s general instructions.

  • Each conversation begins with a system prompt and continues with a user prompt containing remaining instance details and requesting the first query.
  • TreeSearch: TreeSearch requires queried nodes to connect to previously queried nodes, so responses include newly available nodes in randomized order.
  • Figures 5, 6, and 7 show the HillSearch, TreeSearch, and MaxSatSearch prompt templates, respectively.Blue text marks dynamic variables specific to the problem instance or generated queries.
  • HillSearch: The HillSearch prompt defines a hidden continuous function on [0, 10], limited queries, and the goal of finding its global maximum.
  • TreeSearch: The TreeSearch prompt presents a graph game with limited queries, a starting node value, randomized adjacency order, and validity constraints on queried nodes.
  • MaxSatSearch: The MaxSatSearch prompt describes Boolean assignments, weighted clauses formed with AND, and feedback based on the sum of satisfied-clause weights.

D. Evaluation Setup Details

The appendix details evaluation procedures, supplementary instances, and analyses of model behavior, budgets, and robustness. It also reports that models generally underperform explore–exploit baselines, while summarization and parallelization improve performance.

  • Evaluation Protocol: Queries are decoded with temperature T = 0.7 and nucleus sampling top-p = 0.95 when supported, while unsupported controls use provider defaults.Other decoding settings remain at framework or provider defaults.
  • Evaluation Protocol: Structured outputs enforce the required JSON format and include a reason or think field for model reasoning.This also supports models whose internal reasoning features are disabled or unavailable.
  • Evaluation Protocol: Models use multiple independent runs to account for variance and obtain statistically meaningful results.The main results use sample sizes specified in Table 4, with complementary analyses using task- and model-specific run counts.
  • Supplementary Analyses: Additional analyses examine greedy exploration trajectories, varying budgets, additional instances, and robustness beyond the main evaluation.The appendix includes HillSearch, TreeSearch, and MaxSatSearch supplementary instances and budget settings.
  • Supplementary Results: Trajectory analysis shows early exploration followed by local exploitation on HillSearch and persistence along the initially selected branch on TreeSearch.The HillSearch visualization reports later queries clustering near local maxima, while the TreeSearch pattern maintains nearly constant distance to the previously queried node.

E.5. Full Results of Difficulty Variation

The difficulty-variation evaluation changes interpretable task parameters while comparing parallel and summary interventions across budgets and instances. Supplementary tables and prompts document these comparisons and the baseline procedures.

  • Intervention Comparisons: The evaluation compares parallel execution with p ∈{2, 3, 4} and summary intervals with s ∈{2, 3, 4, 6} under budget N = 36.Figure 12 presents the complete intervention evaluation for this budget.
  • Additional Instances: Tables 8–12 report results for additional TreeSearch and MaxSatSearch instances across interaction budgets.The supplementary instances vary tree structure and MaxSatSearch parameters such as n, m, kgold, kother, and wgold.
  • Uncertainty: Bootstrap standard errors show non-overlapping intervals separating parallel performance from the single-thread baseline in the reported comparisons.Table 15 similarly reports bootstrap standard errors for summary-method experiments.
  • Summary Prompts: The summary prompts rely only on query history and previously revealed context, rather than providing new information.Separate prompts are used for HillSearch, TreeSearch, and MaxSatSearch.
  • Difficulty Design: Difficulty varies by HillSearch peak width, TreeSearch good-to-trap gateway ratio, and MaxSatSearch gold-clause size.Harder parameter settings yield lower baseline performance.
  • Baselines: The explore–exploit baselines use stratified sampling then local search for HillSearch, frontier-node scoring for TreeSearch, and random assignments then bit flips for MaxSatSearch.These algorithms provide the comparison procedures for the intervention experiments.

G.2. Parameters

Baseline sensitivity experiments vary exploration and selection parameters across all three tasks. The simple baselines consistently match or exceed language-model performance across broad parameter ranges.

  • Experimental Design: 500 evaluation episodes measure baseline sensitivity to parameter settings across all tasks.The results are summarized in Figure 16.
  • HillSearch: HillSearch varies exploration fraction α from 0 to 1, with α = 0.8 used in the main experiments.Settings with 0.5 ≤α ≤1 outperform the language models.
  • TreeSearch: TreeSearch varies softmax temperature τ from 0 to 6, with τ = 4 as the default setting.Values in the range 2 ≤τ ≤6 surpass the best language model.
  • MaxSatSearch: MaxSatSearch varies random-sampling fraction α from 0 to 1, using α = 0.5 in the main experiments.Settings where α ≥0.3 outperform all evaluated language models.
  • Cross-Task Comparison: All baseline variations outperform Qwen2.5-7B-Instruct in the reported MaxSatSearch sensitivity analysis.The results support consistent baseline performance across parameter settings.
  • Cross-Task Comparison: Across tasks and parameter values, explore–exploit baselines consistently outperform language models with query budget N = 48.Figure 16 reports performance under varying baseline parameters.

H. Theoretical Results

The theoretical analysis studies whether splitting a fixed budget across independent threads can improve success probability or reward. It proves no advantage over an optimal single-thread strategy for the studied TreeSearch and MaxSatSearch settings, while identifying a low-budget success-probability regime where parallelization can help.

  • Overall Result: The paper explicitly proves that fixed-budget parallelization has no theoretical advantage over a single interaction trace of length N on the studied tasks.This provides the basis for fair empirical comparison between parallel and single-thread methods.
  • Success-Probability Analysis: Theorem 5.1 states that for q(x) = cx^α with 0 < α < 1, parallelization is beneficial below a threshold v_p and not beneficial at or above it.The threshold exists for every integer p > 1.
  • Success-Probability Analysis: For small budgets, the success-probability analysis finds parallelization beneficial because the parallel-minus-single success function initially has positive slope.The proof establishes h′(0) > 0 when α < 1 and p > 1.
  • Threshold Approximation: Near α ≈1, the two-thread threshold scales as v_2 ≈4 ln 2 · 1−α.This is obtained from the stated solution y_2* = 2−2α and its Taylor expansion.
  • TreeSearch: For TreeSearch, the union of nodes explored by parallel threads is connected and can be traversed by a single thread within the same total budget.Therefore, parallel strategy reward cannot exceed the optimal single-thread reward.
  • MaxSatSearch: For MaxSatSearch, a single thread can query the union of assignments explored by parallel threads within budget N and attain at least their best reward.Thus, fixed-budget parallel outcomes are upper-bounded by an optimal single-thread interaction.
Loading 2601.22345v1…