Reconciliation Is a Graph Problem, Not a Matching Problem

A customer account closes the month with five items in the exception queue and nothing whatsoever wrong with it.

The customer owed 81,000 across four invoices. The customer paid 81,000 across three transfers. Every unit arrived, from the right account, inside the settlement window, with a remittance advice attached. The matching engine cleared one item and queued the other five.

What happened is ordinary. One invoice of 40,000 was paid in two transfers, 25,000 and 15,000, because the payer's approval limit sits below the invoice value. Three smaller invoices — 25,000, 9,400 and 6,600 — were paid in a single remittance of 41,000, because the payer's treasury nets weekly before it wires. The engine has no way to say this movement settles part of that obligation or this movement settles those three, so it did the only thing it can do: it looked for a movement whose amount equalled an obligation's amount.

It found one. The 25,000 transfer, which was half of the 40,000 invoice, exactly equalled the 25,000 invoice, which was in fact paid inside the 41,000 remittance. The engine cleared that pair with the highest confidence it assigned all month.

The ledger after the run shows 56,000 of open receivables and 56,000 of unapplied cash against a customer who is square. Somebody will spend a morning undoing it, and if they are tired they will force-match the 41,000 remittance to the 40,000 invoice and write off a 1,000 variance that never existed.

Synthetic data/Figures below are generated, not observed. No employer data appears on this site.

The account above is invented, and so is every figure that follows it.

Why better matching does not fix it

The instinct is that the scoring is too crude. Widen the tolerance band. Add fuzzy comparison on the remittance reference. Put a learned model over the pair features — amount ratio, day lag, counterparty, currency, string overlap — and let it discover that this payer part-pays. Each is a real improvement to pairwise evidence. None of them changes the outcome above.

The reason is structural rather than statistical. A matching engine, however it scores, emits one decision per pair and accepts a pair only if the pair is self-justifying. But the evidence that the 25,000 transfer belongs to the 40,000 invoice does not exist inside that pair. It exists in the fact that a second transfer of 15,000 completes it, and that the 25,000 invoice is accounted for elsewhere. That is a property of the whole period. No amount of feature engineering puts a global property inside a local decision.

The second instinct is to add grouping: enumerate subsets of open items and look for subset sums that equal a movement. This is closer to right and fails for two reasons. The search is exponential in the open items, so it needs aggressive pruning, and pruning is where the correct group gets discarded. Worse, a subset-sum matcher with any tolerance at all is a machine for manufacturing coincidences: with a few hundred open items and round-numbered invoices, some subset sums to almost any target you name. Each group is still chosen in isolation, and consuming an invoice in one group silently removes it from every other group that needed it. More expressive power, no more coordination.

Underneath both is an assumption nobody wrote down. Pairwise matching presumes a bijection between two sets of records: each obligation has one movement, each movement has one obligation, and reconciliation is the job of finding the pairing. Splits, aggregations, fees and cross-period timing all violate it. They are also the population that costs the most to clear, because an item nobody disputes still has to be taken apart by hand. I have written elsewhere about the ways record matching breaks; this one survives every fix applied to the others.

The reframe

A period is not a list of pairs to adjudicate. It is a quantity of value that has to land somewhere, and the job is to choose where it lands across the whole account at once — in the way most consistent with the evidence, and still obedient to the arithmetic.

That is a different mathematical object. The candidates form a heterogeneous temporal graph — several kinds of node, several kinds of edge, every edge time-bounded — and the answer is not a set of independent pairs but a single allocation over that graph, chosen to maximise total evidence subject to a hard conservation identity. Reconciliation stops being a search over pairs and becomes an optimisation over assignments.

The special case is not a simplification anyone chose. It is what falls out of a per-pair acceptance rule, and once you write the general problem down it becomes visible as a corner of it.

The mechanism

Four kinds of node

An obligation is a claim with a value and a date: an invoice, a coupon, an expected settlement leg, an accrual. A movement is value that actually changed hands: a bank credit, a wire, a card capture, an internal transfer. An adjustment is a signed correction the business is entitled to make: a credit note, a rebate, a short-payment allowance, a rounding difference. A fee is value that left the system with no obligation behind it: a wire charge, an intermediary deduction, an FX spread.

Rule engines model the first two and treat the last two as reasons for a variance rather than as objects that exist. That is the whole failure in miniature. An unmodelled 12.50 correspondent-bank charge turns a clean three-invoice remittance into a five-item exception, because the group no longer sums and nothing in the system is allowed to say why.

Edges are candidates, not decisions

An edge is a candidate correspondence. It carries a score $s_{ij}$ built from pairwise evidence — reference-token overlap, counterparty identity, amount compatibility, currency, day lag — and a type, because settles, offsets, reverses and absorbs are different relations obeying different constraints. A reversal must pair with its original, never with an obligation, and that is an edge-type constraint rather than a score.

Every edge is time-bounded: $x_{ij}$ is forced to zero when the interval between the obligation date and the movement date falls outside the window $[-\tau^{-}, \tau^{+}]$. The window is deliberately asymmetric. Payers arrive a little early and a lot late.

The scoring model, however good, only builds the graph. It decides nothing.

The assignment is a matrix, and its row sums are not one

Index obligations by $i$ with values $a_i$, movements by $j$ with values $b_j$. Let $X \in \{0,1\}^{m \times n}$ select correspondences, and let $Y \in \mathbb{R}_{\ge 0}^{m \times n}$ record how much of movement $j$ is applied to obligation $i$. The problem is

$$\max_{X,\,Y} \; \sum_{(i,j) \in E} s_{ij} \, y_{ij}$$

subject to

$$\sum_{j} y_{ij} = a_i \;\; \forall i, \qquad \sum_{i} y_{ij} = b_j \;\; \forall j, \qquad 0 \le y_{ij} \le b_j \, x_{ij} .$$

Two things are worth noticing. The objective is value-weighted, so misallocating 25,000 costs a hundred times what misallocating 250 costs, which is the right economics and not merely a modelling convenience. And there is no constraint on $\sum_j x_{ij}$ or on $\sum_i x_{ij}$. A row may carry several ones — that is a split. A column may carry several ones — that is an aggregation. Both at once is a netted remittance against part-paid invoices, which is the case that currently goes to a human.

Conservation is the constraint that does the work

The equality constraints are only satisfiable when

$$\sum_{i} a_i \;=\; \sum_{j} b_j$$

per account, per currency, per period. Value is conserved. That single fact is what makes the problem solvable, and it is global: no pair possesses it, no pairwise score approximates it, and it is exactly the information a per-pair acceptance rule throws away. It is the same species of hard identity that learned models must satisfy rather than approximate.

To be usable on a real period, the formulation needs two exception nodes: a dummy movement that absorbs obligation value nothing settled, and a dummy obligation that absorbs cash nothing explains. Both score zero and neither is capped. The queue then becomes an output of the optimisation with a stated cost, rather than the residue of everything the matcher declined. Adjustments and fees enter as bounded nodes with a penalty, so the solver may create a 12.50 fee node to close a group at a small cost instead of surrendering five items.

Greedy pairwise matching, stated precisely

Now impose the two constraints a rule engine imposes:

$$\sum_{j} x_{ij} \le 1 \;\; \forall i, \qquad \sum_{i} x_{ij} \le 1 \;\; \forall j .$$

Take any selected edge with $a_i > 0$ and $b_j > 0$. The row constraint means obligation $i$ is served by exactly one movement, so $y_{ij} = a_i$. The column constraint means movement $j$ serves exactly one obligation, so $y_{ij} = b_j$. Therefore $a_i = b_j$.

The restriction to one-to-one does not merely make the solution worse. It forces the matched set to be a partial bijection between items of equal value. Relax the equality to a tolerance band and you have the acceptance rule of every rule engine in production. Everything outside that bijection becomes an exception by construction rather than by evidence, which is why exception queues are full of items nobody disputes.

Why the general problem is tractable

Drop $X$ and keep $Y$, and what remains is a transportation problem: min-cost flow on a bipartite network with supplies $b_j$, demands $a_i$ and arc costs $1 - s_{ij}$. Minimising that cost and maximising $\sum s_{ij} y_{ij}$ are the same problem, because the two objectives differ by $\sum_i a_i$, which the conservation identity fixes. This is the Hitchcock–Koopmans formulation from the 1940s. Its constraint matrix is totally unimodular, so when $a_i$ and $b_j$ are whole cents — and a ledger holds nothing else — an optimal basis allocates whole cents too, and nothing has to be rounded before it is posted.

One property of that formulation is worth having for its own sake. A basic solution is a spanning tree of the bipartite graph, so at most $m + n - 1$ arcs carry value: with four obligations and three movements, six arcs, however many candidates the scorer generated. The optimum cannot shred a period into arbitrarily many part-allocations, which is the first thing anybody responsible for the close will want to know. Network simplex handles instances with hundreds of thousands of arcs.

Keeping $X$ with a per-edge charge gives the fixed-charge transportation problem, which is NP-hard. In practice it is approximated by penalising edge count inside the objective and accepting a good solution rather than a proven one.

A worked example

One account, one currency, one weekly period. Four obligations and three movements, all inside a ten-day window. The candidate generator kept eight edges scoring above a floor of 0.15.

The rule engine takes each movement in turn, scores its candidates, and accepts the best one if the score clears 0.80 and the amounts agree within the lesser of half a per cent or 250. MOV-1 finds OBL-2 at 0.88 with the amounts equal to the penny, and clears it. MOV-2's best candidate is OBL-1 at 0.74, on the strength of the invoice number in the remittance reference, but 15,000 is not 40,000, so it is queued. MOV-3's best candidate, OBL-2, has already been consumed, and the next is OBL-3 at 0.75, where 41,000 is not 9,400, so that is queued too. One match, five exceptions, and the one match is wrong.

Now score whole assignments instead. The globally optimal allocation is the five solid edges in the figure:

$$25.0(0.52) + 15.0(0.74) + 25.0(0.77) + 9.4(0.75) + 6.6(0.68) \;=\; 54.89$$

in units of thousands of currency times score. Every obligation is settled, every movement is fully applied, and the exception node is empty. The best feasible assignment that keeps the engine's exact-amount pairing has to push the leftover 25,000 of MOV-3 onto OBL-1, an edge scoring only 0.19 because no reference token supports it, and totals

$$25.0(0.88) + 15.0(0.74) + 25.0(0.19) + 9.4(0.75) + 6.6(0.68) \;=\; 49.39$$

which is ten per cent worse. The engine's own accepted set — one edge, five exceptions — is worth 22.00, or forty per cent of the recoverable objective.

The coincidence that traps the engine is not exotic. Round-numbered invoices, approval limits set at round thresholds and weekly netting all push amounts onto the same coarse grid, so a split whose parts collide with some other open item is a structural consequence rather than bad luck. How often that happens on a real book is an empirical question I have not answered. The mechanism is the point. A pairwise scorer is most confident exactly where it is most likely to be wrong, because amount equality is its strongest single feature and amount equality is what a split manufactures.

Limits

Three honest ones.

The mathematics is neither mine nor new. Transportation and assignment problems date to Hitchcock and Koopmans in the 1940s and the Hungarian algorithm to Kuhn in 1955. The case for resolving entities jointly rather than one pair at a time is Bhattacharya and Getoor's collective entity resolution, which sits downstream of Fellegi and Sunter's probabilistic record linkage. Only the framing is mine: reconciliation as a fixed-charge transportation problem whose one-to-one restriction is what rule engines implement.

A global optimiser is only as good as $s_{ij}$, and it fails differently from a greedy one. A bad pairwise score gives a locally wrong match that looks odd on its own; a bad score inside a global objective gives an allocation that is consistent, arithmetically perfect and wrong, and harder to spot because everything sums.

Conservation rarely holds exactly at a real period boundary. Fees, FX revaluation, disputes and cash in transit break the equality, so the formulation needs slack, and slack with a badly chosen penalty reintroduces the phantom variance it was meant to eliminate. None of this is demonstrated at ledger scale; candidate generation, not the solver, is where I expect it to hurt, and that remains a hypothesis.

Where this goes

The next piece in this pillar takes apart the edge rather than the assignment: the seven distinct ways a candidate correspondence goes wrong, and why three of them are invisible to any similarity function computed on a pair. After that, the uncomfortable corollary. The same graph that makes reconciliation solvable is also a map of who transacts with whom, which becomes a confidentiality problem the moment a model is trained on it. The research page carries the running order.

Hold onto the question the conservation constraint forces. If your reconciliation engine cannot tell you which items it left in the queue because the evidence was weak and which it left because its own structure forbade the answer, it does not know either.