The evolution of goal-driven algorithms

If I now want to do something, I will probably ask a coding agent to do it for me. Or at least to help. This is a very different world from the one I grew up in.

The variety of tasks these models can do is impressive, but how novel is it? We have been building algorithms to carry out tasks since the beginning of mathematics.

This is the definition of an algorithm: a set of instructions to execute a task. But the algorithms we use every day are becoming more and more general. How did that change come about?

To understand what led us to coding agents, this post will take a detour through algorithmic history.

Finding the Greatest Common Divisor

Euclid’s algorithm, one of the oldest recorded, finds the Greatest Common Divisor (GCD) between two numbers \(a\) and \(b\) (like 48 and 36).

1. Divide the larger number (\(48\)) by the smaller number (\(36\)). The remainder is \(12\).
2. Replace the larger number with the smaller number (\(36\)), and the smaller number with the remainder (\(12\)).
3. Divide again (\(36 / 12\)). The remainder is \(0\).
4. Result: The moment your remainder is \(0\), the number you divided by (\(12\)) is your Greatest Common Divisor.

We can verify this result as 36 = 3 * 12 and 48 = 4 * 12. There is no number larger than 12 that divides both 36 and 48.

This algorithm keeps dividing \(a\) by \(b\) until the remainder is 0. When the remainder of \(a / b\) is 0, \(b\) is the GCD of the original numbers.

This is an early example of goal-driven algorithms, the while loop. A program will keep executing a set of steps until a certain condition is reached. In this case, when the remainder of \(a/b\) is \(0\).

This type of algorithm works when:

• There is a clear and verifiable definition of success
• The steps of the algorithm are guaranteed to reach this goal
• This algorithm terminates for any input

Building algorithms guaranteed to find a solution and terminate is not easy. One would imagine it took Euclid a bit of time to get there. These algorithms also presuppose a very rigid goal definition. Such a concise program could not write a sonnet, or carry out a more loosely defined task.

More interestingly, it requires the designer of the algorithm to know how to get there. It took Euclid to build Euclid’s algorithm.

Euclid, a human being endowed with intelligence, could come up with an elegant method to find the GCD of two numbers.

But what is intelligence?

Here, intelligence is a heavy word. It is loaded with meaning and interpretation. It can be defined as the ability to learn or understand things or to deal with new or difficult situations (Merriam-Webster). In this dictionary definition, we see that building Euclid’s algorithm took Euclid’s intelligence to deal with a new situation of finding the GCD.

With this algorithm though, we can now tackle any new situation that involves finding the GCD of two numbers. It is a start, but it is still very narrow, as this algorithm cannot do anything else than finding the GCD. For a while, this is what programs have been able to do.

How could we build algorithms that solve problems that we do not yet know how to solve?

Optimisation Algorithms

You probably already have a good intuition of what this would mean. When I “optimise my suitcase”, I am maximising the satisfaction I get for the items I bring, while respecting volume and weight constraints. My bag needs to close (both security and style) and I need to be able to carry it.

More generally, an optimisation problem involves the minimisation or maximisation of a function (e.g., value / cost) with respect to a set of constraints. If you want to learn more about optimisation, I would refer you to these two articles.

A function is a map from a mathematical object to another, from an input to an output. I like to think of it as a box:

\[\text{input } x \rightarrow \text{function} \rightarrow \text{output}\]

In the case of the suitcase optimisation, an objective function is the utility we get from the list of items we pack. It is a map from an input (list of items) to an output (satisfaction).

\[\begin{pmatrix} \text{16 books} \end{pmatrix} \xrightarrow{\text{Objective Function}} 3/10 \text{ ok}\]

\[\begin{pmatrix} \text{5 t-shirts} \\ \text{3 shorts} \\ \text{5 pairs of socks} \end{pmatrix} \xrightarrow{\text{Objective Function}} 9/10 \text{ good}\]

The problem is easily solvable with 3-4 possible items. It becomes much harder to solve with 20, 30, 40 items. To solve these, we can use optimisation algorithms to find the optimal list of items.

You may say that this is the same as Euclid’s algorithm. It is easy to compute for smaller numbers, but we need the optimisation algorithm when dealing with larger numbers. There, a professional anecdote may be helpful.

When I was a consultant, I was asked to optimise the schedule of an amusement parks’ maintenance staff. In these parks, guests could stay overnight in bungalows. Bungalows have to be cleaned after check-out and before the next check-in. This is the constraint. The hotel wants the lowest number of cleaners working simultaneously (objective function). This dictates the number of people to hire on any given day. With 60 parks and hundreds of bungalows, I had no idea where to start.

This was also long before ChatGPT. As a new joiner, I did not want to panic. I started looking for a solution.

I was reading papers upon papers, without really knowing what I was looking for. Then, I remembered my microeconomics lectures. Utility maximisation was an optimisation problem. In microeconomics though, optimisation can be solved with neat little formulas.

I was dealing with messy reality. There was no partial derivative I could calculate. This scheduling problem was tricky.

It turns out that there are general methods to solve an optimisation problem. A lot of these involve constructing a random solution (e.g., a schedule), scoring it against the objective function, and improving it incrementally. For instance, what is the impact on the objective function of cleaning Bungalow 13B two hours earlier?

One of the most common optimisation algorithms is Hill Climbing. You can apply it to the scheduling problem:

• Random Solution: Construct a random cleaning schedule that satisfies the constraints
• Evaluation: Score this solution by calculating the maximum number of cleaners working at the same time
• Neighbours: Try to shift some bungalow preparations a few hours earlier or later
• Evaluate Neighbours: Calculate the maximum number of cleaners working at the same time
• Selection: Select the best neighbour, and start again at step 3 until no improvement can be found

Or to the suitcase optimisation problem:

• Random Solution: Put random items in the suitcase until your bag is full
• Evaluation: Calculate the satisfaction you get from these items
• Neighbours: Try to replace some items in the bag with other items
• Evaluate Neighbours: Calculate the satisfaction you get from every neighbour
• Selection: Select the best neighbour, and start again at step 3 until no improvement can be found

There are many other general-purpose optimisation algorithms. You can learn more about them in the series I wrote on the topic here.

I ran another optimisation algorithm (Genetic Algorithm) on the problem, and to my surprise, it worked. You can probably imagine, I was 21, it was late at night, I was overwhelmed by the problem I had to solve. And there it was on my screen: the solution. I was going to keep my job. But more importantly, I had solved the problem.

With these optimisation algorithms we can solve new problems. The people who designed them did not need to know about scheduling to solve my problem.

We are getting closer to more general goal-driven programs.

Reinforcement Learning

Optimisation algorithms are great. Can you see their limitation though? Most of the optimisation problems we have seen so far are one-off maximisations or minimisations: optimising the content of a bag or building a maintenance staff schedule.

Many goals or objectives require a bit more work than this. For instance, let’s say that I am designing a robot vacuum cleaner. I want to make sure that the robot cleans the entire room without hitting my walls (and pet). We cannot solve this problem with an optimisation algorithm.

Why? Because it is dynamic. The robot will have to interact with its environment and choose a range of actions: “move left/right”, “vacuum dust”, etc…

Vacuum robot in a grid environment

These actions should maximise a reward function; here, the cleanliness of the room.

Some of these concepts should start looking familiar. We have a function that maps the state of the environment to a reward:

\[\text{Room Cleanliness (State)} \xrightarrow{\text{Reward Function}} \text{Reward } \in [0, 1]\]

The algorithm will need to maximise. We are back to optimisation land. We cannot use exactly the same tools though.

Instead of optimising for a fixed set of parameters like a list of items to pack or a schedule, we are finding the policy that maximises the reward function over time.

The policy is a function (yet another one) that decides what to do next. More rigorously, it takes past actions, rewards and the state of the environment as input; and outputs the next action.

\[\begin{pmatrix} \text{Past Actions} \\ \text{Rewards} \\ \text{Environment State} \end{pmatrix} \xrightarrow{\text{Policy Function}} \text{Next Action}\]

Can you think of the optimal sequence?

In the picture above, the optimal policy would suggest moving up, up, vacuum dust, right, right, vacuum dust.

This policy function is learnt once in training; it is then fixed. A fixed function, to maximise a reward, this starts sounding a lot like optimisation. And it is!

We can use optimisation to find the policy function that maximises the reward function. Mind-blown. How exactly this is done is the topic of another article.

Can you see an issue with Reinforcement Learning (RL) though? Reinforcement Learning agents are trained to maximise a very narrow reward like cleaning a room for a robot vacuum. This reward must be mathematically defined. Ideally, a single number.

To have a Reinforcement Learning algorithm write a sonnet, we would need to build a very sophisticated reward function, just for this task! If I then want the algorithm to write a blog post, I would have to use another reward function.

It is now time to turn to Large Language Models.

Language Models

I managed to write about 2-3 pages on goal-driven algorithms without once using the word “AI”. I am afraid that this short period of bliss now comes to an end.

Let’s say we want to build an algorithm to write a poem based on a prompt. Is there a general way we could build such a machine?

This question is now so banal that the answer does not seem that impressive. If you build a model to predict the next word, and put it in a situation in which predicting the next word repeatedly gets us to a poem, we are good to go.

Imagine we had built a perfect word predictor. We ask it to predict the next word given this following sentence:

The following poem is a Shakespearean sonnet celebrating Berlin’s falafel restaurants:

A good predictor would have to start predicting that sonnet. It has no choice. This is what we call prompting. We can make this even stronger by using the role of user and the system:

User: What is \(3 \cdot 3\)?
System:

There, the word predictor would have to play the role of the helpful system. Exactly how these predictors work is a fascinating topic (more here). The general topic of building predictive algorithms is fascinating, and totally out of the scope of this article (more here).

With this type of approach though, we are getting closer to a general purpose, dare I say “intelligent”, algorithm. If that system works well, it can accomplish any task the user gives it.

At least in theory. The early LLMs like ChatGPT 3.5 had obvious flaws. The development of this technology over the last three years has made LLMs and assistant models generally capable.

This chapter focuses on text though. As long as the goal of the user can be solved with only text given as input and output, these LLMs could do it. But what about building things? Or interacting with the world through the internet? Dealing with information that does not fit into context?

From language to actions

Over the last 6 months, LLMs have started being good at doing things. How could a model that is a simple text input/output machine do things? The answer there is agents. Agents are LLMs equipped with tool-calling capabilities.

Given the input:

User: What is \(3 \cdot 3\)?
System:

The system would have learnt to call a calculator tool:

multiply(\(3, 3\))

Get the response from the calculator:

\(9\)

And use this to generate its reply in natural language:

\(3 \cdot 3\) equals \(9\).

This example looks trivial but only a few tools could enable an LLM to use a computer. These tools include:

• Search for files
• Read files
• Write files
• Search and replace within file
• Web search
• Run command line script

The last one is a bit of a “get out of jail free” card as you can do anything on a computer from the command line.

But how could you teach a model to use these tools? There are two main approaches:

• Supervised fine-tuning
• Reinforcement learning (coming back!)

Supervised fine-tuning involves adding examples of tool-uses in the training dataset of the next word predictor. This means that the model will learn that the next logical continuation after:

User: What is \(3 \cdot 3\)?
System:

Does not involve a guess, but a calculator call. Some supervised fine-tuning dataset could look like this:

User: What is \(3 \cdot 3\)?
System: call: multiply(\(3, 3\))
Tool response: \(9\)
System: \(3 \cdot 3\) equals \(9\).

Remembering the above chapter on Reinforcement Learning, we would need the following components:

• Environment
• Action
• Reward

What would they be in this case?

• Environment: user input or previous words
• Action: next word prediction given an input
• Reward: how correct the answer is

It would be difficult to calculate the reward of the sonnet about Berlin falafel restaurants. I could probably rate its content or its structural correctness but we would not go far.

Other domains, like mathematics or code writing have the advantage of being verifiable. This means that we can calculate a reward. For instance, we know that \(3 \cdot 3 = 9\). Our reward could be \(1\) when the agent gives the right answer and \(0\) when it does not.

Using Reinforcement Learning, the agent can learn that using the calculator makes it more likely to get the reward. The next time it is faced with a calculation task, it will pick the calculator tool with a higher probability.

With the calculator, we may even get the agent to calculate the Greatest Common Divisor between two numbers.

What now?

I grew up in a world in which the only general purpose goal-directed agent was a human. If you have an ambiguous or ambitious goal you would like to reach, you would do it yourself, ask an expert or build a team to do it.

This is not the world we live in today. I can now ask an agent to do most of the tasks that were associated with the previous version of my job. To write a program to do pretty much anything I could think of. What are we humans going to do with this technology?