MAXS: Meta-Adaptive Exploration with LLM Agents

Jian Zhang, Zhiyuan Wang, Zhangqi Wang, Yu He, Haoran Luo, Li Yuan, Lingling Zhang, Rui Mao, Qika Lin, Jun Liu

TL;DR

MAXS (Meta-Adaptive Exploration with LLM Agents) is a novel inference-time framework that solves the dual challenges of short-sighted tool usage and cascading errors in LLM agents. By combining a lightweight 4-step lookahead strategy with stability metrics derived from dynamical systems theory, MAXS achieves state-of-the-art reasoning accuracy while consuming up to 1,000 times fewer tokens than traditional tree-search methods like MCTS.

What Problem Does This Paper Address?

When Large Language Model (LLM) agents solve complex problems, they often rely on external tools like code interpreters or search engines. However, current test-time reasoning strategies fall into two traps:

  1. Locally Myopic Generation: Agents decide to use a tool based only on the immediate next step, failing to foresee whether that tool will actually add value down the line.
  2. Trajectory Instability: Multi-tool reasoning paths are highly sensitive. A tiny error early in the reasoning chain can compound, causing the agent to diverge into completely broken logic.

While global exploration strategies like Monte Carlo Tree Search (MCTS) can mitigate these issues by simulating entire future paths, they are computationally extravagant, often consuming thousands of times more tokens than standard decoding. MAXS introduces a way to balance global effectiveness with strict computational efficiency.

Methods

MAXS integrates tool execution and reasoning planning through three core components:

  • Lookahead Strategy: Instead of simulating a path to the very end (like MCTS), MAXS uses a short, multi-step rollout (typically 4 steps ahead) to estimate the future value of a reasoning step based on the Bellman Optimality Principle.
  • Stability-Aware Value Estimation: To prevent trajectory drift, candidate paths are scored using a composite reward function:
  • Advantage Score: Measures the relative progress gained by choosing a specific step.
  • Step-Level Variance: Inspired by Lyapunov stability theory, this constrains state fluctuations to ensure the reasoning path remains stable.
  • Slope-Level Variance: Inspired by Lipschitz continuity, this measures and enforces the directional smoothness of the trajectory, avoiding abrupt logical jumps.
  • Trajectory Convergence (Early Stopping): To save compute, MAXS monitors the variance of the candidate rewards. Once the path consistency stabilizes below a threshold ($\delta = 0.002$), the model halts expensive rollouts and switches back to standard autoregressive decoding.
Illustration of the MAXS framework showing rollout, value estimation, and early termination via trajectory convergence.

Datasets

The authors evaluated MAXS across five diverse and mathematically rigorous benchmarks:

  • MathVista: A large-scale visual and mathematical reasoning dataset (1,000 testmini samples).
  • OlympiadBench: High-level competition and college-level scientific problems (6,728 open-ended questions across math and physics).
  • EMMA (MINI): An enhanced multimodal reasoning benchmark spanning math, physics, and chemistry (300 samples).
  • TheoremQA: A theorem-driven question-answering dataset (800 QA pairs).
  • MATH: High school competition-level problems (300 sampled problems across 5 difficulty tiers).

Key Insights and Ideas

  • The 4-Step Efficiency Frontier: The authors discovered that looking ahead further than 4 steps yields diminishing returns for accuracy but causes token costs to explode. A 4-step window represents the sweet spot for foresighted agent planning.
  • Math as a Dynamical System: Applying classical control theory concepts (Lyapunov stability and Lipschitz bounds) to token log-probabilities successfully regularizes LLM generation, favoring smoother, more predictable, and less error-prone reasoning paths.
  • Token Efficiency is Possible: You don't need full-tree expansion to get global-like reasoning quality. Knowing when to stop exploring (trajectory convergence) makes test-time scaling practical for real-world deployment.
Inference-time scaling law showing MAXS achieving superior accuracy at a fraction of the token budget compared to MCTS.

Key Results

MAXS was tested using three backbones: MiMo-VL-7B, Qwen2.5-VL-7B, and Qwen2.5-VL-32B. It consistently achieved state-of-the-art results:

  • MiMo-VL-7B: Reached an average accuracy of 63.46% across all benchmarks, outperforming Chain-of-Thought (CoT) by 10.53% and Tree-of-Thoughts (ToT) by 6.42%.
  • Qwen2.5-VL-7B: Achieved 42.85% average accuracy, notably outperforming Guided Decoding by 7.43%.
  • Compute Savings: Horizontally compared, MAXS achieved a target accuracy of 49% while using roughly 1,000x fewer tokens than MCTS.

Limitations and Future Work

The authors noted that MAXS remains vulnerable to early recognition errors, particularly in multimodal settings. If the agent misidentifies an element in an image at step zero, it might generate a highly confident, stable, and directionally smooth reasoning trajectory based on that false premise. Because the internal logic remains coherent, the stability metrics fail to flag the error, leading to an incorrect final answer.

Future work will likely focus on improving the agent's resilience to ambiguous tool outputs and initial perception errors.

Summary updated

Abstract

Large Language Model (LLM) Agents exhibit inherent reasoning abilities through the collaboration of multiple tools. However, during agent inference, existing methods often suffer from (i) locally myopic generation, due to the absence of lookahead, and (ii) trajectory instability, where minor early errors can escalate into divergent reasoning paths. These issues make it difficult to balance global effectiveness and computational efficiency. To address these two issues, we propose meta-adaptive exploration with LLM agents https://github.com/exoskeletonzj/MAXS, a meta-adaptive reasoning framework based on LLM Agents that flexibly integrates tool execution and reasoning planning. MAXS employs a lookahead strategy to extend reasoning paths a few steps ahead, estimating the advantage value of tool usage, and combines step consistency variance and inter-step trend slopes to jointly select stable, consistent, and high-value reasoning steps. Additionally, we introduce a trajectory convergence mechanism that controls computational cost by halting further rollouts once path consistency is achieved, enabling a balance between resource efficiency and global effectiveness in multi-tool reasoning. We conduct extensive empirical studies across three base models (MiMo-VL-7B, Qwen2.5-VL-7B, Qwen2.5-VL-32B) and five datasets, demonstrating that MAXS consistently outperforms existing methods in both performance and inference efficiency. Further analysis confirms the effectiveness of our lookahead strategy and tool usage.
BibTeX
@inproceedings{zhang2026maxs,
  author = {Jian Zhang and Zhiyuan Wang and Zhangqi Wang and Yu He and Haoran Luo and Li Yuan and Lingling Zhang and Rui Mao and Qika Lin and Jun Liu},
  title = {{MAXS: Meta-Adaptive Exploration with LLM Agents}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2026},
  doi = {10.18653/v1/2026.findings-acl.670},
}
Figure