Backtracking Over Header Paths in Deep Variant-Effect Tables

Experiments on disease mutations report their results in large, deeply nested tables. One axis lists the protein, the variant, and the cell line. The other lists the readout, such as steady-state abundance, half-life after protein synthesis is blocked, or abundance after the proteasome (the cell's protein-shredding machinery) is inhibited, each under several temperatures and drug conditions. Answering a simple question such as "is R239C's low abundance rescued by proteasome inhibition at 37°C?" means picking the one correct path through two header trees. Many wrong paths look almost as plausible. Language models fail on such tables mostly by reading the wrong cell, not by doing the arithmetic wrong. Their accuracy also collapses once headers nest more than four levels deep. We propose to treat the choice of header path as a search problem. A model proposes a binding from each condition in the question to a header node and reads the cell. Cheap, automatically checkable constraints then decide whether it must back up and try a sibling branch.

The protein-destabilization literature supplies both the test bed and the checks. Its tables are naturally deep. Its questions often require joining across tables, for example checking whether a mutated protein's non-mutated binding partner is also lost, a "domino" degradation. Its quantities carry strong unit and range structure, such as folding-energy changes in kcal/mol, abundance relative to the unmutated protein, and half-lives in hours, which makes wrong reads detectable. The aim is not to predict variant effects. It is to make models read the evidence that experimentalists already published correctly, at nesting depths where current systems fail.

Core Claim

On deep hierarchical tables, the dominant error is choosing among several header paths that each partly match the question. Rewriting the table into a cleaner format does not remove this ambiguity, because the ambiguity sits in the question-to-header mapping. A search that binds question constraints to header nodes and backtracks when a verifier rejects the binding should therefore close most of the "nesting cliff." The verifier checks whether the binding covers every condition in the question, has no conflicting siblings, and yields a value with consistent units and range. The gain over single-pass reading should grow with depth. It should also persist against sampling many independent answers at the same token budget. If the gain is flat in depth, or matched-budget sampling erases it, the claim is wrong.

The work sits against three lines of prior work. Each plays a different role.

Evidence that motivates the claim. HiTab built a hierarchical-table question-answering benchmark. It showed that logical operators aware of the header tree lift execution accuracy from roughly 29% to 45.1%, and that accuracy falls to about 14.1% beyond four header levels. Srivastava et al. found that financial-table failures are dominantly extraction errors under nested headers. ReasTAP showed that Markdown, CSV, and HTML serializations lose cells that span several rows or columns.

The closest existing system. TABALIGN plans with a diffusion language model and checks during execution that the model's attention lands on the target cells. It reaches 90.62% average accuracy over six benchmarks. Its authors nonetheless report two weaknesses. The reasoner bypasses the plan in 67% of failures, and HiTab-style hierarchies remain hard for cell-level mapping. TABALIGN verifies where the model looks. We verify what the chosen path means, and we add the backtracking that TABALIGN lacks.

Prior work that supplies the method. a1/EAG couples a model to a code sandbox and backtracks when execution fails. Removing that branch exploration cost 21.1 points on AIME24. PGTS casts reasoning as expand, branch, backtrack, and terminate actions under a learned policy. On MATH it reaches 41.0% against 34.4% for chain-of-thought, at 5.28x the tokens versus 16.25x for Monte Carlo tree search. PGTS also failed on graduate science because nothing scored intermediate steps. Our verifiers are a domain-specific substitute for those missing step scorers. Self-verifying reflection shows that depth-first backtracking with self-checks works even in tiny transformers. That supports the bet that a weak controller plus a strong checker suffices.

Research Program

The environment represents each table as two header forests, built in the bi-dimensional tree view that TUTA used for pretraining, plus a cell lookup. A language-model controller emits sandboxed calls of the kind used in EAG. The calls bind a question constraint (for example "37°C", "+bortezomib", "MLH1 partner PMS2") to a header node, descend a level, read the cell at the intersection of two bound paths, compute, join to a second table, backtrack to an earlier binding, or terminate.

An answer can only come from a read action on a path that has passed verification. This rule makes TABALIGN's plan-bypass failure structurally impossible. It does not rely on detecting the bypass after the fact.

The verifiers are deliberately cheap and deterministic, and there are four.

Coverage. Every condition extracted from the question must be bound on some path. No bound node may have a sibling that the question also names.

Type and unit. The header's declared unit, whether kcal/mol, hours, or relative abundance, must match what the question asks for.

Aggregate. Where the table contains total or mean rows, the read value must be consistent with them.

Join consistency. Cross-table questions, such as whether loss of a mutated protein leaves its partner orphaned and degraded, must match on protein, cell line, and condition.

We avoid biological plausibility checks as verifiers, for example "destabilized variants should have short half-lives." These are exactly the claims the tables exist to test. Using them would bias answers toward textbook expectations.

The controller starts as a prompted open model of about 8B parameters, which allows a fair comparison with TABALIGN's scale. A second variant is fine-tuned on a few thousand search traces, mirroring EAG's 2,000-trace recipe. A PGTS-style learned policy is an optional third stage, pursued only if the prompted controller wastes tokens.

The benchmark has two parts. The controlled part starts from long-format sources where every value's full condition tuple is known. These sources are FireProtDB's 13,274 curated stability entries (FireProtDB), MaveDB abundance datasets (MaveDB 2024), the Parkin and glucokinase abundance atlases (Parkin; GCK), and the multi-assay data on MSH2, MLH1, and folliculin (MSH2; MLH1; FLCN). We pivot the same data into layouts of depth 2 through 7, so answers are exact and depth can be varied with content held fixed. Question templates cover single lookups, condition contrasts (29°C versus 37°C rescue, with versus without bortezomib), threshold questions (fraction of variants above 3 kcal/mol, the degradation threshold the MSH2 and folliculin studies report), and partner-degradation joins (MLH1 to PMS1 and PMS2, folliculin to FNIP1 and FNIP2). The naturalistic part is a smaller set of real supplementary tables from these papers, with human-written questions double-annotated for answer and required cells.

Baselines

Naive reference. The do-nothing point is the same 8B model reading the table serialized as Markdown and answering with chain-of-thought. This is what practitioners do today.

Normalization plus code, the strongest simple competitor. This baseline rewrites every cell into a tidy row carrying its full header path, then lets the model write one pandas program, with one retry on execution error. It isolates whether our gain comes from search or merely from undoing serialization damage.

Sampling at matched budget. Best-of-N sampling with majority vote is the cheapest way to spend extra compute. It runs on top of the normalization baseline with N chosen so total tokens match our search. Beating it shows that structured backtracking, not extra samples, does the work.

Hierarchy-aware logical forms. HiTab's operators provide the strongest structured-program reference: 45.1% execution accuracy on HiTab (HiTab).

Closest existing system. TABALIGN is run at 8B with its released planner and attention verifier (TABALIGN). Its reported figure is 90.62% average across six benchmarks. The file gives no HiTab-specific number, so we will run it ourselves on HiTab and stratify by depth. There is no reported result found on Lacuna for any system on hierarchical variant-effect tables, so every number on the new benchmark comes from our own runs.

Fairness. All systems share the same base model where architecture allows. Each gets an equal prompt-tuning budget on a held-out development split. Each is reported at equal mean tokens per question.

Ablations. Three ablations target the key ingredient. Search with all verifiers off tests whether the checks matter. Search with a random backtrack trigger tests whether any second chance helps. Single-pass binding with verifiers used only to abstain tests whether backtracking matters beyond rejection.

Beating the baselines means two things. First, a higher accuracy slope across depth on the controlled set. Second, a statistically clear gain over both normalization-plus-code and matched-budget sampling at depth 5 and beyond, on the variant tables and on HiTab's deep slice.

Why not just…?

Why not just flatten every cell into a tidy row with its full header path and query it with code? This is the real threat. If the cliff comes from serialization, this baseline will remove it, and ReasTAP's findings make that plausible. Our hypothesis is that it fixes serialization but not ambiguity: at depth 5 or more, "abundance" and "37°C" each appear under several subtrees, and one-shot code still selects a wrong but well-typed column. The controlled pivots settle this directly. If normalization-plus-code tracks our system at every depth, we will report that normalization is the fix, and the search contribution is null.

Why not just sample many answers and vote? Voting helps when errors are independent. Header-path errors are probably correlated, because the same misleading header attracts every sample. PGTS's token comparison against Monte Carlo tree search shows that how compute is spent matters, but it does not settle this case. The matched-budget comparison does.

Why not just use TABALIGN's attention verifier? Attention landing on a cell does not mean the cell's header path matches the question. A model can attend faithfully to the 29°C column when asked about 37°C. TABALIGN also cannot recover once it has committed, which is its 67% plan-bypass failure. Running TABALIGN on our depth-stratified sets shows whether semantic path checks plus backtracking add anything beyond attention grounding.

Why not just predict destabilization from structure with FoldX or a protein language model? That answers a different question, namely what a variant's effect will be, rather than what the experiment showed. FLIP2 found that simple ridge models often match large fine-tuned protein models. That cautions against claiming any predictive gain, so we make none. Reading the measured evidence correctly is what curators and clinicians need when predictions and assays disagree.

Decisive Experiments

The central test is the depth curve on the controlled pivots. We plot accuracy against nesting depth from 2 to 7 for every system, with content held fixed. The claim survives only if the search system's curve is flatter than both normalization-plus-code and matched-budget voting, and the gap is largest at depth 5 and beyond, where HiTab reports collapse to about 14.1%.

The second test is error decomposition. Each failure is labeled as a wrong header binding, a wrong join, an arithmetic error, or a parse error. Labeling is automatic on the controlled set and by annotators on the naturalistic set. Search should reduce the wrong-binding share specifically. The verifier and random-backtrack ablations then show whether that reduction comes from the checks.

The third test is transfer to HiTab's deep slice without domain-specific verifiers. Only the coverage and type checks are kept. This tests whether the mechanism is general or only benefits from biology's clean units.

The final check is the partner-degradation join questions. These are the only templates whose answer requires two tables. If the method works, accuracy on them should approach single-table accuracy. Without join verification, it should fall well below.