tape-tool-guided-adaptive-planning

name	tape-tool-guided-adaptive-planning
title	TAPE: Tool-Guided Adaptive Planning and Constrained Execution
version	0.0.2
engine	skillxiv-v0.0.2-claude-opus-4.6
license	MIT
url	https://arxiv.org/abs/2602.19633
keywords	["agent planning","constraint satisfaction","tool use","LLM agents","planning under constraints"]
description	Improve LLM agents operating under strict feasibility constraints (budget limits, tool usage caps) by separating planning from execution. Generate multiple candidate plans, merge into plan graph, then use external solver (ILP) to find optimal feasible path. Constrained decoding forces execution of planned actions, eliminating sampling errors. Adaptive replanning handles observation surprises. Achieves 21+ pp improvements on constrained tasks vs. ReAct.

TAPE: Constraint-Aware Planning for Tool-Using Agents

Language model agents often fail under strict feasibility constraints—budget limits, tool usage quotas, or action count restrictions. Two failure modes dominate:

Planning Errors: The agent's internal reasoning suggests non-viable action sequences that violate constraints or become infeasible mid-trajectory.

Sampling Errors: Even with correct planning, stochastic token generation produces actions different from what was intended, causing the agent to execute unplanned detours.

Standard frameworks like ReAct treat constraint satisfaction reactively—only checking feasibility after deciding. Better to embed constraint awareness into the planning phase, generating feasible action sequences upfront.

Core Concept

TAPE separates planning into three phases:

1. Plan Graph Generation: Multiple candidate plans from the agent, merged into a directed graph where nodes are states and edges are actions
2. Solver-Based Path Selection: External optimizer (ILP) finds the optimal feasible path through the graph, accounting for constraints
3. Constrained Execution: Rather than free generation, the agent is constrained to output only the planned next action using controlled decoding

When observations diverge from predictions, the system replans on updated state, maintaining feasibility throughout.

Architecture Overview

• Multi-Plan Generator: Sample K candidate plans from agent without execution
• Plan Graph Merger: Combine plans into DAG, deduplicating states and merging equivalent actions
• Cost Predictor: Estimate per-action cost (budget consumed, tool calls used, steps taken)
• Constraint Solver: ILP formulation to find lowest-cost feasible path given budget constraints
• Constrained Decoder: Force agent to output only next planned action using prefix constraints or token masking
• Observation Tracker: Monitor actual outcomes vs. predicted; trigger replanning if divergence exceeds threshold
• Adaptive Replanner: Regenerate plans from new observation state if replanning triggered

Implementation

Generate multiple plans and build plan graph:

def generate_candidate_plans(agent, state, num_candidates=5):
    
    plans = []

     _  (num_candidates):
        
        prompt = 
        plan_text = agent.generate(prompt, temperature=, max_tokens=)
        actions = parse_actions(plan_text)

        
        cost = estimate_plan_cost(actions, state)

        plans.append((actions, cost))

     plans

 ():
    
     networkx  nx

    graph = nx.DiGraph()
    state_nodes = {}
    initial_state = 

     plan_idx, (actions, _)  (plans):
        current_state = 
         initial_state  :
            initial_state = current_state

         action  actions:
            
             current_state   state_nodes:
                state_nodes[current_state] = (state_nodes)
                graph.add_node(current_state)

            
            next_state = execute_action_simulation(current_state, action)

            
            action_cost = estimate_action_cost(action)
            graph.add_edge(current_state, next_state, action=action, cost=action_cost)

            current_state = next_state

     graph, initial_state

 ():
    
     pulp  LpProblem, LpMinimize, LpVariable, lpSum

    
    prob = LpProblem(, LpMinimize)

    
    edge_vars = {}
     u, v  graph.edges():
        edge_vars[(u, v)] = LpVariable(, cat=)

    
    objective = lpSum([
        edge_vars[(u, v)] * graph[u][v][]
         u, v  graph.edges()
    ])
    prob += objective

    
     node  graph.nodes():
         node == initial_state:
            
            prob += lpSum([edge_vars[(initial_state, v)]  v  graph.successors(initial_state)]) == 
         node == goal_state:
            
            prob += lpSum([edge_vars[(u, goal_state)]  u  graph.predecessors(goal_state)]) == 
        :
            
            in_edges = lpSum([edge_vars[(u, node)]  u  graph.predecessors(node)])
            out_edges = lpSum([edge_vars[(node, v)]  v  graph.successors(node)])
            prob += in_edges == out_edges

    
    total_cost = lpSum([
        edge_vars[(u, v)] * graph[u][v][]
         u, v  graph.edges()
    ])
    prob += total_cost <= budget_constraint

    
    prob.solve(solver=, msg=)  

    
    path = []
    current = initial_state
     current != goal_state:
         v  graph.successors(current):
             edge_vars[(current, v)].varValue == :
                action = graph[current][v][]
                path.append(action)
                current = v
                

     path