Packing Contracts into Windows: Segmentation as Constrained Assignment with Coupled Clauses

When a long contract is fed to a model with a fixed input size, it has to be cut into pieces. The usual cuts are arbitrary, so a sub-clause ends up separated from the section heading that limits its scope, or from the exception twenty pages later that cancels it. This note proposes treating segmentation differently. Instead of sliding a window along the text, we decide which pieces of the document go into which window. Every clause must share at least one window with its governing headers and preambles, and with the clauses it explicitly depends on. The goal is to use as few total tokens as possible. That problem has the same shape as a known hard problem in matching markets. In medical residency matching, couples must be placed together, and in budget-constrained hiring, items of different sizes must fit within caps. In both settings, adding such requirements turns an easy assignment problem into a hard one.

The central bet is about where the difficulty comes from. Keeping each clause together with its ancestors in the document tree is easy: packing clauses in tree order already does it well. The hard part, both computationally and for model accuracy, comes from cross-references, such as "except as provided in Section 18" or a defined term used far from its definition. A cross-reference forces two distant clauses to travel together, much as a couple's joint preference forces two residents into one location. We expect the payoff to show up on the failure mode current systems handle worst, which is contradictions created by exceptions in legal text.

Core Claim

Our claim has three parts. First, assigning a contract's clauses to fixed-size encoder windows is a many-to-one assignment problem with three ingredients: knapsack-style token costs, ancestor-inclusion requirements, and "coupling" requirements from cross-references. Second, if we solve this assignment instead of using overlapping sliding windows, document-level inference should improve at equal or lower compute, and the gain should concentrate on contradiction labels that hinge on distant exceptions. Third, the gap between a cheap greedy packer and an exact solver should be close to zero on documents with few cross-references, and should open only as cross-reference density grows. That third part is a falsifiable test of whether matching-theoretic machinery earns its place in this problem.

Concretely, a document is a tree of leaf spans $s$ with token length $\ell(s)$. Each span has an ancestor set $A(s)$ (headings, preambles) and a coupled set $C(s)$ (spans it cross-references). We choose windows $W_1,\dots,W_m$, each a set of spans with total length at most the window budget $B$, so as to

$$ \min \sum_{j=1}^{m} \sum_{u \in W_j} \ell(u) \quad \text{s.t.} \quad \forall s \;\exists j: \; \{s\} \cup A(s) \cup C(s) \subseteq W_j . $$

Ancestors and coupled spans may be duplicated across windows. Duplication is the cost being minimized, so siblings that share a long preamble should be packed together. Without the coupling term, the requirements follow the tree, and depth-first packing is a natural near-optimal heuristic. With coupling, the problem contains bin packing and loses that tree structure.

Where This Sits in Prior Work

The motivating evidence comes from legal NLP. ContractNLI introduces document-level inference over 607 non-disclosure agreements. Its Span NLI BERT model uses "dynamic context segmentation," which places overlapping windows so that no window cuts through a logical span. That is the closest existing method to ours. However, its windows are still placed linearly. They keep no ancestor path and do not deliberately co-locate cross-referenced clauses. The authors name "negation by exception" as the main failure, with contradiction F1 around 0.36 against roughly 0.85 for entailment. CUAD handles 100-page contracts with a flat sliding window and down-weights uninformative chunks. Its authors explicitly leave hierarchical clause logic to future work. We take up both of these open items.

A second group of methods attacks hierarchical context loss by attaching structure to retrieved text. TreeRAG prepends each chunk's ancestor path (for example, "Section 1 > Subsection A") before embedding it. HTSIR builds a three-level tree of summaries and raw chunks for retrieval. PDFTriage lets an agent navigate a JSON tree of the PDF. PAKTON builds a Sections > Clauses > Sub-clauses tree for multi-agent contract question answering. These methods supply our ancestor-inclusion idea. Two things separate our proposal from them. They all select content by ranking (top-K, thresholds, or agent calls) for retrieval. We instead want full coverage of the document under a compute budget, and we treat cross-references as hard co-location requirements rather than hoping the ranker retrieves both ends of a reference. Prefixing every chunk with its path, as TreeRAG does, also pays for the same preamble again in every chunk. Our objective is designed to remove exactly that redundancy.

The matching literature supplies the method and sets expectations. SAT Is an Effective and Complete Method for Solving Stable Matching Problems with Couples shows that couples make residency matching NP-complete, yet SAT solvers handle real instances. We reuse that recipe and encode the assignment above for an exact SAT or integer-programming solver. Approximately Stable Matchings With Budget Constraints shows that greedy knapsack-style choice achieves a bound of $1/(1-\bar{s})$, where $\bar{s}$ is the largest fraction of a budget any single item consumes. We expect the analogous parameter here, the largest clause-plus-context relative to $B$, to control how badly greedy packing can do. This is a hypothesis we will measure, not a theorem we import. Diversity Constraints in Public Housing Allocation reports an empirical "price of diversity" near 1.0 despite a worst-case bound of $1/q_{\min}$. It cautions that worst-case hardness often disappears on real data, which is why we treat the greedy-versus-exact gap as an empirical question. We deliberately do not import stability concepts. Encoder windows have no preferences, and pretending they do would add theory without content.

Research Program

We will build four things. The first is a structure-and-reference extractor for contracts. It recovers the section tree from numbering and heading patterns, in the spirit of PDF-to-Tree. It also detects cross-references ("subject to," "except as," "notwithstanding," section pointers, and defined-term uses linked to their definitions). Its precision and recall will be checked on a small hand-annotated sample.

The second is a family of packers sharing one interface:

  • Depth-first greedy packer. It fills windows in tree order and adds ancestors as required.
  • Greedy packer with coupling repair. It also pulls in cross-referenced spans and starts a new window when the budget overflows.
  • Exact SAT/integer-programming packer. It runs under a time limit.

For pairs whose combined context exceeds $B$, the exact packer relaxes the coupling to a penalty. Such cases are reported separately.

The third is retraining Span NLI BERT, with the same backbone and objective, on windows produced by each packer, so that training and test segmentation match.

The fourth is an analysis of solver behavior. We will record runtime and the optimality gap as functions of document length, tree depth, and the number of coupled spans. The test is whether exact solving stays practical when the parameter that matters is the count of cross-referenced spans rather than document length. This mirrors the fixed-parameter results for matching with ties in FPT-Approximability of Stable Matching Problems, and here it remains an empirical conjecture.

Baselines

The naive reference point is disjoint fixed-length chunking at 512 tokens with no overlap. Every system is measured against it in both accuracy and tokens processed per document.

The strongest existing method on our primary benchmark is Span NLI BERT from ContractNLI. With a DeBERTa v2 xlarge backbone it reports 88.5% NLI accuracy, evidence-identification mean average precision of 0.933, and contradiction F1 of about 0.36. It is the strongest competitor because it already avoids cutting spans and is trained end to end on this task. We will rerun it with the same backbone, data split, and hyperparameter search budget as our variants. We will log its total tokens processed so that all comparisons can be made at matched compute. Beating it means equal or better overall accuracy and evidence mean average precision at no more tokens, plus a clear rise in contradiction F1. We will treat 0.36 as the reference figure and compute confidence intervals over seeds.

On CUAD, the reference is the paper's DeBERTa-xlarge sliding-window model: 47.8% area under the precision-recall curve and 44.0% precision at 80% recall, as reported in CUAD. We will rerun it under the same conditions.

The most dangerous competitor is a strong simple combination: a 50% overlapping sliding window, which roughly doubles compute as noted in InstructCoder, with every window prefixed by the ancestor path of its first span, TreeRAG style. We run it at its natural cost and also budget-matched to our packer.

Two ablations isolate the key ingredient. The first removes coupling from our packer, leaving ancestors only. The second compares greedy coupling repair against the exact solver at equal window counts. If coupling contributes nothing beyond ancestor inclusion, the matching framing is unnecessary, and we will say so.

Why not just…?

Why not just prefix every sliding window with its section path? This is the real threat. TreeRAG's prefixing raised finance-domain top-10 recall from 29.02% for late chunking to 83.63% on Dragonball (TreeRAG), so hierarchy alone clearly helps. Prefixing cannot, however, bring the exception clause in Section 18 into the window holding the permission in Section 2, and that pairing is exactly the failure ContractNLI names. The prefix-plus-overlap baseline and the ancestors-only ablation settle this. If they match our full packer on exception-dependent contradictions, the coupling idea fails.

Why not just give the whole contract to a long-context model? For an encoder-classification task like ContractNLI the comparison is not like for like. Still, MuLD shows that a 16k-token Longformer beats 512-token T5 chunking on character classification (82.58 vs 54.01 F1), so longer windows can substitute for clever segmentation. We will include a Longformer-style long-window encoder at equal parameter scale. Our claim survives only if co-location helps at a fixed window size, or if it matches the long model at much lower cost.

Why not just pack greedily and skip the solver? Greedy packing may well be enough. The housing results suggest worst cases rarely appear (Diversity Constraints in Public Housing Allocation), while heuristics in balanced matching sometimes leave gaps up to nine times the optimum (Balancing Bias in Two-sided Markets for Fair Stable Matchings). We make this a measured outcome. If the greedy-to-exact token ratio stays near 1 and downstream accuracy is unchanged, we will recommend the greedy coupling packer and report the exact solver only as a certificate of near-optimality.

Proposed Experiments

The primary experiment retrains Span NLI BERT on ContractNLI under each segmentation. We report NLI accuracy, evidence mean average precision, per-label F1, and tokens processed. Results are additionally sliced by whether the gold evidence spans contain a detected cross-reference or exception cue.

The decisive check is that subset. The prediction is that our full packer raises contradiction F1 there while ancestors-only packing does not, at token cost no higher than the 50%-overlap baseline.

The second experiment repeats the comparison on CUAD extractive review, using area under the precision-recall curve and precision at 80% recall. We expect smaller gains there, since many clause categories are local.

The third experiment is the solver study. Across both corpora we plot the greedy-to-exact token ratio and exact-solver runtime against the number of coupled spans and against the largest context-to-budget fraction $\bar{s}$. The prediction is that the gap grows with coupling density and with $\bar{s}$, not with raw length. If the gap is flat, the matching lens is descriptively wrong for this problem.

A robustness check injects controlled errors into the extracted tree and cross-references. This measures how quickly gains decay with parser noise, the brittleness that PDFTriage identifies as the main weakness of structure-dependent methods.