At a glance
This edition reviews arXiv v3 dated 20 November 2025. All six authors are affiliated with UT Austin Computer Science. The complete nine-page paper has no appendix; all figures, tables, formal expressions and references are retained.
STAR treats recalling an old observation and probing the current environment as actions in one decision loop. A language/vision model combines an indexed archive with a task-specific working memory, checking whether remembered objects remain where they were seen.
STARBench contains 360 simulated tasks. STAR improves over the compared one-shot retrieval baselines, with some ties. Real-robot evaluation tests guiding a person to the correct landmark, rather than physically picking and delivering the requested object.
I INTRODUCTION
A request can identify an object by its appearance, present relation or past location. The robot must determine which object the user means, locate it now and sometimes open a receptacle to access it. An earlier sighting can establish identity without establishing the current location.
STAR retains task-agnostic captions, poses, timestamps and raw views during patrols. Once a request arrives, its controller can retrieve evidence, navigate, perceive or manipulate, then use each outcome to choose again. This extends the archive approach of ReMEmbR with repeated interaction between memory and current evidence.
The contribution is a unified memory/action architecture and a benchmark for evolving households. “Open-world” denotes open-ended language and potentially unseen targets within the supplied sensors, memory and tool interface; the experiments use a small, controlled set of scenes and object classes.
II Related Work
Object search: navigation methods find visible targets, while mechanical search can expose hidden objects. Dynamic and open-vocabulary scene representations broaden the setting, but the authors argue that accessible histories are needed for references to past states.
Benchmarks: embodied visual question answering, ALFRED and object-navigation suites evaluate related perception and interaction skills. STARBench adds changing scenes and instructions that distinguish objects using historical or habitual locations.
Language-model agents: Code as Policies, LM-Nav and later systems connect pretrained reasoning to callable robot skills. STAR exposes memory retrieval through that same tool interface, allowing recall and physical verification to alternate.
Memory: scene graphs and long-term semantic maps organize objects and relations; Embodied-RAG and ReMEmbR instead retrieve stored observations. STAR keeps raw views so task-relevant details omitted from captions can still be inspected. The broad novelty claims are the authors’ characterization of prior work, not a controlled comparison against every cited system.
III Problem Statement
The changing environment is only partially observed. Each patrol record contains a timestamp, observation and robot pose. Before the instruction is known, a memory-construction function indexes this history in a task-agnostic form; after task time T, the robot has at most K policy steps.
The policy conditions on the instruction, stored history and new observations. Old observations identify likely locations but can be stale, so successful search requires deciding when to recall and when to obtain fresh evidence. The objective is to reach the requested object within the budget, preferably using fewer steps. The formal history definitions and policy remain below.
Equations 1
| (1) |
IV STAR: SpatioTemporal Active Retrieval
STAR separates persistent experience from the evidence needed for the current request. Figure 2 shows the archive-building process, the controller’s tool interface and the action/outcome loop that updates working memory.
IV-A System Overview
Putting the entire archive into a model prompt would exceed context limits and introduce irrelevant material. STAR instead retrieves records into working memory H, which also accumulates outcomes of actions in the current environment.
At every step the controller chooses either an archive query or an embodied action. Equation 2 expresses the intended approximation of full-history conditioning by working-memory conditioning; the paper does not prove that the selected memory is sufficient or lossless for every instruction.
Equation 2
| (2) |
IV-B Non-Parametric Long-term Memory
The non-parametric archive stores each observation with three searchable indices: a text embedding of its caption, its timestamp, and the robot pose. Text, time and location queries therefore retrieve different views of the same records.
Raw images remain attached to the indices. The agent can replay an image when its caption or embedding omits a distinguishing attribute. Adding another modality means adding an index rather than changing the record-storage design. Exact captioner/embedding versions, similarity metrics, retrieval count and storage scaling are not specified in this paper.
Equation
IV-C Working Memory Update with Spatio-temporal Actions
Working memory is an action/outcome trajectory. An action pairs a callable tool with arguments drawn from that tool’s parameter space. Temporal, spatial and semantic archive queries count as searches in memory; navigation, detection, grasping and other robot skills probe the present environment.
For an archive query, the tool converts the model’s text argument into the relevant vector representation, retrieves its top-r neighbors and returns the corresponding records. These results can establish what an object looked like, where it was seen and when. Nearest-neighbor retrieval is not a guarantee that every relevant historical event is returned.
A robot skill returns a raw observation, detections or a success/failure signal. The controller appends the executed action and outcome to working memory, then reasons again. Fresh evidence can invalidate an old location hypothesis without discarding the old observation’s value for identifying the target. The update is append-only in the described method; no learned compression or forgetting mechanism is evaluated.
Equations 3–4
| (3) |
| (4) |
IV-D Action Selection with Working Memory
The controller receives the instruction, working memory and remaining step budget, selects a tool/argument pair and repeats until retrieval succeeds or the budget is exhausted. Budget awareness is supplied in context, rather than established by an optimal planning guarantee.
The printed budget formula is Rₖ=(T+K)−k, although earlier k denotes steps since task time T. Under that relative convention the remaining budget would be K−k; the paper’s expression instead corresponds to absolute time. The original formula is preserved, and the implementation convention is not clarified.
Equation
V STARBench: A Benchmark for Spatiotemporal Object Search
STARBench uses VirtualHome apartment scenes and Unity3D interactions. Patrol histories cover three to six simulated days with 1,200–1,500 observations per day, including views, poses, times and captions. Scene-graph histories are also supplied for comparison.
Three scenes support 225 visible-search tasks, 90 interactive-search tasks and 45 commonsense-search tasks. Visible and interactive search each use five instruction families: class, attribute, current spatial relation, past spatial relation, and habitual spatial relation. Interactive search requires exposing a hidden object; commonsense search can require finding a target never observed in memory.
The benchmark has five object classes for visible search, two for interactive search and five for commonsense search. Thus it tests varied references and changes within controlled households rather than arbitrary real-world object diversity. Figure 3’s spatial-temporal caption says t=8 while that row’s first image is labeled t=13; both original labels are retained.
| Task Type | Visible | Interactive | Commonsense |
|---|---|---|---|
| No. of scenes | |||
| No. of Tasks | |||
| No. of Object Classes | |||
| Task families |
VI Experimental Evaluation
Simulation success requires retrieving the requested object within twenty decisions. The reported backbone is OpenAI o3; each model call selects one action. Available simulated skills include navigate, detect, pick and open, alongside queries of past text/images.
Memory knowledge: Oracle construction supplies true visible-object labels and scene-graph relations, plus true node associations for the graph agent. Realistic construction uses predicted perception. However, both modes still use simulator segmentation masks for object detection during skill execution, so Realistic is not an entirely unprivileged end-to-end perception test.
Baselines: Random navigates randomly; SG+S uses scene-graph history and a single retrieval attempt; TR+S uses non-parametric recall followed by a one-shot plan. STAR interleaves recall and embodied actions with feedback. These comparisons evaluate the complete loop against those restricted one-shot designs, not an isolated change in memory representation.
Hardware: a TIAGo operates in one mock apartment with kitchen, living and study areas. There are nine tasks in each of six categories, fifty-four total. Success means leading the user to a correct landmark where the item can be found. Physical pickup, delivery and cabinet manipulation are not required by this hardware success criterion.
Experimental Results
Visible search: Figure 5 reports forty-five tasks per instruction family. The plotted STAR rates lead the compared methods, especially for attributes and temporal references. Graph history and temporal retrieval show complementary strengths. Figure 6 assigns 46.2% of STAR actions to physical actions versus 27.7% for TR+S; action proportions support a behavioral difference but do not alone establish its causal contribution or runtime cost.
Interactive search: in Oracle mode STAR scores 0.67/0.50/0.50/0.61/0.61 across class/attribute/spatial/past/frequentist tasks, versus 0.56/0.33/0.22/0.17/0.28 for TR+S. In Realistic mode STAR scores 0.67/0.61/0.50/0.28/0.44. The past-reference condition ties TR+S at 0.28 and falls from STAR’s Oracle 0.61; improvement is therefore not strict in every condition. The paper attributes gains to using past visual context to choose the correct receptacle, without a separate controlled ablation of that explanation.
Action efficiency: successful visible runs average 4.93 Oracle or 4.74 Realistic actions, versus a minimum of three. Interactive runs average 8.27 or 8.16, versus five. These are roughly 1.58–1.65 times the minima and exclude failed runs. The table includes perception calls alongside navigation and manipulation, so its “physical action” total is not simply robot motions or elapsed time. The 4.93 total differs by 0.01 from the sum of its rounded category means, consistent with rounding.
Unseen targets: commonsense search yields STAR 0.57 in both modes, versus TR+S 0.19 Oracle/0.43 Realistic and Random/SG+S 0.10 Oracle. The result supports searching likely locations beyond directly remembered sightings, but success remains limited to the benchmark’s objects and scenes.
Hardware: STAR succeeds at rates 0.67/0.78/1.00/0.56/0.56/0.33 across the six listed categories, compared with TR+S 0.44/0.67/1.00/0.56/0.44/0.33. It improves class, attribute and habitual-location tasks and ties the other three. With nine trials per category, the rounded rates correspond to 35/54 successes versus 31/54, about a 7.4-percentage-point aggregate gain. This is landmark guidance in one apartment, not a demonstrated end-to-end grasp-and-deliver rate.
Tables and plots preserve the reported uncertainty marks, but their interval definition and repeated-model-run protocol are not given. No independent archive-size, raw-image-replay, retrieval-count, backbone or closed-loop graph-baseline ablation is reported, and wall-clock latency, token cost and long-term memory growth are not quantified.
| Task | TR+S | STAR | ||
|---|---|---|---|---|
| Oracle | Realistic | Oracle | Realistic | |
| C | 0.56 0.21 | 0.28 0.19 | 0.67 0.20 | 0.67 0.20 |
| A | 0.33 0.20 | 0.17 0.17 | 0.50 0.21 | 0.61 0.21 |
| S | 0.22 0.18 | 0.06 0.12 | 0.50 0.21 | 0.50 0.21 |
| ST | 0.17 0.17 | 0.28 0.19 | 0.61 0.21 | 0.28 0.19 |
| SF | 0.28 0.19 | 0.11 0.15 | 0.61 0.21 | 0.44 0.21 |
| Visible Object Search | |||||
|---|---|---|---|---|---|
| Method | Env. | Percep. | Nav. | Manip. | Total |
| STAR | Oracle | 1.80 | 1.62 | 1.52 | 4.93 |
| Realistic | 1.70 | 1.60 | 1.44 | 4.74 | |
| Optimal | – | 1 | 1 | 1 | 3 |
| Interactive Object Search | |||||
| Method | Env. | Percep. | Nav. | Manip. | Total |
| STAR | Oracle | 3.21 | 2.00 | 3.06 | 8.27 |
| Realistic | 3.18 | 2.11 | 2.87 | 8.16 | |
| Optimal | – | 2 | 1 | 2 | 5 |
| Method | Oracle | Realistic |
|---|---|---|
| Random | – | |
| SG+S | – | |
| TR+S | ||
| STAR |
| Task Type | Random | TR+S | STAR |
|---|---|---|---|
| Class-based | 0.00 | 0.44 | 0.67 |
| Attribute-based | 0.00 | 0.67 | 0.78 |
| Spatial | 0.11 | 1.00 | 1.00 |
| Spatial-Temporal | 0.00 | 0.56 | 0.56 |
| Spatial-Frequentist | 0.00 | 0.44 | 0.56 |
| Common-Sense | 0.00 | 0.33 | 0.33 |
VII Conclusions
Treating memory recall and current-world interaction as actions in one loop improves the evaluated object-search tasks relative to the selected one-shot baselines. The evidence concerns three simulated scenes and one real mock apartment, with different simulation and hardware success criteria.
Future work includes pruning or compressing memory while retaining useful history, and distilling low-level action traces into reusable high-level skills. The source promises a public benchmark release upon acceptance; this edition does not independently establish the later release status.