LLMs can iteratively design, implement, and debug code with external tools!

Here we explore how large language models can iteratively design, code, and debug their own proposed code solutions while using an external tool like a Python interpreter. This allows LLMs to accurately code and showcases the model’s capabilities in self-evaluation, verification using external tools, and reasoning using working memory.

The following features and prompting techniques are being used:

• Design before implementing: Encouraging the agent to design the solution and test scenarios before the implementation phase ensures that the code is built on a strong foundation.
• Step-by-Step Reasoning: Requesting the agent to use step-by-step reasoning for various stages, such as designing the solution, calculating the expected output of test cases, and brainstorming required changes promotes critical thinking and reasoning leading to lesser mistakes.
• Brainstorming Required Changes : After comparing the terminal output with the expected output, the agent assesses any discrepancies and brainstorms necessary changes required for not only the implementation but the test cases as well. This involves identifying the root cause of the issue and determining the best course of action to rectify it.
• Working Memory : The agent is provided with working memory that allows for the iterative refinement of plans, solutions, and code. By maintaining only a single copy of the actual stages and updating previous stages when necessary, the agent conserves valuable and expensive context length.
• External Tool Integration (Python Interpretter) : The ability to run the implementation and test code in an external python interpreter, greatly enhances the coding assistant’s capabilities. By incorporating external resources, the agent can verify and validate its code more effectively, leading to more accurate and efficient results.
• Self-Paraphrasing : Encouraging the agent to repeat and distill information into the “Expected Output” section helps the agent retain essential information. This aids in better matching when comparing the actual output from the terminal and expected output, allowing the agent to identify discrepancies more effectively.
• Breaking Down the Process : Dividing the entire process into smaller, more manageable steps makes it easier for the agent to focus on individual aspects of the task.
• Tagging : Assigning a title or trigger statement and an END tag to each stage helps maintain structure and distinguish each stage of the process.

The system prompt given to the agent:

As a Python coding assistant, your task is to provide an accurate and optimal solution to a coding problem. To accomplish this, follow these steps:

Solution Design:
Step 1: Say "Proposed Solution". Then brainstorm and design the solution. 
Step 2: Say "Implementation". Then implement the proposed solution in Python.

Testing and Debugging:
Step 1: Say "Testing Scenarios". Then design all possible testing scenarios, making sure to include all possible edge cases. For each test scenario, also find the expected output step by step with actual examples. 

Use the following format:
<test description>
<input>
<the step by step reasoning for expected output>
<expected output>

Step 2: Say "Testing code". In python write the necessary test cases with the above examples and expected outputs as print statements using the format:

print("brief test name", test) # expected output

You can print all the necessary output to help identify failure cases and debug. 

Step 3: Say "Expected Terminal Output". Write down the exact expected output, this can then be used to check if all test cases have passed later. 

Step 4: Say "Please run the above test cases.". This will trigger running your tests.

Step 5: The user will execute the testing code and share the output from the terminal, including any errors that show up.

Now, you need to iteratively revise your answer by following these steps:

Step 6: Use the output to debug your code if it fails. Additionally, re-verify if the test cases are correct. 

If the implementation is incorrect:
-Say "Implementation Changes:". Then briefly brainstorm step by step and mention what changes need to be performed.
-Say "Revised Implementation" and then propose the revised implementation. The previous solution in the history will automatically be replaced by the string "Implementation has been updated". 

Similarly, if the test case is incorrect:
-Say "Test Changes:" and mention what is going to be revised. 
-Say "Revised testing code" and propose the revised test cases. Your previous test cases in history will be automatically replaced by the string "Test cases have been updated". 

Then, go back to step 3.

Step 6: Once the code works as expected, share the final updated code with the user after saying "Here is the final implementation:".

Remember: For all the steps please label the end of each step with <END> tag. This will help parse and extract the code. 

Example from GPT-3.5 Turbo:

User:

Now solve the following task:

from typing import List
def separate_paren_groups(paren_string: str) -> List[str]: 
""" Input to this function is a string containing multiple groups of nested parentheses. Your goal is to separate those group into separate strings and return the list of those. Separate groups are balanced (each open brace is properly closed) and not nested within each other Ignore any spaces in the input string. >>> separate_paren_groups('( ) (( )) (( )( ))') ['()', '(())', '(()())'] 
""" 

Assistant:

Proposed Solution:

1. Create an empty list to store the separate groups of parentheses.
2. Create a variable to store the current group of parentheses.
3. Create a variable to store the count of open parentheses.
4. Iterate through each character in the input string.
5. If the character is an open parenthesis, increment the count of open parentheses and add the character to the current group.
6. If the character is a closing parenthesis, decrement the count of open parentheses and add the character to the current group.
7. If the count of open parentheses is 0, append the current group to the list of separate groups and reset the current group.
8. Ignore any spaces in the input string.
9. Return the list of separate groups.

Implementation: 

def separate_paren_groups(paren_string: str) -> List[str]:
    separate_groups = []
    current_group = ''
    open_paren_count = 0
    
    for char in paren_string:
        if char == ' ':
            continue
        elif char == '(':
            open_paren_count += 1
            current_group += char
        elif char == ')':
            open_paren_count -= 1
            current_group += char
        if open_paren_count == 0:
            separate_groups.append(current_group)
            current_group = ''
    
    return separate_groups

Assistant:

Testing Scenarios:

1. Test with one group of parentheses:
Input: '(())'
Expected Output: ['(())']

2. Test with multiple groups of parentheses:
Input: '()(()())'
Expected Output: ['()', '(()())']

3. Test with multiple groups of nested parentheses:
Input: '((()))(())'
Expected Output: ['((()))', '()']

4. Test with extra spaces:
Input: '( ) (( )) (( )( ))'
Expected Output: ['()', '(())', '(()())']

5. Test with no parentheses:
Input: 'hello world'
Expected Output: []

6. Test with only one parenthesis:
Input: '('
Expected Output: []

7. Test with unbalanced parentheses:
Input: '()((())'
Expected Output: []

8. Test with unbalanced parentheses:
Input: '())()'
Expected Output: []

9. Test with empty string:
Input: ''
Expected Output: []

Testing code:

print("Test case 1: ", separate_paren_groups('(())')) # ['(())']
print("Test case 2: ", separate_paren_groups('()(()())')) # ['()', '(()())']
print("Test case 3: ", separate_paren_groups('((()))(())')) # ['((()))', '()']
print("Test case 4: ", separate_paren_groups('( ) (( )) (( )( ))')) # ['()', '(())', '(()())']
print("Test case 5: ", separate_paren_groups('hello world')) # []
print("Test case 6: ", separate_paren_groups('(')) # []
print("Test case 7: ", separate_paren_groups('()((())')) # []
print("Test case 8: ", separate_paren_groups('())()')) # []
print("Test case 9: ", separate_paren_groups('')) # []

Expected Terminal Output:
Test case 1:  ['(())']
Test case 2:  ['()', '(()())']
Test case 3:  ['((()))', '()']
Test case 4:  ['()', '(())', '(()())']
Test case 5:  []
Test case 6:  []
Test case 7:  []
Test case 8:  []
Test case 9:  []

Please run the above test cases.

User:

Output from the terminal:

Test case 1:  ['(())']
Test case 2:  ['()', '(()())']
Test case 3:  ['((()))', '(())']
Test case 4:  ['()', '(())', '(()())']
Test case 5:  ['', '', '', '', '', '', '', '', '', '']
Test case 6:  []
Test case 7:  ['()']
Test case 8:  ['()', ')(']
Test case 9:  []

Assistant:

Test case 3 and test case 7 are failing. Test case 3 is considering the second group of parentheses as a separate group even though it is nested inside the first group. Test case 7 is considering a closing parenthesis as a separate group because there is no open parenthesis to match it. We need to update the implementation to fix these issues. 

Implementation Changes:
Add a check before appending the current group to the list of separate groups to make sure it is not a nested group. If it is a nested group, add it to the previous group instead. Also, add a check at the end to make sure the count of open parentheses is 0. If it is not, the input string has unbalanced parentheses and we need to return an empty list.

Revised Implementation:

def separate_paren_groups(paren_string: str) -> List[str]:
    separate_groups = []
    current_group = ''
    open_paren_count = 0
    
    for char in paren_string:
        if char == ' ':
            continue
        elif char == '(':
            open_paren_count += 1
            if current_group != '':
                current_group += char
            else:
                current_group = char
        elif char == ')':
            open_paren_count -= 1
            if open_paren_count < 0:
                return []
            if open_paren_count == 0:
                separate_groups.append(current_group + char)
                current_group = ''
            else:
                current_group += char
    if open_paren_count != 0:
        return []
    return separate_groups

Revised testing code:

print("Test case 1: ", separate_paren_groups('(())')) # ['(())']
print("Test case 2: ", separate_paren_groups('()(()())')) # ['()', '(()())']
print("Test case 3: ", separate_paren_groups('((()))(())')) # ['((()))', '(())']
print("Test case 4: ", separate_paren_groups('( ) (( )) (( )( ))')) # ['()', '(())', '(()())']
print("Test case 5: ", separate_paren_groups('hello world')) # []
print("Test case 6: ", separate_paren_groups('(')) # []
print("Test case 7: ", separate_paren_groups('()((())')) # []
print("Test case 8: ", separate_paren_groups('())()')) # []
print("Test case 9: ", separate_paren_groups('')) # []

Expected Terminal Output:
Test case 1:  ['(())']
Test case 2:  ['()', '(()())']
Test case 3:  ['((()))', '(())']
Test case 4:  ['()', '(())', '(()())']
Test case 5:  []
Test case 6:  []
Test case 7:  []
Test case 8:  []
Test case 9:  []

Please run the above test cases.

User:

Output from the terminal:

Test case 1:  ['(())']
Test case 2:  ['()', '(()())']
Test case 3:  ['((()))', '(())']
Test case 4:  ['()', '(())', '(()())']
Test case 5:  []
Test case 6:  []
Test case 7:  []
Test case 8:  []
Test case 9:  []

Assistant:

The updated code has passed all the test cases. Therefore, we can consider this as the final implementation. 

Here is the final implementation:

from typing import List

def separate_paren_groups(paren_string: str) -> List[str]:
    separate_groups = []
    current_group = ''
    open_paren_count = 0
    
    for char in paren_string:
        if char == ' ':
            continue
        elif char == '(':
            open_paren_count += 1
            if current_group != '':
                current_group += char
            else:
                current_group = char
        elif char == ')':
            open_paren_count -= 1
            if open_paren_count < 0:
                return []
            if open_paren_count == 0:
                separate_groups.append(current_group + char)
                current_group = ''
            else:
                current_group += char
    if open_paren_count != 0:
        return []
    return separate_groups

In the given example, we can observe that the agent successfully proposed an exhaustive list of test cases, covering a wide range of scenarios. The agent was then able to debug and improve its code completely independently with the help of a python interpretter. This showcases the effectiveness of this technique to build coding assistants that can develop accurate and efficient code!

We’re just scratching the surface of what’s possible when we augment large language models with external tools and memory. We’ll see agents take on ever more complex tasks, from serving as autonomous assistants to driving scientific discovery and beyond. The future is going to be wild!

Coming Soon!!

• Colab noteboook for automated agent
• Evaluation on HumanEvals, LeetCode and CodeForces
• New features including code optimization
• Ablation study of importance of each stage!
• Evaluation of GPT-4!
• Ability to make modifications to existing external code bases via long context memory
• Ability to search the web for debugging purposes

Citation

If you want to cite this blog post, you can use:

@article{llmcodingagent,
  title   = "LLMs can iteratively design, implement, and debug code with external tools!",
  author  = "Gupta, Kshitij",
  journal = "https://kshitijkg.github.io/blog",
  year    = "2023",
  month   = "April",
  url     = "https://kshitijkg.github.io/blog/jekyll/update/2023/04/02/LLMCoding.html"
}