acceptodds
Under review as a conference paper at ICLR 2027

SPINE: Structured Policy Refinement with Intent-to-Execution Lineage for LLM Software Agents

Abstract

As Large Language Models (LLMs) expand agentic workflows across complex systems, execution logs capture runtime actions but fail to answer key operational questions: which stakeholder intent prompted an action, which intermediate decision derived it, and who was responsible. Consequently, operators must reconstruct attribution post hoc rather than retrieve it directly from the execution record. We present SPINE, a policy refinement framework that represents stakeholder intents as declarative policies and progressively refines them into definitive and imperative policies with explicit refinement relationships. The resulting policy hierarchy establishes an end-to-end intent-to-execution lineage: every policy node records its parent, definer, and enforcer, while an orchestrator stamps the active policy identifier onto execution records at write time. Traceability is thus reduced to a parent-pointer traversal bounded by policy tree depth. Evaluated on SWE-bench Lite instances using two foundation models across four intent representations (68 evaluated runs, 62 resolved), SPINE preserves task resolution performance while achieving 100% (344/344) write-time provenance stamping compared to 0% for other representations. SPINE fundamentally replaces implicit trace reasoning with explicit, queryable semantic lineage by construction.

Primary area:
interpretability and explainable AI
Keywords:
intent-based systems, LLM software agents, provenance, traceability, policy trees, SWE-bench, agent evaluation, governance

Reviews

Among:
Shape:
1234this paper, Bottom 27%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.00 over 3 reviews, above 27% of the others.
Reviewer_1sQiOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper investigates how to improve the traceability and auditability of LLM-based software agents. In typical agent workflows, logs record the actions taken by an agent, but it can be difficult to determine which original user intent motivated a specific action, how the decision was made, and who was responsible. The authors propose SPINE, a framework that organizes policies into a hierarchy of declarative, definitive, and imperative policies, with explicit parent-child relationships linking the original intent to executable actions.

The main contribution is an explicit lineage structure connecting user intent, intermediate policies, and runtime actions. Each policy records its parent, definer, and enforcer, while an orchestrator attaches the active policy ID to execution records at write time. This allows actions to be traced back to the original intent without having to reconstruct these relationships from logs afterward.

The authors evaluate SPINE on three SWE-bench Lite software bug-fixing tasks using two language models, comparing it with raw prompts, free-form plans, and trajectory-based representations. The results show that SPINE substantially improves traceability and accountability while achieving task resolution rates comparable to those of other methods.

Critical strengths

A key strength of this work is that policy attribution is handled by the orchestrator rather than left to the LLM itself. This makes execution records more reliable, as the model cannot simply omit or incorrectly report the policy associated with an action.

Critical weaknesses

The main weakness is the limited experimental evaluation. SPINE is tested on only three software bug-fixing tasks, making it difficult to determine whether the results generalize to more complex tasks or other application domains.

Questions for authors

Does the construction of the policy tree rely entirely on the LLM generating valid structured outputs? If so, for more complex tasks, does SPINE provide mechanisms to ensure policy ID uniqueness and the validity of parent references to ensure that every referenced parent node actually exists?

1 comment
AuthorsOpenReview ↗

Response to Reviewer 1sQi

We sincerely thank the reviewer for their encouraging assessment and for recognizing the core strength of SPINE. Your constructive feedback directly guided our expanded evaluation, and we are glad to share that our revised manuscript fully resolves your concern about scale and clarifies our structural guarantees.

Limited experimental evaluation: We have addressed this concern. We have expanded the evaluation to all 300 SWE-bench Lite instances for refinement and 225 to 285 per representation and model for execution, with five representations, including the newly added Tree of Thought (ToT) planning, and two models (Table 1).

Policy ID uniqueness and the validity of parent references: SPINE does not rely on the LLM alone to maintain tree integrity. Instead, SPINE cleanly separates policy proposal (by the LLM) from deterministic admission validation (enforced by the orchestrator before any policy enters the tree):

  1. Guaranteed policy_id Uniqueness: Every policy node is either assigned a unique deterministic identifier by the orchestrator upon admission or checked against the active tree registry so duplicate IDs are automatically rejected.
  2. Strict Pre-Admission Checks: Before any proposed policy is admitted or allowed to trigger tools, the orchestrator deterministically verifies that:
  • Parent Reference Exists (parent_id): The referenced parent_id is already committed in the tree, guaranteeing a single valid parent and a cycle-free path back to root intent P0.

  • Tier Ordering Holds: The parent-to-child refinement strictly follows Declarative -> Definitive -> Imperative, and only Imperative leaf nodes can execute tools.

  • Required Fields Are Present: Definer, Enforcer, and (R,S,T,CT) scope fields are properly populated.

  1. Automatic Rejection & Recovery on Malformed Proposals: If the LLM produces a missing or invalid parent_id, a duplicate ID, or an invalid tier transition, the orchestrator blocks admission, preventing any unverified execution, and would return a validation error so the model immediately corrects the proposal. Across all 300 SWE-bench Lite runs, this gate maintained 100% unique policy IDs and 100% valid parent references with zero broken links.

We have added this deterministic admission mechanism in Section 5.2 of the revised paper, and we hope these full-scale evaluation and clarifications further strengthen your confidence in our work.

Reviewer_1q67OpenReview ↗
Rating
1
Confidence
3
Informativeness
2
Presentation
3
Soundness
1
Read review
Paper summary

This paper introduces SPINE, which links software agents’ high-level intent, policy refinement, and execution actions. It organizes policies into three abstraction levels—declarative, definitive, and imperative—using common fields for actions, constraints, definers, and enforcers, while retaining parent–child relationships. At runtime, an orchestrator dispatches executable policies sequentially and writes the active policy identifier directly into tool-call records, allowing each action to be traced through the policy tree to the original intent. Software-repair case studies demonstrate the completeness of these recorded links. The data can also be exported in standard tracing formats for inspection through existing observability tools.

Critical strengths
  1. The orchestrator writes policy identifiers from its current state, avoiding reliance on the execution model to supply them. The links between tool calls and policies can be queried directly, reducing the need to infer these relationships retrospectively from natural-language logs.
  2. Policy nodes retain responsible roles and constraints, and execution records can be exported as OpenTelemetry traces for integration with existing observability tools. The reported storage overhead is small, making this implementation practically useful.
Critical weaknesses
  1. The paper requires child policies to semantically preserve or specialize their parents, but the automatic pre-execution checks verify only the root node type, parent references, and abstraction levels. Semantic preservation therefore still depends on the generator refining policies correctly. Stating this requirement as an invariant does not establish how it is guaranteed. Similarly, following parent pointers reconstructs the recorded derivation process, but does not establish that the rationale for each derivation is correct. Presenting semantic preservation and explanation fidelity as properties of the representation itself goes beyond what the current mechanism can guarantee.
  2. Free-Form Steps and Trajectory Format are capped at 0.5 points per semantic-fidelity item solely because they lack explicit root-policy fields, whereas SPINE can receive 1 point. This imposes different scoring ceilings on the representations, preventing a fair comparison even when they express the same content. Moreover, Explanation fidelity checks only whether a rationale exists, while semantic fidelity is assessed only at the root node. These metrics primarily reward field completeness rather than measuring the paper’s central concern: whether intent is preserved through successive refinements.
Questions for authors
  1. Relative to P-PLAN’s existing subplan representation and plan–execution links, what specific checkable property does SPINE’s three-level policy model add?
  2. If the 0.5-point cap for free-text representations were removed and all representations were assessed using the same content-based criteria, would the existing human-scoring materials still support SPINE’s claimed semantic advantage?
1 comment
AuthorsOpenReview ↗

Response to Reviewer 1q67

We sincerely thank the reviewer for their constructive feedback. Your critique regarding the distinction between structural guarantees and semantic verification, as well as evaluation fairness across representations, directly strengthened our revision.

Semantic preservation and Intent guarantee: You are completely right; we used imprecise wording in the original submission. As noted in our Conclusion, SPINE does not verify semantic intent compliance, so calling this property "semantic intent preservation" was a mistake on our part; the accurate term is Intent Attribute Preservation which is verified using Invariant 3 (Section 4.3), ensuring that structural policy attributes, such as constraints, parent links, and role bindings, are explicitly preserved and propagated down the hierarchy. In the revised manuscript, we have corrected this terminology throughout (Section 1, Section 3, and Section 4) and now explicitly state in the Introduction that automated intent compliance verification is outside the scope of this paper. Instead, SPINE establishes the explicit, mechanically inspectable policy structure which can support automated intent verification in future work.

Different scoring ceilings on the representations and semantic advantage of SPINE: Thank you for pointing this out. We acknowledge the limitation of the previous partial-credit rubric we set and have replaced it completely. Every representation is now scored on the same five lineage items, each asked as a general traceability question in the wording of Section 3 and answered stated or absent (Section 6.3, Appendix H) to avoid penalizing other representations. In the human-annotated evaluation covering 2,102 items across five instances, SPINE explicitly records all four refinement attributes (step identifier, parent, definer, and enforcer) for 104/104 steps and all five required attributes for 54/54 sampled execution calls under an active policy. In contrast, Free-Form Steps (56/56) and Tree of Thoughts (30/30) record only step identifiers, while Trajectory Format records none of these attributes across its 73 steps. Neither Free-Form Steps nor Trajectory Format explicitly links sampled execution calls to their corresponding steps. These results show that SPINE's advantage persists under uniform scoring criteria without representation-specific caps. The distinction is therefore not an artifact of the scoring rubric, but the explicit availability of structured refinement and execution-lineage information. Table 1 further reports this pattern across 155 instances using the calibrated judge.

Explanation fidelity: Thank you for pointing this out. Mentioning rationale in that context was a mistake on our part. As defined in Section 4.5, explanation fidelity is a structural property of the policy tree itself: because every node has a unique parent link back to the root policy P0P_0, traversing the tree from any node or linked execution action reconstructs the exact causal derivation path showing how that policy was reached, consistent with the structural/causal notion of explanation (Pearl, 2009; Miller, 2019).

SPINE’s three-level policy model vs. P-Plan: We thank the reviewer for this question. While P-PLAN provides a general-purpose provenance ontology for representing plans, subplans, and their correspondence to execution activities, it does not prescribe the policy-specific refinement and runtime governance mechanisms introduced by SPINE. Specifically, SPINE adds four properties compared to P-Plan:

  1. Typed Abstraction-Tier Progression: Policies follow a defined Declarative → Definitive → Imperative refinement hierarchy, with runtime execution restricted to imperative leaf policies. Unlike P-PLAN’s uniform step/subplan hierarchy, separating policies into typed abstraction tiers also makes the resulting explanation adaptable to audiences with different levels of expertise.
  2. Unique-Parent Lineage: Each non-root policy has exactly one parent, enabling deterministic traversal from an executed policy to its originating stakeholder intent (P_0).
  3. Explicit Accountability and Operational Attributes: Every policy follows a uniform model specifying Definer, Enforcer, Action, Resource, Spatial, and Temporal constraints, and Context, enabling attribute-level inspection and providing a foundation for future semantic verification.
  4. Write-Time Execution Attribution: An orchestrator dispatches active imperative policies and stamps their identifiers onto execution records directly from system state, independently of generated annotations by LLMs.

We hope that correcting our terminology, fixing our assessment criteria, and adding the P-PLAN comparison resolve your concerns about soundness and evaluation fairness.

Reviewer_FPBeOpenReview ↗
Rating
2
Confidence
4
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

SPINE (Structured Policy Refinement with Intent-to-Execution Lineage) is a framework built to fix the opacity of LLM agent execution logs. Instead of trying to guess an agent's reasoning after the fact, SPINE explicitly preserves the link between high-level user intents and runtime actions. It does this by organizing policies into a three-tier hierarchy (Declarative, Definitive, Imperative) using a uniform semantic tuple. To prevent "intent drift," it enforces strict semantic rules like Unique Parent and Attribute Propagation. Crucially, an external orchestrator deterministically stamps the active policy ID onto the execution logs at write-time, completely bypassing the risk of LLM hallucinations. The authors tested SPINE on 3 instances of SWE-bench Lite, reporting 100% write-time provenance stamping without hurting task resolution, alongside native compatibility with OpenTelemetry.

Critical strengths

Highly Practical Architecture: Decoupling the policy generation from its representation and letting an external orchestrator handle the provenance stamping at write-time is a great design choice. It completely removes the risk of hallucinated attribution, a massive issue for current LLM agents.

Principled Framework: Formalizing the three-tier hierarchy and enforcing strict semantic invariants provides a rigorous way to stop "intent drift" during long-horizon planning.

Ready for Production: Mapping execution records and policy attribution directly to standard OpenTelemetry (OTLP/JSON) formats makes this framework incredibly practical. It’s essentially ready to drop into existing enterprise observability stacks.

Critical weaknesses

Meaningless Evaluation Scale: The framework is evaluated on exactly 3 hand-picked instances from the SWE-bench Lite dataset, which has 300 instances total. Testing on 1% of a benchmark means the claims about task resolution performance, robustness, and cost-efficiency are statistically meaningless and suffer from severe selection bias.

No Dynamic Replanning: SPINE enforces a strict, single-pass, monotonic refinement process. In the real world, software engineering agents constantly need to backtrack, handle execution failures, and revise their high-level plans. SPINE currently has no mechanism for upward error propagation or dynamic re-planning that wouldn't violate its own structural rules.

Missing Structural Baselines: The evaluation compares SPINE to unstructured or loosely structured baselines (Raw Prompt, Free-Form Steps). However, it completely ignores established hierarchical reasoning baselines like Tree of Thoughts (ToT) or Graph of Thoughts (GoT), which also explicitly maintain reasoning structures and parent-child lineage.

Questions for authors
  1. Why did you limit the evaluation to only 3 instances of SWE-bench Lite? Is it feasible to run this on the full 300-instance dataset to give a statistically robust picture of task resolution and overhead?

  2. How can the framework be extended to handle execution failures that require revising a definitive or declarative policy? If an imperative policy fails, how does the agent backtrack without breaking the monotonic refinement invariants?

  3. Did you measure the impact of the extra policy_complete turns on context window bloat for longer tasks? Could the orchestrator allow the LLM to execute multiple independent imperative policies in a single turn?

  4. Why were structured reasoning baselines like Tree of Thoughts (ToT) or Graph of Thoughts (GoT) excluded from the comparisons?

1 comment
AuthorsOpenReview ↗

Response to Reviewer FPBe

We sincerely thank the reviewer for the positive assessment of SPINE's architectural design, practical relevance, and clarity of presentation. We particularly appreciate the recognition of our separation of policy representation from generation, the orchestrator-controlled write-time provenance attribution, and the structured three-level policy refinement model. These observations align with our central objective: establishing explicit, queryable intent-to-execution lineage rather than reconstructing relationships retrospectively from agent execution logs. We are also pleased that the reviewer recognizes the practical value of our OpenTelemetry compatibility, which enables integration with existing observability infrastructure. We appreciate the constructive feedback and have used it to improve our paper further.

Scale of evaluation: We agree and have scaled the study according to your suggestion. The revision refines all 300 SWE-bench Lite instances under every planned representation with both models around 2,400 plans artifacts and executes 225 to 285 instances per representation and model, with lineage judged on 155 of them. Lineage is now measured by a human-annotated key of 2102 items and an LLM judge calibrated against it (agreement 0.99, Section 6.3). The lineage result holds at scale where SPINE states every item on 100 percent of refinement steps and 95 percent of sampled execution calls, against around 7 percent for any item under the other representations (Table 1).

Dynamic Replanning: We appreciate the reviewer raising this point and have clarified in Section 4.1 that SPINE does not require single-pass upfront planning and natively supports failure recovery and replanning without violating any structural invariants. SPINE does support dynamic replanning and backtracking after execution failures without breaking any structural rules. Because SPINE builds the policy tree incrementally alongside execution, the agent can revise its plan whenever a tool call or test fails by adding a new branch rather than overwriting past nodes: If an Imperative policy fails, the agent adds a new sibling Imperative policy under the same Definitive parent (noting the error in its rationale). If a whole sub-strategy fails, the agent adds a new Definitive branch under the root policy P0 and generates new Imperative steps under it. Every new node still has a single valid parent, follows the three-tier hierarchy, and gets stamped at write time so both the failed attempt and the recovery plan remain cleanly recorded in the tree.

Structural baseline: According to your suggestion, we have added Tree of Thoughts (ToT) to our evaluation.

Handling execution failures and backtrack: Because SPINE builds the policy tree incrementally alongside execution, the agent can revise its plan whenever a tool call or test fails by adding a new branch rather than overwriting past nodes: If an Imperative policy fails, the agent adds a new sibling Imperative policy under the same Definitive parent (noting the error in its rationale). If a whole sub-strategy fails, the agent adds a new Definitive branch under the root policy P0 and generates new Imperative steps under it. Every new node still has a single valid parent, follows the three-tier hierarchy, and gets stamped at write time so both the failed attempt and the recovery plan remain cleanly recorded in the tree. We have clarified this in Section 4.1.

Impact of the extra policy_complete turns on context window bloat: Yes. policy_complete adds 3.5 and 3.1 turns per run with the two models around 12 and 14 percent of SPINE’s execution tokens (Appendix I). Per-turn latency stays comparable to the other representations, so the overhead is in the number of turns. Executing several imperative policies in one turn would put several identifiers on one record and weaken the attribution so we leave it as future work.

We hope that the full 300-instance SWE-bench Lite evaluation, the added Tree of Thoughts baseline, and our clarifications on dynamic replanning and context overhead address your concerns.

Comments on the paper

1 comment
AuthorsOpenReview ↗

Overall Response to Program Chairs, Senior Area Chairs, Area Chairs, and Reviewers

Dear Program Chairs, Senior Area Chairs, Area Chairs, and Reviewers,

We sincerely thank you for your time and constructive feedback on our paper. We appreciate the insightful comments, which have helped us improve the clarity, rigor, and completeness of our paper.

In response, we have undertaken the following revisions:

  • Expanded evaluation at scale. We extended the refinement evaluation from 3 to all 300 SWE-bench Lite instances, and the execution evaluation to 225–285 instances per representation and model, using two foundation models (Claude Sonnet 4.6 and GPT-5.6 Terra) and five representations, including Tree of Thoughts as an additional structured baseline. The experimental setup is described in Section 6.1, with results in Section 7, task-resolution outcomes in Appendix G, and cost analysis in Appendix I.

  • Introduced a uniform, evidence-based annotation protocol. We replaced the previous partial-credit rubric with five identical lineage questions applied to every representation: step identifier, tool-call-to-step link, parent, definer, and enforcer. Each item is assessed as stated or absent, supported by a verbatim quotation, without representation-specific scoring caps. We constructed a 2,102-item human-annotated reference set across five instances. The protocol is described in Section 6.3 and Appendix H, with the annotation guidelines and reference set provided in the supplementary material.

  • Conducted a human-annotated evaluation. One author independently annotated all refinement plans and execution runs across five calibration instances (astropy-12907, pytest-11143, sympy-15011, matplotlib-25311, and django-11099). The evaluation covered 39 refinement plans (263 steps; 1,052 annotation items) and 29 execution runs (210 sampled tool calls; 1,050 annotation items), totaling 2,102 items. Each item was labeled stated or absent, with supporting verbatim evidence, before any LLM-judge outputs were examined.

  • Calibrated and validated the LLM-based evaluation. Following the Trust or Escalate approach (Jung et al., ICLR 2025), we employed GPT-5.6 Luna as a judge with five simulated annotators and selective confidence calibration. The judge agreed with the human annotations on 2,084/2,102 items (99.1%), without abstention on the reference set, and subsequently evaluated 69,248 items across 155 instances. Full methodological details are provided in Section 6.3 and Appendix H.

  • Added comprehensive mechanical verification. We implemented script-based validation of all 600 policy trees and 536 orchestrated execution runs, checking policy identifier uniqueness, parent-reference resolution, abstraction-level ordering, attribute propagation, and execution-record lineage to the root intent. These checks are documented in Sections 6.2 and 7.2.

  • Clarified the framework and its scope. We refined the terminology and removed ambiguity about intent preservation(Sections 1, 3, and 4.5); clarified incremental refinement and dynamic replanning (Section 4.1), orchestrator admission checks (Section 5.2), and distinctions from P-PLAN, Tree of Thoughts, and Graph of Thoughts (Section 2). We also rewrote the Limitations section and updated the Reproducibility and AI Use statements.

  • Expanded the supplementary evidence. The appendices now include request templates and the Tree of Thoughts baseline (Appendix A); supplementary materials and instrument logs (Appendices B–C); task-resolution outcomes over 228 graded instances (Appendix G); the full annotation and judge-calibration protocol (Appendix H); and refinement and execution costs, storage, latency, and a per-step cost comparison with Who&When (Appendix I).

We are grateful for the opportunity to clarify and strengthen our work and have carefully revised the manuscript, where changes are highlighted in Blue. Below, we address each comment point-by-point.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.