Skip to main content Inicio Creadores adu2021 skillxiv bavt-budget-aware-search
bavt-budget-aware-search Allocate LLM reasoning budget optimally via value tree search: use residual value prediction to estimate step utility, then dynamically shift exploration-exploitation balance as budget depletes. Outperform high-budget baselines at 1/4 cost.
Ir a la instalación Skills Marketplace Descubre y explora habilidades de IA creadas por la comunidad.
Instalar con Codex o Claude Copia este prompt, pégalo en Codex, Claude u otro asistente, y deja que revise la página de la skill y la instale por ti.
Mostrar detalles del prompt Un comando directo omite el prompt de revisión. Revisa el origen antes de ejecutarlo.
npx skills add https://github.com/ADu2021/skillXiv --skill bavt-budget-aware-searchEl comando permanece en una sola línea. Desplázate horizontalmente para revisarlo antes de copiarlo.
¿Prefieres una copia local? Descarga los archivos que SkillsMP tiene disponibles ahora.
Descargar Zip Descargando... Más de este repositorio meaningful-kebab-case-name Convert arXiv papers into ready-to-use agent skills using category-aware extraction. First classifies the paper into one or more of 11 research categories, then applies a specialized extraction pipeline for each category — because different types of papers produce different types of usable knowledge. A single paper can yield multiple skills if it spans categories. Use this skill whenever the user wants to turn a paper into a skill, extract practical techniques from research, build a skill library from papers, convert arXiv papers into reusable agent instructions, or batch-process multiple papers into skills. Also trigger when someone asks about extracting actionable knowledge from papers, making research practical for LLM agents, or systematically converting academic contributions into structured agent capabilities.
action-quantization-behavior-cloning Establish regret bounds for behavior cloning with discretized actions combining statistical error and quantization error terms. Prove smoothness requirements for safe quantizer design, show that learning-based quantizers fail these requirements, and propose model-based augmentation to reduce error dependence from H² to H.
adaptive-lora-personalized-ranks Dynamically allocate LoRA ranks per-layer during fine-tuning instead of using fixed uniform ranks. Learn optimal rank for each layer and subject via variational framework with discretized exponential distribution, reducing memory footprint while maintaining fidelity and text-alignment.
Ocupaciones relacionadas SOC
Basado en la clasificación ocupacional SOC
name bavt-budget-aware-search title Spend Less, Reason Better: Budget-Aware Value Tree Search for LLM Agents version 0.0.2 engine skillxiv-v0.0.2-claude-opus-4.6 license MIT url https://arxiv.org/abs/2603.12634 keywords ["Tree Search","Budget-Aware","Value Estimation","Multi-Hop Reasoning","LLM"] description Allocate LLM reasoning budget optimally via value tree search: use residual value prediction to estimate step utility, then dynamically shift exploration-exploitation balance as budget depletes. Outperform high-budget baselines at 1/4 cost.
Technique: Budget-Conditioned Value Tree Search with Dynamic UCB
Agentic reasoning requires exploring multiple paths, but computational budgets are finite. Budget-Aware Value Tree (BAVT) search makes principled allocation decisions: it estimates marginal utility per step using residual value prediction, then dynamically modulates exploration strength as budget depletes.
The key insight is a power-law scaling exponent inversely proportional to remaining budget, creating smooth transitions from broad exploration to aggressive greedy exploitation.
Core Concept
BAVT operates through three mechanisms:
Step-Level Value Estimation : Critics predict marginal progress (residual value) rather than absolute trajectory valueBudget-Conditioned Node Selection : Dynamic UCB scaling (αt = 1/rt) where rt is remaining budgetTraining-Free Dual-Role LLM : Single model alternates between generator and critic roles
This achieves superior performance under budget constraints: 4× budget-efficient compared to baseline.
Architecture Overview
Generator role : Proposes next reasoning stepsCritic role : Estimates residual value (marginal progress)Value predictor : MLP head for step-level valueTree search engine : Maintains search tree with UCB-based selectionBudget manager : Tracks and allocates remaining compute
Implementation Steps
Step 1: Residual Value Prediction
Critic estimates incremental progress, not absolute returns.
import torch
import torch.nn as nn
class ResidualValuePredictor (nn.Module):
def __init__ (self, hidden_dim=768 ):
super ().__init__()
self .hidden_dim = hidden_dim
self .predictor = nn.Sequential(
nn.Linear(hidden_dim, hidden_dim * 2 ),
nn.ReLU(),
nn.Linear(hidden_dim * 2 , 1
def
forward
self, context_embeddings
"""
Predict residual value from current state.
context_embeddings: (batch, hidden_dim) current reasoning state
returns: (batch, 1) residual value predictions (information delta)
"""
self
return
class
CriticHead
def
__init__
self, model, hidden_dim=768
super
self
self
def
estimate_residual_value
self, trajectory_text
"""
Estimate marginal utility of reaching current state.
trajectory_text: str of reasoning steps so far
"""
self
self
return
Step 2: Budget-Aware Node Selection Dynamically adjust exploration-exploitation trade-off based on remaining budget.
class BudgetAwareUCB :
def __init__ (self, exploration_constant=1.0 ):
self .exploration_constant = exploration_constant
def compute_ucb_score (
self,
node_value,
visit_count,
total_budget,
remaining_budget
):
"""
Compute UCB score with budget-dependent exploration.
Scaling exponent: α_t = 1 / r_t (r_t = remaining budget)
"""
exploitation = node_value / (visit_count + 1e-8 )
exploration_scale = self .exploration_constant / (remaining_budget + 1e-8 )
import math
ucb_score = (
exploitation +
exploration_scale * math.sqrt(
math.log(total_budget + 1 ) / (visit_count + 1e-8 )
)
)
return ucb_score
def select_best_child (self, node, remaining_budget, total_budget ):
"""
Select child with highest UCB score.
"""
best_child = None
best_score = -float ('inf' )
for child in node.children:
ucb_score = self .compute_ucb_score(
child.value_sum,
child.visit_count,
total_budget,
remaining_budget
)
if ucb_score > best_score:
best_score = ucb_score
best_child = child
return best_child
Step 3: Tree Search with Dual-Role LLM Use single LLM model for both generation and critic roles.
class TreeNode :
def __init__ (self, text="" , parent=None ):
self .text = text
self .parent = parent
self .children = []
self .visit_count = 0
self .value_sum = 0.0
self .residual_value = None
class BudgetAwareValueTreeSearch :
def __init__ (self, model, critic_head, budget=1000 ):
self .model = model
self .critic = critic_head
self .total_budget = budget
self .remaining_budget = budget
def search (self, question, max_depth=10 ):
"""
Perform budget-aware tree search for question.
"""
root = TreeNode(question)
ucb = BudgetAwareUCB()
for budget_step in range (self .total_budget):
self .remaining_budget = self .total_budget - budget_step
leaf_node = self ._select_and_expand(
root,
ucb,
max_depth
)
if leaf_node is None :
break
residual_value = self .critic.estimate_residual_value(
leaf_node.text
)
self ._backup(leaf_node, residual_value)
best_path = self ._extract_best_path(root)
return best_path
def _select_and_expand (self, node, ucb, max_depth ):
"""
Traverse tree using UCB, expand at leaf.
"""
current = node
depth = 0
while current.children and depth < max_depth:
current = ucb.select_best_child(
current,
self .remaining_budget,
self .total_budget
)
depth += 1
if depth < max_depth:
next_steps = self .model.generate_next_steps(
current.text,
num_candidates=3
)
for step in next_steps:
child = TreeNode(current.text + "\n" + step, parent=current)
current.children.append(child)
if current.children:
return current.children[0 ]
return None
def _backup (self, node, value ):
"""
Propagate value up tree from leaf.
"""
current = node
while current is not None :
current.visit_count += 1
current.value_sum += value
current = current.parent
def _extract_best_path (self, root ):
"""
Extract highest-value path from root to leaf.
"""
path = []
current = root
while current.children:
best_child = max (
current.children,
key=lambda c: c.value_sum / (c.visit_count + 1e-8 )
)
path.append(best_child.text)
current = best_child
return '\n' .join(path)
Step 4: Training-Free Integration Use model for both roles without additional training.
class DualRoleLLMAgent :
def __init__ (self, base_model ):
self .model = base_model
self .critic_head = CriticHead(base_model)
def reason_with_budget (
self,
question,
budget_tokens=1000 ,
max_depth=10
):
"""
Multi-step reasoning within token budget.
"""
search = BudgetAwareValueTreeSearch(
self .model,
self .critic_head,
budget=budget_tokens
)
best_reasoning = search.search(question, max_depth)
return best_reasoning
def generate_next_steps (self, context, num_candidates=3 ):
"""
Generator role: propose next reasoning steps.
"""
prompt = f"{context} \n\nNext reasoning steps:"
steps = []
for _ in range (num_candidates):
step = self .model.generate(prompt, max_tokens=50 , temperature=0.7 )
steps.append(step.strip())
return steps
def compare_budgets (self, question, budgets=[100 , 250 , 500 , 1000 ] ):
"""
Demonstrate budget-performance trade-off.
"""
results = {}
for budget in budgets:
reasoning = self .reason_with_budget(question, budget)
score = self .evaluate(reasoning, question)
results[budget] = score
return results
Step 5: Benchmark Against Baselines Compare budget efficiency to standard approaches.
def benchmark_budget_efficiency ():
"""
Demonstrate BAVT efficiency gains.
"""
agent = DualRoleLLMAgent(base_model)
questions = [...]
results = {
'bavt' : {},
'baseline_fixed' : {},
'baseline_10x_budget' : {}
}
for budget in [250 , 500 , 1000 ]:
scores = []
for q in questions:
answer = agent.reason_with_budget(q, budget)
score = evaluate(answer, q)
scores.append(score)
results['bavt' ][budget] = sum (scores) / len (scores)
baseline_budget = 1000
scores = []
for q in questions:
answer = agent.reason_fixed_budget(q, baseline_budget)
score = evaluate(answer, q)
scores.append(score)
results['baseline_fixed' ][baseline_budget] = sum (scores) / len (scores)
scores = []
for q in questions:
answer = agent.reason_fixed_budget(q, baseline_budget * 10 )
score = evaluate(answer, q)
scores.append(score)
results['baseline_10x_budget' ][baseline_budget * 10 ] = sum (scores) / len (scores)
return results
Practical Guidance
Multi-hop reasoning with strict token/compute budgets
Interactive settings where latency matters
Resource-constrained deployment scenarios
Questions benefiting from diverse exploration early, exploitation later
Trivial questions requiring minimal reasoning
Unlimited compute available (no budget pressure)
Tasks requiring exhaustive search
exploration_constant : 0.5-2.0; affects early exploration breadthmax_depth : 5-15; balance depth and breadthnum_candidates per node : 2-5; more diversity, higher costbudget allocation : Typically linear; can experiment with quadratic/exponential
Residual values not calibrated (use ground-truth answer for supervision)
Exploration exponent too aggressive (reverts to random at low budget)
Insufficient diversity in candidate generation
Not tracking spent budget (crucial for correct UCB scaling)
Reference 