Reuse, but Verify: Certified Maintenance of LLM-Computed Table Cells under Prompt Edits

Abstract

AI-native tables let users define columns in natural language: each cell is computed by a language model from a versioned prompt over its row. When the prompt is edited, deployed systems face a choice: recompute every cell, which is expensive and rate-limited, or silently reuse stale ones, which incurs unbounded error. We present sIVM, a maintenance layer that certifies which cached cells may be reused after a prompt edit, bounding the expected false-reuse rate of each certified stratum by a user budget alpha with probability at least 1 - delta. sIVM freezes cached-value strata, samples adaptively on a doubling look schedule, and bounds each stratum's flip rate with empirical-Bernstein confidence bounds; a strict mode certifies at a deflated threshold to bound the error of the reused cells alone. We also establish an impossibility floor: a model's rate of disagreement with itself under the unedited prompt floors the certifiable budget. On two public corpora (89,184 Stack Overflow developer profiles; 210,250 Djinni candidate CVs) with 32,000+ labeled cells and a production table system, a formatting-only edit certifies 82.6% call savings at alpha=0.2, the loose end of a measured savings-budget frontier, and at deployment scale 225 oracle calls certify reuse of 81,289 of 89,184 cells (91.1% fewer model calls). In every seeded sweep and sampling replication, and in 396,000 known-rate calibration trials, no certified stratum's true flip rate exceeded its budget. We release the system, the labels, and a benchmark of versioned prompt-edit pairs.