CAIRN: Dynamic Fact-Intent DAGs for Multi-Agent Exploration

1 INTRODUCTION

• CAIRN represents findings as FACTs and planned investigations as INTENTs that cite supporting FACTs, forming a persistent DAG across workers and sessions.The graph supports reuse and parallel exploration while making investigation trajectories traceable for human verification and intervention.Source: §1 · p. 2
• On high-effort tasks (≥1M baseline tokens), CAIRN finishes sooner in 76.5% of cases, with speedups of up to 3.08×.CAIRN uses more tokens on average, but its relative token overhead decreases as task effort increases.Source: §1 · p. 2
• The evaluation covers twelve FrontierMath problems and forty Cybench tasks, comparing CAIRN with a baseline agent using the same model, agent loop, and task environment.Manual review of sixteen FrontierMath DAGs found that they reveal reuse of earlier findings, evidence combination, and error correction.Source: §1 · p. 2

2 CAIRN: EXPLORATION THROUGH FACT–INTENT DAGS

• Task solving is represented as an incremental FACT–INTENT DAG from an ORIGIN containing initial information toward a GOAL specifying the desired outcome.INTENTs link motivating FACTs to findings recorded as new FACTs; evidence can support further investigations or a completion INTENT.Source: §2 · p. 2, §2.1 · pp. 2–3

2.1 TASK SOLVING AS GRAPH CONSTRUCTION

• Exploration proceeds through proposing FACT-supported INTENTs, assigning eligible INTENTs to WORKERs, and recording findings as FACTs for later investigations.Shared FACTs can motivate separate branches whose findings jointly support a subsequent INTENT.Source: §2.1 · p. 3, Figure 2 · p. 3

2.2 COORDINATION THROUGH A SHARED GRAPH

• A persistent shared DAG gives REASONER and WORKER sessions access to investigation state, while a DISPATCHER starts sessions and assigns eligible INTENTs.Accepted findings become available to later sessions while a WORKER may continue investigating, allowing branches to develop in parallel.Source: §2.2 · pp. 3–4, Figure 3 · p. 4

2.3 INSPECTABLE TRAJECTORIES AND REVISION

• The graph’s source and output edges expose which findings motivated investigations, what they produced, and where branches split or join.FACTs are agent-reported findings whose reliability may change; the REASONER can drop INTENTs, and the graph preserves dropped-intent history for review.Source: §2.3 · p. 4

3 EXPERIMENT SETUP

• CAIRN is evaluated as a task-architecture change against DIRECT, using the same model, agent-loop implementation, and task environment.The comparison treats the high-level coordination paradigm as the variable of interest.Source: §3 · p. 4, Figure 4 · p. 5
• The study uses the twelve publicly available FrontierMath sample problems; FrontierMath is a mathematical reasoning benchmark with problems of increasing difficulty from Tier 1 to Tier 4.Epoch AI reports that Tier 3 and Tier 4 problems can occupy specialists for days; leading mathematicians have described them as “exceptionally challenging” (Epoch AI, 2026).Source: §3 · p. 4
• Cybench contributes CTF tasks with interactive environments and externally checkable outcomes, evaluated in the unguided complete-task setting.Solvers receive the original task, permitted files, and target access without benchmark subtask hints.Source: §3 · p. 5
• Both systems use Pi 0.85.1 and GLM-5.1 in isolated containers without public Internet access, with up to six shared execution slots and a five-hour hard limit.Solving time is measured to the first accepted answer, with five hours assigned to unsolved runs; total token usage is also reported.Source: §3 · p. 5

4.1 BENCHMARK-LEVEL RESULTS

• On FrontierMath, CAIRN’s mean solving time is 27.45 versus 53.19 minutes for DIRECT, and it is faster on 8 of 12 problems; on Cybench, DIRECT is faster on 30 of 40 tasks.Mean total token usage is 13.44M for CAIRN versus 2.81M for DIRECT on FrontierMath, and 0.83M for DIRECT versus 3.22M for CAIRN on Cybench.Source: §4.1 · p. 5, Table 1 · p. 6

4.2 TASK-DEPENDENT PERFORMANCE

• Mean solving time falls from 47.20 to 25.35 minutes (DIRECT to CAIRN) in the ≥1M-baseline-token group; DIRECT is faster on average in both lower-effort groups.The mean per-task token ratio (CAIRN/DIRECT) falls from 14.71 in the lowest-effort group to 3.69 in the highest-effort group.Source: §4.2 · p. 5, Table 2 · p. 6
• As task effort increases, the mean solving-time ratio (DIRECT/CAIRN) rises above 1 in the high-effort group while the mean token ratio (CAIRN/DIRECT) falls.The pooled fit estimates a break-even point at 1.24M baseline tokens; CAIRN is faster on 7 of 11 high-effort Cybench tasks and all 6 high-effort FrontierMath problems.Source: §4.2 · p. 6, Figure 6 · p. 7, Figure 7 · p. 7

4.3 CONCURRENCY ANALYSIS

• 97.22, 73.70, and 26.51 minutes are the recorded solving times with one, three, and six execution slots, respectively; peak active WORKERs are one, three, and five.Token totals are 13.51M, 28.12M, and 20.60M, respectively, so the six-slot run finishes sooner than the three-slot run while using fewer recorded tokens.Source: §4.3 · pp. 7–8, Figure 8 · p. 8

4.4 EXECUTION TRACE ANALYSIS

• A manual review of sixteen FrontierMath DAGs finds that the shared graph records concurrent investigations and their findings, supporting solution construction, error correction, and verification.The execution traces show how CAIRN organizes and coordinates investigations and proposes subsequent work.Source: §4.4 · p. 8
• In the fm-02 trace, two independent checks publish f001 and f002, and INTENT i006 cites both to recover the target quantity used in the accepted submission.The run’s solving time is 26.51 minutes.Source: §4.4 · pp. 8–9, Figure 9 · p. 8
• For fm-05 and fm-01, paired DAGs and execution flows expose which INTENTs produced or reused FACTs and when events occurred, making large runtime records more legible for targeted audit and attribution.The runs use 43.0M and 77.8M input-plus-output tokens, with archived request/response bodies of 130 and 256 MB, respectively.Source: Figure 10 · p. 9, §4.4 · p. 9

5 RELATED WORK

• Prior systems use role-based workflows and programmable conversations, while adaptive approaches create task-specific sub-agents or learn orchestration configurations.Interactive security systems maintain task context, operate terminal tools, and feed execution results back into planning.Source: §5 · p. 9
• Interactive security work provides a concrete setting for multi-agent coordination, combining task context, terminal-tool operation, and execution feedback to planning.The cited systems include Deng et al. (2024), Abramovich et al. (2025), and Udeshi et al. (2025).Source: §5 · p. 9
• Blackboard architectures provide a common knowledge store, while graph-based methods connect reasoning states, evolve agent communication, or encode verification dependencies.CAIRN links these strands with a shared FACT–INTENT DAG in which findings motivate executable investigations and their outputs guide later branches.Source: §5 · p. 9

• CAIRN uses a shared FACT–INTENT DAG to coordinate multi-agent exploration.Source: §6 · p. 9
• Time advantages grow on high-effort tasks as relative token overhead declines, while CAIRN offers inspectable parallel investigations.Source: §6 · p. 10
• Evaluations use authorized cybersecurity benchmarks in isolated environments, without public-Internet access, sensitive data, or live-system deployment.Source: ETHICS STATEMENT · p. 10
• The paper describes anonymized source code, configurations, evaluation scripts, and benchmark images for independent reproduction in supplementary material.Source: REPRODUCIBILITY STATEMENT · p. 10

A.1 STATE AND GRAPH INVARIANTS

• CAIRN’s bipartite graph links INTENTs to existing FACT sources and published FACTs or the terminal GOAL, while creation-order edges preserve acyclicity.Dropping an INTENT retains its source edges and findings; completion adds a fresh INTENT pointing to the GOAL.Source: §A.1 · p. 13

A.2 ASYNCHRONOUS SCHEDULING

• The dispatcher prioritizes pending INTENTs by priority and creation time, and schedules reviews from consistent graph snapshots while other slots execute accepted work.New FACTs, exhausted open work, and explicit requests can trigger a review; evidence arriving during a review remains pending for a later one.Source: §A.2 · p. 13

A.3 REASONER AND WORKER DECISIONS

• Reasoners review evidence and choose investigations, while workers execute assigned INTENTs; validated submissions support retries, incremental findings, and final outcomes.An uncertain submission is retried with the same key and arguments, and successful receipts confirm acceptance; workers can publish findings before their INTENT concludes.Source: §A.3 · p. 14

A.4 ATOMIC SUBMISSIONS AND RECEIPT RECOVERY

• State-changing calls use scoped credentials and submission keys; accepted operations atomically store their arguments, results, state changes, and receipts.Exact retries recover the stored result, while reuse of a key with different arguments conflicts; operation-specific checks validate permissions, sources, and state.Source: §A.4 · pp. 14–16

B.1 PROMPT CONSTRUCTION

• Role prompts are instantiated with task context and a YAML graph snapshot, alongside role-specific fields, environment instructions, and budget instructions.Run-specific prompts and configurations preserve the instantiated instructions and their versions.Source: §B.1 · p. 17, B AGENT PROMPTS · p. 17

B.2 REASONER WORKING PROMPT

• The reasoner prompt directs the model to delegate new derivations, searches, implementation, experiments, and lengthy computations to Explore Intents rather than investigate them itself.It calls for focused, non-overlapping work, accounting for dependencies and existing open Intents; planning can finish once useful work is covered.Source: §B.2 · pp. 18–19

B.3 WORKER WORKING PROMPT

• The worker template assigns one INTENT and specifies incremental finding publication and submission of a final outcome.Source: §B.3 · p. 20
• Workers pursue the assigned Intent, return reviewable evidence, submit verified findings, and finish with a submitted fact ID.The working prompt asks workers to report methods, results, artifacts, and limitations; with multiple findings, they should submit a summary fact referencing supporting facts.Source: §B.3 · pp. 20–21

B.4 REASONER CONCLUSION PROMPT

• At the end of its budget, the Reasoner closes review using existing evidence, completing the project only when verified facts satisfy the goal or otherwise scheduling justified next steps.If no justified decision is possible, it records unresolved questions and useful next steps rather than inventing work or a success claim.Source: §B.4 · p. 21

B.5 WORKER CONCLUSION PROMPT

• When the working phase ends, workers stop exploration, submit observed findings and uncertainty, then finish the assigned Intent and confirm its receipt.The worker conclusion prompt limits this phase to recording observed evidence, correcting submissions, and finishing the Intent.Source: §B.5 · pp. 22–23

• The reference implementation details graph records, agent-facing tools, and the submission protocol.Source: C TOOL INTERFACE AND EXECUTION PROTOCOL · p. 24
• These interfaces connect the graph formulation to the execution architecture in Section 2.2.Source: C TOOL INTERFACE AND EXECUTION PROTOCOL · p. 24
• Run-specific settings are recorded separately in Appendix D.Source: C TOOL INTERFACE AND EXECUTION PROTOCOL · p. 24

C.1 GRAPH RECORDS AND DATA FLOW

• FACT records retain descriptions, provenance, and timestamps; INTENT records retain sources, investigation details, ownership, priority, and lifecycle timestamps.Source: §C.1 · p. 24
• Session snapshots provide graph state and provenance, while referenced workspace files hold larger supporting artifacts such as code or detailed computations.Source: §C.1 · p. 24
• New graph records are submitted as structured MCP arguments, and accepted findings become available to subsequent investigations during the worker’s execution.Source: §C.1 · p. 24

C.2 ROLE-SCOPED TOOLS

• The reference implementation exposes eleven MCP tools: workers have four for findings and conclusions, while the reasoner has nine for planning, progress review, and completion judgments.Source: §C.2 · p. 24
• New INTENTs require distinct existing source FACTs from the same project, and accepted INTENTs become dispatch-eligible subject to capacity.Source: §C.2 · p. 24
• Workers may publish multiple FACTs but must select one from their execution to finish; the benchmark’s independent verifier evaluates the resulting answer.Source: §C.2 · p. 24

C.3 OWNERSHIP AND TRANSACTIONAL SUBMISSIONS

• Submission claims bind credentials to projects, roles, workers, and assigned INTENTs; the server checks active state and lease heartbeats, while allowing one active reasoner per project.Reasoning claims record the request revision under review, and completing a review acknowledges that revision without discarding later requests.Source: §C.3 · pp. 24–25
• State-changing calls use submission keys and commit graph updates with receipts atomically; retrying an identical request recovers its receipt without repeating the update.Reusing a key with different arguments is rejected, and credential revocation blocks updates and receipt replay.Source: §C.3 · p. 25

C.4 EXAMPLE GRAPH RECORDS

• The example graph records supporting FACTs in the from field and links each finding to its producing INTENT, showing how investigation branches converge.The excerpt illustrates two findings supporting a subsequent INTENT and resulting FACT.Source: §C.4 · pp. 25–26

C.5 REVISION AND CANCELLATION

• When evidence disputes a finding, CAIRN can add verification work, drop affected INTENTs, and assign replacement investigations fresh identifiers while retaining prior records.Structural validation checks graph consistency; evidence assessment remains part of agent investigation and review.Source: §C.5 · p. 26

D.1 TASK INTERFACES AND VERIFICATION

• Both systems receive the same task information and access permissions, and answers are checked independently without agents accessing grading references during solving.FrontierMath submissions are Python programs checked in a fresh sandbox; Cybench submissions are answer strings checked against task criteria.Source: §D.1 · p. 27

D.2 AGENT CONFIGURATION AND PROMPT COMPOSITION

• CAIRN and DIRECT use Pi 0.85.1 with glm-5.1-highspeed; DIRECT uses one agent loop, while CAIRN adds role-specific instructions and graph tools with up to six shared execution slots.Runs use fresh isolated project containers, and public Internet access is disabled.Source: §D.2 · p. 27

D.3 DEADLINES AND MEASUREMENT

• Solving time runs from activation to the first accepted submission or five-hour cutoff, while total tokens sum provider-reported counts across sessions.Runs reaching the hard limit without acceptance are assigned 300 minutes; the time measure includes planning, tool use, coordination, and waiting.Source: §D.3 · p. 27