Implementing One-to-Many Batch-to-Invoice Matching

A counterparty rarely pays one invoice at a time. More often a single settlement deposit lands in the bank feed as one lump sum that covers a batch of open invoices settled together — a customer clearing a month of purchase orders in one wire, or a payment processor sweeping a day’s receivables into a single payout. Unlike the one-to-one lookups covered in Exact-Match Hash Comparison, a one-to-many batch-to-invoice match has to search: given a deposit amount, which combination of open invoices, drawn from a bounded candidate pool, sums to that amount within tolerance? This page implements that search end to end inside Multi-Step Reconciliation Chains — candidate generation, a bounded subset-sum search, tie-breaking between equally valid subsets, guardrails against combinatorial blowup, and an audited confirm-and-post step.

Prerequisites

• The deposit and invoice records have both passed through Multi-Step Reconciliation Chains Stage 1 without resolving — a single-record hash lookup already failed, which is what tells the pipeline this is a batch settlement rather than a one-to-one payment.
• Counterparty identity is normalized (a shared counterparty_id) and each invoice carries an invoice_date and due_date, so candidates can be blocked before any arithmetic runs.
• The tolerance and date-window rules from Date-Window & Amount Tolerance Rules are available as configuration, not hard-coded constants.
• Python 3.10+ with pydantic v2 installed; every monetary field is Decimal, never float.
• A structured logger is configured to emit trace_id, source_hash, and match_decision on every candidate evaluation and every posted match.

Step 1 — Model the deposit and the invoice pool

Both records are frozen and typed. amount is always Decimal, quantized to two decimal places at the validation boundary, because subset-sum arithmetic that mixes float rounding error with tolerance comparisons produces false negatives on penny-level totals.

from pydantic import BaseModel, ConfigDict, field_validator
from decimal import Decimal
from datetime import date
from uuid import UUID

class Deposit(BaseModel):
    model_config = ConfigDict(frozen=True)

    deposit_id: UUID
    counterparty_id: str
    amount: Decimal
    value_date: date
    source_hash: str

    @field_validator("amount")
    @classmethod
    def positive_two_dp(cls, v: Decimal) -> Decimal:
        if v <= 0:
            raise ValueError("deposit amount must be positive")
        return v.quantize(Decimal("0.01"))

class OpenInvoice(BaseModel):
    model_config = ConfigDict(frozen=True)

    invoice_id: str
    counterparty_id: str
    amount: Decimal
    due_date: date

    @field_validator("amount")
    @classmethod
    def positive_two_dp(cls, v: Decimal) -> Decimal:
        return v.quantize(Decimal("0.01"))

Step 2 — Generate candidates by blocking, not brute force

Never run the aggregation search against the entire open-invoice ledger. Block first: restrict the pool to the same counterparty_id and a due_date inside a bounded window around the deposit’s value_date. Blocking is what keeps the search space small enough for the next step to be tractable — the same discipline that governs one-to-one comparisons in Date-Window & Amount Tolerance Rules applies here, except the payoff is larger, since every unnecessary candidate multiplies the size of the subset search rather than just the number of comparisons.

from datetime import timedelta

def generate_candidates(
    deposit: Deposit,
    open_invoices: list[OpenInvoice],
    date_window_days: int = 10,
    max_candidates: int = 40,
) -> list[OpenInvoice]:
    lo = deposit.value_date - timedelta(days=date_window_days)
    hi = deposit.value_date + timedelta(days=date_window_days)
    pool = [
        inv for inv in open_invoices
        if inv.counterparty_id == deposit.counterparty_id
        and lo <= inv.due_date <= hi
        and inv.amount <= deposit.amount  # an invoice larger than the deposit can never be in a valid subset
    ]
    pool.sort(key=lambda inv: inv.amount, reverse=True)
    return pool[:max_candidates]

Sorting candidates by amount descending before the search starts does double duty: it feeds a greedy pass that resolves the common case in a single linear pass, and it gives the fallback search a branch order that finds valid subsets faster, since large invoices eliminate more of the remaining deposit per step.

Step 3 — Try greedy aggregation first

Most batches are clean: the counterparty paid exactly the invoices they intended to, with no partial payments folded in. A greedy pass — repeatedly take the largest remaining candidate that does not overshoot the deposit — resolves this case in O(n log n) without ever touching the combinatorial search. Only fall through to Step 4 when greedy fails to land inside tolerance.

def greedy_subset(
    deposit_amount: Decimal,
    candidates: list[OpenInvoice],
    amount_tolerance: Decimal,
) -> list[OpenInvoice] | None:
    remaining = deposit_amount
    chosen: list[OpenInvoice] = []
    for inv in candidates:  # already sorted descending by amount
        if inv.amount <= remaining + amount_tolerance:
            chosen.append(inv)
            remaining -= inv.amount
        if abs(remaining) <= amount_tolerance:
            return chosen
    return None

Step 4 — Bounded subset-sum search when greedy fails

When greedy overshoots or undershoots, fall back to a depth-first search over the remaining candidates — but bound it hard. Unconstrained subset-sum over n candidates is exponential; a pool of 40 invoices has over a trillion subsets. Two guardrails keep this safe: max_subset_size caps how many invoices a single deposit can be split across, and a hard max_candidates counter aborts the search once it has explored too many branches without finding a solution, rather than letting it run to exhaustion.

class CombinatorialBlowupError(Exception):
    pass

def bounded_subset_sum(
    deposit_amount: Decimal,
    candidates: list[OpenInvoice],
    amount_tolerance: Decimal,
    max_subset_size: int = 6,
    max_nodes: int = 20_000,
) -> list[list[OpenInvoice]]:
    """Depth-first search bounded by subset size and node count.
    Returns every subset that lands inside tolerance, so the caller
    can detect ties rather than silently keeping the first hit.
    """
    solutions: list[list[OpenInvoice]] = []
    nodes_visited = 0

    def dfs(start: int, remaining: Decimal, chosen: list[OpenInvoice]) -> None:
        nonlocal nodes_visited
        nodes_visited += 1
        if nodes_visited > max_nodes:
            raise CombinatorialBlowupError(
                f"exceeded {max_nodes} search nodes with {len(candidates)} candidates"
            )
        if abs(remaining) <= amount_tolerance and chosen:
            solutions.append(list(chosen))
        if len(chosen) >= max_subset_size or remaining < -amount_tolerance:
            return
        for i in range(start, len(candidates)):
            inv = candidates[i]
            if inv.amount > remaining + amount_tolerance:
                continue  # candidates are sorted descending; further ones only get smaller
            chosen.append(inv)
            dfs(i + 1, remaining - inv.amount, chosen)
            chosen.pop()

    dfs(0, deposit_amount, [])
    return solutions

Pruning on inv.amount > remaining + amount_tolerance is what makes the bound effective in practice rather than just in theory: because candidates are sorted descending, the moment one candidate is too large for the remaining balance, every candidate after it is too, so the loop can be tightened further with an early break in high-volume deployments. The max_nodes counter is the real safety valve — it guarantees the function returns (or raises) in bounded time regardless of pool composition.

Step 5 — Break ties between multiple valid subsets

A bounded search can legitimately return more than one subset that sums within tolerance — two different combinations of invoices that both land on the deposit amount. Resolving this deterministically matters for audit reproducibility: the same inputs must always produce the same match. Rank candidates by fewest invoices first (a cleaner ledger entry), then by smallest residual variance, then by earliest due_date as a final deterministic tiebreaker.

def select_best_subset(
    solutions: list[list[OpenInvoice]],
    deposit_amount: Decimal,
) -> tuple[list[OpenInvoice], bool]:
    def variance(subset: list[OpenInvoice]) -> Decimal:
        return abs(deposit_amount - sum((inv.amount for inv in subset), Decimal("0")))

    ranked = sorted(
        solutions,
        key=lambda s: (len(s), variance(s), min(inv.due_date for inv in s)),
    )
    is_ambiguous = len(solutions) > 1 and len(ranked[0]) == len(ranked[1])
    return ranked[0], is_ambiguous

is_ambiguous does not block the match — it is a signal, not a veto. A tier-appropriate policy might auto-post unambiguous single-solution matches and route ambiguous ones to a manual review queue for a human to confirm which invoices the counterparty actually intended to settle.

Step 6 — Confirm and post with a structured audit record

The final step commits the chosen subset, marks each invoice SETTLED, and emits one audit log line per match carrying the trace_id, source_hash, and match_decision triple required for SOX evidence trails.

import hashlib
import logging
from datetime import datetime, timezone

log = logging.getLogger("matching.batch_to_invoice")

def confirm_and_post(
    deposit: Deposit,
    subset: list[OpenInvoice],
    is_ambiguous: bool,
) -> str:
    total = sum((inv.amount for inv in subset), Decimal("0"))
    decision = "AMBIGUOUS_SUBSET" if is_ambiguous else "SUBSET_SUM_OK"
    blob = f"{deposit.deposit_id}|{','.join(sorted(i.invoice_id for i in subset))}|{total}"
    audit_hash = hashlib.sha256(blob.encode("utf-8")).hexdigest()

    log.info(
        "batch_to_invoice.matched",
        extra={
            "trace_id": str(deposit.deposit_id),
            "source_hash": deposit.source_hash,
            "match_decision": decision,
            "invoice_ids": [inv.invoice_id for inv in subset],
            "invoice_count": len(subset),
            "deposit_amount": str(deposit.amount),
            "matched_total": str(total),
            "audit_hash": audit_hash,
            "posted_at": datetime.now(timezone.utc).isoformat(),
        },
    )
    return decision

Posting only after the audit line is constructed — not after — means every ledger write has a corresponding, hash-chained log entry it can be reconciled against later, consistent with NIST SP 800-53 Rev. 5 AU-2 audit-event guidance.

Configuration boundary table

Raising max_subset_size or max_candidates grows the search space multiplicatively, not linearly — tune max_nodes alongside either change and re-run the fixture in the next section before deploying.

Verification and testing

A deterministic fixture where the deposit exactly equals the sum of a known invoice subset is the baseline test: it must resolve through the greedy path without ever invoking the bounded search.

def test_greedy_resolves_clean_batch():
    deposit = Deposit(
        deposit_id=UUID(int=1),
        counterparty_id="MEGACORP",
        amount=Decimal("4820.00"),
        value_date=date(2026, 6, 1),
        source_hash="d34db33f",
    )
    invoices = [
        OpenInvoice(invoice_id="INV-101", counterparty_id="MEGACORP",
                     amount=Decimal("1200.00"), due_date=date(2026, 6, 3)),
        OpenInvoice(invoice_id="INV-102", counterparty_id="MEGACORP",
                     amount=Decimal("1620.00"), due_date=date(2026, 6, 4)),
        OpenInvoice(invoice_id="INV-103", counterparty_id="MEGACORP",
                     amount=Decimal("2000.00"), due_date=date(2026, 6, 5)),
        OpenInvoice(invoice_id="INV-104", counterparty_id="MEGACORP",
                     amount=Decimal("940.00"), due_date=date(2026, 6, 6)),
    ]
    pool = generate_candidates(deposit, invoices)
    subset = greedy_subset(deposit.amount, pool, Decimal("0.02"))
    assert subset is not None
    assert sum(i.amount for i in subset) == Decimal("4820.00")
    assert {i.invoice_id for i in subset} == {"INV-101", "INV-102", "INV-103"}

    decision = confirm_and_post(deposit, subset, is_ambiguous=False)
    assert decision == "SUBSET_SUM_OK"

A second fixture should force the fallback path — remove one invoice from the clean set so greedy overshoots and only the bounded DFS finds the two-invoice subset that lands within tolerance — and a third should set max_nodes deliberately low against a wide, unhelpful candidate pool to assert that CombinatorialBlowupError is raised rather than the process hanging.

Troubleshooting

• NO_SUBSET_FOUND — the bounded search returns an empty list. Root cause: the true matching invoices fall outside the current date_window_days, or amount_tolerance is tighter than a legitimate rounding difference (partial credit note, bank fee netted out of the wire). Fix: widen the blocking window incrementally and re-run before assuming the deposit needs manual research; log the miss with the pool size and total pool amount for diagnosis.
• AMBIGUOUS_SUBSET — more than one subset sums within tolerance. Root cause: the candidate pool contains invoices whose amounts are combinatorially interchangeable (e.g. two pairs that both total the deposit). Fix: this is not an error to suppress — route it to manual review per Step 5 rather than auto-posting the first solution found, since silently picking one risks misattributing which invoices were actually settled.
• COMBINATORIAL_BLOWUP — CombinatorialBlowupError raised mid-search. Root cause: blocking let too many same-amount or near-amount invoices into the pool, so the DFS branches faster than max_nodes allows. Fix: tighten date_window_days, lower max_candidates, or reduce max_subset_size — the search space shrinks combinatorially with any of the three, so a small reduction in pool size buys a large reduction in worst-case nodes.
• TOLERANCE_EXCEEDED — greedy and the bounded search both terminate with a nonzero residual larger than amount_tolerance. Root cause: the deposit genuinely does not equal the sum of any subset of the blocked pool — it may include invoices from a different counterparty alias, or a short payment. Fix: do not silently widen amount_tolerance to force a match; instead surface the residual amount alongside the closest candidate subset so a reviewer can decide whether it is a short payment requiring a write-off code.
• STALE_INVOICE_STATE — a chosen invoice was already settled by a concurrent match before posting. Root cause: two deposits raced against overlapping candidate pools without a row lock. Fix: acquire a row-level lock (e.g. SELECT ... FOR UPDATE SKIP LOCKED) on the invoice rows between Step 5 and Step 6, and re-validate that every invoice in the chosen subset is still OPEN immediately before posting.

Related

• Configuring Tolerance Thresholds for Currency Fluctuations
• Building Deterministic Composite Keys for Hashing
• Optimizing Pandas Merge for High-Volume Transaction Matching
• Date-Window & Amount Tolerance Rules

Part of Multi-Step Reconciliation Chains within Transaction Matching Algorithms & Logic.