Security operators use red teams to simulate real attackers and proactively find defense gaps. In realistic enterprise settings, this involves executing multi-host network attacks spanning many “stepping stone” hosts. Unfortunately, red teams are expensive and entail significant expertise and effort. Given the promise of LLMs in CTF challenges, we first analyze whether LLMs can autonomously execute multi-host red-team exercises. We find that state-of-the-art LLM-assisted offense systems (e.g., PentestGPT, CyberSecEval3) with leading LLMs (e.g., Sonnet 4, Gemini 2.5 Pro) are unable to do so. Building on our observations in understanding the failure modes of state-of-the-art systems, we argue the need to improve the abstractions and interfaces for LLM-assisted red teaming. Based on this insight, we design and implement Incalmo11All code is publicly available: Incalmo GitHub an LLM-assisted system for autonomously red teaming multihost networks. Incalmo uses LLMs to plan red-team exercises in terms of high-level declarative tasks that are executed by domain-specific task agents. Incalmo also uses auxiliary services to manage context and acquired assets. For our evaluation, we develop MHBench, a novel multihost attack benchmark with 40 realistic emulated networks (from 22 to 50 hosts). We find that Incalmo successfully acquires critical assets (i.e., key hosts or data) in 37 of 40 MHBench environments. In contrast, state-of-the-art LLMassisted systems succeed in only three of 40 environments. We also show that Incalmo is efficient: successful attacks took 1254 minutes and cost $\leq$ $ 15 in LLM credits.