Companies routinely send invoices, medical intake forms, and financial statements to cloud models that pull out structured fields, such as "this box is the patient's date of birth, and that number is its value." Homomorphic encryption, a way of computing directly on encrypted data so the server never sees the document, could make this private. In practice it is far too slow. Encrypted inference is orders of magnitude slower than normal inference, and much of the slowdown comes from rotations: expensive operations that shuffle values between the slots of a packed ciphertext so that elements which must interact end up aligned. Document models make rotations especially costly, because their key task is linking a key to its value across an irregular two-dimensional page. Neighbors on a page scattered across slots look like an arbitrary graph, and arbitrary graphs need many rotations.
This proposal starts from one observation: a form is not an arbitrary graph. Keys and values almost always sit next to each other, either side by side or one above the other. If the client, who owns the document and already runs text recognition, orders the text blocks once by rows and once by columns before encrypting them, nearly every true key–value pair should land within a small, fixed distance $w$ in at least one of the two orderings. The server's layout-reasoning network then only needs banded interactions. Each layer costs about $2w$ rotations per ordering, whatever the page looks like. The client also computes pairwise geometry, such as the offset between two boxes, in plaintext and encrypts it. The server therefore never has to evaluate comparisons or divisions on encrypted coordinates. We aim to show that a banded, fully polynomial graph network run this way gives accurate encrypted entity labeling and linking on real forms, at a cost set by page length and band width rather than by layout irregularity.
Core Claim
The claim has two parts. The first is empirical: under a row-major and a column-major ordering of text blocks, the large majority of ground-truth key–value links in form datasets fall within a small band, and this can be measured before any cryptography is built. The second is methodological: a server model built from banded message passing over client-encrypted geometry features can be evaluated non-interactively in one upload and one download under the CKKS scheme (an approximate-arithmetic homomorphic scheme suited to real-valued networks). It should recover most of the plaintext accuracy on entity labeling and linking, and use far fewer rotations than dense encrypted attention or general encrypted graph packing.
The core layer is a banded aggregation. Let $h_i$ be the encrypted feature vector of block $i$ in a given ordering, $g_{i,i+d}$ the client-computed, encrypted geometry features between block $i$ and the block $d$ positions away (relative offsets, size ratios, overlap), $W$ a server-owned weight matrix, and $a_d(\cdot)$ a low-degree polynomial gate with server-owned coefficients. Then
$$h_i' = \sum_{d=-w}^{w} a_d(g_{i,i+d}) \odot W h_{i+d},$$
where $\odot$ is elementwise multiplication. When blocks occupy consecutive slots, each offset $d$ is exactly one ciphertext rotation. This is the diagonal method for matrix–vector products, restricted to $2w+1$ diagonals. Key–value linking uses the same structure: a bilinear score between block $i$ and each in-band neighbor. The client decrypts the scores and takes the argmax locally, so the protocol never needs an encrypted comparison.
Relation to Prior Work
The gap is real. The research file finds no encrypted inference on visually rich documents at all. Plaintext form models such as FormNetV2, which builds token graphs over spatial neighbors and adds visual features for each edge, and the unified parser OmniParser set the accuracy targets but assume trusted plaintext execution. FUNSD supplies the task definition, and it motivates the focus on linking: its original baseline links entities at an F1 of only 0.04.
On the encryption side, three works supply pieces of the method and differ from us in what they assume. Penguin packs graph convolutions under homomorphic encryption by balancing nodes against features and encrypting the adjacency matrix. It handles arbitrary citation graphs and does node classification only. We instead exploit the near-planar locality of documents to turn adjacency into a fixed band, and we do edge-level linking. MOAI removes rotations from softmax and normalization in dense one-dimensional transformers through consistent diagonal packing. We borrow the diagonal-packing view, but we replace dense two-dimensional attention, whose spatial bias would need encrypted distance computations, with banded interactions over client-precomputed geometry. Converting Transformers to Polynomial Form, ULD-Net, and PolyNeXt show how to train networks with only low-degree polynomial operations. That means range control, a quadratic normalization (PolyNorm) with variance penalties, and Hadamard-product MLPs in place of activations. We reuse PolyNorm and PolyMLP directly. These papers also act as a constraint: they report that deep polynomial networks diverge without variance control, so the design keeps depth at three or four banded layers.
The work closest to ours in deployment is Privacy-Preserving Text Classification on BERT Embeddings. It has the client compute embeddings locally and the server run encrypted logistic regression. We adopt its split between client and server, but the server does more. It runs multi-layer spatial reasoning over the whole page, which is exactly where the proprietary value of a document model sits. The client-side part stays cheap: text recognition, a public frozen text embedder, sorting, and pairwise offsets. It avoids the image-level ciphertext traffic that led HE-Transformer to about 56 GB per image in A Systematic Comparison of Encrypted Machine Learning Solutions.
Research Program
The first stage costs nothing cryptographically. We group words into blocks on FUNSD and CORD, produce the row-major and column-major orderings with simple line clustering, and measure link coverage as a function of $w$: the fraction of ground-truth links whose endpoints lie within distance $w$ in at least one ordering. If coverage at $w \le 8$ is well below 90%, the premise fails. In that case we would either add a third ordering, such as a space-filling curve, or abandon the approach.
The second stage trains the server model in plaintext. The model has two banded channels, one per ordering, and their outputs are fused by addition in shared slot positions. The client fills a fixed permutation table that maps each block's row-order slot to its column-order slot, and this mapping is applied as a masked plaintext permutation. Nonlinear operations are PolyMLP, PolyNorm, and degree-2 gates, trained with the variance penalties from ULD-Net. Node features combine a public text embedding, normalized box coordinates, and optionally a pooled visual patch that the client computes with a small public encoder. Heads handle entity labeling (header, question, answer, other) and in-band linking.
The third stage compiles the model to CKKS with the pages padded to a fixed length. Padding means the server learns only the padded size and the public band width. We count rotations, multiplicative depth, bootstraps, upload and download sizes, and latency per page. We also check that encrypted outputs match the plaintext polynomial model up to CKKS approximation error.
Baselines
The naive reference point is the same banded polynomial model run in plaintext, together with a trivial linker that pairs each question with its nearest answer-labeled block to the right or below. The trivial linker shows how much of linking is pure geometry. The plaintext banded model shows the accuracy lost to banding and polynomialization before any encryption. The accuracy ceiling comes from FormNetV2, which reports an FUNSD entity extraction F1 of 86.35, against 82.53 for LayoutLMv3 in the same paper. We found no linking number on Lacuna for FormNetV2 or LayoutLMv3 on FUNSD. The only reported linking figure is the 0.04 F1 original baseline in FUNSD, so we will train a plaintext unbanded graph model with the same features to serve as the linking ceiling.
The strongest competitor on the actual question is the client-heavy split in the style of Lee et al.. The client runs the best public layout encoder it can afford and builds pair features, and the server evaluates only an encrypted linear or bilinear head. This is dangerous for us because it is cheap and may already capture most of the signal. We will give it the same public text embedder, the same visual features, and the same client-computed geometry, and tune it with the same hyperparameter budget. We beat it if our server model improves linking F1 by at least three points at matched client compute, or matches it with a much smaller client model.
The encrypted alternatives are a dense polynomial transformer over all blocks, compiled with MOAI-style packing, and a Penguin-style polynomial graph network over the full spatial k-nearest-neighbor graph with encrypted adjacency. Both use the same features, depth, and training recipe. For reference, MOAI reports an amortized 2.36 minutes per BERT-base input on an H200 GPU, and Zimerman et al. report 305 seconds for 128 tokens. Neither figure comes from documents, so the comparison is run within our setup at matched sequence length. We beat these baselines if we match their accuracy within one point while cutting rotations and latency by a large constant factor.
Three ablations isolate the key ingredients. The first uses a single ordering instead of two, to test whether column-major order is what captures above-below links. The second removes the client-computed geometry features, keeping only absolute coordinates on each node. The third sweeps the band width $w$ to trace the tradeoff between accuracy and rotation count.
Why not just…?
Why not just compute everything on the client and send an encrypted linear head? This is the main threat, and the client-heavy baseline tests it directly. The evidence for doubting it is indirect. Lee et al. note that their approach stops at logistic regression, and the weak FUNSD linking baseline suggests that pairwise linking needs reasoning over context beyond local pair features, such as competing candidate values. If the linear head comes within a point of the banded network, we will say so. The contribution then shrinks to the coverage finding and a recommendation for the cheap split.
Why not just use Penguin's general graph packing on the document graph? Penguin keeps the adjacency encrypted and arbitrary, which pays rotation costs for irregular structure. On citation graphs its reported latency already reaches thousands of seconds for the largest graph. Our Penguin-style baseline measures whether banding actually saves rotations on pages of FUNSD size, or whether pages are so small that general packing is already cheap enough.
Why not just use a secure enclave or multi-party computation? The systematic comparison paper reports about 0.14 s for an SGX enclave and 0.25 s for CrypTen, against about 549 s for HE-Transformer. On raw speed these are real competitors. They change the threat model, though. Enclaves trust vendor hardware and have tight protected memory, and two-server protocols such as p²RAG assume the servers do not collude. We do not claim to beat them on latency. The claim is that single-server, non-interactive homomorphic encryption becomes affordable for forms, and our latency measurements will state the remaining gap honestly.
Decisive Checks
Three results would settle the proposal. The first is link coverage at small $w$ on FUNSD and CORD, measured before building anything. The second is plaintext accuracy of the banded polynomial model within about three F1 points of the unbanded plaintext graph model on entity labeling and linking. The third is an encrypted page latency and rotation count well below the dense and Penguin-style encrypted baselines at equal accuracy, together with a clear margin over the client-heavy linear head. Failing the first check kills the idea cheaply. Failing only the third means the geometry insight holds but the encryption savings do not, which is still worth reporting.
References
- FormNetV2: Multimodal Graph Contrastive Learning for Form Document Information Extraction
- OmniParser: A Unified Framework for Text Spotting, Key Information Extraction and Table Recognition
- FUNSD: A Dataset for Form Understanding in Noisy Scanned Documents
- Penguin: Parallel-Packed Homomorphic Encryption for Fast Graph Convolutional Network Inference
- MOAI: Module-Optimizing Architecture for Non-Interactive Secure Transformer Inference
- Converting Transformers to Polynomial Form for Secure Inference Over Homomorphic Encryption
- ULD-Net: Enabling Ultra-Low-Degree Fully Polynomial Networks for Homomorphically Encrypted Inference
- Activation-Free Backbones for Image Recognition: Polynomial Alternatives within MetaFormer-Style Vision Models
- Privacy-Preserving Text Classification on BERT Embeddings with Homomorphic Encryption
- A Systematic Comparison of Encrypted Machine Learning Solutions for Image Classification
- $p^2$RAG: Privacy-Preserving RAG Service Supporting Arbitrary Top-$k$ Retrieval