Lazy-k Decoding: Constrained Decoding for Information Extraction

Arthur Hemmer, Mickaël Coustaty, Nicola Bartolo, Jérôme Brachat, Jean-Marc OgierEMNLP 2023 · DOI

Abstract

Lazy-k is a novel decoding algorithm designed to improve Information Extraction (IE) by ensuring model outputs satisfy logical and arithmetic constraints. By efficiently searching through high-probability alternative predictions only when the primary choice violates these rules, Lazy-k allows smaller, faster models to achieve performance levels previously reserved for much larger architectures. Evaluated on benchmarks like CORD and WildReceipt, Lazy-k demonstrates significant accuracy gains and order-of-magnitude speedups over traditional Integer Linear Programming (ILP) approaches.

Introduction

Modern Information Extraction—the task of pulling structured data from semi-structured documents like invoices or receipts—typically relies on "top-1" decoding. In this paradigm, a model (such as BERT or LayoutLM) predicts the most likely label for every token independently. However, these models often produce "logically impossible" outputs. For example, a model might label a "Cash" amount as a "Total," even if the resulting arithmetic on the receipt (e.g., Total = Subtotal + Tax) is no longer valid.

Example of a receipt where logical constraints (Total, Cash, Change) must be maintained for accurate extraction.

While domain knowledge—such as arithmetic or formatting rules—can be used to identify these errors, incorporating them directly into the model's training is challenging. Existing solutions like Integer Linear Programming (ILP) are mathematically rigorous but computationally expensive and often restricted to linear constraints. Greedy methods like Beam Search frequently miss globally optimal solutions in structured tasks.

Methods: Lazy-k Decoding

The authors introduce Lazy-k Decoding, a variant of best-first search optimized to find the highest-probability sequence of labels that satisfies a set of global constraints. The algorithm is characterized by three key features:

  1. Efficient Exploration: Lazy-k exploits the mathematical property that the $k$-th most probable sequence is always a single "edit" (changing one label) away from one of the $k-1$ more probable sequences.
  2. Heap Management: By maintaining a priority queue (heap) of potential label assignments and only expanding the search space as needed, Lazy-k significantly reduces memory and time overhead compared to standard best-first search.
  3. Constraint Agnostic: Unlike ILP, Lazy-k is compatible with any constraint that can be expressed as a function (e.g., complex non-linear tax calculations in Python), making it highly flexible for diverse real-world applications.

Experimental Evaluation

The method was evaluated on three popular document information extraction benchmarks: CORD (Indonesian receipts), WildReceipt (diverse layouts), and DocILE (large-scale business documents). These datasets are ideal for testing constrained decoding because they contain inherent arithmetic structures (prices, taxes, totals) that can be formulated as hard constraints.

Key Results and Insights

The researchers found that constrained decoding provides a disproportionate benefit to smaller models. For instance, a "Small" BERT model (29M parameters) using Lazy-k decoding was able to match or exceed the performance of a "Base" BERT model (110M parameters) using standard decoding.

Performance comparison on the WildReceipt dataset, showing the substantial improvement in F1 score across model sizes when using Lazy-k decoding.

On the WildReceipt dataset, the $F^s_1$ score—a metric combining accuracy and constraint satisfaction—jumped from 44.5% with standard decoding to 82.1% with Lazy-k. Furthermore, Lazy-k proved to be 38x to 182x faster than a "Lazy-ILP" baseline while achieving comparable or superior accuracy.

Conclusion and Future Work

Lazy-k Decoding offers a path toward more efficient and "green" AI by allowing edge-compatible models to leverage logical reasoning. Currently, the algorithm is designed for models with independent token probabilities (e.g., BERT-style encoders) and focuses on "hard" constraints. Future research may extend this approach to autoregressive generative models and explore "soft" constraints to handle noisy or imperfectly OCR'd documents.

Summary updated

BibTeX
@inproceedings{hemmer2023lazy,
  author = {Arthur Hemmer and Mickaël Coustaty and Nicola Bartolo and Jérôme Brachat and Jean-Marc Ogier},
  title = {{Lazy-k Decoding: Constrained Decoding for Information Extraction}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2023},
  doi = {10.18653/v1/2023.emnlp-main.416},
}

Loading related content...

Figure