Skip to content

Latest commit

 

History

History
498 lines (393 loc) · 28.9 KB

budgeted-research-planning.md

File metadata and controls

498 lines (393 loc) · 28.9 KB

Budgeted Research Planning: Goals, Theory and Design Rationale

中文

This companion explains why LoopX should compare conditional research plans by their final accepted outcomes within a resource budget. It supports the joint Target/Yardstick/Stride RFC and the EdgeBench pilot. Those RFCs own requirements and acceptance; this is an explanatory design basis, not a new runtime policy, empirical result or mandatory per-Turn prompt.

Read §§1–3 for the objective and planning model, §§4–6 for feedback and evidence, and §§7–9 for the existing implementation, first experiment and learning path. All numerical examples below are illustrative, not benchmark measurements.

1. The goal: better use of a long budget

LoopX keeps goals, state, evidence and decisions available across work sessions. That infrastructure is useful only if it helps an agent deliver better outcomes at comparable total cost, or comparable outcomes at lower cost and attention. More durable records, longer activity and more replans are not that outcome.

There are two research loops:

  • Within a task: improve candidate artifacts, learn which routes work and choose measurements while the budget runs down.
  • Across tasks/runs: improve the research policy itself, eventually learning forecasts or allocation rules from qualified experience.

Success in the first loop does not establish recursive improvement of the second. Near-term work uses the current model and existing decision owners to improve EdgeBench continuation. A learned Meta Model is a later research stage, not a prerequisite for testing whether better planning instructions help.

Let x0 be the starting candidate, X_B^π the candidate selected by the task's declared terminal rule after policy π uses budget B, and F the accepted outcome in a higher-is-better orientation:

$$ J_\pi(B\mid s_0)=\mathbb E[F(X_B^\pi)\mid s_0]. $$

For a common starting state, maximizing J also maximizes expected improvement over F(x0): the common baseline cancels. Precise knowledge of the initial absolute score is not required to compare policies, but starting evidence, headroom, candidates and evaluator state still matter.

The practical target is incremental benefit over a strong continuation:

$$ \Delta J(B\mid s_0) =\mathbb E[F(X_B^\pi)-F(X_B^{\pi_0})\mid s_0]. $$

If both start at 60, LoopX reaches 70 and the comparator reaches 68, within-run progress is 10 while incremental benefit is 2. The comparator keeps working; it is not a frozen starting artifact. The full experiment therefore retains strong Official continuation and current LoopX, not only a weakened ablation.

Budget B can constrain wall time, tokens and evaluator resources separately. Equal wall time does not imply equal compute. Planning, context reads, failed experiments, yardstick repair and confirmation consume those resources. Parallel durations cannot simply be summed into wall time. Under a fixed-budget outcome objective, the opportunity cost is the other work displaced; do not also subtract an invented score penalty for the same expense. A monetary objective requires an explicit conversion to utility.

2. From selecting fixed candidates to creating better ones

Selecting Computations studies computations that reveal information about fixed candidates. Program research also changes candidates and the instruments used to evaluate them:

Activity What changes Why it can matter at the horizon
Test an unchanged candidate Belief about its quality Select the right candidate or abandon a misleading route
Change an implementation or algorithm The candidate itself Create an outcome that was not available before
Build/calibrate a yardstick Future measurement quality/cost Make many subsequent decisions more informative

These benefits can overlap; they are not independently additive reward terms. Repeated measurements of different code versions are not iid samples of one fixed success probability. A low score may be useful evidence, and a high proxy score may contribute nothing to final accepted quality.

For explanation, suppose action a uses known positive resource k(a). Let b be remaining budget and G(s) the expected outcome if research ends now under the declared candidate-selection rule:

$$ V^_(s,b)=\max\left{G(s), \max_{a:k(a)\le b}\mathbb E[V^_(S',b-k(a))\mid s,a]\right}. $$

This is a budgeted Bellman model, not the paper's utility-minus-cN objective. The expectation includes all later choices, not just the next score delta. Real actions have uncertain duration, overlapping resource occupancy, pending results and evaluation availability; implementations must preserve those facts rather than pretend every command is one equal-cost step.

A useful state distinguishes candidate versions and retained valid results, unresolved prerequisites, evidence scope/uncertainty, pending experiments, remaining resources and time for final confirmation. A posterior mean alone cannot distinguish little evidence from strong evidence with the same mean. The simple Beta model admits two sufficient counts; real research does not therefore admit a universal two-number state or require rereading every log.

Stopping a route can free resources for another. Ending the whole run has no automatic budget-saving benefit when unused budget has no other value. Existing completion, exhaustion, permission and resource limits remain legitimate stops; the objective does not require useless activity until a timer expires.

3. Why compare plans, not just immediate gain/cost

Information is valuable when it can change a useful later decision. A first probe may not change today's winner but may enable a second probe that does. Likewise, a correctness harness or algorithm skeleton can be necessary before any scored improvement becomes possible.

A deterministic example exposes the limit of greedy ratios. With budget 8, action A costs 1 and gains 2 but is available only twice; plan B costs 8 and gains 10 only on completion. A has the higher immediate gain/cost, but taking it first prevents completing B and yields at most 4. Ratios can screen routes; they do not solve dependencies, indivisible investments or deadlines.

Priority also depends on competing routes and the remaining horizon. Even independent candidate uncertainties do not imply independent decision values: changing the best alternative can change which candidate is worth measuring. The paper's non-indexability example rules out a generally optimal ranking based only on each candidate's own state.

Use a short conditional continuation: necessary setup, an observation that distinguishes outcomes, and the next response to each material outcome. Execute its first coherent slice and reconsider when useful evidence arrives. Long-term planning means allowing justified delayed payoff, not protecting a plan from counterevidence or demanding a method switch at every review.

Where the expectations come from

Bellman notation does not provide a transition model. In the paper, a posterior can explicitly predict the next observation; program research usually has only mechanism arguments, comparable experience and uncertain estimates.

For a synthetic example, a safe route has expected gain 2.8, while a new route adds 20 with probability p and otherwise retains the same valid incumbent. Both routes include all work through the same deadline. The new route wins when:

$$ 20p>2.8\quad\Longleftrightarrow\quad p>0.14. $$

The useful question is whether evidence puts p above that threshold, not whether an LLM can confidently invent “25%.” Use mechanism/headroom analysis, cheap discriminating probes, comparable past episodes, ranges and sensitivity checks. Record predictions before results, then calibrate success, gain and duration against what happened. Missing evidence remains unknown.

What the finite dynamic program teaches

The paper's VPI/c bound limits expected computation count; it is not a safe fixed truncation depth. For one Beta(1,1) candidate versus known λ, a stronger condition guarantees stopping once c ≥ λ(1−λ)/(n+3). This gives a depth H=O(1/c). Success/failure histories with the same counts (a,b) merge, leaving only 1+2+…+(H+1)=O(1/c²) states. Backward induction compares stopping with −c+pV(a+1,b)+(1−p)V(a,b+1), using complete continuation values.

The paper precomputes 129 λ grid points and interpolates. Its blinkered policy evaluates one direction at a time against the best other current mean, then reconsiders after an observation. Precomputation is O(D/c²), while scanning k candidates online is O(k). Grid interpolation and single-direction planning remain approximations to the general multi-candidate problem.

The transferable idea is to reuse valid sufficient state and amortize repeated decision work. It is not a claim that LoopX has this small state space. Learned or cached estimates must still match the candidate, measurement assumptions and remaining horizon; c=0 cannot be substituted into these bounds for a hard-budget task. A full dynamic-programming solver is not required for the first pilot.

4. Milestones are state before they are reward

“Executable → correct → within the tail-latency limit → improved native score” describes dependent conditions. They can be reversible, shared across routes or replaced by an alternative route. If all are necessary, their joint probability uses conditional factors, not a product of independent marginal success rates.

Keep three feedback meanings distinguishable:

Feedback Example What it does not establish
Accepted outcome change A valid candidate improves the task outcome Which previous action caused the whole gain
Progress state A prerequisite now holds for this version Guaranteed final improvement
Information change A counterexample defeats a local assumption A better artifact already exists

This state helps choose the next work without awarding one point per milestone. Counting easy steps, repeatedly repairing the same defect or ignoring regressions can produce reward without improving the intended result.

For a fixed scalar outcome rule, signed differences telescope:

$$ \sum_t[F(x_{t+1})-F(x_t)]=F(x_T)-F(x_0). $$

Do not add the terminal outcome again or discard negative changes. If the task selects a best valid submission, use that declared quantity consistently rather than mixing it with current-workspace quality. Repeated selection on noisy measurements still needs evaluation safeguards.

For a future learner, potential-based shaping offers a more general accounting:

$$ r'_t=r_t+\Phi(s_{t+1})-\Phi(s_t),\qquad \sum_t r'_t=\sum_t r_t-\Phi(s_0). $$

in the undiscounted finite task when every true terminal potential is zero and time/budget is represented as needed. Discounted tasks use γΦ(s')−Φ(s); truncation is not termination, and changing the potential online needs consistent accounting. Policy invariance does not guarantee easier finite-budget learning. The potential difference is a trajectory change, not a causal action label. These are design constraints for a later learner, not a new runtime reward API.

5. Yardstick: information quality is part of the plan

A useful local measurement can be modeled as:

$$ Z_{\mathrm{local}}(x)=F(x)+b_{\mathrm{local}}(x)+\epsilon. $$

More local samples can reduce random noise ε without removing systematic bias b. A local holdout still uses that measurement system. Mean improvement can also hide a correctness or timeout violation that invalidates the whole submission. Multi-fidelity optimization provides this problem frame; its particular surrogate assumptions are not automatically valid for program search.

Check fidelity at actual selection decisions: matched parent/child or sibling candidates, exact workload/evaluator versions, and relevant validity boundaries. High correlation across a rising historical score curve can merely track time; it need not distinguish the next useful change. When affordable and informative, audit uncertain or proxy-rejected candidates too, so false negatives are visible. A reversal is scoped counterevidence, not proof that a whole evaluator family must be permanently blacklisted.

Native confirmation can qualify a candidate, redirect research or calibrate the proxy. Its value includes how it changes later choices. A pending result is not failure or measured gain. Cooldown and queue availability are separate from compute cost; waiting may overlap independent work. Plan backward from the deadline so a candidate can actually receive the confirmation required by the frozen terminal rule. Do not manufacture extra evaluation opportunities.

6. Why action logs are not causal labels

"At state s, switch was selected; two hours later the next Native result improved by one point" is useful evidence, but not "switch added one point over continuing grow." If a matched grow branch improved by two points, switch made +1 progress but had a −1 contrast. Without executing or credibly identifying the comparator, that contrast remains unknown. Two hours may only be the interval to the next measurement, not the remaining research horizon. Earlier implementation, calibration and exploration may also contribute; the last action does not own the whole observed gain.

The observed fraction of gains after grow, verify or switch mixes different starting states. Grow may be selected after promising evidence; switch after a route stalls. Their raw frequencies cannot rank the actions at one shared state. Nor does a flat incumbent prove a particular check prevented a regression.

A local comparison can instead target:

$$ \tau_B(s;a,a_0,\pi) =\mathbb E[Y_B^{a,\pi}-Y_B^{a_0,\pi}\mid S_0=s]. $$

This compares intervening with a or a0 at the same start and then using the same continuation rule π within B. Later actions can differ in response to new evidence; forcing identical later actions would remove the information benefit. Already spent resources and the cost of the first action must be accounted for consistently.

Credible experiments need well-defined treatment versions (consistency), comparable or randomized assignment (exchangeability), and coverage of feasible alternatives in target states (positivity). Shared mutable memory, evaluator sessions or caches can create interference. Repeated seeds improve precision but do not fix missing state or unobserved alternatives.

Two generalization questions remain separate:

  1. Does a candidate improve beyond checks used to develop it?
  2. Does the controller improve outcomes on tasks not used to tune/select it?

Freeze the controller and evaluation protocol before a new-task test. This freezes how feedback is used, not the evolving candidate or the agent's ability to react to permitted Native feedback during that test. Repeatedly tuning the controller on test outcomes consumes that test set's independence. A checkpoint fork estimates continuation from that state; it does not establish the from-start effect of the full policy.

7. A complete decision-to-outcome example

The following is a synthetic interpretation of the existing decision path, not a schema or prescribed tool order. The run has a valid incumbent, a local speed gain with untested tail behavior, another feasible route, a pending evaluation window and a fixed deadline.

Boundary Reasoning and work Durable evidence / next decision
Restore state Check candidate/evaluator versions, incumbent, pending work and remaining resources Unknown or omitted feedback remains a retrieval need
Compare continuations Continue tuning versus establish a discriminating stress check, then confirm if useful Explain the prerequisite, expected range and comparator
Forecast before work State which result would justify more investment, which would refute it, and whether confirmation can finish Prediction and source basis in existing reasoning/finding
Execute a bounded slice Run the selected check; independently useful work may continue while waiting Actual method, artifact, result and resource use
Interpret feedback Suppose the fast candidate violates a tail constraint Revise that route/yardstick scope; preserve the valid incumbent
Continue and confirm Repair or pursue the alternative, using the remaining authorized opportunity Bind accepted result to the exact candidate and frozen rule
Assess policy benefit Compare matched continuation or complete runs Good local reasoning alone is not evidence of aggregate gain

The useful loop is: decision-time state → prediction and choice → actual work and cost → observation → revised continuation → accepted terminal outcome. Keep failed/cancelled work, delayed results and unknowns. Attribute dependencies across the sequence instead of giving all terminal gain to its last action.

The most useful feedback explains why the action seemed worthwhile then, which key forecast was supported or refuted, and how that changed the next choice. A tail counterexample can refute the premise for a wider tuning sweep; subsequent work should address that question. Evidence-backed continuation also counts as adoption when new evidence supports the original route; switching is not mandatory.

8. Existing owners and the smallest useful next experiment

Source snapshot: bd2af5e. This audit describes source, not installed adoption or measured benefit.

Owner / boundary Available basis What remains to establish
Stride Decision axes, next probe, previous review; bounded Explore measurement/yardstick feedback Whether the model uses it to improve the next continuation
Yardstick Profiles, cited measurements, ordering counterevidence, proposed method/cost boundary Calibrated fidelity, transition/value prediction and useful confirmation choices
Followthrough Previous decision and subsequent evidence Actual adoption, causal contribution and total outcome benefit
EdgeBench adapter Frozen feedback/selection, submission constraints and result lineage A qualified same-state restore for each proposed checkpoint comparison

PRs #8382 and #8385 are merged at this snapshot. They make evidence reachable; they do not supply numerical fidelity, an optimal planner or a learned policy. The current single-agent path is sufficient for the first treatment; a second controller session is not a prerequisite.

The existing pilot contract remains the experiment owner:

  1. Pin a bounded planning instruction on the existing Stride/Yardstick/Explore path, keeping defaults and wire fields unchanged. Demonstrate actual decision-to-work readback before expensive comparisons.
  2. Compare current LoopX with that treatment at prospectively selected, genuinely restorable checkpoints. The proposed 3 tasks × 2 checkpoints × 2 arms × 3 hours is 36 additional worker-hours, not the total study cost.
  3. Account separately for creating those states, control and evaluation. Preserve Native history/cooldown; if equivalent restoration is unavailable, use a correctly labeled from-start comparison. An uninformative short horizon does not justify relaxing the protocol.
  4. Follow promising evidence with the proposed matched 18-hour from-start comparison against strong Official continuation and current LoopX. Freeze repeats, margins, resource caps, selection and analysis before confirmation.

A successful first result is a better accepted outcome after paying all overhead, supported by trajectories showing what decision changed and why. More complete forms, extra Native calls or a plausibly intelligent explanation are insufficient. Detailed task choice and run authorization remain in the pilot, not this essay.

9. From useful feedback to a learned research policy

9.1 Learning target: the current action and remaining continuation

A Meta Model used to allocate research budget should estimate value conditional on state, remaining budget and the subsequent policy, not assign grow/verify/switch one fixed success rate each. Let Y_b be the terminal outcome selected under the frozen rule within budget b, a the concrete first action, and π the continuation:

$$ Q^\pi(s,b,a)=\mathbb E[Y_b^{a,\pi}\mid S_0=s],\qquad A^\pi(s,b;a,a_0)=Q^\pi(s,b,a)-Q^\pi(s,b,a_0). $$

The first quantity forecasts the terminal result after starting this way and continuing with π; the second compares another feasible first route. Both include the first action's resource use. Specify a by method, candidate and verification choice; a coarse action name does not define a treatment. A changed π revision, remaining budget or acceptance rule changes the prediction target. One completed trajectory supplies a noisy outcome for the executed route, not the true Q or a complete label for A.

Start with checkable subpredictions: what a probe will show, implementation duration, or whether confirmation can meet the deadline. Then test whether they help choices. Better forecasts need not change action ranking, and better local ranking need not improve the terminal result. Stride chooses how far to pursue a direction, Yardstick identifies measurement scope and confirmation gaps, and the Meta Model estimates conditional value for those choices. Estimates do not replace the existing owners' authority, budget or acceptance checks.

9.2 A reconstructable decision episode

Link the following at meaningful decision boundaries; do not require a form per tool call or a full-trajectory reread every Turn. Reconstruct from existing decision, finding, execution and measurement references. These are semantic requirements, not a new wire schema.

Time What must be recoverable Why it matters
Before selection Visible candidates/incumbent, directions, premises/counterevidence, verification gaps, pending results and remaining resources; source revisions and availability times Forecast from information available then, not a later rewritten summary
Forecast and choice A few feasible alternatives, selected concrete method, key result and duration predictions/ranges, basis, and what would change the next choice Separate the prior reason, uncertainty and retrospective explanation; do not invent precise probabilities
Execution Actual method versus plan and reason for changes, artifact revision, complete resources, failure/cancellation and waiting Proposal is not adoption, adoption is not success; do not double-count overlapping wall time
Feedback and next decision Candidate/workload/evaluator of the observation, when feedback became available, forecast supported/refuted, and actual continuation/revision Late results belong to the originating experiment; a decision uses only evidence then available; pending is not zero
After the episode Continuation revision, relevant prerequisite/subsequent work, terminal result at the frozen horizon and selection rule Preserve delayed value and multi-step dependencies instead of crediting only the last action

Record a source-backed forecast revision before the result is visible. Retain old predictions and new evidence when revising, rather than overwriting the forecast. A two-hour measurement checks the corresponding horizon; an eighteen-hour terminal forecast needs that endpoint or the predeclared missing/cancelled-outcome treatment. Do not relabel a local gain or pending result as terminal success/failure.

9.3 Four data sources with different evidential roles

Data What it can test What it does not establish
Pre-action forecasts and corresponding realized outcomes Probability, gain-range and duration calibration on covered states; report missing/cancelled outcomes separately Unchosen outcomes, or that accurate prediction makes allocation better
Same-candidate Proxy–Native pairs Measurement bias, ordering and scope Proxy improvement as a causal policy gain
Different continuations from the same checkpoint Local contrasts and uncertainty under equivalent restoration, isolation and aligned budgets One pair as an exact expectation, or the policy's from-start effect
Complete new-task runs with a frozen policy Matched-budget terminal benefit and transfer Repeated same-task tuning as independent generalization evidence

Specify the forecast target, horizon, scope and missing-outcome treatment before choosing calibration metrics. Retain all prospectively selected episodes, not only successful forecasts. Calibration data follows the actions actually chosen and usually does not cover every alternative. Off-policy evaluation separately needs coverage and comparability assumptions; unchosen actions are not zero-reward labels. Adjacent episodes from one task and branches sharing a prefix are dependent: hold out tasks/source runs or whole branch families rather than randomly splitting Turns. Shared parent trajectories can cross the training/evaluation split; future peaks, later test answers and post-hoc explanations must not enter decision-time features either.

9.4 Validate progressively through existing owners

First test whether the current model uses this feedback chain to improve EdgeBench continuation; then decide whether a separate learned model is useful:

Stage Learn or demonstrate Evidence that can support it
Current-model planning Better choices at useful evidence boundaries Adopted work and matched outcome/cost comparisons
Calibrated prediction More reliable gain, duration and failure forecasts Predictions recorded before outcomes, evaluated on held-out episodes
Learned allocation Better policies for state and remaining budget Prospective policy comparisons and frozen new-task tests

The pilot's episode readback and separate acceptance levels use the existing experimental budget and feedback protocol. Preserve task/source permissions and candidate/version lineage; diagnostic records do not authorize training. A more complete model or full trajectory warehouse is not a prerequisite for the first useful comparison.

For an implementation or document handoff, preserve the chain: objective and comparator → theoretical reason → existing owner → proposed change → evidence that would show benefit. Keep source implementation, forecast, hypothesis and measured result distinct. A later proposal should change a design because a specified assumption or observation warrants it, not silently promote this explanatory model to a solved optimizer.

Sources and scope

  • Selecting Computations, §§2–6: fixed-candidate metareasoning, complementary information, stopping, context-dependent priorities and blinkered/VOI approximations.
  • BOCA, §§1–3: costly target evaluations and cheaper fidelities; its surrogate assumptions are not established for arbitrary code modifications.
  • Potential-based shaping, §3: reward-transformation conditions, not evidence that every milestone reward accelerates learning.
  • What If, Ch. 1–3: potential outcomes, randomized comparisons and identification assumptions.
  • DuoDiscover and LoopX feedback analysis: motivation for target/yardstick choice and separating startup, continuation and retained outcomes; neither proves this planning treatment works.

The budgeted candidate-creation model and the links between these theories are design synthesis. No new benchmark run, training or policy-benefit measurement was performed to produce this document.