# Loop Invariants

A condition true before and after every iteration, used to prove a loop does what it claims.

**Rests on:** Proof by Induction

*Machine Learning · Algorithms and Complexity*


## Why learn this

This concept gives you a reliable way to prove that any repeated set of instructions actually works before you execute them. You have likely encountered complex processes where a small error repeats many times, compounding until the result is completely wrong. This technique lets you inspect one single step and guarantee it stays correct forever. It transforms code from 'hoping it works' into 'knowing it works.' For example, consider calculating the total price of items in a shopping cart by adding them one by one. You need to be sure that after every addition, your running total is exactly the sum of the items you have looked at so far. If that belief never breaks, the final total will be correct regardless of how many items are in the cart. This method is essential for writing robust software, debugging tricky errors, and understanding why some algorithms succeed while others fail silently.


## The intuition

Imagine you are stacking bricks to build a wall. You have a rule: 'Every time I place a brick, the stack must be level and stable.' Before you pick up the first brick, the empty ground is perfectly level (this is your starting point). You place the first brick on the level ground. It stands firm and level. You check your rule: yes, the stack of one brick is level. You pick up the second brick. You place it carefully on top of the first. You check your rule again: is the stack of two bricks still level? Yes. You continue this process for every brick in the box. Because you verified that placing a new brick never breaks the levelness, you can be absolutely certain that when the box is empty, the wall is standing perfectly straight. In programming, a loop is just a set of instructions you repeat. A loop invariant is that 'levelness' rule. It must hold true before the loop begins. It must remain true after every single repetition. And it must still be true when the loop stops. If you can show these three things, you have proved the loop achieves its goal. Take the example of summing a list of numbers: [3, 5, 2]. The invariant is 'the current total equals the sum of the numbers processed so far.' Start: total is 0, zero numbers processed. Sum of zero numbers is 0. True. Step 1: add 3. Total is 3. One number processed (3). Sum of [3] is 3. True. Step 2: add 5. Total is 8. Two numbers processed ([3, 5]). Sum of [3, 5] is 8. True. Step 3: add 2. Total is 10. Three numbers processed ([3, 5, 2]). Sum of [3, 5, 2] is 10. True. The loop ends. The total is 10. It is correct.


## An analogy

Think of a librarian reshelving books. The invariant is 'all books to the left of my current position are on the correct shelf.' At the start, the librarian stands at the beginning of the aisle. There are no books to the left, so the rule is trivially true because there is nothing to check yet (a situation we call vacuously true). The librarian picks up the first book and places it on the right shelf. Now, all books to the left (just that one) are correctly placed. The invariant holds. The librarian moves to the next book. After placing it, the librarian pauses: 'Are all books to my left correctly shelve?' Yes. They continue down the aisle, checking this fact after every single move. When they reach the end, all books are shelve. The power of the analogy is that if the librarian makes a mistake and puts a book on the wrong shelf, the invariant breaks immediately. They would see the rule fail right then, rather than discovering the error only at the very end when trying to read the whole section. In code, this invariant acts as that continuous checkpoint, ensuring integrity at every step.


## Definition

A loop invariant is a condition that is true before a loop starts, remains true after every single repetition of the loop body, and is still true when the loop finishes, thereby proving the loop accomplishes its intended result.


## How it connects

This concept sits beside Binary Search, which is a method for finding items in a sorted list by repeatedly cutting the search area in half; Binary Search relies on keeping track of exactly where the answer might still hide. It also connects to Merge Sort, which is a way of organizing lists by dividing them into small pieces, sorting each piece, and combining them; Merge Sort uses this invariant to ensure that every time two sections are joined, they remain perfectly ordered.


## The mathematics

The branch of mathematics here is **logic** — specifically the logic of making promises that can be proven. You are not calculating numbers; you are reasoning about states: before a loop, after one pass, after many passes. The three-part proof structure (initialisation, maintenance, termination) is a form of mathematical induction, which you will meet formally later. But you do not need to know induction now. What matters is the idea of a property that stays true while a number (like the loop counter) changes. In plain words: you have a loop that repeats something. You write down a statement that is true at the very beginning. Then you force yourself to check: if it was true before one repetition, is it still true after that repetition? If yes, then by repeating that argument over and over, it must be true after every repetition. Finally, you make sure the loop actually ends — that there is a condition that will eventually stop it. If all three hold, you have proven the loop is correct. The arithmetic you need is minimal: you only need to compare numbers and track whether an equality or inequality holds. For example, to prove that a loop that sums numbers works, you need to know that adding a number to a running total gives the sum of the numbers added so far — that is arithmetic, but the proof itself is logic.

Let I be the loop invariant. The three-part proof is: (1) Initialisation: I holds before the first iteration. (2) Maintenance: if I holds at the start of an iteration, it holds at the end of that iteration. (3) Termination: the loop ends, and when it ends, I (together with the loop condition) implies the postcondition.


## A worked example

```
We want to sum the list [3, 5, 2] using a loop. The loop will go through each number one by one, keeping a running total. Our invariant is: 'After i numbers have been processed, the total is the sum of those i numbers.' Here i starts at 0, and the running total starts at 0.

Step 1: Before loop: i = 0, total = 0. Invariant: total = sum of first 0 numbers = 0 (true)   # The loop has not started, so no numbers have been added. The invariant holds because the sum of zero numbers is taken to be 0.
Step 2: Iteration 1: i = 0 -> i = 1. total = 0 + 3 = 3. Check invariant: total = sum of first 1 number = 3 (true)   # We have added the first number (3). The total now equals the sum of the first one number.
Step 3: Iteration 2: i = 1 -> i = 2. total = 3 + 5 = 8. Check invariant: total = sum of first 2 numbers = 3 + 5 = 8 (true)   # We added the second number (5). The total matches the sum of the first two numbers.
Step 4: Iteration 3: i = 2 -> i = 3. total = 8 + 2 = 10. Check invariant: total = sum of first 3 numbers = 3 + 5 + 2 = 10 (true)   # We added the third number (2). Now the total equals the sum of all three numbers.
Step 5: After loop ends: i = 3, which equals the length of the list. Therefore total = sum of all numbers = 10   # The loop terminates because there are no more numbers. The invariant becomes the desired result.

Result: The loop correctly computed the sum 10. The invariant held at every step, and when the loop ended, the invariant gave exactly what we wanted.
```


## From scratch, in Python

```python
def sum_list(numbers):
    total = 0
    i = 0
    # Invariant: total == sum of the first i numbers
    while i < len(numbers):
        total = total + numbers[i]
        i = i + 1
        # After this update, invariant still holds: total == sum of first i numbers
    return total

# Test it
print(sum_list([3, 5, 2]))  # Output: 10
```


## What the code does

First, we define a function called `sum_list` that takes a list of numbers. In Python, a list is an ordered collection of items, like `[3, 5, 2]`. We start with `total = 0` and `i = 0`. The variable `i` is an index that tells us which position in the list we are at. The list `[3, 5, 2]` has length 3; `len(numbers)` gives 3. The `while` loop repeats as long as `i < len(numbers)`. Inside the loop, we add the current number to the total, then increase `i` by 1. After each update, the invariant 'total is the sum of the first i numbers' holds. When `i` reaches 3, the condition `i < 3` is false, so the loop stops. The function returns `total`, which is 10. The key point is that we did not just write the loop — we stated the invariant in a comment. That comment is what lets us reason about correctness. If we forgot to update `i`, the loop would never end — a termination failure. If we added the number after increasing `i`, the sum would be off by one — a maintenance failure. The invariant catches both bugs. This is plain Python with no libraries, so you can run it directly.


## Common misconceptions

**A loop invariant must be true only at the end.** — I only need to check that my loop gives the right answer at the end. The intermediate steps are just implementation details.

If the intermediate state is wrong, the final answer will be wrong. The invariant being true after every iteration is what guarantees the final answer is correct. In fact: The invariant must be true before the loop starts, after every iteration, and at the end. Only then does the loop's correctness follow.

**The invariant is the loop condition.** — The condition in my `while` statement (like `i < n`) is the invariant.

The loop condition is about when to stop — it changes from true to false. The invariant is a different statement that stays true throughout. In fact: The loop condition is the guard that controls termination. The invariant is a separate statement that holds regardless of the condition.

**An invariant is a variable that changes.** — The invariant is something like `total` that changes each iteration.

The variable changes, but the invariant is a statement about that variable that does not change — it is always true. In fact: The invariant is a condition or property, not a value. It describes a relationship, like 'total equals the sum of the first i numbers', which holds at every step.

**You need to prove the invariant only once.** — If I check it once after writing the loop, that is enough.

A bug could appear only after many iterations, so a one-time check is insufficient. You need to establish that the invariant survives every iteration. In fact: You must establish all three: initialisation (true at start), maintenance (if true before an iteration, true after), and termination (loop ends).


## In short

A loop invariant is a claim that must be true before every iteration and after the loop ends. To prove a loop correct, you show three things: it holds at the start (initialisation), it is preserved by each iteration (maintenance), and the loop actually stops (termination). Writing the invariant down often reveals bugs immediately. This is the foundation for reasoning about Binary Search, sorting algorithms, and any loop you will ever write or read in AI code.


## Where this is used

You might wonder where loop invariants matter in building AI systems — after all, AI is about neural networks and data, not formal proofs. But every algorithm inside an AI system is a loop, and every loop has an invariant. Here are concrete places:

**Large language models (LLMs):** Training an LLM is one enormous loop over the entire training dataset, often repeated for many 'epochs'. The invariant is that the model parameters (the weights) are updated in a way that the training loss decreases on average. More specifically, inside the training loop, there is a loop over batches of data. A bug in that inner loop — say, not updating the index correctly — can cause the model to see the same batch twice or skip batches, silently corrupting the training. Engineers use invariants like 'every training example is processed exactly once per epoch' to catch such bugs. When you read a training script from PyTorch or TensorFlow, you will see `for epoch in range(num_epochs):` and inside that, `for batch in dataloader:` — the invariant that each batch is used exactly once is maintained by the `dataloader`, and if you write your own data loader, you must ensure the invariant holds.

**Small language models on phones or laptops:** When a model runs on a phone, it often has to process text in a streaming fashion — word by word — because memory is limited. The loop that generates tokens has an invariant: the model's internal state (like the hidden state in an RNN or the attention cache) correctly represents all tokens seen so far. If that invariant is broken — say, the cache holds tokens that are no longer relevant — the output becomes garbage. Developers explicitly maintain that invariant by resetting the cache at appropriate boundaries.

**Retrieval-augmented generation (RAG):** RAG systems retrieve relevant documents from a database before generating an answer. The retrieval step often uses a k-nearest-neighbour search, which is a loop over all items to find the k closest. The invariant there is: 'the list of best candidates found so far contains the k closest items among the first i examined.' If you implement that loop yourself, you must maintain that invariant — otherwise you might return a wrong document, and the LLM will produce a wrong answer. In practice, you would use a library like FAISS, but the library itself relies on the same invariant internally.

**Agentic systems that plan and call tools:** An AI agent that decides, acts, and observes is a loop: while the task is not done, the agent picks a tool, calls it, and observes the result. The invariant is 'the agent's belief about the world is consistent with the observations gathered so far.' If the loop breaks that invariant — for example, the agent's memory (context) is not updated after a tool call — the agent will make decisions based on outdated information and fail. In code, this is often a `while not done:` loop, and developers write detailed prompts to maintain that invariant.

**Everyday applied machine learning:** Consider a recommendation system that loops over users to recommend items. The invariant might be 'the recommendation list is sorted by predicted score descending.' Or a fraud-detection system that loops over transactions; the invariant is 'the model's prediction for each transaction is computed with the same feature pipeline.' A common bug is that the feature normalisation accidentally changes between training and serving, breaking the invariant and causing wildly wrong predictions. Engineers catch this by writing tests that assert the invariant holds.

**What a developer actually writes:** In practice, a developer does not write 'invariant' comments in production code for every loop — but they do write unit tests that check the invariant holds. For example, they might write a test that runs the loop on a small input and checks the output, and also a test that checks the intermediate state. For critical loops, they might use an assertion inside the loop, like `assert total == sum(numbers[:i])`, which is a runtime check. In Python, `assert` is a statement that raises an error if the condition is false. That is a direct way to enforce the invariant. In libraries like PyTorch, invariants are often encoded in the shape of tensors: a tensor is a multi-dimensional array, and the invariant might be 'all batches have the same first dimension.' Shape mismatches immediately raise errors.


---

Read this on the web: https://basavapurushottam.com/learn-ai/loop-invariants
