[ALGO-6] Optimize Tree Operations for Async Parallelization

[MVPandey]

⚡ ASYNC TREE OPTIMIZATION

Priority: LOW - Marginal Performance

Problem

Tree operations (selection, backpropagation) are synchronous while LLM calls are async, limiting parallelization potential.

Location: app/services/mcts/algorithm.py:70-74 - synchronous tree traversal operations

Solution

Optimize tree traversal and node selection for better async parallelization.

async def _parallel_node_selection(self, root: MCTSNode, num_parallel: int = 3) -> List[MCTSNode]:
    """Select multiple nodes for parallel expansion"""
    selected_nodes = []
    available_nodes = [root]
    
    for _ in range(num_parallel):
        if not available_nodes:
            break
            
        # Select best node from available options
        node = max(available_nodes, key=lambda n: n.ucb1_score())
        selected_nodes.append(node)
        
        # Update available nodes (avoid conflicts)
        available_nodes = self._get_non_conflicting_nodes(available_nodes, node)
    
    return selected_nodes

async def _parallel_expansion(self, nodes: List[MCTSNode], config: MCTSConfig):
    """Expand multiple nodes in parallel"""
    expansion_tasks = [
        self._expand_and_simulate(node, config)
        for node in nodes
    ]
    
    results = await asyncio.gather(*expansion_tasks, return_exceptions=True)
    
    # Handle results and update tree
    for node, result in zip(nodes, results):
        if not isinstance(result, Exception):
            self._update_node_with_result(node, result)

Implementation Steps

• Implement parallel node selection
• Add concurrent tree expansion
• Optimize tree traversal algorithms
• Add conflict detection for parallel operations

Expected Benefits

• Marginal performance gains through better parallelization
• Improved resource utilization of async capabilities
• Better scalability for concurrent requests

Effort: Medium (3-4 days)