acceptodds
Under review as a conference paper at ICLR 2027

ARSM: Auto-Regressive State Machine for Agentic Reasoning Compression

Abstract

While Large Language Model (LLM)-based agents demonstrate strong capabilities in long-horizon tasks by interleaving reasoning with external environment interactions, the continuous accumulation of context rapidly creates a critical memory bottleneck. Existing memory compression methods rely on task-specific optimization or external auxiliary models, introducing significant computational overhead. Furthermore, the resulting compressed representations tend to lose structured relationships, leading to information dilution, attention collapse, and degraded decision consistency. To address these limitations, we propose **A**uto-**R**egressive **S**tate **M**achine (ARSM), a lightweight training-free framework that enables in-situ reasoning compression through structured state evolution. ARSM introduces two key components: (i) a trajectory abstraction mechanism that reorganizes interaction histories into compact **H**ypothesis-**A**ction-**R**esult (HAR) micro-chains; (ii) a dynamic state machine that regulates hierarchical memory through atomic operations and a compression-control parameter. These components are unified within an auto-regressive, self-compressive generation space, where each model output jointly performs external action execution and internal state updates. We evaluate ARSM on Webshop, Multi-Objective Multi-Hop QA, and SWE-Bench Lite datasets. Experimental results show that ARSM maintains the task performance while simultaneously reducing token consumption, offering a practical, cost‑effective route toward scalable autonomous agents for long‑horizon tasks.

Primary area:
foundation or frontier models, including LLMs
Keywords:
LLM Agents, Reasoning Compression

Reviews

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

ARSM is a training-free context-compression framework for LLM agents. It has two parts. First, interaction histories are reorganized into Hypothesis–Action–Result micro-chains, and each model output carries state-update metadata alongside the next action. Second, a five-layer dynamic state machine (global checklist, pitfall memory, loop alerts, milestones, active reasoning path) evolves through atomic operations gated by one of four routing signals, ONGOING, MILESTONE, FAILURE, and SUCCESS, while a compression-control parameter ρ jointly scales raw-trajectory retention and structured-state capacity. The executor stays frozen and the mechanism is implemented entirely through prompts and configuration. Experiments cover WebShop, a 16-objective multi-hop QA setting, and SWE-Bench Lite across six backbones: WebShop reward improves while total tokens drop by about two thirds, QA ΣEM\Sigma_{EM} rises from 0.567 to 2.01, and SWE-Bench Lite token consumption falls by up to 82%. The paper also reports routing distributions, component ablations, solved-set overlap across ρ, and a trajectory-level evaluation.

Critical strengths
  1. The training-free, self-contained mechanism delivers real efficiency gains with a genuine operating knob. WebShop reward improves consistently across three model families while total tokens drop by about two thirds; ρ yields an explicit performance-cost frontier (Figures 5 and 7) that lets users pick a point by task and budget. Code and YAML configurations ship with the supplementary material, supporting reproducibility.
  2. The empirical analysis goes beyond headline numbers. The routing-signal distribution (Table 5) shows the state machine does not degenerate into an append-only log; the component ablation (Table 6) separates the contributions of HAR abstraction and state evolution; solved-set overlap across ρ (Table 8) shows a stable core with complementary coverage; the trajectory-level evaluation (Table 7) quantifies state fidelity and sufficiency; and the case study illustrates how information migrates between the two memory surfaces. This level of mechanistic characterization is uncommon in scaffolding papers.
Critical weaknesses
  1. Baseline health and statistical rigor are insufficient. No seeds or variance are reported for accuracy metrics, and several baselines appear to run far outside their design regime: Search-R1 scores 0.009 ΣEM\Sigma_{EM} against 0.567 for the raw backbone, MEM1-Webshop reaches 0.153 reward against 0.286 for the raw backbone, and ContextBudget is evaluated without RL. These numbers are far below the results reported in the original papers and inflate ARSM's relative advantage. Meanwhile, on SWE-Bench Lite, ARSM trails SWE-Pruner by about 11 points at a similar token budget on the 9B model (29.7% vs. 40.7%) and Mini SWE-Agent by 5.2 points on the 27B model, so the abstract's claim of maintaining task performance while reducing token consumption is too strong for this benchmark; the body's more honest framing is a tunable trade-off.
  2. The formalism is disconnected from the actual mechanism. Equations 3 to 6 describe state updates through a transition-operator matrix with element-wise broadcasting and a one-hot routing vector, but what actually executes is an LLM emitting status tags and a controller applying hardcoded per-layer rules; no property of this state machine is stated or proved, the loop-detection similarity indicator 1_sim and the penalty increment γ are never defined, and Appendix A truncates in the middle of the prune operator. The mathematics adds nothing verifiable and forces the reader to rebuild the algorithm from appendix examples.
Questions for authors
  1. Please provide the implementation of 1_sim (similarity metric, threshold, and over what representations) and the value of γ\gamma, and complete the truncated operator definitions in Appendix A.
  2. Were the Search-R1, MEM1, and ContextBudget numbers re-run under your protocol or taken from their papers? Search-R1's 0.009 ΣEM\Sigma_{EM} and MEM1-Webshop's 0.153 reward are far below their published levels; please either validate these baselines within their design regime or explain why they collapse here.
  3. Are the accuracy numbers single runs? Please report variance over at least three seeds for WebShop reward and SWE-Bench Pass@1, and add significance for the ρ\rho-sensitivity claims.
  4. On SWE-Bench Lite with the 9B model, ARSM trails SWE-Pruner by about 11 points at a comparable token budget. What is the source of this gap, and how should users choose between the two?
2 comments

Thank you for the response. For the weakness and questions mentioned in the review:

W2 and Q1. State transitions and loop detection. Figure 3 and §3.2 show how the controller parses the status tag and applies the corresponding branch’s updates. The transition matrix summarizes those four branches. In Eq. (10), the binary indicator 1_sim is 1 when a repeat failure is detected and 0 otherwise. Each detected repeat increments the loop counter by γ = 1. Appendix D gives an example of an inspection warning after three reads of the same file or path set without new evidence. The pruning operator on page 13 removes the last η entries from the active reasoning path in Eq. (11). The check operator on page 14 returns WARN when a loop counter reaches its threshold in Eq. (12).

W1 and Q2. Baseline provenance. The Search-R1 result in Table 3 (summed EM = 0.009, summed F1 = 0.011) comes from MEM1’s Table 1 [1], which reports a performance collapse for the original Search-R1 at 16 objectives. We reran the MEM1-style truncation baseline on the same 16-objective QA test set, using the same E5 retrieval endpoint (top-k = 3), 20-turn cap, and evaluator as ARSM. In this baseline, each call used the original 16-objective prompt, a truncated window of preceding responses, and the latest retrieved evidence.

The 30B ContextBudget result comes from the published no-RL ablation in Table 1 and serves as a training-free reference [2]. We will place its 0.170 in the summed F1 column and label 8K as a configured context limit.

For MEM1-WebShop, we retrained MEM1 on the same backbone as ARSM, used GRPO, LoRA (rank = 8, alpha = 16) and a maximum of 1,024 generated tokens per call. Both evaluations used Qwen2.5-7B-Instruct, temperature zero, an 8,192-token context limit, and up to 20 environment interaction steps. Most MEM1 trajectories ended without a purchase, which helps explain the low reward in this resource-constrained reproduction. We will clarify the training and evaluation settings in the revised manuscript.

W1 and Q3. Seeds, variance, and ρ sensitivity. The supplementary YAML lists the seed configurations. Table 2 reports dispersion in peak token usage for WebShop. For the 9B SWE-bench comparisons below, we ran each issue five times with distinct seeds and computed Pass@1 and Pass@5 as defined in Appendix C.2.

MethodPass@1 (mean ± sample standard deviation)Sample variance (pp²)
Mini SWE-Agent26.6% ± 1.3 pp1.65
SWE-Pruner40.7% ± 2.4 pp5.73
ARSM (ρ = 0.5)26.2% ± 1.5 pp2.13

Across five seeds, ARSM at ρ = 0.5 achieved a mean Pass@1 close to Mini SWE-Agent’s and showed less run-to-run variation than SWE-Pruner.

In the Qwen3.5-27B ρ-sensitivity analysis, Cochran’s Q test showed that Pass@1 differed across settings (Q(10) = 52.68, p = 8.55 × 10⁻⁸). In follow-up exact McNemar tests against ρ = 0.5, Pass@1 was significantly lower at ρ = 0.7 and ρ = 0.9 after Holm correction (adjusted p = 0.0031 and 0.0159, respectively).

ρHolm-adjusted p vs. ρ = 0.5
0.00.5980
0.11.0000
0.21.0000
0.30.2402
0.41.0000
0.5—
0.61.0000
0.70.0031
0.81.0000
0.90.0159
1.01.0000

In this analysis, increasing ρ from 0.5 to 0.7 or 0.9 reduced Pass@1 by 8.7 and 8.0 percentage points, respectively. Stronger compression can therefore lower task-solving accuracy at these settings.

W1 and Q4. The 9B gap and method choice. On SWE-bench Lite, SWE-Pruner achieves 40.7% Pass@1 at 2.29M reported tokens, compared with 29.7% at 2.40M for ARSM at ρ = 0.1. As discussed in Appendix C.3, one possible contributor is how the methods divide the work. SWE-Pruner uses a separately trained 0.6B model for line-level pruning, while ARSM’s backbone handles both repair and structured memory updates. The 9B backbone sometimes omits required memory fields and needs extra turns to recover. We observed this behavior to a lesser extent on 27B. At the reported 9B settings, SWE-Pruner is preferable when Pass@1 is the priority and the auxiliary model can be deployed. ARSM offers a single-backbone option with adjustable token usage.

[1] MEM1: Learning to Synergize Memory and Reasoning for Efficient Long-Horizon Agents

[2] ContextBudget: Budget-Aware Context Management for Long-Horizon Search Agents

Thank you for the detailed rebuttal, which addresses several concerns, although some issues regarding baseline fairness, formalization, and statistical robustness remain unresolved.

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

This paper proposes a lightweight training-free framework called Autoregressive State Machine, aiming to address the context memory bottleneck problem faced by large language model agents in long-term tasks. This method reorganizes the interaction history through a trajectory abstraction mechanism into micro-chains of assumed action outcomes, and combines a dynamic state machine to regulate hierarchical memory.

Critical strengths
  1. The article accurately points out the memory bottleneck and attention degradation problems that intelligent agents encounter due to the accumulation of context during long-term interactions, which is a practical pain point that is currently highly concerned in the field.

  2. The research clearly sets reducing token consumption as one of the core optimization goals, and proposes compressing control parameters to balance memory capacity and state sparsity. This has clear engineering reference value for practical deployment.

  3. The proposed framework does not require additional fine-tuning or auxiliary models. It directly utilizes the in-place generation capability of the existing model to update the state, reducing the computational threshold of the application.

Critical weaknesses
  1. Summarizing the interaction trajectories into a structured format for predicting the outcome of actions, along with simple state maintenance, essentially belongs to heuristic prompt engineering techniques. Such methods have been extensively explored in existing literature. This paper does not propose new architectures or paradigms with theoretical depth; it merely recombines existing concepts.

  2. The article emphasizes a significant reduction in token consumption, but on some datasets, the task success rate did not improve and even declined. In complex software engineering or multi-hop question-answering tasks, a slight decline in success rate often indicates a break in the critical reasoning chain. The author fails to fully demonstrate the acceptability of this performance loss in practical applications.

  3. The atomic operations and transition matrices of the dynamic state machine highly rely on artificially designed heuristic rules. This hard-coded logic may be effective on distributed internal data, but when facing complex and variable long-term tasks in the real world, its generalization ability and robustness are questionable. The paper does not provide sufficient out-of-distribution generalization experiments to support its validity.

  4. The case studies provided in the paper only show the intuitive differences in text fragments under different compression parameters, lacking deep quantitative trajectory-level analysis. The author claims that this method retains the causal topology structure, but does not provide convincing evidence to prove that the state machine truly captures the deep logic rather than merely performing simple text truncation and summarization.

Questions for authors

see weakness

1 comment

We sincerely thank you for the constructive review. For the weaknesses mentioned in the review:

W1. Contribution. We agree that structured summaries and state maintenance are established techniques. Our contribution is a training-free controller that uses status signals generated alongside the next action to update different parts of the agent’s memory. It uses hypothesis–action–result records to track ongoing work, folds completed subgoals into memory, and retains lessons from failed branches. The same backbone generates both the action and the metadata used for these updates.

W2. Success–cost trade-off and failure cases. On 27B, ARSM at ρ = 0.1 uses 0.92M tokens at 46.5% Pass@1, compared with Mini SWE-Agent’s 1.74M tokens at 51.7%. The choice depends on the token budget and the target success rate. Maintaining compressed state alongside solving the task can also place extra demands on the backbone. Two instances illustrate where errors occurred.

In the matched MultiHopQA instance multiqa16-c183e9eaff47 (Qwen2.5-14B-Instruct, ρ = 0.5), the baseline answered 4 of 16 objectives correctly and ARSM answered 2. For question two, ARSM retrieved evidence identifying Philip III of France as Joan of Valois, Countess of Hainaut’s paternal grandfather, and retained him as the resolved candidate in its sparse-state ledger. The final output listed the two birth dates for the preceding comparison as separate answers. This moved Philip III of France to the third position and caused the evaluator to mark question two incorrect.

In pytest-dev__pytest-5692 (Qwen3.5-9B, ρ = 0.1, run 1), ARSM identified that the JUnit XML <testsuite> element lacked hostname and timestamp and added both attributes. The final patch placed the datetime and socket imports inside the module docstring, and the local check ran against the environment’s pytest 9.1.1. The task remained unresolved, while the baseline passed both issue-specific tests. This trace shows that a correct diagnosis can coexist with errors in implementation and validation.

W3. Shared rules across domains. ARSM’s hand-designed transition rules are shared across tasks. The same milestone rule consolidates progress after the agent identifies a suitable product in WebShop, finds relevant evidence in multi-hop QA, or isolates a bug in SWE-bench Lite. We reuse the transition rules and largely the same prompt structure across all three domains, and adjust the retention and clipping hyperparameters in Appendix B by task. Task-specific rules performed better in our early experiments. We report the shared design to assess how the same rules perform across domains.

W4. Trajectory evidence. On SWE-bench Lite with 9B, ARSM at ρ = 0.9 reduces token usage by 82.5% relative to Mini SWE-Agent (1.15M vs. 6.57M), with Pass@1 of 20.3% vs. 26.6%. Table 7 quantifies state fidelity (76.1%) and routing correctness (73.2%) on 100 WebShop trajectories scored by an LLM judge.

In django__django-11001 (Qwen3.5-9B, ρ = 0.9), multiline RawSQL ORDER BY clauses were incorrectly treated as duplicates. The agent identified that newlines affected extraction by the ordering_parts regex, so distinct SQL expressions with the same final line could produce identical deduplication keys. It normalized SQL with " ".join(sql.split()) at both extraction sites and passed the official evaluation. This case illustrates the link between the diagnosis and the resulting fix in the recorded trajectory.

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

The paper proposes a training-free controller that replaces growing agent histories with Hypothesis–Action–Result records and a structured state containing task progress, pitfalls, loop alerts, milestones, and an active reasoning path. The agent generates update metadata alongside its next action, and a compression parameter controls several retention and clipping budgets. Experiments cover WebShop, 16-objective multi-hop QA, and SWE-bench Lite. The results show substantial token savings and improved WebShop reward, with a more mixed accuracy–cost tradeoff on software repair.

Critical strengths
  1. Generating compact interaction records during the existing action-generation process is a practical design. It avoids requiring a separate compression model and makes failure lessons and completed subtasks explicit.
  2. The WebShop gains are substantial and appear with several backbones. For Qwen2.5-14B at rho = 0.5, reward rises from 0.4464 to 0.5736 while reported total tokens fall from 45.34K to 21.01K (Table 2). This is the clearest evidence for the approach.
  3. Table 6 includes meaningful simplified variants rather than only removing the entire memory system. HAR-only and state-machine-only behave differently, and their combination gives the best reward and token tradeoff among the reported variants.
Critical weaknesses
  1. Preserving performance is not a consistent result on SWE-bench Lite. With the 27B model, every ARSM setting in Table 4 falls below Mini SWE-Agent: 46.0% versus 51.7% at rho = 0.5. With the 9B model, SWE-Pruner reaches 40.7%, compared with ARSM's best reported 29.7%. Lower token use is valuable, but a comparison at matched success or matched total cost is needed to show when ARSM is preferable.
  2. The QA comparison mixes model sizes, trained and untrained methods, and measured peak usage with ContextBudget's configured context limit. Table 3 also leaves total-token costs unavailable for every baseline. The very low Search-R1 result and the use of ContextBudget without RL need a more direct explanation. These rows do not establish a conservative comparison simply because some original methods involve training.
  3. Rho changes raw-history retention, structured-memory capacity, and observation clipping together (Appendix B). Consequently, the sweep cannot tell whether the gain comes from HAR/state transitions or simpler truncation choices. Table 6 is helpful, but its variants have different realized context sizes; a matched-budget summary baseline and the same component study on code tasks would strengthen the causal claim.
  4. The uncertainty and fidelity analyses are incomplete. SWE-bench uses temperature 0.6, but Table 4 gives no uncertainty or clear account of how Pass@1 and Pass@5 are aggregated. Table 7 reports only 76.1% state fidelity and 73.2% routing correctness under one LLM judge, without human validation or an analysis connecting these errors to task failures.
Questions for authors
  1. Can you report success–cost curves against Mini SWE-Agent and SWE-Pruner, including all generated metadata, and explain whether token totals are averaged per task or computed another way?
  2. Were the QA baselines rerun with the same retriever, objective packaging, stopping rule, and answer parser? What explains Search-R1's near-zero score?
  3. What happens when a generated MILESTONE or SUCCESS is unsupported? Please provide the relevant validation rule and results for a summary baseline with matched retention and clipping budgets.
4 comments

Thank you for the response. For the weakness and questions mentioned in the review:

W1 and Q1. SWE-bench success and token cost. As defined in Appendix C.2, token usage includes both prompt and completion tokens. For each SWE-bench trajectory, we sum the API-reported usage across recorded model calls. Completion tokens include the full generated response, including ARSM’s status, reflection, aim, and pitfalls, even when those fields are later removed from context. We report the mean total token usage per task attempt. Peak usage is the maximum prompt-plus-completion count across turns within each trajectory, averaged across tasks.

Figures 7 and 8 break down the number of resolved tasks by prompt tokens, completion tokens, total tokens, and interaction turns on Qwen3.5-9B and Qwen3.5-27B. On both backbones, ARSM at ρ = 0.5 resolves more tasks in the lowest total-token bin. Table 4 gives the overall success–cost trade-off. On 27B, ARSM at ρ = 0.1 achieves 46.5% Pass@1 at 0.92M tokens, compared with 51.7% at 1.74M for Mini SWE-Agent. On 9B, SWE-Pruner achieves 40.7% at 2.29M tokens, compared with ARSM’s 29.7% at 2.40M tokens at ρ = 0.1. We will reflect this trade-off in the abstract.

W2 and Q2. QA baseline sources and evaluation. The Search-R1 result in Table 3 (summed EM = 0.009, summed F1 = 0.011) comes from Table 1 of MEM1 [1], which reports a sharp decline for the original Search-R1 as the number of objectives increases from 2 to 16. We reran the MEM1-style truncation baseline on the same 16-objective QA test set as ARSM, using the same E5 retrieval endpoint (top-k = 3), 20-turn cap, and evaluator. Each call received the original 16-objective prompt, a truncated window of preceding model responses, and the latest retrieved evidence. Earlier interaction history was discarded.

We use the published ContextBudget 30B no-RL ablation as a training-free reference [2]. We will report its 0.170 under summed F1 and label the 8K context budget as the configured limit.

W3 and Q3. Component study and status correction. The ρ sweep jointly varies history retention, structured-state capacity, and observation clipping. Table 6 reports the WebShop summary and component ablations with their realized token costs. In §3.2, MILESTONE folds progress into memory and advances the checklist, and SUCCESS appends the result and checks for loops. Official patch evaluation determines SWE-bench success.

In mwaskom__seaborn-3190 (Qwen3.5-9B, ρ = 0.1), the agent emitted MILESTONE after Plot(...).add(Bar()) returned successfully without rendering the plot. After the second loop recovery, the agent revisited the original issue and realized it had yet to reproduce or fix the bug. It changed the status to FAILURE, called .plot() to reproduce the original TypeError, traced it to boolean data handling, and submitted a patch that passed official SWE-bench evaluation. The baseline failed to resolve this issue.

W4. Run-to-run variation and trajectory evaluation. In the five-seed 9B comparisons, Pass@1 averages the fraction of passing attempts per issue. Pass@5 is the fraction of issues solved at least once in five attempts. The across-seed sample standard deviations for Mini SWE-Agent, SWE-Pruner, and ARSM (ρ = 0.5) are 1.3, 2.4, and 1.4 percentage points, respectively. Table 7 evaluates 100 WebShop trajectories using one LLM judge and reports 76.1% state fidelity and 73.2% routing correctness.

[1] MEM1: Learning to Synergize Memory and Reasoning for Efficient Long-Horizon Agents

[2] ContextBudget: Budget-Aware Context Management for Long-Horizon Search Agents

Thank you for clarifying the token counting and metric definitions, providing the mwaskom__seaborn-3190 case, and promising to revise the claim in the abstract. However, I still have some concerns: the paper lacks a summary baseline with comparable Peak Tokens (Structured Summary uses nearly half of ARSM's in Table 6), and although the authors reran MEM1-QA, its Total Tokens are still not reported in Table 3. I decide to keep my rating unchanged.

Thank you for pointing out these concerns.

Difference in peak token usage. Table 6 includes Plain Summary, which reaches a higher peak (3.63K) than ARSM (2.97K). At these evaluated settings, ARSM achieves higher reward (0.4899 for ARSM and 0.3305 for Plain Summary) while using fewer total tokens (22.84K for ARSM and 44.71K for Plain Summary).

We agree that Structured Summary, at 1.37K peak tokens, leaves open how a structured summary would perform at a peak closer to ARSM’s. As described in Appendix C.4, Structured Summary is designed to distill the interaction history into a compact summary with fixed fields. Its 1.37K peak is an observed outcome of that design. Requiring the model to produce longer summaries solely to approach ARSM’s peak would change the summarization policy being evaluated. We therefore interpret Table 6 as a comparison of the reward and token costs achieved by each method under its evaluated configuration.

The SM-only ablation provides a closer comparison. It retains the state machine and uses generic structured turn summaries in place of HAR records. At similar peak usage (2.97K for ARSM and 2.74K for SM-only), ARSM achieves substantially higher reward (0.4899 for ARSM and 0.3178 for SM-only) and uses fewer total tokens (22.84K for ARSM and 24.18K for SM-only). This comparison supports the value of explicitly preserving HAR chains within the state machine.

Thank you for pointing out this concern.

Total-token reporting for Multi-Objective Multi-Hop QA. Multi-Objective Multi-Hop QA (16-Objective) benchmark was an early experiment, and following the MEM1 setup, we recorded peak-token usage but did not retain per-call API usage metadata. Although the saved trajectories allow us to reconstruct an approximate token count, the exact server-reported total-token usage cannot be recovered from the original run. We will rerun and report complete total-token measurements in the final version.

Although total token data is missing for MEM1-QA in this specific experiment, we evaluated the performance between the MEM1 and our ARSM using the Webshop benchmark. In our WebShop evaluation, ARSM (Qwen-7B, ρ = 0.3) achieved a reward of 0.4906 with 21.46K total tokens while MEM1-WebShop (Qwen, RAG+RL) achieved a reward of 0.1528 with 21.82K total tokens.

The performance decline in MEM1-QA is linked to the 20-turn limit; in many of its task trajectories, no answer was provided by the 20th turn. This indicates that MEM1-QA requires a higher number of turns to complete tasks, whereas ARSM is capable of achieving superior results in fewer turns. The results on the SWE tasks (Figure 4) further substantiate this point.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.