Language-model agents that turn a biologist's plain request ("find the cortical layers in this tissue slice") into working analysis code are a promising way to give bench scientists access to advanced tools. They are also unreliable. On open-ended analyses they fail most of the time, they give different answers on identical repeat runs, and they can spend hours stuck in loops of fixing their own code. This note proposes to treat that loop as what it structurally is: a randomized search. Decades of work on puzzle and logic solvers show that such searches often have heavy-tailed runtimes, meaning a few runs take enormously long while many finish fast. In that regime, killing a run early and starting fresh with a new random seed beats patience.
There is a catch that is specific to spatial biology. A restart policy is only as good as its test for "this run succeeded." Current agents check spatial results by having a vision-language model look at plots, and vision-language models are known to be poor at basic spatial judgments such as left versus right. We therefore propose to pair restart schedules borrowed from combinatorial search with cheap programmatic geometric checks. We will measure whether agent time-to-correct-answer on spatial transcriptomics tasks is heavy-tailed. We will then test whether restarts with geometric verification raise the probability of a correct answer within a fixed local compute budget for open-weight models that can run on confidential patient data. Spatial transcriptomics here means measuring gene expression at known positions across a tissue slice.
Core Claim
Two claims are tested together. First, the number of agent turns needed to reach a verified-correct result on spatial transcriptomics workflows has a power-law survival curve. Under a fixed budget $B$, that means restarting with a cutoff of $L$ turns succeeds with probability $1-(1-p_L)^{\lfloor B/L \rfloor}$, where $p_L$ is the chance that a single run succeeds within $L$ turns. This can far exceed the single long run's $p_B$ when the tail is heavy, which is the mechanism behind the 70%-to-10% failure reduction from restarts on quasigroup completion in Heavy-Tailed Distributions in Combinatorial Search.
Second, the benefit of restarts depends on the success test. With a vision-language model as judge, an agent can stop early on a spatially wrong answer, for example a slice whose coordinates are mirrored or mis-scaled. Restarts then make things worse, because they multiply the chances of one of these silent false successes. A geometric verifier removes this failure mode.
The second claim is what makes the proposal more than "apply restarts to agents." It ties together the three directions. Heavy tails supply the mechanism. Local deployment for biologists supplies the regime: a fixed budget, open-weight models, and users who cannot debug outputs themselves. The spatial reasoning deficiency is the constraint on how success can be detected.
Prior Work and Positioning
Three groups of prior work motivate the proposal.
Agent failures in bioinformatics. BixBench runs frontier agents on expert-built analysis tasks and finds open-answer accuracy of 21% for Claude 3.5 Sonnet and 15% for GPT-4o. BioAgent Bench runs ten multi-step pipelines under 4-hour and 48 GB caps. It reports 82.5% completion for the best open-weight model (GLM-4.7) and a mean Jaccard overlap of only 0.43 across identical repeat runs, along with decoy files and corrupted inputs going unnoticed. Both benchmarks treat each run as a single trial with a fixed cap. Neither measures the shape of the runtime distribution, which is exactly what determines whether a cap should be short or long.
Visual self-checking. CellAgent automates single-cell and spatial analysis with planner, executor and evaluator agents, and its evaluator inspects plots using GPT-4o. It reports more than 96% execution success across 64 datasets including Visium and Slide-seqV2. Execution success is not spatial correctness, however. On ViewSpatial-Bench, GPT-4o scores 34.98% on perspective-dependent localization. What's "up" with vision-language models? finds 56% for the best model versus 99% for humans on isolated left/right and on/under relations. These results lead us to suspect that visual evaluation of tissue layouts is the weak link, but nobody has measured this on tissue.
Methods we reuse. Heavy-Tailed Distributions in Combinatorial Search provides the diagnosis, a log-log survival plot with tail index $\alpha$, and the restart remedy. Left Heavy Tails ... for Sokoban Planning provides two pieces. One is a way to randomize a neural searcher, using dropout at inference. The other is the evidence that restarts help even a learned policy: deep best-first search with restarts solved 69% of 137 instances that a specialized solver could not solve in two hours. That study used exact simulators with unambiguous success. Our setting lacks such an oracle, which is why the verifier matters. Utilitarian Algorithm Configuration and Practical, Utilitarian Algorithm Configuration supply a key objective: they replace expected runtime, which is undefined under heavy tails, with expected bounded utility $E[u(T)]$, and they choose caps adaptively. Their caps are chosen per configuration on solvers. We instead use the same objective to choose a per-run cutoff for an agent.
What the agent should reach. The spatial clustering tools define this target. GraphST, SAINT and JADE report human DLPFC (dorsolateral prefrontal cortex) adjusted Rand index (ARI, agreement between found clusters and annotated layers) of 0.60, 0.64–0.75 and about 0.61–0.65 respectively. An accessible agent that reliably calls these tools correctly is the goal. Beating them is not.
Research Program
We will build a spatial agent task suite on public data used in the file. It includes domain identification on the 12 DLPFC Visium slices, domain identification on the GraphST breast cancer Visium and Stereo-seq mouse embryo data, and multi-slice alignment of adjacent DLPFC slices. Each task is posed in natural language to a CellAgent-style planner/executor/evaluator agent running open-weight models locally.
Following BioAgent Bench's perturbation methodology, we add spatially specific traps: x/y coordinates swapped, a mirrored slice, high-resolution versus low-resolution image scale factors confused, and a decoy coordinate file from another slice. Each trap yields code that runs and plots without error but produces a wrong result.
For every task and model we will log many independent runs to a generous cap. We will estimate survival curves of turns-to-verified-correct with censoring-aware estimators, and estimate $\alpha$ from the tail. Ground truth for "correct" comes from annotated layers (an ARI threshold relative to GraphST's run on the same slice) and from known trap transformations.
The geometric verifier uses no labels. It checks four things. The first is the fraction of spot coordinates falling inside the tissue mask after applying the claimed scale factor. The second is the spatial autocorrelation of cluster labels on the spot neighbor graph, measured by Moran's I. The third is the alignment residual and the orientation determinant, where a negative determinant flags a mirror. The fourth is agreement of neighboring-domain adjacency between replicate slices. We will compare this verifier against vision-language judges: GPT-4o, the Qwen2.5-VL-3B base, and the multi-view fine-tuned MVSM from ViewSpatial-Bench.
Restart schedules will be compared at equal turn and wall-clock budgets: a fixed cutoff, Luby's universal schedule, and a utilitarian adaptive-doubling cutoff in the style of UP. Randomization between runs comes from sampling temperature and seed.
Baselines
Naive reference. The do-nothing reference is the agent run once up to the full budget with its built-in evaluator. This is how BioAgent Bench and CellAgent operate today. For open-weight models, the closest reported figure is GLM-4.7's 82.5% completion on BioAgent Bench, though completion is not spatial correctness. For the agent architecture itself, CellAgent reports more than 96% execution success and 0.85 annotation accuracy. No reported result was found on Lacuna for agent accuracy on DLPFC domain identification. We will therefore measure the naive agent ourselves on identical slices, hardware and budget.
Strongest competitor. The strongest competitor is best-of-$N$: $N$ parallel independent runs, each capped at $B/N$, with the answer chosen by vision-language judging or majority vote over cluster labels. This is the standard response to unreliable agents. It is also mathematically a restart schedule with one fixed cutoff, so it is the most direct threat. We will give it the same total budget and tune $N$ on held-out slices with the same tuning effort as our cutoff selection. Our method beats it if the utility-chosen cutoff with geometric verification gives a higher probability of a verified-correct answer within $B$ on held-out slices, with a confidence interval excluding zero.
Expert reference. The expert-tool reference is GraphST run by a human with defaults. It gives median DLPFC ARI 0.60 as reported in its paper and serves as the accuracy ceiling the agent should approach.
Ablations. Two ablations isolate the key ingredients. The first swaps the geometric verifier for each vision-language judge while holding the restart schedule fixed. The second holds the geometric verifier fixed and removes restarts, running a single persistent run.
Why not just…?
Why not just use a frontier model? Claude Opus 4.5 completed every BioAgent Bench task. Two reasons argue against relying on this. Confidential patient data often cannot leave institutional hardware, so open-weight models are the relevant regime. And completion does not equal spatial correctness: frontier vision models still fail spatial judgments, with GPT-4o at 34.98% on ViewSpatial-Bench. We will nonetheless run one frontier model on the suite. If its single-run spatial correctness is already near ceiling, the heavy-tail argument loses practical force, and we will report that.
Why not just set a sensible fixed timeout? Utilitarian configuration work shows fixed caps either cut off viable runs or waste budget on lost causes, and the right cap depends on the unknown tail. Our experiments include fixed caps over a sweep. If one fixed cap works uniformly across tasks and models, adaptive schedules add nothing, and that would be a legitimate negative result.
Why not just use a spatially fine-tuned vision model as the judge? MVSM reaches 82.09% on ViewSpatial-Bench and SpatialThinker improves 3D benchmarks. This is a real threat, because a judge that is good enough would make programmatic checks unnecessary. However, both were trained on indoor scenes, and the What'sUp authors found spatial fine-tuning produced dataset-specific shortcuts. The verifier ablation, with MVSM as judge on our mirrored and mis-scaled traps, settles this directly.
Why not just give biologists a fixed pipeline? InstantDL and the GraphST scripts work when inputs are standard. Our traps are exactly the non-standard inputs on which a fixed pipeline also runs silently and returns wrong results. We include the default GraphST script on trapped inputs to quantify this.
Decisive Checks
Four outcomes decide whether the proposal holds.
The first decisive check is whether the survival curves show a heavy tail, meaning a straight log-log tail with $\alpha$ below 2 on a meaningful share of tasks. If the tails are light, restarts cannot help much, and the project reduces to the verifier study.
The second is the interaction effect. With a vision-language judge, restarts should increase the silent false-success rate on trapped inputs. With the geometric verifier, they should increase correct-within-budget. A two-way analysis over judge type and schedule will test this.
The third concerns trap detection. We will measure the trap detection rate of each judge, along with the verifier's false-rejection rate on clean DLPFC slices, where agreement with GraphST-level ARI defines clean success.
Finally, on held-out slices, we will report expected bounded utility with a reported utility curve, verified-correct probability within the BioAgent Bench-style 4-hour cap, and run-to-run agreement of final cluster labels. The last is compared against the 0.43 consistency reported by BioAgent Bench.
References
- Heavy-Tailed Distributions in Combinatorial Search
- BixBench: a Comprehensive Benchmark for LLM-based Agents in Computational Biology
- BioAgent Bench: An AI Agent Evaluation Suite for Bioinformatics
- CellAgent: LLM-Driven Multi-Agent Framework for Natural Language-Based Single-Cell Analysis
- ViewSpatial-Bench: Evaluating Multi-perspective Spatial Localization in Vision-Language Models
- What's "up" with vision-language models? Investigating their struggle with spatial reasoning
- Left Heavy Tails and the Effectiveness of the Policy and Value Networks in DNN-based best-first search for Sokoban Planning
- Utilitarian Algorithm Configuration
- Practical, Utilitarian Algorithm Configuration
- Spatially informed clustering, integration, and deconvolution of spatial transcriptomics with GraphST
- SAINT: Sequence-Aware Integration for Spatial Transcriptomics Multi-View Clustering
- JADE: Joint Alignment and Deep Embedding for Multi-Slice Spatial Transcriptomics