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 a Python framework implementing probabilistic angelic nondeterminism (PAN), which decouples an agent's core workflow logic from its inference-time search strategy. The programmer annotates "locations of unreliability" with branchpoint() calls; the @encompass.compile decorator compiles the function into a search-space object over which any search algorithm can then be applied by changing a single parameter. This eliminates the need to rewrite agent code when switching between best-of-N, beam search, refinement, or tree search.

Problem

Existing agent programming frameworks force developers to hard-code inference-time strategies (sampling loops, tree search) directly into agent workflow code. This entanglement reduces readability, prevents reuse of search implementations across agents, and makes it impractical to experiment with more sophisticated strategies (e.g., beam search within a loop) because each requires substantial structural code changes.

Method

EnCompass implements PAN by modeling agent execution as a Markov chain over program states. The programmer decorates their function with @encompass.compile and inserts two primitives:

  • branchpoint(**params) — marks a nondeterministic location; the runtime snapshots program state here, enabling branching into multiple execution paths.
  • record_score(score) — records a numerical signal to guide the search policy (heuristic, value function, or group evaluator).

The decorator compiles the function body into a search space object at runtime. Search is invoked via .search(algo, **config), where algo is a string (e.g., "dfs", "beam"). The Checkpoint abstraction exposes a step() method that resumes execution to the next branchpoint, enabling custom search algorithms. Shared mutable state across branches is handled with NoCopy type annotations, enabling refinement-with-memory patterns. Standard inference-time strategies unify as special cases: global best-of-N is beam search with beam width \(N\) and branching factor 1; local best-of-N is beam width 1 and branching factor \(N\); general beam search interpolates between them.

Key Contributions

  • PAN programming model: formal separation of search policy (inference-time algorithm) from search space specification (agent workflow) via angelic nondeterminism.
  • EnCompass Python library: @encompass.compile decorator, branchpoint()/record_score() primitives, out-of-the-box search algorithms (DFS, BFS, beam, best-first, MCTS-style), and a Checkpoint interface for custom algorithms.
  • Unifying framework: shows that best-of-N, beam search, refinement, backtracking with memory, self-consistency, and group evaluation (CodeT-style) are all special cases of PAN search.
  • Empirical case studies: three program-in-control agents re-implemented in EnCompass, demonstrating 3–6× reduction in added/changed lines of code compared to plain Python equivalents.

Results

  • Code modification overhead (EnCompass vs. plain Python):
  • Code Repository Translation (base LoC = 597): without EnCompass +423 lines / +24 changed; with EnCompass +75 lines / +8 changed — ~5.6× reduction in added lines.
  • Hypothesis Search (base LoC = 11): without +21 lines; with +8 lines.
  • Reflexion (base LoC = 20): without +27 lines; with +9 lines.
  • Case Study 1 (Java→Python repo translation): fine-grained beam search at the method level outperforms global best-of-N and local best-of-N; beam search demonstrates better inference-time scaling.
  • Case Study 2 (Hypothesis Search on ARC subset): BFS and global best-of-N perform comparably; plain Python version requires 2 new function definitions and 10 indentation-level changes versus 0 with EnCompass.
  • Case Study 3 (Reflexion on LeetCodeHard): increasing \(N\) in best-of-N or search steps in best-first search scales better than increasing refinement iterations in vanilla Reflexion.

Limitations

  • Targets only program-in-control style agents; explicitly excludes LLM-in-control agents (SWEBench, WebArena).
  • No head-to-head benchmark comparisons against SOTA agent frameworks on standard leaderboards — paper is primarily a programming-model contribution.
  • Shared mutable state (NoCopy) is fragile: correctness depends on using in-place mutation (.append()) rather than rebinding, which is a non-obvious invariant.
  • Branching factor and beam width must still be tuned; EnCompass eases experimentation but does not automate strategy selection.
  • Parallel branch execution overhead and memory scaling are not analyzed for large branching factors.

Relevance to Harnesses / Meta-Harnesses

EnCompass is structurally a meta-harness: it wraps an agent workflow via a decorator, intercepts execution at annotated points, and injects an externally-specified control strategy without modifying the agent's logic. This is the canonical meta-harness pattern — the harness owns the execution loop, the agent owns the computation. The branchpoint() annotation mechanism is a form of declarative instrumentation that meta-harnesses can exploit to multiplex, retry, or search over inner-agent executions. For researchers building or studying harnesses, EnCompass demonstrates how separating the specification of a search space from the policy that navigates it enables composable, reusable harness infrastructure — a direct design principle applicable to meta-harnesses that orchestrate multiple agents or tools.