RICH From Zero: Short Profitable Circles With Colour Coding

Lesson 8 of the course "Build your own arbitrage bot". Bellman-Ford and SPFA find any profitable circle. Today you meet the idea behind a recent research algorithm that finds good short circles.

Why "any circle" is not enough

Suppose Bellman-Ford returns a profitable circle with nine steps. Every step is a trade, and every trade has a fee, a delay and a chance that the price moves before you finish. On a blockchain exchange, every step can also cost a network fee. A nine-step circle is almost always worse in practice than a three-step circle with a slightly lower margin.

So a bot wants a different question: find a profitable circle with at most k steps. Computer scientists call this a k-hop negative cycle problem. The bot decides k (3, 4 or 5 is common).

The research paper behind this lesson is "RICH: Real-time Identification of negative Cycles for High-efficiency Arbitrage" (Luo, Jiang and coauthors, PVLDB volume 18, VLDB 2025). The authors report that RICH is up to 32.7 times faster than earlier methods on cryptocurrency and foreign exchange data. Their approach rests on an old trick called colour-coding, plus a few engineering ideas to reduce work. Today we build the core trick and leave out the engineering. The simplified version in this lesson is not their code.

The head-on way and where it breaks

To find the best circle with at most k steps from a start node, you could try every path of length up to k. With 300 currencies and 6 pairs each, paths of length 4 number about 6⁴ = 1296 per start node, which is fine. With 300 currencies each trading against 100 others, it is 100⁴ = 100 million per start node, which is not fine.

A smarter way is dynamic programming: remember, for each node and each step count, the cheapest way to get there. This is exactly Bellman-Ford with the number of rounds limited to k. The catch is that the cheapest walk of k steps may revisit a currency. A "circle" USD, EUR, USD, EUR, USD with four steps is not a real new opportunity: it is the two-step circle done twice. You want circles that visit each currency once, called simple cycles. Forcing a path to have no repeated node is what makes the problem hard.

The colour-coding trick

Here is the trick, which sounds silly and works well.

1. Give every currency a random colour out of k colours. (If k = 3, each currency is randomly red, green or blue.)
2. Now look only for circles where every step has a different colour: one red, one green, one blue. Such a circle cannot visit the same currency twice, because a repeated currency would repeat its colour.
3. This restricted search is easy, because you only need to remember which colours you have already used, not which currencies. With k colours there are only 2ᵏ sets of used colours. For k = 3 that is 8, for k = 5 it is 32.
4. A real profitable circle may be missed because two of its currencies got the same colour. But if you recolour randomly and repeat, it will be caught. The chance that one particular circle of k currencies gets k different colours is k!/kᵏ (for k = 3: 6/27, about 22 percent; for k = 4: 24/256, about 9 percent). Repeating 50 or 100 times makes missing it very unlikely.

An analogy: paint each person in a crowd with one of three random colours, then look for a group of three people in three different colours. Do it again with new random colours, and again. Every group of three real friends will, sooner or later, get three different colours at once.

Working through a tiny example

Currencies: USD, EUR, GBP, JPY. Look for the best circle through USD with at most 3 steps.

Suppose the random colours this round are USD red, EUR green, GBP blue, JPY green.

The search keeps a table. Each row says: "I am at this node, I used these colours, the cheapest cost so far is this, and the path was this."

• Start: at USD, used {red}, cost 0.
• Step 1: from USD to EUR (green, not used): at EUR, used {red, green}, cost +0.1054. From USD to GBP (blue): at GBP, used {red, blue}, cost +0.2877 (the weight of 0.75).
• Step 2: from EUR to GBP (blue, not used): at GBP, used {red, green, blue}, cost 0.1054 + 0.1278 = 0.2332. From EUR to JPY (green): green is already used, skip.
• Close the circle: from GBP back to USD costs −0.2624. Total 0.2332 − 0.2624 = −0.0292. A negative total, so USD, EUR, GBP, USD is a profitable simple circle.

If the colours had been USD red, EUR green, GBP green, the circle would have been skipped this round (EUR and GBP are both green), and a later round with different colours would catch it.

The code

import math, random

random.seed(7)
rates = {("USD", "EUR"): 0.90, ("EUR", "GBP"): 0.88, ("GBP", "USD"): 1.30,
         ("EUR", "USD"): 1.10, ("GBP", "EUR"): 1.10, ("USD", "GBP"): 0.75,
         ("USD", "JPY"): 150.0, ("JPY", "USD"): 0.0066,
         ("EUR", "JPY"): 160.0, ("JPY", "EUR"): 0.0062}
nodes = sorted({n for edge in rates for n in edge})
w = {edge: -math.log(r) for edge, r in rates.items()}

def best_cycle_through(start, k, rounds=200):
    """Cheapest cycle through `start` with at most k steps, by colour-coding."""
    best = (math.inf, None)
    for _ in range(rounds):
        colour = {n: random.randrange(k) for n in nodes}
        # table[(node, set of used colours)] = (cost, path); the set is a bit mask
        table = {(start, 1 << colour[start]): (0.0, [start])}
        for _step in range(k - 1):
            for (node, used), (cost, path) in list(table.items()):
                for (a, b), wt in w.items():
                    if a != node or b == start:
                        continue
                    bit = 1 << colour[b]
                    if used & bit:
                        continue                      # this colour is already used
                    key = (b, used | bit)
                    if key not in table or cost + wt < table[key][0]:
                        table[key] = (cost + wt, path + [b])
        for (node, used), (cost, path) in table.items():
            if (node, start) in w and cost + w[(node, start)] < best[0]:
                best = (cost + w[(node, start)], path + [start])
    return best

cost, path = best_cycle_through("USD", 3)
print(path, "cost", round(cost, 4), "money x", round(math.exp(-cost), 4))

Output:

['USD', 'EUR', 'GBP', 'USD'] cost -0.0292 money x 1.0296

The program found the profitable three-step circle and its multiplier 1.0296.

What this simplified version leaves out

• It scans all edges in the inner loop, which is slow. A real implementation stores outgoing roads per node.
• It does not reduce the graph first. The paper describes graph reduction and a compact encoding, which are where much of the speed-up comes from.
• It gives a probabilistic answer: with random colours there is a small chance to miss a circle, shrinking with the number of rounds.
• It handles one start node. A bot loops over start nodes, or uses one table for all.

Treat the lesson as a way to understand why colour-coding keeps the search small (only 2ᵏ colour sets), and read the paper for the engineering.

When does it pay off?

Use Bellman-Ford or SPFA when you only need to know whether any profitable circle exists. Use a limited-step search such as colour-coding when circles with many steps are useless for you (fees, delays, gas), which is nearly always. For small k and a graph of a few hundred currencies, the cost of the search is small enough to run on every price update.

Let an AI agent write and test it

A vague request:

Implement RICH.

A request with scope and a check:

Do not implement the full RICH paper. Write colour_cycle.py with a function best_cycle_through(start, k, rounds) that finds the cheapest simple cycle through the start currency with at most k steps by colour-coding: random colour per currency, a table keyed by (node, bitmask of used colours), repeated for many random colourings. Use weights minus natural log of rate. Test: with the ten rates in this lesson, start USD, k = 3, it must return USD, EUR, GBP, USD with a money multiplier of 1.0296. Test 2: multiply all rates by 0.95, it must return no negative cost. Store outgoing edges per node instead of scanning all edges.

Then ask the agent: "What did you leave out compared with the paper?" A good agent lists the omitted parts. If it claims to have implemented the full paper, do not believe it.

Your exercise

1. Run the code. You should see multiplier 1.0296.
2. Change rounds from 200 to 3, 5 and 10, running each setting 20 times with different seeds. How often do you miss the circle? Compare with the chance k!/kᵏ = 6/27 per round for k = 3.
3. Compute by hand the probability of missing a three-currency circle after 10 rounds: (1 − 6/27)¹⁰ ≈ 0.08.
4. Compute by hand the product of the rates for USD, JPY, EUR, USD (150 × 0.0062 × 1.10). It is 1.023, a second profitable circle, smaller than the first. Run the code with k = 3 and rounds = 200 and confirm that the program prefers the first one, then explain why from the weights.

What comes next

World 2 ends here. Your stage 1 can now find profitable circles in a graph of rates. But all these rates are the top of the book, valid for a tiny amount. World 3 opens the order book and asks how much money a circle can really carry. Lesson 9 starts with reading and walking an order book.