Time-Decayed Vector Search in the Rhythm of TANGO: Jointly Modeling Semantic Similarity and Temporal Freshness

Jiuqi Wei; Qiyao Luo; Quanqing Xu; Chuanhui Yang; Themis Palpanas

Source-linked AI summary

Time-Decayed Vector Search in the Rhythm of TANGO: Jointly Modeling Semantic Similarity and Temporal Freshness

Jiuqi Wei, Qiyao Luo, Quanqing Xu, Chuanhui Yang, Themis Palpanas

arXiv:2609.00548v1Sep 1, 2026cs.DB

TL;DR

Vector search often assumes fixed semantic relevance even when freshness changes over time, motivating a native formulation that combines semantic similarity with temporal decay. The paper introduces TDVS, STR, Chronos, and TANGO to support this objective, and reports stronger query and index performance across diverse temporal settings, including 3.5× higher query throughput and 4.05× faster index construction than competitors.

Problem
Conventional vector search uses fixed semantic similarity, while many applications require relevance to reflect continuously changing temporal freshness.
Method
The paper formalizes TDVS, reduces it exactly to MIPS with STR, and develops Chronos and the hierarchical graph index TANGO with controllable layer-specific semantic–temporal geometries.
Results
TANGO consistently outperforms state-of-the-art graph-based competitors in query and index performance across diverse temporal settings, achieving up to 3.5× higher query throughput and 4.05× faster index construction.
Takeaways & Limitations
The results support TDVS-native graph indexing as a robust approach for jointly modeling temporal locality and long-range semantic connectivity while enabling online insertion.
Takeaways & Limitations
STR inherits structural constraints from temporal factorization, including dependence on a global anchor T that can make recent vectors central hubs and distort semantic neighborhoods.

Abstract

from arXiv · show

Vector search typically measures relevance through semantic similarity under a fixed scoring function. However, in a growing range of applications, relevance may evolve over time, making temporal freshness an additional signal beyond semantic similarity. In this paper, we formalize time-decayed vector search (TDVS), which incorporates continuous temporal decay into the search objective so that relevance is jointly determined by semantic similarity and temporal freshness. We design Score-Preserving Temporal Reduction (STR) that enables existing Maximum Inner Product Search indexes to directly support TDVS. We further present Chronos, a TDVS-native framework that derives an exact metric formulation and introduces Query-Orthogonal TimeLift to control data--data geometry while preserving all query--data scores and rankings. Building on Chronos, we propose TANGO, a hierarchical graph index that adopts layer-specific TimeLift geometries to preserve temporal locality at the base layer while strengthening long-range semantic connectivity in upper layers. TANGO traverses the hierarchy using the exact TDVS score, caches temporal factors to reduce computation, and supports efficient online insertion. Extensive experiments show that TANGO achieves up to 3.5$\times$ higher query throughput and 4.05$\times$ faster index construction than state-of-the-art graph-based competitors. TANGO also maintains its advantage over all competitors across diverse temporal settings and enables efficient online insertion, demonstrating its robustness and practicality.

1 INTRODUCTION

The paper argues that vector-search relevance increasingly depends on both semantic similarity and continuously changing temporal freshness. It formalizes time-decayed vector search and develops STR, Chronos, and TANGO to support this objective, with reported gains in query throughput and index construction.

Motivation: Standard vector search ranks items using a fixed semantic similarity function, but emerging applications also require temporal freshness to influence relevance.Examples include agent memory, freshness-sensitive RAG, temporal question answering, and recency-sensitive web search.
Limitations of Existing Approaches: Filter-based methods impose coarse time thresholds, while rerank-based pipelines cannot recover semantically relevant items omitted by the first-stage retriever.These approaches treat time as metadata or an additional ranking signal rather than integrating continuous decay into the search objective.
TDVS: Time-decayed vector search jointly ranks timestamped vectors by semantic similarity and temporal decay at query time.The formulation asks how vector search should be reformulated when relevance changes continuously over time.
Solutions: STR exactly reduces TDVS to Maximum Inner Product Search, allowing existing MIPS indexes to support the new objective.The reduction is generic across semantic measures and inherits structural constraints from temporal factorization.
Solutions: Chronos preserves query–data scores and rankings while enabling controllable semantic–temporal geometry, and TANGO assigns different TimeLift geometries across graph layers.TANGO preserves temporal locality at the base layer, strengthens long-range semantic connectivity above it, and supports online insertion.
Evaluation: 3.5× higher query throughput and 4.05× faster index construction are reported for TANGO versus the best-performing competitors.The experiments compare TANGO with state-of-the-art graph-based methods across diverse temporal settings.

2 PROBLEM STATEMENT

Time-decayed vector search extends vector retrieval by making relevance depend jointly on semantic similarity and temporal freshness. The paper defines additive and multiplicative TDVS and develops exact reductions and encodings that preserve TDVS scores while enabling MIPS-based search.

Classical Vector Search: Standard vector search ranks items by semantic similarity, but approximate search is used in high-dimensional settings because exact search is costly.Classical search assumes relevance remains fixed once an embedding is assigned.
Time-Decayed Vector Search: TDVS retrieves timestamped vectors using a joint score over semantic similarity and freshness, with item age defined as query time minus creation time.The freshness weight is non-increasing with age and equals 1 at age zero.
Time-Decayed Vector Search: Additive TDVS weights semantic similarity and freshness separately, while multiplicative TDVS scales semantic relevance by freshness.The additive trade-off is controlled by α, while the decay timescale is controlled by the half-life h or decay rate λ.
Time-Decayed Vector Search: With h=30 and α=0.7, multiplicative TDVS promotes fresher candidates and lowers the rank of an old highly similar item, whereas additive TDVS keeps strong semantic matches competitive.Figure 1 visualizes top-3 membership under both modes in semantic similarity–freshness space.
STR: Exact TDVS-to-MIPS Reduction: STR reduces additive and multiplicative TDVS for inner product, cosine similarity, and Euclidean distance to finite-dimensional MIPS inner products without approximation.The reduction uses semantic encoding, temporal factorization, and vector mapping to produce mode-specific query and data representations.
STR: Exact TDVS-to-MIPS Reduction: STR preserves the exact TDVS score and ranking, but its fixed temporal anchor can widen transformed norms as newer vectors arrive and may require re-encoding and index rebuilding when updated.The temporal factorization also imposes structural constraints on transformed representations.

3 CHRONOS FRAMEWORK

Chronos is a TDVS-native framework that preserves exact query–data scores while controlling data–data geometry through anchor-free temporal representations, metricization, and Query-Orthogonal TimeLift.

3.1 Anchor-Free Temporal Representation: Chronos uses an anchor-free temporal representation based on relative timestamps, preserving query–data decay while eliminating anchor dependence from pairwise temporal geometry.The anchor-free kernel is symmetric and translation invariant, so shifting the time origin does not alter indexed-vector affinities.
3.2 Exact TDVS Metricization: Chronos combines unit-norm semantic embeddings with unit-norm temporal features to obtain mode-specific Hilbert-space mappings that preserve complete TDVS scores.The construction covers multiplicative TDVS through a tensor-product space and supports exact metricization for nearest-neighbor search.
3.2 Exact TDVS Metricization: Minimizing Chronos’s Hilbert-space distance or squared distance is exactly equivalent to maximizing the TDVS score.The mapped query and data vectors have unit norm, making the metric formulation ranking-equivalent to TDVS.
3.3 Query-Orthogonal TimeLift: Query-Orthogonal TimeLift appends semantic components to data representations and zero components to queries, changing data–data distances without changing query–data scores or rankings.This decouples indexing geometry from the TDVS objective and allows semantic influence on data geometry to be adjusted independently.
3.3 Query-Orthogonal TimeLift: The parameter κ controls the geometry: κ=0 recovers the base geometry, while larger values strengthen semantic influence and connectivity across distant timestamps.TANGO addresses the resulting locality–connectivity trade-off by assigning layer-specific κℓ values while preserving the same TDVS ordering.

4 TANGO: A TDVS-NATIVE GRAPH INDEX

TANGO is a TDVS-native hierarchical graph index that assigns layer-specific geometries while traversing with the exact TDVS score. Temporal-factor caching reduces repeated computation and supports efficient insertion and querying.

Layered graph geometry: TANGO applies distinct TimeLift parameters across graph layers, strengthening semantic connectivity above while preserving temporal locality at the base.Its schedule satisfies 0 ≤ κ_0 ≤ κ_1 ≤ ··· ≤ κ_L.
Query processing: TANGO performs upper-layer navigation and base-layer exploration under one exact TDVS scoring rule, returning the k candidates with largest TDVS scores.Its unified traversal avoids materializing Chronos representations and requires one semantic inner product plus constant-time scalar operations per visited candidate.
Index structure: TANGO retains HNSW’s hierarchical organization while incorporating TDVS-aware geometry into proximity decisions and traversal.The resulting index supports hierarchical navigation with semantic–temporal proximity computations.
Construction and query scoring: TANGO uses layer-specific squared TimeLift distances for graph construction but the common exact TDVS score for query traversal and candidate ranking.Different κ values alter graph neighborhoods without changing query candidate ordering.
Temporal computation: Temporal-factor caching computes one exponential per inserted vector and one per query, reusing scalar operations across pairwise comparisons and graph layers.The cached factors are independent of layer-specific κ values.

5 EXPERIMENTAL EVALUATION

The evaluation compares TANGO with graph-based methods on query and index performance, temporal robustness, and online insertion. Experiments use controlled hardware and implementation settings.

Evaluation goals: The evaluation addresses query and index performance, robustness across temporal settings, and efficiency of online insertion.These questions correspond to Sections 5.2–5.4.
Evaluation goals: All methods use 64 construction threads and one query-processing thread on a server with 88 physical cores and 881 GiB of memory.Implementations use GCC 11.4, C++17 release mode, -O3, and -march=native.

5.1 Experimental Setup

The experiments cover seven unit-length-embedding datasets from 500K to 10M vectors and evaluate multiplicative and additive TDVS under controlled temporal workloads.

Datasets and queries: Seven datasets span 500K–10M vectors and dimensionalities from 96 to 4096, using exactly 1,000 queries per dataset.Several datasets use disjoint held-out queries or independent public queries.
Temporal workloads: Timestamps are assigned in [0, H], with larger values representing newer objects, because the datasets lack native timestamps.The topic-independent workload samples timestamps independently of semantic clusters.
Temporal workloads: The default setting uses H = τ = 365 days, half-life h = 90 days, α = 0.7, and the topic-correlated workload for both TDVS modes.The study also varies workload type, h, and α.
Metrics and baselines: Query efficiency is measured with Recall–QPS curves, while index evaluation reports construction time and deployed index memory footprint.The footprint includes retained deployed artifacts but excludes temporary construction artifacts.
Metrics and baselines: The experiments use open-source implementations of ip-NSW, ip-NSW+, MAG, and PSP, plus an implementation of NAPG based on its original paper.The default number of returned results is k = 50.

5.2 Overall Performance

TANGO consistently outperforms graph-based competitors in query performance and index construction across TDVS modes and datasets. It remains competitive across temporal workloads while maintaining comparable memory footprints.

Query performance: 3.50× higher query throughput at recall 0.99 under multiplicative TDVS is TANGO’s largest reported query speedup over the best competitor.At recall 0.95, the multiplicative speedup reaches 3.06×; additive TDVS reaches 2.41× and 2.44× at recalls 0.95 and 0.99.
Query performance: TANGO achieves the best query performance under both multiplicative and additive TDVS across the evaluated datasets.Its advantage is often larger on high-dimensional, large-scale datasets and in the high-recall region.
Index performance: 4.05× faster index construction is TANGO’s maximum advantage over the fastest competitor across all seven datasets.All methods have similar memory footprints because they use sparse graphs with comparable connectivity budgets.

5.3 Robustness to Temporal Settings

TANGO remains robust as temporal decay and semantic–temporal weighting change, consistently delivering the best query performance across the evaluated settings.

Topic-independent setting: Removing semantic–temporal correlation by independently sampling timestamps weakens the alignment between semantic and temporal neighborhoods.
Half-life sensitivity: TANGO achieves the best query performance in all six half-life settings across multiplicative and additive TDVS.The half-lives are h ∈ {30, 90, 180}; smaller values increase temporal selectivity, while larger values emphasize semantic similarity.
Half-life sensitivity: At recall 0.95, TANGO outperforms the best-performing competitor by 2.00–2.21× under multiplicative TDVS and 1.41–1.70× under additive TDVS.
Semantic–temporal weighting: TANGO achieves the best query performance for every additive-TDVS weight α ∈ {0.3, 0.5, 0.7, 0.9}.Smaller α gives more weight to temporal freshness, whereas larger α emphasizes semantic similarity.
Semantic–temporal weighting: At recall 0.95, TANGO achieves speedups of 1.48–2.43× over the best-performing competitor under additive TDVS.The largest gain occurs at α = 0.3 and generally narrows as α increases.

5.4 Online Insertion Performance

TANGO supports online insertion while maintaining stable insertion throughput and robust query performance as the index grows.

Insertion throughput: Insertion throughput remains stable and improves slightly as the index grows under both TDVS modes.The initial index contains the oldest 50% of MSMARCO-10M vectors; the remaining 50% are inserted in five timestamp-ordered batches using one thread.
Insertion throughput: Later arrivals benefit from increasingly well-covered recent-time neighborhoods, facilitating efficient insertion.
Query performance: TANGO maintains stable query performance throughout index growth at target recalls of 0.90, 0.95, and 0.99.

6 RELATED WORK

Prior time-aware retrieval methods mainly filter or rerank around static semantic search, whereas TDVS incorporates continuous temporal decay directly into the vector-search objective.

Time-aware retrieval and vector search: Filter-based methods use temporal metadata or predicates to restrict eligibility while leaving the underlying semantic ranking objective unchanged.
Time-aware retrieval and vector search: Rerank-based methods first retrieve candidates under a static semantic objective and then incorporate recency through fusion or post-retrieval reranking.
Time-aware retrieval and vector search: TDVS keeps all items eligible and incorporates continuous temporal decay directly into the vector-search objective.This provides a native formulation for freshness-sensitive workloads in which relevance evolves continuously.
Kernel and feature mapping: Chronos preserves an exact metric formulation for TDVS without kernel approximation or explicit high-dimensional transformed representations.This avoids approximation error and feature-expansion overhead.

7 CONCLUSIONS

The paper formalizes TDVS and develops exact reduction and metric frameworks before introducing TANGO, a graph index designed for temporal and semantic search. Experiments show consistent performance advantages and robustness across temporal settings.

Contributions: TDVS jointly models semantic similarity and temporal freshness in the search objective.
Contributions: STR enables existing MIPS indexes to support TDVS through an exact reduction, while Chronos provides a TDVS-native metric framework with controllable geometry.
Contributions: TANGO combines temporal locality with long-range semantic connectivity and supports efficient online insertion.
Evaluation: Across seven real-world datasets, TANGO consistently outperforms state-of-the-art graph-based methods in query and index performance and remains robust across diverse temporal settings.