Compile the Table: Query-Calibrated Operator Compression for Tabular In-Context Learning

What it claims

QCOC compresses the KV cache of a frozen tabular ICL model once, then reuses that compressed cache for every later query. The attention output still depends on each query. Table 1 shows mean accuracy on 64 held-out OpenML-CC18 datasets, using up to 512 in-context examples:

At M=32, QCOC is about 0.8 points below full context and about 4 points above the best dynamic retrieval method. Most of that margin comes from KV-level compression in general: weighted joint-KV already beats every row-selection method. Value fitting adds roughly 1.4 points at M=32 and 1.2 points at M=64.

How it works

The process runs per layer and per head. It needs no parameter updates and no external data.

1. Joint clustering. Each example's state is the concatenation [k/σK ; v/σV], where σK and σV are scalar standard deviations. Deterministic Lloyd K-means runs on these states to produce M prototypes. Empty clusters are repaired by assigning the farthest points. Clustering keys and values jointly avoids merging states that have similar keys but incompatible values.
2. Count weights. All examples are reassigned to their nearest prototype, and each prototype stores its count w_j. Adding log w_j to the attention logits restores the total mass that each cluster represents.
3. Original N. Any length-dependent query transform is still evaluated with the original example count N, not with M.
4. Calibration. The calibration queries are the N attention query vectors that the in-context examples themselves produce. These are run through the full cache to get target outputs Y_cal. Keys and weights stay fixed, which makes the attention matrix P_cal fixed. Values are then fit by anchored ridge regression: Ṽ* = (PᵀP + λγI)⁻¹(PᵀY_cal + λγṼ₀) Here γ = max(tr(PᵀP)/M, ε), which keeps regularization comparable across heads. Ṽ₀ is the cluster-mean values, which serve as the anchor. Keys are not fit, because fitting them jointly with values makes the problem non-convex.

flowchart LR
  E[In-context examples] --> KV[Full KV cache]
  E --> Q[Example query vectors]
  KV --> C[Joint KV K-means + counts]
  KV --> T[Full-cache targets Y_cal]
  Q --> T
  C --> P[Fixed compact attention P_cal]
  Q --> P
  P --> R[Anchored ridge fit of values]
  T --> R
  R --> M[Reusable memory: K, V*, log w, N]

Evidence

• Primary benchmark. M ∈ {32, 64}. Hyperparameters were tuned on ten disjoint CC18 validation datasets. Confidence intervals use a paired bootstrap over datasets. All methods share the same prediction model.
• Baselines. Global selection: random, input K-means, LUCoS. Dynamic retrieval: MICP, CRUMB, KATE, KNN, and an ARASH-style reproduction (a reimplementation, not the original). The appendix also compares key-centroid and ToMe/KVMerger-style KV merging.
• Long tables. Seven CC18 datasets plus SUSY, HIGGS and Covertype, evaluated in 12 configurations. QCOC ranks first among compressed methods in 10 of them and averages 0.23 points below full context.
• Serving. Compressing 8,192 examples to 512 slots gives 10.5× cache compression. The timing setup is a single CPU core over 1,000 queries, with one-time compilation excluded. In that setup QCOC is up to 508× faster than dynamic retrieval and 1.98× faster than full context.

Limits

• The guarantee that value fitting does not increase the residual covers only the calibration queries. The authors state it does not ensure lower test error. Value fitting consistently improves attention-output fidelity, but its effect on accuracy is dataset-dependent.
• The error bound (≤ δ + 2V_max·tanh(ε)) tightens only when keys and values are concentrated within each cluster.
• The speedups exclude compilation cost. They pay off only when one example set serves many queries.
• The fetched text does not name the backbone model. It also gives no code, weights or licence. The text is cut off after Table 1, so the failure-case analysis and appendix ablations were not visible. Check the full paper before relying on QCOC for a specific backbone.