Skip to content

EnCompass: Enhancing Agent Programming with Search Over Program Execution Paths

🕒 Published (v1): 2025-12-03 08:50 UTC · Source: Arxiv · Venue: NEURIPS 2025 · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

EnCompass introduces probabilistic angelic nondeterminism (PAN), a Python programming model that cleanly separates an agent's core workflow logic from its inference-time search strategy. Programmers annotate "locations of unreliability" (LLM calls) with branchpoint() statements; the framework compiles the function into a search space object over which any search algorithm (BFS, beam, MCTS, best-of-N, etc.) can then be applied by changing a single parameter. This decoupling reduces the code overhead of adding sophisticated search to program-in-control agents by 3–6×.

Problem

Current "program-in-control" agent frameworks (LangChain, DSPy, AutoGen) entangle the core workflow logic with the inference-time scaling strategy. Adding beam search or tree search to an existing agent requires restructuring it into an explicit state machine, obscuring control flow, breaking static type checking, and making it prohibitively expensive to experiment with multiple strategies. There is no framework that lets programmers swap inference-time strategies independently of workflow logic.

Method

EnCompass implements PAN as a Python decorator (@encompass.compile) that transforms a normal Python function into a search space object at runtime. The programmer inserts two new primitives: - branchpoint() — marks a program location where execution can branch (typically before an LLM call); the runtime snapshots the program state and adds it as a node in a search tree. - record_score(score) — emits a scalar signal that guides the search policy.

The compiled function becomes a Markov chain over program states (location + memory). A search policy chooses nodes, calls checkpoint.step() to stochastically sample the next program state, and explores the resulting tree to find the highest-scoring terminal path. Common strategies (best-of-N, beam search, BFS, refinement with memory, self-consistency, MCTS-style best-first) are all expressed as instances of this search, selectable via func(...).search("beam", beam_width=2, default_branching=3). Cross-branch shared mutable state (for refinement memory) is supported via a NoCopy type annotation.

Key Contributions

  • The PAN programming model: formalizes inference-time strategies as search over nondeterministic program execution paths, modeled as a Markov chain.
  • EnCompass Python library: decorator-based compiler, branchpoint()/record_score() primitives, built-in algorithms (DFS, BFS, beam, best-first), and a Checkpoint API for custom search algorithms.
  • Unification result: shows that best-of-N (global and local), beam search, refinement, backtracking with memory, self-consistency, and CodeT-style group evaluation are all special cases of PAN search.
  • Three case studies demonstrating 3–6× code reduction and ability to discover better-scaling inference-time strategies that are impractical to implement without the framework.

Results

  • Code Repository Translation (Case Study 1, Java→Python, MIT OCW ps0–ps4): Beam search at both file and method level ("beam coarse + beam fine") outperforms global best-of-N and local best-of-N at matched cost (p < 0.03 vs. all other strategies). Performance scales log-linearly with cost (all χ² p-values > 0.3), consistent with prior inference-time scaling literature.
  • Code modifications: EnCompass reduces added/changed lines by 3–6× across all three case studies vs. equivalent plain Python state machine implementations (e.g., Case Study 1: +423 lines added without EnCompass vs. +75 with; 20 new function definitions reduced to 1; 189 indentation-changed lines reduced to 0).
  • Case Study 2 (Hypothesis Search, ARC subset): BFS and global best-of-N perform equally; primary benefit is implementation simplicity.
  • Case Study 3 (Reflexion, LeetCodeHard): Scaling N in best-of-N or search steps in best-first search outperforms increasing refinement iterations in vanilla Reflexion.

Limitations

  • Targets only program-in-control style agents; explicitly not designed for LLM-in-control agents (e.g., SWEBench, WebArena-style tool-calling agents).
  • Programmers must still manually identify where to place branchpoint() statements and design intermediate reward/verification signals — both require domain expertise.
  • No fully automated branchpoint placement; source code modifications remain necessary.
  • The framework itself does not address the engineering challenge of designing good search algorithms for a given task.

Relevance to Agentic AI / LLM Agents

EnCompass directly addresses a core engineering bottleneck in building reliable program-in-control agents: the conflation of workflow logic with search strategy. By making inference-time scaling strategies (beam search, MCTS, refinement) first-class, swappable components, it lowers the barrier to exploring compute-scaling laws for agents — analogous to what DSPy did for prompt optimization. The PAN model also provides a clean theoretical unification of disparate agentic patterns (Tree of Thoughts, Reflexion, Hypothesis Search) as special cases of nondeterministic program search. This is directly relevant to anyone building agents that must be reliable on multi-step tasks, as it makes it tractable to discover which inference-time strategy best fits a given workflow without rewriting the agent from scratch.