acceptodds
Under review as a conference paper at ICLR 2027

Adaptive Small Worlds: Query-Sufficient Compilation for Efficient World-Model Planning

Abstract

World models enable planning by simulating actions, but a model broad enough to support many tasks may be unnecessarily large for any single decision. Moreover, a planning query may depend on only a few state factors such as object locations and resource counts. Thus, planning in the full model spends rollouts on irrelevant factors, whereas aggressive pruning can cause failures. We propose Adaptive Small Worlds (ASW), a test-time compiler that can reduce an existing world model to a query-specific small world, i.e., a planning model of selected factors, action effects, and rewards. It selects factors from a supplied state description via agent-generated rules to build a small world, then uses dependency links built from training traces to add prerequisites and necessary missing state factors. ASW searches for this reduced model, decodes proposals into environment actions, and checks their initial steps in the original model within the same transition budget. Our analysis shows that query-specific representations can require exponentially fewer states than a shared representation, and bounds the expected cumulative reward loss relative to planning in the original model under stated assumptions. Across BabyAI, QueryStress, and symbolic Craftax, our proposed ASW improves the success–budget frontier over both static abstraction, query-based baselines, and conventional planners. These results support our claim: efficient planning should first compile the smallest executable world that preserves the present decision while retaining a well-formed route back to the full one.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
world model, planning, small world

Reviews

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

This paper proposes ASW, a test-time compilation approach for efficient planning with world models. Instead of planning over the entire world model, ASW dynamically compiles a compact, task-specific “small world” for each query, including only the relevant state factors, action effects, and rewards necessary for the current decision. It uses dependency closure to automatically supplement missing but required preconditions, ensuring executability. Planning is performed in this reduced model, and candidate plans are verified in the original full model under a shared transition budget. Theoretical analysis shows that query-specific abstractions can drastically reduce the state space compared to static abstractions, with bounded loss in expected reward. Experiments demonstrate that ASW achieves better success rate–computation trade-offs than static abstractions, query-based masking, and traditional planners.

Critical strengths

I believe this paper is novel within its field. Strengths: The writing is well-organized, the theoretical analysis is sound, and the experimental results support the authors' claims.

Critical weaknesses

In my opinion, while ASW presents an interesting approach, it may have limited impact on the practical advancement of world models. As the authors themselves note, the quality of the dependency graph plays a crucial role, and this remains a common challenge in related domains. I am not fully convinced that simple automatic methods or manually crafted rules can effectively address this issue, or that they can easily scale to a broader range of tasks and environments beyond the evaluation datasets.

Additionally, compared to recent work such as SLAP, it is unclear how the authors are able to outperform such strong baselines without employing reinforcement learning. If this improvement is achieved without any training, it may fundamentally alter the experimental assumptions, which makes the comparison with baselines less meaningful.

Questions for authors

a) How can it be demonstrated that the construction of the dependency graph is generalizable? b) Regarding the constructed small world model, how can its quality be evaluated?

2 comments
AuthorsOpenReview ↗

Rebuttal response

Thank you for recognizing the novelty, theoretical soundness, and empirical support. Your questions helped us sharpen the practical contribution: ASW improves how an available model and skill library are used for each query, including when the skills are learned through reinforcement learning.

Weakness 1 / Question (a). Dependency generalization and practical impact

Thank you for highlighting this central issue. As specified in Sec. 3.2 and Appendix C.4, the graph contains support-filtered relations among task and action records from training traces. Its role is to recover useful prerequisites; full-model verification checks proposed execution. The learned relations contribute useful planning information. The graph diagnostic gives:

Dependency conditionSuccess (%)Mean model calls
Graph disabled54.0116
Learned training graph64.098
Type-valid shuffled graph51.0120

The learned graph improves success by 10.0 points over disabling it, with fewer calls. Shuffling the relations while preserving their types loses this benefit.

The construction also transfers. We exclude the test corridor layout and both composite query templates during bank construction, then evaluate the frozen bank on 50 fresh held-out worlds × ten queries. ASW reaches 64.6% success, versus 64.0% for the static control. Deleting 30% of runtime edges preserves ASW's result across three corruption seeds. These complementary tests show that the dependency structure matters, can transfer to unseen layouts and compositions within the task vocabulary, and need not be complete to remain useful. The learned visual-model and PPO-skill extensions further test the use of learned interfaces.

Weakness 2. SLAP and the role of training

We appreciate this fairness concern. Skill learning supplies useful actions; query-time compilation organizes their search. ASW adds no RL training phase and can operate on exactly the same learned skills as SLAP.

We use SLAP's official shortcut-discovery and PPO pipeline with three training seeds. Within each row below, both searches receive the same skill bank, simulator, 50 fresh continuous starts, and 1,024-call cap:

Shared skill bankNative SLAP search: success (%) / callsASW extension: success (%) / calls
Base skills100.0 / 41.6100.0 / 29.5
Base + SLAP-trained shortcuts95.3 / 723.499.3 / 357.5

The base-skill row provides a solved reference; the shortcut row tests how each planner searches an expanded learned action library. With identical RL-trained skills, ASW gains 4.0 points and uses 50.6% fewer model calls. At the predeclared 512-call cap, success is 99.3% versus 4.0%. Appendix E.7, Fig. 4(b), shows the complete tested budget range and individual seeds. The 1,024-call result demonstrates that the call reduction persists when both searches achieve high success.

These within-bank comparisons keep training fixed and test how the available skills are used. This native-domain experiment complements the benchmark-specific adaptations in the submitted Table 1 and directly addresses the concern about different training assumptions.

Question (b). Quality of the constructed small world

Thank you for this useful suggestion. We assess the proposals supplied to verification, the size of the selected working set, and the resulting execution. The coverage and regret measures below are diagnostics within the evaluated candidate pool; downstream task success provides a separate measure of decision quality:

Matched proposal generatorTop proposal executable (%)Top-two best-candidate coverage (%)Mean candidate-pool regret
Query seeds only76820.12
Query seeds + learned closure93960.04

Closure improves proposal executability and best-candidate coverage while lowering candidate-pool regret. The matched closure component selects an average of 11.82 of 558 option records, linking these gains to a compact working set.

Separately, all 10,563 verified ASW prefixes replay without dead ends or public-state trace mismatches. On 50 preselected reference tasks, ASW solves 43/50 using 52.1 model calls, versus static's 42/50 using 63.1. Together, these diagnostics connect the retained structure to proposal quality, consistent checked execution, and task success under a finite budget.

We hope these targeted controls address your concerns about practical applicability, dependency generalization, and comparison fairness, and would appreciate your reconsideration based on the new evidence.

Appreciate your response. I prefer to maintain my rating.

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

The paper proposes Adaptive Small Worlds. Given a planning problem query, it select a small world model abstraction to plan in, then verifies the plan in the original world model of the problem. The goal is to maximize planning performance with the least amount of calls to the original world model, assuming that calls to the small world model abstraction are free.

Critical strengths

Abstract World Modeling is an Interesting Problem: The idea of planning with abstract world models dependent on query is intuitive. Humans also construct abstractions at test-time depending on what the problem requires.

Critical weaknesses

Unclear Writing with Unintroduced Terminologies: The paper is extremely difficult to understand. The writing constantly refers to terminologies that have never been introduced. For example:

Line 51: " Minimal value-equivalent partial models retain only task-relevant aspects, while CAMPs learns context-specific abstractions in factored environments (Alver & Precup, 2023; Chitnis et al., 2021). " CAMPs is not introduced.

Line 108: " A fixed gate selects an accepted prefix or a predefined fallback; exact-match caching reuses only compatible query- independent structure." Concept of fixed gaps and compatible query-independent structure is not introduced. There are such sentences throughout the paper.

Major Method Details are in Appendix: Details related to how the small world model is constructed, how planning is done and how verification is done is all referred to the appendix. The actual paper just talks through high-level motivations which are not grounded in salient details.

Positioning with Related Work: The Related Works section is relegated to the appendix and its unclear how this paper advances from the state of the art.

Most of the Method Relies on Hand-Crafted Rules: The key method components such as creation of the small world and planning within its abstractions are defined manually or through LLM agents. Since any calls to the small world model are not counted in the planning budget, its unclear how close they are to the original model. In any case, the details about the small world construction are all pushed to the appendix.

Relies on Dataset of Expert Trajectories: The method uses an offline dataset of expert trajectories to initialize the construction of the small world model and compute the transition function. Its unclear how much overlap this dataset has with the test-time problems.

Questions for authors
  • How does this method compare with imitation learning on the offline dataset? Similar to the original BabyAI paper? [1]

[1] Maxime Chevalier-Boisvert, Dzmitry Bahdanau, Salem Lahlou, Lucas Willems, Chitwan Saharia, Thien Huu Nguyen, Yoshua Bengio. "BabyAI: A Platform to Study the Sample Efficiency of Grounded Language Learning." ICLR 2019.

  • Given the reliance of LLM-generated programs throughout the method, how does the method compared to zero-shot LLM planning like BALROG [2]?

[2] "BALROG: Benchmarking Agentic LLM and VLM Reasoning On Games." ICLR 2025.

2 comments
AuthorsOpenReview ↗

Rebuttal response (1/2)

Thank you for identifying where the presentation obscured the implementation and for suggesting the imitation-learning and direct-LLM comparisons. We will address every weakness and question below.

Weakness 1. Unintroduced terminology

We appreciate this feedback and have clarified the terms at their first use in Sec. 1. CAMPs are context-specific abstract Markov decision processes. The fixed gate is a predetermined acceptance rule that selects a checked action prefix or invokes the configured fallback. Compatible caching requires matching environment, model, library, task-program, and configuration identities; it never reuses a previous acceptance decision. Sections 3.4–3.5 give the operational rules.

Weakness 2. Main-text method details

Thank you for pointing out the need for a concrete execution example. We have added one to Sec. 3.3. For a query to open a locked red door, frozen task code binds the door and its current requirements; dependency traversal selects supporting action records; the shared decoder proposes navigation, pick-up, and toggle primitives; and the full model checks selected prefixes before execution. Replanning updates task progress while retaining the same cumulative transition budget.

The structured implementation follows at most six predecessors per record to depth three, retains at most 24 candidates, and checks at most the top two. The small world is therefore an executable, query-specific working set of factors and action records. Sections 3.2–3.4 and Algorithm 1 describe the construction, decoding, and checks; Appendix C.4 supplies the full record and ranking definitions.

Weakness 3. Advance over related work

We appreciate the opportunity to sharpen the positioning. CAMPs learns behavioral constraints that enable variable removal; minimal value-equivalent partial models characterize task-relevant predictive information; SLAP learns shortcut skills. ASW makes model scope a query-time decision and connects selection to prerequisite completion, executable decoding, and checking under one cumulative full-model budget. The revised Sec. 1 states this distinction directly. Section 4 explains the representation benefit and value-preservation conditions; the shared-component control below tests the practical contribution.

Weakness 4. Handcrafted components, uncounted computation, and model quality

Your concern motivated us with a more direct control. ASW's advantage persists when the action bank, decoder, and verifier are identical. On 500 fresh QueryStress tasks:

Success (%)64-call cap256-call cap1,024-call cap
Static abstraction + common verifier54.657.257.2
ASW58.660.059.8
Paired gain in percentage points+4.0 [1.0, 7.4]+2.8 [0.8, 5.0]+2.6 [0.8, 4.6]

These controls test the additional value of the complete compiler given the same reusable components. The result cannot be explained by giving ASW a better action library or a verifier unavailable to the comparator.

Every online full-model transition is charged, including proposal and verification calls, under the cumulative ledger defined in Sec. 2. Graph traversal and reduced-model operations also take computation, so we additionally measure the entire online procedure. Under the same strict 1.25-second deadline, ASW completes 59.4% of tasks versus 57.2%, using 70.1 versus 101.0 model calls. Figure 4(a) in Appendix E.7 provides the full tested deadline curve.

We also examine proposal quality: adding learned closure raises top-proposal executability from 76% to 93% and top-two best-candidate coverage from 82% to 96%, while reducing mean candidate-pool regret from 0.12 to 0.04. Separately, replay of all 10,563 verified ASW prefixes finds no dead ends or public-state trace mismatches. These diagnostics connect the selected working set to useful proposals and consistent checked execution.

Weakness 5. Expert demonstrations and test overlap

Thank you for raising this distinction. Demonstrations provide reusable action/effect and dependency records; the original transition model is supplied independently, rather than inferred from those demonstrations. Appendix C.2 identifies the training-only BabyAIBot and A* sources.

The saved construction dataset contains 1,198 successful demonstrations, with zero exact task or complete initial-state overlaps with evaluation. Excluding the two BabyAI cases whose grid geometry also occurs in training preserves the findings. The frozen bank is therefore reused on held-out tasks, without supplying their expert action sequences at test time.

AuthorsOpenReview ↗

Rebuttal response (2/2)

Question 1. Imitation learning on the same offline dataset

Thank you for this useful suggestion; we have added the requested comparison. Recurrent behavior cloning uses the same saved demonstrations, three training seeds, and development-only architecture/checkpoint selection. BC+verifier additionally checks one-step action proposals using the common verifier.

MethodQueryStress success (%)BabyAI success (%)
Recurrent BC37.932.2
BC + common one-step verifier21.143.0
ASW using the same demonstrations60.082.9

Evaluation uses 500 QueryStress and 175 BabyAI tasks. ASW and BC+verifier share a cumulative 256-model-transition cap; direct BC uses no simulated lookahead. Appendix E.7, Fig. 4(c–d), shows the BC learning and development-selection curves. The same-data experiment answers the imitation-learning question, while the shared-bank control above separately tests compilation given the same execution components.

Question 2. Zero-shot LLM planning

We appreciate this suggestion. Following the direct-action evaluation setting highlighted by BALROG, we tested a DeepSeek-V4.1-Flash agent with the same public fields and 256-real-step horizon:

Paired evaluationDirect-action Flash success (%)ASW success (%)
QueryStress, 200 tasks24.560.5
BabyAI, 70 tasks44.381.4

The requested Flash reasoning allowance is 512 tokens per decision. ASW receives 256 simulated transitions; the direct-action agent uses no simulated lookahead. All Flash trajectories were replay-checked. ASW makes zero online LLM calls: its generated task programs are frozen offline and executed as ordinary code. These results answer whether repeatedly invoking an LLM for actions provides a stronger alternative in this evaluation.

Comment on AI assistance

Thanks for this reminder and feedback. Our submitted AI-use statement discloses manuscript editing and offline program generation. We sincerely claim that the research conception, method design, and direction were human-led, and we take responsibility for the manuscript, implementation, and evidence. The ICLR 2027 author policy addresses disclosure and author responsibility in terms of the AI usage.

Thank you again for the concrete suggestions. We hope the operational clarification, end-to-end timing evaluation, and requested comparisons resolve the substantive concerns and support reconsideration of your assessment.

Reviewer_EmMqOpenReview ↗
Rating
2
Confidence
2
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

The paper introduces adaptive small worlds (ASW). This is a method that makes planning more efficient by building a smaller, task-specific, proxy world model instead of searching within the entire environment. ASW identifies relevant state factors, adds missing prerequisites through dependency graphs, plans in the reduced model, and verifies proposed actions using the original model. Experiments on BabyAI, QueryStress, and symbolic Craftax show improved planning performance with fewer model transitions.

Critical strengths
  • The problem is well motivated. The paper aims to address an important problem, ie, reducing planning costs without losing essential information.

  • The proposed framework makes intuitive sense. It combines query-specific abstraction, dependency recovery, action verification, and caching. More importantly, the frameworks shows consistent improvements across three benchmarks with multiple baselines and statistical tests.

Critical weaknesses
  • Current experiments only focus on limited structured and symbolic environments. Performance in high-dimensional, partially observable, or real-world settings remains unclear.

  • The assumption is overly strong. It requires predefined state factors, executable action controllers, and reliable dependency information. Such information may be difficult to obtain in practice.

  • The current efficiency evaluation is limited. The primary cost metric in the paper is model transitions, while offline computational overhead hasn't been mentioned and compared.

Questions for authors

See the weakness section.

1 comment
AuthorsOpenReview ↗

Rebuttal response

Thank you for recognizing the motivation and the consistent empirical improvements. Your comments helped us examine the practical interfaces and computational costs more directly. We address your three concerns below.

Weakness 1. Evaluation beyond structured and symbolic environments

Thank you for encouraging this extension. We have added a main-text discussion in Sec. 5 and a compact protocol and results table in Appendix E.8 (Table 12). These additions evaluate ASW with learned visual dynamics and, separately, a shared belief interface.

The visual evaluation uses three frozen DINO-WM checkpoints, with current pixels, public proprioception, and goal images as planner inputs. ASW selects goal-relative latent factors and proposes training-derived action prefixes; the shared learned predictor checks the proposed actions. Each environment has 30 fresh task pairs constructed from 25-action trajectories. All planners share a 4,096-model-transition cap and a 50-real-action execution limit.

Visual taskMatched static: success (%) / model callsiCEM: success / model callsASW: success / model calls
TwoRoom100.0 / 738.4100.0 / 970.7100.0 / 814.7
PushT28.9 / 3,510.615.6 / 3,940.728.9 / 3,377.9

ASW retains 100% TwoRoom success with 16.1% fewer model calls than direct iCEM. On PushT, it improves success by 13.3 percentage points (paired 95% interval [1.1, 25.6]) with 14.3% fewer calls, while matching static success. These results improve the success–model-call trade-off over direct iCEM in the evaluated image-goal setting; iCEM remains faster in wall time.

The separate partial-observation evaluation uses public geometry, hidden object/door states, and the same observation-history belief for both planners. Every simulated root comes from that belief, without access to the actual hidden state.

Planner using the shared belief and verifierSuccess (%)Mean model calls
Static abstraction46.5652
ASW extension54.0521

ASW gains 7.5 points with 20.1% fewer calls. These complementary evaluations show that query-specific compilation can operate over learned visual factors or belief-derived states, extending its applicability beyond directly observed symbolic inputs. We appreciate your suggestion, which helped us make this broader applicability explicit in the manuscript.

Weakness 2. Assumptions about factors, controllers, and dependencies

We appreciate this important question. The required interfaces can be supplied by learning: the visual extension uses pixel-derived latent factors and training-derived action prefixes (Appendix E.8), and the SLAP extension uses PPO-trained skills. ASW's role is to select and compose the available interface for each query.

The dependency graph is built from supported training associations and declared prerequisites, as described in Sec. 3.2 and Appendix C.4. It does not require a complete ground-truth causal graph. To test reuse, we exclude the test corridor layout and both composite query templates during bank construction. The frozen bank supports 64.6% success on 500 held-out tasks, versus 64.0% for the static control. Deleting 30% of runtime edges preserves ASW's result across three corruption seeds.

The bank, decoder, and verifier are shared by the controls. Thus, the experiments test query-time compilation over reusable learned or supplied components, including imperfect dependencies, within the evaluated task interfaces.

Weakness 3. Offline preparation and end-to-end online cost

Thank you for asking us to make the efficiency claim more complete. We timed the entire online procedure, including loading, graph processing, decoding, verification, and execution. Success must be completed within the same strict deadline, selected on development tasks:

PlannerSuccess within 1.25 seconds (%)Mean model callsMean total time (s)
Static abstraction + common verifier57.2101.00.55
ASW59.470.10.61

ASW achieves higher success under the same deadline with 30.6% fewer model calls. The paired success improvement is +2.2 points [0.4, 4.2]. Appendix E.7, Fig. 4(a), shows the complete tested deadline curve, including the shorter-deadline regime, so the operating range is visible.

Regenerating demonstrations, loading them, and constructing the reusable bank takes 252.1 CPU-seconds, contributing 0.0252 CPU-seconds per query over 10,000 queries. This figure measures bank rebuilding; offline LLM program authoring and visual-model pretraining are separate cost categories. The matched planners share the reusable resources, while the deadline experiment includes ASW's additional online compilation work.

We hope these targeted evaluations address your concerns about applicability and complete cost and expect your reconsideration in terms of the additional evidence.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.