Reconciliation is a Knapsack Problem

Certain workflows in transaction reconciliation are well-suited to AI, while others are math problems well-suited to deterministic engines.

Imagine we have 10 identical $1 payments that we need to reconcile. Typically, on a bank statement, we would see some of those batched together, and they would appear something like this:

This totals $10, which is what we were expecting. Now, we need to match our business payments to these transactions.

Imagine our payments are tagged A through K (omitting “I” for readability). So, one possible solution to our reconciliation problem is this:

The question is, how many other possible solutions are there? If we solve the batches individually, we are selecting from a list of 10 items to put three into our “solution,” which follows this formula:

And equals:

Once that’s solved, we do the same with the $2 batch.

And finally, we have to match the remaining five transactions. That’s an easier problem to manage, since it’s one-to-one matching, so the number of possibilities is:

The total number of possibilities—if you’re trying to solve all of this at once, as we are—becomes:

That’s a lot of possible solutions. In Computer Science terms, this type of problem is a specific variant of the Knapsack problem, where each item has the same weight. In the example I’ve been describing, the knapsacks are the bank statement transactions, and the items are the equally weighted $1 payments. It’s a combinatorial optimization problem for a computer.

This is why, in most cash reconciliation or audit environments, teams give up on 1:1 transaction matching and opt instead to ensure the totals are equal—because crunching 302,400 options just isn’t worth it.

But that’s what computers are good at! Reconciliation engines, like the one we’ve built at Modern Treasury, have seen a lot of transactions, and every time they see another, it adds to their ability to match. These engines are entirely deterministic, picking up on IDs and data en masse, allowing them to reconcile transactions with 100% confidence and repeatability. The consequence of picking the wrong match in finance is too high to use a probabilistic approach.

But of course, there are edge cases.

So imagine instead of 10 transactions, your business is processing one thousand $1 transactions per day, and you run those using a recon engine like Modern Treasury. Let’s say 99% of those payments reconcile automatically with software. But those pesky ten would still remain, and though 10 out of 1000 doesn’t seem like that many, based on the math we just learned, it’s actually a lot. It’s a hard problem to solve.

This is where AI shines. Instead of trying to brute-force compute the way to a correct answer, you take in a bunch of real-world observations to train a model. It’s substituting abstract, mathematical determinism for a probabilistic model that is tuned to what our system is encountering in the real world at scale.

When you operate in money, the matches have to be 100% accurate. Therefore, the responsible way to use AI is to build it into workflows that humans oversee. It’s the combination of deterministic methods and AI that is a superpower against reconciliation as a knapsack problem. In our example, a deterministic reconciliation engine would operate in real-time for the 990 payments and near-real-time for the AI-suggested, human-approved 10 payments.

Interestingly, as we move into the new era of payments, where more money moves in real-time and settles instantly, the reconciliation challenge increases in multiple ways—first, speed. Teams running reconciliation processes need to find transaction matches, or knapsack objects, in real-time, whether that’s Sunday at 2am or the middle of Thursday afternoon.

Second, math. If, instead of showing up in a few batches, our payments arrive one by one, then we need to match this way:

To which there are 10! answers, or 3,628,800 solutions. That’s too much to brute force. Luckily, these new payment rails, such as RTP and FedNow, include more remittance information to disambiguate payments as they come in. Companies will need to implement software to take advantage of these types of remittance information and not end up in a 3.6M solution quagmire.

Here’s an illustrative example. Imagine we are reconciling transactions for something related to real estate, where physical address is a regular component of the remittance information we receive in these real-time payments. If the physical address is 101 South State Street, it may show up in the text in multiple ways:

While it may be hard to deterministically model the three scenarios shown above, this is the type of thing that language models can do very easily.

Financial workflows are some of the best places to implement AI responsibly. The data is vast, and the solution space is even vaster, but the data is structured in a way that models can take advantage of.

If you have these kinds of high-volume reconciliation challenges, reach out to us. Or send me a note if you want to nerd out on AI in money.