ProcBench: Benchmark for Multi-Step Reasoning and Following Procedure

## Abstract

Abstract Reasoning is central to a wide range of intellectual activities, and while the capabilities of large language models (LLMs) continue to advance, their performance in reasoning tasks remains limited. The processes and mechanisms underlying reasoning are not yet fully understood, but key elements include path exploration, selection of relevant knowledge, and multi-step inference. Problems are solved through the synthesis of these components. In this paper, we propose a benchmark that focuses on a specific aspect of reasoning ability: the direct evaluation of multi-step inference. To this end, we design a special reasoning task where multi-step inference is specifically focused by largely eliminating path exploration and implicit knowledge utilization. Our dataset comprises pairs of explicit instructions and corresponding questions, where the procedures necessary for solving the questions are entirely detailed within the instructions. This setup allows models to solve problems solely by following the provided directives. By constructing problems that require varying numbers of steps to solve and evaluating responses at each step, we enable a thorough assessment of state-of-the-art LLMs’ ability to follow instructions. To ensure the robustness of our evaluation, we include multiple distinct tasks. Furthermore, by comparing accuracy across tasks, utilizing step-aware metrics, and applying separately defined measures of complexity, we conduct experiments that offer insights into the capabilities and limitations of LLMs in reasoning tasks. Our findings have significant implications for the development of LLMs and highlight areas for future research in advancing their reasoning abilities. Our dataset is available at https://huggingface.co/datasets/ifujisawa/procbench and code at https://github.com/ifujisawa/proc-bench .

## 1 Introduction

Reasoning is a fundamental component of intelligence, involving complex processes where the application of knowledge and logical inference are deeply intertwined (Wason & Johnson-Laird, ; Huang & Chang, ; Fagin et al., ). We define reasoning as the progression toward a specific goal through multiple steps of inference to derive new knowledge from existing information (Yu et al., ); it begins with goal setting, which can be self-initiated or explicitly provided, as is often the case in problem-solving; then, a series of inference is repeated until the goal is achieved, handling both explicit and implicit knowledge such as common sense or domain-specific information.

There are three classes of inference: induction, deduction and abduction (Peirce, ); induction is a process of generalization from a specific observation, while deduction is the opposite: from general to specific, and abduction is the inference to the best explanation from observations (Huang & Chang, ; Yu et al., ). All of them in common often require an exploration in a vast search space to determine the correct path to the goal, choosing necessary knowledge for the decisions from substantial knowledge.

Although reasoning involves such complex processes, here we focus on the process to follow a fixed path to a given goal with explicit knowledge, proposing ProcBench, which consists of tasks that do not require complex knowledge but can be solved by following the provided procedures. The goal of this dataset is to evaluate the ability of AI systems to follow and execute specific instructions, which we refer to as instruction followability. While trivial for humans, it can be challenging for AI systems that do not strictly adhere to the instructions. In choosing the tasks, we take into consideration that they have the following properties:

- •
The procedure to reach the goal is explicitly provided, so no search for the correct path is necessary.
- •
Minimal implicit knowledge beyond basic language comprehension is required to execute the procedure.
- •
The steps in the procedure are straightforward for humans to execute.

Numerous benchmarks (Saxton et al., ; Hendrycks et al., ; ; Yu et al., ; Cobbe et al., ; Dinh et al., ; Suzgun et al., ) have been proposed to evaluate reasoning in AI systems, ranging from basic arithmetic to advanced theorem proving and competitive programming challenges (Jain et al., ; Lu et al., ; Zhuo et al., ). While these benchmarks have evolved to tackle more complex tasks, they often require implicit knowledge, making it difficult to isolate and assess an AI’s procedural adherence. Furthermore, traditional AI evaluation methods have largely focused on final outputs, often at the expense of the reasoning process itself. This oversight can lead to systems that perform well in simple scenarios but fail when confronted with complex tasks that require careful, multi-step reasoning. ProcBench sets itself apart by emphasizing evaluative tasks that require minimal prerequisite knowledge and demanding exact adherence to instructions, whilst all necessary information is provided within the task description – thereby filling a critical gap in current evaluation methods.

Instruction followability is crucial across several key areas in AI, including reasoning (Yu et al., ), explainable AI (Arrieta et al., ), mitigating hallucinations (Bai et al., ), and AI alignment (Ji et al., ). Multi-step inference requires the models to follow instructions precisely to reach the correct conclusions. Models that adhere strictly to instructions provide clear intermediate reasoning steps, resulting in more transparent and interpretable outputs, which is essential for explainable AI. Strict procedural adherence reduces the risk of generating inaccurate or nonsensical information, thereby mitigating hallucinations by ensuring logical connections of distinct pieces of knowledge. Furthermore, ensuring that AI systems follow human instructions is fundamental to aligning their behavior with human intentions from the aspect of both safety and functionality.

Using ProcBench, we evaluated several state-of-the-art large language models (LLMs) to assess their instruction followability. Our evaluations of several state-of-the-art LLMs demonstrate a wide range of performance across tasks and complexity levels. Some models, such as o1-preview and o1-mini, performed consistently well on simpler tasks, accurately following multi-step instructions. However, as the complexity increased with longer sequences, even these models exhibited a significant drop in performance, highlighting their limitations in handling complex, multi-step reasoning. These findings emphasize the need for future improvements in procedural reasoning and offer a pathway for advancing LLMs in this area.

## 2 Related Work

### 2.1 Benchmarks for Large Language Models

Various benchmarks have been proposed to assess the capabilities of LLMs across diverse domains. Some benchmarks evaluate knowledge, reading comprehension, and general reasoning skills in fields such as science, medicine, and law (Hendrycks et al., ; Dua et al., ; Lai et al., ). Others focus on problem-solving and code generation capabilities (Suzgun et al., ; Chen et al., ). Mathematical reasoning is assessed through specific benchmarks (Saxton et al., ; Cobbe et al., ; Shi et al., ), while some are designed to evaluate LLMs’ performance in software operations, such as executing commands and web browsing (Xi et al., ; Liu et al., ; Ma et al., ). Instruction-following capabilities have also begun to receive attention through recent benchmarks (Zhou et al., ). Due to the rapid development of LLMs, such benchmarks that require implicit knowledge described above generally require frequent updates by adding more difficult tasks, or have short useful lifespans (Martínez-Plumed et al., ). Furthermore, because these benchmarks tend to focus on specific task-oriented skills that LLMs have been trained on, they are not fully adequate for assessing the models’ general intellectual capabilities, which is also pointed out in Chollet ().

In contrast to existing benchmarks, ProcBench focuses on assessing procedural reasoning, an essential component of complex problem-solving that remains underexplored. By isolating procedural follow-up from domain-specific knowledge, ProcBench reveals significant limitations in the ability of LLMs to strictly adhere to detailed, multi-step instructions. This makes the challenges of procedural reasoning explicit and provides a new perspective for evaluating and improving LLMs in domains that require precise, sequential operations.

### 2.2 Instruction Following

Instruction Following (Lou et al., ) has become an important research area, particularly in the context of LLMs (Zhou et al., ; Kim et al., ; Mishra et al., ). The primary goal in this field is to evaluate whether models can accurately interpret and execute given instructions. However, much of the existing research focuses on the final output, with less attention paid to the reasoning process that leads to that output.

Our research links Instruction Following to reasoning, positioning it as a specialized form of multi-step reasoning. We emphasize the importance of evaluating not only whether the final output follows the instructions but also the intermediate steps taken during the problem-solving process, distinguishing our work from previous studies.

Figure: (a) An example of input prompt

**Table 1: List of tasks.**
| Name | Type | Description |
| --- | --- | --- |
| Compare | str/list[str] | Compare a target string with a list and find the first exact match. |
| Compose | list[str] | Replace adjacent characters based on rules. |
| Copy | str | Concatenate strings based on a list of indices. |
| Count | list[str] / int | Count alphabets and numeric characters, then compute a product. |
| Count2 | list[int] | Count alphabets word by word, ignoring case. |
| Cumulate | int | Add or multiply numbers based on operations. |
| Decode | str | Decode a compressed string representation. |
| Decompose | str | Replace characters based on rules while replacement is possible. |
| DeleteChar | str | Remove characters step by step from a string. |
| DeleteWord | str | Remove words step by step from a sentence. |
| Encode | list[str] | Encode a binary string by grouping identical characters. |
| FillWord | str | Replace numbers in a sentence with words from a list. |
| FindCyclic | list[str] / str | Find a letter by moving a specified number of steps cyclically. |
| Gather | str | Extract and concatenate substrings based on index sets. |
| MoveCyclic | str | Move a character cyclically in an array. |
| PushPop | str | Add or remove characters using push/pop actions. |
| Rhythm | str | Pair and concatenate numbers and characters cyclically. |
| Rotate | str | Rotate a substring within a string step by step. |
| Search | list[int] | Count substring occurrences in a list of strings. |
| Sort | str | Sort a string alphabetically by swapping characters. |
| Split1 | list[str] | Split a string at specified positions. |
| Split2 | list[str] | Split substrings based on index pairs. |
| Substitute | str | Replace characters in a string based on a list of pairs. |

## 3 ProcBench

In this section, we introduce ProcBench, a benchmark dataset for testing LLMs’ instruction followability. The models are asked to solve simple but long step-by-step tasks by precisely following the provided instructions. Each step is a simple manipulation of either a string, a list of strings, or an integer number. There are 23 types of tasks in total, listed in Table 1. The tasks are designed to require only minimal implicit knowledge, such as a basic understanding of the English language and the ordering of alphabets. While the complexity increases with the number of steps, the tasks can essentially be solved by following the instructions without the need for specialized knowledge. While these tasks are easy for humans regardless of their lengths as long as we can execute each step, LLMs may fail as the number of steps becomes larger.

### 3.1 Structure

Each example is composed of the combination of a template and a question. Each task is associated with a fixed template, which contains the procedure for solving the question. A concrete example of this combination is shown in Figure 1(a), along with the corresponding intermediate states and final state as the ground truth in Figure 1(b). Additional templates can be found in Appendix A. The question represents the specific problem and is generated by the Generator. The Generator also produces the correct answer and the intermediate states leading to that answer simultaneously. Since the questions are generated by the Generator, it is easy to increase the number of examples in our dataset. However, for the convenience of evaluation, we provide a fixed dataset. We set the number of steps for each problem from 2 to 25, generating 10 examples per number. Therefore, each task consists of 240 examples, with a total of 5,520 examples. We further classify the step counts of 2 to 6 as Short, 7 to 16 as Medium, and 17 to 25 as Long, and aggregate metrics at these levels as well.

The models receive the combination of a template and a question and are required to provide not only the final state but also the intermediate states. Thus, the responses are more complex than simply providing words or choices. The elements contained in the intermediate and final states are of types int, str, and list. The list type contains int or str as its elements. The types of these elements differ by task, as listed in Table 1. The model’s predictions must be converted into a JSON format that adheres to these types to facilitate evaluation through the metric functions.

### 3.2 Metrics

We introduce Prefix Accuracy (PA) as a metric for evaluating sequence-based tasks, with a primary focus on assessing how accurately a system adheres to a specific procedure to solve a question. These tasks often involve multi-step procedures or free-form answer generation, where even small deviations from the correct steps can lead to significant mismatches. The sequences in question represent complex state transitions, making precise adherence to the intended procedure critical for successful problem-solving.

Let $T=(t_{0},t_{1},t_{2},\dots,t_{N})$ represent the target sequence of length $N+1$, where $t_{0}$ corresponds to the initial state provided in the question and is not required to be predicted. The parameter $N$ denotes the number of steps necessary to solve the problem, which we refer to as the Problem Length. Similarly, let $P=(p_{1},p_{2},\dots,p_{M})$ denote the predicted sequence of length $M$.

We define the Prefix Match Length (PML) as the length of the longest contiguous prefix where the elements of the predicted sequence match those of the target sequence exactly. Formally, let $k$ be the largest index such that $t_{i}=p_{i}$ for all $1\leq i\leq k$. Then,

$$ $\text{PML}(T,P)=\max\left\{k\mid t_{i}=p_{i}\text{ for all }1\leq i\leq k \right\}.$ $$

Here, the comparison of sequence elements $t_{i}=p_{j}$ denotes an exact match regardless of type. Specifically, for each of int, str, and list, it represents complete equality as integers, characters, or lists, respectively. In the case of lists, a match is considered to be 1 only if all corresponding elements in the lists are identical.

Using the PML, we define Prefix Accuracy (PA) as the ratio of the longest matching prefix to the length of the longer sequence between the target and predicted sequences. This normalization ensures that the metric is bounded between 0 and 1, where 1 indicates a perfect match. Formally,

$$ $\text{PA}(T,P)=\frac{\text{PML}(T,P)}{\max(N,M)}.$ $$

PA penalizes both over- and under-prediction by considering the length of the longer sequence, thereby reducing the score for deviations in either direction.

In addition, we introduce Sequential Match (SM) as a binary indicator of whether the predicted sequence perfectly matches the target sequence from the first element to the last. SM is defined as:

$$ $\text{SM}(T,P)=\begin{cases}1&\text{if }\text{PA}(T,P)=1,\\ 0&\text{otherwise}.\end{cases}$ $$

SM captures cases where the predicted sequence adheres fully to the target sequence across all steps, making it a stringent indicator of complete procedural correctness.

Finally, we introduce Final Match (FM) as a binary indicator of whether the final elements of the two sequences match. This metric captures whether the final state, or solution, predicted by the model aligns with the target outcome, regardless of intermediate discrepancies. Formally,

$$ $\text{FM}(T,P)=\begin{cases}1&\text{if }t_{N}=p_{M},\\ 0&\text{otherwise}.\end{cases}$ $$

FM complements PA by ensuring that final solutions are evaluated independently of intermediate state matches.

## 4 Experiment

### 4.1 Experimental Setup

We evaluate the performance of seven state-of-the-art models using our benchmark, which covers a variety of task types and complexities. The models selected for evaluation include Claude-3.5-sonnet (Anthropic, ), Mistral-large (Jiang et al., ), Gemini-1.5-Pro (Google, ), GPT-4o, GPT-4o-mini (OpenAI, ), o1-mini, and o1-preview (OpenAI, ).

The tasks presented to the models require generating sequences rather than simple question-and-answer pairs. Given that the output of LLMs is generally provided in free-form text, we convert the responses into a structured JSON format (OpenAI, ) to facilitate evaluation. This transformation process, performed by GPT-4o, is uniformly applied to all models, and the evaluation metrics defined in Section 3.2 are computed based on this standardized format. It is important to note that the results reflect not only the models’ raw accuracy but also the impact of the conversion process on the final evaluation scores.

**Table 2: Model Performance Across Different Difficulty Levels. Prefix Accuracy (PA) measures the ratio of the longest matching prefix between the predicted and target sequences, normalized by the length of the longer sequence.Sequential Match (SM) is a binary metric indicating whether the predicted sequence exactly matches the target sequence from start to finish. The full definitions of the metrics can be found in Section 3.2.**
| Model | Short | Medium | Long | Overall |  |  |  |  |
| --- | --- | --- | --- | --- | --- | --- | --- | --- |
|  | PA | SM | PA | SM | PA | SM | PA | SM |
| Claude-3.5-Sonnet | 0.589 | 0.455 | 0.382 | 0.221 | 0.255 | 0.115 | 0.378 | 0.230 |
| Mistral-Large | 0.495 | 0.366 | 0.384 | 0.239 | 0.265 | 0.142 | 0.362 | 0.229 |
| Gemini-1.5-Pro | 0.329 | 0.167 | 0.230 | 0.117 | 0.159 | 0.071 | 0.224 | 0.110 |
| GPT-4o | 0.631 | 0.396 | 0.437 | 0.285 | 0.344 | 0.204 | 0.443 | 0.278 |
| GPT-4o-mini | 0.408 | 0.201 | 0.220 | 0.089 | 0.143 | 0.039 | 0.230 | 0.093 |
| o1-mini | 0.801 | 0.722 | 0.681 | 0.484 | 0.508 | 0.214 | 0.641 | 0.432 |
| o1-preview | 0.799 | 0.656 | 0.736 | 0.563 | 0.599 | 0.333 | 0.698 | 0.496 |

Figure: (a) Sequential Match
Refer to caption: extracted/5900509/fig_table/fig_legend.png

Figure: Figure 3: Proportion of PA across problem lengths for o1-preview.
Refer to caption: extracted/5900509/fig_table/fig_model_step_PAbin_o1-preview.png

Figure: Figure 5: Prefix Match Length (PML) for different problem lengths across all models and three tasks; FindCyclic, Compare and Sort. Each bar in the graph represents the average PML for a given problem length, with separate graphs for each model-task pair.
Refer to caption: extracted/5900509/fig_table/fig_model_task_PML_selected.png

Figure: Figure 6: Model performance across all 23 tasks. The metrics shown are Prefix Accuracy. Tasks are ordered by the median PA.
Refer to caption: extracted/5900509/fig_table/fig_task_model_PA_xtick.png

### 4.2 Results

Model Performance in Summary.
Table 2 provides a comprehensive comparison of model performances across varying task difficulty levels—Short, Medium, and Long—evaluated through the metrics of PA (Prefix Accuracy) and SM (Sequential Match). The o1-preview model consistently leads across most categories, particularly excelling in the Medium and Long tasks, where it achieves the highest scores for both PA and SM. In contrast, o1-mini demonstrates a competitive edge in simpler tasks, outperforming o1-preview in the Short task with a PA of 0.801 and SM of 0.722.

Performance Across Problem Length and Stepwise Predictions.
To further analyze how model performance is affected by problem length $N$, Figure 2 displays the results across four key metrics: SM, PA, FM, and PML. These metrics provide a detailed view of the models’ effectiveness in solving sequence-based tasks as $N$ increases.

By definition, SM is the most strict of the metrics. Indeed, as shown in Figure 2(a), SM exhibits the most pronounced decline as the Problem Length increases. While PA shows a similar trend to SM, its decline is more gradual (Figure 2(b)). Additionally, PA follows a pattern similar to PML (Figure 2(d)), but its normalization allows for model comparisons independent of problem length. FM was originally defined based on the inherent difficulty of our proposed tasks and the common assumption that only the final answer needs to be correct. However, as observed in the averaged visualizations in Figure 2(c), this metric behaves almost identically to SM and PA in practice. Figure 2(d) focuses on the PML metric, which reveals that the average PML increases with problem length but plateaus after a certain point. This suggests that models have inherent limitations in the number of inference steps they can reliably manage.

Figure 4 illustrates the distribution of PA across different problem length bins for o1-preview, the model with the highest overall performance. The visualization reveals that the proportion of errors at the initial step remains nearly constant, regardless of problem length $N$. While the model demonstrates high accuracy for shorter questions, its performance gradually declines as $N$ increases, with longer questions resulting in lower PA. A similar pattern can be observed in other models, as shown in Figure 10 in the Appendix.

Figure 4 visualizes the proportion of correct predictions made by each model at or above a given step threshold. Each point represents the proportion of questions for which the model successfully predicted beyond a particular step threshold $N$. Similar to an ROC curve, models with curves that remain higher and shift to the right demonstrate stronger performance on tasks with longer sequences. o1-preview and o1-mini exhibit superior performance, with their curves declining more gradually, indicating their ability to handle longer step sequences effectively. In contrast, other models experience a sharp drop in accuracy around the 5-step mark, reflecting their limited capacity to maintain correct predictions over extended sequences.

Task-Specific Model Performance
To further assess model accuracy on specific tasks, Figure 5 illustrates PMLs across tasks such as FindCyclic, Compare, and Sort. The results show that some models retain high accuracy throughout all problem lengths in FindCyclic, while they show significant accuracy declines as the number of steps increases in Compare. Additionally, certain tasks like Sort consistently exhibit smaller PML values across steps, indicating their difficulties. All graphs can be found in Figure 11 and 12 in Appendix.

Lastly, Figure 6 presents the accuracy variation across the seven models for each of the 23 tasks in the dataset. Notably, tasks such as FillWord and Sort have been identified as particularly challenging for many models, with certain questions in these tasks frequently resulting in lower PA. If a substantial portion of questions within a task consistently result in PA = 0, this could indicate not merely high difficulty but also potential flaws in task design, such as internal contradictions or settings that render the problem unsolvable. Nevertheless, only 91 out of the 5,520 examples across the entire dataset exhibit a PA of 0 across all models, suggesting that the dataset is well-calibrated and that such issues of unsolvability or internal contradictions are minimal.

## 5 Discussion

Relationship Between Instruction Following and Reasoning.
The relationship between Instruction following and reasoning is a fascinating one. For humans, the most challenging aspects of reasoning often involve the application of knowledge, particularly implicit knowledge. In contrast, simply following instructions is generally not considered reasoning. However, we propose that Instruction following can be understood as a specialized form of reasoning, particularly when it is disentangled from implicit knowledge and focuses on scenarios where the path to the goal is explicitly defined. Although this may not initially seem like reasoning, once one successfully navigates the search for the correct procedure and applies the relevant knowledge, it becomes closely aligned with the types of problems we seek to address. In this sense, our approach deconstructs the reasoning process. While the ultimate reasoning systems may not explicitly separate these functions, they should still be capable of solving the kinds of problems we address.

We developed a dataset to explore this connection, and our results show that models recognized for their strong reasoning capabilities, such as o1-preview and o1-mini, performed well. This suggests a qualitative link between reasoning ability and the capacity to follow instructions. However, the experiments also revealed that even tasks that may seem straightforward or merely tedious to humans—tasks that appear self-evident—are not consistently solved by the models. On the other hand, these models demonstrate strong reasoning capabilities in domains like law or physics (OpenAI, ; Google, ). Since the effective application of knowledge can reduce the number of computational steps, it suggests that state-of-the-art LLMs may be more adept at leveraging knowledge to solve complex problems rather than excelling at multi-step procedural reasoning itself. This underscores a fundamental challenge in the current deep learning paradigm, where many models struggle with intricate reasoning tasks unless they can heavily rely on prior knowledge.

Minimal Implicit Knowledge.
While the ideal goal is to eliminate all implicit knowledge requirements, some minimal assumptions are inevitable. For example, we assume a basic understanding of the English language, the order of the alphabet, and that numbers such as 0, 1, 2, and so on represent numerical values. However, these assumptions are deliberately kept minimal and are significantly less specialized compared to the knowledge required for tasks in fields like physics, chemistry, law, or mathematics. By focusing on such foundational concepts, the dataset preserves a structured challenge that emphasizes reasoning and procedural execution rather than relying on domain-specific knowledge.

Expected Use Cases and Limitations.
The simplest and most straightforward use of our dataset is for evaluating LLMs, particularly with respect to their reasoning capabilities. This is the primary intended application, allowing researchers to assess how well a new model handles multi-step reasoning tasks.

Additionally, ProcBench can be used to evaluate variations of methods such as In-Context Learning or Chain-of-Thought reasoning (Wei et al., ). However, we do not envision the use of task-specific prompts for each of the 23 distinct tasks in the dataset, as this would introduce domain-specific knowledge. Such prompts might enable the model to skip significant portions of the actual reasoning process, which would defeat the purpose of evaluating its raw reasoning capabilities. An extreme example of this would be programming-based solutions, where directly introducing task-specific solvers should be avoided. If a general-purpose model, such as one with coding capabilities, can solve tasks without specific tuning, this reflects its versatility. However, in such cases, the intended measurement of multi-step Instruction followability would no longer be feasible within this dataset.

Although the primary focus is on the current LLM paradigm, ProcBench is still applicable to traditional machine learning models, such as those used in inductive programming, which learn from concrete examples. However, the fixed dataset provided for evaluation is unlikely to be sufficient for training such models. In this case, the Generator could be utilized to augment the dataset, enabling a model to be constructed from scratch with the goal of following procedural instructions.

## 6 Conclusion

We introduced ProcBench, a benchmark designed to assess LLMs on their ability to follow explicit, multi-step instructions. By concentrating on tasks that require minimal implicit knowledge, ProcBench allows us to evaluate the procedural reasoning capabilities of models independent of their reliance on domain-specific knowledge. Our results show that while state-of-the-art models like o1-preview and o1-mini perform well on tasks involving shorter steps, they face significant difficulties as the step length increases. This highlights a critical limitation in current LLMs: despite excelling in knowledge-driven tasks, they struggle to consistently follow detailed procedural instructions when faced with more complex, multi-step reasoning.

Our findings emphasize the distinction between knowledge-based reasoning and instruction following, an area where LLMs have yet to achieve consistent mastery. Enhancing the ability of these models to precisely follow instructions will be key to improving their performance in more complex problem-solving scenarios. Future work will expand ProcBench to encompass a broader range of tasks and further investigate how explicit instruction-following capabilities can be more effectively integrated into models trained on traditional benchmarks. This will contribute to developing systems that can reliably handle multi-step reasoning across diverse domains.

## Reproducibility

Details regarding the construction of the benchmark and the models used in the experiments can be found in Section 3, Section 4.1 and Table 3. The dataset we created, the code used to generate it, the prediction results, and the evaluation results will be made publicly available after the paper is accepted for publication.

## Acknowlegedment

We thank Yuya Fujisaki and Toma Tanaka for helpful discussion.
This work was supported by the JST, Moonshot R&D Grant Number JPMJMS2012.

## Appendix A Dataset Examples

### A.1 Example Templates

Here, we provide detailed examples of 3 out of the 23 templates used in our experiments. The remaining templates can be found in the dataset that has been made publicly available. Please refer to the dataset for the full set of templates.

Figure: Figure 7: Templates for the tasks of Sort, Rotate, and MoveCyclic.

### A.2 Example Prompts

Figure: Figure 8: Prompts from the tasks of Substitute, Rhythm and Encode.

## Appendix B Baseline Models

**Table 3: Information of baseline models**
| Name | Version | URL |
| --- | --- | --- |
| GPT-4o | gpt-4o-2024-08-06 | [https://cdn.openai.com/gpt-4o-system-card.pdf](https://cdn.openai.com/gpt-4o-system-card.pdf) |
| GPT-4o-mini | gpt-4o-mini-2024-07-18 | [https://cdn.openai.com/gpt-4o-system-card.pdf](https://cdn.openai.com/gpt-4o-system-card.pdf) |
| o1-preview | o1-preview-2024-09-12 | [https://cdn.openai.com/o1-system-card-20240917.pdf](https://cdn.openai.com/o1-system-card-20240917.pdf) |
| o1-mini | o1-mini-2024-09-12 | [https://cdn.openai.com/o1-system-card-20240917.pdf](https://cdn.openai.com/o1-system-card-20240917.pdf) |
| Gemini-1.5-Pro | gemini-1.5-pro-latest | [https://deepmind.google/technologies/gemini/pro/](https://deepmind.google/technologies/gemini/pro/) |
| Claude-3.5-sonnet | claude-3-5-sonnet-20240620 | [https://ai.meta.com/blog/llama-3-2-connect-2024-vision-edge-mobile-devices/](https://ai.meta.com/blog/llama-3-2-connect-2024-vision-edge-mobile-devices/) |
| Mistral-large | mistral-large-2407 | [https://mistral.ai/news/mistral-large-2407/](https://mistral.ai/news/mistral-large-2407/) |

## Appendix C Additional Results

Figure: Figure 9: Model performance across all 23 tasks. The metrics shown are Sequential Match (SM) (top), Prefix Accuracy (PA) (middle), and Final Match (FM) (bottom). Tasks are ordered by the median SM score.
Refer to caption: extracted/5900509/fig_table/fig_task_model_SM.png

Figure: Figure 10: Proportion of PA across problem lengths for all models.
Refer to caption: extracted/5900509/concat_fig/appendix_pabin.png

Figure: Figure 11: Prefix Match Length (PML) for different problem lengths across all models and tasks. Each bar in the graph represents the average PML for a given problem length, with separate graphs for each model-task pair. FindCyclic, Cumulate, Rhythm, Gather, PushPop, Decode, Substitute, Split1, Split2, Copy, DeleteChar and Rotate are shown.
Refer to caption: extracted/5900509/fig_table/fig_model_task_PML_part1.png

Figure: Figure 12: Prefix Match Length (PML) for different problem lengths across all models and tasks. Each bar in the graph represents the average PML for a given problem length, with separate graphs for each model-task pair. Count2, Compare, Count, DeleteWord, Search, Decompose, MoveCyclic, FillWord, Compose, Encode and Sort are shown.
Refer to caption: extracted/5900509/fig_table/fig_model_task_PML_part2.png

Figure: Figure 13: Problem Length vs Prediction Length. Gemini-1.5-Pro and Mistral-Large tend to give long predictions.
Refer to caption: extracted/5900509/concat_fig/appendix_predlen.png

## Peer Reviews

confidence: 3
contribution: 3
initial_rating: 6
presentation: 3
questions: Exploration of Prompting Strategies and Model Fine-Tuning: Have you considered evaluating the impact of different prompting techniques, chain-of-thought reasoning, or fine-tuning strategies on model performance in ProcBench tasks?

Failure cases: Could you dig deeper into what are the failure cases of the models and what proportion of them are non-reasoning related (tokenization and formatting issues)?
soundness: 3
strengths: Novel Focus on Procedural Reasoning: The paper addresses a critical but underexplored aspect of LLM evaluation by isolating the ability to follow explicit, multi-step instructions without relying on implicit knowledge. This focus fills an important gap in existing benchmarks.

Comprehensive and Carefully Designed Controllable Benchmark: ProcBench includes 23 distinct tasks that cover a range of procedural challenges across different domains, involving string manipulation, list operations, and arithmetic computations. The tasks vary in length and complexity, providing a thorough and controllable assessment of models' capabilities.

Evaluation Metrics like Prefix Accuracy (PA) and Sequential Match (SM) capte not only the correctness of the final outcome but also adherence to each intermediate step.

Insightful Analysis: The study reveals significant performance drops in models as task complexity increases highlighting limitations of current LLMs and areas for future improvement.

Open-Source Dataset and Code Availability: Making ProcBench and the evaluation code publicly available promotes transparency, reproducibility, and encourages further research in this area.
summary: The paper introduces ProcBench, a novel benchmark designed to evaluate the ability of large language models (LLMs) to accurately follow explicit, multi step instructions, a capability referred to as instruction followability. Unlike existing benchmarks that often require implicit knowledge or complex domain specific reasoning, ProcBench focuses on tasks where all necessary procedures and information are explicitly provided. This approach minimizes the reliance on implicit understanding and isolates the models' proficiency in procedural adherence.

ProcBench comprises 23 diverse tasks (e.g., DeleteChar, FillWord, Sort) that vary in complexity from short to long steps, emphasizing step-by-step correctness. The authors evaluate several state-of-the-art LLMs, including GPT-4 variants, Claude-3.5-Sonnet, Mistral-large, and Gemini-1.5-Pro, using newly introduced evaluation metrics: Prefix Accuracy (PA), Sequential Match (SM), and Final Match (FM). These metrics assess both intermediate and final outputs of multi-step sequences. The results reveal that while some models perform well on simpler tasks, their performance degrades significantly as task complexity and as the number of steps increase, highlighting current limitations in handling complex, multi-step procedural reasoning.
weaknesses: Limited Real-World Applicability: While effective for isolating procedural reasoning, the tasks may not fully capture the complexities and nuances of real-world scenarios where implicit knowledge and domain-specific understanding are often required.

Focus on Specific Task Types: The benchmark predominantly includes tasks involving string manipulation, list operations, and basic arithmetic. This may limit the assessment of models' abilities in other types of procedures, such as complex logical reasoning, spatial reasoning, or tasks requiring hierarchical planning.

Insufficient Exploration of Prompting Strategies and Model Adaptability: The impact of different prompting techniques, chain-of-thought reasoning, or model fine-tuning on performance is not thoroughly investigated.

Insufficient explanation of causes of regression. It would be useful for the authors to dig into the actual model outputs and categorize failure cases (tokenization issue, format mismatch vs actual instruction followability issue).

---

confidence: 5
contribution: 1
initial_rating: 3
presentation: 2
questions: In addition to points stated in weaknesses, It would be good to include following analysis:

- Task Difficulty Analysis: In Figure 6, tasks are ordered by median accuracy without prior analysis or justification of what makes some tasks harder than others. A taxonomy based on task nature, required implicit knowledge, number of steps, etc., compared to empirical accuracy, would be informative. The paper mentions only 91 out of 5,520 examples had PA=0 across all models. Could you provide more details about these examples? Are there common patterns that make these particularly challenging?

- Robustness Analysis : Incorporating robustness checks such as perturbations in instructions or introducing minor distractions, It would add a practical dimension to ProcBench, aligning it more closely with real-world scenarios where instructions may not always be perfectly structured.
soundness: 2
strengths: - I believe, this paper is clearly written and easy to understand.
- Various metrics to measure instruction following capabilities
summary: The authors develop a new benchmark, ProcBench, to assess the capacity of big language models to follow multi-step instructions taken from library of 23 text based tasks. They tested the performance of seven mostly closed source language models on ProcBench. The models need to construct sequences of intermediate and final states. Further, authors come up straightforward metrics in order to assess the performance of models for these tasks.
weaknesses: # Limitations


- Lack of Novelty : [1], [2] already demonstrate LLM's accuracy declines as, planning depth of procedurally generated problems increases. Paper doesn't propose any new technique that can improve/augment the instruction following capabilities.

- Insufficient Benchmarking: The paper fails to provide benchmarking insights across various model variants and sizes, which limits the usability of its benchmarking insights.

- Effect of tokenization : Given the tasks involve character manipulation, ablation about how different tokenization schemes (e.g., byte-level, subword-level, character-level) impact the models' ability to follow instructions and maintain coherence over long sequences would provide valuable insights into the relationship between input representation and procedural reasoning.

- Other techniques : techniques such as majority voting, self-consistency, self-refine [3] prompting to improve model adherence to instructions. Their analysis is completely absent. 

[1] : Karthik V. et al “LLMs Still Can’t Plan; Can LRMs? A Preliminary Evaluation of OpenAI’s o1 on PlanBench,”

[2] : Kevin W. et al "On The Planning Abilities of OpenAI's o1 Models: Feasibility, Optimality, and Generalizability"

[3] : Aman N. et al "Self-Refine: Iterative Refinement with Self-Feedback"

---

confidence: 4
contribution: 1
initial_rating: 3
presentation: 2
questions: - Is there some evidence that improving in this step-by-step instruction following where all the information is provided and the exact path is outlined is correlated with how well the LLM will be able to execute step-by-step instruction following when it needs to explore different paths + use implicit knowledge/world knowledge?
- Could you clarify how you transform the LLM output into a JSON format for assesement?
- Do you have a sense of how the model performance will vary if you don't prompt the model to do the task step by step but rather ask it to complete the steps in one go?
soundness: 3
strengths: - The paper introduces new metrics such as prefix match length, prefix accuracy, sequential match, and final match which provide some interesting analysis of the role task complexity (i.e. increasing the number of steps required for the task) plays in a model’s ability to perform extended precise instruction following
- The benchmark creation process is clear and is constructed in a manner to assess the capability coined as “instruction follow-ability”
summary: The paper first proposes that the general task of reasoning can be broken down into sub-capabilities (e.g. path exploration, selection of relevant knowledge, multi-step inference). The paper then adjusts the focus on evaluating multi-step inference capability in isolation. To achieve such evaluation, the authors construct 23 tasks that require manipulation of strings, integers, and lists such that the exact procedure to complete the task is explicitly provided, minimal implicit knowledge is required, and is straightforward for humans. Although these tasks provide some insight into a model’s capability of performing rote tasks, it does not provide sufficiently interesting tasks that separates itself from other instruction-following benchmarks. In order to gather some insights regarding task complexity and measure a model’s ability to follow precise instructions, the authors develop some metrics, namely, prefix match length, prefix accuracy, sequential match, and final match. These metrics provide some insight into the role task complexity (i.e. increasing the number of steps required for the task) plays in a model’s ability to perform extended precise instruction following. However, the findings are that the final match accuracy provides similar information as the prefix accuracy and sequential match metrics, thus, ultimately providing limited additional insights into models’ capabilities.
weaknesses: - The 23 tasks created are not representative of real tasks that an LLM would perform in practice and there were no experiments that attempts to correlate the performance on this type of instruction followability task to general reasoning tasks
- The paper mentions that a novelty of their benchmark to other instruction following benchmarks is that they are able to assess the intermediate steps and not rely simply on the final outcome. However, their empirical findings show that FM is, in practice, similar to PA and SM, which begs the question of whether evaluating final outcome is already sufficient enough to assess step-by-step explicit instruction following.
- A lack of interesting ablations/error analysis. Some ideas could be to compare FM performance when the model is prompted to complete the set of steps in one go or error analysis on the types of mistake the model makes and a breakdown of which step (whether it is earlier or later steps) the model usually makes the wrong move. It would also be interesting to see if the mistakes are mostly just error in one step but the rest of the steps, conditioned on that error, are still accurate.

---

confidence: 4
contribution: 2
initial_rating: 5
presentation: 3
questions: See Weaknesses



**After Rebuttal**

**Thanks for the author's response, although it was somewhat late. However, I noticed two points:**

1. The authors acknowledge that it is currently not possible to effectively establish the relationship between multi-step instruction-following ability and reasoning ability ("for future research"). However, this makes the mention of "MULTI-STEP REASONING" in the manuscript, particularly in the title, quite confusing. Since the relationship between ProcBench and reasoning ability cannot be validated, it raises the question of why reasoning ability is emphasized. I suggest the authors revise such phrasing, as it lacks rigor.

2. The authors have not responded to my third concern.

**Given these considerations, I believe the manuscript requires further refinement to meet the expected quality. Therefore, I have lowered my score.**
soundness: 3
strengths: - The authors provided a reasonable breakdown of reasoning abilities and, under controlled variables, introduced ProcBench to focus on exploring the multi-step instruction-following capabilities of models.
- The authors proposed metrics such as PML, PA, SM, and FM to assist in analyzing the performance of LLMs on ProcBench.
- The authors presented some interesting insights, including that the o1 series models exhibit a more gradual decline in performance as task difficulty increases, reflecting a fundamental difference between this series and other LLMs.
summary: In this paper, the authors interpret the reasoning process as the exploration of paths, the utilization of knowledge, and the following of multi-step instructions. They propose ProcBench, a benchmark consisting of 23 subtasks designed to evaluate the multi-step instruction-following capabilities of large language models (LLMs), aiming to assess the reasoning ability of LLMs from a specific perspective. The authors evaluated the performance of seven models on ProcBench and conducted corresponding analyses.
weaknesses: - When models engage in reasoning, they often do not follow a paradigm where they first plan all procedures and then execute them step by step, as typically reflected in benchmarks. Instead, they undergo a process of continuous exploration, following single-step instructions along the way. Therefore, the authors need to further verify the relationship between the multi-step instruction-following ability assessed by the benchmark and the actual reasoning ability. The experiments in the paper focus on ProcBench, but I suggest that the authors analyze the correlation between multi-step instruction-following ability and reasoning ability by statistically examining the reasoning performance of LLMs on relevant benchmarks and relating it to their performance on ProcBench.
- As the authors mentioned, 91 samples exhibit a PA of 0 across all models, which "could indicate not merely high difficulty but also potential flaws in task design." The authors are advised to conduct a case check to ensure the high quality of the benchmark.
- The authors provided quantitative statistics of LLM performance on ProcBench, but there is a lack of attribution analysis for model failures (as well as case studies), which is crucial for guiding model improvement.

Meta-review: The paper proposes a multi-step instruction following benchmark for LLMs that mainly consist of  tasks that do not assume access implicit knowledge (e.g., string manipulation). The paper also argued to use evaluation metrics that capture not only the correctness of the final outcome but also adherence to each intermediate step. Similar to prior literature, the results show that performance of LLMs (include the recent state of the models such as o1, claude and Gemini) degrade as we increase task complexity and number of steps.

Strengths:

- Precise instruction following using procedural benchmarks and partial correctness metrics are quite useful for analysis and benchmarking beyond final accuracy. 
- Open-Source Dataset and Code Availability for ProcBench  promotes reproducibility, and encourages future use.
- Clear presentation and well-written paper. 

Weaknesses: 
- Narrow set of tasks, focusing mainly on algorithmic and string manipulation. While such tasks are useful as diagnostics and surfacing differences in LLM capabilities, it's unclear whether higher performance on ProcBench corresponds to better reasoning capability on realistic tasks and common use cases of LLMs. 
- Lack of ablations analyzing design choices, particularly tokenization schemes (e.g., byte-level, subword-level, character-level). Other minor improvements could incorporate  prompting techniques to make tasks more self-contained, such as many-shot ICL or very long instruction prompts (e.g., task tutorial). 
- Lack of attribution analysis for current failure cases.  Fro example, planning and plan execution are not done independently, so it needs to be established how performance on ProcBench tasks relates to performance on the same tasks without explicit instructions to follow the specified plans (and just asking it to think step by step). The reviewers also suggested several interesting analysis / ablations. 

Reasons to reject: While the paper focuses on benchmarking an underexplored aspect of LLM instruction following capability, the paper has major weakness due to lack of real world applicability and the toy nature of the benchmark. The discussion and authors engagement during rebuttal did improve my view of this work, but I'm still leaning towards rejection.

Decision: Reject