DynaAct: Large Language Model Reasoning with Dynamic Action Spaces

We genuinely appreciate your considerate and thorough feedback. We thoroughly respond to all of your concerns and questions below. We will also make sure to incorporate your insightful suggestions into the final version of the paper.

Q1: On the applicability of step-level MDP modeling

You raised a valid point regarding the notion of “step” in math and reasoning tasks, and the appropriateness of modeling them as MDPs. To clarify, our framework does not focus on single-step problems. In our setting, each “action” in the MCTS corresponds to a single reasoning step rather than the entire reasoning trace.

As you pointed out, agentic tasks such as WebArena and ScienceWorld are indeed more naturally framed as multi-step MDPs. We fully agree, and to further assess the broader applicability of our method beyond standard reasoning tasks, we applied DynaAct to both benchmarks. For evaluation, we adopt the official metrics defined by each benchmark and report the average performance over 10 independent runs to mitigate statistical variance. The results are as follows:

Our framework exhibits a considerable performance advantage over all baseline models, showcasing its versatility even in more intricate, agent-like settings.

Q2: Comparison with training-based methods

We appreciate this concern and would like to clarify that many training-based methods require significant data curation and fine-tuning effort, which limits their scalability and transferability across tasks. Moreover, in the context of strong instruct models (like Llama-3.1-8B-Instruct), we observed only marginal improvements with training-based methods.

To illustrate this, we compared our method with a training-based variant, where Llama-3.1-8B-Instruct was fine-tuned on the training sets of GSM8K and MATH-500, and evaluated on their respective test sets:

Furthermore, for certain benchmarks such as GPQA and MMLU, no training data is available, making our plug-and-play design particularly valuable.

Q3: Generalization to OOD tasks (e.g., AIME)

This is an excellent question that aligns with our core motivation. To evaluate this, we tested DynaAct on both AIME 2024 and AIME 2025 using Qwen3 as the backbone (due to Llama-3.1’s low base performance on these challenging tasks). The results are:

Qwen3-1.7B

Qwen3-4B

Qwen3-8B

Qwen3-14B

Qwen3-32B

These results confirm that our method retain effectiveness on unseen, harder evaluations.

Q4: On semantic duplication in action space

Currently, we only filter actions based on surface-form duplicates (i.e., exact matches). We will make this point clearer in the final version.

Q5: Sensitivity to the choice of m

Thank you for suggesting a deeper analysis of the parameter $m$, which controls the size of the action space at each reasoning step.

Here are the empirical results across six benchmarks:

As shown, $m = 5$ achieves a strong tradeoff between performance and redundancy. Beyond that, marginal gains taper off or slightly regress, possibly due to an overly large candidate set introducing distractors.

Q6: Human intuition vs. submodular function value

Thank you for your thoughtful question regarding the interpretability of our submodular objective. To demonstrate how the function behaves and whether it aligns with human intuition, we provide a concrete example below.

Given the following reasoning context:

Question: Is the Earth the center of the universe?

Answer: I clarify the problem by identifying the assumptions made in the past and restating them in my own words to better understand how they shaped the current situation. Early models placed Earth at the center, like Ptolemy’s.

We trace the evolution of the action space during the submodular optimization process:

As you can see, from step 1 to step 2, the submodular score increases significantly, reflecting a meaningful gain in both utility and diversity. The newly added action (Action 3) introduces a distinct angle of reasoning, thereby enriching the action space.

However, from step 2 to step 3, the increase becomes marginal. This is because Action 4 shares semantic overlap with Action 2 and Action 3 (all aiming at clarification and reframing), which leads to diminishing marginal gains under the submodular objective. This behavior aligns well with human intuition — once a range of complementary reasoning strategies is already covered, adding similar ones contributes less value.

We truly appreciate the time and expertise you dedicated to reviewing our work. Your comments have helped sharpen the focus and rigor of our contributions. Please don’t hesitate to let us know if further clarifications are needed.

Thanks a lot for the authors' response. I have raised the clarity score as the authors have clarified most of my concerns. And I keep my overall rating since it is positive.

We sincerely thank you for your detailed and constructive review. We appreciate your positive comments on the writing quality, the breadth of the evaluation, and the analysis. Below, we carefully address each of your insightful concerns. We will also make sure to incorporate your insightful suggestions into the final version of the paper.

Q1: Generalization across model backbones and sizes

Thank you for raising this important point regarding the generalizability of the proposed method. We have conducted additional experiments using Qwen-2.5 models of various sizes (1.5B, 7B, and 72B) to evaluate the robustness and transferability of the submodular action selection framework. Below are the results:

Qwen-2.5-1.5B-Instruct

Qwen-2.5-7B-Instruct

Qwen-2.5-72B-Instruct

These results demonstrate that DynaAct consistently outperforms strong baselines across different model sizes.

Q2: Qualitative analysis of action selection process

You bring up an important point regarding interpretability. While our primary focus has been on quantitative evaluation, we fully agree that qualitative insights are essential for understanding how and why the method behaves as it does.

In addition to the three examples in Appendix F.9, we are glad to include more comprehensive failure cases to highlight the limitations and edge behaviors of the method in the final version. Furthermore, we provide a more detailed illustration of how the action space evolves during the submodular optimization process, which helps demonstrate how DynaAct progressively refines the candidate set to balance utility and diversity.

Given the reasoning context:

Question: Is the Earth the center of the universe?

Answer: I clarify the problem by identifying the assumptions made in the past and restating them in my own words to better understand how they shaped the current situation. Early models placed Earth at the center, like Ptolemy’s.

The change in the action space across optimization steps is shown below:

This example highlights how the action set grows more diverse and focused with each step, improving the coverage of reasoning strategies relevant to the given context. We appreciate your suggestion and believe this qualitative illustration helps clarify the internal dynamics of our method and enhances its interpretability.

Q3: Comparison with few-shot prompting / dynamic exemplar selection

Thank you for drawing this insightful connection. To better contextualize our method, we compared DynaAct with strong few-shot prompting baselines, including GritLM, Gecko, and Instructor:

These results show that DynaAct consistently outperforms competitive few-shot baselines across all tasks, reinforcing its effectiveness.

Q4: Release of observations from Section 4.4

Yes, absolutely. We are committed to open-sourcing the observations described in Section 4.4 to support reproducibility and foster further research in this area. We appreciate your encouragement on this front.

Once again, thank you for your thoughtful and constructive feedback. We believe your suggestions have helped us further validate and clarify the contributions of our work.

Thank you very much for your thoughtful and constructive review. We truly appreciate your recognition of our work and your encouraging feedback on its clarity, novelty, and significance. We will also make sure to incorporate your insightful suggestions into the final version of the paper. Below, we address your specific questions in detail:

Q1: Can this be applied to tasks with highly dynamic and unpredictable action spaces? For example in robotics?

We value your insightful question about the relevance of our method in fields with extremely dynamic and unpredictable action environments, like robotics. To investigate this, we carried out further experiments on Alfworld [1], a recognized benchmark for embodied agents. Alfworld features six categories of domestic chores that differ in complexity and unpredictability. Following the official evaluation protocol, we use success rate as the evaluation metric. We evaluated our approach using the unseen test set composed of 134 instances, averaging the results over 10 runs to minimize statistical variance.

Here are the results:

As you can see, DynaAct substantially outperforms all baselines across all task types. This suggests that your concern is well-addressed in practice: DynaAct indeed generalizes effectively to settings with dynamic and complex action spaces, such as those found in robotics.

Q2: Submodular optimization can be computationally expensive. Do you see any scalability problems related to this for large complex domains?

Thank you for bringing up this significant matter. We recognize the worries about the computational expense of submodular optimization. To specify, according to our profiling and quantitative analysis (refer to Table 8), the primary source of computational burden in our framework originates from the MCTS component instead of the submodular optimization phase. Indeed, the submodular optimization we use is executed through a greedy algorithm with linear time complexity, which proves to be highly effective in real-world applications. Additionally, as mentioned in Appendix F.6, the main factor for scalability is the magnitude of the proxy action space. In our approach, DynaAct performs effectively even with extensive proxy action spaces owing to two key strategies: (1) Storing action embeddings, which prevents unnecessary calculations across various evaluations; and (2) Linear-time greedy submodular selection, which guarantees that potential actions can be chosen efficiently without exhaustive searching. Therefore, we are confident DynaAct can manage large and intricate domains without major computational limitations because of the submodular optimization itself.

Thank you again for your insightful feedback. We trust that these explanations alleviate your concerns completely and showcase the broad applicability and effectiveness of our method.

Reference:

[1] Shridhar, M., Yuan, X., Côté, M. A., Bisk, Y., Trischler, A., & Hausknecht, M. (2020). Alfworld: Aligning text and embodied environments for interactive learning.

We truly appreciate your considerate and insightful feedback. We are pleased that you consider our paper to be well-written and technically sound. We meticulously respond to all of your questions and suggestions in depth below. We will also make sure to incorporate your insightful suggestions into the final version of the paper.

Q1: Novelty of high-level actions

We understand your concern that constructing high-level actions to group similar low-level actions has been previously explored in the literature, as noted in Section 1 of our manuscript. However, we would like to clarify that the key novelty of our work lies not in the general concept of high-level actions per se, but in the principled construction of a compact and scalable action space. We believe this direction — making high-level actions scalable, compact, and generalizable in a unified framework — addresses an under-explored and practically important challenge in the field.

Q2: How is the number of high-level actions determined?

I appreciate you bringing this to attention. To clarify, our framework does not involve partitioning actions into disjoint “subsets.” Rather, we dynamically construct a set of high-level actions to serve as the compact action space at each step of reasoning.

In our current implementation, we empirically fix the number of high-level actions $m$ to 5, which strikes a good balance between expressiveness and search efficiency. We also conducted ablation studies to investigate how varying $m$ impacts performance. The results are summarized below:

As shown, $m=5$ achieves consistently strong performance across benchmarks, and increasing $m$ beyond this point provides diminishing or even negative returns. We will make this clearer in our paper revision.

Q3: Fragility of embedding-based clustering

You raised an excellent point about the limitations of embedding-based clustering. We agree that naive clustering of embeddings can be fragile. Indeed, our own experiments (see Appendix F.5) show that using pure embedding-based methods without additional regularization leads to unstable results.

To address this, our method integrates submodular selection as a principled approach to ensure both coverage and diversity of action candidates. We also compared this with a variant where action categories are directly derived from LLM reasoning. Specifically, we use Llama-3.1-8B-Instruct to generate high-level actions at each step, conditioned on the trajectory so far, without applying submodular selection (referred to as “– submodular” in Table 2). The performance of this LLM-based variant was significantly lower due to reduced compactness and increased redundancy, which negatively impacts the MCTS exploration efficiency.

Therefore, while we appreciate the benefit of pure LLM-driven clustering, our empirical findings suggest that submodular selection yields a better trade-off between semantic relevance and decision efficiency.

Q4: Evaluation on Qwen3 and AIME benchmarks

Thank you for suggesting additional evaluation on the Qwen3 model series and AIME24/25 benchmarks. We fully agree that incorporating newer models and more challenging datasets can strengthen the empirical foundation of our work.

We would like to clarify that the Qwen3 series was released only about two weeks before the submission deadline, which limited our ability to include these models in our original experiments. Nonetheless, we have since conducted a comprehensive set of evaluations using Qwen3 Series on AIME 2024 and AIME 2025

Below are the results:

Qwen3-1.7B

Qwen3-4B

Qwen3-8B

Qwen3-14B

Qwen3-32B

These results clearly demonstrate that DynaAct consistently improves the problem-solving capabilities of Qwen3 models, often by large margins over the strong baselines.

We hope these additional results effectively address your concerns and further strengthen the empirical impact of our work.

We appreciate your thorough review and valuable comments once more. Your feedback has improved our understanding of how to convey the value and merits of our work, and we sincerely value your suggestions.