# EnCompass: Enhancing Agent Programming with Search Over Program Execution Paths

arXiv: https://arxiv.org/abs/2512.03571 · HTML: https://mlsanity.com/paper/2512.03571/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Placed in Software engineering coding agents, one of 16 directions in LLM agents and tool use.
- Builds on 8 of its 41 references that are in the map.
- First posted on arXiv 3 Dec 2025.

## Placed in

- LLM agents and tool use / [Software engineering coding agents](https://mlsanity.com/agents/software-engineering-coding-agents/)

## Builds on (most cited first, 8 of 8)

- [Training Verifiers to Solve Math Word Problems](https://mlsanity.com/paper/2110.14168/) (2021)
- [The AI Scientist: Towards Fully Automated Open-Ended Scientific Discovery](https://mlsanity.com/paper/2408.06292/) (2024)
- [Large Language Monkeys: Scaling Inference Compute with Repeated Sampling](https://mlsanity.com/paper/2407.21787/) (2024)
- [The AI Scientist-v2: Workshop-Level Automated Scientific Discovery via Agentic Tree Search](https://mlsanity.com/paper/2504.08066/) (2025)
- [Accessing GPT-4 level Mathematical Olympiad Solutions via Monte Carlo Tree Self-refine with LLaMa-3 8B](https://mlsanity.com/paper/2406.07394/) (2024)
- [Tree Search for Language Model Agents](https://mlsanity.com/paper/2407.01476/) (2024)
- [On the Measure of Intelligence](https://mlsanity.com/paper/1911.01547/) (2019)
- [Syzygy: Dual Code-Test C to (safe) Rust Translation using LLMs and Dynamic Analysis](https://mlsanity.com/paper/2412.14234/) (2024)

## Built on by (most cited first, 3 of 3)

- [Self-Programmed Execution for Language-Model Agents](https://mlsanity.com/paper/2605.06898/) (2026)
- [PPDL: LLM-Based Flows as Probabilistic Programs](https://mlsanity.com/paper/2608.05234/) (2026)
- [Pay for the Fault, Not the Flow: Label-Free In-Flow Multi-Agent Workflow Optimization](https://mlsanity.com/paper/2610.01017/) (2026)

## Abstract (arXiv)

We introduce a new approach to agent programming, the development of LLM-based agents. Current approaches to agent programming often entangle two aspects of agent design: the core workflow logic and the inference-time strategy (e.g., tree search). We introduce "probabilistic angelic nondeterminism" ("PAN"), a programming model that disentangles these two concerns, allowing the programmer to describe the agent workflow and independently experiment with different inference-time strategies by simply changing a few inputs. We provide an implementation of PAN in Python as the EnCompass framework, which uses a Python decorator to compile agent workflow programs into a search space. We present three case studies that demonstrate how the framework lets the programmer quickly improve the reliability of an agent and easily switch between different inference-time strategies, all with little additional coding.