DynaAct: Large Language Model Reasoning with Dynamic Action Spaces

AI summary

Overview

Research area: Large language model reasoning, specifically test-time scaling and MDP-based sequential reasoning (machine learning, cs.LG).

Technical level: Advanced. The paper builds on Markov Decision Processes, Monte Carlo Tree Search, submodular optimization, and Q-learning, though its central idea can be understood without deep mathematics.

Scope: The paper proposes DynaAct, a framework that builds a small, dynamically selected candidate action space at each reasoning step by maximizing a utility-and-diversity submodular function, and shows gains on six benchmarks with Llama-3.1-8B-Instruct as the backbone.

What This Paper Is About

When a language model solves a hard problem step by step, it must decide what to do next, and that choice depends on which candidate actions it is even allowed to consider. Existing systems either hand-design those candidates (which does not scale across domains) or let the model search freely over natural language (which is computationally prohibitive). DynaAct's goal is to automatically learn a compact, information-dense set of candidate actions at every reasoning step, so that the search is both scalable and efficient.

Key Contributions

1. It frames dynamic action space construction as a research question in its own right, described by the authors as orthogonal to most existing work on LLM reasoning, test-time scaling, data curation, and reinforcement learning.
2. It introduces a submodular objective for action space construction that jointly scores candidate actions by their utility to the current reasoning state and by their diversity, so that a small subset can be chosen greedily.
3. It empirically verifies the method across six benchmarks spanning general, reasoning, and math domains, reporting improved accuracy over baselines while keeping inference latency comparable.
4. It releases an implementation at https://github.com/zhaoxlpku/DynaAct.

Main Findings

• Best result on all six benchmarks: DynaAct scores 70.22 on MMLU, 51.40 on MMLU-Pro, 39.39 on GPQA, 88.31 on ARC-C, 89.16 on GSM8K, and 61.00 on MATH-500. The strongest baselines for comparison score 69.66/49.36/34.34/80.63/86.66/52.00 for SC@maj16 and 68.61/48.81/36.87/86.43/87.11/54.20 for rStar.
• Largest gain is in math: The paper reports a 6.8% absolute gain over rStar on MATH-500 (61.00 versus 54.20) and states improvements of 1.37% on GSM8K and 6.80% on MATH-500 over the baselines.
• Every component matters: In the ablation on ARC-C and MATH-500, the full DynaAct scores 88.31 and 61.00. Removing the utility term gives 87.63 and 53.40; removing the diversity term gives 86.52 and 53.80; removing Q-learning from the embedding gives 87.80 and 55.80; removing the submodular function entirely gives the worst result at 85.15 and 52.00.
• Compact action spaces drive gains: Compared against RAP with sub-question actions, RAP's action spaces are described as highly redundant, showing limited improvement as rollouts grow at m = 5 or m = 10, and noticeable gains only at m = 15. DynaAct with m = 5 continues to improve as rollouts increase, and keeps its advantage across all tested values of m.
• Actions trigger more critical steps: On the Level 5 (most difficult) subset of MATH-500, DynaAct achieves 0.63 Critical Step Coverage and 31.34 accuracy, versus 0.47 and 26.87 for rStar.
• Latency is comparable: With m = 5 and 16 rollouts, relative time is 0.95 for rStar, 1.00 for DynaAct, and 1.12 for RAP (relative to DynaAct). DynaAct is slower than rStar but more accurate, and faster than RAP while scoring 61.00 versus 51.60.
• Limited scalability limits manually designed actions: The paper attributes rStar's weaker performance outside MATH-500 to the limited scalability of its five manually defined actions.
• Only a lightweight model is trained: The base LLM stays frozen; only the embedding model used inside the submodular function is trained.

Methodology in Plain English

DynaAct works in three stages.

First, it builds a rough approximation of the whole action space, called the proxy action space. The authors take a broad problem corpus (Open-Platypus), split it into 2,500 groups, and ask Llama-3.1-70B-Instruct to extract general "observation sketches" from each group — short cues that guide reasoning and are meant to transfer across problems. This yields 40,822 observations, with duplicates removed, forming the action space.

Second, it defines a scoring function that decides which actions are worth offering at a given reasoning state. The score combines two terms: a utility term, which measures how promising an action looks for the current state, and a diversity term, which penalizes candidates that are too similar to one another. The utility term is grounded in Q-learning: the embedding of the state dotted with the embedding of the action is trained to approximate the expected future reward. The embedding model is Llama-3.2-1B-Instruct (using the last token's embedding), fine-tuned on 83,083 state-action pairs with a learning rate of 1e-5, with reward 1 for the ground-truth action and 0 otherwise. The paper proves (Lemma 1, proof in Appendix E) that this combined function is submodular, and sets the balancing weights to alpha = 0.9 and beta = 0.1.

Third, it selects the actual candidate set. Because the function is submodular, a greedy algorithm can pick the m = 5 best actions with complexity O(m²|A|) instead of performing an exhaustive search. Reasoning then follows a standard Markov process: pick candidates with the greedy selection, estimate each one's value with Monte Carlo Tree Search (16 rollouts; Llama-3.1-8B-Instruct acts as the world model), take the highest-value action, and generate the next reasoning step. Because the candidate action embeddings are precomputed and cached, only the state embedding has to be computed online.

Why This Matters

Impact on research. Most work on LLM reasoning focuses on policy learning, reward modeling, data curation, or reinforcement learning. This paper targets a different lever — how the action space itself is built — and shows that a compact, learned space changes performance meaningfully. It also brings submodular optimization, previously applied to model interpretability and feature selection, into sequential reasoning for LLMs.

Real-world applications (implied by the method and benchmarks):

• Step-by-step math tutoring or homework-help systems, where reasoning traces must be both correct and efficient.
• Multi-step scientific or graduate-level question answering assistants, such as those in the GPQA and ARC-C style domains.
• Enterprise decision-support or agentic workflows where each step should be drawn from a small, curated set of operations rather than free-form text.
• Deployments with latency and compute budgets, since the paper reports no substantial latency increase over baselines such as rStar and lower latency than RAP.

Industry relevance. The setup is attractive operationally: the base LLM stays frozen and only a lightweight embedding model is trained, so the approach can be layered onto existing inference stacks. Automated action space construction also removes the manual engineering cost that limits hand-designed action sets like rStar's five actions.

Future Directions

• Scaling the proxy action space to broader domains or building domain-specific agents from domain-specific corpora, which the paper notes is straightforward.
• Studying the trade-off between candidate set size m, number of rollouts, and accuracy beyond the tested settings, since the paper's compactness study only covers a few values of m.
• Investigating how the utility definition (critical step coverage) could be extended to other tasks and difficulty levels; the paper confines its utility analysis to the Level 5 subset of MATH-500.
• Re-examining the remaining ablations and analyses: the paper defers the difficulty-level (RQ5) and action-diversity (RQ6) discussions to Appendix F, which is not included in the provided text.

Target Audience

Researchers and engineers working on LLM reasoning, test-time scaling, and agentic systems who are interested in how the candidate action space shapes search quality. It is also relevant to practitioners who want to reproduce or adapt a frozen-backbone reasoning pipeline with a small trainable component, and to readers familiar with MDPs, MCTS, or submodular optimization who want to see those tools applied to language model reasoning.

Authors’ abstract

In modern sequential decision-making systems, the construction of an optimal candidate action space is critical to efficient inference. However, existing approaches either rely on manually defined action spaces that lack scalability or utilize unstructured spaces that render exhaustive search computationally prohibitive. In this paper, we propose a novel framework named \textsc{DynaAct} for automatically constructing a compact action space to enhance sequential reasoning in complex problem-solving scenarios. Our method first estimates a proxy for the complete action space by extracting general sketches observed in a corpus covering diverse complex reasoning problems using large language models. We then formulate a submodular function that jointly evaluates candidate actions based on their utility to the current state and their diversity, and employ a greedy algorithm to select an optimal candidate set. Extensive experiments on six diverse standard benchmarks demonstrate that our approach significantly improves overall performance, while maintaining efficient inference without introducing substantial latency. The implementation is available at https://github.com/zhaoxlpku/DynaAct.