TailHorizon: tail-aware horizon allocation for research agents

Key points

• TailHorizon runs m = 4 short probe attempts and computes the tail ratio: the largest probe improvement divided by the median positive one.
• When the ratio is high or few probes succeed, it spends the rest of the budget on many restarts. Otherwise it extends the best attempt. The idea comes from restart theory for randomised algorithms.
• On KernelBench with a budget of ten calls, TailHorizon reached fast_1 scores of 48%, 78% and 22% on Levels 1, 2 and 3, against 43%, 72% and 18% for the strongest baseline (three seeds).
• On RE-Bench it was ahead of the best baseline in six of seven environments. This is suggestive but not statistically significant (one-sided sign test p = 0.0625).
• Ablations that remove or randomise the tail signal lowered KernelBench Level 2 performance.

Limitations

Abstract

Given a fixed compute budget, should a language-model agent make one long attempt at a task, or several shorter independent ones? The answer differs from task to task, and systems usually fix it by hand. We describe TailHorizon, a small controller that runs m = 4 short probe attempts, computes the ratio of the largest probe improvement to the median positive one (the tail ratio), and then spends the rest of the budget either on many restarts, when the ratio is high or few probes succeed, or on extending the best attempt. The idea comes from restart theory for randomised algorithms. On KernelBench with a budget of ten calls, TailHorizon reached fast_1 scores of 48%, 78% and 22% on Levels 1, 2 and 3, against 43%, 72% and 18% for the strongest baseline, an average gain of 5.0 percentage points (three seeds). On RE-Bench, TailHorizon was ahead of the best baseline in six of seven environments, which is suggestive but not statistically significant (one-sided sign test p = 0.0625). Ablations that remove or randomise the tail signal lowered KernelBench Level 2 performance. Several reported numbers in the underlying experiments cannot yet be reconciled with each other, and we list them in the limitations. The experiments are small, and the claim that a tail ratio above 2 identifies restart-dominated tasks is a hypothesis that these experiments do not test directly.

Related research

• Viveka: Viveka is a checking layer that re-tests a self-improving agent’s changes on fresh seeds, so that changes kept by chance do not become the bar for real progress.
• Agent Kalki: Agent Kalki is a Rust coding-agent harness in which a gate the agent cannot write to admits each self-modification only when eight ordered predicates hold.
• The Harness Is the Lab: A position paper and blueprint for an open AI-scientist harness that grounds every claim in a typed ontology and accepts self-improvement only on held-out evidence.

Cite this paper

@misc{chowdhury2026tailhorizon,
  title     = {{TailHorizon: Tail-aware horizon allocation for long-horizon autonomous research agents}},
  author    = {Chowdhury, Sayan},
  year      = {2026},
  publisher = {Zenodo},
  note      = {Preprint, Kalaris Labs},
  doi       = {10.5281/zenodo.24121494},
  url       = {https://doi.org/10.5281/zenodo.24121494}
}