Research map / Multi-agent systems and games / LLM agents
EnCompass: Enhancing Agent Programming with Search Over Program Execution Paths
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces the EnCompass Python framework and probabilistic angelic nondeterminism (PAN) programming model, which lets programmers add branchpoints to agent workflows and apply search (BoN, beam, BFS, best-first) over execution paths without rewriting the workflow.
Problem
Inference-time strategies (tree search, beam search, refinement with backtracking) in program-in-control LLM agents are entangled with core workflow logic, making them inflexible, hard to read, and costly to implement and experiment with.
Approach
Treat inference-time strategies as search over execution paths of a probabilistic program: a Python decorator compiles a function with branchpoint() and record_score() calls into a search space, and search algorithms (BoN, beam, DFS, BFS, best-first) are selected by a single parameter, extending angelic nondeterminism to sampled LLM outputs.
Key results
- On the Java-to-Python translation ps0, beam search at both file and method levels gave the best log-linear cost scaling, outperforming global and local best-of-N with p < 0.03.
- On ARC-AGI subset with GPT-4o, global best-of-N (N=36) reached 38.7% and BFS reached 38.3%, versus 24.0% for the two-step base agent and 32.7% for the reproduced ADAS agent.
- On LeetCodeHard with Reflexion, EnCompass BeFS matched Reflexion's accuracy at lower cost (e.g., 36.1% at $0.168/task vs. Reflexion 35.5% at $0.279/task in the low setting).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Add global best-of-N sampling | Two-step agent · ARC-AGI subset | accuracy: 4.3 ± 0.9 -> 11.7 ± 0.8 (GPT-3.5, N = 8); 4.3 ± 0.9 -> 16.0 ± 1.0 (GPT-3.5, N = 36); 24.0 ± 1.5 -> 36.3 ± 1.1 (GPT-4o, N | Helped |
| Use BFS with branching = 8 instead of the base two-step agent | Two-step agent · ARC-AGI subset | accuracy: 4.3 ± 0.9 -> 15.0 ± 0.9 (GPT-3.5); 24.0 ± 1.5 -> 38.3 ± 1.2 (GPT-4o) | Helped |
| Replace global best-of-N with BFS, branching = 8 (ablation) | Two-step agent · ARC-AGI subset | accuracy: 16.0 ± 1.0 vs. 15.0 ± 0.9 (GPT-3.5); 38.7 ± 1.1 vs. 38.3 ± 1.2 (GPT-4o) | No clear effect |
| Add the second branchpoint before the second LLM call, using BFS with branching = 8 (ablation) | Two-step agent · ARC-AGI subset | accuracy: 11.7 ± 0.8 -> 15.0 ± 0.9 (GPT-3.5); 36.3 ± 1.1 -> 38.3 ± 1.2 (GPT-4o) | Helped |
| Use reexpand best-first search instead of vanilla Reflexion refinement scaling | Reflexion · LeetCodeHard | cost/task at comparable accuracy: 35.9 ± 1.3 at 0.449 ± 0.005 -> 36.1 ± 1.1 at 0.289 ± 0.007; 38.2 ± 1.2 at 0.736 ± 0.010 -> 38.1 ± 1.3 at 0.512 ± 0.006 | Helped |
| Add best-of-N sampling to Reflexion (ablation) | Reflexion · LeetCodeHard | accuracy: 35.5 ± 1.0 vs. 35.5 ± 1.0 (low); 38.2 ± 1.2 vs. 37.6 ± 1.7 (high) | No clear effect |
| Increase the number of refinement loops in vanilla Reflexion (ablation) | Reflexion · LeetCodeHard | accuracy: 35.5 ± 1.0 -> 35.9 ± 1.3 -> 38.2 ± 1.2 | Helped |
| Use fine-grained beam search at both file and method levels instead of simpler sampling strategies | Java-to-Python code repository translation agent · MIT OCW Software Construction repositories | self-validation (%) | Helped |
| Use BFS instead of global best-of-N (ablation) | Simplified Hypothesis Search agent · ARC benchmark subset | evaluation score | No clear effect |
Surprising findings
- The best-performing strategy for code translation (beam at both levels) is also the hardest to implement in plain Python, so the framework unlocks combinations programmers would otherwise avoid.
- On ARC, best-of-N and BFS performed comparably, suggesting that the extra branching structure did not add accuracy beyond simple sampling.
Limitations
- Requires source-code modifications (adding branchpoints, scores, and a search algorithm choice), and choosing branchpoint locations and good verification signals remains an engineering challenge.
- Targets only program-in-control style agents, not LLM-in-control agents such as SWE-bench or WebArena.
- Evaluations are small-scale (one small repo for hyperparameter search, 60 ARC tasks, 40 LeetCodeHard problems) with only GPT-3.5 and GPT-4o.
Experimental setup
Datasets: MIT OCW Software Construction ps0-ps4 Java repositories ARC-AGI public training set (easy) subset of 60 tasks LeetCodeHard (40 problems)
Benchmarks: MIT OCW ps0 self-validation MIT OCW ps1-ps4 self-validation ARC-AGI subset (60 tasks) LeetCodeHard
Metrics: self-validation (%) accuracy (%) average pass rate cost per task (USD) lines of code added/changed
Baselines: Global best-of-N Local best-of-N Plain Python state machine implementation Two-step agent Reflexion ADAS best agent
Builds on: Syzygy Hypothesis Search Reflexion Self-consistency amb operator
Closest papers by meaning
- AgentSwift: Efficient LLM Agent Design via Value-Guided Hierarchical Search (AAAI 2026 · similarity 0.89)
- Automated Design of Agentic Systems (ICLR 2025 · similarity 0.88)
- LTLf Synthesis on First-Order Agent Programs in Nondeterministic Environments (AAAI 2025 · similarity 0.87)
- WorldCoder, a Model-Based LLM Agent: Building World Models by Writing Code and Interacting with the Environment (NeurIPS 2024 · similarity 0.87)
- FML-bench: A Controlled Study of AI Research Agent Strategies from the Perspective of Search Dynamics (NeurIPS 2026 · similarity 0.87)
- EvoMAS: Evolutionary Generation of Multi-Agent Systems (ICML 2026 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.