Difficulty- and Saturation-Aware Adaptive Task-Level Recursion Budgeting
Dynamically allocate test-time exploration budgets using early rollout divergence and early-stopping checks so agents avoid wasting inference tokens on easy or saturated tasks.
Time
Compute level
Resources
What the paper used
Prerequisites
Scope
The Gap
In Section 2.2.2 and Section 4 (Figure 6), task-level recursion fixes both the recursion structure (parallel or sequential) and the exploration budget k (e.g., k=1 or k=5) in advance for every incoming task in the stream.
“Future work could allocate exploration according to task difficulty and the relevance of prior experience, or stop when additional probes yield little new evidence.”
Limitation
Applying a uniform fixed budget k across all tasks incurs substantial inference cost (up to tens of millions of tokens per task on JobBench) on straightforward tasks where the base harness already succeeds, while failing to adaptively switch between parallel width and sequential depth when probes stop yielding new evidence.
Proposed Solution
Replace the static budget k with a two-stage adaptive controller: (1) execute a small initial pilot of k_0=2 base rollouts plus a lightweight static/trajectory diagnostic (checking tool-error rates, empty deliverables, and inter-rollout behavioral divergence) alongside library retrieval confidence; (2) bypass refinement entirely (returning the verified base output) when pilot rollouts agree cleanly with zero tool or structural errors and high confidence; (3) otherwise trigger iterative contrastive steps that compute a marginal information-gain score across consecutive probe diffs and trajectory contrasts, terminating recursion early when candidate behavioral contrasts converge or switching to sequential refinement if initial parallel probes expose multi-step procedural dependencies.
The paper’s authors list this direction as future work, so they may already be pursuing it.
Why This Matters
This is expected to improve the compute-performance Pareto frontier by reducing average token consumption per task while reserving deeper exploration budgets for genuinely difficult or novel tasks.
How to Get Started
How to test it: Test the hypothesis that adaptive pilot gating and contrast-saturation early stopping match or beat fixed k=5 Harness^2 scores at significantly lower average token cost per task on JobBench and WorkBuddy-Bench. Plot the Pareto frontier against fixed k=1 and k=5 Harness^2 using task score and total tokens per task; stop if adaptive budgeting degrades mean score by >1.5 points relative to fixed k=5 at comparable compute.
- Analyze per-task trajectories from k=1 and k=5 runs in github.com/google-research/harness2 on WorkBuddy-Bench and JobBench to quantify how often base runs already match k=5 performance.
- Design a lightweight divergence and error-signal classifier over k_0=2 base trajectories (measuring tool-error counts, artifact completeness, and deliverable agreement) without seeing ground-truth scores.
- Implement early-exit gating and marginal-contrast stopping inside the parallel and sequential recursion loops.
- Benchmark the adaptive controller against fixed k=1, k=3, and k=5 Harness^2 on the compute-performance Pareto curve.
Suggested by AI. Adapt it to your setup.
Has This Been Done?
Papers [1], [2], and [3] investigate adaptive test-time compute and budget allocation for reasoning tasks. The proposed idea adds a specific two-stage pilot and information-gain-based termination logic that is not covered by these existing adaptive budgeting approaches.
- What If We Allocate Test-Time Compute Adaptively? · 2026 · 7 citations
- Uncertainty-Aware Budget Allocation for Adaptive Test-Time Reasoning · 2026 · 2 citations
- Early Verdicts, Better Budgets: Sequential Adaptive Rollout Allocation for Compute-Efficient RLVR · 2026 · 1 citations
We searched OpenAlex and arXiv for “adaptive test-time compute allocation early stopping agents” and “Difficulty- and Saturation-Aware Adaptive Task-Level Recursion Budgeting” and an AI compared the idea with the top 10 results. A small search can miss relevant work.
Source Paper
Harness^2: Recursive Agent Harnessing for an Open WorldRuiyao Xu, Yanfei Chen, Zhongying CuiZhu +6 more · 2026
This paper introduces Harness^2, a plug-and-play recursive agent harnessing framework that enables LLM agents to optimize their execution harnesses at test time in open-world settings without ground-truth verifiers. It couples task-level contrastive refinement (Propose-Probe-Compose) with harnessing-level recursion that distills reusable harness components and lessons into an evolving improvement library across tasks.
Related Ideas
- Uncertainty-Aware Proposal and Rollout Allocation for Continual Recursive Self-ImprovementSelf-Improvement Memory Enables Continual Recursive Self-Improvement🟠Medium
- Backtracking Search for Multi-Step Coding ChainsGLM-5: from Vibe Coding to Agentic Engineering🟡Fairly easy
- Feedback-Loop Retrieval VerificationSimpleMem: Efficient Lifelong Memory for LLM Agents🟢Easy
- Multi-Shape Generalization and End-to-End Workload Evaluation for NPU Kernel OptimizationAscendGYM: A Cost-Aware Kernel Optimization Benchmark for Real-World Workloads on Ascend NPUs🟠Medium
- Verifiable Tree-Search with Partial State FeedbackDeepPlanning: Benchmarking Long-Horizon Agentic Planning with Verifiable Constraints🟠Medium