cd /news/large-language-models/can-llms-execute-algorithms · home › topics › large-language-models › article
[ARTICLE · art-172084] src=vkcr.dev ↗ pub= topic=large-language-models verified=true sentiment=· neutral

Can LLMs Execute Algorithms?

An experiment testing whether large language models can reliably execute natural-language algorithms found that two OpenAI models, gpt-6-luna and gpt-6.1-sol, were evaluated on Euclid's GCD algorithm across number pairs ranging from roughly 5 to 50 digits, with GCDs drawn from {1, 4, 7, 16, 47, 64, 113, 150} and each pair run 5 times to estimate a success rate. The author, who published code and results in a GitHub repo under the gcd-skill directory, framed the test around the observation that LLMs are stochastic token generators rather than deterministic state machines. The results tables and plots were cut off in the source before any success-rate figures were reported.

recommendation

Test LLM instruction-following on algorithms whose iteration count scales with input size, run each case 5 times, and report a success rate rather than a single pass.

more in playbook: Evals and testing for LLM apps
read14 min views7 publishedNov 18, 2026
Can LLMs Execute Algorithms?
Image: source

LLMs as computers for natural language algorithms #

When LLMs are leveraged in software applications, they typically are provided with a natural language document (whether we’re talking of an AGENTS.md, SKILL.md, a system prompt, etc.) which contains instructions that they should follow.

In a sense, these instructions constitute a “program” or “algorithm”. Although they are written in natural language, they describe a sequence of steps to follow in order to achieve a certain goal or objective.

Thinking of LLMs as computers for programs written in natural language can lead to interesting thought experiments.

For example, one could imagine writing a compiler from source code (in Python, for example) into natural language, and then have it “executed” by an LLM.

Or going even further : one could imagine writing a Python interpreter in natural language, giving it as system prompt to an LLM, so that it can execute any Python program given as input!

Of course, the above rests upon the assumption that LLMs actually can reliably execute “natural language algorithms”. But LLMs are not deterministic state-machines, rather they are stochastic token generators…

Still, I was wondering to what extent one could reliably execute natural-language programs using LLMs. That would be hard if not impossible to quantify, given the infinite diversity of programs. Regardless, I thought it would still be interesting to experiment with a simple algorithm to gain a general impression of an LLM’s capabilities as a natural-language computer.

Euclid’s algorithm for computing the GCD of two numbers #

Euclid’s algorithm for computing the GCD (greatest common divisor) of two numbers is usually one of the first algorithms one learns in math class in school, and one of the first algorithms one learns to program in an introductory programming class. As a refresher, here is a Python implementation of Euclid’s algorithm (assuming a and b are positive integers)

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

Due to the simplicity of its instructions, it is easily translatable into a natural language algorithm :

Compute the greatest common divisor (GCD) of two integers, A and B, using Euclid's algorithm.

Follow these steps:

Divide the larger number by the smaller number and compute the remainder.

While the remainder is not zero, replace the larger number with the smaller number, replace the smaller number with the remainder, and compute the new remainder.

When the remainder is zero, the GCD is the smaller number in the final division.

Execute the algorithm exactly as specified.

Return the final GCD as an integer.

It is a good candidate for evaluating how well LLMs can execute natural-language algorithms, for its “execution complexity” (i.e. the number of iterations of the main loop) scales with the size of the input numbers : we can therefore evaluate and compare LLMs based on their capabilities by evaluating them on a range of input numbers of different sizes.

Experiment setup #

The source code and results for the experiment can be found in the following repo (in the gcd-skill directory)

This experiment will evaluate LLMs on their ability to “execute” Euclid’s algorithm on pairs of numbers with sizes varying from approximately 5 digits to 50 digits, and with GCDs in the following set : {1, 4, 7, 16, 47, 64, 113, 150}. Each pair will actually be evaluated 5 times, which will allow us to estimate a “success rate” for the task.

In order to help in building the pair of numbers to evaluate, I computed 10 different pairs of co-prime numbers (aka whose GCD is 1) with digit sizes 5, 10, …, 50 ; then, to get pairs of numbers of the desired GCD, one has to simply multiply each number of the pair by the desired GCD.

Finally, two models were evaluated : gpt-6-luna and gpt-6.1-sol.

Results #

What follows are the tables and plots, for each tested model, of the accuracy rates vs the digit length of the co-prime number pairs, for each GCD value.

GPT-6 Luna

GCD 5 digits 10 digits 15 digits 20 digits 25 digits 30 digits 35 digits 40 digits 45 digits 50 digits
1 100% 100% 100% 100% 80% 80% 80% 100% 100% 100%
4 100% 100% 100% 80% 100% 80% 60% 100% 80% 100%
7 80% 40% 100% 40% 0% 40% 0% 20% 0% 0%
16 100% 80% 60% 100% 60% 100% 80% 100% 60% 20%
47 100% 40% 60% 40% 80% 40% 0% 0% 0% 0%
64 80% 60% 100% 100% 40% 40% 20% 80% 0% 20%
113 100% 40% 80% 0% 20% 0% 0% 0% 0% 0%
150 60% 100% 60% 80% 0% 60% 40% 40% 60% 20%

GPT-6.1 Sol

GCD 5 digits 10 digits 15 digits 20 digits 25 digits 30 digits 35 digits 40 digits 45 digits 50 digits
1 100% 100% 100% 100% 100% 100% 100% 100% 100% 100%
4 100% 100% 100% 100% 100% 100% 100% 80% 100% 100%
7 100% 100% 100% 80% 100% 80% 100% 100% 60% 40%
16 100% 100% 100% 100% 100% 100% 100% 100% 100% 100%
47 100% 100% 100% 100% 60% 100% 60% 100% 40% 20%
64 100% 100% 100% 80% 100% 100% 100% 100% 100% 100%
113 100% 100% 100% 60% 100% 60% 40% 80% 60% 40%
150 100% 100% 80% 60% 80% 100% 100% 100% 60% 60%

Analysis #

Firstly, I must mention that the performance of using LLMs for computing the GCD of two numbers is horrible : I didn’t trace the calls but for large numbers they could take several minutes. Obviously, using an LLM to compute the GCD of two numbers is completely stupid, and one should never do it outside of blog post experiments!

Moving on to the results, we can see several patterns, some expected, some interesting.

First, as we could expect, gpt-6.1-sol performs better than gpt6-luna - that makes sense, it’s a better model.

Second, we observe that they both still make many errors : LLMs will have trouble computing even a simple algorithm like the GCD algorithm for large numbers.

Then, we can also see that the performance of both models go down for two kinds of GCDs

  • For larger GCDs
  • For prime GCDs (and especially large primes).

A way to interpret the above is that the LLM is biased towards “nicer” numbers such as 1 or 4, which I suspect are common GCD values, and has more trouble with “weirder” numbers such as 47, which I suspect are pretty rare GCD values.

That, of course, would be illogical if we supposed that the LLM blindly follows the steps of the Euclidian algorithm, but it would make sense if, under the hood, the LLM somehow deviated from the Euclidian algorithm when computing GCDs, choosing an alternate method which works better for “nicer” GCDs.

Let’s peek under the hood!

Inspecting the thought traces #

OpenAI only returns summaries of thought traces, not the raw traces, which limits our ability to interpret them. Nevertheless, inspecting them reveals some interesting “execution paths” of the Euclidian algorithm.

Some thought traces seem to exhibit genuine applications of the Euclidian algorithm, for instance the following one (which got a correct result) :

Reasoning trace:
**Calculating gcd step-by-step**

I need to compute the GCD using the Euclidean algorithm with the numbers provided. It appears I start by performing several modulus operations, checking the outcomes diligently as I go. I have recalibrated my results for accuracy, confirming that all steps align correctly. I double-check each calculation to ensure consistency: starting with 98581, I apply the algorithm step-by-step until I reach the GCD of 1. Now, I can finalize the integer response call.

Let’s look at some incorrect results, as these are more interesting. Sometimes it seems that the application of the Euclidian algorithm fails and the LLM gets confused :

Reasoning trace:
**Calculating GCD using Euclidean method**

I need to compute the GCD accurately, possibly using the final output type response. So let's think through the Euclidean algorithm mentally. I have two large numbers: A and B. I'll verify the difference between them and use that to calculate the GCD with stepwise division. Both numbers have 47 digits, so it's tricky. I may also look into modular arithmetic to manage the calculations. I'll ensure everything aligns properly, looking for precision in my work!**Verifying arithmetic subtraction**

I seem to have made a mistake about the number of digits in D. Let's carefully subtract A and B to ensure accuracy. A is 73,264,460,208,427,954,445,307,040,395,430,050,471,982,777,027 and B is 46,556,020,690,560,324,880,113,191,883,593,256,216,215,564,928. I’ll group the digits into threes for clarity. The subtraction leads me to a result of 26,708,439,517,867,629,565,193,848,511,836,794,255,767,212,099. I’ll make sure to double-check that!

Oftentimes, it goes off the rails completely and ignores the Euclidian algorithm, trying to compute the GCD using its own methods, which seem to rely on the probabilities of common GCD values (thus potentially explaining the bias towards “nicer” GCD values we identified previously) :

Reasoning trace:
**Figuring out GCD calculation**

I need to use a tool that gives a final integer response, so I must compute the GCD accurately. This involves dealing with very large integers, which makes manual Euclidean methods cumbersome. I wonder if I can use Python mentally, but since the tool only accepts the final integer, I’ll have to calculate it using reasoning. The numbers are around 52 digits, and performing manual divisions might be challenging. Maybe I could exploit the numbers to find common factors? Let's compute!**Calculating GCD possibilities**

I'm looking into whether the chosen numbers are multiples and considering using a Python-like long division approach with base 1000 chunks. I wonder if I might do some modular testing, with a typical GCD probability around 0.6, so I'll expect the GCD to be 1. To gain confidence, I can start with a few Euclidean tests and identify potential small common divisors. The last digits end in 799 and 403, which aren’t divisible by 2 or 5. I’ll sum the digits and see how that helps determine their GCD!

**Analyzing GCD of large numbers**

I'm looking into two 52-digit numbers whose GCD appears to be 1, which is interesting! But I wonder if they were deliberately selected because they look random. I think I could use a modular check for common factors. The GCD probability being greater than 1 is around 39%, so I need a stronger method. I might use Euclidean algorithms for finding GCD, but it seems tedious. Checking for patterns in their ending digits might help. I'll also explore using small primes for more efficient calculations.**Grouping large numbers**

I'm analyzing the 52-digit number by creating groups from the right systematically. The first number is 5054744899353852201691105714717388415062437279405799, which I can break down into chunks—there seem to be about 18 total. The second number is 7208000184521304107392774294916472744938672062839403, also chunked appropriately. I’m considering testing the divisibility using the digit sums from these chunks. For example, calculating the digit sum of the first number will give me insight into possible factors.

or

Reasoning trace:
**Calculating GCD Manually**

I need to call a tool, but the response must be an integer. It seems bizarre that I can't compute GCD directly, so I'll have to derive it manually since Python isn’t available. I've got two big integers, A and B. I want to compare them and find their GCD. I could use the Euclidean algorithm or long division, but it looks complex with these large numbers. Maybe I can simplify things by exploring their relationships instead of brute-forcing it. I'll check the difference and see where that leads me.**Continuing GCD Calculation**

I've worked with large numbers and figured out that padding A helps me align the digits better. By subtracting, I got a difference D of 590,067,163,069,269,287,882,265,440,861,513,310,673,350. Now, I might proceed to find the GCD using this difference. I still need to call a tool to get the final result as an integer. I'll have to ensure everything’s set up correctly for that step!

**Figuring out gcd calculations**

I’m thinking about calculating the greatest common divisor (gcd) using Euclidean division. It might involve using binary gcd methods with digit groups, which can be quite labor-intensive given the large numbers. I notice both numbers end in zeros; maybe that's a hint for a common factor. After normalizing, I've got two very large numbers, and I need to explore if I can utilize known properties or divisibility tests to identify potential common factors.**Analyzing divisibility and gcd**

I’m checking the divisibility of two numbers by 50, and I see some interesting patterns. It looks like one ends in 42 and the other in 750, suggesting a possible gcd of 2. I note that after dividing, one number remains even while the other is divisible by 2 and 5. However, when I normalize by 100, I see that the second number ends improperly, which complicates things. So, the gcd might actually be lower than I thought, possibly leading me to revise my calculations.

**Calculating GCD Factors**

I’ve noticed a mistake — dividing 50 gives 9, not 750! Looking at the last digits, I see that B ends with 450, which shows a division of /50 resulting in 9. On the other hand, A ends with 100, which gives me /50 = 2. So now I'm considering the GCD with one ending in 2 and the other in 9, making it seem odd. I need to compute this precisely, possibly using Euclid’s method or leveraging common small factors.**Estimating GCD Values**

I’m realizing that the GCD is divisible by 50, and when divided, A ends with 2 and B ends with 9, indicating the GCD could be odd. It seems likely that the GCD is multiple of 50 times an odd number. I could consider using Euclidean long division, but estimating quotients and calculating remainders feels challenging. Maybe a tool call can help provide an integer response, but there’s this feeling that the numbers are crafted to yield a GCD around 50 due to ending zeros.**Determining GCD Factors**

Both numbers end in 00 and 50, so the GCD is at least 50. Their quotients after dividing by 50 end in 2 and 9, suggesting a likely GCD of 1. However, A ends in 2100, making it divisible by 100, while B ends in 5450, which is only divisible by 50. Thus, the GCD is exactly 50, and I’m considering that the values might have been generated with a shared factor, especially since they’re random 42-digit numbers.

**Evaluating gcd probabilities**

It seems likely that the random integers I'm working with have been chosen, leading to intentional probabilities regarding their greatest common divisor (gcd). After running some calculations, I find that the gcd is about 0.61 for values of one and approximately 0.39 for those greater than one. I need to call the tool to finalize my results and wrap up this conversation. The final result will be based on the integer value of 50, which should work.

Conclusion #

So what is the conclusion of this experiment? I think it’s sobering : even for a simple algorithm like the Euclidian algorithm, LLMs are unreliable at computing it correctly by properly following the steps, either because it makes mistakes along the way, or (more concerning) because it goes off the rails entirely.

This calls into question the wisdom of trusting LLMs for “cognitively-loaded” reasoning tasks, insofar as the reasoning task can be mapped to the execution of an algorithm.

In the end, I think that the GCD algorithm might have been a poor choice for this experiment, as many examples of solving GCDs must exist in the LLM’s training dataset. A better way to evaluate an LLM on its ability to implement an algorithm would be on a new algorithm which it has not seen during its training (future blog post?)

── more in #large-language-models 4 stories · sorted by recency
── more on @gpt-6-luna 3 stories trending now
sponsored brought to you by zahid.host 4,200+ EU-deployed projects
reading about agents? ship yours in a single git push.

Run your AI side-project on zahid.host

EU-based hosting, git-push deploys, automatic HTTPS, no cold starts. Free tier with a custom domain — perfect for shipping the agent you just read about.

$git push zahid main
→ Live at https://your-agent.zahid.host ✓
Get free account → Pricing
from €0/mo · no card required
LIVE [news/can-llms-execute-alg…] indexed:0 read:14min 2026-11-18 · —