diff --git a/libs/gui/BLASTBufferQueue.cpp b/libs/gui/BLASTBufferQueue.cpp
index 797d6ae..60603ba 100644
--- a/libs/gui/BLASTBufferQueue.cpp
+++ b/libs/gui/BLASTBufferQueue.cpp
@@ -587,9 +587,23 @@
         t->setDesiredPresentTime(bufferItem.mTimestamp);
     }
 
-    if (!mNextFrameTimelineInfoQueue.empty()) {
-        t->setFrameTimelineInfo(mNextFrameTimelineInfoQueue.front());
-        mNextFrameTimelineInfoQueue.pop();
+    // Drop stale frame timeline infos
+    while (!mPendingFrameTimelines.empty() &&
+           mPendingFrameTimelines.front().first < bufferItem.mFrameNumber) {
+        ATRACE_FORMAT_INSTANT("dropping stale frameNumber: %" PRIu64 " vsyncId: %" PRId64,
+                              mPendingFrameTimelines.front().first,
+                              mPendingFrameTimelines.front().second.vsyncId);
+        mPendingFrameTimelines.pop();
+    }
+
+    if (!mPendingFrameTimelines.empty() &&
+        mPendingFrameTimelines.front().first == bufferItem.mFrameNumber) {
+        ATRACE_FORMAT_INSTANT("Transaction::setFrameTimelineInfo frameNumber: %" PRIu64
+                              " vsyncId: %" PRId64,
+                              bufferItem.mFrameNumber,
+                              mPendingFrameTimelines.front().second.vsyncId);
+        t->setFrameTimelineInfo(mPendingFrameTimelines.front().second);
+        mPendingFrameTimelines.pop();
     }
 
     {
@@ -653,6 +667,7 @@
     {
         std::unique_lock _lock{mMutex};
         BBQ_TRACE();
+
         const bool syncTransactionSet = mTransactionReadyCallback != nullptr;
         BQA_LOGV("onFrameAvailable-start syncTransactionSet=%s", boolToString(syncTransactionSet));
 
@@ -847,12 +862,13 @@
         return mBbq->setFrameRate(frameRate, compatibility, changeFrameRateStrategy);
     }
 
-    status_t setFrameTimelineInfo(const FrameTimelineInfo& frameTimelineInfo) override {
+    status_t setFrameTimelineInfo(uint64_t frameNumber,
+                                  const FrameTimelineInfo& frameTimelineInfo) override {
         std::unique_lock _lock{mMutex};
         if (mDestroyed) {
             return DEAD_OBJECT;
         }
-        return mBbq->setFrameTimelineInfo(frameTimelineInfo);
+        return mBbq->setFrameTimelineInfo(frameNumber, frameTimelineInfo);
     }
 
     void destroy() override {
@@ -874,9 +890,12 @@
     return t.setFrameRate(mSurfaceControl, frameRate, compatibility, shouldBeSeamless).apply();
 }
 
-status_t BLASTBufferQueue::setFrameTimelineInfo(const FrameTimelineInfo& frameTimelineInfo) {
+status_t BLASTBufferQueue::setFrameTimelineInfo(uint64_t frameNumber,
+                                                const FrameTimelineInfo& frameTimelineInfo) {
+    ATRACE_FORMAT("%s(%s) frameNumber: %" PRIu64 " vsyncId: %" PRId64, __func__, mName.c_str(),
+                  frameNumber, frameTimelineInfo.vsyncId);
     std::unique_lock _lock{mMutex};
-    mNextFrameTimelineInfoQueue.push(frameTimelineInfo);
+    mPendingFrameTimelines.push({frameNumber, frameTimelineInfo});
     return OK;
 }
 
diff --git a/libs/gui/Surface.cpp b/libs/gui/Surface.cpp
index edb18a8..b18bf5b 100644
--- a/libs/gui/Surface.cpp
+++ b/libs/gui/Surface.cpp
@@ -1863,6 +1863,7 @@
 
 int Surface::dispatchSetFrameTimelineInfo(va_list args) {
     ATRACE_CALL();
+    auto frameNumber = static_cast<uint64_t>(va_arg(args, uint64_t));
     auto frameTimelineVsyncId = static_cast<int64_t>(va_arg(args, int64_t));
     auto inputEventId = static_cast<int32_t>(va_arg(args, int32_t));
     auto startTimeNanos = static_cast<int64_t>(va_arg(args, int64_t));
@@ -1872,7 +1873,7 @@
     ftlInfo.vsyncId = frameTimelineVsyncId;
     ftlInfo.inputEventId = inputEventId;
     ftlInfo.startTimeNanos = startTimeNanos;
-    return setFrameTimelineInfo(ftlInfo);
+    return setFrameTimelineInfo(frameNumber, ftlInfo);
 }
 
 bool Surface::transformToDisplayInverse() const {
@@ -2641,7 +2642,8 @@
     return NO_ERROR;
 }
 
-status_t Surface::setFrameTimelineInfo(const FrameTimelineInfo& /*frameTimelineInfo*/) {
+status_t Surface::setFrameTimelineInfo(uint64_t /*frameNumber*/,
+                                       const FrameTimelineInfo& /*frameTimelineInfo*/) {
     // ISurfaceComposer no longer supports setFrameTimelineInfo
     return BAD_VALUE;
 }
diff --git a/libs/gui/fuzzer/libgui_bufferQueue_fuzzer.cpp b/libs/gui/fuzzer/libgui_bufferQueue_fuzzer.cpp
index 761f08f..17f4c63 100644
--- a/libs/gui/fuzzer/libgui_bufferQueue_fuzzer.cpp
+++ b/libs/gui/fuzzer/libgui_bufferQueue_fuzzer.cpp
@@ -130,7 +130,7 @@
     queue->setFrameRate(mFdp.ConsumeFloatingPoint<float>(), mFdp.ConsumeIntegral<int8_t>(),
                         mFdp.ConsumeBool() /*shouldBeSeamless*/);
     FrameTimelineInfo info;
-    queue->setFrameTimelineInfo(info);
+    queue->setFrameTimelineInfo(mFdp.ConsumeIntegral<uint64_t>(), info);
 
     ManageResourceHandle handle(&mFdp);
     queue->setSidebandStream(handle.getStream());
diff --git a/libs/gui/include/gui/BLASTBufferQueue.h b/libs/gui/include/gui/BLASTBufferQueue.h
index 001d8e5..c93ab86 100644
--- a/libs/gui/include/gui/BLASTBufferQueue.h
+++ b/libs/gui/include/gui/BLASTBufferQueue.h
@@ -106,7 +106,7 @@
     void update(const sp<SurfaceControl>& surface, uint32_t width, uint32_t height, int32_t format);
 
     status_t setFrameRate(float frameRate, int8_t compatibility, bool shouldBeSeamless);
-    status_t setFrameTimelineInfo(const FrameTimelineInfo& info);
+    status_t setFrameTimelineInfo(uint64_t frameNumber, const FrameTimelineInfo& info);
 
     void setSidebandStream(const sp<NativeHandle>& stream);
 
@@ -231,7 +231,7 @@
     std::vector<std::tuple<uint64_t /* framenumber */, SurfaceComposerClient::Transaction>>
             mPendingTransactions GUARDED_BY(mMutex);
 
-    std::queue<FrameTimelineInfo> mNextFrameTimelineInfoQueue GUARDED_BY(mMutex);
+    std::queue<std::pair<uint64_t, FrameTimelineInfo>> mPendingFrameTimelines GUARDED_BY(mMutex);
 
     // Tracks the last acquired frame number
     uint64_t mLastAcquiredFrameNumber GUARDED_BY(mMutex) = 0;
diff --git a/libs/gui/include/gui/Surface.h b/libs/gui/include/gui/Surface.h
index b9ccdc9..39a59e4 100644
--- a/libs/gui/include/gui/Surface.h
+++ b/libs/gui/include/gui/Surface.h
@@ -213,7 +213,7 @@
 
     virtual status_t setFrameRate(float frameRate, int8_t compatibility,
                                   int8_t changeFrameRateStrategy);
-    virtual status_t setFrameTimelineInfo(const FrameTimelineInfo& info);
+    virtual status_t setFrameTimelineInfo(uint64_t frameNumber, const FrameTimelineInfo& info);
 
 protected:
     virtual ~Surface();