Test-Time Compute for Agents: Beat Random at Equal Cost

Suppose an agent team reviews a pull request with eight agent processes, a debate round, and a final judge. The single-pass baseline reviews it once. In this illustrative case, the team returns a passing review while the baseline misses an issue, but it spends eight agent processes plus the debate and judge calls.

That comparison has not yet shown that the team is smarter. It has shown that more work can buy more chances to succeed.

Test-time compute is the work spent after the model is selected and the task is known. It includes extra samples, longer reasoning, retries, tool calls, search branches, refinements, checker calls, and multiple agents. A compute budget is the limit on that work, measured across dimensions such as model calls, tokens, time, tools, dollars, sandbox minutes, or risk. An execution shape is the arrangement of calls, branches, tools, and stopping decisions used to spend that budget. A runtime is the software that supplies tools, controls turns, spends the budget, and records the run. An agent profile is the model, instructions, tools, skills, permissions, and limits assigned to one run. A trace is the record of the run’s calls, decisions, tool actions, costs, and result. An evaluation compares those traces and outcomes on a stated task set. A selection rule is the rule or component that chooses which candidate result to return. A checker is a repeatable check that supplies evidence about whether a result is correct, complete, safe, or ready to use. A judge is a scorer for qualities that a deterministic checker cannot fully measure. A baseline is the simpler or currently deployed version used for comparison. A candidate is a proposed result or execution policy being compared with the baseline.

The first bar for an agent execution shape is simple:

Beat the best simple way to spend the same budget.

Random sampling is not a straw man. It is the control that tells you whether the new structure adds useful guidance or merely purchases more attempts.

Extra work has a shape

Let x be a task, m a fixed model, r the runtime, a a policy for allocating extra work, and B a budget. The product objective is:

utility(a) = quality(run(m, r, a, x, B)) - cost_penalty

The budget is a vector rather than one number:

B = {
  samples,
  inputTokens,
  outputTokens,
  modelCalls,
  toolCalls,
  wallClockMs,
  sandboxMinutes,
  dollars,
  riskAllowance,
}

Two strategies can spend the same output tokens while one makes more tool calls. They can use the same number of model calls while one runs a costly browser or sandbox action. They can have the same dollar estimate while one creates a much longer wait for the user.

A fair comparison fixes the dimensions that matter to the product or reports the tradeoff plainly.

Strategy	How it spends work	What can make it look better than it is
Repeated sampling	Generates several independent candidates	It is compared with one greedy sample
Self-consistency	Samples several paths and aggregates answers	Wrong paths share the same bias
Refinement	Revises a result after feedback	The feedback is vague or repeats the same error
Checker reranking	Scores candidates and returns the highest one	The checker rewards style instead of correctness
Tree search	Expands and prunes partial solutions	Partial states are hard to evaluate
Multi-agent fanout	Gives one task to several workers	The merger has no reliable winner rule

The execution shape is a policy for spending the budget. It is not proof of quality by itself.

The baseline ladder

Start with the ordinary one-shot result so the product behavior remains visible. Then climb the baseline ladder before introducing a more complicated execution shape.

The single-sample baseline

One sample answers:

y_1 ~ model(prompt, task)
return y_1

It records the product’s first result without selection or retry overhead. It is weak as a complexity baseline because almost any extra work can beat it on a stochastic task.

Random@k

Generate k candidates with the same model and prompt. Choose them with a fixed rule that uses no extra task-specific insight, or report the best deployable simple selection rule.

y_i ~ model(prompt, task) for i = 1..k
return simple_select(y_1, ..., y_k)

This answers the question, “What if we bought k attempts and changed nothing else?”

Pass@k

For a task with an exact checker, pass@k asks whether at least one candidate passes:

pass@k = P(at least one of k candidates passes)

If each candidate succeeds independently with probability q, then:

pass@k = 1 - (1 - q)^k

For q = 0.20 and k = 8, the calculation is:

1 - 0.8^8 = 0.8322

That is an 83.22% chance that a passing candidate appears under the independence assumption. The assumption often fails because model samples share errors. The bigger limitation is selection: pass@k can use the answer key to discover that one sample passed, while a deployed product usually cannot.

Best-of-k with a deployable selection rule

Now use a selection rule that the product can call at runtime:

y_hat = choose(task, y_1, ..., y_k)

The final score of y_hat is the product-relevant measure. The gap between “a good answer appeared” and “the system returned the good answer” is selection loss:

selection_loss = P(good candidate appears) - P(selector returns a good candidate)

When a good candidate appears often but the selector returns it rarely, the generator has coverage but the deployed system is not reliable.

Why random is a hard baseline

Self-consistency, Tree of Thoughts, Large Language Monkeys, and compute-optimal test-time scaling are published examples of repeated or guided sampling. Self-consistency samples multiple reasoning paths and chooses the answer with the largest agreement. Tree of Thoughts makes intermediate states, lookahead, and backtracking explicit. Large Language Monkeys studies what repeated sampling can achieve as attempts increase. Compute-optimal test-time scaling shows that the best allocation depends on task difficulty, model, and checker rather than one universal strategy.

An architecture diagram does not establish that the execution shape is a better allocation of compute. A supervisor, debate loop, or specialist fanout can lose to the same model sampled repeatedly at equal cost. If that happens, the execution shape may still be valuable for interpretability, latency, fault isolation, or a different task mix. The quality claim needs to be narrowed to what the data supports.

OpenAI’s public reasoning-model report also describes performance improving with more reinforcement-learning compute and more time spent thinking at inference. That observation establishes test-time work as a real scaling axis. It does not establish that one agent arrangement is the best way to allocate it.

Parallel, sequential, and guided allocation

Extra work can be spent in different directions.

parallel:
  make k attempts -> verify or select

sequential:
  draft -> critique -> revise -> verify

search:
  expand states -> score partial states -> keep a frontier

tool-evidence-based:
  form hypothesis -> call tool -> observe -> update

Parallel attempts help when candidate diversity is useful and a selection rule can recognize quality. Sequential refinement helps when feedback identifies a local error and the next step can act on it. Search helps when partial states have meaningful checks. Tool-evidence-based work helps when the environment returns evidence that changes the decision.

The controller can observe:

candidate confidence
checker margin
disagreement between attempts
task difficulty estimate
remaining budget
latency deadline

It can then choose:

sample | refine | verify | expand | stop

The controller is itself a policy that needs evaluation. If difficulty estimates are poorly calibrated, adaptive spending becomes unpredictable cost. If the checker is overconfident, early stopping can lock in a fluent failure.

The checker becomes the bottleneck

Each added candidate increases the selector’s ranking burden and the opportunity to choose a polished failure. The checker must distinguish a correct artifact from a polished imitation.

Possible checkers include:

unit tests and integration tests;
typechecks and schema validation;
proof checkers and simulators;
retrieval-backed citation checks;
process or outcome reward models;
calibrated language-model judges;
human review.

Each checker sees a different slice of correctness. Unit tests miss untested behavior. Typechecks miss semantic errors. Proof checkers cover only formalized claims. Language-model judges can reward verbosity, confidence, or rubric mimicry. Human review adds reviewer time and can disagree across reviewers, so report minutes, reviewer count, and agreement alongside the score.

The evaluation should keep observed and true outcomes separate:

observed = checker(task, candidate, trace)
reference = independent_product_check(task, candidate)
checker_gap = observed - reference

If the search optimizes the checker faster than the checker tracks the product outcome, the agent is learning to satisfy its measurement. That is reward hacking in a selection loop.

A pull-request example

Imagine a coding agent asked to update a payment client. The task has an exact test suite, a static analysis pass, and a human review for changes to payment authorization.

For this sample comparison, suppose the budget is eight model calls, 80,000 output tokens, 90 seconds, and one sandbox run:

Policy	Calls	Selection rule	Hard checks
One-shot	1	First result	Tests and static analysis
Random@8	8	Lowest-cost result that passes tests	Tests and static analysis
Fanout	6 workers + 2 merger calls	Merger model	Tests, static analysis, approval
Refinement	4 drafts + 4 critique/revision calls	Last passing result	Tests, static analysis
Adaptive	Starts with 2, adds work on uncertainty	Policy-specific	Tests, static analysis, approval

The comparison is meaningful only if every policy receives the same task, tool set, model family, maximum spend, and final checks. The fanout policy cannot count a passing patch that the merger ignored. The random policy cannot use private test labels to choose a winner unless the product also has those labels at runtime. The adaptive policy must report how often it stopped early and how often it exhausted its budget.

The trace should show branches, calls, tools, test output, selected artifact, approval state, cost, and cancellation. The metrics report should show pass rate, median (p50) and 95th-percentile (p95) latency, token use, sandbox time, and failure class. Those distributions expose tail latency, rare failures, and tasks that exhaust the budget.

Tangle’s execution boundary

The public Tangle agent-runtime repository documents bounded rounds, refine and fanout combinators, validators, and budget limits as separate runtime concepts. Bounded rounds, fanout, refine, validators, and budget limits schedule and cap the additional model calls. Each candidate profile carries the model, tools, instructions, skills, permissions, and limits that shape its work. The resulting trace records the branches, decisions, tool calls, costs, and result. The evaluation compares those traces and outcomes under the stated task set.

The public TypeScript packages document this installation path:

pnpm add @tangle-network/agent-runtime @tangle-network/agent-eval @tangle-network/sandbox

If this workflow is offered as a Tangle service, a Blueprint is the reusable service template and an operator is the party that runs a live service instance from it. A Tangle router sends a typed job to its handler. An x402 request is a paid web invocation whose payment is verified before the job enters the runner. An attestation can provide evidence that a required confidential-computing environment was used. None of those facts is a quality score for the agent’s selected patch. The product still needs a checker and an evaluation that examine the result.

Equal budget does not mean identical experience

Budget matching is necessary, not sufficient. An eight-call strategy can still be worse for a user if its calls run serially while a four-call strategy runs concurrently. A fast strategy can be worse if it creates more dangerous side effects. A cheap strategy can be worse if it requires expensive human review.

Report the full tradeoff:

quality
pass rate
failure distribution
input and output tokens
model calls
tool calls
wall-clock latency
sandbox or browser time
dollars
human review time
trace completeness

Treat quality and cost as a frontier rather than forcing every product decision into one score. Policy A dominates Policy B only when it is at least as good on every relevant dimension and strictly better on one. Otherwise the product owner is choosing a tradeoff.

When extra compute misleads

Unmatched compute lets a candidate win by using more calls, turns, tokens, tools, or time.

Hidden-label selection reports pass@k as if the product could identify the passing candidate without a label.

Correlated sampling produces eight versions of the same mistake and makes diversity look larger than it is.

Checker overfit makes search target the judge’s preferences rather than the task.

Retry theater repeats an invalid tool call without changing the state, evidence, or policy.

Hidden branching reports a multi-agent workflow whose trace contains one actual call.

Tool-cost laundering matches tokens while allowing a candidate to spend much more browser, sandbox, service, or human time.

Early-stop bias reports mean quality without showing that hard cases consume the entire budget.

Trace loss makes it impossible to prove where the extra work went.

Make the equal-cost decision

Use test-time compute when the task has stochastic failures, extra evidence can change the next action, the checker is strong enough to select, and the product can afford the latency and cost.

Do not call an execution shape intelligent because it has more roles. Do not call repeated sampling a solved product because one candidate passed somewhere in a batch. Do not promote a checker that has not been tested against the failure modes it is meant to catch.

The defensible claim is narrower:

Under this model, task set, checker, and budget,
this allocation policy returned better verified outcomes than the simple baseline.

That is the first bar for runtime execution, multi-agent coordination, and any system that calls extra inference “reasoning.”

Sources

What is test-time compute?

Test-time compute is extra work spent after the model is selected and the task is known. It includes repeated sampling, refinement, search, tool use, checker calls, retries, and multi-agent fanout.

Why compare against random at equal cost?

Because a complex strategy has not earned its complexity if it only wins by spending more. An equal-cost repeated-sampling baseline measures the value of guidance, selection, and coordination separately from the value of extra attempts.

Is `pass@k` a deployable agent metric?

Usually not by itself. pass@k measures whether a successful candidate appeared among samples, while a deployed system also needs a selection rule that can find the successful candidate without hidden labels.

Where does this fit in Tangle’s agent stack?

Test-time compute belongs in the runtime and evaluation layers. Tangle’s runtime can provide bounded rounds and execution shapes, while evaluation must compare quality, cost, latency, hard checks, and traces before a new policy replaces the baseline. For the runtime and tooling changes that make those execution shapes possible, continue with agent-runtime harness evolution.