AQA-Bench: An Interactive Benchmark for Evaluating LLMs’ Sequential Reasoning Ability in Algorithmic Environments
Authors: Siwei Yang
Bingchen Zhao
Cihang Xie
Venue: Accepted by TMLR ()

Abstract: This paper introduces AQA-Bench, a novel benchmark to assess the sequential reasoning capabilities of large language models (LLMs) in algorithmic contexts, such as depth-first search (DFS). The key feature of our evaluation benchmark lies in its interactive evaluation protocol — for example, in DFS, the availability of each node’s connected edge is contingent upon the model’s traversal to that node, thereby necessitating the LLM’s ability to effectively remember visited nodes and strategize subsequent moves considering the possible environmental feedback in the future steps. We comprehensively build AQA-Bench with three different algorithms, namely binary search, depth-first search, and breadth-first search, and to evaluate the sequential reasoning ability of 14 different LLMs. Our investigations reveal several interesting findings: (1) Closed-source models like GPT-4 and Gemini generally show much stronger sequential reasoning ability, significantly outperforming open-source LLMs. (2) Naively providing in-context examples may inadvertently hurt few-shot performance in an interactive environment due to over-fitting to examples. (3) Instead of using optimal steps from another test case as the in-context example, a very limited number of predecessor steps in the current test case following the optimal policy can substantially boost small models’ performance. (4) The performance gap between weak models and strong models is greatly due to the incapability of weak models to start well. (5) The scaling correlation between performance and model size is not always significant, sometimes even showcasing an inverse trend. We hope our study can catalyze future work on advancing the understanding and enhancement of LLMs’ capabilities in sequential reasoning.

Published in Transactions on Machine Learning Research (06/2025)
AQA-Bench. An Interactive Benchmark for Evaluating LLMs' Sequential Reasoning Ability in Algorithmic Environ- ments
Siwei Yang"
Bingchen Zhao*2
Cihang Xie
"equal technical contribution
'CC Santa Cruz
UUniversity of Edinburgh
Reviewed on OpenReview:
Abstract
This paper introduces AQA-Bench, a novel benchmark to assess the sequential reasoning capabilities of large language models (LLMss) in algorithmic contexts, such as depth-first search (DFS). The key feature of our evaluation benchmark lics in its interactive evaluation protocol - for example, in DFS, the availability of each node's connected edge is cont upon the model's traversal to that node, thereby necessitating the LLM's ability to effec- tively remember visited nodes and strategize subscquent moves considcring the possible en- vironmental feedback the future steps. We comprehensively build AQA- with three different algorithms, namely binary search, depth-first search, and breadth-first search, and to evaluate the sequential reasoning ability of 14 different LLMs. Our investigations reveal several interesting findings: (1) Closed-source source models like GPT-4 and Gemini generally show much stronger sequential reasoning ability, significantly outperforming open-source LLMss. (2) Naively providing in-context examples may inadvertently hurt few-shot performance in an interactive environment due to over-fitting to examples.
(3) Instead of using optimal steps from another test case as the in-context example, a very limited number of predeces- sor steps in the current test case following the optimal policy can substantially boost small models' performance.
(4) The performance gap between weak models and strong models is greatly due to the incapability of weak models to start well. (5) The scaling correlation between performance and model size is not always significant, sometimes even showcasing inverse trend. We hope our study can catalyze future work on advancing the understanding and enhancement of LLMs' capabilities in sequential reasoning. The code is available al https:// http://ggtttuuboom http://gggaabbboo/CCCCCC///LLL UCSC-VLAA/AQA-
1 Introduction
Recent advancements in Large Language Models (LLMs) have led to impressive strides in reasoning across a diverse array of linguistic tasks, as evidenced by a growing body of research (Wei al. 2022 Wang
ct al. 2022 Brown al.) 2020 OpenAl 2023). The reasoning capabilities of these models have typically been assessed through benchunarks locusing on arithmetic reasoning (Cobbe al., 2021 Ling al. 2017
symbolic inference (Suzgun et al. 20222. knowledge (Hendrycks et al.) 2020), and science understanding [Hendrycks et al., 2021). These benchmarks require LLMs to engage in multi-step reasoning, leveraging both the context provided by the question and their internally learned world knowledge (Wei et al. 2022
Nevertheless, a critical limitation of these existing benchmarks their reliance on one-off interactions, predominantly the form of multiple-choice questions or singlo-response queries. While these metrics offer valuable insights into the LLMs' reasoning abilities, they fall short in evaluating other erucial aspects of intelligence. Specifically, they do not assess the models' capacity for procedural adherence, active memory

---

Published in Transactions on Machine Learning Research (06/2025)
maintenance, and ability to think ahead, which are elements vital for more complex, sequential reasoning tasks. To address this, agentic benchmarks, such as WebArena (Zhou et al. 2023 Mind2Web (Deng et al. 2023), and VisualWebArena (Koh et al. 2024), have been developed to evaluate LLMs in real-world situations where such abilities are essential. However, there are still two major drawbacks for such agentic benchmarks. First, scaling these benchmarks and quantifying environmental complexity remains difficult, complicating the systematic exploration of how these factors impact model performance. Morcover, due to the lack of known optimal strategies for these tasks, of various prompting techniques (Wei et al. 2022 Zhou et a on model outcomes.
difficult to guide LLMs effectively and investigate the influence
In this work, we aim to bridge this evaluation gap in benchmarks, thereby offering better understanding and measuring the cognitive capabilities of LLMs in mimicking human-like reasoning processes. To this end, we hereby develop an interactive Q&A benchmark, referred to as Algorithmic- QA benchmark (AQA- Bench), specifically designed quantitatively assess LLMs' proficiency executing predefined algorithmic procedures. These procodures necessitate basic reasoning over observed data, coupled with the updating of internal or external state that represents a specific data structure. One such example is solving a maze problem using the depth-first search algorithm - In each interactive instance, the model is provided with only the node ID it occupies and the edges connected to that node, representing the observed data; based on this current information and its visiting history, the model must then determine which edge to follow to progress to the subsequent node. Additionally, sequential reasoning, which is what AQA-Bench is targeting, also requires models to think ahead of the current time, considering possible environmental feedback that may receive in future steps. Take binary search as an Example. Although the probability of the targeting being any number in the given range is the same, the most optimal policy is still choosing the middle one the current guess, this policy can best reduce search space in the future. Through this interactive design, our AQA-Bench can effectively gauge the LLMs' capabilities in sequential reasoning in algorithmic enviromments. In comparison to current agentic benchmarks, our proposed AQA-Bench is more readily scalable in terms of environmental complexity and the number of test cases, facilitating alignment with the latest models. Furthermore, as the optimal strategies in our environments are known, AQA-Bench can examine the impact of various guidance forms, such as in-context examples and teacher guiding, on model performance, thus providing more comprehensive empirical foundation for detailed analysis.
We empirically build AQA-Bench utilizing three al- gorithms: (1) Binary search, wherein the model's task is to deduce a number within a specified range, idcally employing the binary scarch algorithm. (2) Depth-first search (DFS), where the model navigates a graph to map all nodes and edges. (3) Breadth- first search (BFS), similar to DFS, but with an ex- plicit requirement for the model to apply the BFS algorithm instead. The corresponding evaluations reveal 5 interesting findings: 1) The closed-source models like GPT-4 and Gemini strongly dominate all open-source LLMs on sequential reasoning. 2) Naively providing interactive examples may inad- vertently hurt few-shot performance, probably due to overfitting with in-context learning. This trend is observed even with the advanced GPT-4 and Gemini-Pro in certain SoAA-ennheeviroomenns 3) Given a few predecessor steps under the optimal policy, the performance of small models can be sig- nificantly improved, sometimes even comparable to large models. 4) The difference in performance be- tween weak and strong models largely stems from the inability of weak models to have a good initial performance. 5) The scaling correlation between performance and model size is not always signifi-
You are required to guess the random number have just picked between and 20 Instruction
Picked random number:
Evaluator
Model
Start
10
The true number smaller than
The true number bigger than 5
The true number is smaller than 8
Right answer!
The equal to 7
Figure 1: Illustration of AQA-Bench's 's evaluation pro- cess. After receiving instruction regarding the task goal, the tested model will interact with the evaluator in the form of a Q&A conversation. Metrics measuring the model's capability of achieving the task goal and following the intended algorithm are calculated based on the process. Note this is not the actual prompt we fed the model.
2

---

Published in Transactions on Machine Learning Research (06/2025)
cant, sometimes even showcasing an inverse trend. This contradicts common assertions in LLM development and points to an oversight of sequential reasoning capabilities and "overfitting" to provided exemplars in the practice of in-context learning in current LLM research. We hope our AQA-Bench can serve as use- ful benchmark for future research focused on evaluating and enhancing the sequential reasoning abilitics of LLMs.
2 Evaluation Environments
2.1 Motivation behind Environment Design
AQA-Bench focuses on assessing LLMs' sequential reasoning ability with algorithmic environments mainly due to the following reasons.
Scalable dataset. Massive data for training and lesting can be dynamically generated without human effort. It should be noted that only enviromment settings such as nodes and edges are pre-generated. Environments' responses to the models' interactions are not pre-defined but generated dynamically according to the models' behavior.
Controllable complexity. The complexity of environments can be controlled by just a few hyper- parameters. Since LLMs still evolving at very rapid pacc, traditional benchmarks may have short life before re-development is required, while our AQA-Bench can still evaluate increasingly more powerful LLMs due to the flexible complexity of environments.
Known optimal policy Since the optimal policy is alrcady known, it is much casier for us to determine whether the test model performing the desired algorithm. This also enables teacher- teacher-guiding evaluation mode, which will be introduced Sec. 3.3
Additionally, this is crucial to keep the environments initially opaque to the tested model so that it can be forced to actively interact with the environments to gain the information necessary for performing the task via multi-time interactions. Otherwise, the task can be solved in a mega single-time generation with perhaps explicit or implicit chain-of-thought (Wei et al. 2022), and there will be no need for sequential reasoning ability.
2.2 Base Environment
We hereby introduce the design of three basic interactive environments. In each environment, instructions about the objective are initially fod to the model via the system prompt, while the information about the current enviroument is only revealed to the model following its response. Our design makes sure that the key information for making decisions can only be gained by interacting with the environment so that the model can be evaluated based on how it can plan and execute the optimal strategy. Thus, the tested model is forced to perform sequential planning by actively exploring the environment and adjusting its response according to feedback alternately.
Base Env 1: GuessNum. The objective of the Guess.Num environment is for the model to accurately predict a number predetermined by the evaluator. During each interaction, the model interacts with the environment by guessing a number and receives feedback indicating whether guessed number higher or lower than the predetermined number. The optimal strategy this sccnario involves the model implementing binary search. Consequently, the performance in this environment serves an indicator of the model's understanding of the binary search algorithm.
Base Env 2: DFS. In this environment, the model is tasked with navigating a graph using the DFS algorithm. Initially, the model is presented with information about its current node and the edges connected to that node. The model interacts with the environments by deciding which edge it will follow, and then the environment will update the model with the information of the newly reached node and its associated edges. The model's performance is evaluated based on its adherence to the DFS policy. Critical the evaluation is the ability to comprehend and implement the concept of frrst-in-last-out stack, along with maintaining
3

---

Published in Transactions on Machine Learning Research (06/2025)
memory of previously visited nodes. The process of the DFS algorithm is described in the instructions to reduce difficulty.
Base Env 3: BFS. This enviromment closely mirrors the DFS environment in structure but diverges in its core algorithmic requirement, instructing the model to employ the BFS algorithm for graph navigation. This key distinction enables the BFS environment specifically assess the model's comprehension of the first-inffisstouu queue principle, a fundamental aspect of BFS.
2.3 Embodied Environment
We additionally design embodied environments where the information about each base environment is re- placed with more real-life background descriptions. These embodied environments can then be used assess if the model can perform sequential reasoning with irrelevant information, and if the model can abstract algorithmic problems from real-life situations and find the optimal algorithms.
Embodied Env 1: Coin (GuessNum). The tested model is required to play a hero encountering witch guarding a chest of gold coins in a hidden temple. To claim the prize, the model needs to guess the number of gold coins with limited chances.
Embodied Env CaveDFS (DFS). Rather than navigating graph, the model is required play as an explorer to visit all the caves in an underground cave system in fewest steps possible. Unlike the DFS environment, the model is not explicitly required to use any algorithm but the objective naturally demands the DFS algorithm.
Embodied Env 3: CaveBFS (BFS). Similar to CaveDFSS environment, this environment requests the tested model to traverse an underground cave system as well but as a group. The group can split into smaller groups to visit adjacent caves without backtracing. This environment doesn't explicitly call for a specific algorithm as well.
3 Evaluation
3.1 Metrics
To holistically assess performance in each environment, we design two specific metrics. The first is the goal metric, which evaluates how close is the model's final output to the ground truth; the second is the policy metric, which measures the efficiency of the model's policy. For the goal metrie, adopt error-based approach where lower scores are preferable. This design choice enables the goal metric at cach intermediato step can be accumulated as the policy metric to measure how fast the model's output converges to the final objective. Note that we typically prioritize the goal metric over the policy metric when comparing the performance of two models. This hierarchy metric evaluation is crucial due to the observed tendency of perforrefonnn models to prematurely exit the evaluation process. Such early termination is typically a result of generating invalid responses, therefore leading lower goal metric score but sometimes higher policy metric score.
GuessNum (Coin) requires the model to accurately guess the number specified by the evaluator. For the goal metric in this environment, we use the minimal error of the responses from the model to the target number, which is defined as
1g, g
Errmin max H L+-++1
(1)
where 9i is the guess model produced in the i-th step of interaction, 9 is the target number, and H and L denote the upper and lower bound of the guessing range. As for the policy metric, we accurullate the error between each guess and the target number, and define the metric as:
19s - 9 Errsum -H 1+11+1
(2)
4

---

Published in Transactions on Machine Learning Research (06/2025)
System: required to guess number between 0 and
You are required to guess a number between 0 and 1024
Q: Start
Q: Start
Q: The true number smaller than 4.
Q: The true number is bigger than
2
A: 20
Q: The true number bigger than 2.
Q: The true number is bigger than 20
A: 3
Q: Right answer. The true number is equal to 3.
ICE
A:
(b) Interactions w/o teacher-guiding
Q: Start
A: 4
System: You are required to guess a number between and Start
Q: The true number bigger than
6
T:
Q: Right answer. The true number equal 6.
The number is smaller than
A-
T:2
Start
Q: The true number is bigger than 2. Ac...
Actual Interaction
T:...
Q: The true number bigger than 4.
A:
(c) Interactions w/ leacher-guiding
(a) Interactions with in-context examples (ICE=2)
Figure 2: (a) Evaluation with In-context example. The interactions of the optimal policy and the environ- ment on the of test cases are used as examples, which can provide additional contextual information about the algorithm for in-context learning. (b,c) When teacher- guiding is enabled, the responses are replaced with the optimal ones to ensure no error will accumulate.
seacher-guiding
Given the similar objectives of the DFS (CaveDFS) and BFS (CaveBFS) environments, we employ a consistent metric evaluate performance in both. The primary goal in these environments to achieve full graph traversal. Accordingly, we define the goal metric, denoted as Gmins measure the extent of node coverage in relation to the total number of nodes in the graph. Let M represent the total number of nodes in the graph, and (a), denote the set of nodes visited by the model up to the i-th interaction step. The goal metric is then formulated as follows:
Ka)d M
(a)-1l M
Gmin = max
where Ka)-il is the number unique nodes visited by the model by the end of the interaction.
Similarly, we define policy metric, Gsum; as the cumulative gap in graph coverage throughout the interaction:
Ka)
Gsum Σ
M
Furthermore, we introduce the ratio between the step number Kiollow that the model follows the algorithm and the total number of steps the model takes Keotal to access the efficiency of models' policy:
Krollow
ACC
K
3.2 In-context Examples
Wei et al. (0022 argue LLM's strong reasoning abilities are, in part, attributable to their in-context learning abilitics. Built upon this insight, we also incorporate it into the design of our benchmark. In Fig. ((a) we outline our prolocol for testing in-context examples within our benchmark. Specifically, it involves integrating a series interaction examples between the optimal teacher model and the environment into the model's context. These in-context examples are expected to serve as a foundational reference, aiding the model in comprehending the expected interaction dynamics and decision-makiin processes in each specific environment.
5

---

Published in Transactions on Machine Learning Research (06/2025)
3.3 Teacher Guiding
Directly evaluating the model on the interaction will lead to error accumulation. Such errors can result in catastrophic failure, even with strong models, due to the dependency of each step on its predecessors. However, also interesting to check whether correct interaction steps may also improve models' generation. To investigate this issue, we implement a strategy termed Teacher- Guiding. This approach involves using the intented algorithm as the optimal policy, tailored for each environment, which acts as teacher model. The teacher model amends the outputs of the subject model, ensuring that any incorrect decision made an intermediate step does not adversely impact subsequent interactions. The implementation of this procedure is rated in Fig. 2
We specifically designed metric named Per-step ACC for this mode, defined as
N No.
PSACC
where N& is the number of test cases in which the model follows the algorithm at the k-th step, and Mi is the number test cases of which the optimal policy takes at least & steps. Thus, PSACC₁ can be roughly viewed as the probability of the model following the algorithm at the k-th step given that the algorithm is followed all the predecessor steps.
The averaged PSACC across all Kmax steps in the optimal policy is used evaluate models' overall self- guiding ability:
PSACC
PSACC avg
(5)
K Kmax
It should be noted that major difference between teacher-guidee and in-context examples described in Sec. 3.2 is that the reference is from the current test case when evaluating with teacher-guiding while with in-context examples the reference is from other Lest cases.
4 Experiments
We evaluate models on all the environments. For the GuessNum and Coin, we set the target mumber between 32 and 32800, For the DFS and CaveDFS, we set the number of graph nodes to 8. For the BFS and CaveBFS, we set the number of graph nodes to 15. The worst-case runtime of the optimal policy for environments is about 15 sleps so we run evaluation with the maximum number of interactions being 20. In addition this EASY mode, we also develop a HARD mode with a target range of 32 3.3 107 for GuessNum and Coin, 13 nodes for DFS and CaveDFS, 25 nodes for BFS and CaveBFS. The optimal worst-case runtime is about 25 sleps and the maximum number of interaction steps is 30. Results under the EASY mode are reported by default.
For casier comparison, we divided models into 4 categorics according to the number paramcters:
Small models with 10B parameters: Llama2-7B-chat Touvron et al. 2023
Llama3-88 8B-
Instruct Team 2024 (reuna-BBvv.5--1e (Chiang et al. 2023). Mistral-7h uustruct-v0.2 (Jang
et al.
2023 DeepSeck-LLMM775 Bi et al. 2024) and DeepSeck-MoF-1on Dai et al.
2024
Medium models with 2 10B and 50B parameters: Llama2-13B-chatt Vicuna- 13B-v1.
12..v15--11 10.5--166 16K
Mixtral--xx7B.-nstrnctt-w (Jiang et al. 2024 and DeepStck-Rt--issilll..ee 2025).
DeepSeck--T
Large models with 2 50B parameters: Llama2-70B-chat and DeepScck-LLM-667B
Closed-source models: GPT-335-Turbe GPT-4-Turbo OpenAl 2023
Gemini-Pro
TTam et al.
2023) and O1-Previow OPenAA 2024).
Note that Figs. 2(a) and 2(c) are only for demonstration, the actual prompt fed the model the Appendix

---

Published in Transactions on Machine Learning Research (06/2025)
For mixture-of-experts models (e.g., DeepSeek-MoE-1663 number of activated parameters during inference. All evaluations are run with zero-shot and without teacher- guiding by default.
we only consider the
4.1 Re-productivity and Variance
Although test cases in our AQA-Bench can be generated dynamically during evaluation, we still pre-generated a test set with 400 test cases for each base environment under the EASY mode and 1500 test cases under the HARD mode for simpler re-production. The final scores are averaged among test. cases. A variance study on the pre-generated test set is discussed in Appendix L showing that the evaluation results drawn from our test. set can sulficiently represent the lested models' performance in environments with this level of complexity. Another factor that may affect our results is the randomness of the model itself. For open-source models and Gemini-Pro, we disable the random sampling in all the experiments. But for GPTs, which can only be accessed via OpenAl API, we cannot turn off such model randomness. However, as shown in the supplementary Appendix B.1 the variance observed in GPT models is relatively minor.
4.2
Main Results
Base environments. star by investigating models' algorithmic sequential reasoning abilities by running evaluations three basc environments: GuessNum, DFS, and BFS. These evaluations were conducted naively, without the incorporation of in-context examples or teacher guidance. As shown in Tab. [ closed- source models like GPTs and Gemini generally exhibit much superior performance compared to most of the tested open-source models; The only exception among tested environments is the DFS environment, where open-source models outperform (PT-3.5-Turbb, but are still not as good as GPT-4-Turbo and Gemini-Pro.
Next, among open-source models, one interesting observation is that more recently released models (e.g., Mistral, Deepseek- LLM) are arguably better than relatively older ones (e.g., Llama, Vicuna). For example, Mixtral-&xx7--Instruct
which claimed to be better than chat in GuessNum and BFS but falls short in DFS. As for the Moo--eee--Mo-16 model, which out- performs Llaha2-7B-chat on conventional language benchmarks (Bi et al. 2024), underperforms Llama2- 7B-chat across all three tested environments. Notably, Llama3-70B-IIstruee, being the best open-source non-reasoning we tested, still manages to achieve higher performance than P-T-3..-Turbo, even surpass closed-source models in CaveBFS.
does excel Llama2-70B-
As for the recently trending reasoning models, it is particularly worth mentioning that O1-Preview almost achieves the task goal all test cases with a substantially low goal metric and much higher accuracy, suggesting that strong reasoning models can not only excel in single-round Q&A tasks but also in interactive environments that require long-term planning.
The other reasoning model we tested is DegpSeek-ii-Dssilll-wews.. worse goal metrics than other medium models, especially under HARD Mode, as shown in Tab. [ This suggests that for a weaker reasoning model, it is better at following the optimal policy at the beginning of a full trajeotory but quickly failed to adhere, resulting in an early termination of the interaction and much worse goal metrics, which likely due to the incrcased token length of reasoning models. Unlike O1-Preview, a reasoning model built upon weaker base model with a much shorted supported token length might be greatly held back by this issue, which is lot more server in interactive environments compared to single-round Q&& tasks.
showing much better ACCs but
Embodied environments. The findings from the embodied environments, as detailed in Tab. | largely mirror the conclusions drawn from the base environments. Moreover, as shown in Fig. 3 we interestingly note that models don't consistently perform worse in embodicd environments, although these embodicd environments require models to implicitly abstract from the environments and decide the optimal algorithm to execute, thus expected to be more difficult for models.
7

---

Published in Transactions on Machine Learning Research (06/2025)
Table 1: The main evaluation results with all environments. For models with strong goal metrics (e.g., Errmin: Gmin) indicting weak performance, goal metrics are more informative than policy metries (e.g.. Errsum, Gaum, ACC).
Base Envs under EASY Mode
Embodied Envs under EASY Mode
Model
GueseNum
DFS
BFS
Model
Coan
CaveDES
CaveBES
Eriain 4 ACC 1 Gan 1. ACC Gmi
ACC
Eremns 4 ACC Guis 4 ACC Gain ACC
Small 10B
Small < 10H
Llama227B BB-chat
0.26
0.00
0.58
0.21
0.60
0.00
Liama2 BB-hhtt
0.07
0.00
0.50
0.33
0.76
0.05
0.01
0.00
0.21
0.51
0.02
0.23
-lamaa--0-Innsrres
0.07
0.00
0.17
0.40
0.10
0.16
Vicuma 7B
0.46
0.000
0.65
0.15
0.84
0.03
Vicuna-7
1.00
0.00
0.54
0.21
0.72
0.07
Mistral-7B Ins02uct-v0.22
0.06
0.00
0.19
0.61
0.21
0.13
Miskral-7B - 78-Inneruct--0..
0.07
0.00
0.49
0.18
0.27
0.11
Seep LLM-7B
0.43
0.00
0.31
0.36
0.52
0.00
DeepStekkLLLa LLMM
0.39
0.00
0.58
0.16
0.77
0.0L
DiepSeell MoE-16B
1.00
0.00
0.63
0.07
0.88
0.02
DeepStek-MoE MoE--6B
1,00
0.00
0.71
0.11
0.89
0.01
10B s. Medium < 50D
10D S Medium < 500
0:41
0.65
0.05
0.39
0.38
0.36
0.55
0.09
Vlemmn-33B
0.39
0.00
0.66
0.12
0.81
0.05
Vicana-133 133
1.00
0.00
0.56
0.21
0.64
0.06
0.00
0.57
0.14
0.21
Mixiral-8s
0.00
0.45
0.15
0.17
DoegSooll-R1. RR-Dietill--een-------0
0.12
0.05
0.58
0.43
0.72
0.13
0.18
0.06
0.72
0.13
0.58
0.44
Large
50B
Large 2 500
Llama2-70B-on 700-hhht
0.11
0.00
0.33
0.44
0.28
0.06
1lama2-70--ah
0.00
0.00
0.35
0.44
0.30
0.03
Hlema3-70/B--msee Instuutt
0.01
0.00
0.10
0.68
0.01
0.53
0.03
0.00
0.03
0.76
0.01
0.17
DoegSooll LLM-77
0.12
0.00
0.40
0.42
0.45
0.09
De.pSock-LLM--61
0.36
0.00
0.28
0.57
0.38
0.08
Cloeed-sonce
Closed-suure
GPT-3355 Turbo
0.00
0.01
0.35
0.61
0.11
0.52
GPT-335- -.T-
0.00
0.00
0.20
0.86
0.27
0.10
CPT-4-Turbo
0.00
0.46
0.03
0.94
0.00
0.38
GPT-4-Turbo
0.00
0.50
0.23
0.74
0.12
0.16
Gemini-Pro
0.00
0.00
0.25
0.76
0.06
0.17
Gemini- Pro
0.00
0.00
0.22
0.70
0.10
0.16
O1-Preview
0.00
0.43
0.00
1.00
0.00
0.99
O1-Preview
0.00
0.05
0.00
1.00
0.12
0.08
Base Envs under HARD Mode
Embodied Envs under HARD Mode
GuessNum
DFS
BFS
Model
Coin
CaseDES
CaeRBFS
Ertom L 1 Gmm ACC 1 Gain J ACC 1
Model
Ertans Small < 10B
ACC Gan ACC
Gatn
ACC
Small < 10B
0.49
0.00
0.74
0.19
0.01
Maam22-7B-caa
0.49
0.00
0.68
0.19
0.53
0.04
3-amaa3-8--usstaa
0.07
0.00
0.41
0.43
0.07
0.13
Llana3 SB-Instruct
0.07
0.00
0.29
0.29
0.22
0.09
Vicuma-7B
0.24
0.00
0.78
0.10
0.80
0.02
Vicuma-78
0.49
0.00
0.70
0.13
0.83
0.05
Misttaal77B-losstuutt--222
0.00
0.65
0.61
0.08
0.08
0.00
0.61
0.50
0.49
0.07
De.gSocl-LLLM-77
0.49
0.00
0.61
0.18
0.71
0.04
DeepSeck-LLMN
0.49
0.00
0.74
0.11
0.86
0.03
DeegSeel-MoB-11
1.00
0.00
0.78
0.03
0.92
0.01
DoopSook-Mo-1119
1.00
0.00
0.86
0.05
0.34
0.01
10B
Medium
50B
10B x Mediun < 50B
Llama2-1300 1aah-httt
0.49
0.00
0.59
0.25
0.76
0.03
Mamm2-133l-chht
0.08
0.00
0.56
0.28
0.68
0.06
Vicuma-135 13B
0.49
0.00
0.80
0.07
0.83
0.03
Vicuma-199 193
1.00
0.00
0.65
0.17
0.71
0.05
Mixteal-Sx7BB. Instraccstt
0.00
0.58
0.13
Bostral-Sxx7--Insttec
0.07
0.00
0.50
0.38
0.30
0.09
0.00
0.00
0.51
0.28
0.67
0.05
DeepSeek- RU--Dittlll----- QwenllQQeenn
0.19
0.07
0.73
0.38
0.84
0.13
Large 2 50B
Large 2 508
1amma2-70B-hhan
0.49
0.00
0.48
0.35
0.43
0.04
Llana2 70B chat
0.08
0.00
0.49
0.33
0.80
0.02
Mamaa--70R-Instror
0.00
0.00
0.25
0.56
0.02
0.37
Elama3-700-Inntt
0.00
0.13
0.56
0.05
0.09
MeegSeek-LLM-G7
0.00
0.00
0.51
0.28
0.67
0.06
DeepSesk LLM
0.02
0.00
0.39
0.10
0.58
0.06
Closed source
Closed-souros
GPT-4-Turbo
GPr-
0.00
0.00
0.04
0.08
0.55
0.51
0.87
0.01
0.27
0.26
0.29
GPT-3.3
GPT-4-Tir Tarbo
Gennin- Pro
0.00
0.00
0.37
0.00
0.00
0.04
0.35
0.33
0.33
0.56
0.56
0.67
0.19
0.23
0.45
0.09
0.09
0.07
Gemini-Pro
0.00
0.00
0.33
0.89
0.12
0.00
O1-Previow
0.00
0.22
0.00
0.99
0.22
0.05
O1-Presiew
0.22
0.00
0.99
0.96
4.3 Effect of In- In-Context Examples
This section explores the impact of introducing in-context examples on different models. The results, detailed Tabs. 2 and 3 showease that most models get significant improvement when provided with in- context examples. For example, initially, in the absence of in-context examples (ICE=0), DeepScek-MoE-7B is outperformed by Llamma-7B-chat across all six environments; but when presented with more in-context examples, DeepSeek-MoF-7 7B not only bridges the performance gap but actually surpasses Llama2-7B-chal in effectiveness.
However, the benefit of in-context examples is not universally observed across all models. For instance, the Llama2-13B-chal model exhibits decline in performance in the DFS environment when presented with seven
8

---

Published in Transactions on Machine Learning Research (06/2025)
Uamaa277bchat Llama2-138-chst
Uamma-7066ccat viunm-7BBw115-100
Wicune-13B-v1.5-16
Mixtral 1xx78--nttrrut-x0.1111
DeepSeek-
DeepSeekkWoE-160
DeepSeek-LLKe Lu4--eee--LU--70
GuessNum vs Coin
DFS vs CaveDFS
BFS vs CaveBFS
1.0
1.0
1.0
Effm
Gasin
Gein
0.0
0.0
0.0
Figure 3: Goal metrics from all 6 environments. Bars that are fully filled represent results from base envi- ronments (e.g., GuessNum, DFS, BFS) while bars filled with diagonal lines are from embodied environments (e.g., Coin, CaveDFS, CaveBFS), Models in the same family represented with the same hue, and larger models correspond to darker colors. Results from GPTs and Gemini-P Pro are not shown in this figure. It should be noted that these metrics are the lower the better.
Table 2:
The evaluation results (ICE=7) in 3 base environments. For models with strong goal metries (e.g.. Errmin, Gmin) indicting weak performance, goal metrics are more informative than ACC.
GuessNum
DFS
BFS
Model
Errmin
ACC f
Gmin +
ACC 1
Gmin +
ACC f
Small
10B
Llama2-7B-chat
0.08 (-0.18)
0.10 (+0.20)
0.39 (-0.19)
0.23 (-0.01)
0.65 (40.055
0.14 (40.14)
Mlama--B-IInstenn
0.02 (+0.01)
0.19 (+0.11)
0.04 (-0.17)
0.48 (-0.03)
0.37 (4-0355)
0.12 (-0.11)
Vicuna-7B
0.02 (-0.44)
0.22 (40.22)
0.37 (-0.28)
0.27 (+0.12)
0.68 (-0.16)
0.15 (+0.12)
Nisttral-IB-IIsstrnettv0222
0.01 (-0.05)
0.22 (40.22)
0.14 (-0.35)
0.51 (-0.10)
0.39 (400115)
0.17 (40.04)
DeepScek-LLM-7B
0.04 (-0.39)
0.18 (+0.118
0.16 (-0.18)
0.17 (-0.19)
0.61 (+0.09)
0.18 (+0.12)
16e
0.02 (-0.98)
0.21 (+0.211
0.14 (-0.49)
0.30 (+0.223)
0.86 (-0.02)
0.10 (+0.08)
10B Medium
50B
Llama2- 11-22-13-chat
0.06 (40.05)
0.13 (40.13)
0.50 (+0.16)
0.18 (-0.23)
0.37 (-0.08)
0.09 (+0.04)
Vicuna-13B
0.12 (-0.27)
0.12 (40.12)
0.16 (-0.50)
0.63 (+0.51)
0.23 (-0.58)
0.27 (+0.22)
Boctral-8x7B--Instueeewvo
0.00 (40.00)
0.25 (40.25)
0.20 (-0.27)
0.44 (-0.18)
0.48 (4-0.34)
0.21
(40.00)
Large
2 50B
Llama2-70B-cha
0.07 (-0.04)
0.13
(+0.13)
0.14
(-0.19)
0.46 (+0.02)
0.46 (4-0.18)
0.11 (+0.05)
Llama3-700 7-B--BBBBBnnt
0.01 (+0.00)
0.19
(+00119
0.00 (-0.10)
0.72 (+-0.04)
0.00 (-0.01)
0.37 (-0.16)
DeepSeek- DeepSeck-LLM-6778 LLM-67B
0.00 (-0.12)
0.25
(+0.25)
0.18 (-0.22)
0.33
(-0.09)
0.36 (-0.09)
0.18
(40.09)
Closed-source
GPT-3.5-Ture
0.00 (+0.00)
0.01
(+0.00)
0.36 (+0.01)
0.62 (+0.01))
0.12 (+0.01)
0.51
(-0.01)
GPT-1-Turbo
0.00 (40.00)
0.47
(+0.01)
0.02 (-0.01)
0.94 (+0.00)
0.00 (+0.00)
0.40 (40.02)
Gemini-Pro
0.00 (+0.00)
0.43
(+0.43)
0.02 (-0.23)
0.68 (-0.08)
0.03 (-0.03)
0.36 (+0.19)
in-context examples (ICE=7). To delve deeper into this phenomenon, we analyze the performance variation in relation to the number of in-context examples, depicted in Fig, 4 Two interesting observations are noted: 1) For GPT models, in-context learning barely had any impact
their performance, even though there is still room for improvement in embodied environments; and 2) An intriguing pattern emerged among the Llama2 models in the Coin enviromment, where their performance significantly dropped with just one in-context example (ICE=1), but showed gradual improvement as the number of examples increased. Similar trends were observed in recent open-source models, such as Mistral-7B BFS, DeepSeck-677 closed-souree Gemini-Pro in BFS. This contradicts the typical assumption that in-context learning universally enhances LLMs' performance. We hypothesize that this contradiction may stem from the interactive and
Coin and
9

---

Published in Transactions on Machine Learning Research (06/2025)
Table 3: The evaluation results (ICE=7) embodied environments. For models with strong goal metrics
(e.g., Errmins Gmin) indicting weak performance, goal metrics are more informative than policy metrics (e.g., Errsum Gaum: ACC).
Coin
CaveDFS
CaveBFS
Model
Erimin +
ACC
Gmin
ACC 1
Gmin +
ACC
Small
10B
Llama2-7B-hhn
0.11 (+0.04)
0.08 (+0.08)
0.38 (-0.12)
0.26 (-0.07)
0.58 (-0.18)
0.11 (40.06)
Llama3-8B-Iustruce
0.02 (-0.05)
0.19 (+0.19)
0.04 (-0.13)
0.49 (40.09)
0.42 (+0.33)
0.10 (-0.06)
Vicuna-7B
0.02 (-0.98)
0.22 (+0.22)
0.39 (-0.15)
0.25 (40.04)
0.68 (-0.04)
0.14 (40.07)
Mistral- Disstrl-7B-Iustruee TB-Instruut-v0.2
0,01 (-0.06)
0.22 (+0.22)
0.18 (-0.31)
0.45 (-0.03)
0.48 (+0:21)
0.15 (+0.04)
DeepSeek-LLM-77B
0.04 (-0.35)
0.17 (+0.17)
0.19 (-0.39)
0.33 (+0.17)
0.62 (-0.15)
0.17 (40.13)
DeepSeek-MoE-16h0
0.02 (-0.98)
0.21 (+0.21)
0.13 (-0.58)
0.34 (400228
0.87 (-0.02)
0.08 (40.07)
10B S Modium
50B
Llama2-13B-chat
0.05 (-0.14)
0.13 (40.18)
0.48 (40.10)
0.19 (-0.17)
0.56 (+0.01)
0.11 (+0.02)
Vicuna-13B
0.13 (-0.87)
0.12
(+0.12)
0.15 (-0.41)
0.59 (40.38)
0.27 (-0.37)
0.27 (+0.21)
Sinttral-S77B-Insttreee
0.00 (40000)
0.23
(40.25)
0.17 (-0.15)
0.43 (-0.02)
0.39 (+0.24)
0.21 (40.04)
Large 2 50B
Laama-70BB-hhe
0.09 (+0.09)
0.12
(+0.12)
0.20 (-0.15)
0.42 (-0.02)
0.60
(+0.30)
0.08 (40.05)
JJama3-70B-Instrun
0.01 (-0.02)
0.17
(+0.17)
0.00 (-0.03)
0.75 (-0.01)
0.01 (+0.00)
0.32 (+0.15)
DeepSeek-LLMMe L--666
0.00 (-0.36)
0.24
(40.24)
0.18 (-0.10)
0.37 (-0.20)
0.39 (40.01)
0.21 (40.18)
Closed- source
GPT-3.5-Thre
0.02 (+0.02)
0.00
(400000)
0.19 (-0.01)
0.66 (+0.00)
0.27 (+0.00)
0.10 (+0.00)
GPT-4-Turbo
0.00 (40.00)
0.50
(40.00)
0.23
(40.00)
0.76
(40.02)
0.11 (-0.01)
0.16 (40.00)
Gemini-Pro
0.00 (+0.00)
0.41
(+0.41)
0.04 (c0.18)
0.54 (-0.16)
0.05 (-0.05)
0.33 (+0.17)
[ama2-70a-chat 3-0 indrart
Vrune- 18
Werrat-nn Matri asThestnecve
GF:3 STuue
GemisiPrs
- Vouta-88
* 400-514
.e. GPT-47uube
GuessNum
Coin
0.4
0.2
0.0
CaveDFS
0 0.4
0.0
BFS
CaveBrs
0.6
0 0.3
0.0
Number of in-context examples (ICE)
Number of in-context examples (ICE)
Figure 4: Goal metrics from all 6 environments.
It should be noted that these metrics are the lower the better. Large models are more prune to performance drop when ICE is provided.
multi-round nature of examples in AQA- Bench, opposed to the single-round format typical in standard Q&A benchmarks.
This suggests that more studies about how multi-round examples for interactive lasks should be given to LLMs are required. It is also worth noting that with ICE=7, Gemini-Pro showed comparable or even better performance than GPT-4-Turbo in all environments except CaveDFS. Lastly, we investigate the influence of instructional differences between the base environments and their embodied variants, particularly with we observe notable trend: the number of
the increasing number of in-context examples. In Fig. 4
10

---

Published in Transactions on Machine Learning Research (06/2025)
in-context examples increases, the disparity in goal metrics between most models across these two types of environments tends to diminish. This suggests that the method of instruction and example provision can substantially reshape model behaviors.
Uama2278 7B shat Limma-13B-ccstt
Liamz 700 GP7-3.5 Subub
Table 4: PSACC in all 6 environments. All tests are run w/ seacher-guiding
Genini--rr
Guesshum
BFS
Model
GussNua
DFS f BPS
Coin
CavsDFS
CavdBF
Small
1000
0.25
0.27
0.30
Coln
CaveDFs
CaveBFs
Viems-IB
0.88
0.82
0.51
Mistral -i-l
0.00
0.37
0.72
0.00
0.75
0.78
DeggSebel LM--78
0.22
0.81
0.60
0.01
0.27
0.00
Decjeckk M00---MMO---- 18B
0.04
0.68
0.60
0.00
0.71
0.28
10B
Moliun
Lbmm2-130l-dht
Vieuns1333
0.38
0.82
1ith Step
Siicroo Eastruct-v))
0.79
0.45
0.85
0.51
Lange
Figure 5: Per-step ACC in all environments. Weak models are greatly improved even when a few optimal predecessor steps are provided.
0.58
0.26
Llund3- 700 Iestratt
0.72
DecpSeck LL3C-67B
0.31
Cloedd-ouroe
CPT-a.S-Turio CPT-4-Turb
0.85
0
0.92
0.67
0.89
0.77
0.93
0.58
0.58
0.95
0.89
0.76
Geiini-Pro
0.36
0.94
0.56
0.83
0.84
4.4 Failure of Scaling Law
Zero-shot setting. Fig. 3 provides comparisons among models from the same family. An interesting observation is, contrary to the expected improvement with increased model size tize-aa a trend typically observed in LLM benchmarks the performance in tasks like GuessNum, DFS, and their embodied variants does not consistently correlate with larger model sizes. Notably, certain models exhibit an inverse scaling effect. For instance, Dee-S surpasses its larger 65B counterpart in the DFS environment. Similarly, Llama-7B-chat outperforms the 13B one in the Coin environment.
Few-shot setting. The deviation from the scaling law becomes even more pronounced in the few-shot settings, as evidenced in Fig. 4 In these scenarios, medium and large models more frequently experience performance drops compared to smaller models. This phenomenon is probably caused during the overfitting process from in-context learning of medium and large models, which is also an overlooked area. This pattern also suggests that while larger models are often touted by developers for their superior performance across range of benchmarks, their effectiveness may not uniformly extend to specialized domains such algorithmic execution and interactive sequential reasoning. In these areas, the challenges are distinct from those encountered in conventional one-round Q&A formats, indicating need to reconsider the scaling assumptions in LLM for these applications.
4.5 Teacher Guiding
As evidenced in Fig. 5 even Llama2-7BBchat, which is small model, yielded higher PSACC as the number of steps grows, indicating the probability of executing the optimal policy improves over time, especially as correct decisions accumulate. In environments like DFS (CaveDFS) and BFS (CaveBFS), we noted that the differences in PSACC among various Llama2 models diminish when more guidance steps are provided by the teacher model. While larger models still tend to exhibit a higher average PSACC, as shown Tab. the gap narrows with increased teacher model intervention. However, it is important to note, as in Fig. PSACC may begin to decline in later stages of interaction. This decline can be attributed to the complexity of adhering to the optimal policy as the model is required to track and remember previous steps, such (implicitly) maintaining a queue of nodes in BFS and CaveBFS. These observations imply that the weak models' failure to perform well initially is one of the major reasons behind the performance gap between weak models and strong models. Therefore, even a limited series of correct steps at the beginning can significantly assist models in sequential reasoning tasks. Furthermore, for models possessing sufficient level of soquential reasoning ability, this process may lead to form of self-guidance, where the model reinforces its decisions based prior correct actions.
11

---

Published in Transactions on Machine Learning Research (06/2025)
5
Related Works
Large Language Models As the number of parameters and the scale of pretrained data increase, emerging behaviors become evident, allowing the model to perform tasks that are unachievable when complexity remains below a specified threshold (OpenAT, 2023). Additionally, it has been found that the utilization of meticulously crafted prompts (Fu et al., 2022; Zhou et al. 2022) can significantly improve the reasoning capabilities of LLMs. Open-source models [ouvron et al., 2023 Taori ct al.) 2023) have also emerged from community efforts and shown their effectiveness, with Vicuna (Chiang el al. 2023) and Mixtral (Jiang et al. Mlse-to-GPP-335 2024) demonstrating close-to- GPT-3.5 performance on human benchmarks. In our evaluation, we found
that despite the impressive chat abilities, there exists a gap in the algorithmic reasoning abilities between open-source models and close-sourced models.
Benchmarking Reasoning A bilities. Benchmarking LLMs' reasoning abilitics in performing complicated tasks have always been difficult. Most existing benchmarks in this area. mainly focus on well-formulated
objectives such as coding benchmarks like Codex (Chen et al.)
2021), Swe-bench (Jimenez et al. 2023
and TiveCodeBench (Jain et al.) 2024) and mathematical benchmarks like GSM8K (Cobbe et al. 2021
MMLU (Hendrycks et al.) (2000) MATH (Hendrycks et al.
2021 ,MMLU Wang et al. 2024h. These bench-
marks is based on one-round Q&A and lack the ability to access LLMs' sequential reasoning and planning capabilities. To address this, agentic benchmarks, e.g., website agent benchmarks such as WebArena (Zhou
ct al. 2023). ; Mind2Web (Deng et al. 2023), VisualWebArena (Koh et al. 2024), etc., have been devisod to assess LLMs within real-life scenarios that inherently necessitate foresight and retrospective analysis. How- ever, contrary to coding and mathematical problems, it is challenging for agentic benchmark to scale in size and to quantify the complexity of the environment, thereby impeding the systematic investigation of how these factors impact the performance of models. Furthermore, given the absence of known optimal strategies for these lasks, it proves difficult to guide LLMs and to examine how different prompting techniques (Wei) et al.) 2022 Zhou et al.) may affect the models' performance. Some works (Shi et al., 2023) investigate how these prompting techniques affect LLMs' reasoning ability but they didn't take planning and sequential reasoning ability into account and the resulted conclusions are sill superficial. Unlike previous works, our proposed AQA-Bench provides more comprehensive empirical evidence and results in deeper analysis.
6 Conclusion
In this study, we embark on an initial exploration into the realm of evaluating LLMs within interactive environments. These environments necessitate a deep understanding of specific algorithmic procedures by the LLMs, ranging from efficienlly guessing a number within minimal steps to strategically searching for unvisited nodes in a graph. Our comprehensive evaluation reveals a notable performance gap between current open-source and closed-sourced models, with the latter showing superior capabilities in these tasks. We expect future efforts to focus on introducing broader range of interactive environments and developing more effective prompting strategies to better equip LLMs for these benchmarks.
Acknowledgment
This work is partially supported by Open Philanthropy. We thank the Microsoft Accelerate Foundation Mod- els Rescarch Program, the OpenAT Researcher Access Program, Google Cloud Research Credits Program, Center for AI Safety, and Lambda Cloud for supporting our computing needs.
References
Xiao Bi, Deli Chen, Guanting Chen, Shanhuang Chen, Damai Dai, Chengqi Deng, Honghui Ding. Kai Dong, Qiushi Du, Zhe Fu, et al. Deepseek Ilm: Scaling open-source language models with longtermism. arXiv preprint arXiv:2401.00 029554, 2024.
Tom Brown, Benjamin Mann, Nick Ryder, Mclanic Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020.
12

---

Published in Transactions on Machine Learning Research (06/2025)
Mark Chen, Jerry Tworek, Heewoo Jun, Qiming Yuan, Henrique Ponde de Oliveira Pinto, Jared Kaplan, Harri Edwards, Yuri Burda, Nicholas Joseph, Greg Brockman, et al. Evaluating large language models trained on code. erXiv preprint ar arXio:2107.03377 2021.
Wei-Lin Chiang, Zhuohan Li, Zi Lin, Ying Sheng, Zhanghao Wu, Hao Zhang, Lianmin Zheng, Siyuan Zhuang, Yonghao Zhuang, Joseph E. Gonzalez, Ion Stoica, and Eric P. Xing. Vicuna: An open-source chatbot impressing gpt-4 with 90%* chatgpt quality, March 2023. URL. htttps///msys...e
0023-03-30-vicum
Karl Cobbe, Vineet Kosaraju, Mohammad Bavarian, Mark Chen, Heewoo Jun, Lukasz Kaiser, Matthias Plappert, Jerry Tworck, Jacob Hilton, Reiichir Nakano, et al. Training verifiers to solve math word problems. arXiv preprint arXiv:2110. 14168, 2021.
Damai Dai, Chengqi Deng, Chenggang Zhao, R. X. Xu, Huazuo Gao, Deli Chen, Jiashi Li, Wangding Zeng, Xingkai Yu, Y. Wu, Zhenda Xie, Y. K. Li, Panpan Huang, Fuli Luo, Chong Ruan, Zhifang Sui, and Wenfeng Liang, Deepseekmoe: Towards ultimate expert specialization in mixture-ofexxpers language models. CoRR, 24011.6666, 2024. URL https://arxii: wttg/b/////.....///.o
DeepSeek-AL Deepseek-rl. r1: Incentivizing reasoning capability in llms via reinforcement learning, 2025. URL https://arxiv argg/bb///00000 12948
Xiang Deng, Yu Gu, Boyuan Zheng, Shijie Chen, Samuel Stevens, Boshi Wang, Huan Sun, and Yu Su. Mind2web: Towards generalist agent for the web. arXiv preprint ar Xic:2306.06070 2023.
Yao Fu, Hao Peng, Ashish Sabharwal, Peter Clark, and Tushar Khot. Complexity-based prompting for multi-step reasoning. arXiv preprint orXiv:2210.0072 2022.
Dan Hendrycks, Collin Burns, Steven Basart, Andy Zou, Mantas Mazeika, Dawn Song, and Jacob Steinhardt. Measuring massive multitask language understanding. arXic preprint arXiv:2009.0300 2020.
Dan Hendryeks, Collin Burns, Saurav Kadavath, Akul Arora, Steven Basart, Eric Tang, Dawn Song, and Jacob Steinhardt. Measuring mathematical problem solving with the math dataset. arXiv preprint arXiv:2103.0m 03874, 2021.
Naman Jain, King Han, Alex Gu, Wen-Ding Li, Fanjia Yan, Tianjun Zhang, Sida Wang, Armando Solar- Tezama, Koushik Sen, and Ion Stoica. Tivecodebench: Holistic and contamination free evaluation of large language models for code. CoRR, 2024.
Albert Q Jiang, Alexandre Sablayrolles, Arthur Mensch, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Florian Bressand, Gianna Lengyel, Guillaune Lample, Lucile Saulnier, et al. Mistral 7b. arXiv preprint arXiv:2310.0660 06.22,,, 2023.
Albert Q Jiang, Alexandre Sablayrolles, Antoine Roux, Arthur Mensch, Blanche Savary, Chris Bamford, Devendra Singh Chaplot, Diego de las Casas, Emma Bou Hanna, Florian Bressand, et al. Mixtral of experts. Xixiv preprint ar Xix:2400004088, 2024.
Carlos E Jimenez, John Yang, Alexander Wellig, Shunyu Yao, Kexin Pei, Ofir Press, and Karthik Narasimhan. Swe-bench: Can language models resolve real-world github issues? arXiv preprint arXiv:2310006770 2023.
Jing Yu Koh, Robert Lo, Lawrence Jang, Vikram Duvvur, Ming Chong Lim, Po-Yu Huang, Graham Ncubig, Shuyan Zhou, Ruslan Salakhutdinov, and Daniel Fried. Visualwebarena: Evaluating multinodal agents on realistic visual web tasks. arXiv preprint arXiv:2401.1364 2024.
Wang Ling, Dani Yogatama, Chris Dyer, and Phil Blunsom. Program induction by rationale generation: Learning to solve and explain algebraic word problems. In Proceedings of the 55th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers). Association for Computational Linguistics, 2017.
13

---

Published in Transactions on Machine Learning Research (06/2025)
OpenAL. Gpt-4 technical report. arXiv, 2023.
OpenAl. Introducing openai http:////w/////////////////////t 2024.
Freda Shi, Xinyun Chen, Kanishka Misra, Nathan Scales, David Dohan, Ed H Chi, Nathanael Schärli, and Denny Zhou. Large language models can be easily distracted by irrelevant context. In International Conference on Machine Learning, pp. 31210 31227. PMLR, 2023.
Mirac Suzgun, Nathan Scales, Nathanael Schärli, Sebastian Gehrmann, Yi Tay, Hyung Won Chung, Aakanksha Chowdhery, Quoc V Le, Ed H Chi, Denny Zhou, et al. Challenging big-bench tasks and whether chain-offthought can solve them. arxiv preprinl or Xix:2222 Xii:2220.00961,, 2022.
Rohan Taori, Ishaan Gulrajani, Tianyi Zhang, Yann Dubois, Xuechen Li, Carlos Guestrin, Percy Liang, and Tatsuori B. Hashimoto. Stanford alpaca: An instruction-following llama model. https://githuu: /to.mt..tt.coomm tatsu-lab/stanfon alpaca 2023.
Gemini Team, Rohan Anil, Sebastian Borgeaud, Yonghui Wu, Jean-Baptiste Alayrac, Jiahui Yu, Radu Sori- cut, Johan Schalkwyk, Andrew M Dai, Anja Hauth, et al. Gemini: family of highly capable multimodal models. Xiv preprint arXiv:2312. 11805, 2023.
Meta LLaMA Team. Introducing meta llama 3: The most capable openly available 1lm to date. https 2024.
//ai meta. com com/bblog/mmettaaaaaa
Hugo Touvron, Thibaut Lavril, Gautier Izacard, Xavier Martinet, Marie-Anne Lachaux, Timothée Lacroix, Baptiste Rozière, Naman Goyal, Eric Hambro, Faisal Azhar, et al. Llama: Open and efficient foundation language models. orXiv preprint Xrv: 139711 2023.
Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoe Le, Ed Chi, and Denny Zhou. Self-consistency improves chain of thought reasoning in language models. arXiv preprint arXi::2203.111 111711 2022.
Yubo Wang, Xueguang Ma, Ge Zhang, Yuansheng Ni, Abhranil Chandra, Shiguang Guo, Weiming Ren, Aaran Arulraj, Xuan He, Ziyan Jiang, et al. Mmlu-pro: A more robust and challenging multi-task language understanding benchmark. In The Thirby-eight. Conference on Newral Information Processing Systems Datasets and Benchmarks Track, 2024.
Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, Fd Chi, Quoc Le, and Denny Zhou. Chain of thought prompting clicits reasoning in large language models. arXiv preprint 3rXiv:2201.11900 2022.
Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuurmans, Claire Cui, Olivier Bousquet, Quoc Le, et al. Least-to-most prompting enables complex reasoning in large language models. In The Fleventh International Conference Learning Represenlations.
Denny Zhou, Nathanael Schärli, Le Hou, Jason Wei, Nathan Scales, Xuezhi Wang, Dale Schuurmans, Olivier Bousquet, Quoc Le, and Ed Chi. Loast prompting enables complex reasoning in large language models. arXiv preprint 2rX:5 10625, 2022.
Shuyan Zhou, Frank F Xu, Hao Zhu, Xuhui Zhou, Robert Lo, Abishek Sridhar, Xianyi Cheng, Tianyue Ou, Yonatan Bisk, Daniel Fried, et al. Webarena: A realistic web environment for building autonomous agents. arXiv preprint arXiv:2307.1855, 2023.
14

---

Published in Transactions on Machine Learning Research (06/2025)
A Effect of CoT prompting
Although Chain-of-Thought prompting have been proven to be highly effective in the inteessvee lasks, such as coding and mathematical problems, we find that it can not consistently improve performance across all environments, as shown Tabs. and
Table 5:
The comparison between evaluation results without and with Chain-of- Shoin-of-Thought. For models with strong goal metrics (e.g., Errmins Gmin) indicting weak performance, goal metrics are more informative than policy metrics (e.g., ErTsums Gaum; ACC).
Base Envs under HARD Mode
BinarySearch
DFS
BFS
Model
Errmin & Errsum & ACC 1 Gmin J Gsum & ACC 1 Gmin J Gsum + ACC f
Llama3-70BB-nstruu Maama3-70B-Instruct w/ CoT
0.00
1.20
0.00
0.25
8.12
0.56
0.02
11.10
0.37
0.00
1.44
0.05
0.43
7.86
0.50
0.24
13.68
0.13
Chain-of-Thought. Table 6: The comparison between evaluation results without and with Chain-of- Thought. For
models with strong goal metries (e-g., Errmin, Gmin) indicting weak performance, goal metrics are more informative than policy metrics (e.g., Errgum, Gaum> ACC).
Embodied Envs under HARD Mode
Coin
CaveDFS
CaveBFS
Model
Erraii + Errsum ACC t Gaii Geum + ACC t Gmiu G + ACC f
Insttruuut
0.00
0.62
0.00
0.13
8.74
0.56
0.05
11.89
0.09
Llama3-700 70B-Instrume w/ CoT
0.00
0.61
0.03
0.28
7.53
0.56
0.14
13.51
0.08
15

---

Published in Transactions on Machine Learning Research (06/2025)
A.1 Re- Re-prod productivity and Variance
Although test cases in our AQA-Bench can be generated dynamically, pre-generated test set with 400 test cases for each base environment under the EASY mode for simpler re-production. The final scores are averaged among test cases.
B Variance of Test Sets
Given that GuessNum, DFS and BFS each can have at most 32768, 1.18 109, 9.17 * 10 test cases under the EASY mode, the quantity of our pre-generated test cases is somewhat modest. To verify that evaluation results with this number of test cases are valid and representative of the models' performance in each environment, we generated another 3 equally sized test sets and evaluated Llama2-7B-Chan and Vicuna-7B- v1.5-16K on all 4 Lest sets. To quantify the variance of results, we define that
{m,}
Avg KmiHl
(6)
Marginmin Avg min (mm))
(7)
Marginmax = max((m;)) Avg,
(8)
where min({m:)) is set of the same metric from different evaluation runs. Margin and Marginmas can be viewed as measurement for variance of evaluation results.
As shown in Tab. 7 Mangin and Marginmax are relatively low compared to metric difference across models, which shows that evaluation results drawn from our pre-generated test set (with only 400 cases) can sufficienly represent the tested models' performance Therefore, we only report results from the first test set rather than from all four test sets in the following context to save computation. For the HARD mode, we pro-generated 1500 test cases for cach environment of which the variance is shown in in Tab. indicating that under the HARD mode, the performance of the models do not show strong variance
environments with this level of complexity.
test sets with 1500 test cases for each environments.
Table 7: Inter-dataset variance of Llama2-7B-chat and Vicuma-BB-v15-16k under EASY mode. Results are summarized from evaluations on 4 independently generated test sets. All tests are run with ICE=0 and no leacher-guiding.
Base Environments
Embodied Environments
GueeeNuan
DPS
BPS
Coin
CaveDFS
CaweBS
Drian Eri.n
ACC
Gata
Gran
Gat Gsen J
Ertate Ettren ACC Gats 1 Gaan
Gats Gon
Liama2 7B chat
Llama2 7B chat
Avg
0.265
7.886
0.588
3.588
0.235
0.079
5,256
0.340
0.757
Manginaa
0.009
0.185
0.060
0.017
0.115
0.016
0.008
0.274
0.001
Margin....
0.005
0.238
0.000
0.008
0.080
0.011
0.001
0.208
0.002
Mangingux
0.006
0,168
0.000
(.020
0.138
0.010
0.007
0.209
0.001
Margit.ae
0.008
0.269
0.000
0.011
0.021
0.010
0.001
0.255
0.001
"'iunss7BBeell 5-16K
Aug
0.476
9.606
0.000
0.644
5.709
0.151
0.549
10.007
0.029
Avg
1.000
1.000
0,000
0.538
7.884
0.208
0.717
13.914
0.069
Man
0.017
0.366
0.000
0.000
0.196
0.007
0.010
0.600
0.001
Margin....
0.000
0.000
0.000
0.015
0.589
0.007
0.007
0.403
0.004
Margingux
0.016
0.341
0.181
0.012
Margiigaa
0,000
0.008
0.009
B.1 Variance of GPT models
Another factor that may affect our experimental conclusion the randomness of the model itself. For open-source models and Gemini-Pro, we disable the random sampling in all the experiments. But for GPT models, they only be accessed via OpenAl API, we cannot turn off such model randomness. Here we evaluated GPT models on the same datasct for 4 times to investigate the variance of the GPT models' performance measurement.
It is shown in Tab, 9 that Margin,in and Margin are a lot smaller than metric difference between GPT- 3.5-Turbo and Gur-4-Turb. This demonstrates that 400 test cases are sufficient to alleviate the impact of GPTs' randomness on the evaluation results. Thus, the experimental results of GPTs we report in the following context are only from single-time evaluation instead of summary of four different evaluations.
16

---

Published in Transactions on Machine Learning Research (06/2025)
Table 8: Inter-dataset variance of Llama2-7B-chat and Vicuma-7B-v1.5-166 under HARD mode. Results are summarized from evaluations on 4 independently generated test sets. tests are run with ICE=0 and no teacher-guie teacher-guiding.
Base Environments
Embodied Environments
GamseNaan
DFS
BFS
Coin
CaveDFS
CoveBPS
Fir..n
Br
ACC1
G...
C.a. ACC1 G...
G.on 4 ACC
Ert.in
Err.on
ACC
Gais 1 Guan
ACC G...
Cunn ACD
Lanndl-BB-hat
Llans2-71adat
Jong
0.498
14,956
0.000
0.735
7,360
0.193
0,761
15.949
0.035
Avg
0.079
5.256
0.000
0.488
4.633
0.360
0.157
5,405
0.046
Marginai
0.106
0.187
Morgiiaa
0,005
0.111
Mangin
0.011
0.332
0.000
0.007
0:397
0.007
0.006
0.300
0.002
Margie ...
0.008
0.260
0.000
0.021
0.010
0.001
0.255
0.001
Vicuna TB.
v1.3 16K
Vicuma 713
v1.5 10K
0.476
5.768
1.000
0.208
Man
0.008
0.012
0.000
0.002
0.205
0.002
0.002
0.302
0.000
Margin
0.000
0.000
0.000
0.015
0.389
0.007
0.007
0.003
0.004
Mazgin,....
0.086
0.022
0,000
1.000
0.119
0.001
0.003
0.479
0.001
Margie.....
0.000
0.000
0,000
0.013
0.361
01,06
0,009
0.473
12000
Table 9: Intra-dataset variance of GPT-3.5-Turie and GPT-4-Turbo under EASY mode. These results summarized from results from 4 different test the Lest set. All tests are run with ICE=0 and no teacher-guiding
Base Environments
Embodied Environments
Coin
CaveDFS
CaveBSS
Ertaa Bir.n ACC 1 G... J Gran ACC C... 1 G.a. J. ACC
Ettyin Ertyon ACC Gais & Caun ACC Gai
Com ACC'
GPT-B--Tubo
GPT-355 Turbo
Avg
0.000
0.513
0.003
0.348
5.142
0.618
6.116
6,773
0.517
Arg
0.001
1.013
0.000
0.199
4.769
0.669
0.272
0.505
0.100
Marginaat
Margitaga
0.001
0.917
..0000
0,055
0.010
0.007
0.106
0,002
Margituax
0.000
0.004
0.003
(L003
0.064
0.006
0.002
0.342
0.008
Margit.aas
0.001
0.005
0.010
0.005
GPT- Turboo
GPT - Turbo
Avg
0.000
0.496
0.483
0.025
3.935
0.935
0.002
6.087
0.383
0.000
0.705
Manginaat
0.000
0.000
0.033
01004
0.025
0.003
0.000
0.004
0.015
Margin
0.000
0.000
0.007
0.007
0.069
0.011
0.003
0.052
0.002
Margin
0.000
Mar
0.000
0.000
0.007
0.008
0.117
0.008
0.007
0.059
0.002
17

---

Published in Transactions on Machine Learning Research (06/2025)
C Full Evaluation Results with Policy Metrics
In this section, we present the full evaluation results with policy metrics.
C.1 Main Results (ICE=0)
Table 10:
The main evaluation results with all environments. For models with strong goal metries (e.g., Errmin, Gmin) indicting weak performance, goal metrics are more informative than policy metrics (e.g.;
Errsum, Grum; ACC).
Base Envs under EASY Mode
Embodied Envs under EASY Mode
GaraNun
CardDPS
Cas
ACCC
Scall IBB
Suail 10B
6:26
1.71
11.00
0.56
5.75
1.36
0,00
9:88
0,00
Hlund--B--di
5,82
0.00
01:00
6.85
0.83
0.70
5.66
BL0G
0.00
1:31
11:00
1.85
0.13
6:54
0:23
Lianod- Ieatract
5.70
01.00
11:17
5.52
0.30
6.92
0.16
0.34
0.00
0.84
0.05
Vicumn TB. 1.6-11
1.00
0.00
8.04
0.72
0.00
MBatcal-BB--ea Ti-latttett
3.00
0.00
2.73
0:34
0.13
Misrcl-7hh 78-taatact---00
3.20
0.00
6.80
0.57
0.11
DeeBSekk Mol.
1.00
4.7%
0.88
0.00
DeeyS MrF lol
1.00
0.50
0.01
10B 5 Mellon X G0B
10B: 5 Melican < 50B
6:01
3.31
0.00
5.06
0.65
10.30
0.05
Llanoch 1353 -ria
11
7.93
0.00
0.28
0133
0.55
19.23
0.00
Vioma-1 Hllee 5-1
0:30
8:31
0.06
13:21
0.83
0.03
Vierna -1
1.001
1.00
0.00
01.6
11:24
B1.66
0.60
0.00
9.50
0.14
0.21
Misteel-Rod Berteen--R--BBBaaa 61
0.00
0.72
0.00
0.22
4.01
0.15
0.17
Dieptieel-11
Quoveetats
3001
5011
6.31
2.64
[1.01
0.35
4.30
0.25
11414
C,05
Liunad TEEF-caat
0.00
0..51
0,00
11:30
4.53
11:48
11:31
10.53
6.00
1.41
(L:0)
0.30
4.37
0.01
0,08
0.53
Liuns TEE- lestree
2.00
0,00
4.381
0.76
0.01
0.51
0.17
DrepSteel 1
0.19
5.62
0.00
0.10
4.31
0.42
0.45
0.09
TreedSiol I 1-38-177
0.36
7.80
0.00
5.31
0.57
0.58
10:49
0.06
GPT--355 5- Thebo GPT-4-Tube
0.00
[1.1
11.01
5:21
0.13
0.52
G
0,00
1.01
0.00
3.87
0.99
11.7
1:09
11:00
0.00
0,60
0.66
0.06
3.65
D.54
0.00
6.05
0.35
GPT---Taris
0.00
0.50
0.50
0.23
3.02
0.74
0.12
8.07
0.16
Gomini--he tho
0.00
[4:5
11:01
0.25
3.71
1.76
0.15
7:38
6.17
Gendno-P7
0.00
0.91
0.10
11:22
5.11
0.71
0.30
T.57
1136
OC OcePherdow
0.00
0.50
11:35
0.00
3,86
1,00
0.00
6.07
0.30
C1-Prastery
0.00
0.75
0303
0.00
3380
3.00
0132
6.6
Base Envs under HARD Mode
Embodied Envs under HARD Mode
Xoold
Grm Erfeas Lifix. ACC 1 Guss Duas J. ADC Gun & Geas ACC
1255
BVS
Modei
Citn
Caveby'
Cavelars
Bi Io ACC
Gas
Gua
ACC Guas J G... ACC
3GB
-B-chat
0.46
14.77
11:81
0.74
7.24
1.39
0.25
16:35
CJ33
11:51
14.77
0,90
01:55
1..64
01:39
11.51
12.04
1LD6
Llonad an hastartratt
0:07
6.64
0.00
0.41
7.50
0.45
3.07
13.50
6.13
ZJannd SB, Inokrrct
0.07
10.01
0.00
0.29
10.90
0.29
0.59
15:22
0.00
Vioms--TB--t 5---66
6:24
14:36
11.0)
0.76
10.37
3.30
0.49
17.16
0,02
Vicans 15--1.5-0KK
11:21
14.77
0.80
11.00
15.50
0.33
[685
24.45
IL1G
Klateak- 1B- 12
0:06
5.45
1.00
0.66
4,31
0.61
0.45
10.20
0,05
Siiemb-7BB lastrazt-002
5,30
0.00
01.1
0.30
0.30
0.40
18:45
ILU7
Drepttoel- M-1
0:19
6.12
01000
0.61
16.07
0.18
0.21
0.01
Deeppiiee XI-77
01:0
1:38
0.00
0.71
16.05
0:11
01966
17:30
[10G)
DoppSek-MoE-168
1.00
0.00
0.78
5.96
0.02
0.01
Dxsp8sd-M00B-10
1.00
1.00
0.00
2.74
0.06
0.01
5 Mediots
S Molium
0:45
14.77
0.00
0.50
11.21
0:55
0.76
17.27
0.05
Zianed: chat
0.08
10.78
0.00
0.05
18,56
0.29
0.68
22.20
0.06
Viome. LBB-v. 1.10
6:45
14:77
0.00
9.50
20. 03
D:07
0.83
54.00
0.03
Vicans 133 5
1.00
1.00
0.00
0.65
11.75
0.17
0.71
23.33
0.06
Klistrak-ttaltb instruck--ttt
0.00
1.46
(L00)
0.64
6.00
0.:12
15:-2
6.15
2:23
0,00
11.00
8.21
11:24
14.30
15:45
(L10)
DrepSookk Twweell--goeeo Quaen 201
6.19
7.95
0.00
0.79
5.72
6.45
0.43
(3.00)
0.13
ThepSoois Tesill Queo-331
0.10
7:95
0.07
0.73
0.28
0.80
14:31
0.13
Large 308
Targo
Limmaa Bille
6:16
14:27
8.00
1615
9:01
1135
0:41
18:05
6.01
LJmmd Th0k-hhat
B108
12.72
0..00
10:99
19:35
10:33
15:31
11.00
1,20
11.01
0.25
8.32
11.16
0.12
0.37
Liamad- T1ts tnutreet
0,00
0.522
0.00
10.13
8.70
11:56
0.05
0.09
0.00
0.70
0.00
0,51
9.45
0.55
3.67
21.98
0.05
DecpSodd LLN567B
0.00
2.15
0.00
0.29
10.70
0.90
0.06
23.05
0.06
Cl-red- aortnco
QPI-4-Tubb
OPT-4-Tuabe
Goudal-Pr. Pro
0.51
0.00
0.19
6.09
Groini-Po
0.00
1.04
0.00
0.33
0.56
0.50
15.24
0.09
0.55
0.22
7.55
0.99
0.00
11.05
0.86
Oi-Precterr
0.00
0.67
0.22
0.00
7.85
0.99
01:00
0.00
C.2 Effect of In-Context Examples (ICE=7)
18

---

Published in Transactions on Machine Learning Research (06/2025)
Table 11: The evaluation results (ICE-7) in 3 base environments. For models with strong goal metries (e.g., Errmin, Gmin) indicting weak performance, goal metrics are more informative than policy metrics (e.g.. Errsum; Gaum; ACC).
Model
GueseNam
DFS
BFS
Frima
Frr 4
ACC 1
Gain 4
Cann l
ACC f
Guin 4
Cams
ACC
Small < 10B
-B-cat-BB-lust
0.08 (.0.15)
2:32 (:0.90)
0.10 (40.10)
0.39 (-0.19)
9.04 (+5.31)
0:23 (-0.01)
0.65
(+0.03)
8.25
(-1.02)
0.14 (+0.34)
Llann--98-Isstruc
0.02 (+0.01)
1.31 (40.27)
0.18
(40029)
0.04 (-0.17)
5.38 (40.72)
0:48 (-0.05)
0.37 (+0.33)
9.89 (+3.22)
0.12 (-0.11)
0.02 (-0.44)
1.27 (77.0)
0.22 (49.22)
0.37 (-0.5)
8.61 (42252)
0.27 (49012))
0.88 (4.11)
13.10
(422881)
0.15 (+0.12)
0.01 (-0.05)
(-0.95)
0.22 (40.22)
0:14 (c0,55
(43.002
(-0.10)
0.39 (+0.133
9.87
(+1.15)
0.17 (+0.04)
DorpSeck-L.MM--1
0.04 (-0.99)
1,50 (7.74
0.18 (40.35)
0.16 (-018)
6.93 (400.4)
0.17 (-0.19)
0.61 (40000)
11.43
(4-0.25)
0.18 (40.32)
DeepSocl-MoE-Jooe
0.02 (.0.66)
1.51
(40.55)
0.21
(40031)
0.14 (10-0)
6.75 (411.97)
0.30
(4-0.33)
(0.00)
2.60
(.5.58)
0.10
(40.05)
1013 S Medium
50B
Almma2-13B-chat
0.06 (+0.0))
1.89
(11255
0.13
(+0.13)
0.50 (+0.36)
(444.77)
(-0.00)
0.57 (10.08)
11.48
(+-0.90)
0.09
(+0.00
Vicune- 13B-v1 x1.-11KK
0.12 (-0.27)
5:42
(-2.99)
0.12 (40:32)
0.16 (-0.00)
5.24
0.63 (49.51)
0.23 (-0.58)
8.11 (-7.47)
0.27 (+0.32)
Mixten-8xx7B- 10----08t---
0.00 (40.00)
0.36
(.0.15)
0.25
(4-.25)
0:20 (.0.2)
(+9.34)
(-0.18)
(+-033))
11.34
(+0.88)
0.21
(+0.00)
Large 2 50B
Llama2-7033 70B-c
0.07 (-0.04)
1.96
(-0.04)
0.13
(40.33)
0.14 (-0.10)
(+1.44)
0.40
(4-0.02)
0.36
(+-0118)
(-0.08)
0.11 (+0.05)
LlouaS-708 70B-778B----ne Instrnc
0.01 (40.00)
0.70
(-0.71)
0.19
(49.19)
0.00 (-0.10)
1.30 (-0.07)
0.72
(400004
0.00 (-0.01)
6.37
(+0.39)
0.37 (-0.10)
DeepSeok-L
0.00 (-0.13)
0:38
(-0.04)
(4-0233
0:18 (-0.23)
6.79 (+2.45)
(-0.00)
(-0.00)
(-1.19)
0.18
(40.00)
Closed-oanve
CPT-3-- S-rboo
0.00 (-0.00)
0.52
(+0.01)
0.01 (+00000)
(+0.01)
5:30 (+90.0))
0.62
(+-0.01)
0.12
(+-0.03)
6:63
(-0.05)
(-0.01)
GPT-4-Turbo
0.00 (-0.00)
0.50
(40.00)
0.17 (40.03)
0.02
3.93 (490000
0.94 (+0.00)
0.00
(+0.00)
6.08
(-0.00)
0.40 (+0.02)
Gomini-Pro
0.00 (40.00)
0:51
(-0.13)
0.43 (4-0443
0.02 (-0.28)
4.57 (+-0.6)
0.68 (-0.05)
(-0.05)
(-0.80)
0.36 (4-0.19)
Table 12: The evaluation results (ICE-7) in 3 embodied environments. For models with strong goal metrics (e-g., Frrmin, Gmin) indicting weak performance, goal metrics are more informative than policy metries (e.g.. Errsum, Geums ACC).
Model
Coin
CaveDPS
CaveBFS
Erraii
Ery.n
ACC
Guia
Gean
ACC
G
Cama +
AOC
Small < 10B
Lamma277--chot
(en.as)
2.70
(2.a2)
0.08 (40.05)
(..19)
8:78 (14.14)
0:28
(.0.0))
0.58 (.0.18)
11:27
(60.0))
0.11
(60.00)
Llama3 SB Instruct
0.02 (o.os)
1:22
(-4.48)
0.19 (90.19)
0.04 (40.9)
5.37 (60.15)
0.19 (40.00)
0.12 (40.30)
10.12
(+1.00)
0.10 (-0.00)
Vieuna-BB-v1.5- 16K
0.02 (-0.9s)
1.13
(-0.13)
0:22 (40.22)
0.39
(-0.55)
8.88 (40,84)
0.25 (40.04)
0.68 (.0.04)
13:48
(-0.913
0.34 (-0.07)
Mistral-7BB- hittrrdd-tt
0.01 (c0.0))
1.15 (-2.44)
0.22 (40.22)
(-0.3))
6.28 (43.41)
0.45 (-0.00)
0.48 (40.23)
10:24
(40.36)
0.15 (-0.04)
DoepSecis-mm-T1
0.04 (o0a0)
1.53
(-7.00)
0.17 (40.17)
0.19 (.0.9)
6.50 (22.88)
0.33 (40.1)
0.62 (.0.15)
12.00
(611300
0.17 (60.55)
DeepSeekk moe- 18B
0.02 (-0.9)
(-0.61)
(40.23)
(-0.56)
6.71 (+3.72)
(40.20)
0.87 (-0.03)
2.71
(60.10)
0.08
(-0.07)
10B S Medium
50B
Llama2 chat
0.05 (o.14)
1,98 (-5.05)
(40.15)
0.48 (40.10)
10.50 (49.09)
0.19
(-0.17)
(40.01)
11.65 (-1.07)
0.11 (-0.02)
Vioma-138-v11 5-16
0.13 (ooam)
5.48
(-4.45)
0.12
(40.12)
0.15 (-0.41)
5.50 (-2.00)
0.59
(40.36)
0.27
8.54 (12.74)
0.27 (+0.23)
Misttra--c7T---nstrrett.
0.00 (40.00)
0.64
(-0.14)
(40.23)
(-0.15)
6.27 (+1.00)
0.43 (-0.00)
(40.24)
10:40 (+1.92)
0:21 (-0.04)
Large 2. 501
Llama2 70B-clue clut
0.09 (40.00)
(41.86)
(40.13)
(-0.5))
6.68 (42.13)
0:42
(-0.00)
(40.30)
8.39 (<2.12)
0.08 (40.05)
Llnma3-70tt-1 Instrec
0.01
0.73 (13/99)
0.17
(90.17)
0.00 (10/0))
4.23 (10.0)
0.75 (10m)))
0.01
(6/200)
6.41
(60-10)
0.32 (60.15)
DeepSteels lhm 67B
0.00 (40.0)
0.57
(17.00)
0.24
(40.94)
0.18
(40.00)
6.67 (44444)
0.37
(-0.20)
0.39
(49.01)
10.54
(-0.0))
0.21 (40.18)
Closed-souree
GPT--..G-Tut
0.02 (40.0)
1.02 (40.00
0.00
(40.00)
(1001)
4.83 (10.4)
0.66
(40.00)
0.27
(10.00)
9.56
(40.07)
0.30 (40.00)
GPT-4-Twrbo
0.00 (40.00)
0.50 (a.00)
0.50
(40.00)
0.23
(1000)
3.49 (10.10)
0.76 (4
0.11
(1001)
8.07 (10.0))
0.16 (-0.00)
Gemini- Pro
0.00 (40.00)
0.51
(-0.00)
0:41 (40.43)
0.04
(-0.88)
5.17 (40.00)
0.31 (-0.20)
0.05 (-0.05)
6.79 (41.18)
0.33 (40.77)
19

---

Published in Transactions on Machine Learning Research (06/2025)
D Prompt Instructions for the Models
In this section, we present the prompts we fed the models.
D.1 Base Environments
GuessNum
You are required to guess the random number which have just picked between {min} and {max]. I will only tell you whether the true number bigger or lower than your guess. Adjust your guess according my response. Try as few times as you can. You can only reply with an integer number between {min} and {max).
DFS
You required to visit all the nodes in undirected non-cyclic graph. An undirected non-cyclic graph contains set of nodes and set of edges that each connect pair of nodes. All edges are undirected so that you can move from one node to the other connected by the edge in either direction. Every time you visit node, you will be given the adjacont nodes connected to this node. You can only reply with an integer number indicating which node be visited next. Do not explain your answer. Try to traverse the entire graph as few rounds as possible. You are currently on the node You should use depta-first-search algorithm, each time you should select & node you have moved to. If all nodes adjacent to the current node have been visited, you should backtrack to the node through which you entered this node for the first time.
BFS
You are required to visit. all the nodes an undirected non-cyelic graph. An undirected non-cyclic graph contains a set of nodes, and set of edges that each connects a pair nodes. Every time you visit node, you will be given the adjacent nodes connected to this node. You can only visit nodes that adjacent to the already visited nodes. You can only reply with an integer number indicating which node to be visited next. Do not explain your answer. Try to traverse the entire graph in as few rounds possible. You currently the node 0. You should use breadth-first-eaan The algorithm works follows: 1. Initialize queue data structure and add the starting node to the queue. 2. While the queue is not empty, visit the first node and remove it from the queue. 3. For nodes adjacent to the removed vertex, add the unvisited ones to the queue. 4. Repeat steps 2-3 until the queue is empty.
algorithm.
D.2 Embodied Environments
Coin
You are in a hidden temple where an old witch sits with a chest of gold. The witch promises reward you with gold coins, the amount hidden within the chest ranging from {min] and (max). To claim your prize, you must correctly guess the exact number of gold coins in the chest. After each guess, the witch will hint if the actual amount is higher or lower than your guess. Use these clues to adjust your guess accordingly. Try as few times as you can. You can only reply with an integer number between {min) and (max).
20

---

Published in Transactions on Machine Learning Research (06/2025)
CaveDFS
There is expansive underground system in which each cave is uniquely numbered and intercon- nected by tunnels. Every time you visit cave, you will know the adjacent caves directly connected to this one. You can only reply with an integer number indicating which cave to be visited next. Do not explain your answer. Your objective is to explore every cave, starting from cave 0. Try to visit all the caves in as few rounds as possible. You are currently in the cave
CaveBFS
There is an expansive underground cave system in which each cave is uniquely numbered and inter- connected by tunnels. Every time you and your team visit a cave, will know the adjacent caves directly connected tno this one. Your team will then split into smaller groups to explore different caves, but groups can only move to caves adjacent to the visited cave. You can only reply with an integer number indicating which cave to visited next. Do not explain your answer. Your objective is to explore every cave, starting from cave O. Try visit all the caves few rounds as possible. You and your team currently in the cave 0.
E
Model Versions
We used the chockpoint "2023-11-06' for GPT-3.5 and GPT-4.0 and '2024-09-12' for O1-Preview. The open- source model and the corresponding commit ID on HuggingFace are listed as below
Jlama2-7B-chat [ibbbeo0000eellee000000000000000
Jlama2-13B-chat 3BBcchhaaa///e222222000000000003
Llama2-70B-chat Luce77hhrrrrs0000000440400000000
De w1
21


Reviews:
[{"review_id": "aMZNIGFgWN", "reviewer": "Reviewer_ZLgk", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper is mostly well written (a few sections could use some more polishing, but on the whole the presentation is very clear)\n- The setting is interesting; although somewhat contrived/synthetic, I think it offers a valuable perspective on a style of reasoning that O1/R1-style CoT RL would *not* immediately help with, since there is no way to know the correct answer without interacting repeatedly with the environment\n- The evaluations are thorough; the models considered span several licenses, size ranges and release dates\n- The authors do a good job of deriving a few downstream insights from their benchmark (eg the performance gap closing as the number of ICL examples increases)\n\nWeaknesses:\n- The biggest weakness to me is that your prompts discourage the mode from doing CoT. I do not understand why you did this; it artificially reduces the amount of computation the model can do (since some computations might require multiple forward\npasses), and it makes your framing of Wei et al. (2022) in 3.2 very strange, since you essentially state that it informed your experiment design and then go ahead to set up an experiment that does not leverage the core finding of the paper at all.\n- The (in my opinion close) relationship between this benchmark and agent benchmarks is somewhat swept under the rug, being only discussed briefly in the related work when it could have been a solid motivation for why your benchmark (which effectively distills some of the core algorithmic challenges that agents implicitly face in other agent benchmarks) should exist\n- There is a lot of bespoke metrics being defined, which makes it very hard to interpret the results, especially as there is already a lot of information to trawl through in the first place due.\n- There are a few minor typos here and there.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents a new benchmark, AQA-bench, which seeks to measure the ability of language models to reason about sequential tasks. The benchmark consists of three core algorithmic tasks: a \"20 questions\" style number guessing game with binary (higher/lower) feedback; a depth-first DAG exploration task; and a breadth-first variation of the same. The authors also construct a more naturalistic version of each task, which targets the same underlying mechanisms but in a \"gamified\" manner, to see whether this affects the models' ability to reason optimally. Using this benchmark, the authors evaluate a broad range of commercial and open models, finding that the commercial models tend to do significantly better. However, further experiments reveal that the differences are reduced with sufficient in-context examples. Finally, the authors argue that their results contradict common wisdom regarding how performance is expected to scale with model size, as they do not find that larger models always perform the best out of their model family.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Consider making the relationship to agentic benchmarks such as webarena, SWE-bench etc. clear in the introduction to the paper. I believe your contribution is different from theirs since you hone in on a few specific behaviors that models need to be able to replicate to consistently score well in these, and I think you could build a story off that instead of acting like your benchmark is the first to require an LLM to interact sequentially with an environment (which I hope we can agree it is not).\n- It would be good if you could simplify the exposition and distill the results into a smaller set of metrics. For example, for the graph exploration tasks your ACC metric seems to capture the notion of a policy metric (as defined by you as \"measur[ing] how fast the model's output converges to the final objective\") better than the G-sum metric (which I cannot think of a relevant interpretation of).\n- I assume it is too late to change your prompts to allow for CoT but I would at least like to see this rather strange design decision justified in the main text, and the relationship to Wei et al. (2022) clarified accordingly.\n- Your claim that the embodied environments are harder does not (based on Figure 3) look true to me; on average I would say they look to be about equal. Luckily there's a good way of finding out which one of us is wrong by running some form of hypothesis test on the null hypothesis that the mean accuracies of each setting are equal (eg compute a p-value and present it in the paper to justify this claim)\n- I believe you would be able to find prior work discussing the trend you have observed in your ICL study, ie that performance initially drops but then increases. Unfortunately I cannot find the reference, so I might simply be wrong, but if you can find prior work along the lines of \"icl first causes memorization and then generalization\" then that would strengthen your findings here.\n- I think claim (4) in the abstract is a little bit too strong in light of your experiments and the extended version of the claim given in the introduction. I recommend double checking that you feel confident that your experiments support this claim, and if so unifying that with the slightly weaker claim from the introduction.\n- I do not think you need the \"margin\" metrics in your experiments. If the point is to show that the variance (over the task generating distribution) is low, a simple range would have sufficed. This would also reduce the cognitive burden of having to parse yet another new metric, and might free up some space in your tables.\n- Typos and spelling mistakes:\n  - 2.2, GuessNum: \"guess\" should be \"guessing\"\n  - 2.2, DFS: \"decide\" should be \"deciding\"\n  - 3.1: second and fifth sentences of the first paragraph have inconsistent tenses / incorrect sentence structure\n  - 4: Incorrect citation format for GPT-4\n  - 4.2: \"but still not\" should be \"but are still not\"\n  - 5: first and second sentence are very difficult to parse", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "8NlMINZzUU", "reviewer": "Reviewer_TTaH", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\nThe benchmark is well scoped.\n\nThere are extensive experiments on a range of LLMs.\n\nExperimental findings are interesting.\n\nPaper writing is clear.\n\n**Weaknesses**\n\nI am not quite sure about the impact of this work. \n- Algorithmic games are interesting, but they are not representatives of real-life sequential decision making problems that we encounter in reality.\n- Algorithmic games can be hard, but it does not seem to be a good testbed for \"sequential reasoning\". Specially, for binary search, optimal actions are always to choose the new middle point; for DFS, it is optimal to always go deeper and then backtrack; for BFS, it is optimal to always traverse the graph layer by layer. It doesn't seem that one really needs to *plan* at all in these games: we don't need to think about what future information an action may reveal; we aren't allowed to undo or redo a previous action either. (Note: here my \"undo\" and \"redo\" are different from the backtracking in DFS.)\n\nI like the findings of the paper, but I am concerned that some findings are not as deep as it should reach.\n- When DFS/BFS algorithm description is given, the problem seems to become \"which LLMs can follow algorithmic instructions well\" (again, not \"sequential reasoning\" on-the-fly as the benchmark aims to test).\n- Since picking an optimal action requires some reasoning about visited nodes and trajectories, it seems natural to use chain-of-thought (CoT) reasoning methods to generate the action at each step, but the paper hasn't done experiments of this kind.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The key contribution of this paper is AQA-Bench, a new benchmark to evaluate LLMs' sequential reasoning abilities in algorithmic games. The benchmark is interactive: e.g., in DFS games, the LLM will see adjacent nodes once it reaches a node, and it has to remember visited nodes and plans the next move accordingly. The paper evaluates 14 LLMs, and show interesting findings: 1) close-source models are better than open-source models; 2) in-context examples hurt performance; 3) predecessor steps (following optimal policy) as few-shot examples work better than steps of other cases (following optimal policy); 4) weak models struggle to start well; 5) scaling up doesn't seem to help much in this setting.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Could you run experiments with CoT reasoning to generate actions at each step?\n\nParticularly, it will be very interesting to see how CoT reasoning affects your current conclusions (2) - (5).\n\nCan you also share your thoughts on including other algorithms into AQA-Bench? Something more contextual and may have a learnable heuristics to guide search and planning?", "broader_impact_concerns": "I have no concerns on the ethical implications of the work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "E9x8B44xbx", "reviewer": "Reviewer_yQcR", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n1. This paper provides a new data source for interactive sequential reasoning evaluation.\n\n2. The paper is well-structured and easy to follow.\n3. This work covers the evaluation of a wide range of closed- and open-source models, which provides comprehensive insights for future works.\n4. It’s interesting to see that scaling does not always bring better performance.\n\nWeaknesses:\n\n1. **Some arguments are a bit unclear or over-claimed**: On page 1, for instance, the authors claim that existing works ‘do not assess the models’ capacity for procedural adherence, active memory maintenance, and ability to think ahead, which are elements vital for more complex, sequential reasoning tasks’, while this is not entirely accurate. There are already existing works on code simulation, which evaluate LLMs’ algorithmic capability (e.g., [1]), and works that use LLMs as embodied agents to interact with the environment (e.g., [2]). These tasks require the abilities highlighted by the authors as well. Moreover, some insights provided in the paper are also widely observed in previous papers: e.g., ICL is well known to be brittle to the design of the in-context examples (e.g., [3]). Can the authors make more concrete claims about the novel contributions of this work?\n\n2. **Insufficient prompt design**: The prompt, in my opinion, is not well-designed: it is not even clear enough for humans to understand what to do. For instance, in the guess number task, the starting instruction is mere “You are required to guess a number between 0 and 8.” To specify the task, more information about the task objective and how the environment provides feedback should also be specified (e.g., ‘At each round, you will only give me a number of your guess. I will give you feedback about whether your guess is smaller/bigger than or equal to the target number. You should use as few rounds of guessing as possible.’)\n\n[1] Liu, Changshu, Shizhuo Dylan Zhang, and Reyhaneh Jabbarvand. \"Codemind: A framework to challenge large language models for code reasoning.\" arXiv preprint arXiv:2402.09664 (2024).\n\n[2] Song, Chan Hee, et al. \"Llm-planner: Few-shot grounded planning for embodied agents with large language models.\" Proceedings of the IEEE/CVF International Conference on Computer Vision. 2023.\n\n[3] Shi, Freda, et al. \"Large language models can be easily distracted by irrelevant context.\" International Conference on Machine Learning. PMLR, 2023.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work (i) provides a benchmark AQA-bench which enables the evaluation of LLMs’ sequential reasoning capabilities in interactive environments, (ii) it evaluates a wide set of LLMs and prompting strategies on this benchmark.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Provide more information about arguments specified in Weakness 1.\n\n2. Revise prompts to make them clearer.", "broader_impact_concerns": "I have no concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The primary contribution of this work in the provided benchmark itself. Reviewers seem to agree that the existence of this benchmark will be useful for people working on agents and reasoning in environments.

However, I do have a request:
Currently there is some discussion on the relation between this benchmark and other benchmarks related to agents and coding. I think the discussion on agent benchmarks should be in the introduction and should mention not only coding benchmarks (swebench, etc.) but also web agent benchmarks (WebArena, Mind2web, and more). The authors should explain in the beginning why do we need their benchmark. The claim that it allows for control and scale is fine but needs to be in the intro not differred to related work, this is a required change.

The second contribution is the evaluation of models on this benchmark. On this front, most of the models evaluated are what is often thought of as "old" nowadays. I was glad to see that the authors added llama-3-70b which is newer (came out april 2024). However, there is no discussion in the text about the results of llama-3-70b even though it does well. For example in 4.2 it is discussed that open models are much worse than closed models but this is not accurate in terms of this newer model added. The authors must change the text to reflect the results of the strongest open source model they present. This is a required change.

Moreover, since December 2024 there has been a lot of interest in reasoning models (o1, gemini-thinking, deepseek-r1, etc.).
This is a benchmark on reasoning so if the authors actually want people to appreciate the empirical work done it seems necessary to evaluate reasoning models at this point. Seems possible to do this for Deepseek-r1 distilled model, there are 8b/70b based on llama and other sizes based on qwen. I know this might not be seen as a "minor revision" but I view this as important for a benchmark that is focused on reasoning. It should be easy given that weights are open.

Last, I would recommend in general to evaluate newer models. Llama-2 is considered quite old. If authors want researchers to read the paper it would serve them to use modern models. Inevitably benchmarks saturate so evaluating with the right models can influence how much the benchmark will be used down the line. This is **not** required by me, only a thought the authors can consider.

A few more asks:
* please proofread citations and use \citet and \citep appropriately so that citations that are not part of the text are in parenthesis and citations that are part of the text are presented with only the year in parenthesis.
* "This contradicts common assertions in LLM development and points to an oversight of sequential reasoning capabilities and overfitting during in-context learning in current LLM research". The part after "overfitting..." is unclear in my opinion it would be good to clarify (not required but advised)








A few more minor requests:
Decision: Accept (poster)