The Backtrace I/O crash analysis platform fundamentally improves software debugging and fault detection by empowering engineers to identify root causes and trends with unparalleled efficiency

Backtrace I/O

backtraceio

Backtracking: Why We Replaced External Feedback With a Lightweight Classifier

The basics of backtracking has proven itself to be a universal algorithmic technique that can be applied while solving all kinds of computational problems, from the most primitive (such as counting all possible paths between two vertices) to the most complex ones (such as finding all Hamiltonian paths or solving the N Queen problem). Backtracking According to the study on , it can be defined as an improvement to the brute force approach. In other words, the basic idea behind the backtracking technique is the search for a solution to a particular problem among all the options available. fundamental backtracking The backtracking algorithm owes its success and effectiveness to the . When the algorithm initiates its extensive search for solutions, it promptly applies the abounding function, making it possible to determine whether a proposed solution meets the constraints set. In case the answer is positive, the algorithm continues its search. If this is not the case, the algorithm removes the branch and simply returns to the previous level. depth-first search method In general, there are three common types of problems that backtracking solves: problems - finding a feasible solution; Decision problems - finding the best solution possible; Optimization problems - finding all the feasible solutions. Enumeration Now, let's move on from theory to practice and have a look at by the backtracking techniques. Noteworthy is that both of the problems were taken from real job interviews, and they are included in the list. 2 algo problems solved Leetcode Top Interview Questions Subsets Problem description Given an integer array of unique elements, return . The solution set must not contain duplicate subsets. Return the solution in any order. nums all possible subsets (the power set) Input:  nums = [0,1,2] Output: [[],[0],[1],[0,1],[2],[0,2],[1,2],[0,1,2]] Idea It is common knowledge that the of a set is considered to be the set of all subsets of S, including both the empty set and itself. The power set of is graphically illustrated below: power set S S {0,1,2} The most direct way is to: compute all the subsets that do not contain a particular element (which could be any single element); U compute all the subsets that do contain the required element. V After it, each subset set must appear either in or in , providing us with the final result of . The construction is recursive, and the is when the input set is empty, in which case we return an empty list. U V U⋃V base case Example Now, it’s the right moment to study the example: Let = [0,1,2]. Pick any element, e.g., 0. nums First, we recursively compute all subsets of {1,2}. To do this, we select 1. This leaves us with {2}. Now, we pick 2 and get to the base case. -> {} Returning from the recursive calls: 3. So, the set of subsets of {2} is {} union with {2}, i.e., {{}, {2}}.
2. The set of subsets of {1, 2} is then {{}, {2}} union with {{1}, {1, 2}}, i.e., {{}, {2}, {1}, {1, 2}}. The set of subsets of {0,1,2} is then {{}, {2}, {1}, {1, 2}} union with {{0}, {0, 2}, {0, 1}, {0, 1, 2}}, i.e., {{}, {2}, {1}, {1, 2), {0}, {0, 2}, {0, 1}, {0, 1, 2}}. Solution class Solution {
  public List<List<Integer>> subsets(int[] nums) {
    List<List<Integer>> ans = new LinkedList<>();
    backtrack(nums, 0, new LinkedList<>(), ans);
    return ans;
  }

  void backtrack(int[] nums, int i, List<Integer> cur, List<List<Integer>> ans){
    ans.add(new ArrayList<>(cur));
    for (int j = i; j<nums.length; j++){
      cur.add(nums[j]);
      backtrack(nums, j + 1, cur, ans);
      cur.remove(cur.size() - 1);
    }
  }
} Performance all the subsets are generated and further copied to the output list using . The number of recursive calls, , satisfies the recurrence , which solves to . Since we spend time within a call, the time complexity is . The time complexity: O(N×2^N) C(n) C(n) = 2C(n - 1) C(n) = (2^N) O(N) O(N×2^N) is calculated by the following formula: . We are using the space to maintain , and are modifying in-place with backtracking. The space complexity O(N) O(N) cur cur Permutations Problem description Given an array of distinct integers, return . The answer can be returned in any order. nums all the possible permutations Input: nums = [1,2,3] Output: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]] Idea It is generally known that every permutation of begins with one of . The basic idea here is to generate all permutations starting with , then all permutations starting with , and so on. Computing all permutations starting with means computing all permutations of , which suggests the use of recursion. A A[0], A[1], ..., A[n-1] A[0] A[1] A[0] A[1:n-1] To compute all permutations starting with , we swap with and compute all permutations of the updated . As we go on, we restore the original state before embarking on the computation of all permutations that start with , and so on. A[1] A[0] A[1] A[1:n-1] A[2] Example For instance, for the array (1, 2, 3), we would first generate all permutations starting with 1. This implies generating all permutations of (2, 3). Next, we find all permutations of (2, 3) starting with 2. Given that (3) is an array of length 1, it has the only possible permutation. The implication of this is that (2, 3) has a single permutation starting with 2. After that, we look for permutations of (2, 3) starting with 3, which can be executed by swapping 2 and 3. Consequently, we will find out that there is a single permutation of (2, 3) starting with 3, namely, (3, 2). Hence, there are two permutations starting with 1: (1,2,3) and (1,3,2). To find all permutations starting with 2, we swap 1 with 2 and get two permutations again: (2,1,3) and (2,3,1). The last two permutations we add are (3,2,1) and (3,1,2). In total, there are six permutations: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,2,1) and (3,1,2). Solution class Solution {
  List<List<Integer>> result;

  public List<List<Integer>> permute(int[] nums) {
    Arrays.sort(nums);
    result = new ArrayList<>();
    permute(0, nums);
    return result;
   }

   private void permute(int i, int[] nums){
     if (i == nums.length - 1){
       copyToResult(nums);
     }
     for (int j = i; j<nums.length; j++){
       swap(i,j,nums);
       permute(i+1,nums);
       swap(j,i,nums);
     }
   }

  private void copyToResult(int[] nums){
    List<Integer> list = new ArrayList<>();
    for (int num: nums){
      list.add(num);
    }
    result.add(list);
  }

  private void swap(int i, int j, int[] nums){
    int t = nums[i];
    nums[i] = nums[j];
    nums[j] = t;
  }
} Performance The time complexity is , since there are permutations, and we spend time to store each one. Having studied this example, we can observe that backtracking only visits each state once, which is why its time complexity should be similar to the graph traversal of O(|V|+|E|). 0(n×n!) n! 0(n) Conclusion Summing up the above, backtracking is definitely a perfect algorithmic technique for solving both subset and permutation problems. With the help of its depth-first search method, the backtracking algorithm will inevitably find the required solution in strict compliance with all given constraints. Since 1950, when the term “ ” was coined by D. H. Lehmer, an American mathematician, backtracking managed to handle a wide range of practice problems, starting from printing all paths from a given source to a destination and finishing with finding the shortest safe route in a path with landmines. In this regard, the next time you deal with either permutations or subsets, I strongly recommend that you use the backtracking algo pattern. backtracking List of references Aziz, Adnan; Prakash, Amit; Lee, Tsung-Hsien (2012). “Elements of Programming Interviews in Java” Gurari, Eitan (1999). “CIS 680: DATA STRUCTURES: Chapter 19: Backtracking Algorithms” “Introduction to Backtracking - Data Structure and Algorithm Tutorials” - GeeksforGeeks Upadhyay, Soni (2023). “What is Backtracking Algorithm? Types, Examples & its Application” Zibbu, Shirsh (2018). “Sudoku and Backtracking”

Backtracking LeetCode Pattern: Permutations vs Subsets in Java

in this blog post, we are going to take a look at what is backtracking and how to implement it using ruby First thing first what is backtracking? according to Backtracking is a general algorithm for finding all (or some) solutions to some computational problem notably constrain satisfaction problems that incrementally builds candidates to the solutions, and abandons a candidate ("backtracks") as soon as it determines that the candidate cannot possibly be completed to a valid solution. wikipedia To understand what backtracking is let's take a problem and try to solve it using backtracking. we will be given a tow input where the first number is the desired sum and the remaining is an array of numbers. Determine if the array or any of its sub-arrays can be summed to get the exact sum analyzing the above problem here are the steps we want to follow to solve the problem Implement the recursive function to find all the possible sub-arrays recursively. Follow backtracking strategy and implement required base-cases to process each recursive level. subtract  the first element of every sub-array to the sum and return true if the sum is 0 and return false if the sum is less than 0 or the array is empty. since our steps seem complete let's take a sample case sum== sum < arr.empty?
exact_sum?(sum - arr[ ], arr[ ,arr.length]) puts exact_sum?( , [ , , , , ]); def exact_sum? (sum, arr) return true if 0 return false if 0 || 0 1 end 12 1 2 3 4 5 # expected result => true # actual resut => false looking at the input you can see that if you remove 3 from the array and try to sum it you will get 12 but why do we get false? well the answer is that our above still recursive so we need to make it backtracking and the way to do that is by checking both cases where we include the first element and when we don't By doing that here's how the flow of our algorithm should look like let's include a variable K representing our sum and see how it would work let's implement that in our previous algorithm sum== sum < arr.empty? exact_sum?(sum - arr[ ], arr[ ,arr.length]) exact_sum?(sum, arr[ ,arr.length]) puts exact_sum?( , [ , , , , ]); def exact_sum? (sum, arr) return true if 0 return false if 0 || # now we are checking both cases 0 1 || 1 end 12 1 2 3 4 5 # => true by adding a or statement the algorithm will be checking both cases and will become a backtracking algorithm but this still a little bit confusing let's print the values to fully understand the flow of our algorithm [ , , , , ] [ , , , ] [ , , ] [ , ] [ ] [ ] [ , ] [ ] # the algorithm start 1 2 3 4 5 12 # check for the first condition : 12-1 is not less than 0 so we subtract it from the sum 2 3 4 5 11 # check again 11-2 > 0 is true so we proceed 3 4 5 9 # same thing here 4 5 6 # here 2-5 will return false so we go back to the parent call([4,5]6) and try to exclude the first case without touching the sum 5 2 # we still get false because the array will be empty and the sum will be 1 so go back to the ancestor call([3,4,5]9)and exclude the first element without touching the sum 5 6 # 9-4 > 0 is true so we proceed 4 5 9 # 5-5 is 0 so we return true 5 5 true And Voila!!! just with those few lines of code we have implemented a backtracking algorithm. Thank you for reading If you have any question or suggestion contact me on Twitter

An Introduction to Backtracking in Ruby

Using Sudoku to explore backtracking Sudoku is a number-placement where the objective is to fill a square grid of size ‘n’ with numbers between 1 to ‘n’. The numbers must be placed so that each column, each row, and each of the sub-grids (if any) contains all of the numbers from 1 to ‘n’. Sudoku puzzle The most common Sudoku puzzles use a 9x9 grid. The grids are partially filled (with hints) to ensure a solution can be reached. And here’s the solution. Notice how each row, each column and each sub-grid have all numbers from 1 to 9. Some puzzles may even have multiple solutions. The solution to above Sudoku puzzle. One row, column and sub-grid have been highlighted. Aside: solving a Sudoku puzzle Sudoku is a logic-based puzzle. Needless to say, solving one requires a series of logical moves and might require a bit of guesswork. Since this isn’t an article to explore how to solve a Sudoku puzzle, I’ll just a leave a link to one that helped me getting started: . kristanix.com/sudokuepic/sudoku-solving-techniques Backtracking Backtracking is an algorithm for finding all (or some) of the solutions to a problem that incrementally builds candidates to the solution(s). As soon as it determines that a candidate cannot possibly lead to a valid solution, it abandons the candidate. Backtracking is all about choices and consequences. Abandoning a candidate typically results in visiting a previous stage of the problem-solving-process. This is what it means to “backtrack” — visit a previous stage and explore new possibilities from thereon. Usually, apart from the original problem and the end goal, we also have a set of constraints that the solution must satisfy. The simplest (read ‘dumbest’) implementations often use little to no “logic” or “insight” to the problem. Instead, they frantically try to find a solution by guesswork. A backtracking algorithm can be thought of as a . In this tree, the root node is the original problem, each node is a candidate and the leaf nodes are possible solution candidates. We traverse the tree depth-first from root to a leaf node to solve the problem. tree of possibilities Tree of Possibilities for a typical backtracking algorithm The tree diagram also shows 2 groups — and . Unexplored Possible Candidates Impossible Candidates UPC marks nodes that were never explored. Some of them could have been viable candidates, leading to another solution. Since we never explored them, we can never know. Problems where multiple solutions are acceptable won’t have this group. IC groups are the obvious ones. It contains nodes which have a failed candidate node as one of their ancestor nodes. None of the nodes in this group are candidate nodes and none of the leaf nodes are solution nodes. Sudoku & Backtracking We will now create a Sudoku solver using backtracking by our problem, goal and constraints in a step-by-step algorithm. encoding Problem Given a, possibly, partially filled grid of size ‘n’, completely fill the grid with number between 1 and ‘n’. Goal Goal is defined for verifying the solution. Once the goal is reached, searching terminates. A fully filled grid is a solution if: Each row has all numbers form 1 to ‘n’. Each column has all numbers form 1 to ‘n’. Each sub-grid (if any) has all numbers form 1 to ‘n’. Constraints Constraints are defined for verifying each candidate. A candidate is valid if: Each row has unique numbers form 1 to ’n’ or empty spaces. Each column has unique numbers form 1 to ‘n’ or empty spaces. Each sub-grid (if any) has unique numbers form 1 to ‘n’ or empty spaces. Termination conditions Typically, backtracking algorithms have termination conditions other than reaching goal. These help with failures in solving the problem and special cases of the problem itself. There are no empty spots left to fill and the candidate still doesn’t qualify as a the solution. There are no empty spots to begin with, i.e., the grid is already fully filled. Step-by-step algorithm Here’s how our code will “guess” at each step, all the way to the final solution: Make a list of all the empty spots. Select a spot and place a number, between 1 and ‘n’, in it and validate the candidate grid. If any of the constraints fails, . Otherwise, check if the goal is reached. abandon candidate and repeat step 2 with the next number If a solution is found, stop searching. Otherwise, repeat steps 2 to 4. Pen-paper demo . Now let’s try all this in practice with a simple 3x3 grid. Groovy A 3x3 Sudoku puzzle We start off by listing all the empty spots. If we label each cell in the grid with a pair of numbers and mark the first cell , then our empty spots will be at locations: (x,y) (1,1) (1,2) (2,2) (2,3) (3,1) (3,2) We now select the first spot to work with. Since this is a 3x3 grid, we have numbers 1 to 3 at our disposal and no sub-grids to worry about (sub-grids are only a bother for grids with squared sides, like 4, 9, 16 etc.). (1,2) Let’s place number in this spot and see if it fits. 1 Filling ‘1’ in spot (1, 2) It does. Great. We can now select the next spot on the list and do the same thing again. This time however, it fails. We already have a in this row. This means that we must — which is . (2,2) 1 abandon candidate and repeat step 2 with the next number 2 Filling 2 in spot (2, 2) One more spot is filled. Also, it might not look like it, but we did just perform backtracking on a single spot. We abandoned a candidate solution ( at spot ), visited a previous stage (empty spot ) and explored a new candidate solution (number at spot ). Huzzah! 1 (2,2) (2,2) 2 (2,2) When we move on to spot , we have another problem. As you can see, we are all out of options. None of the possible numbers fit in. This means that we must now . Only this time, we must visit spot first to fix spot . (2,3) abandon candidate and repeat step 2 with the next number (2,2) (2,3) Failure to fill spot (2, 3) We need to fill number in spot and that will resolve the issue. 3 (2,2) Backtracking to spot (2, 2) and then re-visiting spot (2, 3) We now repeat this process until with either reach the goal or we hit one of the termination conditions. Since this was a demo problem, it should be obvious that we’d arrive at the solution without any further complications. Solved 3x3 Sudoku puzzle However, consider the same grid with one small change. Replacing the in cell with a renders the grid unsolvable. Similarly, removing hints from cells and allows for multiple solutions. But since this algorithm has a single goal, it stops after the first solution is reached. 1 (3,3) 2 (2,1) (3,3) Unsolvable 3x3 puzzle (left) and Multi-solution 3x3 puzzle (right) Here’s what the looks like: tree of possibilities Tree of Possibilities for 3x3 Sudoku Implementation Enough talk. Let’s code … Disclaimer (for python-istas): The code you’re about to see is not pythonic.IMHO, it is borderline ugly. The purpose of this snippet is to explain convert the steps shown above into simple, meaningful code and not to boast the elegance of python. What next? This article aims to strengthen the concept of backtracking by drawing connections with a popular game of logic. I should tell you that Sudoku is an ‘ . As complex as it may sound, it really isn’t (not for the scope of this article): NP-complete combinatorial problem’ means that while we can verify a solution, it is rather to arrive at one. NP-complete easily difficult means that to arrive at a solution, we must perform selection and arrangement of some data — combination and permutation. Combinatorial Sample problems We can try to solve some other problems by basing our approach on our current understanding. The problem is a close enough relative to the Sudoku solver. Two more problems that rank similar are and . Binary Watch Combination Sum III Permutation Sequence There are that you can try on. However, trying to mold them into the Sudoku solver pattern might not always be trivial. It’s best to try to formulate your approach in the following pattern: a lot more problems Problem Goal Constraints Termination conditions Step-by-step algorithm

Sudoku and Backtracking

Authors:
(1) Gladys Tyen, University of Cambridge, Dept. of Computer Science & Technology, ALTA Institute, and Work done during an internship at Google Research (e-mail: gladys.tyen@cl.cam.ac.uk);
(2) Hassan Mansoor, Google Research (e-mail: hassan@google.com);
(3) Victor Carbune, Google Research  (e-mail: vcarbune@google.com);
(4) Peter Chen, Google Research and Equal leadership contribution (chenfeif@google.com);
(5) Tony Mak, Google Research and Equal leadership contribution (e-mail: tonymak@google.com). Table of Links Abstract and Introduction BIG-Bench Mistake Benchmark results Backtracking Related Works Conclusion, Limitations, and References A. Implementational details B. Annotation C. Benchmark scores B Annotation We release our annotation guidelines at https:// github.com/WHGTyen/BIG-Bench-Mistake. During annotation of the multistep arithmetic task, we found that the first CoT step given in the original BIG-Bench Hard prompt examples (Suzgun et al., 2022) was incorrect. Since all generated traces contained the same first step, we removed that step before showing traces to the annotators. Figure 3 contains an example screenshot of the user interface. For every trace, we provide the input question as well as the target answer, with a note to be aware of errors that may occur in correctans traces. Annotators can click on words to highlight the same word across the trace and the question text, which we found was particularly helpful for some tasks such as word sorting and tracking shuffled objects. Buttons on the right automatically become inactive if a previous step has been labelled as negative. This paper is available on arxiv under CC 4.0 license. Authors: (1) Gladys Tyen, University of Cambridge, Dept. of Computer Science & Technology, ALTA Institute, and Work done during an internship at Google Research (e-mail: gladys.tyen@cl.cam.ac.uk); (2) Hassan Mansoor, Google Research (e-mail: hassan@google.com); (3) Victor Carbune, Google Research  (e-mail: vcarbune@google.com); (4) Peter Chen, Google Research and Equal leadership contribution (chenfeif@google.com); (5) Tony Mak, Google Research and Equal leadership contribution (e-mail: tonymak@google.com). Authors: Authors: (1) Gladys Tyen, University of Cambridge, Dept. of Computer Science & Technology, ALTA Institute, and Work done during an internship at Google Research (e-mail: gladys.tyen@cl.cam.ac.uk); (2) Hassan Mansoor, Google Research (e-mail: hassan@google.com); (3) Victor Carbune, Google Research  (e-mail: vcarbune@google.com); (4) Peter Chen, Google Research and Equal leadership contribution (chenfeif@google.com); (5) Tony Mak, Google Research and Equal leadership contribution (e-mail: tonymak@google.com). Table of Links Abstract and Introduction Abstract and Introduction BIG-Bench Mistake BIG-Bench Mistake Benchmark results Benchmark results Backtracking Backtracking Related Works Related Works Conclusion, Limitations, and References Conclusion, Limitations, and References A. Implementational details A. Implementational details B. Annotation B. Annotation C. Benchmark scores C. Benchmark scores B Annotation We release our annotation guidelines at https:// github.com/WHGTyen/BIG-Bench-Mistake. During annotation of the multistep arithmetic task, we found that the first CoT step given in the original BIG-Bench Hard prompt examples (Suzgun et al., 2022) was incorrect. Since all generated traces contained the same first step, we removed that step before showing traces to the annotators. Figure 3 contains an example screenshot of the user interface. For every trace, we provide the input question as well as the target answer, with a note to be aware of errors that may occur in correctans traces. Annotators can click on words to highlight the same word across the trace and the question text, which we found was particularly helpful for some tasks such as word sorting and tracking shuffled objects. Buttons on the right automatically become inactive if a previous step has been labelled as negative. This paper is available on arxiv under CC 4.0 license. This paper is available on arxiv under CC 4.0 license. available on arxiv

Our Annotations Guide for BIG-Bench Mistake

Authors:
(1) Gladys Tyen, University of Cambridge, Dept. of Computer Science & Technology, ALTA Institute, and Work done during an internship at Google Research (e-mail: gladys.tyen@cl.cam.ac.uk);
(2) Hassan Mansoor, Google Research (e-mail: hassan@google.com);
(3) Victor Carbune, Google Research  (e-mail: vcarbune@google.com);
(4) Peter Chen, Google Research and Equal leadership contribution (chenfeif@google.com);
(5) Tony Mak, Google Research and Equal leadership contribution (e-mail: tonymak@google.com). Table of Links Abstract and Introduction BIG-Bench Mistake Benchmark results Backtracking Related Works Conclusion, Limitations, and References A. Implementational details B. Annotation C. Benchmark scores A Implementational details A.1 3-shot CoT prompting to generate traces for BIG-Bench Mistake We use PaLM 2 L (Unicorn) to generate the traces used in BIG-Bench Mistake. All traces are generated at temperature = 0. Our prompts and examples can be found at https://github.com/WHGTyen/ BIG-Bench-Mistake. Our prompts are based on chain-of-thought prompts in the BIG-Bench Hard dataset (Suzgun et al., 2022), with four main changes: 1. Example CoT traces in the prompt is broken up into smaller steps (typically one sentence per step). This is done so that mistake location information is more precise. 2. Following Yao et al. (2022), each step in the prompt is signposted with “Thought 1”, “Thought 2:”, etc. This allows us to refer to the number of the step when prompting for mistake location. 3. For the logical deduction task, we find that the notation used in the original prompt with question marks is often inconsistent. It becomes difficult for annotators to determine whether a question mark is a mistake or not, because the correctness of the question mark is dependent on its interpretation. To minimise such ambiguity, the question mark notation is rewritten into text. 4. For the multistep arithmetic task, one of the prompt examples is altered to increase the length of the equation. This is because the BIG-Bench Hard dataset (where the prompts are taken from) only used equations of a specific length, but our dataset contains equations of averaged a variety of lengths, in accordance with the original BIG-Bench dataset (Srivastava et al., 2022) Following Yao et al. (2022), we use the newline as the stop token, which generates one step with every generation call. We algorithmically append “Thought N:” before each step. This allows us to split up steps in a clear and systematic way. We stop generating once an answer is reached, which is detected using the following regex: (?<=[Tt]he answer is).*$ A.2 3-shot prompting to identify mistakes in BIG-Bench Mistake As described in section 3, we explore three different methods of prompting for mistake location: direct trace-level prompting, direct step-level prompting, and CoT step-level prompting. We use 3-shot prompting for all methods, and our prompts and examples can be found at https://github.com/ WHGTyen/BIG-Bench-Mistake. Our prompts follow OpenAI’s chat completion format. All results were obtained with temperature = 0 and no stop tokens. This paper is available on arxiv under CC 4.0 license. Authors: (1) Gladys Tyen, University of Cambridge, Dept. of Computer Science & Technology, ALTA Institute, and Work done during an internship at Google Research (e-mail: gladys.tyen@cl.cam.ac.uk); (2) Hassan Mansoor, Google Research (e-mail: hassan@google.com); (3) Victor Carbune, Google Research  (e-mail: vcarbune@google.com); (4) Peter Chen, Google Research and Equal leadership contribution (chenfeif@google.com); (5) Tony Mak, Google Research and Equal leadership contribution (e-mail: tonymak@google.com). Authors: Authors: (1) Gladys Tyen, University of Cambridge, Dept. of Computer Science & Technology, ALTA Institute, and Work done during an internship at Google Research (e-mail: gladys.tyen@cl.cam.ac.uk); (2) Hassan Mansoor, Google Research (e-mail: hassan@google.com); (3) Victor Carbune, Google Research  (e-mail: vcarbune@google.com); (4) Peter Chen, Google Research and Equal leadership contribution (chenfeif@google.com); (5) Tony Mak, Google Research and Equal leadership contribution (e-mail: tonymak@google.com). Table of Links Abstract and Introduction Abstract and Introduction BIG-Bench Mistake BIG-Bench Mistake Benchmark results Benchmark results Backtracking Backtracking Related Works Related Works Conclusion, Limitations, and References Conclusion, Limitations, and References A. Implementational details A. Implementational details B. Annotation B. Annotation C. Benchmark scores C. Benchmark scores A Implementational details A.1 3-shot CoT prompting to generate traces for BIG-Bench Mistake We use PaLM 2 L (Unicorn) to generate the traces used in BIG-Bench Mistake. All traces are generated at temperature = 0. Our prompts and examples can be found at https://github.com/WHGTyen/ BIG-Bench-Mistake. Our prompts are based on chain-of-thought prompts in the BIG-Bench Hard dataset (Suzgun et al., 2022), with four main changes: 1. Example CoT traces in the prompt is broken up into smaller steps (typically one sentence per step). This is done so that mistake location information is more precise. 2. Following Yao et al. (2022), each step in the prompt is signposted with “Thought 1”, “Thought 2:”, etc. This allows us to refer to the number of the step when prompting for mistake location. 3. For the logical deduction task, we find that the notation used in the original prompt with question marks is often inconsistent. It becomes difficult for annotators to determine whether a question mark is a mistake or not, because the correctness of the question mark is dependent on its interpretation. To minimise such ambiguity, the question mark notation is rewritten into text. 4. For the multistep arithmetic task, one of the prompt examples is altered to increase the length of the equation. This is because the BIG-Bench Hard dataset (where the prompts are taken from) only used equations of a specific length, but our dataset contains equations of averaged a variety of lengths, in accordance with the original BIG-Bench dataset (Srivastava et al., 2022) Following Yao et al. (2022), we use the newline as the stop token, which generates one step with every generation call. We algorithmically append “Thought N:” before each step. This allows us to split up steps in a clear and systematic way. We stop generating once an answer is reached, which is detected using the following regex: (?<=[Tt]he answer is).*$ A.2 3-shot prompting to identify mistakes in BIG-Bench Mistake As described in section 3, we explore three different methods of prompting for mistake location: direct trace-level prompting, direct step-level prompting, and CoT step-level prompting. We use 3-shot prompting for all methods, and our prompts and examples can be found at https://github.com/ WHGTyen/BIG-Bench-Mistake. Our prompts follow OpenAI’s chat completion format. All results were obtained with temperature = 0 and no stop tokens. This paper is available on arxiv under CC 4.0 license. This paper is available on arxiv under CC 4.0 license. available on arxiv

BIG-Bench Mistake: Implementational Details That Are Important

Authors:
(1) Gladys Tyen, University of Cambridge, Dept. of Computer Science & Technology, ALTA Institute, and Work done during an internship at Google Research (e-mail: gladys.tyen@cl.cam.ac.uk);
(2) Hassan Mansoor, Google Research (e-mail: hassan@google.com);
(3) Victor Carbune, Google Research  (e-mail: vcarbune@google.com);
(4) Peter Chen, Google Research and Equal leadership contribution (chenfeif@google.com);
(5) Tony Mak, Google Research and Equal leadership contribution (e-mail: tonymak@google.com). Table of Links Abstract and Introduction BIG-Bench Mistake Benchmark results Backtracking Related Works Conclusion, Limitations, and References A. Implementational details B. Annotation C. Benchmark scores 6 Conclusion In this paper, we describe and release our dataset BIG-Bench Mistake for mistake finding, and propose a backtracking method to correct logical errors in CoT style traces. We show that LLMs generally struggle with finding logical errors without external feedback, but argue that this feedback can come from a reward model instead. Finally, we demonstrate the effectiveness of backtracking, both with gold standard labels as well as with simulated reward models at lower levels of accuracy. Limitations One main limitation of our dataset is that it features tasks that are artificial and unrealistic for real-world applications. We made this choice to minimise ambiguity and subjectivity during the mistake finding process, but further work needs to be done to determine the effectiveness of backtracking in a more realistic setting. Another limitation is that our paper does not evaluate backtracking on the original datasets on BIG-Bench, only showing results on the limited set that we sampled in a skewed manner, in order to maximise the value of the human annotators’ time. We leave the full evaluation to future work. References Rohan Anil, Andrew M Dai, Orhan Firat, Melvin Johnson, Dmitry Lepikhin, Alexandre Passos, Siamak Shakeri, Emanuel Taropa, Paige Bailey, Zhifeng Chen, et al. 2023. Palm 2 technical report. arXiv preprint arXiv:2305.10403. Pinzhen Chen, Zhicheng Guo, Barry Haddow, and Kenneth Heafield. 2023. Iterative translation refinement with large language models. arXiv preprint arXiv:2306.03856. Andrew F Hayes and Klaus Krippendorff. 2007. Answering the call for a standard reliability measure for coding data. Communication methods and measures, 1(1):77–89. Jiaxin Huang, Shixiang Shane Gu, Le Hou, Yuexin Wu, Xuezhi Wang, Hongkun Yu, and Jiawei Han. 2022. Large language models can self-improve. arXiv preprint arXiv:2210.11610. Jie Huang, Xinyun Chen, Swaroop Mishra, Huaixiu Steven Zheng, Adams Wei Yu, Xinying Song, and Denny Zhou. 2023. Large language models cannot self-correct reasoning yet. arXiv preprint arXiv:2310.01798. Geunwoo Kim, Pierre Baldi, and Stephen McAleer. 2023. Language models can solve computer tasks. arXiv preprint arXiv:2303.17491. Hunter Lightman, Vineet Kosaraju, Yura Burda, Harri Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe. 2023. Let’s verify step by step. arXiv preprint arXiv:2305.20050. Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, et al. 2023. Self-refine: Iterative refinement with self-feedback. arXiv preprint arXiv:2303.17651. Ning Miao, Yee Whye Teh, and Tom Rainforth. 2023. Selfcheck: Using llms to zero-shot check their own step-by-step reasoning. arXiv preprint arXiv:2308.00436. Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. 2022. Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems, 35:27730–27744. Liangming Pan, Michael Saxon, Wenda Xu, Deepak Nathani, Xinyi Wang, and William Yang Wang. 2023. Automatically correcting large language models: Surveying the landscape of diverse self-correction strategies. arXiv preprint arXiv:2308.03188. William Saunders, Catherine Yeh, Jeff Wu, Steven Bills, Long Ouyang, Jonathan Ward, and Jan Leike. 2022. Self-critiquing models for assisting human evaluators. arXiv preprint arXiv:2206.05802. Noah Shinn, Federico Cassano, Edward Berman, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao. 2023. Reflexion: Language agents with verbal reinforcement learning. Aarohi Srivastava, Abhinav Rastogi, Abhishek Rao, Abu Awal Md Shoeb, Abubakar Abid, Adam Fisch, Adam R Brown, Adam Santoro, Aditya Gupta, Adrià Garriga-Alonso, et al. 2022. Beyond the imitation game: Quantifying and extrapolating the capabilities of language models. arXiv preprint arXiv:2206.04615. Aarohi Srivastava, Abhinav Rastogi, Abhishek Rao, Abu Awal Md Shoeb, Abubakar Abid, Adam Fisch, Adam R Brown, Adam Santoro, Aditya Gupta, Adrià Garriga-Alonso, et al. 2023. Beyond the imitation game: Quantifying and extrapolating the capabilities of language models. Transactions on Machine Learning Research. 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. 2022. Big-bench-hard/cotprompts. https://github.com/suzgunmirac/ BIG-Bench-Hard/tree/main/cot-prompts. Accessed: 2023-10-31. Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc V. Le, Ed H. Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. 2023. Self-consistency improves chain of thought reasoning in language models. In ICLR 2023. Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, brian ichter, Fei Xia, Ed Chi, Quoc V Le, and Denny Zhou. 2022. Chain-of-thought prompting elicits reasoning in large language models. In Advances in Neural Information Processing Systems, volume 35, pages 24824–24837. Curran Associates, Inc. Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. 2022. React: Synergizing reasoning and acting in language models. arXiv preprint arXiv:2210.03629. This paper is available on arxiv under CC 4.0 license. Authors: (1) Gladys Tyen, University of Cambridge, Dept. of Computer Science & Technology, ALTA Institute, and Work done during an internship at Google Research (e-mail: gladys.tyen@cl.cam.ac.uk); (2) Hassan Mansoor, Google Research (e-mail: hassan@google.com); (3) Victor Carbune, Google Research  (e-mail: vcarbune@google.com); (4) Peter Chen, Google Research and Equal leadership contribution (chenfeif@google.com); (5) Tony Mak, Google Research and Equal leadership contribution (e-mail: tonymak@google.com). Authors: Authors: (1) Gladys Tyen, University of Cambridge, Dept. of Computer Science & Technology, ALTA Institute, and Work done during an internship at Google Research (e-mail: gladys.tyen@cl.cam.ac.uk); (2) Hassan Mansoor, Google Research (e-mail: hassan@google.com); (3) Victor Carbune, Google Research  (e-mail: vcarbune@google.com); (4) Peter Chen, Google Research and Equal leadership contribution (chenfeif@google.com); (5) Tony Mak, Google Research and Equal leadership contribution (e-mail: tonymak@google.com). Table of Links Abstract and Introduction Abstract and Introduction BIG-Bench Mistake BIG-Bench Mistake Benchmark results Benchmark results Backtracking Backtracking Related Works Related Works Conclusion, Limitations, and References Conclusion, Limitations, and References A. Implementational details A. Implementational details B. Annotation B. Annotation C. Benchmark scores C. Benchmark scores 6 Conclusion In this paper, we describe and release our dataset BIG-Bench Mistake for mistake finding, and propose a backtracking method to correct logical errors in CoT style traces. We show that LLMs generally struggle with finding logical errors without external feedback, but argue that this feedback can come from a reward model instead. Finally, we demonstrate the effectiveness of backtracking, both with gold standard labels as well as with simulated reward models at lower levels of accuracy. Limitations One main limitation of our dataset is that it features tasks that are artificial and unrealistic for real-world applications. We made this choice to minimise ambiguity and subjectivity during the mistake finding process, but further work needs to be done to determine the effectiveness of backtracking in a more realistic setting. Another limitation is that our paper does not evaluate backtracking on the original datasets on BIG-Bench, only showing results on the limited set that we sampled in a skewed manner, in order to maximise the value of the human annotators’ time. We leave the full evaluation to future work. References Rohan Anil, Andrew M Dai, Orhan Firat, Melvin Johnson, Dmitry Lepikhin, Alexandre Passos, Siamak Shakeri, Emanuel Taropa, Paige Bailey, Zhifeng Chen, et al. 2023. Palm 2 technical report. arXiv preprint arXiv:2305.10403. Pinzhen Chen, Zhicheng Guo, Barry Haddow, and Kenneth Heafield. 2023. Iterative translation refinement with large language models. arXiv preprint arXiv:2306.03856. Andrew F Hayes and Klaus Krippendorff. 2007. Answering the call for a standard reliability measure for coding data. Communication methods and measures, 1(1):77–89. Jiaxin Huang, Shixiang Shane Gu, Le Hou, Yuexin Wu, Xuezhi Wang, Hongkun Yu, and Jiawei Han. 2022. Large language models can self-improve. arXiv preprint arXiv:2210.11610. Jie Huang, Xinyun Chen, Swaroop Mishra, Huaixiu Steven Zheng, Adams Wei Yu, Xinying Song, and Denny Zhou. 2023. Large language models cannot self-correct reasoning yet. arXiv preprint arXiv:2310.01798. Geunwoo Kim, Pierre Baldi, and Stephen McAleer. 2023. Language models can solve computer tasks. arXiv preprint arXiv:2303.17491. Hunter Lightman, Vineet Kosaraju, Yura Burda, Harri Edwards, Bowen Baker, Teddy Lee, Jan Leike, John Schulman, Ilya Sutskever, and Karl Cobbe. 2023. Let’s verify step by step. arXiv preprint arXiv:2305.20050. Aman Madaan, Niket Tandon, Prakhar Gupta, Skyler Hallinan, Luyu Gao, Sarah Wiegreffe, Uri Alon, Nouha Dziri, Shrimai Prabhumoye, Yiming Yang, et al. 2023. Self-refine: Iterative refinement with self-feedback. arXiv preprint arXiv:2303.17651. Ning Miao, Yee Whye Teh, and Tom Rainforth. 2023. Selfcheck: Using llms to zero-shot check their own step-by-step reasoning. arXiv preprint arXiv:2308.00436. Long Ouyang, Jeffrey Wu, Xu Jiang, Diogo Almeida, Carroll Wainwright, Pamela Mishkin, Chong Zhang, Sandhini Agarwal, Katarina Slama, Alex Ray, et al. 2022. Training language models to follow instructions with human feedback. Advances in Neural Information Processing Systems, 35:27730–27744. Liangming Pan, Michael Saxon, Wenda Xu, Deepak Nathani, Xinyi Wang, and William Yang Wang. 2023. Automatically correcting large language models: Surveying the landscape of diverse self-correction strategies. arXiv preprint arXiv:2308.03188. William Saunders, Catherine Yeh, Jeff Wu, Steven Bills, Long Ouyang, Jonathan Ward, and Jan Leike. 2022. Self-critiquing models for assisting human evaluators. arXiv preprint arXiv:2206.05802. Noah Shinn, Federico Cassano, Edward Berman, Ashwin Gopinath, Karthik Narasimhan, and Shunyu Yao. 2023. Reflexion: Language agents with verbal reinforcement learning. Aarohi Srivastava, Abhinav Rastogi, Abhishek Rao, Abu Awal Md Shoeb, Abubakar Abid, Adam Fisch, Adam R Brown, Adam Santoro, Aditya Gupta, Adrià Garriga-Alonso, et al. 2022. Beyond the imitation game: Quantifying and extrapolating the capabilities of language models. arXiv preprint arXiv:2206.04615. Aarohi Srivastava, Abhinav Rastogi, Abhishek Rao, Abu Awal Md Shoeb, Abubakar Abid, Adam Fisch, Adam R Brown, Adam Santoro, Aditya Gupta, Adrià Garriga-Alonso, et al. 2023. Beyond the imitation game: Quantifying and extrapolating the capabilities of language models. Transactions on Machine Learning Research. 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. 2022. Big-bench-hard/cotprompts. https://github.com/suzgunmirac/ BIG-Bench-Hard/tree/main/cot-prompts. Accessed: 2023-10-31. Xuezhi Wang, Jason Wei, Dale Schuurmans, Quoc V. Le, Ed H. Chi, Sharan Narang, Aakanksha Chowdhery, and Denny Zhou. 2023. Self-consistency improves chain of thought reasoning in language models. In ICLR 2023. Jason Wei, Xuezhi Wang, Dale Schuurmans, Maarten Bosma, brian ichter, Fei Xia, Ed Chi, Quoc V Le, and Denny Zhou. 2022. Chain-of-thought prompting elicits reasoning in large language models. In Advances in Neural Information Processing Systems, volume 35, pages 24824–24837. Curran Associates, Inc. Shunyu Yao, Jeffrey Zhao, Dian Yu, Nan Du, Izhak Shafran, Karthik Narasimhan, and Yuan Cao. 2022. React: Synergizing reasoning and acting in language models. arXiv preprint arXiv:2210.03629. This paper is available on arxiv under CC 4.0 license. This paper is available on arxiv under CC 4.0 license. available on arxiv

LLMs Can Correct Reasoning Errors! But Not Without Limitations

Authors:
(1) Gladys Tyen, University of Cambridge, Dept. of Computer Science & Technology, ALTA Institute, and Work done during an internship at Google Research (e-mail: gladys.tyen@cl.cam.ac.uk);
(2) Hassan Mansoor, Google Research (e-mail: hassan@google.com);
(3) Victor Carbune, Google Research  (e-mail: vcarbune@google.com);
(4) Peter Chen, Google Research and Equal leadership contribution (chenfeif@google.com);
(5) Tony Mak, Google Research and Equal leadership contribution (e-mail: tonymak@google.com). Table of Links Abstract and Introduction BIG-Bench Mistake Benchmark results Backtracking Related Works Conclusion, Limitations, and References A. Implementational details B. Annotation C. Benchmark scores 5 Related work Datasets To our knowledge, the only publicly available dataset containing mistake annotations in LLM outputs is PRM800K (Lightman et al., 2023), which is a dataset of solutions to Olympiad-level math questions. Our dataset BIG-Bench Mistake covers a wider range of tasks to explore the reasoning capabilities of LLMs more thoroughly. Additionally, the generator LLM used in PRM800K has been fine-tuned on 1.5B math tokens as well as a dataset of step-by-step math solutions. For this paper, we wanted to explore few-shot in-context learning methods, which is typically used in realworld applications with API-based LLMs. Self-correction Pan et al. (2023) present a plethora of self-correction methods in recent literature. While their list includes training-time correction strategies such as RLHF (Ouyang et al., 2022) and self-improve (Huang et al., 2022), our backtracking method falls into the category of post-hoc correction, where the correction process is applied to outputs that have already been generated. Our paper focuses on correction of logical and reasoning errors, rather than stylistic or qualitative improvements. Previous post-hoc correction methods that are applied to reasoning errors include Reflexion (Shinn et al., 2023) and RCI (Kim et al., 2023), both of which cause performance deterioration when the oracle label is not used (Huang et al., 2023). Other methods such as Self-Refine (Madaan et al., 2023) and iterative refinement (Chen et al., 2023) focus on q ualitative or stylistic improvements rather than correcting logical errors. This paper is available on arxiv under CC 4.0 license. Authors: (1) Gladys Tyen, University of Cambridge, Dept. of Computer Science & Technology, ALTA Institute, and Work done during an internship at Google Research (e-mail: gladys.tyen@cl.cam.ac.uk); (2) Hassan Mansoor, Google Research (e-mail: hassan@google.com); (3) Victor Carbune, Google Research  (e-mail: vcarbune@google.com); (4) Peter Chen, Google Research and Equal leadership contribution (chenfeif@google.com); (5) Tony Mak, Google Research and Equal leadership contribution (e-mail: tonymak@google.com). Authors: Authors: (1) Gladys Tyen, University of Cambridge, Dept. of Computer Science & Technology, ALTA Institute, and Work done during an internship at Google Research (e-mail: gladys.tyen@cl.cam.ac.uk); (2) Hassan Mansoor, Google Research (e-mail: hassan@google.com); (3) Victor Carbune, Google Research  (e-mail: vcarbune@google.com); (4) Peter Chen, Google Research and Equal leadership contribution (chenfeif@google.com); (5) Tony Mak, Google Research and Equal leadership contribution (e-mail: tonymak@google.com). Table of Links Abstract and Introduction Abstract and Introduction BIG-Bench Mistake BIG-Bench Mistake Benchmark results Benchmark results Backtracking Backtracking Related Works Related Works Conclusion, Limitations, and References Conclusion, Limitations, and References A. Implementational details A. Implementational details B. Annotation B. Annotation C. Benchmark scores C. Benchmark scores 5 Related work Datasets To our knowledge, the only publicly available dataset containing mistake annotations in LLM outputs is PRM800K (Lightman et al., 2023), which is a dataset of solutions to Olympiad-level math questions. Our dataset BIG-Bench Mistake covers a wider range of tasks to explore the reasoning capabilities of LLMs more thoroughly. Additionally, the generator LLM used in PRM800K has been fine-tuned on 1.5B math tokens as well as a dataset of step-by-step math solutions. For this paper, we wanted to explore few-shot in-context learning methods, which is typically used in realworld applications with API-based LLMs. Self-correction Pan et al. (2023) present a plethora of self-correction methods in recent literature. While their list includes training-time correction strategies such as RLHF (Ouyang et al., 2022) and self-improve (Huang et al., 2022), our backtracking method falls into the category of post-hoc correction, where the correction process is applied to outputs that have already been generated. Our paper focuses on correction of logical and reasoning errors, rather than stylistic or qualitative improvements. Previous post-hoc correction methods that are applied to reasoning errors include Reflexion (Shinn et al., 2023) and RCI (Kim et al., 2023), both of which cause performance deterioration when the oracle label is not used (Huang et al., 2023). Other methods such as Self-Refine (Madaan et al., 2023) and iterative refinement (Chen et al., 2023) focus on q ualitative or stylistic improvements rather than correcting logical errors. This paper is available on arxiv under CC 4.0 license. This paper is available on arxiv under CC 4.0 license. available on arxiv

Using LLMs to Correct Reasoning Mistakes: Related Works That You Should Know About

Authors:
(1) Gladys Tyen, University of Cambridge, Dept. of Computer Science & Technology, ALTA Institute, and Work done during an internship at Google Research (e-mail: gladys.tyen@cl.cam.ac.uk);
(2) Hassan Mansoor, Google Research (e-mail: hassan@google.com);
(3) Victor Carbune, Google Research  (e-mail: vcarbune@google.com);
(4) Peter Chen, Google Research and Equal leadership contribution (chenfeif@google.com);
(5) Tony Mak, Google Research and Equal leadership contribution (e-mail: tonymak@google.com). Table of Links Abstract and Introduction BIG-Bench Mistake Benchmark results Backtracking Related Works Conclusion, Limitations, and References A. Implementational details B. Annotation C. Benchmark scores 3 Benchmark results Table 4 shows the accuracy of GPT-4-Turbo, GPT4, and GPT-3.5-Turbo on our mistake-finding dataset. For each question, the possible answers are either that there are no mistakes, or, if there is a mistake, the number N indicating the step in which the first mistake occurs. A model’s output is only considered correct if the location matches exactly, or the output correctly indicates that there are no mistakes. All models are given the same 3-shot prompts. We use three different prompting methods: • Direct trace-level prompting involves using the whole trace as input to the model and directly prompting for the mistake location. The model must output either the number representing the step, or "No". • Direct step-level prompting prompts for a binary Yes/No output for every step, indicating whether or not the step is correct. In each generation call, the input contains the partial trace up to (and including) the target step, but does not contain results for previous steps. The final answer is inferred from where the first "No" output occurs (subsequent steps are ignored). • CoT step-level prompting is an extension of direct, step-level prompting. Instead of a binary Yes/No response, we prompt the model to check the (partial) trace through a series of reasoning steps. This method is the most resource intensive of all three methods as it involves generating a whole CoT sequence for every step. Due to cost and usage limits, we are unable to provide results from GPT-4-Turbo here. As with direct step-level prompting, the final answer is inferred from where the first "No" output occurs (subsequent steps are ignored). 3.1 Discussion All three models appear to struggle with our mistake finding dataset. GPT-4 attains the best results but only reaches an overall accuracy of 52.87 with direct step-level prompting. Our findings are in line with and builds upon results from Huang et al. (2023), who show that existing self-correction strategies are ineffective on reasoning errors. In our experiments, we specifically target the models’ mistake finding ability and provide results for additional tasks. We show that state-of-the-art LLMs clearly struggle with mistake finding, even in the most simple and unambiguous cases. (For comparison, humans can identify mistakes without specific expertise, and have a high degree of agreement, as shown in Table 2.) We hypothesise that LLMs’ inability to find mistakes is a main contributing factor to why LLMs are unable to self-correct reasoning errors. If LLMs are unable to identify mistakes, it should be no surprise that they are unable to self-correct either. Note that the mistakes in our dataset are generated using PaLM 2 L (Unicorn), and traces were sampled according to whether the final answer was correct or not. Therefore, we expect that using PaLM 2 itself to do mistake finding will produce different and likely biased results. Further work is needed to elucidate the difference between crossmodel evaluation and self-evaluation. 3.2 Comparison of prompting methods As we compare results across the three methods, we find that the accuracy on traces with no mistakes goes down7 considerably from direct, trace-level prompting to CoT, step-level prompting. Figure 1 demonstrates this trade-off. We hypothesise that this is due to the number of outputs generated by the model. Our three methods involve generating increasingly complex outputs, starting with direct, trace-level prompting requiring a single token, then direct, step-level prompting requiring one token per step, and finally CoT step-level prompting requiring several sentences per step. If each generation call has some probability of identifying a mistake, then the more calls made on each trace, the more likely the model will identify at least one mistake. 3.3 Few-shot prompting for mistake location as a proxy for correctness In this section, we investigate whether our prompting methods can reliably determine the correctnessans of a trace rather than the mistake location. Our motivation was that even humans use mistake finding as a strategy for determining whether an answer is correct or not, such as when going through mathematical proofs, or working through argumentation. Additionally, one might think that directly predicting the correctnessans of a trace may be easier than having to pinpoint the precise location of an error We calculate averaged F1 scores based on whether the model predicts that there is a mistake in the trace. If there is a mistake, we assume the model prediction is that the trace is incorrectans. Otherwise, we assume the model prediction is that the trace is correctans. In Table 5, we average the F1s using correctans and incorrectans as the positive label, weighted according to the number of times each label occurs. Note that the baseline of predicting all traces as incorrect achieves a weighted F1 average of 78. The weighted F1 scores show that prompting for mistakes is a poor strategy for determining the correctness of the final answer. This is in line with our previous finding that LLMs struggle to identify mistake locations, and also builds upon results from Huang et al. (2023), who demonstrate that improvements from Reflexion (Shinn et al., 2023) and RCI (Kim et al., 2023) are only from using oracle correctnessans information. This paper is available on arxiv under CC 4.0 license. Authors: (1) Gladys Tyen, University of Cambridge, Dept. of Computer Science & Technology, ALTA Institute, and Work done during an internship at Google Research (e-mail: gladys.tyen@cl.cam.ac.uk); (2) Hassan Mansoor, Google Research (e-mail: hassan@google.com); (3) Victor Carbune, Google Research  (e-mail: vcarbune@google.com); (4) Peter Chen, Google Research and Equal leadership contribution (chenfeif@google.com); (5) Tony Mak, Google Research and Equal leadership contribution (e-mail: tonymak@google.com). Authors: Authors: (1) Gladys Tyen, University of Cambridge, Dept. of Computer Science & Technology, ALTA Institute, and Work done during an internship at Google Research (e-mail: gladys.tyen@cl.cam.ac.uk); (2) Hassan Mansoor, Google Research (e-mail: hassan@google.com); (3) Victor Carbune, Google Research  (e-mail: vcarbune@google.com); (4) Peter Chen, Google Research and Equal leadership contribution (chenfeif@google.com); (5) Tony Mak, Google Research and Equal leadership contribution (e-mail: tonymak@google.com). Table of Links Abstract and Introduction Abstract and Introduction BIG-Bench Mistake BIG-Bench Mistake Benchmark results Benchmark results Backtracking Backtracking Related Works Related Works Conclusion, Limitations, and References Conclusion, Limitations, and References A. Implementational details A. Implementational details B. Annotation B. Annotation C. Benchmark scores C. Benchmark scores 3 Benchmark results Table 4 shows the accuracy of GPT-4-Turbo, GPT4, and GPT-3.5-Turbo on our mistake-finding dataset. For each question, the possible answers are either that there are no mistakes, or, if there is a mistake, the number N indicating the step in which the first mistake occurs. A model’s output is only considered correct if the location matches exactly, or the output correctly indicates that there are no mistakes. All models are given the same 3-shot prompts. We use three different prompting methods: • Direct trace-level prompting involves using the whole trace as input to the model and directly prompting for the mistake location. The model must output either the number representing the step, or "No". • Direct trace-level prompting • Direct step-level prompting prompts for a binary Yes/No output for every step, indicating whether or not the step is correct. In each generation call, the input contains the partial trace up to (and including) the target step, but does not contain results for previous steps. The final answer is inferred from where the first "No" output occurs (subsequent steps are ignored). • Direct step-level prompting • CoT step-level prompting is an extension of direct, step-level prompting. Instead of a binary Yes/No response, we prompt the model to check the (partial) trace through a series of reasoning steps. This method is the most resource intensive of all three methods as it involves generating a whole CoT sequence for every step. Due to cost and usage limits, we are unable to provide results from GPT-4-Turbo here. As with direct step-level prompting, the final answer is inferred from where the first "No" output occurs (subsequent steps are ignored). • CoT step-level prompting 3.1 Discussion All three models appear to struggle with our mistake finding dataset. GPT-4 attains the best results but only reaches an overall accuracy of 52.87 with direct step-level prompting. Our findings are in line with and builds upon results from Huang et al. (2023), who show that existing self-correction strategies are ineffective on reasoning errors. In our experiments, we specifically target the models’ mistake finding ability and provide results for additional tasks. We show that state-of-the-art LLMs clearly struggle with mistake finding, even in the most simple and unambiguous cases. (For comparison, humans can identify mistakes without specific expertise, and have a high degree of agreement, as shown in Table 2.) We hypothesise that LLMs’ inability to find mistakes is a main contributing factor to why LLMs are unable to self-correct reasoning errors. If LLMs are unable to identify mistakes, it should be no surprise that they are unable to self-correct either. Note that the mistakes in our dataset are generated using PaLM 2 L (Unicorn), and traces were sampled according to whether the final answer was correct or not. Therefore, we expect that using PaLM 2 itself to do mistake finding will produce different and likely biased results. Further work is needed to elucidate the difference between crossmodel evaluation and self-evaluation. 3.2 Comparison of prompting methods As we compare results across the three methods, we find that the accuracy on traces with no mistakes goes down7 considerably from direct, trace-level prompting to CoT, step-level prompting. Figure 1 demonstrates this trade-off. We hypothesise that this is due to the number of outputs generated by the model. Our three methods involve generating increasingly complex outputs, starting with direct, trace-level prompting requiring a single token, then direct, step-level prompting requiring one token per step, and finally CoT step-level prompting requiring several sentences per step. If each generation call has some probability of identifying a mistake, then the more calls made on each trace, the more likely the model will identify at least one mistake. 3.3 Few-shot prompting for mistake location as a proxy for correctness In this section, we investigate whether our prompting methods can reliably determine the correctnessans of a trace rather than the mistake location. Our motivation was that even humans use mistake finding as a strategy for determining whether an answer is correct or not, such as when going through mathematical proofs, or working through argumentation. Additionally, one might think that directly predicting the correctnessans of a trace may be easier than having to pinpoint the precise location of an error We calculate averaged F1 scores based on whether the model predicts that there is a mistake in the trace. If there is a mistake, we assume the model prediction is that the trace is incorrectans. Otherwise, we assume the model prediction is that the trace is correctans. In Table 5, we average the F1s using correctans and incorrectans as the positive label, weighted according to the number of times each label occurs. Note that the baseline of predicting all traces as incorrect achieves a weighted F1 average of 78. The weighted F1 scores show that prompting for mistakes is a poor strategy for determining the correctness of the final answer. This is in line with our previous finding that LLMs struggle to identify mistake locations, and also builds upon results from Huang et al. (2023), who demonstrate that improvements from Reflexion (Shinn et al., 2023) and RCI (Kim et al., 2023) are only from using oracle correctnessans information. This paper is available on arxiv under CC 4.0 license. This paper is available on arxiv under CC 4.0 license. available on arxiv

What Are the Benchmark Results of GPT-4-Turbo, GPT4, and GPT-3.5-Turbo?

Authors:
(1) Gladys Tyen, University of Cambridge, Dept. of Computer Science & Technology, ALTA Institute, and Work done during an internship at Google Research (e-mail: gladys.tyen@cl.cam.ac.uk);
(2) Hassan Mansoor, Google Research (e-mail: hassan@google.com);
(3) Victor Carbune, Google Research  (e-mail: vcarbune@google.com);
(4) Peter Chen, Google Research and Equal leadership contribution (chenfeif@google.com);
(5) Tony Mak, Google Research and Equal leadership contribution (e-mail: tonymak@google.com). Table of Links Abstract and Introduction BIG-Bench Mistake Benchmark results Backtracking Related Works Conclusion, Limitations, and References A. Implementational details B. Annotation C. Benchmark scores 2 BIG-Bench Mistake BIG-Bench Mistake consists of 2186 sets of CoTstyle traces. Each trace was generated by PaLM 2-L-Unicorn, and annotated with the location of the first logical error. An example trace is shown in Table 1, where the mistake location3 is the 4th step. Our traces span across a set of 5 tasks4 from the BIG-bench dataset (Srivastava et al., 2023): word sorting, tracking shuffled objects, logical deduction, multi-step arithmetic, and Dyck languages. CoT prompting is used to prompt PaLM 2 to answer questions from each task. As we wanted to separate our CoT traces into distinct steps, we follow the method used by Yao et al. (2022) and generate each step separately, using the newline as a stop token. In this dataset, all traces are generated with temperature = 0. The correctness of answers are determined by exact match. Prompts can be found at https://github.com/WHGTyen/ BIG-Bench-Mistake. 2.1 Annotation Each generated trace is annotated with the first logical error. We ignore any subsequent errors as they may be dependent on the original error. Note that traces can contain a logical mistake yet arrive at the correct answer. To disambiguate the two types of correctness, we will use the terms correctans and incorrectans to refer to whether the final answer of the trace is correct. Accuracyans would therefore refer to the overall accuracy for the task, based on how many final answers are correct. To refer to whether the trace contains a logical mistake (rather than the correctness of the final answer), we will use correctmis and incorrectmis. 2.1.1 Hman annotation For 4 of the 5 tasks, we recruit human annotators to go through each trace and identify any errors. Annotators have no domain expertise but are given guidelines5 to complete the task. Before annotation, we sample a set of 300 traces for each task, where 255 (85%) are incorrectans, and 45 (15%) are correctans. Since human annotation is a limited and expensive resource, we chose this distribution to maximise the number of steps containing mistakes and to prevent over-saturation of correct steps. We also include some correctans traces because some may contain logical errors despite the correct answer, and to ensure that the dataset included examples of correct steps that are near the end of the trace. This also prevents annotators from feeling forced to find a mistake in all traces.To account for this skewed distribution, results in section 4 are split according to whether the original trace is correctans or incorrectans. Following Lightman et al. (2023), annotators are instructed to go through each step in the trace and indicate whether the step is correct or not (binary choice). Annotators only submit their answers until all steps have been annotated, or there is one incorrect step. If an incorrect step is identified, the remaining steps are skipped. This is done to avoid ambiguities where a logically correct deduction is dependent on a previous mistake. We make our annotation guidelines available at https:// github.com/WHGTyen/BIG-Bench-Mistake, and we include a screenshot of the user interface in Figure 3. Each trace has been annotated by at least 3 annotators. If there are any disagreements, we take the majority label. We calculate Krippendorff’s alpha (Hayes and Krippendorff, 2007) to measure inter-rater reliability (see Table 2). 2.1.2 Automatic annotation For Dyck languages, we opt for mostly automatic annotation instead of human annotation as the traces show limited variation in phrasing and solution paths. For each trace, we generate a set of standard steps based on the format used in the prompt examples. Using pattern matching, we can identify whether each model-generated step also conforms to the same format. If so, we compare the two and assume that the trace is incorrect if the symbols do not match. Additionally, we also account for edge cases such as where the final two steps are merged into one, or variations in presentation where some symbols are placed in quotes and some are not. We release the code at https://github.com/WHGTyen/ BIG-Bench-Mistake along with our dataset. This paper is available on arxiv under CC 4.0 license. Authors: (1) Gladys Tyen, University of Cambridge, Dept. of Computer Science & Technology, ALTA Institute, and Work done during an internship at Google Research (e-mail: gladys.tyen@cl.cam.ac.uk); (2) Hassan Mansoor, Google Research (e-mail: hassan@google.com); (3) Victor Carbune, Google Research  (e-mail: vcarbune@google.com); (4) Peter Chen, Google Research and Equal leadership contribution (chenfeif@google.com); (5) Tony Mak, Google Research and Equal leadership contribution (e-mail: tonymak@google.com). Authors: Authors: (1) Gladys Tyen, University of Cambridge, Dept. of Computer Science & Technology, ALTA Institute, and Work done during an internship at Google Research (e-mail: gladys.tyen@cl.cam.ac.uk); (2) Hassan Mansoor, Google Research (e-mail: hassan@google.com); (3) Victor Carbune, Google Research  (e-mail: vcarbune@google.com); (4) Peter Chen, Google Research and Equal leadership contribution (chenfeif@google.com); (5) Tony Mak, Google Research and Equal leadership contribution (e-mail: tonymak@google.com). Table of Links Abstract and Introduction Abstract and Introduction BIG-Bench Mistake BIG-Bench Mistake Benchmark results Benchmark results Backtracking Backtracking Related Works Related Works Conclusion, Limitations, and References Conclusion, Limitations, and References A. Implementational details A. Implementational details B. Annotation B. Annotation C. Benchmark scores C. Benchmark scores 2 BIG-Bench Mistake BIG-Bench Mistake consists of 2186 sets of CoTstyle traces. Each trace was generated by PaLM 2-L-Unicorn, and annotated with the location of the first logical error. An example trace is shown in Table 1, where the mistake location3 is the 4th step. Our traces span across a set of 5 tasks4 from the BIG-bench dataset (Srivastava et al., 2023): word sorting, tracking shuffled objects, logical deduction, multi-step arithmetic, and Dyck languages. CoT prompting is used to prompt PaLM 2 to answer questions from each task. As we wanted to separate our CoT traces into distinct steps, we follow the method used by Yao et al. (2022) and generate each step separately, using the newline as a stop token. In this dataset, all traces are generated with temperature = 0. The correctness of answers are determined by exact match. Prompts can be found at https://github.com/WHGTyen/ BIG-Bench-Mistake. 2.1 Annotation Each generated trace is annotated with the first logical error. We ignore any subsequent errors as they may be dependent on the original error. Note that traces can contain a logical mistake yet arrive at the correct answer. To disambiguate the two types of correctness, we will use the terms correctans and incorrectans to refer to whether the final answer of the trace is correct. Accuracyans would therefore refer to the overall accuracy for the task, based on how many final answers are correct. To refer to whether the trace contains a logical mistake (rather than the correctness of the final answer), we will use correctmis and incorrectmis. 2.1.1 Hman annotation For 4 of the 5 tasks, we recruit human annotators to go through each trace and identify any errors. Annotators have no domain expertise but are given guidelines5 to complete the task. Before annotation, we sample a set of 300 traces for each task, where 255 (85%) are incorrectans, and 45 (15%) are correctans. Since human annotation is a limited and expensive resource, we chose this distribution to maximise the number of steps containing mistakes and to prevent over-saturation of correct steps. We also include some correctans traces because some may contain logical errors despite the correct answer, and to ensure that the dataset included examples of correct steps that are near the end of the trace. This also prevents annotators from feeling forced to find a mistake in all traces.To account for this skewed distribution, results in section 4 are split according to whether the original trace is correctans or incorrectans. Following Lightman et al. (2023), annotators are instructed to go through each step in the trace and indicate whether the step is correct or not (binary choice). Annotators only submit their answers until all steps have been annotated, or there is one incorrect step. If an incorrect step is identified, the remaining steps are skipped. This is done to avoid ambiguities where a logically correct deduction is dependent on a previous mistake. We make our annotation guidelines available at https:// github.com/WHGTyen/BIG-Bench-Mistake, and we include a screenshot of the user interface in Figure 3. Each trace has been annotated by at least 3 annotators. If there are any disagreements, we take the majority label. We calculate Krippendorff’s alpha (Hayes and Krippendorff, 2007) to measure inter-rater reliability (see Table 2). 2.1.2 Automatic annotation For Dyck languages, we opt for mostly automatic annotation instead of human annotation as the traces show limited variation in phrasing and solution paths. For each trace, we generate a set of standard steps based on the format used in the prompt examples. Using pattern matching, we can identify whether each model-generated step also conforms to the same format. If so, we compare the two and assume that the trace is incorrect if the symbols do not match. Additionally, we also account for edge cases such as where the final two steps are merged into one, or variations in presentation where some symbols are placed in quotes and some are not. We release the code at https://github.com/WHGTyen/ BIG-Bench-Mistake along with our dataset. This paper is available on arxiv under CC 4.0 license. This paper is available on arxiv under CC 4.0 license. available on arxiv

BIG-Bench Mistake: What Is It?

Authors:
(1) Gladys Tyen, University of Cambridge, Dept. of Computer Science & Technology, ALTA Institute, and Work done during an internship at Google Research (e-mail: gladys.tyen@cl.cam.ac.uk);
(2) Hassan Mansoor, Google Research (e-mail: hassan@google.com);
(3) Victor Carbune, Google Research  (e-mail: vcarbune@google.com);
(4) Peter Chen, Google Research and Equal leadership contribution (chenfeif@google.com);
(5) Tony Mak, Google Research and Equal leadership contribution (e-mail: tonymak@google.com). Table of Links Abstract and Introduction BIG-Bench Mistake Benchmark results Backtracking Related Works Conclusion, Limitations, and References A. Implementational details B. Annotation C. Benchmark scores Abstract While self-correction has shown promise in improving LLM outputs in terms of style and quality (e.g. Chen et al., 2023; Madaan et al., 2023), recent attempts to self-correct logical or reasoning errors often cause correct answers to become incorrect, resulting in worse performances overall (Huang et al., 2023). In this paper, we break down the self-correction process into two core components: mistake finding and output correction. For mistake finding, we release BIG-Bench Mistake, a dataset of logical mistakes in Chain-of-Thought reasoning traces. We provide benchmark numbers for several state-of-the-art LLMs, and demonstrate that LLMs generally struggle with finding logical mistakes. For output correction, we propose a backtracking method which provides large improvements when given information on mistake location. We construe backtracking as a lightweight alternative to reinforcement learning methods, and show that it remains effective with a reward model at 60-70% accuracy. 1 Introduction Large Language Models (LLMs) have dominated the field of NLP in recent years, achieving state of-the-art performance in a large variety of applications. In particular, LLMs have demonstrated the ability to solve tasks with zero- or few-shot prompting, giving rise to prompting methods such as Chain-of-Thought (CoT) (Wei et al., 2022), SelfConsistency (SC) (Wang et al., 2023), ReAct (Yao et al., 2022), etc. Recent literature on few- or zero-shot prompting has focused on the concept of self-correction, i.e. having an LLM correct its own outputs (Shinn et al., 2023; Miao et al., 2023; Madaan et al., 2023; Chen et al., 2023; Saunders et al., 2022). (See Pan et al. (2023) for a review of the literature.) However, Huang et al. (2023) note that while self-correction may prove effective for improving model outputs in terms of style and quality, there is limited evidence that LLMs can identify and fix their own reasoning and logical errors without external feedback. For example, Reflexion (Shinn et al., 2023) and RCI (Kim et al., 2023) both use ground truth correctness as a signal to halt the selfcorrection loop. Initially observed by Madaan et al. (2023) on a math reasoning dataset, Huang et al. (2023) further demonstrate this shortcoming of selfcorrection in 2 additional datasets. While previous work typically present selfcorrection as a single process, we divide it into mistake finding and output correction. Mistake finding is a fundamental reasoning skill that has been studied and utilised extensively in philosophy, psychology, and mathematics, spawning concepts such as critical thinking, and logical and mathematical fallacies. One might expect that the ability to find mistakes should also be an important requirement for LLMs. However, our results show that state-of-the-art LLMs currently cannot find mistakes reliably. Output correction involves partially or completely changing previously generated outputs. In the context of self-correction, this is typically done with outputs generated by the same model (see Pan et al. (2023) for an overview of different strategies). Despite LLMs’ inability to find mistakes, our results show that they can correct outputs using our backtracking method, if given information about the mistakes, for example via a small, supervised reward model. Our contributions for this paper are as follows: 1. With Chain-of-Thought prompting, any task can be turned into a mistake-finding task. We collect and release1 to the research community BIGBench Mistake, a dataset of CoT-style traces generated using PaLM 2, and annotated according to where the first logical mistake is. To our knowledge, BIG-Bench Mistake is the first dataset of its kind that goes beyond problems in mathematics. 2. We produce benchmark results for our dataset to test the reasoning capabilities of state-of-the-art LLMs. We demonstrate that current state-ofthe-art LLMs struggle with mistake finding, even for objective, unambiguous cases. We hypothesise that this is a main contributing factor to LLMs’ inability to self-correct reasoning errors, and we call on the research community to pursue further improvements on the mistake finding task 3. We propose backtracking as an output correction technique that makes use of mistake location information to improve performance on the original task. We demonstrate that this method corrects outputs that are originally incorrect, with minimal effect on outputs that are originally correct. 4. We construe backtracking as a form of “verbal reinforcement learning” (Shinn et al., 2023), allowing iterative improvement on CoT outputs without requiring any weight updates. We propose that backtracking can be used with a trained classifier as a reward model, and demonstrate the effectiveness of backtracking at various reward model accuracies. This paper is available on arxiv under CC 4.0 license. Authors: (1) Gladys Tyen, University of Cambridge, Dept. of Computer Science & Technology, ALTA Institute, and Work done during an internship at Google Research (e-mail: gladys.tyen@cl.cam.ac.uk); (2) Hassan Mansoor, Google Research (e-mail: hassan@google.com); (3) Victor Carbune, Google Research  (e-mail: vcarbune@google.com); (4) Peter Chen, Google Research and Equal leadership contribution (chenfeif@google.com); (5) Tony Mak, Google Research and Equal leadership contribution (e-mail: tonymak@google.com). Authors: Authors: (1) Gladys Tyen, University of Cambridge, Dept. of Computer Science & Technology, ALTA Institute, and Work done during an internship at Google Research (e-mail: gladys.tyen@cl.cam.ac.uk); (2) Hassan Mansoor, Google Research (e-mail: hassan@google.com); (3) Victor Carbune, Google Research  (e-mail: vcarbune@google.com); (4) Peter Chen, Google Research and Equal leadership contribution (chenfeif@google.com); (5) Tony Mak, Google Research and Equal leadership contribution (e-mail: tonymak@google.com). Table of Links Abstract and Introduction Abstract and Introduction BIG-Bench Mistake BIG-Bench Mistake Benchmark results Benchmark results Backtracking Backtracking Related Works Related Works Conclusion, Limitations, and References Conclusion, Limitations, and References A. Implementational details A. Implementational details B. Annotation B. Annotation C. Benchmark scores C. Benchmark scores Abstract While self-correction has shown promise in improving LLM outputs in terms of style and quality (e.g. Chen et al., 2023; Madaan et al., 2023), recent attempts to self-correct logical or reasoning errors often cause correct answers to become incorrect, resulting in worse performances overall (Huang et al., 2023). In this paper, we break down the self-correction process into two core components: mistake finding and output correction. For mistake finding, we release BIG-Bench Mistake, a dataset of logical mistakes in Chain-of-Thought reasoning traces. We provide benchmark numbers for several state-of-the-art LLMs, and demonstrate that LLMs generally struggle with finding logical mistakes. For output correction, we propose a backtracking method which provides large improvements when given information on mistake location. We construe backtracking as a lightweight alternative to reinforcement learning methods, and show that it remains effective with a reward model at 60-70% accuracy. 1 Introduction Large Language Models (LLMs) have dominated the field of NLP in recent years, achieving state of-the-art performance in a large variety of applications. In particular, LLMs have demonstrated the ability to solve tasks with zero- or few-shot prompting, giving rise to prompting methods such as Chain-of-Thought (CoT) (Wei et al., 2022), SelfConsistency (SC) (Wang et al., 2023), ReAct (Yao et al., 2022), etc. Recent literature on few- or zero-shot prompting has focused on the concept of self-correction, i.e. having an LLM correct its own outputs (Shinn et al., 2023; Miao et al., 2023; Madaan et al., 2023; Chen et al., 2023; Saunders et al., 2022). (See Pan et al. (2023) for a review of the literature.) However, Huang et al. (2023) note that while self-correction may prove effective for improving model outputs in terms of style and quality, there is limited evidence that LLMs can identify and fix their own reasoning and logical errors without external feedback. For example, Reflexion (Shinn et al., 2023) and RCI (Kim et al., 2023) both use ground truth correctness as a signal to halt the selfcorrection loop. Initially observed by Madaan et al. (2023) on a math reasoning dataset, Huang et al. (2023) further demonstrate this shortcoming of selfcorrection in 2 additional datasets. While previous work typically present selfcorrection as a single process, we divide it into mistake finding and output correction. Mistake finding is a fundamental reasoning skill that has been studied and utilised extensively in philosophy, psychology, and mathematics, spawning concepts such as critical thinking, and logical and mathematical fallacies. One might expect that the ability to find mistakes should also be an important requirement for LLMs. However, our results show that state-of-the-art LLMs currently cannot find mistakes reliably. Output correction involves partially or completely changing previously generated outputs. In the context of self-correction, this is typically done with outputs generated by the same model (see Pan et al. (2023) for an overview of different strategies). Despite LLMs’ inability to find mistakes, our results show that they can correct outputs using our backtracking method, if given information about the mistakes, for example via a small, supervised reward model. Our contributions for this paper are as follows: 1. With Chain-of-Thought prompting, any task can be turned into a mistake-finding task. We collect and release1 to the research community BIGBench Mistake, a dataset of CoT-style traces generated using PaLM 2, and annotated according to where the first logical mistake is. To our knowledge, BIG-Bench Mistake is the first dataset of its kind that goes beyond problems in mathematics. 2. We produce benchmark results for our dataset to test the reasoning capabilities of state-of-the-art LLMs. We demonstrate that current state-ofthe-art LLMs struggle with mistake finding, even for objective, unambiguous cases. We hypothesise that this is a main contributing factor to LLMs’ inability to self-correct reasoning errors, and we call on the research community to pursue further improvements on the mistake finding task 3. We propose backtracking as an output correction technique that makes use of mistake location information to improve performance on the original task. We demonstrate that this method corrects outputs that are originally incorrect, with minimal effect on outputs that are originally correct. 4. We construe backtracking as a form of “verbal reinforcement learning” (Shinn et al., 2023), allowing iterative improvement on CoT outputs without requiring any weight updates. We propose that backtracking can be used with a trained classifier as a reward model, and demonstrate the effectiveness of backtracking at various reward model accuracies. This paper is available on arxiv under CC 4.0 license. This paper is available on arxiv under CC 4.0 license. available on arxiv

LLMs Cannot Find Reasoning Errors, but They Can Correct Them!

The change in sentiment surrounding Wall Street has been palpable as stubborn inflation continues in its refusal to subside. Following December’s buoyant outlook and the expectation among some that rate cuts could come as soon as March, markets are now having to react to the very real possibility that there may be no cuts at all this year. But how could a higher-for-longer scenario impact the S&P 500? March had been pinpointed as an optimistic stage for the beginning of the Fed’s switch to a dovish monetary policy as the battle against inflation continued to be won. Instead, it was March’s Consumer Price Index (CPI) figures that sparked concern throughout Wall Street. CPI inflation surpassed expectations to post a 3.5% increase in consumer prices for the year to March. Although it weighed in only a little higher than its 3.4% forecast, the headlines were clear: high inflation isn’t going anywhere fast. The S&P 500 reacted to the news by retracing sharply from a period of consistent growth that began in late October 2023, posting a decline of more than 5% from its March 28th peak of 5,254.35. Following the decline, the contrast between the optimistic start to Q1 2024 and Q2 is jarring. While the S&P 500 posted growth of more than 10% in the first quarter, much of its progress has been undone by the shifting economic outlook. More pessimism could be on the way. Although the market-implied odds for no cuts to take place at all in 2024 remains low at 11%, confounding inflation figures could see the prospect of a higher-for-longer period of high inflation manifest throughout the year. According to Bank of America economists, the prospect of no rate cuts until March 2025 at the earliest is a “real risk.” The economists still believe that one single cut taking place throughout the year is the most likely scenario, but it’s clear that investors need to consider the possibility of inflation staying for a good while longer on Wall Street. At the beginning of the year, forecasts had been suggesting that at least six quarter-percentage point reductions would be likely, and markets had largely priced in lower rates moving into the new year. This makes April’s inflation figures especially worrying. But what’s next for the S&P 500 and Wall Street as a whole? Keeping Up With Expectations Wall Street has largely managed to perform well amid historically high interest rates in 2023, so why is the news that rates may stay higher for longer so concerning? The cause for concern stems from the market’s ability to anticipate events and prices in its expectations many months in advance. The S&P 500’s market rally of more than 25% between late October and late March has been down in no small part to the anticipation that the Fed’s switch to a dovish monetary policy means rate cuts are imminent. We can see in the index’s rapid 5% drop that these shifting expectations are a key cause for concern among investors, who may be exploring more safe haven strategies while uncertainty creeps back into Wall Street. Here, the problem stems from the S&P 500’s exceptional form in the wake of Federal Reserve rate cuts. Investors likely saw parallels between the 2023 economic climate and 1995, in which the Fed doubled interest rates to 6% in 12 months before undergoing a series of cuts once inflation calmed to 2%. With the final rate hike arriving on February 1st and the first cut taking place on July 6th of the same year, 1995 became a springboard for growth on the S&P 500, with the index posting 34% growth–its highest annual gain since the 1950s. As the parallels broke down and CPI data arrived hotter than expected, the timely reality check for the S&P 500 has been particularly tumultuous. What Will Higher for Longer Look Like? With interest rate hikes in 2023 coinciding with the generative AI boom, the S&P 500 actually posted a strong annual growth rate of 24%. Should the rate of innovation in this industry continue to facilitate both hype and adoption at an enterprise level, it’s entirely possible that big tech stocks can continue to bring positivity to US markets even during times of high-interest rates. However, the wider impact of higher-for-longer rates can be varied depending on the impacted stocks and their fundamentals. While the first interest rate hikes in 2022 saw stocks with high valuations struggle, the 2023 macroeconomic climate forced more investors to look instead at how the bottom line of companies was being impacted by higher rates. Rob Haworth, senior investment strategy director at U.S. Bank Wealth Management, suggests that this puts smaller companies under the microscope due to issues in funding at higher rates, as opposed to more resilient larger companies with higher liquidity to navigate uncertainty. Data supports this thesis. While the large-cap stocks populating the S&P 500 Growth Index suffered a 29.41% decline in 2022, the small-cap stocks among the Russell 2000 Index performed better, experiencing smaller losses of 20.44%. These fortunes were reversed in 2023, with the S&P 500 Growth and Russell 2000 posting growth of 30.03% and 16.93% respectively. This trend is continuing into 2024, and recent disappointment surrounding the expectation of rate cuts is likely to push more investors to look for stocks that offer economic stability, rather than riskier opportunities based on innovation. With this in mind, the S&P 500 stocks that boast stronger balance sheets and higher cash reserves could become a leading choice on the index, but backtracking rate expectations will likely pave the way for more long-term volatility throughout US markets. “Given these dynamics, investors may choose to take a balanced approach by diversifying their portfolios to include both safe assets such as gold and riskier assets such as both growth and value stocks,” explained Maxim Manturov, head of investment research at Freedom Finance Europe. “While cautious optimism may prevail in the stock market, the appeal of gold as a hedge against economic uncertainty remains attractive, from a tactical perspective.” “Gold's expected upside is emphasized by the speculative potential offered by the NUGT ETF (Direxion Daily Gold Miners Index Bull 2x Shares), presenting an attractive proposition for investors in terms of risk/reward ratio from current levels.” Diversification Remains Key for Investors Although we’re experiencing a generative AI boom, the uncertainty of the current economic climate suggests that more diversification should be a priority for investors. Building exposure to more commodities can be an excellent way of hedging against more disappointment and confounding inflation figures in 2024, but investor optimism can help to drive markets off the back of good news. The record-breaking S&P 500 rally of 1995 will shape sentiment today, and the arrival of any lower-than-expected CPI data could see more optimism flood back into US markets. While it’s difficult to anticipate Fed rate cuts in 2024, sentiment will continue to shape Wall Street performance throughout the year, and with this in mind, maintaining some levels of exposure can go a long way toward building a sustainable portfolio amid wider market uncertainty. The change in sentiment surrounding Wall Street has been palpable as stubborn inflation continues in its refusal to subside. Following December’s buoyant outlook and the expectation among some that rate cuts could come as soon as March, markets are now having to react to the very real possibility that there may be no cuts at all this year. But how could a higher-for-longer scenario impact the S&P 500? March had been pinpointed as an optimistic stage for the beginning of the Fed’s switch to a dovish monetary policy as the battle against inflation continued to be won. Instead, it was March’s Consumer Price Index (CPI) figures that sparked concern throughout Wall Street. CPI inflation surpassed expectations to post a 3.5% increase in consumer prices for the year to March. Although it weighed in only a little higher than its 3.4% forecast, the headlines were clear: high inflation isn’t going anywhere fast. 3.5% increase 3.5% increase The S&P 500 reacted to the news by retracing sharply from a period of consistent growth that began in late October 2023, posting a decline of more than 5% from its March 28th peak of 5,254.35. Following the decline, the contrast between the optimistic start to Q1 2024 and Q2 is jarring. While the S&P 500 posted growth of more than 10% in the first quarter , much of its progress has been undone by the shifting economic outlook. more than 10% in the first quarter more than 10% in the first quarter More pessimism could be on the way. Although the market-implied odds for no cuts to take place at all in 2024 remains low at 11%, confounding inflation figures could see the prospect of a higher-for-longer period of high inflation manifest throughout the year. According to Bank of America economists , the prospect of no rate cuts until March 2025 at the earliest is a “real risk.” The economists still believe that one single cut taking place throughout the year is the most likely scenario, but it’s clear that investors need to consider the possibility of inflation staying for a good while longer on Wall Street. Bank of America economists Bank of America economists At the beginning of the year, forecasts had been suggesting that at least six quarter-percentage point reductions would be likely, and markets had largely priced in lower rates moving into the new year. This makes April’s inflation figures especially worrying. But what’s next for the S&P 500 and Wall Street as a whole? Keeping Up With Expectations Wall Street has largely managed to perform well amid historically high interest rates in 2023, so why is the news that rates may stay higher for longer so concerning? The cause for concern stems from the market’s ability to anticipate events and prices in its expectations many months in advance. The S&P 500’s market rally of more than 25% between late October and late March has been down in no small part to the anticipation that the Fed’s switch to a dovish monetary policy means rate cuts are imminent. We can see in the index’s rapid 5% drop that these shifting expectations are a key cause for concern among investors, who may be exploring more safe haven strategies while uncertainty creeps back into Wall Street. Here, the problem stems from the S&P 500’s exceptional form in the wake of Federal Reserve rate cuts. Investors likely saw parallels between the 2023 economic climate and 1995, in which the Fed doubled interest rates to 6% in 12 months before undergoing a series of cuts once inflation calmed to 2%. likely saw parallels likely saw parallels With the final rate hike arriving on February 1st and the first cut taking place on July 6th of the same year, 1995 became a springboard for growth on the S&P 500, with the index posting 34% growth–its highest annual gain since the 1950s. As the parallels broke down and CPI data arrived hotter than expected, the timely reality check for the S&P 500 has been particularly tumultuous. What Will Higher for Longer Look Like? With interest rate hikes in 2023 coinciding with the generative AI boom, the S&P 500 actually posted a strong annual growth rate of 24%. Should the rate of innovation in this industry continue to facilitate both hype and adoption at an enterprise level, it’s entirely possible that big tech stocks can continue to bring positivity to US markets even during times of high-interest rates. However, the wider impact of higher-for-longer rates can be varied depending on the impacted stocks and their fundamentals. While the first interest rate hikes in 2022 saw stocks with high valuations struggle, the 2023 macroeconomic climate forced more investors to look instead at how the bottom line of companies was being impacted by higher rates. Rob Haworth, senior investment strategy director at U.S. Bank Wealth Management, suggests that this puts smaller companies under the microscope due to issues in funding at higher rates, as opposed to more resilient larger companies with higher liquidity to navigate uncertainty. Data supports this thesis. While the large-cap stocks populating the S&P 500 Growth Index suffered a 29.41% decline in 2022, the small-cap stocks among the Russell 2000 Index performed better, experiencing smaller losses of 20.44%. These fortunes were reversed in 2023, with the S&P 500 Growth and Russell 2000 posting growth of 30.03% and 16.93% respectively. growth of 30.03% and 16.93% growth of 30.03% and 16.93% This trend is continuing into 2024, and recent disappointment surrounding the expectation of rate cuts is likely to push more investors to look for stocks that offer economic stability, rather than riskier opportunities based on innovation. With this in mind, the S&P 500 stocks that boast stronger balance sheets and higher cash reserves could become a leading choice on the index, but backtracking rate expectations will likely pave the way for more long-term volatility throughout US markets. “Given these dynamics, investors may choose to take a balanced approach by diversifying their portfolios to include both safe assets such as gold and riskier assets such as both growth and value stocks,” explained Maxim Manturov, head of investment research at Freedom Finance Europe . Freedom Finance Europe “While cautious optimism may prevail in the stock market, the appeal of gold as a hedge against economic uncertainty remains attractive, from a tactical perspective.” “Gold's expected upside is emphasized by the speculative potential offered by the NUGT ETF (Direxion Daily Gold Miners Index Bull 2x Shares), presenting an attractive proposition for investors in terms of risk/reward ratio from current levels.” Diversification Remains Key for Investors Although we’re experiencing a generative AI boom, the uncertainty of the current economic climate suggests that more diversification should be a priority for investors. Building exposure to more commodities can be an excellent way of hedging against more disappointment and confounding inflation figures in 2024, but investor optimism can help to drive markets off the back of good news. The record-breaking S&P 500 rally of 1995 will shape sentiment today, and the arrival of any lower-than-expected CPI data could see more optimism flood back into US markets. While it’s difficult to anticipate Fed rate cuts in 2024, sentiment will continue to shape Wall Street performance throughout the year, and with this in mind, maintaining some levels of exposure can go a long way toward building a sustainable portfolio amid wider market uncertainty.

What’s the Fate of the S&P 500 if Rate Cuts Don’t Happen in 2024?

যদি 2024 সালে রেট কম না হয় তাহলে S&P 500-এর ভাগ্য কী?

Was droht dem S&P 500, wenn es 2024 nicht zu Zinssenkungen kommt?

¿Cuál es el destino del S&P 500 si no se producen recortes de tipos en 2024?

Quel sera le sort du S&P 500 si les baisses de taux ne se produisent pas en 2024 ?

यदि 2024 में ब्याज दरों में कटौती नहीं होती है तो S&P 500 का क्या होगा?

2024年に利下げが行われない場合、S&P 500の運命はどうなるでしょうか?

2024년에 금리 인하가 일어나지 않는다면 S&P 500의 운명은 어떻게 될까요?

Qual será o destino do S&P 500 se os cortes nas taxas não acontecerem em 2024?

Какова судьба S&P 500, если снижение ставок не произойдет в 2024 году?

2024'te Faiz İndirimi Olmazsa S&P 500'ün Kaderi Ne Olur?

Số phận của S&P 500 sẽ ra sao nếu việc cắt giảm lãi suất không xảy ra vào năm 2024?

如果 2024 年不降息，标准普尔 500 指数的命运将会如何？

Elevating Software Quality: A Guide to Effective Code Reviews

This paper is under CC 4.0 license. available on arxiv Authors: (1) Ryen W. White, Microsoft Research, Redmond, WA, USA. Table of Links Abstract and Taking Search to task AI Copilots Challenges Opportunities The Undiscovered Country and References ABSTRACT As many of us in the information retrieval (IR) research community know and appreciate, search is far from being a solved problem. Millions of people struggle with tasks on search engines every day. Often, their struggles relate to the intrinsic complexity of their task and the failure of search systems to fully understand the task and serve relevant results [58]. The task motivates the search, creating the gap/problematic situation that searchers attempt to bridge/resolve and drives search behavior as they work through different task facets. Complex search tasks require more than support for rudimentary fact finding or re-finding. Research on methods to support complex tasks includes work on generating query and website suggestions [21, 62], personalizing and contextualizing search [4], and developing new search experiences, including those that span time and space [1, 64]. The recent emergence of generative artificial intelligence (AI) and the arrival of assistive agents, or copilots, based on this technology, has the potential to offer further assistance to searchers, especially those engaged in complex tasks [41, 61]. There are profound implications from these advances for the design of intelligent systems and for the future of search itself. This article, based on a keynote by the author at the 2023 ACM SIGIR Conference, explores these issues and charts a course toward new horizons in information access guided by AI copilots. ACM Reference Format: Ryen W. White. 2023. Navigating Complex Search Tasks with AI Copilots. Under review at REDACTED. October, 2023 1 TAKING SEARCH TO TASK Tasks are a critical part of people’s daily lives. The market for dedicated task applications that help people with their “to do” tasks is likely to grow significantly (effectively triple in size) over the next few years.[1] There are many examples of such applications that can help both individuals (e.g., Microsoft To Do, Google Tasks, Todoist) and teams (e.g., Asana, Trello, Monday.com) tackle their tasks more effectively. Over time, these systems will increasingly integrate AI to better help their users capture, manage, and complete their tasks [60]. In information access scenarios such as search, tasks play an important role in motivating searching via gaps in knowledge and problematic situations [3, 15]. AI can be central in these search scenarios, too, especially in assisting with complex search tasks. 1.1 Tasks in Search Tasks drive the search process. The IR and information science communities have long studied tasks in search [42] and many information seeking models consider the role of task directly [3, 15]. Prior research has explored the different stages of task execution (e.g., pre-focus, focus formation, post-focus) [53], task levels [39], task facets [29], tasks defined on intents (e.g., informational, transactional, and navigational [8]; well-defined or ill-defined [23]; lookup, learn, or investigate [32]), the hierarchical structure of tasks [68], the characteristics of tasks, and the attributes of task searcher interaction, e.g., task difficulty and, of course, a focus in this article, task complexity [11, 26]. As a useful framing device to help conceptualize tasks and develop system support for them, tasks can be represented as trees comprising macrotasks (high level goals), subtasks (specific components of those goals), and actions (specific steps taken by searchers toward the completion of those components) [42]. Figure 1 presents an example of a “task tree” for a task involving an upcoming vacation to Paris, France. Examples of macrotasks, subtasks, and actions are included. Moves around this tree correspond to different task applications such as task recognition (up), task decomposition (down), and task prediction (across). Only actions (e.g., queries, clicks, and so on) are directly observable to traditional search engines. However, with recent advances in search copilots (more fully supporting natural language interactions via language understanding and language generation), more aspects of macrotasks and subtasks are becoming visible to search systems and more fully understood by those systems. Challenges in working with tasks include how to represent them within search systems, how to observe more task-relevant activity and content to develop richer task models, and how to develop task-oriented interfaces that place tasks and their completion at the forefront of user engagement. Task complexity deserves a special focus in this article given the challenges that searchers can still face with complex tasks and the significant potential of AI to help searchers tackle complex tasks. 1.2 Complex Search Tasks Recent estimates suggest that half of all Web searches are not answered.[2] Many of those searches are connected to complex search tasks. These tasks are ill-defined and/or multi-step, span multiple queries, sessions, and/or devices, and require deep engagement with search engines (many queries, backtracking, branching, etc.) to complete them [21]. Complex tasks also often have many facets and cognitive dimensions, and are closely connected to searcher characteristics such as domain expertise and task familiarity [38, 58]. To date, there have been significant attempts to support complex search tasks via humans (e.g., librarians, subject matter experts) and search systems (both general Web search engines and those tailored to specific industry verticals or domains). The main technological progress so far has been in areas such as query suggestion and contextual search, with new experiences also being developed that utilize multiple devices, provide cross-session support, and enable conversational search. We are now also seeing emerging search-related technologies in the area of generative AI [35]. Before proceeding, let us dive into these different types of existing and emerging search support for complex tasks in more detail. Researchers and practitioners have long developed and deployed support such as query suggestion and trail suggestion, e.g., [21, 45], including providing guided tours [51] and suggesting popular trail destinations [62] as ways to find relevant resources. This coincides with work on contextual search and personalized search, e.g., [4, 47, 63], where search systems can use data from the current searcher such as session activity, location, reading level, and so on, and the searcher’s long-term activity history, to provide more relevant results. Search engines may also use cohort activities to help with cold-start problems for new users and augment personal profiles for more established searchers [48, 69]. • Suggestions, personalization, and contextualization: Devices have different capabilities and can be used in different settings. Multidevice experiences, e.g., [64], utilizing multiple devices simultaneously to better support complex tasks such as recipe preparation, auto repair, and home improvement that have been decomposed into steps manually or automatically [73]. Cross-device and cross-session support [1, 56] can help with ongoing/background searches for complex tasks that persist over space and time. For example, being able to predict task continuation can help with “slow search” applications that focus more on result quality than the near instantaneous retrieval of search results [46]. • Multi-device, cross-device, and cross-session: Natural language is an expressive and powerful means of communicating intentions and preferences with search systems. The introduction of clarification questions on search engine result pages (SERPs) [71], progress on conversational search [20], and even “conversations” with documents (where searchers can inquire about document content via natural language dialog) [49], enable these systems to engage more fully with searchers to better understand their tasks and goals. There are now many emerging opportunities to better understand and support more tasks via large-scale foundation models such as GPT-4[3] and DALL·E 3,[4] including offering conversational task assistance via chatbots such as ChatGPT.5 • Conversational experiences and generative AI: All of these advances, and others, have paved the way for the emergence of AI copilots, assistive agents that can help people tackle complex search tasks. [1] https://www.verifiedmarketresearch.com/product/task-management-softwaremarket/ [2] https://blogs.microsoft.com/blog/2023/02/07/reinventing-search-with-a-new-aipowered-microsoft-bing-and-edge-your-copilot-for-the-web/ [3] https://openai.com/gpt-4 [4] https://openai.com/dall-e-3 [5] https://openai.com/chatgpt

Navigating Complex Search Tasks with AI Copilots: Abstract and Taking Search to task

Authors:
(1) Aya Kherrour, Department of Information Engineering and Computer Science University of Trento;
(2) Marco Robol, Department of Information Engineering and Computer Science University of Trento;
(3) Marco Roveri, Department of Information Engineering and Computer Science University of Trento;
(4) Paolo Giorgini,  Department of Information Engineering and Computer Science University of Trento. 2 State of the art and related work Path planning is a relevant problem in autonomous agents, such as, self-driving cars, robots, unmanned aerial vehicles (UAVs), and unmanned ground vehicles (UGVs), in which the host agent deliberates its path by moving from one position to another while avoiding obstacles and respecting some constraints [19]. One of the path planning approaches that have been proposed to control the movement of these agent-based systems is search-based algorithms, with Dijkstra and its extension A* [5, 21], being the most popular and effective ones. Besides these, other search algorithms have been proposed in the literature, specifically to reduce reaction time, broadly classified as real-time or incremental search algorithms. Real-time search algorithms must find a solution in a limited time, while incremental search instead uses the previously obtained searches to speed up the search. Amongst the first class, Real-time A* (RTA*) and Learning real-time A* (LRTA*) [14] were some of the first algorithms to apply real-time heuristic search in path planning problems for moving agents. Both algorithms use heuristics to guide the search toward the goal, with RTA* storing the second-best f-values of the previous state as the best alternative to choose when backtracking from the current state. However, this may mislead the agent. Thereby, LRTA* overcomes this by storing the first best value rather than the second and learning from comparing the heuristic values of the adjacent states, thus preventing the algorithm from misleading the agent. Another optimized version of LRTA* is real-time adaptive A* (RTAA*) [12]. It first determines its local search space and then speeds up the search by updating the heuristics values of states. It was developed for stationary target search problems and it follows trajectories of smaller costs. Anytime repairing A* (ARA*) [15] is a variation of A* that has been designed to find suboptimal solutions fast and then improve them over time, which makes it a good algorithm for problems where finding an optimal solution is not mandatory or too expensive [15]. However, finding suboptimal solutions does not make it find the optimal solution [15]. Moving to incremental search algorithms, D* (Dynamic A*) is an incremental search algorithm used in real-time planning in robotics [20]. It is designed to react quickly to changes in the environment, by updating the nodes affected in the search tree rather than recomputing a new plan from scratch. D* has a main drawback that it requires a lot of memory to perform the search. LPA* (Lifelong Planning A*), an incremental version of A*. This algorithm is used in path planning or robot navigation in unknown terrain. It behaves just like A* in the first run, and then for the rest of subsequent searches it reuses the previous search thus reducing the number of examined nodes, which makes it fast. LPA* differs from D* in its search direction where it finds a path from the initial state to the initial goal state, therefore it does not fit in applications where the starting point may change over time. Another variant of D*, D* Lite, was developed based on LPA*, and is used for goal-directed path planning in unknown environments using the same idea as D*, however, it is a simple version of D* and produces effective results as the one delivered by D* as proven in [11]. While these heuristic search algorithms are numerous and diverse, it is important to emphasize that there are even more algorithms in the literature with new ones being developed, or existing ones being improved such as [2, 13, 7]. This variety of algorithms in the field emphasizes the complexity of the problem. Consequently, this variety of proposed algorithms presents a challenge; the wide number of these algorithms results in disparate performances in tasks such as path planning, making it difficult to select the optimal algorithms for a given task. Given the multitude of algorithms, studies have been done to compare the performance of RTS algorithms in path planning tasks such as [1] where authors have compared the performances of path planning algorithms using agents equipped with a sensor in both stationary and moving target settings to select the most appropriate algorithm. The obtained results were compared using various sensor ranges and angles, and the authors concluded that sensor range is an important parameter in selecting the algorithm, unlike the sensor angle. Therefore the most appropriate algorithm can be selected based on the sensor range and its priorities. However, the authors did not consider varying the environmental characteristics, which may influence the performance of the algorithms. Another study has been presented in [13], in which the authors also compared real-time and incremental heuristic search algorithms using an autonomous agent in a navigation task to know which class of heuristic search approach is better to be used depending on how informed the h-values are, and the search objective such as minimizing the sum of the search and action execution. The comparative analysis done in [1] considers only a static environment, neglecting the possible variations in the algorithm performance under different environmental characteristics. This limitation hampers us from creating a clear understanding of different search algorithms that could perform under different environmental characteristics, precisely in the context of path planning. Similarly, the study conducted in [13] restricts its investigation to only two algorithms each one from a different class i.e., real-time and incremental heuristic search. Even though it provides an insightful comparison, the study does not fully capture the breadth of available algorithms in these classes. Moreover, the study aimed to provide a recommendation on when to use each of the algorithm classes, but also does not investigate algorithm performances in diverse environmental characteristics. Consequently, considering the challenge posed by the presence of a wide range of search algorithms and the lack of a comprehensive comparative analysis under different environment settings, we propose to evaluate and analyze the performance of some search algorithms under different environment characteristics in the context of path planning, But first, we define the characteristics of the environment used, and through our experiments, we aim to provide a comprehensive evaluation of these algorithms followed by proposing our selection algorithm. This paper is available on arxiv under CC 4.0 license. Authors: (1) Aya Kherrour, Department of Information Engineering and Computer Science University of Trento; (2) Marco Robol, Department of Information Engineering and Computer Science University of Trento; (3) Marco Roveri, Department of Information Engineering and Computer Science University of Trento; (4) Paolo Giorgini,  Department of Information Engineering and Computer Science University of Trento. Authors: (1) Aya Kherrour, Department of Information Engineering and Computer Science University of Trento; (2) Marco Robol, Department of Information Engineering and Computer Science University of Trento; (3) Marco Roveri, Department of Information Engineering and Computer Science University of Trento; (4) Paolo Giorgini,  Department of Information Engineering and Computer Science University of Trento. 2 State of the art and related work Path planning is a relevant problem in autonomous agents, such as, self-driving cars, robots, unmanned aerial vehicles (UAVs), and unmanned ground vehicles (UGVs), in which the host agent deliberates its path by moving from one position to another while avoiding obstacles and respecting some constraints [19]. One of the path planning approaches that have been proposed to control the movement of these agent-based systems is search-based algorithms, with Dijkstra and its extension A* [5, 21], being the most popular and effective ones. Besides these, other search algorithms have been proposed in the literature, specifically to reduce reaction time, broadly classified as real-time or incremental search algorithms. Real-time search algorithms must find a solution in a limited time, while incremental search instead uses the previously obtained searches to speed up the search. Amongst the first class, Real-time A* (RTA*) and Learning real-time A* (LRTA*) [14] were some of the first algorithms to apply real-time heuristic search in path planning problems for moving agents. Both algorithms use heuristics to guide the search toward the goal, with RTA* storing the second-best f-values of the previous state as the best alternative to choose when backtracking from the current state. However, this may mislead the agent. Thereby, LRTA* overcomes this by storing the first best value rather than the second and learning from comparing the heuristic values of the adjacent states, thus preventing the algorithm from misleading the agent. Another optimized version of LRTA* is real-time adaptive A* (RTAA*) [12]. It first determines its local search space and then speeds up the search by updating the heuristics values of states. It was developed for stationary target search problems and it follows trajectories of smaller costs. Anytime repairing A* (ARA*) [15] is a variation of A* that has been designed to find suboptimal solutions fast and then improve them over time, which makes it a good algorithm for problems where finding an optimal solution is not mandatory or too expensive [15]. However, finding suboptimal solutions does not make it find the optimal solution [15]. Moving to incremental search algorithms, D* (Dynamic A*) is an incremental search algorithm used in real-time planning in robotics [20]. It is designed to react quickly to changes in the environment, by updating the nodes affected in the search tree rather than recomputing a new plan from scratch. D* has a main drawback that it requires a lot of memory to perform the search. LPA* (Lifelong Planning A*), an incremental version of A*. This algorithm is used in path planning or robot navigation in unknown terrain. It behaves just like A* in the first run, and then for the rest of subsequent searches it reuses the previous search thus reducing the number of examined nodes, which makes it fast. LPA* differs from D* in its search direction where it finds a path from the initial state to the initial goal state, therefore it does not fit in applications where the starting point may change over time. Another variant of D*, D* Lite, was developed based on LPA*, and is used for goal-directed path planning in unknown environments using the same idea as D*, however, it is a simple version of D* and produces effective results as the one delivered by D* as proven in [11]. While these heuristic search algorithms are numerous and diverse, it is important to emphasize that there are even more algorithms in the literature with new ones being developed, or existing ones being improved such as [2, 13, 7]. This variety of algorithms in the field emphasizes the complexity of the problem. Consequently, this variety of proposed algorithms presents a challenge; the wide number of these algorithms results in disparate performances in tasks such as path planning, making it difficult to select the optimal algorithms for a given task. Given the multitude of algorithms, studies have been done to compare the performance of RTS algorithms in path planning tasks such as [1] where authors have compared the performances of path planning algorithms using agents equipped with a sensor in both stationary and moving target settings to select the most appropriate algorithm. The obtained results were compared using various sensor ranges and angles, and the authors concluded that sensor range is an important parameter in selecting the algorithm, unlike the sensor angle. Therefore the most appropriate algorithm can be selected based on the sensor range and its priorities. However, the authors did not consider varying the environmental characteristics, which may influence the performance of the algorithms. Another study has been presented in [13], in which the authors also compared real-time and incremental heuristic search algorithms using an autonomous agent in a navigation task to know which class of heuristic search approach is better to be used depending on how informed the h-values are, and the search objective such as minimizing the sum of the search and action execution. The comparative analysis done in [1] considers only a static environment, neglecting the possible variations in the algorithm performance under different environmental characteristics. This limitation hampers us from creating a clear understanding of different search algorithms that could perform under different environmental characteristics, precisely in the context of path planning. Similarly, the study conducted in [13] restricts its investigation to only two algorithms each one from a different class i.e., real-time and incremental heuristic search. Even though it provides an insightful comparison, the study does not fully capture the breadth of available algorithms in these classes. Moreover, the study aimed to provide a recommendation on when to use each of the algorithm classes, but also does not investigate algorithm performances in diverse environmental characteristics. Consequently, considering the challenge posed by the presence of a wide range of search algorithms and the lack of a comprehensive comparative analysis under different environment settings, we propose to evaluate and analyze the performance of some search algorithms under different environment characteristics in the context of path planning, But first, we define the characteristics of the environment used, and through our experiments, we aim to provide a comprehensive evaluation of these algorithms followed by proposing our selection algorithm. This paper is available on arxiv under CC 4.0 license. This paper is available on arxiv under CC 4.0 license. available on arxiv

Evaluating Path Planning Algorithms: Real-Time vs. Incremental Search

Fundamentals of Graph Theory A graph is a mathematical structure used to model pairwise relationships between objects. A graph consists of a set of vertices (or nodes) and a set of edges, each of which connects a pair of vertices. This allows the representation of various data as networks, including road networks, social connections, relationships between different business processes, and more. Graphs can be directed or undirected. In a directed graph, edges have a direction indicating from one vertex to another, whereas in an undirected graph, edges have no directionality. 0 ------ 1
     / \       | \
    /   \      |  \
   2 --- 3     |   4
    \   / \    |  /
     \ /   \   | /
      5 ------ 6 What is a tree in the context of graph theory? In the context of graph theory, a tree is a special case of a graph. It is an undirected graph that is connected and acyclic. Trees exhibit several interesting properties, such as there being exactly one path between any two vertices. This makes them ideal for use in data structures such as search trees, parsing trees, process management structures, and more. 1
       / \
      2   3
     / \   \
    4   5   6
       /
      7 In problem-solving, we may also encounter binary trees. A binary tree is a hierarchical data structure in the form of a tree, consisting of nodes (vertices), where each node has at most two children: a left child and a right child. Each node contains some data (value) and references (pointers) to its child nodes. Key characteristics of a binary tree: : This is the topmost node of the tree, from which the entire structure originates. A binary tree has exactly one root. Root : Children Each node can have a maximum of two children: a left child and a right child. : The node positioned to the left of the current node. Left Child : The node positioned to the right of the current node. Right Child : Leaves These are nodes in the binary tree that do not have any children (i.e., their and pointers are ). left right null : Height of the Tree The height of a tree is defined as the maximum number of levels from the root to the furthest leaf node. An empty tree (with no nodes) has a height of 0, and a tree with only one node (just the root) has a height of 1. : Level of a Node The level of a node is determined by the number of edges on the path from the root to that node. The root node is at level 0. A binary tree is a fundamental data structure used in computer science and programming for a variety of applications, including binary search trees, expression trees, binary heaps, and more. Understanding the properties and operations of binary trees is essential for implementing efficient algorithms and solving various computational problems. It's time to look at some examples. Graph To begin with, I'd like to suggest implementing a basic graph construction first, and then we'll see how we can use it in problems. We'll create a simple representation of a graph using adjacency lists. import java.util.*;

class Graph {

    private int V; // Number of vertices
    private LinkedList<Integer>[] adj; // Adjacency list representation

    Graph(int v) {
        V = v;
        adj = new LinkedList[v];
        for (int i = 0; i < v; ++i) {
            adj[i] = new LinkedList();
        }
    }

    void addEdge(int v, int w) {
        adj[v].add(w); // Add w to v's adjacency list
        adj[w].add(v); // Add v to w's adjacency list (for undirected graph)
    }

    public static void main(String[] args) {
        Graph graph = new Graph(5);
        graph.addEdge(0, 1);
        graph.addEdge(0, 4);
        graph.addEdge(1, 2);

    }
} To work with graphs, we use just two important algorithms: DFS and BFS. Let's look at them and go through the theory. Depth-First Search (DFS) DFS (Depth-First Search) is an algorithm for traversing or searching in a graph or tree. It starts by choosing an initial vertex and then moves to its adjacent vertices. Once a vertex is reached that has no unvisited neighbours, the algorithm backtracks and continues exploring other branches. The main idea of DFS is to go as deep as possible into the data structure before backtracking. Key steps of DFS: Visit the current vertex. Recursively call DFS for each adjacent unvisited vertex. DFS can be used for various tasks such as finding paths between vertices, determining graph connectivity, topological sorting, and others. Let’s check the problem: .  We realized that we can solve this using a graph and DFS, but how? Instead of simple rooms, we have a graph here. We can start at position 0 without any keys, but we can move further. In our problem, we need to track the rooms we have visited. Therefore, we create a boolean array and mark room zero as visited. https://leetcode.com/problems/keys-and-rooms/ boolean[] seen = new boolean[rooms.size()];
 seen[0] = true; In Java, we can use the class to help maintain the order of our elements (Last-In-First-Out, or LIFO). We can push our nodes onto the stack. Stack while (!stack.isEmpty()) {
   int curruentNode = stack.pop(); 
   for (int n: rooms.get(curruentNode))
       if (!seen[n]) { 
           seen[n] = true; 
           stack.push(n); 
        }
   }
} The final step is to check if there are any unvisited rooms left. If we find an unvisited room, we return , indicating that not all nodes have been visited. Otherwise, we return , indicating that we have visited all nodes. false true class Solution {

    public boolean canVisitAllRooms(List<List<Integer>> rooms) {
        boolean[] seen = new boolean[rooms.size()];
        seen[0] = true;

        Stack<Integer> stack = new Stack();
        stack.push(0);

        while (!stack.isEmpty()) {
            int curruentNode = stack.pop(); 

            for (int n: rooms.get(curruentNode))
                if (!seen[n]) { 
                    seen[n] = true; 
                    stack.push(n); 
                }
        }

        for (boolean v: seen) {
            if (!v) {
                return false;
            }
        }
         
        return true;
    }
} Breadth-First Search (BFS) BFS (Breadth-First Search) is an algorithm for traversing or searching in a graph or tree. It starts by choosing an initial vertex and explores all of its neighbours at the current level before moving to neighbours of neighbours in the next level. In other words, it processes all adjacent vertices of the current vertex before moving on to adjacent vertices of those vertices and so on. Key steps of BFS: Enqueue the initial vertex into a queue. While the queue is not empty, dequeue a vertex from the front of the queue. Visit the current vertex and enqueue all its unvisited adjacent vertices to the back of the queue. Repeat steps 2-3 until the queue is empty. BFS is often used for finding the shortest path in unweighted graphs, checking graph connectivity, level-order traversal in trees, and other applications where it's necessary to process all vertices of a specific level before moving to the next level. Let’s check this one: As we can see, we already have a class TreeNode (we are near the topic, yes). https://leetcode.com/problems/same-tree/ public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
       this.val = val;
       this.left = left;
       this.right = right;
   }
} And what do we need to do? We should use recursion and check all nodes. Let’s start with checking nodes: boolean left = isSameTree(p.left, q.left);
boolean right = isSameTree(p.right, q.right);

boolean result = left && right; But we need to stop the recursion call and for the case, we should add base cases: all nodes are null if (p == null && q == null) return true; One node isn’t null if (p == null || q == null) return false; Values aren’t equels if (p.val != q.val) return false; And finally, we’ll add the return statement: /**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if (p == null && q == null) return true;
        if (p == null || q == null) return false;
        if (p.val != q.val) return false;

        boolean left = isSameTree(p.left, q.left);
        boolean right = isSameTree(p.right, q.right);
        return left && right;
    }
} Conclusion Graphs and Trees: Graphs and trees are important data structures in computer science used for modelling and analyzing complex relationships between objects. They find wide applications in various fields including algorithms, network modelling, databases, bioinformatics, and more. Key Characteristics of Graphs and Trees: Graphs can be directed or undirected, contain cycles or be acyclic. Trees are a special case of graphs that are connected and acyclic. In graphs, each element is called a vertex, and the connections between vertices are called edges. DFS (Depth-First Search): Allows traversal of a graph or tree in a depth-first manner. Uses a stack for the recursive traversal of vertices. Applied for pathfinding, connectivity checking, topological sorting, and other tasks. BFS (Breadth-First Search): Allows traversal of a graph or tree in a breadth-first manner. Uses a queue for systematic exploration of neighbours at each level. Applied for shortest path finding, connectivity checking, level-order traversal, and other tasks.

Solving LeetCode Problems Using Graph Theory

Read the first part of this article here: Unveiling a 35-Year-Old Vulnerability in nix libX11: Part 1 My team recently discovered two security vulnerabilities in X.Org libX11, the widely popular graphics library – (with a high NVD severity ). These vulnerabilities cause a denial-of-service and remote code execution. X11’s latest versions contain fixes for these vulnerabilities. CVE-2023-43786 and CVE-2023-43787 CVSS 7.8 The team constantly monitors open-source projects to find new vulnerabilities and malicious packages and shares them with the wider community to help improve their overall security posture. This 2-part blog series provides details of the inner workings of the vulnerable Xpm file format and deep-dives into exploiting these vulnerabilities. This post provides a walkthrough for achieving code execution by exploiting CVE-2023-43787 on a Debian machine. RCE vulnerability – CVE-2023-43787 CVE-2023-43787 is a heap-based buffer overflow vulnerability that occurs when parsing a malformed XPM image, which can be exploited to achieve remote code execution. Fix commit: The vulnerability was fixed in libX11 version 1.8.7, in commit . 7916869d Technical analysis The root cause of CVE-2023-43787 lies in , a libX11 function that is used to create an object, representing an off-screen image that can be manipulated and displayed on the screen. With , developers can efficiently manage off-screen images in X11 applications, specifying parameters like width, height, depth, and format to customize image attributes. XCreateImage XImage XCreateImage package org.example;

import java.io.IOException;
import org.yaml.snakeyaml.LoaderOptions;
import org.yaml.snakeyaml.constructor.*;
import org.yaml.snakeyaml.Yaml;

public class Main {
    public static void main(String[] args) throws IOException {
        LoaderOptions options = new LoaderOptions();
        Yaml yaml = new Yaml(new Constructor(options));
        String strYaml = Files.readString(args[0]); 
        String parsed = yaml.load(strYaml);
    }
} XImage *XCreateImage (
    register Display *dpy,
    register Visual *visual,
    unsigned int depth,
    int format,
    int offset,
    char *data,
    unsigned int width,
    unsigned int height,
    int xpad,
    int image_bytes_per_line)
        /*How many bytes between a pixel on one line and the pixel with the same X coordinate on the next line? 0 means 	  XCreateImage can calculate it.*/
{
    register XImage *image;
    int bits_per_pixel = 1;
    int min_bytes_per_line;


    .......
    if (format == ZPixmap)
    {
       bits_per_pixel = _XGetBitsPerPixel(dpy, (int) depth); [1]
    }

    image->xoffset = offset;
    image->bitmap_pad = xpad;
    image->depth = depth;
    image->data = data;
    /*
     * compute per line accelerator.
     */
    {
    if (format == ZPixmap)
        min_bytes_per_line =                              [2]
           ROUNDUP((bits_per_pixel * width), image->bitmap_pad);
    else
        min_bytes_per_line =
            ROUNDUP((width + offset), image->bitmap_pad);
    }
     if (image_bytes_per_line == 0) {
        image->bytes_per_line = min_bytes_per_line;
    } else if (image_bytes_per_line < min_bytes_per_line) { Xfree(image); return NULL; } else { image->bytes_per_line = image_bytes_per_line;     [3]
    }
    ....... When the format is it calculates [1], and then uses the result to calculate the [2]. ZPixmap bits_per_pixel min_bytes_per_line It is then set to the attribute of the XImage [3]. bytes_per_line There is no validation on the of the image, and so the calculation [2] exceeds the capacity of (a 4-byte integer), causing an overflow. width min_bytes_per_line is called from libXpm’s function, defined in : XCreateImage CreateXImage create.c /*
 * Create an XImage with its data
 */
static int
CreateXImage(
    Display	 *display,
    Visual	 *visual,
    unsigned int  depth,
    int		  format,
    unsigned int  width,
    unsigned int  height,
    XImage	**image_return)
{
    ...

    /* then create the XImage with data = NULL and bytes_per_line = 0 */
    *image_return = XCreateImage(display, visual, depth, format, 0, 0,
                     width, height, bitmap_pad, 0);                       [1]
    if (!*image_return)
    return (XpmNoMemory);

#if !defined(FOR_MSW) && !defined(AMIGA)
    if (height != 0 && (*image_return)->bytes_per_line >= INT_MAX / height) {
        XDestroyImage(*image_return);
        *image_return = NULL;
        return XpmNoMemory;
    }
    /* now that bytes_per_line must have been set properly alloc data */
    if((*image_return)->bytes_per_line == 0 ||  height == 0) {
        XDestroyImage(*image_return);
        *image_return = NULL;
        return XpmNoMemory;
    }
    (*image_return)->data =
        (char *) XpmMalloc((*image_return)->bytes_per_line * height);     [2]

    ...
} On [1] there’s the call to the vulnerable function that calculates the size needed to be allocated. XCreateImage On [2] there’s an allocation that uses the overflown property of the XImage, which will then proceed to allocate a smaller buffer than needed. bytes_per_line is called from the function [1], triggered when libXPM is asked to parse an XPM file: CreateXImage xpmParseDataAndCreate /*
 * This function parses an Xpm file or data and directly create an XImage
 */
int
xpmParseDataAndCreate(
    Display		 *display,
    xpmData		 *data,
    XImage		**image_return,
    XImage		**shapeimage_return,
    XpmImage		 *image,
    XpmInfo		 *info,
    XpmAttributes	 *attributes)
{
    


   .....

    /*
     * parse the header
     */
    ErrorStatus = xpmParseHeader(data);
    if (ErrorStatus != XpmSuccess)
        return (ErrorStatus);

    /*
     * read values
     */
    ErrorStatus = xpmParseValues(data, &width, &height, &ncolors, &cpp,
                 &x_hotspot, &y_hotspot, &hotspot,
                 &extensions);
    if (ErrorStatus != XpmSuccess)
        return (ErrorStatus);

   .........

    /* now create the ximage */
    if (image_return) {
        ErrorStatus = CreateXImage(display, visual, depth,
                       (depth == 1 ? bitmap_format : ZPixmap),
                       width, height, &ximage);                       [1]
    if (ErrorStatus != XpmSuccess)
        RETURN(ErrorStatus);
        ......... Exploiting CVE-2023-43787 to achieve code execution Let’s discuss all the basic exploitation pieces before moving on to code execution. Piece 1 – Controlling the allocation size The size of the allocation that is overflown, is decided from the width of the Xpm image. As we discussed in the previous blog post, the width can be easily manipulated by modifying this information in the Xpm header. So, we have control over the allocation size (heap bin size). We now want to find out how to control the overflown data. Piece 2 – Controlling the overflowed buffer data The overflown data is , which is the pointer to the image data. ximage->data Piece 3 – Controlling the overflow size Controlling the size of the overflow itself (anything that comes after the allocated buffer). This is easily achieved as Xpm reads the image pixels from the file as long as there are pixels to read. The function calls the function with the ximage object [1]: xpmParseDataAndCreate ParseAndPutPixels .....
    /*
     * read pixels and put them in the XImage
     */
    ErrorStatus = ParseAndPutPixels(
#ifdef FOR_MSW
                    display,
#endif
                    data, width, height, ncolors, cpp,
                    colorTable, &hashtable,
                    ximage, image_pixels,                      [1]
                    shapeimage, mask_pixels);
..... The ParseAndPutPixels function loops over the image pixels and fills the ximage->data: .....
        for (x = 0; x < width; x++) {                                  [1]
            int c = xpmGetC(data);                                      [2]
..... On [1], we can see the loop reads data according to , which is very big (as we needed to overflow the size). On [2], a call to the macro is made: width xpmGetC #define xpmGetC(mdata) \
    ((!mdata->type || mdata->type == XPMBUFFER) ? \
    (*mdata->cptr++) : (getc(mdata->stream.file))) Multiple Avenues of Exploitation After going over the basic exploitation pieces, let’s see which primitives can be triggered by overwriting different heap chunks. Specifically, we will examine the case of exploitation when the vulnerability is triggered through the CLI utility (for example, using the simple command-line . These exploitation avenues can be extrapolated to other vulnerable cases as well (ex. exploiting code that uses the library’s vulnerable functions) – sxpm sxpm attacker_image.xpm) Option #1 – Function pointer overwrite – Code Execution #1 Due to time constraints, we opted to switch from a 64-bit binary to 32-bit for this exploitation (which would have required more research into the pixel data). Exploitation with Option #1 will focus on Debian 12 32-bit, but the ideas apply similarly to 64-bit. If we set our overflown bin to 428 bytes ( bin), something interesting happens. 0x1b0 (Display) pointer, which is later used when freeing the XPM colors. We managed to overwrite the dpy The structure size is 2,412 bytes – allocated on the large bin. Display 0x970 Specifically, we overwrite the pointer in this structure: lock_fns struct _XLockPtrs *lock_fns; /* pointers to threads functions */ The libX11 code dereferences this pointer and jumps to the address inside it – int
XFreeColors(
    register Display *dpy,
    Colormap cmap,
    unsigned long *pixels, /* LISTofCARD32 */
    int npixels,
    unsigned long planes) /* CARD32 */
{
    register xFreeColorsReq *req;
    register long nbytes;

    LockDisplay(dpy);                                                          [1]
    GetReq(FreeColors, req);
    req->cmap = cmap;
    req->planeMask = planes;

    /* on the VAX, each pixel is a 32-bit (unsigned) integer */
    req->length += npixels;

    nbytes = npixels << 2;		/* watch out for macros... */
    Data32 (dpy, (long *) pixels, nbytes);
    UnlockDisplay(dpy);
    SyncHandle();
    return 1;
} on [1] is a macro: LockDisplay /* used everywhere, so must be fast if not using threads */
#define LockDisplay(d)	     if ((d)->lock_fns) (*(d)->lock_fns->lock_display)(d) As can be seen from the macro, when we overwrite the pointer, it will be dereferenced twice and run the resulting pointer, leading to code execution. dpy After checking the offset of in our payload, and setting its pointer to a predictable address in the 32-bit memory space of (e.g. ), we have total control over EIP. dpy->lock_fns sxpm 0x409774 Option #2 – Limited Write-What-Where Another possible primitive is to overwrite a pointer to the File Descriptor (in an structure). This happens when we allocate 136 bytes (on the fastbin). xpmData 0x90 Inside the loop that reads each character from the XMP file, it uses it and reads a character. The structure: xpmData This is a limited relative write-what-where. We can write 4 bytes (3 controlled bytes + 1 byte fixed ’00’), into a relative address like 0x5555{00414243}. This can be seen here in [1] and [2]: static int
ParseAndPutPixels(
#ifdef FOR_MSW
    Display		*dc,
#endif
    xpmData		*data,
    unsigned int	 width,
    unsigned int	 height,
    unsigned int	 ncolors,
    unsigned int	 cpp,
    XpmColor		*colorTable,
    xpmHashTable	*hashtable,
    XImage		*image,
    Pixel		*image_pixels,
    XImage		*shapeimage,
    Pixel		*shape_pixels)
{
    unsigned int a, x, y;

    switch (cpp) {

    case (1):				/* Optimize for single character
                     * colors */
    {
        unsigned short colidx[256];
#ifdef FOR_MSW
        HDC shapedc;
        HBITMAP obm, sobm;

        if ( shapeimage ) {
            shapedc = CreateCompatibleDC(*dc);
            sobm = SelectObject(shapedc, shapeimage->bitmap);
        } else {
            shapedc = NULL;
        }
        obm = SelectObject(*dc, image->bitmap);
#endif
        if (ncolors > 256)
            return (XpmFileInvalid);
        bzero((char *)colidx, 256 * sizeof(short));
        for (a = 0; a < ncolors; a++) {
            colidx[(unsigned char)colorTable[a].string[0]] = a + 1;
        }

        for (y = 0; y < height; y++) {
            xpmNextString(data);
            for (x = 0; x < width; x++) { int c = xpmGetC(data); [1] if (c > 0 && c < 256 && colidx[c] != 0) {
#ifndef FOR_MSW
                    XPutPixel(image, x, y, image_pixels[colidx[c] - 1]); [2]
                    if (shapeimage) {
                        XPutPixel(shapeimage, x, y,
                            shape_pixels[colidx[c] - 1]);
                    }
#else
                    SetPixel(*dc, x, y, image_pixels[colidx[c] - 1]);
                    if (shapedc) {
                        SetPixel(shapedc, x, y, shape_pixels[colidx[c] - 1]);
                    }
#endif
                }else {
                    return (XpmFileInvalid);
                }
            }
        }
        ...... Option #3 – Code Execution Alternative When allocating a chunk of 136 bytes (which gets allocated on the 0x90 heap fastbin), we can overwrite an object: _XLockInfo The object: structure is 192 bytes long, so it gets allocated on the bin. _XLockInfo dpy->lock 0xd0 As can be seen from the backtrace, we overwrote the that gets used in the function, which then gets accessed at the start of the function (using the register): mutex __pthread_mutex_lock rdi int
__pthread_mutex_lock (pthread_mutex_t *mutex)
{
  unsigned int type = PTHREAD_MUTEX_TYPE_ELISION (mutex);
  .....
}


#define PTHREAD_MUTEX_TYPE_ELISION(m) \
  ((m)->__data.__kind & (127|PTHREAD_MUTEX_ELISION_NP)) This is called when freeing the colors structure in , which calls the function. xpmParseDataAndCreate XFreeColors After the Mutex is accessed, the data is then used in the function: _XDisplayLockWait static void _XDisplayLockWait(
    Display *dpy)
{
    xthread_t self;

    while (dpy->lock->locking_level > 0) {
        self = xthread_self();
        if (xthread_equal(dpy->lock->locking_thread, self))
            break;
        ConditionWait(dpy, dpy->lock->cv);
    }
} The is a macro: ConditionWait #define ConditionWait(d,c) if ((d)->lock) \
    (*(d)->lock->condition_wait)(c, (d)->lock->mutex) It dereferences the lock object and then . executes it as a function This can be used as another code execution primitive. Option #4 – Another Write-What-Where (dead end in the case of sxpm) Another primitive will overwrite the structure (which is 136 bytes long – bin). XImage 0x90 This is when allocating a chunk of 16 bytes (on the fastbin). 0x20 Our image data ( ) is allocated just before the contents, and so we overwrite the pointer with our data to create this primitive. ximage->data XImage ximage->data This can be an absolute write-what-where primitive. Again, switching from a 64-bit binary to 32-bit. The rest of the exploitation will focus on Debian 12 32-bit. The structure on 32-bit is 88 bytes long. Let’s try changing the size of our overflowing buffer to 88: Contrary to the 64-bit primitive, on 32-bit our overflowing buffer is allocated after the target object. XImage XImage The allocation will be adjacent to the structure, but in the reverse order (a bit after the address). ximage->data XImage XImage Therefore – our overflown buffer will not be behind our target XImage structure, and our exploitation won’t work. Using debug prints: Now, let’s groom the heap using an allocation primitive. There are 4 pixel allocations using the following calculation: sizeof(Pixel) * ncolors On 32-bit, equals 4. sizeof(Pixel) Let’s change the file to have only 22 colors, to achieve our needed 88 bytes (22*4). Changing to 22 colors will still not help us overwrite the XImage object. Using debug prints: In the case of , this led us to a dead-end (It would be better to create a new exploitation primitive) however this chain of primitives might be relevant in different exploitation scenarios. sxpm In which cases can CVE-2023-43787 be triggered? Any application or library that uses libXPM to parse externally-supplied XPM images, can trigger CVE-2023-43787 with the use of the following vulnerable libXPM exported functions: XpmCreateImageFromXpmImage
XpmCreateImageFromBuffer
XpmCreateImageFromData
XpmCreatePixmapFromXpmImage
XpmCreatePixmapFromBuffer
XpmCreatePixmapFromData
XpmReadFileToImage
XpmReadFileToPixmap For example, is a CLI utility that is used to display XPM images on the screen. The vulnerability can be triggered via with a simple command line – sxpm sxpm sxpm attacker_image.xpm This utility calls the vulnerable libXpm function, which then calls the vulnerable libX11 functions then . xpmCreatePixmapFromImage XPutImage PutSubImage

Uncovering and Exploiting a 35-Year-Old Vulnerability, *nix libX11: Part 2 

As part of learning the Rust ecosystem, I dedicated the last few days to error management. Here are my findings. Error management 101 The describes the basics of error management. The language separates between recoverable errors and unrecoverable ones. Rust book Unrecoverable errors benefit from the macro. When panics, it stops the program. Recoverable errors are much more enjoyable. panic!() Rust Rust uses the monad, which stems from Functional Programming. Opposite to exceptions in other languages, FP mandates to return a structure that may contain the requested value the error. The language models it as an with generics on each value: Either either or enum #[derive(Copy, PartialEq, PartialOrd, Eq, Ord, Debug, Hash)]
pub enum Result<T, E> {
    Ok(T),
    Err(E),
} Because Rust manages completeness of matches, matching on enforces that you handle both branches: Result match fn_that_returns_a_result() {
    Ok(value) => do_something_with_value(value)
    Err(error) => handle_error(error)
} If you omit one of the two branches, compilation fails. The above code is safe if unwieldy. But Rust offers a full-fledged API around the struct. The API implements the monad paradigm. Result Propagating results Propagating results and errors is one of the main micro-tasks in programming. Here's a naive way to approach it: #[derive(Debug)]
struct Foo {}
#[derive(Debug)]
struct Bar { foo: Foo }
#[derive(Debug)]
struct MyErr {}

fn main() {
    print!("{:?}", a(false));
}

fn a(error: bool) -> Result<Bar, MyErr> {
    match b(error) {                                   //1
        Ok(foo) => Ok(Bar{ foo }),                     //2
        Err(my_err) => Err(my_err)                     //3
    }
}

fn b(error: bool) -> Result<Foo, MyErr> {
    if error {
        Err(MyErr {})
    } else {
        Ok(Foo {})
    }
} Return a which contains a or a Result Bar MyErr If the call is successful, unwrap the value, wrap it again, and return it Foo If it isn't, unwrap the error, wrap it again, and return it The above code is a bit verbose, and because this construct is quite widespread, Rust offers the operator: ? When applied to values of the type, it propagates errors. If the value is , then it will return from the enclosing function or closure. If applied to , then it will unwrap the value to evaluate to . Result<T, E> Err(e) Err(From::from(e)) Ok(x) x -- The question mark operator We can apply it to the above function: a fn a(error: bool) -> Result<Bar, MyErr> {
    let foo = b(error)?;
    Ok(Bar{ foo })
} The trait Error Note that enforces no bounds on the right type, the "error" type. However, Rust provides an trait. Result<T, E> Error Two widespread libraries help us manage our errors more easily. Let's detail them in turn. Implement Error trait with thiserror In the above section, I described how a could implement the trait. However, doing so requires quite a load of boilerplate code. The crate provides macros to write the code for us. Here's the documentation sample: struct Error thiserror #[derive(Error, Debug)]                                                   //1
pub enum DataStoreError {
    #[error("data store disconnected")]                                   //2
    Disconnect(#[from] io::Error),
    #[error("the data for key `{0}` is not available")]                   //3
    Redaction(String),
    #[error("invalid header (expected {expected:?}, found {found:?})")]   //4
    InvalidHeader {
        expected: String,
        found: String,
    }
} Base macro Error Static error message Dynamic error message, using field index Dynamic error message, using field name helps you generate your errors. thiserror Propagate Result with anyhow The crate offers several features: anyhow A custom struct. I will focus on this one anyhow::Result<T> A way to attach context to a function returning an anyhow::Result<T> Additional backtrace environment variables Compatibility with thiserror A macro to create errors on the fly Result propagation has one major issue: functions signature across unrelated error types. The above snippet used a single enum, but in real-world projects, errors may come from different crates. Here's an illustration: #[derive(thiserror::Error, Debug)]
pub struct ErrorX {}                                                      //1
#[derive(thiserror::Error, Debug)]
pub struct ErrorY {}                                                      //1

fn a(flag: i8) -> Result<Foo, Box<dyn std::error::Error>> {               //2
    match flag {
        1 => Err(ErrorX{}.into()),                                        //3
        2 => Err(ErrorY{}.into()),                                        //3
        _ => Ok(Foo{})
    }
} Two error types, each implemented with a different with struct thiserror Rust needs to know the size of the return type at compile time. Because the function can return either one or the other type, we must return a fixed-sized pointer; that's the point of the construct. For a discussion on when to use compared to other constructs, please read this . Box<dyn Error> Box StackOverflow question To wrap the struct into a , we rely on the method Box into() With , we can simplify the above code: anyhow fn a(flag: i8) -> anyhow::Result<Foo> {
    match flag {
        1 => Err(ErrorX{}.into()),
        2 => Err(ErrorY{}.into()),
        _ => Ok(Foo{})
} With the trait, we can improve the user experience with additional details. Context The method is evaluated lazily, while the is evaluated eagerly. with_context() context() Here's how you can use the latter: fn a(flag: i8) -> anyhow::Result<Bar> {
    let foo = b(flag).context(format!("Oopsie! {}", flag))?;              //1
    Ok(Bar{ foo })
}

fn b(flag: i8) -> anyhow::Result<Foo> {
    match flag {
        1 => Err(ErrorX{}.into()),
        2 => Err(ErrorY{}.into()),
        _ => Ok(Foo{})
    }
} If the function fails, print the additional error message with the value Oopsie! flag Conclusion Rust implements error handling via the Either monad of FP and the enum. Managing such code in bare Rust requires boilerplate code. The crate can easily implement the trait for your structs while simplifies function and method signatures. Result thiserror Error anyhow To go further: Rust error handling The Error trait anyhow crate thiserror crate What is the difference between context and with_context in anyhow? Error handling across different languages A retrospective on Errors Management: where do we go from here? Originally published at on February 11th, 2024 A Java Geek

Stories, News & Mentions about BACKTRACEIO

Backtraceio’s Stories on HackerNoon